summaryrefslogtreecommitdiffstats
path: root/bitmap.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 01:26:58 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 01:26:58 +0000
commit999ae6be3243c7b4a815247199447b53c39a3d65 (patch)
tree1f35b42b5e5f462d35ba452e4dcfa188ce0543fd /bitmap.c
parentInitial commit. (diff)
downloadopenssh-999ae6be3243c7b4a815247199447b53c39a3d65.tar.xz
openssh-999ae6be3243c7b4a815247199447b53c39a3d65.zip
Adding upstream version 1:7.9p1.upstream/1%7.9p1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'bitmap.c')
-rw-r--r--bitmap.c214
1 files changed, 214 insertions, 0 deletions
diff --git a/bitmap.c b/bitmap.c
new file mode 100644
index 0000000..5ecfe68
--- /dev/null
+++ b/bitmap.c
@@ -0,0 +1,214 @@
+/* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */
+/*
+ * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "includes.h"
+
+#include <sys/types.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "bitmap.h"
+
+#define BITMAP_WTYPE u_int
+#define BITMAP_MAX (1<<24)
+#define BITMAP_BYTES (sizeof(BITMAP_WTYPE))
+#define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)
+#define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)
+struct bitmap {
+ BITMAP_WTYPE *d;
+ size_t len; /* number of words allocated */
+ size_t top; /* index of top word allocated */
+};
+
+struct bitmap *
+bitmap_new(void)
+{
+ struct bitmap *ret;
+
+ if ((ret = calloc(1, sizeof(*ret))) == NULL)
+ return NULL;
+ if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
+ free(ret);
+ return NULL;
+ }
+ ret->len = 1;
+ ret->top = 0;
+ return ret;
+}
+
+void
+bitmap_free(struct bitmap *b)
+{
+ if (b != NULL && b->d != NULL) {
+ bitmap_zero(b);
+ free(b->d);
+ b->d = NULL;
+ }
+ free(b);
+}
+
+void
+bitmap_zero(struct bitmap *b)
+{
+ memset(b->d, 0, b->len * BITMAP_BYTES);
+ b->top = 0;
+}
+
+int
+bitmap_test_bit(struct bitmap *b, u_int n)
+{
+ if (b->top >= b->len)
+ return 0; /* invalid */
+ if (b->len == 0 || (n / BITMAP_BITS) > b->top)
+ return 0;
+ return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
+}
+
+static int
+reserve(struct bitmap *b, u_int n)
+{
+ BITMAP_WTYPE *tmp;
+ size_t nlen;
+
+ if (b->top >= b->len || n > BITMAP_MAX)
+ return -1; /* invalid */
+ nlen = (n / BITMAP_BITS) + 1;
+ if (b->len < nlen) {
+ if ((tmp = recallocarray(b->d, b->len,
+ nlen, BITMAP_BYTES)) == NULL)
+ return -1;
+ b->d = tmp;
+ b->len = nlen;
+ }
+ return 0;
+}
+
+int
+bitmap_set_bit(struct bitmap *b, u_int n)
+{
+ int r;
+ size_t offset;
+
+ if ((r = reserve(b, n)) != 0)
+ return r;
+ offset = n / BITMAP_BITS;
+ if (offset > b->top)
+ b->top = offset;
+ b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
+ return 0;
+}
+
+/* Resets b->top to point to the most significant bit set in b->d */
+static void
+retop(struct bitmap *b)
+{
+ if (b->top >= b->len)
+ return;
+ while (b->top > 0 && b->d[b->top] == 0)
+ b->top--;
+}
+
+void
+bitmap_clear_bit(struct bitmap *b, u_int n)
+{
+ size_t offset;
+
+ if (b->top >= b->len || n > BITMAP_MAX)
+ return; /* invalid */
+ offset = n / BITMAP_BITS;
+ if (offset > b->top)
+ return;
+ b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
+ /* The top may have changed as a result of the clear */
+ retop(b);
+}
+
+size_t
+bitmap_nbits(struct bitmap *b)
+{
+ size_t bits;
+ BITMAP_WTYPE w;
+
+ retop(b);
+ if (b->top >= b->len)
+ return 0; /* invalid */
+ if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
+ return 0;
+ /* Find MSB set */
+ w = b->d[b->top];
+ bits = (b->top + 1) * BITMAP_BITS;
+ while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
+ w <<= 1;
+ bits--;
+ }
+ return bits;
+}
+
+size_t
+bitmap_nbytes(struct bitmap *b)
+{
+ return (bitmap_nbits(b) + 7) / 8;
+}
+
+int
+bitmap_to_string(struct bitmap *b, void *p, size_t l)
+{
+ u_char *s = (u_char *)p;
+ size_t i, j, k, need = bitmap_nbytes(b);
+
+ if (l < need || b->top >= b->len)
+ return -1;
+ if (l > need)
+ l = need;
+ /* Put the bytes from LSB backwards */
+ for (i = k = 0; i < b->top + 1; i++) {
+ for (j = 0; j < BITMAP_BYTES; j++) {
+ if (k >= l)
+ break;
+ s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
+ }
+ }
+ return 0;
+}
+
+int
+bitmap_from_string(struct bitmap *b, const void *p, size_t l)
+{
+ int r;
+ size_t i, offset, shift;
+ const u_char *s = (const u_char *)p;
+
+ if (l > BITMAP_MAX / 8)
+ return -1;
+ if ((r = reserve(b, l * 8)) != 0)
+ return r;
+ bitmap_zero(b);
+ if (l == 0)
+ return 0;
+ b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
+ shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
+ for (i = 0; i < l; i++) {
+ b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
+ if (shift == 0) {
+ offset--;
+ shift = BITMAP_BITS - 8;
+ } else
+ shift -= 8;
+ }
+ retop(b);
+ return 0;
+}