Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2015 Damien Miller <djm@mindrot.org> |
| 3 | * |
| 4 | * Permission to use, copy, modify, and distribute this software for any |
| 5 | * purpose with or without fee is hereby granted, provided that the above |
| 6 | * copyright notice and this permission notice appear in all copies. |
| 7 | * |
| 8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
| 11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
| 13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
| 14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 15 | */ |
| 16 | |
Damien Miller | 6e2549a | 2015-01-15 02:30:18 +1100 | [diff] [blame] | 17 | #include "includes.h" |
| 18 | |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 19 | #include <sys/types.h> |
| 20 | #include <string.h> |
| 21 | #include <stdlib.h> |
| 22 | |
| 23 | #include "bitmap.h" |
| 24 | |
| 25 | #define BITMAP_WTYPE u_int |
| 26 | #define BITMAP_MAX (1<<24) |
| 27 | #define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) |
| 28 | #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) |
| 29 | #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) |
| 30 | struct bitmap { |
| 31 | BITMAP_WTYPE *d; |
| 32 | size_t len; /* number of words allocated */ |
| 33 | size_t top; /* index of top word allocated */ |
| 34 | }; |
| 35 | |
| 36 | struct bitmap * |
| 37 | bitmap_new(void) |
| 38 | { |
| 39 | struct bitmap *ret; |
| 40 | |
| 41 | if ((ret = calloc(1, sizeof(*ret))) == NULL) |
| 42 | return NULL; |
| 43 | if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) { |
| 44 | free(ret); |
| 45 | return NULL; |
| 46 | } |
| 47 | ret->len = 1; |
| 48 | ret->top = 0; |
| 49 | return ret; |
| 50 | } |
| 51 | |
| 52 | void |
| 53 | bitmap_free(struct bitmap *b) |
| 54 | { |
| 55 | if (b != NULL && b->d != NULL) { |
djm@openbsd.org | d1c6b7f | 2017-05-01 22:09:48 +0000 | [diff] [blame] | 56 | bitmap_zero(b); |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 57 | free(b->d); |
djm@openbsd.org | d1c6b7f | 2017-05-01 22:09:48 +0000 | [diff] [blame] | 58 | b->d = NULL; |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 59 | } |
| 60 | free(b); |
| 61 | } |
| 62 | |
| 63 | void |
| 64 | bitmap_zero(struct bitmap *b) |
| 65 | { |
| 66 | memset(b->d, 0, b->len * BITMAP_BYTES); |
| 67 | b->top = 0; |
| 68 | } |
| 69 | |
| 70 | int |
| 71 | bitmap_test_bit(struct bitmap *b, u_int n) |
| 72 | { |
| 73 | if (b->top >= b->len) |
| 74 | return 0; /* invalid */ |
| 75 | if (b->len == 0 || (n / BITMAP_BITS) > b->top) |
| 76 | return 0; |
| 77 | return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; |
| 78 | } |
| 79 | |
| 80 | static int |
| 81 | reserve(struct bitmap *b, u_int n) |
| 82 | { |
| 83 | BITMAP_WTYPE *tmp; |
| 84 | size_t nlen; |
| 85 | |
| 86 | if (b->top >= b->len || n > BITMAP_MAX) |
| 87 | return -1; /* invalid */ |
| 88 | nlen = (n / BITMAP_BITS) + 1; |
| 89 | if (b->len < nlen) { |
deraadt@openbsd.org | 9e509d4 | 2017-05-31 09:15:42 +0000 | [diff] [blame] | 90 | if ((tmp = recallocarray(b->d, b->len, nlen, BITMAP_BYTES)) == NULL) |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 91 | return -1; |
| 92 | b->d = tmp; |
| 93 | memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES); |
| 94 | b->len = nlen; |
| 95 | } |
| 96 | return 0; |
| 97 | } |
| 98 | |
| 99 | int |
| 100 | bitmap_set_bit(struct bitmap *b, u_int n) |
| 101 | { |
| 102 | int r; |
| 103 | size_t offset; |
| 104 | |
| 105 | if ((r = reserve(b, n)) != 0) |
| 106 | return r; |
| 107 | offset = n / BITMAP_BITS; |
| 108 | if (offset > b->top) |
| 109 | b->top = offset; |
| 110 | b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); |
| 111 | return 0; |
| 112 | } |
| 113 | |
| 114 | /* Resets b->top to point to the most significant bit set in b->d */ |
| 115 | static void |
| 116 | retop(struct bitmap *b) |
| 117 | { |
| 118 | if (b->top >= b->len) |
| 119 | return; |
| 120 | while (b->top > 0 && b->d[b->top] == 0) |
| 121 | b->top--; |
| 122 | } |
| 123 | |
| 124 | void |
| 125 | bitmap_clear_bit(struct bitmap *b, u_int n) |
| 126 | { |
| 127 | size_t offset; |
| 128 | |
| 129 | if (b->top >= b->len || n > BITMAP_MAX) |
| 130 | return; /* invalid */ |
| 131 | offset = n / BITMAP_BITS; |
| 132 | if (offset > b->top) |
| 133 | return; |
| 134 | b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); |
| 135 | /* The top may have changed as a result of the clear */ |
| 136 | retop(b); |
| 137 | } |
| 138 | |
| 139 | size_t |
| 140 | bitmap_nbits(struct bitmap *b) |
| 141 | { |
| 142 | size_t bits; |
| 143 | BITMAP_WTYPE w; |
| 144 | |
| 145 | retop(b); |
| 146 | if (b->top >= b->len) |
| 147 | return 0; /* invalid */ |
| 148 | if (b->len == 0 || (b->top == 0 && b->d[0] == 0)) |
| 149 | return 0; |
| 150 | /* Find MSB set */ |
| 151 | w = b->d[b->top]; |
| 152 | bits = (b->top + 1) * BITMAP_BITS; |
| 153 | while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) { |
| 154 | w <<= 1; |
| 155 | bits--; |
| 156 | } |
| 157 | return bits; |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 158 | } |
| 159 | |
| 160 | size_t |
| 161 | bitmap_nbytes(struct bitmap *b) |
| 162 | { |
| 163 | return (bitmap_nbits(b) + 7) / 8; |
| 164 | } |
| 165 | |
| 166 | int |
| 167 | bitmap_to_string(struct bitmap *b, void *p, size_t l) |
| 168 | { |
| 169 | u_char *s = (u_char *)p; |
| 170 | size_t i, j, k, need = bitmap_nbytes(b); |
| 171 | |
| 172 | if (l < need || b->top >= b->len) |
| 173 | return -1; |
| 174 | if (l > need) |
| 175 | l = need; |
| 176 | /* Put the bytes from LSB backwards */ |
| 177 | for (i = k = 0; i < b->top + 1; i++) { |
| 178 | for (j = 0; j < BITMAP_BYTES; j++) { |
| 179 | if (k >= l) |
| 180 | break; |
| 181 | s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; |
| 182 | } |
| 183 | } |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 184 | return 0; |
| 185 | } |
| 186 | |
| 187 | int |
| 188 | bitmap_from_string(struct bitmap *b, const void *p, size_t l) |
| 189 | { |
| 190 | int r; |
| 191 | size_t i, offset, shift; |
djm@openbsd.org | 4b2e2d3 | 2017-06-01 04:51:58 +0000 | [diff] [blame^] | 192 | const u_char *s = (const u_char *)p; |
Damien Miller | 4f38c61 | 2015-01-15 02:28:00 +1100 | [diff] [blame] | 193 | |
| 194 | if (l > BITMAP_MAX / 8) |
| 195 | return -1; |
| 196 | if ((r = reserve(b, l * 8)) != 0) |
| 197 | return r; |
| 198 | bitmap_zero(b); |
| 199 | if (l == 0) |
| 200 | return 0; |
| 201 | b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; |
| 202 | shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; |
| 203 | for (i = 0; i < l; i++) { |
| 204 | b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; |
| 205 | if (shift == 0) { |
| 206 | offset--; |
| 207 | shift = BITMAP_BITS - 8; |
| 208 | } else |
| 209 | shift -= 8; |
| 210 | } |
| 211 | retop(b); |
| 212 | return 0; |
| 213 | } |