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