![[BACK]](/icons/back.gif){kind=icon}
Return to bitmap.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh|
Return to bitmap.c CVS log | Up to [local] / src / usr.bin / ssh |
1.1 djm 1: /*
2: * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
3: *
4: * Permission to use, copy, modify, and distribute this software for any
5: * purpose with or without fee is hereby granted, provided that the above
6: * copyright notice and this permission notice appear in all copies.
7: *
8: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15: */
16:
17: #include <sys/types.h>
18: #include <string.h>
19: #include <stdlib.h>
20:
21: #include "bitmap.h"
22:
23: #define BITMAP_WTYPE u_int
24: #define BITMAP_MAX (1<<24)
25: #define BITMAP_BYTES (sizeof(BITMAP_WTYPE))
26: #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)
27: #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)
28: struct bitmap {
29: BITMAP_WTYPE *d;
30: size_t len; /* number of words allocated */
31: size_t top; /* index of top word allocated */
32: };
33:
34: struct bitmap *
35: bitmap_new(void)
36: {
37: struct bitmap *ret;
38:
39: if ((ret = calloc(1, sizeof(*ret))) == NULL)
40: return NULL;
41: if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
42: free(ret);
43: return NULL;
44: }
45: ret->len = 1;
46: ret->top = 0;
47: return ret;
48: }
49:
50: void
51: bitmap_free(struct bitmap *b)
52: {
53: if (b != NULL && b->d != NULL) {
54: memset(b->d, 0, b->len);
55: free(b->d);
56: }
57: free(b);
58: }
59:
60: void
61: bitmap_zero(struct bitmap *b)
62: {
63: memset(b->d, 0, b->len * BITMAP_BYTES);
64: b->top = 0;
65: }
66:
67: int
68: bitmap_test_bit(struct bitmap *b, u_int n)
69: {
70: if (b->top >= b->len)
71: return 0; /* invalid */
72: if (b->len == 0 || (n / BITMAP_BITS) > b->top)
73: return 0;
74: return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
75: }
76:
77: static int
78: reserve(struct bitmap *b, u_int n)
79: {
80: BITMAP_WTYPE *tmp;
81: size_t nlen;
82:
83: if (b->top >= b->len || n > BITMAP_MAX)
84: return -1; /* invalid */
85: nlen = (n / BITMAP_BITS) + 1;
86: if (b->len < nlen) {
87: if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL)
88: return -1;
89: b->d = tmp;
90: memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES);
91: b->len = nlen;
92: }
93: return 0;
94: }
95:
96: int
97: bitmap_set_bit(struct bitmap *b, u_int n)
98: {
99: int r;
100: size_t offset;
101:
102: if ((r = reserve(b, n)) != 0)
103: return r;
104: offset = n / BITMAP_BITS;
105: if (offset > b->top)
106: b->top = offset;
107: b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
108: return 0;
109: }
110:
111: /* Resets b->top to point to the most significant bit set in b->d */
112: static void
113: retop(struct bitmap *b)
114: {
115: if (b->top >= b->len)
116: return;
117: while (b->top > 0 && b->d[b->top] == 0)
118: b->top--;
119: }
120:
121: void
122: bitmap_clear_bit(struct bitmap *b, u_int n)
123: {
124: size_t offset;
125:
126: if (b->top >= b->len || n > BITMAP_MAX)
127: return; /* invalid */
128: offset = n / BITMAP_BITS;
129: if (offset > b->top)
130: return;
131: b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
132: /* The top may have changed as a result of the clear */
133: retop(b);
134: }
135:
136: size_t
137: bitmap_nbits(struct bitmap *b)
138: {
139: size_t bits;
140: BITMAP_WTYPE w;
141:
142: retop(b);
143: if (b->top >= b->len)
144: return 0; /* invalid */
145: if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
146: return 0;
147: /* Find MSB set */
148: w = b->d[b->top];
149: bits = (b->top + 1) * BITMAP_BITS;
150: while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
151: w <<= 1;
152: bits--;
153: }
154: return bits;
155: }
156:
157: size_t
158: bitmap_nbytes(struct bitmap *b)
159: {
160: return (bitmap_nbits(b) + 7) / 8;
161: }
162:
163: int
164: bitmap_to_string(struct bitmap *b, void *p, size_t l)
165: {
166: u_char *s = (u_char *)p;
167: size_t i, j, k, need = bitmap_nbytes(b);
168:
169: if (l < need || b->top >= b->len)
170: return -1;
171: if (l > need)
172: l = need;
173: /* Put the bytes from LSB backwards */
174: for (i = k = 0; i < b->top + 1; i++) {
175: for (j = 0; j < BITMAP_BYTES; j++) {
176: if (k >= l)
177: break;
178: s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
179: }
180: }
181: return 0;
182: }
183:
184: int
185: bitmap_from_string(struct bitmap *b, const void *p, size_t l)
186: {
187: int r;
188: size_t i, offset, shift;
189: u_char *s = (u_char *)p;
190:
191: if (l > BITMAP_MAX / 8)
192: return -1;
193: if ((r = reserve(b, l * 8)) != 0)
194: return r;
195: bitmap_zero(b);
196: if (l == 0)
197: return 0;
198: b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
199: shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
200: for (i = 0; i < l; i++) {
201: b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
202: if (shift == 0) {
203: offset--;
204: shift = BITMAP_BITS - 8;
205: } else
206: shift -= 8;
207: }
208: retop(b);
209: return 0;
210: }
211:
212: #ifdef BITMAP_TEST
213:
214: /* main() test against OpenSSL BN */
215: #include <err.h>
216: #include <openssl/bn.h>
217: #include <stdio.h>
218: #include <stdarg.h>
219:
220: #define LIM 131
221: #define FAIL(...) fail(__FILE__, __LINE__, __VA_ARGS__)
222:
223: void
224: bitmap_dump(struct bitmap *b, FILE *f)
225: {
226: size_t i;
227:
228: fprintf(f, "bitmap %p len=%zu top=%zu d =", b, b->len, b->top);
229: for (i = 0; i < b->len; i++) {
230: fprintf(f, " %0*llx", (int)BITMAP_BITS / 4,
231: (unsigned long long)b->d[i]);
232: }
233: fputc('\n', f);
234: }
235:
236: static void
237: fail(char *file, int line, char *fmt, ...)
238: {
239: va_list ap;
240:
241: fprintf(stderr, "%s:%d ", file, line);
242: va_start(ap, fmt);
243: vfprintf(stderr, fmt, ap);
244: va_end(ap);
245: fputc('\n', stdout);
246: /* abort(); */
247: exit(1);
248: }
249:
250: static void
251: dump(const char *s, const u_char *buf, size_t l)
252: {
253: size_t i;
254:
255: fprintf(stderr, "%s len %zu = ", s, l);
256: for (i = 0; i < l; i++)
257: fprintf(stderr, "%02x ", buf[i]);
258: fputc('\n', stderr);
259: }
260:
261: int main(void) {
262: struct bitmap *b = bitmap_new();
263: BIGNUM *bn = BN_new();
264: size_t len;
265: int i, j, k, n;
266: u_char bbuf[1024], bnbuf[1024];
267: int r;
268:
269: for (i = -1; i < LIM; i++) {
270: fputc('i', stdout);
271: fflush(stdout);
272: for (j = -1; j < LIM; j++) {
273: for (k = -1; k < LIM; k++) {
274: bitmap_zero(b);
275: BN_clear(bn);
276: /* Test setting bits */
277: if (i > 0 && bitmap_set_bit(b, i) != 0)
278: FAIL("bitmap_set_bit %d fail", i);
279: if (j > 0 && bitmap_set_bit(b, j) != 0)
280: FAIL("bitmap_set_bit %d fail", j);
281: if (k > 0 && bitmap_set_bit(b, k) != 0)
282: FAIL("bitmap_set_bit %d fail", k);
283: if ((i > 0 && BN_set_bit(bn, i) != 1) ||
284: (j > 0 && BN_set_bit(bn, j) != 1) ||
285: (k > 0 && BN_set_bit(bn, k) != 1))
286: FAIL("BN_set_bit fail");
287: for (n = 0; n < LIM; n++) {
288: if (BN_is_bit_set(bn, n) !=
289: bitmap_test_bit(b, n)) {
290: FAIL("miss %d/%d/%d %d "
291: "%d %d", i, j, k, n,
292: BN_is_bit_set(bn, n),
293: bitmap_test_bit(b, n));
294: }
295: }
296: /* Test length calculations */
297: if (BN_num_bytes(bn) != (int)bitmap_nbytes(b)) {
298: FAIL("bytes %d/%d/%d %d != %zu",
299: i, j, k, BN_num_bytes(bn),
300: bitmap_nbytes(b));
301: }
302: if (BN_num_bits(bn) != (int)bitmap_nbits(b)) {
303: FAIL("bits %d/%d/%d %d != %zu",
304: i, j, k, BN_num_bits(bn),
305: bitmap_nbits(b));
306: }
307: /* Test serialisation */
308: len = bitmap_nbytes(b);
309: memset(bbuf, 0xfc, sizeof(bbuf));
310: if (bitmap_to_string(b, bbuf,
311: sizeof(bbuf)) != 0)
312: FAIL("bitmap_to_string %d/%d/%d",
313: i, j, k);
314: for (n = len; n < (int)sizeof(bbuf); n++) {
315: if (bbuf[n] != 0xfc)
316: FAIL("bad string "
317: "%d/%d/%d %d 0x%02x",
318: i, j, k, n, bbuf[n]);
319: }
320: if ((r = BN_bn2bin(bn, bnbuf)) < 0)
321: FAIL("BN_bn2bin %d/%d/%d",
322: i, j, k);
323: if ((size_t)r != len)
324: FAIL("len bad %d/%d/%d", i, j, k);
325: if (memcmp(bbuf, bnbuf, len) != 0) {
326: dump("bbuf", bbuf, sizeof(bbuf));
327: dump("bnbuf", bnbuf, sizeof(bnbuf));
328: FAIL("buf bad %d/%d/%d", i, j, k);
329: }
330: /* Test deserialisation */
331: bitmap_zero(b);
332: if (bitmap_from_string(b, bnbuf, len) != 0)
333: FAIL("bitmap_to_string %d/%d/%d",
334: i, j, k);
335: for (n = 0; n < LIM; n++) {
336: if (BN_is_bit_set(bn, n) !=
337: bitmap_test_bit(b, n)) {
338: FAIL("miss %d/%d/%d %d "
339: "%d %d", i, j, k, n,
340: BN_is_bit_set(bn, n),
341: bitmap_test_bit(b, n));
342: }
343: }
344: /* Test clearing bits */
345: for (n = 0; n < LIM; n++) {
346: if (bitmap_set_bit(b, n) != 0) {
347: bitmap_dump(b, stderr);
348: FAIL("bitmap_set_bit %d "
349: "fail", n);
350: }
351: if (BN_set_bit(bn, n) != 1)
352: FAIL("BN_set_bit fail");
353: }
354: if (i > 0) {
355: bitmap_clear_bit(b, i);
356: BN_clear_bit(bn, i);
357: }
358: if (j > 0) {
359: bitmap_clear_bit(b, j);
360: BN_clear_bit(bn, j);
361: }
362: if (k > 0) {
363: bitmap_clear_bit(b, k);
364: BN_clear_bit(bn, k);
365: }
366: for (n = 0; n < LIM; n++) {
367: if (BN_is_bit_set(bn, n) !=
368: bitmap_test_bit(b, n)) {
369: bitmap_dump(b, stderr);
370: FAIL("cmiss %d/%d/%d %d "
371: "%d %d", i, j, k, n,
372: BN_is_bit_set(bn, n),
373: bitmap_test_bit(b, n));
374: }
375: }
376: }
377: }
378: }
379: fputc('\n', stdout);
380: bitmap_free(b);
381: BN_free(bn);
382:
383: return 0;
384: }
385: #endif