diff options
Diffstat (limited to 'bitmap.c')
-rw-r--r-- | bitmap.c | 212 |
1 files changed, 212 insertions, 0 deletions
diff --git a/bitmap.c b/bitmap.c new file mode 100644 index 000000000..19cd2e8e3 --- /dev/null +++ b/bitmap.c | |||
@@ -0,0 +1,212 @@ | |||
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 * | ||
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 | ||
53 | bitmap_free(struct bitmap *b) | ||
54 | { | ||
55 | if (b != NULL && b->d != NULL) { | ||
56 | memset(b->d, 0, b->len); | ||
57 | free(b->d); | ||
58 | } | ||
59 | free(b); | ||
60 | } | ||
61 | |||
62 | void | ||
63 | bitmap_zero(struct bitmap *b) | ||
64 | { | ||
65 | memset(b->d, 0, b->len * BITMAP_BYTES); | ||
66 | b->top = 0; | ||
67 | } | ||
68 | |||
69 | int | ||
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 | ||
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 | ||
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 | ||
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 | ||
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 | ||
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 | ||
160 | bitmap_nbytes(struct bitmap *b) | ||
161 | { | ||
162 | return (bitmap_nbits(b) + 7) / 8; | ||
163 | } | ||
164 | |||
165 | int | ||
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 | ||
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 | } | ||