1276541Sdes/* 2276541Sdes * Copyright (c) 2015 Damien Miller <djm@mindrot.org> 3276541Sdes * 4276541Sdes * Permission to use, copy, modify, and distribute this software for any 5276541Sdes * purpose with or without fee is hereby granted, provided that the above 6276541Sdes * copyright notice and this permission notice appear in all copies. 7276541Sdes * 8276541Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9276541Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10276541Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11276541Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12276541Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13276541Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14276541Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15276541Sdes */ 16276541Sdes 17276541Sdes#include "includes.h" 18276541Sdes 19276541Sdes#include <sys/types.h> 20276541Sdes#include <string.h> 21276541Sdes#include <stdlib.h> 22276541Sdes 23276541Sdes#include "bitmap.h" 24276541Sdes 25276541Sdes#define BITMAP_WTYPE u_int 26276541Sdes#define BITMAP_MAX (1<<24) 27276541Sdes#define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) 28276541Sdes#define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) 29276541Sdes#define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) 30276541Sdesstruct bitmap { 31276541Sdes BITMAP_WTYPE *d; 32276541Sdes size_t len; /* number of words allocated */ 33276541Sdes size_t top; /* index of top word allocated */ 34276541Sdes}; 35276541Sdes 36276541Sdesstruct bitmap * 37276541Sdesbitmap_new(void) 38276541Sdes{ 39276541Sdes struct bitmap *ret; 40276541Sdes 41276541Sdes if ((ret = calloc(1, sizeof(*ret))) == NULL) 42276541Sdes return NULL; 43276541Sdes if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) { 44276541Sdes free(ret); 45276541Sdes return NULL; 46276541Sdes } 47276541Sdes ret->len = 1; 48276541Sdes ret->top = 0; 49276541Sdes return ret; 50276541Sdes} 51276541Sdes 52276541Sdesvoid 53276541Sdesbitmap_free(struct bitmap *b) 54276541Sdes{ 55276541Sdes if (b != NULL && b->d != NULL) { 56276541Sdes explicit_bzero(b->d, b->len); 57276541Sdes free(b->d); 58276541Sdes } 59276541Sdes free(b); 60276541Sdes} 61276541Sdes 62276541Sdesvoid 63276541Sdesbitmap_zero(struct bitmap *b) 64276541Sdes{ 65276541Sdes memset(b->d, 0, b->len * BITMAP_BYTES); 66276541Sdes b->top = 0; 67276541Sdes} 68276541Sdes 69276541Sdesint 70276541Sdesbitmap_test_bit(struct bitmap *b, u_int n) 71276541Sdes{ 72276541Sdes if (b->top >= b->len) 73276541Sdes return 0; /* invalid */ 74276541Sdes if (b->len == 0 || (n / BITMAP_BITS) > b->top) 75276541Sdes return 0; 76276541Sdes return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; 77276541Sdes} 78276541Sdes 79276541Sdesstatic int 80276541Sdesreserve(struct bitmap *b, u_int n) 81276541Sdes{ 82276541Sdes BITMAP_WTYPE *tmp; 83276541Sdes size_t nlen; 84276541Sdes 85276541Sdes if (b->top >= b->len || n > BITMAP_MAX) 86276541Sdes return -1; /* invalid */ 87276541Sdes nlen = (n / BITMAP_BITS) + 1; 88276541Sdes if (b->len < nlen) { 89276541Sdes if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL) 90276541Sdes return -1; 91276541Sdes b->d = tmp; 92276541Sdes memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES); 93276541Sdes b->len = nlen; 94276541Sdes } 95276541Sdes return 0; 96276541Sdes} 97276541Sdes 98276541Sdesint 99276541Sdesbitmap_set_bit(struct bitmap *b, u_int n) 100276541Sdes{ 101276541Sdes int r; 102276541Sdes size_t offset; 103276541Sdes 104276541Sdes if ((r = reserve(b, n)) != 0) 105276541Sdes return r; 106276541Sdes offset = n / BITMAP_BITS; 107276541Sdes if (offset > b->top) 108276541Sdes b->top = offset; 109276541Sdes b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); 110276541Sdes return 0; 111276541Sdes} 112276541Sdes 113276541Sdes/* Resets b->top to point to the most significant bit set in b->d */ 114276541Sdesstatic void 115276541Sdesretop(struct bitmap *b) 116276541Sdes{ 117276541Sdes if (b->top >= b->len) 118276541Sdes return; 119276541Sdes while (b->top > 0 && b->d[b->top] == 0) 120276541Sdes b->top--; 121276541Sdes} 122276541Sdes 123276541Sdesvoid 124276541Sdesbitmap_clear_bit(struct bitmap *b, u_int n) 125276541Sdes{ 126276541Sdes size_t offset; 127276541Sdes 128276541Sdes if (b->top >= b->len || n > BITMAP_MAX) 129276541Sdes return; /* invalid */ 130276541Sdes offset = n / BITMAP_BITS; 131276541Sdes if (offset > b->top) 132276541Sdes return; 133276541Sdes b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); 134276541Sdes /* The top may have changed as a result of the clear */ 135276541Sdes retop(b); 136276541Sdes} 137276541Sdes 138276541Sdessize_t 139276541Sdesbitmap_nbits(struct bitmap *b) 140276541Sdes{ 141276541Sdes size_t bits; 142276541Sdes BITMAP_WTYPE w; 143276541Sdes 144276541Sdes retop(b); 145276541Sdes if (b->top >= b->len) 146276541Sdes return 0; /* invalid */ 147276541Sdes if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) 148276541Sdes return 0; 149276541Sdes /* Find MSB set */ 150276541Sdes w = b->d[b->top]; 151276541Sdes bits = (b->top + 1) * BITMAP_BITS; 152276541Sdes while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { 153276541Sdes w <<= 1; 154276541Sdes bits--; 155276541Sdes } 156276541Sdes return bits; 157276541Sdes} 158276541Sdes 159276541Sdessize_t 160276541Sdesbitmap_nbytes(struct bitmap *b) 161276541Sdes{ 162276541Sdes return (bitmap_nbits(b) + 7) / 8; 163276541Sdes} 164276541Sdes 165276541Sdesint 166276541Sdesbitmap_to_string(struct bitmap *b, void *p, size_t l) 167276541Sdes{ 168276541Sdes u_char *s = (u_char *)p; 169276541Sdes size_t i, j, k, need = bitmap_nbytes(b); 170276541Sdes 171276541Sdes if (l < need || b->top >= b->len) 172276541Sdes return -1; 173276541Sdes if (l > need) 174276541Sdes l = need; 175276541Sdes /* Put the bytes from LSB backwards */ 176276541Sdes for (i = k = 0; i < b->top + 1; i++) { 177276541Sdes for (j = 0; j < BITMAP_BYTES; j++) { 178276541Sdes if (k >= l) 179276541Sdes break; 180276541Sdes s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; 181276541Sdes } 182276541Sdes } 183276541Sdes return 0; 184276541Sdes} 185276541Sdes 186276541Sdesint 187276541Sdesbitmap_from_string(struct bitmap *b, const void *p, size_t l) 188276541Sdes{ 189276541Sdes int r; 190276541Sdes size_t i, offset, shift; 191276541Sdes u_char *s = (u_char *)p; 192276541Sdes 193276541Sdes if (l > BITMAP_MAX / 8) 194276541Sdes return -1; 195276541Sdes if ((r = reserve(b, l * 8)) != 0) 196276541Sdes return r; 197276541Sdes bitmap_zero(b); 198276541Sdes if (l == 0) 199276541Sdes return 0; 200276541Sdes b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; 201276541Sdes shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; 202276541Sdes for (i = 0; i < l; i++) { 203276541Sdes b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; 204276541Sdes if (shift == 0) { 205276541Sdes offset--; 206276541Sdes shift = BITMAP_BITS - 8; 207276541Sdes } else 208276541Sdes shift -= 8; 209276541Sdes } 210276541Sdes retop(b); 211276541Sdes return 0; 212276541Sdes} 213276541Sdes