blob: f95032250e7c7fbf91bb4f494f493eb014f3eb5e [file] [log] [blame]
Damien Miller4f38c612015-01-15 02:28:00 +11001/*
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
Damien Miller6e2549a2015-01-15 02:30:18 +110017#include "includes.h"
18
Damien Miller4f38c612015-01-15 02:28:00 +110019#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)
30struct bitmap {
31 BITMAP_WTYPE *d;
32 size_t len; /* number of words allocated */
33 size_t top; /* index of top word allocated */
34};
35
36struct bitmap *
37bitmap_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
52void
53bitmap_free(struct bitmap *b)
54{
55 if (b != NULL && b->d != NULL) {
guenther@openbsd.org14692f72015-09-11 08:50:04 +000056 explicit_bzero(b->d, b->len);
Damien Miller4f38c612015-01-15 02:28:00 +110057 free(b->d);
58 }
59 free(b);
60}
61
62void
63bitmap_zero(struct bitmap *b)
64{
65 memset(b->d, 0, b->len * BITMAP_BYTES);
66 b->top = 0;
67}
68
69int
70bitmap_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
79static int
80reserve(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
98int
99bitmap_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 */
114static void
115retop(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
123void
124bitmap_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
138size_t
139bitmap_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;
Damien Miller4f38c612015-01-15 02:28:00 +1100157}
158
159size_t
160bitmap_nbytes(struct bitmap *b)
161{
162 return (bitmap_nbits(b) + 7) / 8;
163}
164
165int
166bitmap_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 }
Damien Miller4f38c612015-01-15 02:28:00 +1100183 return 0;
184}
185
186int
187bitmap_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}