bitmap.c revision 1.3 
1/*	$NetBSD: bitmap.c,v 1.3 2016/03/11 01:55:00 christos Exp $	*/
2/*
3 * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17#include "includes.h"
18__RCSID("$NetBSD: bitmap.c,v 1.3 2016/03/11 01:55:00 christos Exp $");
19
20#include <sys/types.h>
21#include <string.h>
22#include <stdlib.h>
23
24#include "bitmap.h"
25
26#define BITMAP_WTYPE	u_int
27#define BITMAP_MAX	(1<<24)
28#define BITMAP_BYTES	(sizeof(BITMAP_WTYPE))
29#define BITMAP_BITS	(sizeof(BITMAP_WTYPE) * 8)
30#define BITMAP_WMASK	((BITMAP_WTYPE)BITMAP_BITS - 1)
31struct bitmap {
32	BITMAP_WTYPE *d;
33	size_t len; /* number of words allocated */
34	size_t top; /* index of top word allocated */
35};
36
37struct bitmap *
38bitmap_new(void)
39{
40	struct bitmap *ret;
41
42	if ((ret = calloc(1, sizeof(*ret))) == NULL)
43		return NULL;
44	if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
45		free(ret);
46		return NULL;
47	}
48	ret->len = 1;
49	ret->top = 0;
50	return ret;
51}
52
53void
54bitmap_free(struct bitmap *b)
55{
56	if (b != NULL && b->d != NULL) {
57		explicit_bzero(b->d, b->len);
58		free(b->d);
59	}
60	free(b);
61}
62
63void
64bitmap_zero(struct bitmap *b)
65{
66	memset(b->d, 0, b->len * BITMAP_BYTES);
67	b->top = 0;
68}
69
70int
71bitmap_test_bit(struct bitmap *b, u_int n)
72{
73	if (b->top >= b->len)
74		return 0; /* invalid */
75	if (b->len == 0 || (n / BITMAP_BITS) > b->top)
76		return 0;
77	return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
78}
79
80static int
81reserve(struct bitmap *b, u_int n)
82{
83	BITMAP_WTYPE *tmp;
84	size_t nlen;
85
86	if (b->top >= b->len || n > BITMAP_MAX)
87		return -1; /* invalid */
88	nlen = (n / BITMAP_BITS) + 1;
89	if (b->len < nlen) {
90		if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL)
91			return -1;
92		b->d = tmp;
93		memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES);
94		b->len = nlen;
95	}
96	return 0;
97}
98
99int
100bitmap_set_bit(struct bitmap *b, u_int n)
101{
102	int r;
103	size_t offset;
104
105	if ((r = reserve(b, n)) != 0)
106		return r;
107	offset = n / BITMAP_BITS;
108	if (offset > b->top)
109		b->top = offset;
110	b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
111	return 0;
112}
113
114/* Resets b->top to point to the most significant bit set in b->d */
115static void
116retop(struct bitmap *b)
117{
118	if (b->top >= b->len)
119		return;
120	while (b->top > 0 && b->d[b->top] == 0)
121		b->top--;
122}
123
124void
125bitmap_clear_bit(struct bitmap *b, u_int n)
126{
127	size_t offset;
128
129	if (b->top >= b->len || n > BITMAP_MAX)
130		return; /* invalid */
131	offset = n / BITMAP_BITS;
132	if (offset > b->top)
133		return;
134	b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
135	/* The top may have changed as a result of the clear */
136	retop(b);
137}
138
139size_t
140bitmap_nbits(struct bitmap *b)
141{
142	size_t bits;
143	BITMAP_WTYPE w;
144
145	retop(b);
146	if (b->top >= b->len)
147		return 0; /* invalid */
148	if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
149		return 0;
150	/* Find MSB set */
151	w = b->d[b->top];
152	bits = (b->top + 1) * BITMAP_BITS;
153	while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
154		w <<= 1;
155		bits--;
156	}
157	return bits;
158}
159
160size_t
161bitmap_nbytes(struct bitmap *b)
162{
163	return (bitmap_nbits(b) + 7) / 8;
164}
165
166int
167bitmap_to_string(struct bitmap *b, void *p, size_t l)
168{
169	u_char *s = (u_char *)p;
170	size_t i, j, k, need = bitmap_nbytes(b);
171
172	if (l < need || b->top >= b->len)
173		return -1;
174	if (l > need)
175		l = need;
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++) {
179			if (k >= l)
180				break;
181			s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
182		}
183	}
184	return 0;
185}
186
187int
188bitmap_from_string(struct bitmap *b, const void *p, size_t l)
189{
190	int r;
191	size_t i, offset, shift;
192	const u_char *s = p;
193
194	if (l > BITMAP_MAX / 8)
195		return -1;
196	if ((r = reserve(b, l * 8)) != 0)
197		return r;
198	bitmap_zero(b);
199	if (l == 0)
200		return 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;
205		if (shift == 0) {
206			offset--;
207			shift = BITMAP_BITS - 8;
208		} else
209			shift -= 8;
210	}
211	retop(b);
212	return 0;
213}
214