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