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 *
bitmap_new(void)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
bitmap_free(struct bitmap * b)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
bitmap_zero(struct bitmap * b)66 bitmap_zero(struct bitmap *b)
67 {
68 memset(b->d, 0, b->len * BITMAP_BYTES);
69 b->top = 0;
70 }
71
72 int
bitmap_test_bit(struct bitmap * b,u_int n)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
reserve(struct bitmap * b,u_int n)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
bitmap_set_bit(struct bitmap * b,u_int n)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
retop(struct bitmap * b)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
bitmap_clear_bit(struct bitmap * b,u_int n)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
bitmap_nbits(struct bitmap * b)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
bitmap_nbytes(struct bitmap * b)163 bitmap_nbytes(struct bitmap *b)
164 {
165 return (bitmap_nbits(b) + 7) / 8;
166 }
167
168 int
bitmap_to_string(struct bitmap * b,void * p,size_t l)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
bitmap_from_string(struct bitmap * b,const void * p,size_t l)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