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