2 * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
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.
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.
19 #include <sys/types.h>
25 #define BITMAP_WTYPE u_int
26 #define BITMAP_MAX (1<<24)
27 #define BITMAP_BYTES (sizeof(BITMAP_WTYPE))
28 #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)
29 #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)
32 size_t len
; /* number of words allocated */
33 size_t top
; /* index of top word allocated */
41 if ((ret
= calloc(1, sizeof(*ret
))) == NULL
)
43 if ((ret
->d
= calloc(1, BITMAP_BYTES
)) == NULL
) {
53 bitmap_free(struct bitmap
*b
)
55 if (b
!= NULL
&& b
->d
!= NULL
) {
56 explicit_bzero(b
->d
, b
->len
);
63 bitmap_zero(struct bitmap
*b
)
65 memset(b
->d
, 0, b
->len
* BITMAP_BYTES
);
70 bitmap_test_bit(struct bitmap
*b
, u_int n
)
73 return 0; /* invalid */
74 if (b
->len
== 0 || (n
/ BITMAP_BITS
) > b
->top
)
76 return (b
->d
[n
/ BITMAP_BITS
] >> (n
& BITMAP_WMASK
)) & 1;
80 reserve(struct bitmap
*b
, u_int n
)
85 if (b
->top
>= b
->len
|| n
> BITMAP_MAX
)
86 return -1; /* invalid */
87 nlen
= (n
/ BITMAP_BITS
) + 1;
89 if ((tmp
= reallocarray(b
->d
, nlen
, BITMAP_BYTES
)) == NULL
)
92 memset(b
->d
+ b
->len
, 0, (nlen
- b
->len
) * BITMAP_BYTES
);
99 bitmap_set_bit(struct bitmap
*b
, u_int n
)
104 if ((r
= reserve(b
, n
)) != 0)
106 offset
= n
/ BITMAP_BITS
;
109 b
->d
[offset
] |= (BITMAP_WTYPE
)1 << (n
& BITMAP_WMASK
);
113 /* Resets b->top to point to the most significant bit set in b->d */
115 retop(struct bitmap
*b
)
117 if (b
->top
>= b
->len
)
119 while (b
->top
> 0 && b
->d
[b
->top
] == 0)
124 bitmap_clear_bit(struct bitmap
*b
, u_int n
)
128 if (b
->top
>= b
->len
|| n
> BITMAP_MAX
)
129 return; /* invalid */
130 offset
= n
/ BITMAP_BITS
;
133 b
->d
[offset
] &= ~((BITMAP_WTYPE
)1 << (n
& BITMAP_WMASK
));
134 /* The top may have changed as a result of the clear */
139 bitmap_nbits(struct bitmap
*b
)
145 if (b
->top
>= b
->len
)
146 return 0; /* invalid */
147 if (b
->len
== 0 || (b
->top
== 0 && b
->d
[0] == 0))
151 bits
= (b
->top
+ 1) * BITMAP_BITS
;
152 while (!(w
& ((BITMAP_WTYPE
)1 << (BITMAP_BITS
- 1)))) {
160 bitmap_nbytes(struct bitmap
*b
)
162 return (bitmap_nbits(b
) + 7) / 8;
166 bitmap_to_string(struct bitmap
*b
, void *p
, size_t l
)
168 u_char
*s
= (u_char
*)p
;
169 size_t i
, j
, k
, need
= bitmap_nbytes(b
);
171 if (l
< need
|| b
->top
>= b
->len
)
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
++) {
180 s
[need
- 1 - k
++] = (b
->d
[i
] >> (j
* 8)) & 0xff;
187 bitmap_from_string(struct bitmap
*b
, const void *p
, size_t l
)
190 size_t i
, offset
, shift
;
191 u_char
*s
= (u_char
*)p
;
193 if (l
> BITMAP_MAX
/ 8)
195 if ((r
= reserve(b
, l
* 8)) != 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
;
206 shift
= BITMAP_BITS
- 8;