1 /* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */ 2 /* 3 * Copyright (c) 2015 Damien Miller <djm@mindrot.org> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #include "includes.h" 19 20 #include <sys/types.h> 21 #include <string.h> 22 #include <stdlib.h> 23 24 #include "bitmap.h" 25 26 #define BITMAP_WTYPE u_int 27 #define BITMAP_MAX (1<<24) 28 #define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) 29 #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) 30 #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) 31 struct bitmap { 32 BITMAP_WTYPE *d; 33 size_t len; /* number of words allocated */ 34 size_t top; /* index of top word allocated */ 35 }; 36 37 struct bitmap * 38 bitmap_new(void) 39 { 40 struct bitmap *ret; 41 42 if ((ret = calloc(1, sizeof(*ret))) == NULL) 43 return NULL; 44 if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) { 45 free(ret); 46 return NULL; 47 } 48 ret->len = 1; 49 ret->top = 0; 50 return ret; 51 } 52 53 void 54 bitmap_free(struct bitmap *b) 55 { 56 if (b != NULL && b->d != NULL) { 57 bitmap_zero(b); 58 free(b->d); 59 b->d = NULL; 60 } 61 free(b); 62 } 63 64 void 65 bitmap_zero(struct bitmap *b) 66 { 67 memset(b->d, 0, b->len * BITMAP_BYTES); 68 b->top = 0; 69 } 70 71 int 72 bitmap_test_bit(struct bitmap *b, u_int n) 73 { 74 if (b->top >= b->len) 75 return 0; /* invalid */ 76 if (b->len == 0 || (n / BITMAP_BITS) > b->top) 77 return 0; 78 return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; 79 } 80 81 static int 82 reserve(struct bitmap *b, u_int n) 83 { 84 BITMAP_WTYPE *tmp; 85 size_t nlen; 86 87 if (b->top >= b->len || n > BITMAP_MAX) 88 return -1; /* invalid */ 89 nlen = (n / BITMAP_BITS) + 1; 90 if (b->len < nlen) { 91 if ((tmp = recallocarray(b->d, b->len, 92 nlen, BITMAP_BYTES)) == NULL) 93 return -1; 94 b->d = tmp; 95 b->len = nlen; 96 } 97 return 0; 98 } 99 100 int 101 bitmap_set_bit(struct bitmap *b, u_int n) 102 { 103 int r; 104 size_t offset; 105 106 if ((r = reserve(b, n)) != 0) 107 return r; 108 offset = n / BITMAP_BITS; 109 if (offset > b->top) 110 b->top = offset; 111 b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); 112 return 0; 113 } 114 115 /* Resets b->top to point to the most significant bit set in b->d */ 116 static void 117 retop(struct bitmap *b) 118 { 119 if (b->top >= b->len) 120 return; 121 while (b->top > 0 && b->d[b->top] == 0) 122 b->top--; 123 } 124 125 void 126 bitmap_clear_bit(struct bitmap *b, u_int n) 127 { 128 size_t offset; 129 130 if (b->top >= b->len || n > BITMAP_MAX) 131 return; /* invalid */ 132 offset = n / BITMAP_BITS; 133 if (offset > b->top) 134 return; 135 b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); 136 /* The top may have changed as a result of the clear */ 137 retop(b); 138 } 139 140 size_t 141 bitmap_nbits(struct bitmap *b) 142 { 143 size_t bits; 144 BITMAP_WTYPE w; 145 146 retop(b); 147 if (b->top >= b->len) 148 return 0; /* invalid */ 149 if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) 150 return 0; 151 /* Find MSB set */ 152 w = b->d[b->top]; 153 bits = (b->top + 1) * BITMAP_BITS; 154 while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { 155 w <<= 1; 156 bits--; 157 } 158 return bits; 159 } 160 161 size_t 162 bitmap_nbytes(struct bitmap *b) 163 { 164 return (bitmap_nbits(b) + 7) / 8; 165 } 166 167 int 168 bitmap_to_string(struct bitmap *b, void *p, size_t l) 169 { 170 u_char *s = (u_char *)p; 171 size_t i, j, k, need = bitmap_nbytes(b); 172 173 if (l < need || b->top >= b->len) 174 return -1; 175 if (l > need) 176 l = need; 177 /* Put the bytes from LSB backwards */ 178 for (i = k = 0; i < b->top + 1; i++) { 179 for (j = 0; j < BITMAP_BYTES; j++) { 180 if (k >= l) 181 break; 182 s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; 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 const u_char *s = (const 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