bitmap.c revision 295367 
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)
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) {
56		explicit_bzero(b->d, b->len);
57		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;
157}
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	}
183	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}
213