1285031Sdes/* 2285031Sdes * Copyright (c) 2015 Damien Miller <djm@mindrot.org> 3285031Sdes * 4285031Sdes * Permission to use, copy, modify, and distribute this software for any 5285031Sdes * purpose with or without fee is hereby granted, provided that the above 6285031Sdes * copyright notice and this permission notice appear in all copies. 7285031Sdes * 8285031Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9285031Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10285031Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11285031Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12285031Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13285031Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14285031Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15285031Sdes */ 16285031Sdes 17285031Sdes#include "includes.h" 18285031Sdes 19285031Sdes#include <sys/types.h> 20285031Sdes#include <string.h> 21285031Sdes#include <stdlib.h> 22285031Sdes 23285031Sdes#include "bitmap.h" 24285031Sdes 25285031Sdes#define BITMAP_WTYPE u_int 26285031Sdes#define BITMAP_MAX (1<<24) 27285031Sdes#define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) 28285031Sdes#define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) 29285031Sdes#define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) 30285031Sdesstruct bitmap { 31285031Sdes BITMAP_WTYPE *d; 32285031Sdes size_t len; /* number of words allocated */ 33285031Sdes size_t top; /* index of top word allocated */ 34285031Sdes}; 35285031Sdes 36285031Sdesstruct bitmap * 37285031Sdesbitmap_new(void) 38285031Sdes{ 39285031Sdes struct bitmap *ret; 40285031Sdes 41285031Sdes if ((ret = calloc(1, sizeof(*ret))) == NULL) 42285031Sdes return NULL; 43285031Sdes if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) { 44285031Sdes free(ret); 45285031Sdes return NULL; 46285031Sdes } 47285031Sdes ret->len = 1; 48285031Sdes ret->top = 0; 49285031Sdes return ret; 50285031Sdes} 51285031Sdes 52285031Sdesvoid 53285031Sdesbitmap_free(struct bitmap *b) 54285031Sdes{ 55285031Sdes if (b != NULL && b->d != NULL) { 56294496Sdes explicit_bzero(b->d, b->len); 57285031Sdes free(b->d); 58285031Sdes } 59285031Sdes free(b); 60285031Sdes} 61285031Sdes 62285031Sdesvoid 63285031Sdesbitmap_zero(struct bitmap *b) 64285031Sdes{ 65285031Sdes memset(b->d, 0, b->len * BITMAP_BYTES); 66285031Sdes b->top = 0; 67285031Sdes} 68285031Sdes 69285031Sdesint 70285031Sdesbitmap_test_bit(struct bitmap *b, u_int n) 71285031Sdes{ 72285031Sdes if (b->top >= b->len) 73285031Sdes return 0; /* invalid */ 74285031Sdes if (b->len == 0 || (n / BITMAP_BITS) > b->top) 75285031Sdes return 0; 76285031Sdes return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; 77285031Sdes} 78285031Sdes 79285031Sdesstatic int 80285031Sdesreserve(struct bitmap *b, u_int n) 81285031Sdes{ 82285031Sdes BITMAP_WTYPE *tmp; 83285031Sdes size_t nlen; 84285031Sdes 85285031Sdes if (b->top >= b->len || n > BITMAP_MAX) 86285031Sdes return -1; /* invalid */ 87285031Sdes nlen = (n / BITMAP_BITS) + 1; 88285031Sdes if (b->len < nlen) { 89285031Sdes if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL) 90285031Sdes return -1; 91285031Sdes b->d = tmp; 92285031Sdes memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES); 93285031Sdes b->len = nlen; 94285031Sdes } 95285031Sdes return 0; 96285031Sdes} 97285031Sdes 98285031Sdesint 99285031Sdesbitmap_set_bit(struct bitmap *b, u_int n) 100285031Sdes{ 101285031Sdes int r; 102285031Sdes size_t offset; 103285031Sdes 104285031Sdes if ((r = reserve(b, n)) != 0) 105285031Sdes return r; 106285031Sdes offset = n / BITMAP_BITS; 107285031Sdes if (offset > b->top) 108285031Sdes b->top = offset; 109285031Sdes b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); 110285031Sdes return 0; 111285031Sdes} 112285031Sdes 113285031Sdes/* Resets b->top to point to the most significant bit set in b->d */ 114285031Sdesstatic void 115285031Sdesretop(struct bitmap *b) 116285031Sdes{ 117285031Sdes if (b->top >= b->len) 118285031Sdes return; 119285031Sdes while (b->top > 0 && b->d[b->top] == 0) 120285031Sdes b->top--; 121285031Sdes} 122285031Sdes 123285031Sdesvoid 124285031Sdesbitmap_clear_bit(struct bitmap *b, u_int n) 125285031Sdes{ 126285031Sdes size_t offset; 127285031Sdes 128285031Sdes if (b->top >= b->len || n > BITMAP_MAX) 129285031Sdes return; /* invalid */ 130285031Sdes offset = n / BITMAP_BITS; 131285031Sdes if (offset > b->top) 132285031Sdes return; 133285031Sdes b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); 134285031Sdes /* The top may have changed as a result of the clear */ 135285031Sdes retop(b); 136285031Sdes} 137285031Sdes 138285031Sdessize_t 139285031Sdesbitmap_nbits(struct bitmap *b) 140285031Sdes{ 141285031Sdes size_t bits; 142285031Sdes BITMAP_WTYPE w; 143285031Sdes 144285031Sdes retop(b); 145285031Sdes if (b->top >= b->len) 146285031Sdes return 0; /* invalid */ 147285031Sdes if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) 148285031Sdes return 0; 149285031Sdes /* Find MSB set */ 150285031Sdes w = b->d[b->top]; 151285031Sdes bits = (b->top + 1) * BITMAP_BITS; 152285031Sdes while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { 153285031Sdes w <<= 1; 154285031Sdes bits--; 155285031Sdes } 156285031Sdes return bits; 157285031Sdes} 158285031Sdes 159285031Sdessize_t 160285031Sdesbitmap_nbytes(struct bitmap *b) 161285031Sdes{ 162285031Sdes return (bitmap_nbits(b) + 7) / 8; 163285031Sdes} 164285031Sdes 165285031Sdesint 166285031Sdesbitmap_to_string(struct bitmap *b, void *p, size_t l) 167285031Sdes{ 168285031Sdes u_char *s = (u_char *)p; 169285031Sdes size_t i, j, k, need = bitmap_nbytes(b); 170285031Sdes 171285031Sdes if (l < need || b->top >= b->len) 172285031Sdes return -1; 173285031Sdes if (l > need) 174285031Sdes l = need; 175285031Sdes /* Put the bytes from LSB backwards */ 176285031Sdes for (i = k = 0; i < b->top + 1; i++) { 177285031Sdes for (j = 0; j < BITMAP_BYTES; j++) { 178285031Sdes if (k >= l) 179285031Sdes break; 180285031Sdes s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; 181285031Sdes } 182285031Sdes } 183285031Sdes return 0; 184285031Sdes} 185285031Sdes 186285031Sdesint 187285031Sdesbitmap_from_string(struct bitmap *b, const void *p, size_t l) 188285031Sdes{ 189285031Sdes int r; 190285031Sdes size_t i, offset, shift; 191285031Sdes u_char *s = (u_char *)p; 192285031Sdes 193285031Sdes if (l > BITMAP_MAX / 8) 194285031Sdes return -1; 195285031Sdes if ((r = reserve(b, l * 8)) != 0) 196285031Sdes return r; 197285031Sdes bitmap_zero(b); 198285031Sdes if (l == 0) 199285031Sdes return 0; 200285031Sdes b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; 201285031Sdes shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; 202285031Sdes for (i = 0; i < l; i++) { 203285031Sdes b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; 204285031Sdes if (shift == 0) { 205285031Sdes offset--; 206285031Sdes shift = BITMAP_BITS - 8; 207285031Sdes } else 208285031Sdes shift -= 8; 209285031Sdes } 210285031Sdes retop(b); 211285031Sdes return 0; 212285031Sdes} 213