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