crypto/openssh/bitmap.c

   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
  17 #include "includes.h"
  18
  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) {
  56                 explicit_bzero(b->d, b->len);
  57                 free(b->d);
  58         }
  59         free(b);
  60 }
  61
  62 void
  63 bitmap_zero(struct bitmap *b)
  64 {
  65         memset(b->d, 0, b->len * BITMAP_BYTES);
  66         b->top = 0;
  67 }
  68
  69 int
  70 bitmap_test_bit(struct bitmap *b, u_int n)
  71 {
  72         if (b->top >= b->len)
  73                 return 0; /* invalid */
  74         if (b->len == 0 || (n / BITMAP_BITS) > b->top)
  75                 return 0;
  76         return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
  77 }
  78
  79 static int
  80 reserve(struct bitmap *b, u_int n)
  81 {
  82         BITMAP_WTYPE *tmp;
  83         size_t nlen;
  84
  85         if (b->top >= b->len || n > BITMAP_MAX)
  86                 return -1; /* invalid */
  87         nlen = (n / BITMAP_BITS) + 1;
  88         if (b->len < nlen) {
  89                 if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL)
  90                         return -1;
  91                 b->d = tmp;
  92                 memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES);
  93                 b->len = nlen;
  94         }
  95         return 0;
  96 }
  97
  98 int
  99 bitmap_set_bit(struct bitmap *b, u_int n)
 100 {
 101         int r;
 102         size_t offset;
 103
 104         if ((r = reserve(b, n)) != 0)
 105                 return r;
 106         offset = n / BITMAP_BITS;
 107         if (offset > b->top)
 108                 b->top = offset;
 109         b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
 110         return 0;
 111 }
 112
 113 /* Resets b->top to point to the most significant bit set in b->d */
 114 static void
 115 retop(struct bitmap *b)
 116 {
 117         if (b->top >= b->len)
 118                 return;
 119         while (b->top > 0 && b->d[b->top] == 0)
 120                 b->top--;
 121 }
 122
 123 void
 124 bitmap_clear_bit(struct bitmap *b, u_int n)
 125 {
 126         size_t offset;
 127
 128         if (b->top >= b->len || n > BITMAP_MAX)
 129                 return; /* invalid */
 130         offset = n / BITMAP_BITS;
 131         if (offset > b->top)
 132                 return;
 133         b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
 134         /* The top may have changed as a result of the clear */
 135         retop(b);
 136 }
 137
 138 size_t
 139 bitmap_nbits(struct bitmap *b)
 140 {
 141         size_t bits;
 142         BITMAP_WTYPE w;
 143
 144         retop(b);
 145         if (b->top >= b->len)
 146                 return 0; /* invalid */
 147         if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
 148                 return 0;
 149         /* Find MSB set */
 150         w = b->d[b->top];
 151         bits = (b->top + 1) * BITMAP_BITS;
 152         while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
 153                 w <<= 1;
 154                 bits--;
 155         }
 156         return bits;
 157 }
 158
 159 size_t
 160 bitmap_nbytes(struct bitmap *b)
 161 {
 162         return (bitmap_nbits(b) + 7) / 8;
 163 }
 164
 165 int
 166 bitmap_to_string(struct bitmap *b, void *p, size_t l)
 167 {
 168         u_char *s = (u_char *)p;
 169         size_t i, j, k, need = bitmap_nbytes(b);
 170
 171         if (l < need || b->top >= b->len)
 172                 return -1;
 173         if (l > need)
 174                 l = need;
 175         /* Put the bytes from LSB backwards */
 176         for (i = k = 0; i < b->top + 1; i++) {
 177                 for (j = 0; j < BITMAP_BYTES; j++) {
 178                         if (k >= l)
 179                                 break;
 180                         s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
 181                 }
 182         }
 183         return 0;
 184 }
 185
 186 int
 187 bitmap_from_string(struct bitmap *b, const void *p, size_t l)
 188 {
 189         int r;
 190         size_t i, offset, shift;
 191         u_char *s = (u_char *)p;
 192
 193         if (l > BITMAP_MAX / 8)
 194                 return -1;
 195         if ((r = reserve(b, l * 8)) != 0)
 196                 return r;
 197         bitmap_zero(b);
 198         if (l == 0)
 199                 return 0;
 200         b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
 201         shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
 202         for (i = 0; i < l; i++) {
 203                 b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
 204                 if (shift == 0) {
 205                         offset--;
 206                         shift = BITMAP_BITS - 8;
 207                 } else
 208                         shift -= 8;
 209         }
 210         retop(b);
 211         return 0;
 212 }