/* $NetBSD: bitmap.c,v 1.9 2024/12/01 20:01:42 rillig Exp $ */ /* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */ /* * Copyright (c) 2015 Damien Miller <djm@mindrot.org> * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include "includes.h" __RCSID("$NetBSD: bitmap.c,v 1.9 2024/12/01 20:01:42 rillig Exp $"); #include <sys/types.h> #include <string.h> #include <stdlib.h> #include "bitmap.h" #define BITMAP_WTYPE u_int #define BITMAP_MAX (1<<24) #define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) struct bitmap { BITMAP_WTYPE *d; size_t len; /* number of words allocated */ size_t top; /* index of top word allocated */ }; struct bitmap * bitmap_new(void) { struct bitmap *ret; if ((ret = calloc(1, sizeof(*ret))) == NULL) return NULL; if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) { free(ret); return NULL; } ret->len = 1; ret->top = 0; return ret; } void bitmap_free(struct bitmap *b) { if (b != NULL && b->d != NULL) { bitmap_zero(b); free(b->d); b->d = NULL; } free(b); } void bitmap_zero(struct bitmap *b) { memset(b->d, 0, b->len * BITMAP_BYTES); b->top = 0; } int bitmap_test_bit(struct bitmap *b, u_int n) { if (b->top >= b->len) return 0; /* invalid */ if (b->len == 0 || (n / BITMAP_BITS) > b->top) return 0; return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; } static int reserve(struct bitmap *b, u_int n) { BITMAP_WTYPE *tmp; size_t nlen; if (b->top >= b->len || n > BITMAP_MAX) return -1; /* invalid */ nlen = (n / BITMAP_BITS) + 1; if (b->len < nlen) { if ((tmp = recallocarray(b->d, b->len, nlen, BITMAP_BYTES)) == NULL) return -1; b->d = tmp; b->len = nlen; } return 0; } int bitmap_set_bit(struct bitmap *b, u_int n) { int r; size_t offset; if ((r = reserve(b, n)) != 0) return r; offset = n / BITMAP_BITS; if (offset > b->top) b->top = offset; b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); return 0; } /* Resets b->top to point to the most significant bit set in b->d */ static void retop(struct bitmap *b) { if (b->top >= b->len) return; while (b->top > 0 && b->d[b->top] == 0) b->top--; } void bitmap_clear_bit(struct bitmap *b, u_int n) { size_t offset; if (b->top >= b->len || n > BITMAP_MAX) return; /* invalid */ offset = n / BITMAP_BITS; if (offset > b->top) return; b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); /* The top may have changed as a result of the clear */ retop(b); } size_t bitmap_nbits(struct bitmap *b) { size_t bits; BITMAP_WTYPE w; retop(b); if (b->top >= b->len) return 0; /* invalid */ if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) return 0; /* Find MSB set */ w = b->d[b->top]; bits = (b->top + 1) * BITMAP_BITS; while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { w <<= 1; bits--; } return bits; } size_t bitmap_nbytes(struct bitmap *b) { return (bitmap_nbits(b) + 7) / 8; } int bitmap_to_string(struct bitmap *b, void *p, size_t l) { u_char *s = (u_char *)p; size_t i, j, k, need = bitmap_nbytes(b); if (l < need || b->top >= b->len) return -1; if (l > need) l = need; /* Put the bytes from LSB backwards */ for (i = k = 0; i < b->top + 1; i++) { for (j = 0; j < BITMAP_BYTES; j++) { if (k >= l) break; s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; } } return 0; } int bitmap_from_string(struct bitmap *b, const void *p, size_t l) { int r; size_t i, offset, shift; const u_char *s = (const u_char *)p; if (l > BITMAP_MAX / 8) return -1; if ((r = reserve(b, l * 8)) != 0) return r; bitmap_zero(b); if (l == 0) return 0; b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; for (i = 0; i < l; i++) { b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; if (shift == 0) { offset--; shift = BITMAP_BITS - 8; } else shift -= 8; } retop(b); return 0; }