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