![[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:
! 158: size_t
! 159: bitmap_nbytes(struct bitmap *b)
! 160: {
! 161: return (bitmap_nbits(b) + 7) / 8;
! 162: }
! 163:
! 164: int
! 165: bitmap_to_string(struct bitmap *b, void *p, size_t l)
! 166: {
! 167: u_char *s = (u_char *)p;
! 168: size_t i, j, k, need = bitmap_nbytes(b);
! 169:
! 170: if (l < need || b->top >= b->len)
! 171: return -1;
! 172: if (l > need)
! 173: l = need;
! 174: /* Put the bytes from LSB backwards */
! 175: for (i = k = 0; i < b->top + 1; i++) {
! 176: for (j = 0; j < BITMAP_BYTES; j++) {
! 177: if (k >= l)
! 178: break;
! 179: s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
! 180: }
! 181: }
! 182:
! 183: return 0;
! 184: }
! 185:
! 186: int
! 187: bitmap_from_string(struct bitmap *b, const void *p, size_t l)
! 188: {
! 189: int r;
! 190: size_t i, offset, shift;
! 191: u_char *s = (u_char *)p;
! 192:
! 193: if (l > BITMAP_MAX / 8)
! 194: return -1;
! 195: if ((r = reserve(b, l * 8)) != 0)
! 196: return r;
! 197: bitmap_zero(b);
! 198: if (l == 0)
! 199: return 0;
! 200: b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
! 201: shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
! 202: for (i = 0; i < l; i++) {
! 203: b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
! 204: if (shift == 0) {
! 205: offset--;
! 206: shift = BITMAP_BITS - 8;
! 207: } else
! 208: shift -= 8;
! 209: }
! 210: retop(b);
! 211: return 0;
! 212: }
! 213:
! 214: #ifdef BITMAP_TEST
! 215:
! 216: /* main() test against OpenSSL BN */
! 217: #include <err.h>
! 218: #include <openssl/bn.h>
! 219: #include <stdio.h>
! 220: #include <stdarg.h>
! 221:
! 222: #define LIM 131
! 223: #define FAIL(...) fail(__FILE__, __LINE__, __VA_ARGS__)
! 224:
! 225: void
! 226: bitmap_dump(struct bitmap *b, FILE *f)
! 227: {
! 228: size_t i;
! 229:
! 230: fprintf(f, "bitmap %p len=%zu top=%zu d =", b, b->len, b->top);
! 231: for (i = 0; i < b->len; i++) {
! 232: fprintf(f, " %0*llx", (int)BITMAP_BITS / 4,
! 233: (unsigned long long)b->d[i]);
! 234: }
! 235: fputc('\n', f);
! 236: }
! 237:
! 238: static void
! 239: fail(char *file, int line, char *fmt, ...)
! 240: {
! 241: va_list ap;
! 242:
! 243: fprintf(stderr, "%s:%d ", file, line);
! 244: va_start(ap, fmt);
! 245: vfprintf(stderr, fmt, ap);
! 246: va_end(ap);
! 247: fputc('\n', stdout);
! 248: /* abort(); */
! 249: exit(1);
! 250: }
! 251:
! 252: static void
! 253: dump(const char *s, const u_char *buf, size_t l)
! 254: {
! 255: size_t i;
! 256:
! 257: fprintf(stderr, "%s len %zu = ", s, l);
! 258: for (i = 0; i < l; i++)
! 259: fprintf(stderr, "%02x ", buf[i]);
! 260: fputc('\n', stderr);
! 261: }
! 262:
! 263: int main(void) {
! 264: struct bitmap *b = bitmap_new();
! 265: BIGNUM *bn = BN_new();
! 266: size_t len;
! 267: int i, j, k, n;
! 268: u_char bbuf[1024], bnbuf[1024];
! 269: int r;
! 270:
! 271: for (i = -1; i < LIM; i++) {
! 272: fputc('i', stdout);
! 273: fflush(stdout);
! 274: for (j = -1; j < LIM; j++) {
! 275: for (k = -1; k < LIM; k++) {
! 276: bitmap_zero(b);
! 277: BN_clear(bn);
! 278: /* Test setting bits */
! 279: if (i > 0 && bitmap_set_bit(b, i) != 0)
! 280: FAIL("bitmap_set_bit %d fail", i);
! 281: if (j > 0 && bitmap_set_bit(b, j) != 0)
! 282: FAIL("bitmap_set_bit %d fail", j);
! 283: if (k > 0 && bitmap_set_bit(b, k) != 0)
! 284: FAIL("bitmap_set_bit %d fail", k);
! 285: if ((i > 0 && BN_set_bit(bn, i) != 1) ||
! 286: (j > 0 && BN_set_bit(bn, j) != 1) ||
! 287: (k > 0 && BN_set_bit(bn, k) != 1))
! 288: FAIL("BN_set_bit fail");
! 289: for (n = 0; n < LIM; n++) {
! 290: if (BN_is_bit_set(bn, n) !=
! 291: bitmap_test_bit(b, n)) {
! 292: FAIL("miss %d/%d/%d %d "
! 293: "%d %d", i, j, k, n,
! 294: BN_is_bit_set(bn, n),
! 295: bitmap_test_bit(b, n));
! 296: }
! 297: }
! 298: /* Test length calculations */
! 299: if (BN_num_bytes(bn) != (int)bitmap_nbytes(b)) {
! 300: FAIL("bytes %d/%d/%d %d != %zu",
! 301: i, j, k, BN_num_bytes(bn),
! 302: bitmap_nbytes(b));
! 303: }
! 304: if (BN_num_bits(bn) != (int)bitmap_nbits(b)) {
! 305: FAIL("bits %d/%d/%d %d != %zu",
! 306: i, j, k, BN_num_bits(bn),
! 307: bitmap_nbits(b));
! 308: }
! 309: /* Test serialisation */
! 310: len = bitmap_nbytes(b);
! 311: memset(bbuf, 0xfc, sizeof(bbuf));
! 312: if (bitmap_to_string(b, bbuf,
! 313: sizeof(bbuf)) != 0)
! 314: FAIL("bitmap_to_string %d/%d/%d",
! 315: i, j, k);
! 316: for (n = len; n < (int)sizeof(bbuf); n++) {
! 317: if (bbuf[n] != 0xfc)
! 318: FAIL("bad string "
! 319: "%d/%d/%d %d 0x%02x",
! 320: i, j, k, n, bbuf[n]);
! 321: }
! 322: if ((r = BN_bn2bin(bn, bnbuf)) < 0)
! 323: FAIL("BN_bn2bin %d/%d/%d",
! 324: i, j, k);
! 325: if ((size_t)r != len)
! 326: FAIL("len bad %d/%d/%d", i, j, k);
! 327: if (memcmp(bbuf, bnbuf, len) != 0) {
! 328: dump("bbuf", bbuf, sizeof(bbuf));
! 329: dump("bnbuf", bnbuf, sizeof(bnbuf));
! 330: FAIL("buf bad %d/%d/%d", i, j, k);
! 331: }
! 332: /* Test deserialisation */
! 333: bitmap_zero(b);
! 334: if (bitmap_from_string(b, bnbuf, len) != 0)
! 335: FAIL("bitmap_to_string %d/%d/%d",
! 336: i, j, k);
! 337: for (n = 0; n < LIM; n++) {
! 338: if (BN_is_bit_set(bn, n) !=
! 339: bitmap_test_bit(b, n)) {
! 340: FAIL("miss %d/%d/%d %d "
! 341: "%d %d", i, j, k, n,
! 342: BN_is_bit_set(bn, n),
! 343: bitmap_test_bit(b, n));
! 344: }
! 345: }
! 346: /* Test clearing bits */
! 347: for (n = 0; n < LIM; n++) {
! 348: if (bitmap_set_bit(b, n) != 0) {
! 349: bitmap_dump(b, stderr);
! 350: FAIL("bitmap_set_bit %d "
! 351: "fail", n);
! 352: }
! 353: if (BN_set_bit(bn, n) != 1)
! 354: FAIL("BN_set_bit fail");
! 355: }
! 356: if (i > 0) {
! 357: bitmap_clear_bit(b, i);
! 358: BN_clear_bit(bn, i);
! 359: }
! 360: if (j > 0) {
! 361: bitmap_clear_bit(b, j);
! 362: BN_clear_bit(bn, j);
! 363: }
! 364: if (k > 0) {
! 365: bitmap_clear_bit(b, k);
! 366: BN_clear_bit(bn, k);
! 367: }
! 368: for (n = 0; n < LIM; n++) {
! 369: if (BN_is_bit_set(bn, n) !=
! 370: bitmap_test_bit(b, n)) {
! 371: bitmap_dump(b, stderr);
! 372: FAIL("cmiss %d/%d/%d %d "
! 373: "%d %d", i, j, k, n,
! 374: BN_is_bit_set(bn, n),
! 375: bitmap_test_bit(b, n));
! 376: }
! 377: }
! 378: }
! 379: }
! 380: }
! 381: fputc('\n', stdout);
! 382: bitmap_free(b);
! 383: BN_free(bn);
! 384:
! 385: return 0;
! 386: }
! 387: #endif