Home | History | Annotate | Line # | Download | only in dist 
      1 /*	$NetBSD: bitmap.c,v 1.9 2024/12/01 20:01:42 rillig Exp $	*/
      2 /* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */
      3 /*
      4  * Copyright (c) 2015 Damien Miller <djm (at) 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.9 2024/12/01 20:01:42 rillig 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)
     32 struct bitmap {
     33 	BITMAP_WTYPE *d;
     34 	size_t len; /* number of words allocated */
     35 	size_t top; /* index of top word allocated */
     36 };
     37 
     38 struct bitmap *
     39 bitmap_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 
     54 void
     55 bitmap_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 
     65 void
     66 bitmap_zero(struct bitmap *b)
     67 {
     68 	memset(b->d, 0, b->len * BITMAP_BYTES);
     69 	b->top = 0;
     70 }
     71 
     72 int
     73 bitmap_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 
     82 static int
     83 reserve(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 
    101 int
    102 bitmap_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 */
    117 static void
    118 retop(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 
    126 void
    127 bitmap_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 
    141 size_t
    142 bitmap_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 
    162 size_t
    163 bitmap_nbytes(struct bitmap *b)
    164 {
    165 	return (bitmap_nbits(b) + 7) / 8;
    166 }
    167 
    168 int
    169 bitmap_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 
    189 int
    190 bitmap_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 = (const u_char *)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