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