• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "includes.h"
18 
19 #include <sys/types.h>
20 #include <string.h>
21 #include <stdlib.h>
22 
23 #include "bitmap.h"
24 
25 #define BITMAP_WTYPE	u_int
26 #define BITMAP_MAX	(1<<24)
27 #define BITMAP_BYTES	(sizeof(BITMAP_WTYPE))
28 #define BITMAP_BITS	(sizeof(BITMAP_WTYPE) * 8)
29 #define BITMAP_WMASK	((BITMAP_WTYPE)BITMAP_BITS - 1)
30 struct bitmap {
31 	BITMAP_WTYPE *d;
32 	size_t len; /* number of words allocated */
33 	size_t top; /* index of top word allocated */
34 };
35 
36 struct bitmap *
bitmap_new(void)37 bitmap_new(void)
38 {
39 	struct bitmap *ret;
40 
41 	if ((ret = calloc(1, sizeof(*ret))) == NULL)
42 		return NULL;
43 	if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
44 		free(ret);
45 		return NULL;
46 	}
47 	ret->len = 1;
48 	ret->top = 0;
49 	return ret;
50 }
51 
52 void
bitmap_free(struct bitmap * b)53 bitmap_free(struct bitmap *b)
54 {
55 	if (b != NULL && b->d != NULL) {
56 		explicit_bzero(b->d, b->len);
57 		free(b->d);
58 	}
59 	free(b);
60 }
61 
62 void
bitmap_zero(struct bitmap * b)63 bitmap_zero(struct bitmap *b)
64 {
65 	memset(b->d, 0, b->len * BITMAP_BYTES);
66 	b->top = 0;
67 }
68 
69 int
bitmap_test_bit(struct bitmap * b,u_int n)70 bitmap_test_bit(struct bitmap *b, u_int n)
71 {
72 	if (b->top >= b->len)
73 		return 0; /* invalid */
74 	if (b->len == 0 || (n / BITMAP_BITS) > b->top)
75 		return 0;
76 	return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
77 }
78 
79 static int
reserve(struct bitmap * b,u_int n)80 reserve(struct bitmap *b, u_int n)
81 {
82 	BITMAP_WTYPE *tmp;
83 	size_t nlen;
84 
85 	if (b->top >= b->len || n > BITMAP_MAX)
86 		return -1; /* invalid */
87 	nlen = (n / BITMAP_BITS) + 1;
88 	if (b->len < nlen) {
89 		if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL)
90 			return -1;
91 		b->d = tmp;
92 		memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES);
93 		b->len = nlen;
94 	}
95 	return 0;
96 }
97 
98 int
bitmap_set_bit(struct bitmap * b,u_int n)99 bitmap_set_bit(struct bitmap *b, u_int n)
100 {
101 	int r;
102 	size_t offset;
103 
104 	if ((r = reserve(b, n)) != 0)
105 		return r;
106 	offset = n / BITMAP_BITS;
107 	if (offset > b->top)
108 		b->top = offset;
109 	b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
110 	return 0;
111 }
112 
113 /* Resets b->top to point to the most significant bit set in b->d */
114 static void
retop(struct bitmap * b)115 retop(struct bitmap *b)
116 {
117 	if (b->top >= b->len)
118 		return;
119 	while (b->top > 0 && b->d[b->top] == 0)
120 		b->top--;
121 }
122 
123 void
bitmap_clear_bit(struct bitmap * b,u_int n)124 bitmap_clear_bit(struct bitmap *b, u_int n)
125 {
126 	size_t offset;
127 
128 	if (b->top >= b->len || n > BITMAP_MAX)
129 		return; /* invalid */
130 	offset = n / BITMAP_BITS;
131 	if (offset > b->top)
132 		return;
133 	b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
134 	/* The top may have changed as a result of the clear */
135 	retop(b);
136 }
137 
138 size_t
bitmap_nbits(struct bitmap * b)139 bitmap_nbits(struct bitmap *b)
140 {
141 	size_t bits;
142 	BITMAP_WTYPE w;
143 
144 	retop(b);
145 	if (b->top >= b->len)
146 		return 0; /* invalid */
147 	if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
148 		return 0;
149 	/* Find MSB set */
150 	w = b->d[b->top];
151 	bits = (b->top + 1) * BITMAP_BITS;
152 	while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
153 		w <<= 1;
154 		bits--;
155 	}
156 	return bits;
157 }
158 
159 size_t
bitmap_nbytes(struct bitmap * b)160 bitmap_nbytes(struct bitmap *b)
161 {
162 	return (bitmap_nbits(b) + 7) / 8;
163 }
164 
165 int
bitmap_to_string(struct bitmap * b,void * p,size_t l)166 bitmap_to_string(struct bitmap *b, void *p, size_t l)
167 {
168 	u_char *s = (u_char *)p;
169 	size_t i, j, k, need = bitmap_nbytes(b);
170 
171 	if (l < need || b->top >= b->len)
172 		return -1;
173 	if (l > need)
174 		l = need;
175 	/* Put the bytes from LSB backwards */
176 	for (i = k = 0; i < b->top + 1; i++) {
177 		for (j = 0; j < BITMAP_BYTES; j++) {
178 			if (k >= l)
179 				break;
180 			s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
181 		}
182 	}
183 	return 0;
184 }
185 
186 int
bitmap_from_string(struct bitmap * b,const void * p,size_t l)187 bitmap_from_string(struct bitmap *b, const void *p, size_t l)
188 {
189 	int r;
190 	size_t i, offset, shift;
191 	u_char *s = (u_char *)p;
192 
193 	if (l > BITMAP_MAX / 8)
194 		return -1;
195 	if ((r = reserve(b, l * 8)) != 0)
196 		return r;
197 	bitmap_zero(b);
198 	if (l == 0)
199 		return 0;
200 	b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
201 	shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
202 	for (i = 0; i < l; i++) {
203 		b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
204 		if (shift == 0) {
205 			offset--;
206 			shift = BITMAP_BITS - 8;
207 		} else
208 			shift -= 8;
209 	}
210 	retop(b);
211 	return 0;
212 }
213