1 /*
2 ** Copyright (C) 2005-2020 by Carnegie Mellon University.
3 **
4 ** @OPENSOURCE_LICENSE_START@
5 ** See license information in ../../LICENSE.txt
6 ** @OPENSOURCE_LICENSE_END@
7 */
8
9 /*
10 ** skbitmap.c
11 **
12 ** Bitmap creatation and deletion.
13 **
14 */
15
16
17 #include <silk/silk.h>
18
19 RCSIDENT("$SiLK: skbitmap.c ef14e54179be 2020-04-14 21:57:45Z mthomas $");
20
21 #include <silk/utils.h>
22
23
24 /* LOCAL DEFINES AND TYPEDEFS */
25
26 /*
27 * Return number of 32bit words needed to hold a bitmap with
28 * 'num_bits' elements. Need to add 1 if number of bits is not an
29 * even multiple of 32.
30 */
31 #define BITMAP_GET_WORD_COUNT(num_bits) \
32 (((num_bits) >> 5) + !!((num_bits) & 0x1F))
33
34
35 /* FUNCTION DEFINITIONS */
36
37 /*
38 * Return the number of trailing zeros in 'v'. Note: This function
39 * assumes 'v' is non-zero; it will return 31 if 'v' is 0.
40 */
41 static uint8_t
bitmapCountTrailingZeros(uint32_t v)42 bitmapCountTrailingZeros(
43 uint32_t v)
44 {
45 uint8_t c = 1;
46 if ((v & 0xffff) == 0) {
47 v >>= 16;
48 c += 16;
49 }
50 if ((v & 0xff) == 0) {
51 v >>= 8;
52 c += 8;
53 }
54 if ((v & 0xf) == 0) {
55 v >>= 4;
56 c += 4;
57 }
58 if ((v & 0x3) == 0) {
59 v >>= 2;
60 c += 2;
61 }
62 return c - (uint8_t)(v & 0x1);
63 }
64
65
66 int
skBitmapBind(sk_bitmap_t * bitmap,uint32_t num_bits,uint32_t * bitarray,size_t sizeof_bitarray)67 skBitmapBind(
68 sk_bitmap_t *bitmap,
69 uint32_t num_bits,
70 uint32_t *bitarray,
71 size_t sizeof_bitarray)
72 {
73 uint32_t word_count = BITMAP_GET_WORD_COUNT(num_bits);
74
75 if ( !(bitmap && num_bits && bitarray && sizeof_bitarray)) {
76 return -1;
77 }
78
79 if (sizeof_bitarray < (word_count * sizeof(uint32_t))) {
80 return -1;
81 }
82
83 memset(bitarray, 0, sizeof_bitarray);
84 bitmap->map = bitarray;
85 bitmap->num_bits = num_bits;
86 bitmap->count = 0;
87
88 return 0;
89 }
90
91
92 int
skBitmapCreate(sk_bitmap_t ** bitmap_out,uint32_t num_bits)93 skBitmapCreate(
94 sk_bitmap_t **bitmap_out,
95 uint32_t num_bits)
96 {
97 uint32_t word_count = BITMAP_GET_WORD_COUNT(num_bits);
98
99 assert(bitmap_out);
100
101 if (num_bits == 0) {
102 *bitmap_out = NULL;
103 return -1;
104 }
105
106 *bitmap_out = (sk_bitmap_t*)calloc(1, sizeof(sk_bitmap_t));
107 if (*bitmap_out == NULL) {
108 return -1;
109 }
110
111 (*bitmap_out)->map = (uint32_t*)calloc(word_count, sizeof(uint32_t));
112 if (NULL == (*bitmap_out)->map) {
113 free(*bitmap_out);
114 *bitmap_out = NULL;
115 return -1;
116 }
117
118 (*bitmap_out)->num_bits = num_bits;
119
120 return 0;
121 }
122
123
124 void
skBitmapDestroy(sk_bitmap_t ** bitmap)125 skBitmapDestroy(
126 sk_bitmap_t **bitmap)
127 {
128 if (!bitmap || !*bitmap) {
129 return;
130 }
131
132 free((*bitmap)->map);
133 (*bitmap)->map = NULL;
134 free(*bitmap);
135 *bitmap = NULL;
136 }
137
138
139 void
skBitmapClearAllBits(sk_bitmap_t * bitmap)140 skBitmapClearAllBits(
141 sk_bitmap_t *bitmap)
142 {
143 uint32_t word_count;
144
145 assert(bitmap);
146
147 word_count = BITMAP_GET_WORD_COUNT(bitmap->num_bits);
148
149 memset(bitmap->map, 0, word_count * sizeof(uint32_t));
150 bitmap->count = 0;
151 }
152
153
154 void
skBitmapSetAllBits(sk_bitmap_t * bitmap)155 skBitmapSetAllBits(
156 sk_bitmap_t *bitmap)
157 {
158 uint32_t word_count;
159
160 assert(bitmap);
161
162 word_count = BITMAP_GET_WORD_COUNT(bitmap->num_bits);
163
164 if ((bitmap->num_bits & 0x1F) != 0) {
165 /* last word is not fully used. handle it specially so we
166 * don't set bits that are not in use */
167 --word_count;
168 SET_MASKED_BITS(bitmap->map[word_count], UINT32_MAX,
169 0, (bitmap->num_bits & 0x1F));
170 }
171 memset(bitmap->map, 0xFF, word_count * sizeof(uint32_t));
172 bitmap->count = bitmap->num_bits;
173 }
174
175
176 uint32_t
skBitmapGetSizeF(const sk_bitmap_t * bitmap)177 skBitmapGetSizeF(
178 const sk_bitmap_t *bitmap)
179 {
180 assert(bitmap);
181
182 return skBitmapGetSizeFast(bitmap);
183 }
184
185
186 uint32_t
skBitmapGetHighCountF(const sk_bitmap_t * bitmap)187 skBitmapGetHighCountF(
188 const sk_bitmap_t *bitmap)
189 {
190 uint32_t i;
191 uint32_t count = 0;
192 uint32_t bits;
193
194 assert(bitmap);
195
196 /* check that bitmap->count is corrrect */
197 for (i=BITMAP_GET_WORD_COUNT(bitmap->num_bits)-1; i < (uint32_t)-1; --i) {
198 BITS_IN_WORD32(&bits, bitmap->map[i]);
199 count += bits;
200 }
201 assert(count == bitmap->count);
202
203 return skBitmapGetHighCountFast(bitmap);
204 }
205
206
207 int
skBitmapGetBitF(const sk_bitmap_t * bitmap,uint32_t pos)208 skBitmapGetBitF(
209 const sk_bitmap_t *bitmap,
210 uint32_t pos)
211 {
212 assert(bitmap);
213 assert(pos < bitmap->num_bits);
214
215 return skBitmapGetBitFast(bitmap, pos);
216 }
217
218
219 void
skBitmapSetBitF(sk_bitmap_t * bitmap,uint32_t pos)220 skBitmapSetBitF(
221 sk_bitmap_t *bitmap,
222 uint32_t pos)
223 {
224 assert(bitmap);
225 assert(pos < bitmap->num_bits);
226
227 skBitmapSetBitFast(bitmap, pos);
228 }
229
230
231 void
skBitmapClearBitF(sk_bitmap_t * bitmap,uint32_t pos)232 skBitmapClearBitF(
233 sk_bitmap_t *bitmap,
234 uint32_t pos)
235 {
236 assert(bitmap);
237 assert(pos < bitmap->num_bits);
238
239 skBitmapClearBitFast(bitmap, pos);
240 }
241
242
243 void
skBitmapComplement(sk_bitmap_t * bitmap)244 skBitmapComplement(
245 sk_bitmap_t *bitmap)
246 {
247 uint32_t i;
248 uint32_t bits;
249
250 assert(bitmap);
251
252 bitmap->count = 0;
253
254 i = BITMAP_GET_WORD_COUNT(bitmap->num_bits) - 1;
255
256 if (bitmap->num_bits & 0x1F) {
257 /* last word is not fully used. handle it specially so we
258 * don't complement bits that are not in use */
259 bitmap->map[i] = GET_MASKED_BITS(~bitmap->map[i], 0,
260 (bitmap->num_bits & 0x1F));
261 BITS_IN_WORD32(&bits, bitmap->map[i]);
262 bitmap->count += bits;
263 --i;
264 }
265 for ( ; i < (uint32_t)-1; --i) {
266 bitmap->map[i] = ~bitmap->map[i];
267 BITS_IN_WORD32(&bits, bitmap->map[i]);
268 bitmap->count += bits;
269 }
270 }
271
272
273 int
skBitmapIntersection(sk_bitmap_t * dest,const sk_bitmap_t * src)274 skBitmapIntersection(
275 sk_bitmap_t *dest,
276 const sk_bitmap_t *src)
277 {
278 uint32_t i;
279 uint32_t bits;
280
281 assert(dest);
282 assert(src);
283
284 if (dest->num_bits != src->num_bits) {
285 return -1;
286 }
287
288 dest->count = 0;
289 for (i = BITMAP_GET_WORD_COUNT(src->num_bits) - 1; i < (uint32_t)-1; --i) {
290 dest->map[i] &= src->map[i];
291 BITS_IN_WORD32(&bits, dest->map[i]);
292 dest->count += bits;
293 }
294 return 0;
295 }
296
297
298 int
skBitmapUnion(sk_bitmap_t * dest,const sk_bitmap_t * src)299 skBitmapUnion(
300 sk_bitmap_t *dest,
301 const sk_bitmap_t *src)
302 {
303 uint32_t i;
304 uint32_t bits;
305
306 assert(dest);
307 assert(src);
308
309 if (dest->num_bits != src->num_bits) {
310 return -1;
311 }
312
313 dest->count = 0;
314 for (i = BITMAP_GET_WORD_COUNT(src->num_bits) - 1; i < (uint32_t)-1; --i) {
315 dest->map[i] |= src->map[i];
316 BITS_IN_WORD32(&bits, dest->map[i]);
317 dest->count += bits;
318 }
319 return 0;
320 }
321
322
323 uint32_t
skBitmapCountConsecutive(const sk_bitmap_t * bitmap,uint32_t begin_pos,uint32_t state)324 skBitmapCountConsecutive(
325 const sk_bitmap_t *bitmap,
326 uint32_t begin_pos,
327 uint32_t state)
328 {
329 uint32_t count = 0;
330 uint32_t value;
331 uint32_t limit;
332 uint32_t i;
333
334 assert(bitmap);
335 if (begin_pos >= bitmap->num_bits) {
336 return UINT32_MAX;
337 }
338
339 i = _BMAP_INDEX(begin_pos);
340 limit = _BMAP_INDEX(bitmap->num_bits - 1);
341
342 if (i == limit) {
343 /* look at a single word */
344 value = GET_MASKED_BITS((state ? ~bitmap->map[i] : bitmap->map[i]),
345 begin_pos & 0x1F, bitmap->num_bits-begin_pos);
346 if (value) {
347 return bitmapCountTrailingZeros(value);
348 }
349 return bitmap->num_bits - begin_pos;
350 }
351
352 if (begin_pos & 0x1F) {
353 /* first bit is not least significant bit */
354 value = GET_MASKED_BITS((state ? ~(bitmap->map[i]) : bitmap->map[i]),
355 begin_pos & 0x1F, 32 - (begin_pos & 0x1F));
356 if (value) {
357 return bitmapCountTrailingZeros(value);
358 }
359 count += 32 - (begin_pos & 0x1F);
360 ++i;
361 }
362
363 if ((bitmap->num_bits & 0x1F) == 0) {
364 /* no need to handle final word specially */
365 ++limit;
366 }
367
368 if (state) {
369 for (; i < limit; ++i) {
370 if (UINT32_MAX == bitmap->map[i]) {
371 count += 32;
372 } else {
373 return count + bitmapCountTrailingZeros(~bitmap->map[i]);
374 }
375 }
376 } else {
377 for (; i < limit; ++i) {
378 if (0 == bitmap->map[i]) {
379 count += 32;
380 } else {
381 return count + bitmapCountTrailingZeros(bitmap->map[i]);
382 }
383 }
384 }
385
386 if (bitmap->num_bits & 0x1F) {
387 /* handle final partially filled word */
388 value = GET_MASKED_BITS((state ? ~(bitmap->map[i]) : bitmap->map[i]),
389 0, (bitmap->num_bits & 0x1F));
390 if (value) {
391 return count + bitmapCountTrailingZeros(value);
392 }
393 count += (bitmap->num_bits & 0x1F);
394 }
395
396 return count;
397 }
398
399
400 int
skBitmapRangeSet(sk_bitmap_t * bitmap,uint32_t begin_pos,uint32_t end_pos)401 skBitmapRangeSet(
402 sk_bitmap_t *bitmap,
403 uint32_t begin_pos,
404 uint32_t end_pos)
405 {
406 uint32_t prev;
407 uint32_t bits;
408 uint32_t i;
409
410 assert(bitmap);
411 if (begin_pos > end_pos || end_pos >= bitmap->num_bits) {
412 return -1;
413 }
414
415 i = _BMAP_INDEX(begin_pos);
416 if (i == _BMAP_INDEX(end_pos)) {
417 /* range is in a single word */
418 prev = bitmap->map[i];
419 SET_MASKED_BITS(bitmap->map[i], UINT32_MAX,
420 begin_pos & 0x1F, 1 + end_pos - begin_pos);
421 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
422 bitmap->count += bits;
423 return 0;
424 }
425
426 prev = bitmap->map[i];
427 SET_MASKED_BITS(bitmap->map[i], UINT32_MAX, begin_pos & 0x1F,
428 32 - (begin_pos & 0x1F));
429 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
430 bitmap->count += bits;
431
432 for (++i; i < _BMAP_INDEX(end_pos); ++i) {
433 BITS_IN_WORD32(&bits, bitmap->map[i]);
434 bitmap->count += 32 - bits;
435 bitmap->map[i] = UINT32_MAX;
436 }
437
438 prev = bitmap->map[i];
439 SET_MASKED_BITS(bitmap->map[i], UINT32_MAX, 0, 1 + (end_pos & 0x1F));
440 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
441 bitmap->count += bits;
442 return 0;
443 }
444
445
446 int
skBitmapRangeClear(sk_bitmap_t * bitmap,uint32_t begin_pos,uint32_t end_pos)447 skBitmapRangeClear(
448 sk_bitmap_t *bitmap,
449 uint32_t begin_pos,
450 uint32_t end_pos)
451 {
452 uint32_t prev;
453 uint32_t bits;
454 uint32_t i;
455
456 assert(bitmap);
457 if (begin_pos > end_pos || end_pos >= bitmap->num_bits) {
458 return -1;
459 }
460
461 i = _BMAP_INDEX(begin_pos);
462 if (i == _BMAP_INDEX(end_pos)) {
463 /* range is in a single word */
464 prev = bitmap->map[i];
465 SET_MASKED_BITS(bitmap->map[i], 0,
466 begin_pos & 0x1F, 1 + end_pos - begin_pos);
467 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
468 bitmap->count -= bits;
469 return 0;
470 }
471
472 prev = bitmap->map[i];
473 SET_MASKED_BITS(bitmap->map[i], 0, begin_pos & 0x1F,
474 32 - (begin_pos & 0x1F));
475 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
476 bitmap->count -= bits;
477
478 for (++i; i < _BMAP_INDEX(end_pos); ++i) {
479 BITS_IN_WORD32(&bits, bitmap->map[i]);
480 bitmap->count -= bits;
481 bitmap->map[i] = 0;
482 }
483
484 prev = bitmap->map[i];
485 SET_MASKED_BITS(bitmap->map[i], 0, 0, 1 + (end_pos & 0x1F));
486 BITS_IN_WORD32(&bits, prev ^ bitmap->map[i]);
487 bitmap->count -= bits;
488 return 0;
489 }
490
491
492 uint32_t
skBitmapRangeCountHigh(sk_bitmap_t * bitmap,uint32_t begin_pos,uint32_t end_pos)493 skBitmapRangeCountHigh(
494 sk_bitmap_t *bitmap,
495 uint32_t begin_pos,
496 uint32_t end_pos)
497 {
498 uint32_t value;
499 uint32_t bits1;
500 uint32_t bits2;
501 uint32_t i;
502
503 assert(bitmap);
504 if (begin_pos > end_pos || end_pos >= bitmap->num_bits) {
505 return UINT32_MAX;
506 }
507
508 i = _BMAP_INDEX(begin_pos);
509 if (i == _BMAP_INDEX(end_pos)) {
510 /* range is in a single word */
511 value = GET_MASKED_BITS(bitmap->map[i], begin_pos & 0x1F,
512 1 + end_pos - begin_pos);
513 BITS_IN_WORD32(&bits1, value);
514 return bits1;
515 }
516
517 value = GET_MASKED_BITS(bitmap->map[i], begin_pos & 0x1F,
518 32 - (begin_pos & 0x1F));
519 BITS_IN_WORD32(&bits1, value);
520 value = GET_MASKED_BITS(bitmap->map[_BMAP_INDEX(end_pos)],
521 0, 1 + (end_pos & 0x1F));
522 BITS_IN_WORD32(&bits2, value);
523
524 return (bits1 + bits2 + 32 * (_BMAP_INDEX(end_pos) - i - 1));
525 }
526
527
528 void
skBitmapIteratorBind(const sk_bitmap_t * bitmap,sk_bitmap_iter_t * iter)529 skBitmapIteratorBind(
530 const sk_bitmap_t *bitmap,
531 sk_bitmap_iter_t *iter)
532 {
533 assert(bitmap);
534 assert(iter);
535
536 memset(iter, 0, sizeof(sk_bitmap_iter_t));
537 iter->bitmap = bitmap;
538 skBitmapIteratorReset(iter);
539 }
540
541
542 int
skBitmapIteratorNext(sk_bitmap_iter_t * iter,uint32_t * pos)543 skBitmapIteratorNext(
544 sk_bitmap_iter_t *iter,
545 uint32_t *pos)
546 {
547 uint32_t word_count;
548
549 assert(iter);
550 assert(pos);
551
552 word_count = BITMAP_GET_WORD_COUNT(iter->bitmap->num_bits);
553 if (word_count == iter->map_idx) {
554 return SK_ITERATOR_NO_MORE_ENTRIES;
555 }
556
557 if (iter->bitmap->map[iter->map_idx] >> iter->pos) {
558 /* find next bit in current word */
559 iter->pos += bitmapCountTrailingZeros(iter->bitmap->map[iter->map_idx]
560 >> iter->pos);
561 *pos = ((iter->map_idx << 5) | iter->pos);
562 if (iter->pos < 31) {
563 ++iter->pos;
564 } else {
565 ++iter->map_idx;
566 iter->pos = 0;
567 }
568 return SK_ITERATOR_OK;
569 }
570
571 /* find next word with bits */
572 for (++iter->map_idx; iter->map_idx < word_count; ++iter->map_idx) {
573 if (iter->bitmap->map[iter->map_idx]) {
574 iter->pos
575 = bitmapCountTrailingZeros(iter->bitmap->map[iter->map_idx]);
576 *pos = ((iter->map_idx << 5) | iter->pos);
577 if (iter->pos < 31) {
578 ++iter->pos;
579 } else {
580 ++iter->map_idx;
581 iter->pos = 0;
582 }
583 return SK_ITERATOR_OK;
584 }
585 }
586
587 return SK_ITERATOR_NO_MORE_ENTRIES;
588 }
589
590
591 void
skBitmapIteratorReset(sk_bitmap_iter_t * iter)592 skBitmapIteratorReset(
593 sk_bitmap_iter_t *iter)
594 {
595 assert(iter);
596
597 iter->map_idx = 0;
598 iter->pos = 0;
599 }
600
601
602 /*
603 ** Local Variables:
604 ** mode:c
605 ** indent-tabs-mode:nil
606 ** c-basic-offset:4
607 ** End:
608 */
609