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