crypto/openssh/bitmap.c

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