OpenCoverage

bitmap.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/openssh/src/bitmap.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */-
2/*-
3 * Copyright (c) 2015 Damien Miller <djm@mindrot.org>-
4 *-
5 * Permission to use, copy, modify, and distribute this software for any-
6 * purpose with or without fee is hereby granted, provided that the above-
7 * copyright notice and this permission notice appear in all copies.-
8 *-
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES-
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF-
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR-
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES-
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN-
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF-
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.-
16 */-
17-
18#include "includes.h"-
19-
20#include <sys/types.h>-
21#include <string.h>-
22#include <stdlib.h>-
23-
24#include "bitmap.h"-
25-
26#define BITMAP_WTYPE u_int-
27#define BITMAP_MAX (1<<24)-
28#define BITMAP_BYTES (sizeof(BITMAP_WTYPE))-
29#define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)-
30#define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)-
31struct bitmap {-
32 BITMAP_WTYPE *d;-
33 size_t len; /* number of words allocated */-
34 size_t top; /* index of top word allocated */-
35};-
36-
37struct bitmap *-
38bitmap_new(void)-
39{-
40 struct bitmap *ret;-
41-
42 if ((ret = calloc(1, sizeof(*ret))) == NULL)
(ret = calloc(...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • test_bitmap
0-1
43 return NULL;
never executed: return ((void *)0) ;
0
44 if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
(ret->d = call...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • test_bitmap
0-1
45 free(ret);-
46 return NULL;
never executed: return ((void *)0) ;
0
47 }-
48 ret->len = 1;-
49 ret->top = 0;-
50 return ret;
executed 1 time by 1 test: return ret;
Executed by:
  • test_bitmap
1
51}-
52-
53void-
54bitmap_free(struct bitmap *b)-
55{-
56 if (b != NULL && b->d != NULL) {
b != ((void *)0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • test_bitmap
FALSEnever evaluated
b->d != ((void *)0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • test_bitmap
FALSEnever evaluated
0-1
57 bitmap_zero(b);-
58 free(b->d);-
59 b->d = NULL;-
60 }
executed 1 time by 1 test: end of block
Executed by:
  • test_bitmap
1
61 free(b);-
62}
executed 1 time by 1 test: end of block
Executed by:
  • test_bitmap
1
63-
64void-
65bitmap_zero(struct bitmap *b)-
66{-
67 memset(b->d, 0, b->len * BITMAP_BYTES);-
68 b->top = 0;-
69}
executed 6899905 times by 1 test: end of block
Executed by:
  • test_bitmap
6899905
70-
71int-
72bitmap_test_bit(struct bitmap *b, u_int n)-
73{-
74 if (b->top >= b->len)
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 903887424 times by 1 test
Evaluated by:
  • test_bitmap
0-903887424
75 return 0; /* invalid */
never executed: return 0;
0
76 if (b->len == 0 || (n / BITMAP_BITS) > b->top)
b->len == 0Description
TRUEnever evaluated
FALSEevaluated 903887424 times by 1 test
Evaluated by:
  • test_bitmap
(n / (sizeof(u...* 8)) > b->topDescription
TRUEevaluated 91167192 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 812720232 times by 1 test
Evaluated by:
  • test_bitmap
0-903887424
77 return 0;
executed 91167192 times by 1 test: return 0;
Executed by:
  • test_bitmap
91167192
78 return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
executed 812720232 times by 1 test: return (b->d[n / (sizeof(u_int) * 8)] >> (n & ((u_int)(sizeof(u_int) * 8) - 1))) & 1;
Executed by:
  • test_bitmap
812720232
79}-
80-
81static int-
82reserve(struct bitmap *b, u_int n)-
83{-
84 BITMAP_WTYPE *tmp;-
85 size_t nlen;-
86-
87 if (b->top >= b->len || n > BITMAP_MAX)
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 310443408 times by 1 test
Evaluated by:
  • test_bitmap
n > (1<<24)Description
TRUEnever evaluated
FALSEevaluated 310443408 times by 1 test
Evaluated by:
  • test_bitmap
0-310443408
88 return -1; /* invalid */
never executed: return -1;
0
89 nlen = (n / BITMAP_BITS) + 1;-
90 if (b->len < nlen) {
b->len < nlenDescription
TRUEevaluated 4 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 310443404 times by 1 test
Evaluated by:
  • test_bitmap
4-310443404
91 if ((tmp = recallocarray(b->d, b->len,
(tmp = recallo...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4 times by 1 test
Evaluated by:
  • test_bitmap
0-4
92 nlen, BITMAP_BYTES)) == NULL)
(tmp = recallo...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4 times by 1 test
Evaluated by:
  • test_bitmap
0-4
93 return -1;
never executed: return -1;
0
94 b->d = tmp;-
95 b->len = nlen;-
96 }
executed 4 times by 1 test: end of block
Executed by:
  • test_bitmap
4
97 return 0;
executed 310443408 times by 1 test: return 0;
Executed by:
  • test_bitmap
310443408
98}-
99-
100int-
101bitmap_set_bit(struct bitmap *b, u_int n)-
102{-
103 int r;-
104 size_t offset;-
105-
106 if ((r = reserve(b, n)) != 0)
(r = reserve(b, n)) != 0Description
TRUEnever evaluated
FALSEevaluated 308143440 times by 1 test
Evaluated by:
  • test_bitmap
0-308143440
107 return r;
never executed: return r;
0
108 offset = n / BITMAP_BITS;-
109 if (offset > b->top)
offset > b->topDescription
TRUEevaluated 6490723 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 301652717 times by 1 test
Evaluated by:
  • test_bitmap
6490723-301652717
110 b->top = offset;
executed 6490723 times by 1 test: b->top = offset;
Executed by:
  • test_bitmap
6490723
111 b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);-
112 return 0;
executed 308143440 times by 1 test: return 0;
Executed by:
  • test_bitmap
308143440
113}-
114-
115/* Resets b->top to point to the most significant bit set in b->d */-
116static void-
117retop(struct bitmap *b)-
118{-
119 if (b->top >= b->len)
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 18347471 times by 1 test
Evaluated by:
  • test_bitmap
0-18347471
120 return;
never executed: return;
0
121 while (b->top > 0 && b->d[b->top] == 0)
b->top > 0Description
TRUEevaluated 18167793 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 179684 times by 1 test
Evaluated by:
  • test_bitmap
b->d[b->top] == 0Description
TRUEevaluated 6 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 18167787 times by 1 test
Evaluated by:
  • test_bitmap
6-18167793
122 b->top--;
executed 6 times by 1 test: b->top--;
Executed by:
  • test_bitmap
6
123}
executed 18347471 times by 1 test: end of block
Executed by:
  • test_bitmap
18347471
124-
125void-
126bitmap_clear_bit(struct bitmap *b, u_int n)-
127{-
128 size_t offset;-
129-
130 if (b->top >= b->len || n > BITMAP_MAX)
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 6847632 times by 1 test
Evaluated by:
  • test_bitmap
n > (1<<24)Description
TRUEnever evaluated
FALSEevaluated 6847632 times by 1 test
Evaluated by:
  • test_bitmap
0-6847632
131 return; /* invalid */
never executed: return;
0
132 offset = n / BITMAP_BITS;-
133 if (offset > b->top)
offset > b->topDescription
TRUEnever evaluated
FALSEevaluated 6847632 times by 1 test
Evaluated by:
  • test_bitmap
0-6847632
134 return;
never executed: return;
0
135 b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));-
136 /* The top may have changed as a result of the clear */-
137 retop(b);-
138}
executed 6847632 times by 1 test: end of block
Executed by:
  • test_bitmap
6847632
139-
140size_t-
141bitmap_nbits(struct bitmap *b)-
142{-
143 size_t bits;-
144 BITMAP_WTYPE w;-
145-
146 retop(b);-
147 if (b->top >= b->len)
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 9199872 times by 1 test
Evaluated by:
  • test_bitmap
0-9199872
148 return 0; /* invalid */
never executed: return 0;
0
149 if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
b->len == 0Description
TRUEnever evaluated
FALSEevaluated 9199872 times by 1 test
Evaluated by:
  • test_bitmap
b->top == 0Description
TRUEevaluated 143748 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 9056124 times by 1 test
Evaluated by:
  • test_bitmap
b->d[0] == 0Description
TRUEevaluated 4 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 143744 times by 1 test
Evaluated by:
  • test_bitmap
0-9199872
150 return 0;
executed 4 times by 1 test: return 0;
Executed by:
  • test_bitmap
4
151 /* Find MSB set */-
152 w = b->d[b->top];-
153 bits = (b->top + 1) * BITMAP_BITS;-
154 while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
!(w & ((u_int)...t) * 8) - 1)))Description
TRUEevaluated 134459152 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 9199868 times by 1 test
Evaluated by:
  • test_bitmap
9199868-134459152
155 w <<= 1;-
156 bits--;-
157 }
executed 134459152 times by 1 test: end of block
Executed by:
  • test_bitmap
134459152
158 return bits;
executed 9199868 times by 1 test: return bits;
Executed by:
  • test_bitmap
9199868
159}-
160-
161size_t-
162bitmap_nbytes(struct bitmap *b)-
163{-
164 return (bitmap_nbits(b) + 7) / 8;
executed 6899904 times by 1 test: return (bitmap_nbits(b) + 7) / 8;
Executed by:
  • test_bitmap
6899904
165}-
166-
167int-
168bitmap_to_string(struct bitmap *b, void *p, size_t l)-
169{-
170 u_char *s = (u_char *)p;-
171 size_t i, j, k, need = bitmap_nbytes(b);-
172-
173 if (l < need || b->top >= b->len)
l < needDescription
TRUEnever evaluated
FALSEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
b->top >= b->lenDescription
TRUEnever evaluated
FALSEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
0-2299968
174 return -1;
never executed: return -1;
0
175 if (l > need)
l > needDescription
TRUEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
FALSEnever evaluated
0-2299968
176 l = need;
executed 2299968 times by 1 test: l = need;
Executed by:
  • test_bitmap
2299968
177 /* Put the bytes from LSB backwards */-
178 for (i = k = 0; i < b->top + 1; i++) {
i < b->top + 1Description
TRUEevaluated 8129916 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
2299968-8129916
179 for (j = 0; j < BITMAP_BYTES; j++) {
j < (sizeof(u_int))Description
TRUEevaluated 30946383 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 6522524 times by 1 test
Evaluated by:
  • test_bitmap
6522524-30946383
180 if (k >= l)
k >= lDescription
TRUEevaluated 1607392 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 29338991 times by 1 test
Evaluated by:
  • test_bitmap
1607392-29338991
181 break;
executed 1607392 times by 1 test: break;
Executed by:
  • test_bitmap
1607392
182 s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;-
183 }
executed 29338991 times by 1 test: end of block
Executed by:
  • test_bitmap
29338991
184 }
executed 8129916 times by 1 test: end of block
Executed by:
  • test_bitmap
8129916
185 return 0;
executed 2299968 times by 1 test: return 0;
Executed by:
  • test_bitmap
2299968
186}-
187-
188int-
189bitmap_from_string(struct bitmap *b, const void *p, size_t l)-
190{-
191 int r;-
192 size_t i, offset, shift;-
193 const u_char *s = (const u_char *)p;-
194-
195 if (l > BITMAP_MAX / 8)
l > (1<<24) / 8Description
TRUEnever evaluated
FALSEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
0-2299968
196 return -1;
never executed: return -1;
0
197 if ((r = reserve(b, l * 8)) != 0)
(r = reserve(b, l * 8)) != 0Description
TRUEnever evaluated
FALSEevaluated 2299968 times by 1 test
Evaluated by:
  • test_bitmap
0-2299968
198 return r;
never executed: return r;
0
199 bitmap_zero(b);-
200 if (l == 0)
l == 0Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 2299967 times by 1 test
Evaluated by:
  • test_bitmap
1-2299967
201 return 0;
executed 1 time by 1 test: return 0;
Executed by:
  • test_bitmap
1
202 b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;-
203 shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;-
204 for (i = 0; i < l; i++) {
i < lDescription
TRUEevaluated 29338991 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 2299967 times by 1 test
Evaluated by:
  • test_bitmap
2299967-29338991
205 b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;-
206 if (shift == 0) {
shift == 0Description
TRUEevaluated 8129915 times by 1 test
Evaluated by:
  • test_bitmap
FALSEevaluated 21209076 times by 1 test
Evaluated by:
  • test_bitmap
8129915-21209076
207 offset--;-
208 shift = BITMAP_BITS - 8;-
209 } else
executed 8129915 times by 1 test: end of block
Executed by:
  • test_bitmap
8129915
210 shift -= 8;
executed 21209076 times by 1 test: shift -= 8;
Executed by:
  • test_bitmap
21209076
211 }-
212 retop(b);-
213 return 0;
executed 2299967 times by 1 test: return 0;
Executed by:
  • test_bitmap
2299967
214}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2