![[BACK]](/icons/back.gif){kind=icon}
Return to bitmap.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh|
Return to bitmap.c CVS log | Up to [local] / src / usr.bin / ssh |
1.1 djm 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 <sys/types.h>
18: #include <string.h>
19: #include <stdlib.h>
20:
21: #include "bitmap.h"
22:
23: #define BITMAP_WTYPE u_int
24: #define BITMAP_MAX (1<<24)
25: #define BITMAP_BYTES (sizeof(BITMAP_WTYPE))
26: #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)
27: #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)
28: struct bitmap {
29: BITMAP_WTYPE *d;
30: size_t len; /* number of words allocated */
31: size_t top; /* index of top word allocated */
32: };
33:
34: struct bitmap *
35: bitmap_new(void)
36: {
37: struct bitmap *ret;
38:
39: if ((ret = calloc(1, sizeof(*ret))) == NULL)
40: return NULL;
41: if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
42: free(ret);
43: return NULL;
44: }
45: ret->len = 1;
46: ret->top = 0;
47: return ret;
48: }
49:
50: void
51: bitmap_free(struct bitmap *b)
52: {
53: if (b != NULL && b->d != NULL) {
1.4 ! guenther 54: explicit_bzero(b->d, b->len);
1.1 djm 55: free(b->d);
56: }
57: free(b);
58: }
59:
60: void
61: bitmap_zero(struct bitmap *b)
62: {
63: memset(b->d, 0, b->len * BITMAP_BYTES);
64: b->top = 0;
65: }
66:
67: int
68: bitmap_test_bit(struct bitmap *b, u_int n)
69: {
70: if (b->top >= b->len)
71: return 0; /* invalid */
72: if (b->len == 0 || (n / BITMAP_BITS) > b->top)
73: return 0;
74: return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
75: }
76:
77: static int
78: reserve(struct bitmap *b, u_int n)
79: {
80: BITMAP_WTYPE *tmp;
81: size_t nlen;
82:
83: if (b->top >= b->len || n > BITMAP_MAX)
84: return -1; /* invalid */
85: nlen = (n / BITMAP_BITS) + 1;
86: if (b->len < nlen) {
87: if ((tmp = reallocarray(b->d, nlen, BITMAP_BYTES)) == NULL)
88: return -1;
89: b->d = tmp;
90: memset(b->d + b->len, 0, (nlen - b->len) * BITMAP_BYTES);
91: b->len = nlen;
92: }
93: return 0;
94: }
95:
96: int
97: bitmap_set_bit(struct bitmap *b, u_int n)
98: {
99: int r;
100: size_t offset;
101:
102: if ((r = reserve(b, n)) != 0)
103: return r;
104: offset = n / BITMAP_BITS;
105: if (offset > b->top)
106: b->top = offset;
107: b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
108: return 0;
109: }
110:
111: /* Resets b->top to point to the most significant bit set in b->d */
112: static void
113: retop(struct bitmap *b)
114: {
115: if (b->top >= b->len)
116: return;
117: while (b->top > 0 && b->d[b->top] == 0)
118: b->top--;
119: }
120:
121: void
122: bitmap_clear_bit(struct bitmap *b, u_int n)
123: {
124: size_t offset;
125:
126: if (b->top >= b->len || n > BITMAP_MAX)
127: return; /* invalid */
128: offset = n / BITMAP_BITS;
129: if (offset > b->top)
130: return;
131: b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
132: /* The top may have changed as a result of the clear */
133: retop(b);
134: }
135:
136: size_t
137: bitmap_nbits(struct bitmap *b)
138: {
139: size_t bits;
140: BITMAP_WTYPE w;
141:
142: retop(b);
143: if (b->top >= b->len)
144: return 0; /* invalid */
145: if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
146: return 0;
147: /* Find MSB set */
148: w = b->d[b->top];
149: bits = (b->top + 1) * BITMAP_BITS;
150: while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
151: w <<= 1;
152: bits--;
153: }
154: return bits;
155: }
156:
157: size_t
158: bitmap_nbytes(struct bitmap *b)
159: {
160: return (bitmap_nbits(b) + 7) / 8;
161: }
162:
163: int
164: bitmap_to_string(struct bitmap *b, void *p, size_t l)
165: {
166: u_char *s = (u_char *)p;
167: size_t i, j, k, need = bitmap_nbytes(b);
168:
169: if (l < need || b->top >= b->len)
170: return -1;
171: if (l > need)
172: l = need;
173: /* Put the bytes from LSB backwards */
174: for (i = k = 0; i < b->top + 1; i++) {
175: for (j = 0; j < BITMAP_BYTES; j++) {
176: if (k >= l)
177: break;
178: s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
179: }
180: }
181: return 0;
182: }
183:
184: int
185: bitmap_from_string(struct bitmap *b, const void *p, size_t l)
186: {
187: int r;
188: size_t i, offset, shift;
189: u_char *s = (u_char *)p;
190:
191: if (l > BITMAP_MAX / 8)
192: return -1;
193: if ((r = reserve(b, l * 8)) != 0)
194: return r;
195: bitmap_zero(b);
196: if (l == 0)
197: return 0;
198: b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
199: shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
200: for (i = 0; i < l; i++) {
201: b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
202: if (shift == 0) {
203: offset--;
204: shift = BITMAP_BITS - 8;
205: } else
206: shift -= 8;
207: }
208: retop(b);
209: return 0;
210: }