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