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                 bitmap_zero(b);
  57                 free(b->d);
  58                 b->d = NULL;
  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) {
  90                 if ((tmp = recallocarray(b->d, b->len,
  91                     nlen, BITMAP_BYTES)) == NULL)
  92                         return -1;
  93                 b->d = tmp;
  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;
 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         }
 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;
 192         const u_char *s = (const u_char *)p;
 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 }