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 bitmap_zero(b); 55 free(b->d); 56 b->d = NULL; 57 } 58 free(b); 59 } 60 61 void 62 bitmap_zero(struct bitmap *b) 63 { 64 memset(b->d, 0, b->len * BITMAP_BYTES); 65 b->top = 0; 66 } 67 68 int 69 bitmap_test_bit(struct bitmap *b, u_int n) 70 { 71 if (b->top >= b->len) 72 return 0; /* invalid */ 73 if (b->len == 0 || (n / BITMAP_BITS) > b->top) 74 return 0; 75 return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; 76 } 77 78 static int 79 reserve(struct bitmap *b, u_int n) 80 { 81 BITMAP_WTYPE *tmp; 82 size_t nlen; 83 84 if (b->top >= b->len || n > BITMAP_MAX) 85 return -1; /* invalid */ 86 nlen = (n / BITMAP_BITS) + 1; 87 if (b->len < nlen) { 88 if ((tmp = recallocarray(b->d, b->len, 89 nlen, BITMAP_BYTES)) == NULL) 90 return -1; 91 b->d = tmp; 92 b->len = nlen; 93 } 94 return 0; 95 } 96 97 int 98 bitmap_set_bit(struct bitmap *b, u_int n) 99 { 100 int r; 101 size_t offset; 102 103 if ((r = reserve(b, n)) != 0) 104 return r; 105 offset = n / BITMAP_BITS; 106 if (offset > b->top) 107 b->top = offset; 108 b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); 109 return 0; 110 } 111 112 /* Resets b->top to point to the most significant bit set in b->d */ 113 static void 114 retop(struct bitmap *b) 115 { 116 if (b->top >= b->len) 117 return; 118 while (b->top > 0 && b->d[b->top] == 0) 119 b->top--; 120 } 121 122 void 123 bitmap_clear_bit(struct bitmap *b, u_int n) 124 { 125 size_t offset; 126 127 if (b->top >= b->len || n > BITMAP_MAX) 128 return; /* invalid */ 129 offset = n / BITMAP_BITS; 130 if (offset > b->top) 131 return; 132 b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); 133 /* The top may have changed as a result of the clear */ 134 retop(b); 135 } 136 137 size_t 138 bitmap_nbits(struct bitmap *b) 139 { 140 size_t bits; 141 BITMAP_WTYPE w; 142 143 retop(b); 144 if (b->top >= b->len) 145 return 0; /* invalid */ 146 if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) 147 return 0; 148 /* Find MSB set */ 149 w = b->d[b->top]; 150 bits = (b->top + 1) * BITMAP_BITS; 151 while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { 152 w <<= 1; 153 bits--; 154 } 155 return bits; 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 return 0; 183 } 184 185 int 186 bitmap_from_string(struct bitmap *b, const void *p, size_t l) 187 { 188 int r; 189 size_t i, offset, shift; 190 const u_char *s = (const u_char *)p; 191 192 if (l > BITMAP_MAX / 8) 193 return -1; 194 if ((r = reserve(b, l * 8)) != 0) 195 return r; 196 bitmap_zero(b); 197 if (l == 0) 198 return 0; 199 b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; 200 shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; 201 for (i = 0; i < l; i++) { 202 b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; 203 if (shift == 0) { 204 offset--; 205 shift = BITMAP_BITS - 8; 206 } else 207 shift -= 8; 208 } 209 retop(b); 210 return 0; 211 } 212