2 * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
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.
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.
19 #include <sys/types.h>
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)
32 size_t len; /* number of words allocated */
33 size_t top; /* index of top word allocated */
41 if ((ret = calloc(1, sizeof(*ret))) == NULL)
43 if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
53 bitmap_free(struct bitmap *b)
55 if (b != NULL && b->d != NULL) {
64 bitmap_zero(struct bitmap *b)
66 memset(b->d, 0, b->len * BITMAP_BYTES);
71 bitmap_test_bit(struct bitmap *b, u_int n)
74 return 0; /* invalid */
75 if (b->len == 0 || (n / BITMAP_BITS) > b->top)
77 return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
81 reserve(struct bitmap *b, u_int n)
86 if (b->top >= b->len || n > BITMAP_MAX)
87 return -1; /* invalid */
88 nlen = (n / BITMAP_BITS) + 1;
90 if ((tmp = recallocarray(b->d, b->len,
91 nlen, BITMAP_BYTES)) == NULL)
100 bitmap_set_bit(struct bitmap *b, u_int n)
105 if ((r = reserve(b, n)) != 0)
107 offset = n / BITMAP_BITS;
110 b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
114 /* Resets b->top to point to the most significant bit set in b->d */
116 retop(struct bitmap *b)
118 if (b->top >= b->len)
120 while (b->top > 0 && b->d[b->top] == 0)
125 bitmap_clear_bit(struct bitmap *b, u_int n)
129 if (b->top >= b->len || n > BITMAP_MAX)
130 return; /* invalid */
131 offset = n / BITMAP_BITS;
134 b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
135 /* The top may have changed as a result of the clear */
140 bitmap_nbits(struct bitmap *b)
146 if (b->top >= b->len)
147 return 0; /* invalid */
148 if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
152 bits = (b->top + 1) * BITMAP_BITS;
153 while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
161 bitmap_nbytes(struct bitmap *b)
163 return (bitmap_nbits(b) + 7) / 8;
167 bitmap_to_string(struct bitmap *b, void *p, size_t l)
169 u_char *s = (u_char *)p;
170 size_t i, j, k, need = bitmap_nbytes(b);
172 if (l < need || b->top >= b->len)
176 /* Put the bytes from LSB backwards */
177 for (i = k = 0; i < b->top + 1; i++) {
178 for (j = 0; j < BITMAP_BYTES; j++) {
181 s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
188 bitmap_from_string(struct bitmap *b, const void *p, size_t l)
191 size_t i, offset, shift;
192 const u_char *s = (const u_char *)p;
194 if (l > BITMAP_MAX / 8)
196 if ((r = reserve(b, l * 8)) != 0)
201 b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
202 shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
203 for (i = 0; i < l; i++) {
204 b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
207 shift = BITMAP_BITS - 8;