1 /*****************************************************************************\
2 * bitstring.c - bitmap manipulation functions
3 *****************************************************************************
4 * See comments about origin, limitations, and internal structure in
5 * bitstring.h.
6 *
7 * Copyright (C) 2002 The Regents of the University of California.
8 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
9 * Written by Jim Garlick <garlick@llnl.gov>, Morris Jette <jette1@llnl.gov>
10 * CODE-OCEC-09-009. All rights reserved.
11 *
12 * This file is part of Slurm, a resource management program.
13 * For details, see <https://slurm.schedmd.com/>.
14 * Please also read the included file: DISCLAIMER.
15 *
16 * Slurm is free software; you can redistribute it and/or modify it under
17 * the terms of the GNU General Public License as published by the Free
18 * Software Foundation; either version 2 of the License, or (at your option)
19 * any later version.
20 *
21 * In addition, as a special exception, the copyright holders give permission
22 * to link the code of portions of this program with the OpenSSL library under
23 * certain conditions as described in each individual source file, and
24 * distribute linked combinations including the two. You must obey the GNU
25 * General Public License in all respects for all of the code used other than
26 * OpenSSL. If you modify file(s) with this exception, you may extend this
27 * exception to your version of the file(s), but you are not obligated to do
28 * so. If you do not wish to do so, delete this exception statement from your
29 * version. If you delete this exception statement from all source files in
30 * the program, then also delete it here.
31 *
32 * Slurm is distributed in the hope that it will be useful, but WITHOUT ANY
33 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
34 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
35 * details.
36 *
37 * You should have received a copy of the GNU General Public License along
38 * with Slurm; if not, write to the Free Software Foundation, Inc.,
39 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
40 \*****************************************************************************/
41
42 #include "config.h"
43
44 #include <ctype.h>
45 #include <stdio.h>
46 #include <stdlib.h>
47 #include <string.h>
48
49 #include "src/common/bitstring.h"
50 #include "src/common/log.h"
51 #include "src/common/macros.h"
52 #include "src/common/xassert.h"
53 #include "src/common/xmalloc.h"
54 #include "src/common/xstring.h"
55
56 /* word of the bitstring bit is in */
57 #define _bit_word(bit) (((bit) >> BITSTR_SHIFT) + BITSTR_OVERHEAD)
58
59 /* address of the byte containing bit */
60 #define _bit_byteaddr(name, bit) \
61 ((char *)((name) + BITSTR_OVERHEAD) + ((bit) >> BITSTR_SHIFT_WORD8))
62
63 /* mask for the bit within its word */
64 #ifdef SLURM_BIGENDIAN
65 #define _bit_mask(bit) ((bitstr_t)1 << (BITSTR_MAXPOS - ((bit)&BITSTR_MAXPOS)))
66 #else
67 #define _bit_mask(bit) ((bitstr_t)1 << ((bit)&BITSTR_MAXPOS))
68 #endif
69
70 /* number of bits actually allocated to a bitstr */
71 #define _bitstr_bits(name) ((name)[1])
72
73 /* magic cookie stored here */
74 #define _bitstr_magic(name) ((name)[0])
75
76 /* words in a bitstring of nbits bits */
77 #define _bitstr_words(nbits) \
78 ((((nbits) + BITSTR_MAXPOS) >> BITSTR_SHIFT) + BITSTR_OVERHEAD)
79
80 /* check signature */
81 #define _assert_bitstr_valid(name) do { \
82 xassert((name) != NULL); \
83 xassert(_bitstr_magic(name) == BITSTR_MAGIC \
84 || _bitstr_magic(name) == BITSTR_MAGIC_STACK); \
85 } while (0)
86
87 /* check bit position */
88 #define _assert_bit_valid(name,bit) do { \
89 xassert((bit) >= 0); \
90 xassert((bit) < _bitstr_bits(name)); \
91 } while (0)
92
93
94 /* Ensure valid bitmap size, prevent overflow in buffer size calculation */
95 #define _assert_valid_size(bit) do { \
96 xassert((bit) > 0); \
97 xassert((bit) <= 0x40000000); \
98 } while (0)
99
100 /*
101 * external macros
102 */
103
104 /* allocate a bitstring on the stack */
105 /* XXX bit_decl does not check if nbits overflows word 1 */
106 #define bit_decl(name, nbits) \
107 (name)[_bitstr_words(nbits)] = { BITSTR_MAGIC_STACK, (nbits) }
108
109 /*
110 * Define slurm-specific aliases for use by plugins, see slurm_xlator.h
111 * for details.
112 */
113 strong_alias(bit_alloc, slurm_bit_alloc);
114 strong_alias(bit_test, slurm_bit_test);
115 strong_alias(bit_set, slurm_bit_set);
116 strong_alias(bit_clear, slurm_bit_clear);
117 strong_alias(bit_nclear, slurm_bit_nclear);
118 strong_alias(bit_nset, slurm_bit_nset);
119 strong_alias(bit_set_all, slurm_bit_set_all);
120 strong_alias(bit_clear_all, slurm_bit_clear_all);
121 strong_alias(bit_ffc, slurm_bit_ffc);
122 strong_alias(bit_ffs, slurm_bit_ffs);
123 strong_alias(bit_free, slurm_bit_free);
124 strong_alias(bit_realloc, slurm_bit_realloc);
125 strong_alias(bit_size, slurm_bit_size);
126 strong_alias(bit_and, slurm_bit_and);
127 strong_alias(bit_not, slurm_bit_not);
128 strong_alias(bit_or, slurm_bit_or);
129 strong_alias(bit_set_count, slurm_bit_set_count);
130 strong_alias(bit_set_count_range, slurm_bit_set_count_range);
131 strong_alias(bit_clear_count, slurm_bit_clear_count);
132 strong_alias(bit_clear_count_range, slurm_bit_clear_count_range);
133 strong_alias(bit_nset_max_count,slurm_bit_nset_max_count);
134 strong_alias(bit_rotate_copy, slurm_bit_rotate_copy);
135 strong_alias(bit_rotate, slurm_bit_rotate);
136 strong_alias(bit_fmt, slurm_bit_fmt);
137 strong_alias(bit_fmt_full, slurm_bit_fmt_full);
138 strong_alias(bit_unfmt, slurm_bit_unfmt);
139 strong_alias(bitfmt2int, slurm_bitfmt2int);
140 strong_alias(bit_fmt_hexmask, slurm_bit_fmt_hexmask);
141 strong_alias(bit_unfmt_hexmask, slurm_bit_unfmt_hexmask);
142 strong_alias(bit_fmt_binmask, slurm_bit_fmt_binmask);
143 strong_alias(bit_unfmt_binmask, slurm_bit_unfmt_binmask);
144 strong_alias(bit_fls, slurm_bit_fls);
145 strong_alias(bit_fill_gaps, slurm_bit_fill_gaps);
146 strong_alias(bit_super_set, slurm_bit_super_set);
147 strong_alias(bit_overlap, slurm_bit_overlap);
148 strong_alias(bit_overlap_any, slurm_bit_overlap_any);
149 strong_alias(bit_equal, slurm_bit_equal);
150 strong_alias(bit_copy, slurm_bit_copy);
151 strong_alias(bit_pick_cnt, slurm_bit_pick_cnt);
152 strong_alias(bit_nffc, slurm_bit_nffc);
153 strong_alias(bit_noc, slurm_bit_noc);
154 strong_alias(bit_nffs, slurm_bit_nffs);
155 strong_alias(bit_copybits, slurm_bit_copybits);
156 strong_alias(bit_get_bit_num, slurm_bit_get_bit_num);
157 strong_alias(bit_get_pos_num, slurm_bit_get_pos_num);
158
159 /*
160 * Allocate a bitstring.
161 * nbits (IN) valid bits in new bitstring, initialized to all clear
162 * RETURN new bitstring
163 */
bit_alloc(bitoff_t nbits)164 bitstr_t *bit_alloc(bitoff_t nbits)
165 {
166 bitstr_t *new;
167
168 _assert_valid_size(nbits);
169 new = xmalloc(_bitstr_words(nbits) * sizeof(bitstr_t));
170
171 _bitstr_magic(new) = BITSTR_MAGIC;
172 _bitstr_bits(new) = nbits;
173 return new;
174 }
175
176 /*
177 * Reallocate a bitstring (expand or contract size).
178 * b (IN) pointer to old bitstring
179 * nbits (IN) valid bits in new bitstr
180 * RETURN new bitstring
181 */
bit_realloc(bitstr_t * b,bitoff_t nbits)182 bitstr_t *bit_realloc(bitstr_t *b, bitoff_t nbits)
183 {
184 bitstr_t *new = NULL;
185
186 _assert_bitstr_valid(b);
187 _assert_valid_size(nbits);
188 new = xrealloc(b, _bitstr_words(nbits) * sizeof(bitstr_t));
189
190 _assert_bitstr_valid(new);
191 _bitstr_bits(new) = nbits;
192
193 return new;
194 }
195
196 /*
197 * Free a bitstr.
198 * b (IN/OUT) bitstr to be freed
199 */
200 void
bit_free(bitstr_t * b)201 bit_free(bitstr_t *b)
202 {
203 xassert(b);
204 xassert(_bitstr_magic(b) == BITSTR_MAGIC);
205 _bitstr_magic(b) = 0;
206 xfree(b);
207 }
208
209 /*
210 * Return the number of possible bits in a bitstring.
211 * b (IN) bitstring to check
212 * RETURN number of bits allocated
213 */
214 bitoff_t
bit_size(bitstr_t * b)215 bit_size(bitstr_t *b)
216 {
217 _assert_bitstr_valid(b);
218 return _bitstr_bits(b);
219 }
220
221 /*
222 * Is bit N of bitstring b set?
223 * b (IN) bitstring to test
224 * bit (IN) bit position to test
225 * RETURN 1 if bit set, 0 if clear
226 */
227 int
bit_test(bitstr_t * b,bitoff_t bit)228 bit_test(bitstr_t *b, bitoff_t bit)
229 {
230 _assert_bitstr_valid(b);
231 _assert_bit_valid(b, bit);
232 return ((b[_bit_word(bit)] & _bit_mask(bit)) ? 1 : 0);
233 }
234
235 /*
236 * Set bit N of bitstring.
237 * b (IN) target bitstring
238 * bit (IN) bit position to set
239 */
240 void
bit_set(bitstr_t * b,bitoff_t bit)241 bit_set(bitstr_t *b, bitoff_t bit)
242 {
243 _assert_bitstr_valid(b);
244 _assert_bit_valid(b, bit);
245 b[_bit_word(bit)] |= _bit_mask(bit);
246 }
247
248 /*
249 * Clear bit N of bitstring
250 * b (IN) target bitstring
251 * bit (IN) bit position to clear
252 */
253 void
bit_clear(bitstr_t * b,bitoff_t bit)254 bit_clear(bitstr_t *b, bitoff_t bit)
255 {
256 _assert_bitstr_valid(b);
257 _assert_bit_valid(b, bit);
258 b[_bit_word(bit)] &= ~_bit_mask(bit);
259 }
260
261 /*
262 * Set bits start ... stop in bitstring
263 * b (IN) target bitstring
264 * start (IN) starting (low numbered) bit position
265 * stop (IN) ending (higher numbered) bit position
266 */
267 void
bit_nset(bitstr_t * b,bitoff_t start,bitoff_t stop)268 bit_nset(bitstr_t *b, bitoff_t start, bitoff_t stop)
269 {
270 _assert_bitstr_valid(b);
271 _assert_bit_valid(b, start);
272 _assert_bit_valid(b, stop);
273
274 while (start <= stop && start % 8 > 0) /* partial first byte? */
275 bit_set(b, start++);
276 while (stop >= start && (stop+1) % 8 > 0) /* partial last byte? */
277 bit_set(b, stop--);
278 if (stop > start) { /* now do whole bytes */
279 xassert((stop-start+1) % 8 == 0);
280 memset(_bit_byteaddr(b, start), 0xff, (stop-start+1) / 8);
281 }
282 }
283
284 /*
285 * Clear bits start ... stop in bitstring
286 * b (IN) target bitstring
287 * start (IN) starting (low numbered) bit position
288 * stop (IN) ending (higher numbered) bit position
289 */
290 void
bit_nclear(bitstr_t * b,bitoff_t start,bitoff_t stop)291 bit_nclear(bitstr_t *b, bitoff_t start, bitoff_t stop)
292 {
293 _assert_bitstr_valid(b);
294 _assert_bit_valid(b, start);
295 _assert_bit_valid(b, stop);
296
297 while (start <= stop && start % 8 > 0) /* partial first byte? */
298 bit_clear(b, start++);
299 while (stop >= start && (stop+1) % 8 > 0)/* partial last byte? */
300 bit_clear(b, stop--);
301 if (stop > start) { /* now do whole bytes */
302 xassert((stop-start+1) % 8 == 0);
303 memset(_bit_byteaddr(b, start), 0, (stop-start+1) / 8);
304 }
305 }
306
307 /*
308 * Set all bits in bitstring
309 * b (IN) target bitstring
310 */
311 void
bit_set_all(bitstr_t * b)312 bit_set_all(bitstr_t *b)
313 {
314 bit_nset(b, 0, bit_size(b)-1);
315 }
316
317 /*
318 * Clear all bits in bitstring
319 * b (IN) target bitstring
320 */
321 void
bit_clear_all(bitstr_t * b)322 bit_clear_all(bitstr_t *b)
323 {
324 bit_nclear(b, 0, bit_size(b)-1);
325 }
326
327 /*
328 * Find first bit clear in bitstring.
329 * b (IN) bitstring to search
330 * nbits (IN) number of bits to search
331 * RETURN resulting bit position (-1 if none found)
332 */
333 bitoff_t
bit_ffc(bitstr_t * b)334 bit_ffc(bitstr_t *b)
335 {
336 bitoff_t bit = 0, value = -1;
337
338 _assert_bitstr_valid(b);
339
340 while (bit < _bitstr_bits(b) && value == -1) {
341 int32_t word = _bit_word(bit);
342
343 if (b[word] == BITSTR_MAXVAL) {
344 bit += sizeof(bitstr_t)*8;
345 continue;
346 }
347 while (bit < _bitstr_bits(b) && _bit_word(bit) == word) {
348 if (!bit_test(b, bit)) {
349 value = bit;
350 break;
351 }
352 bit++;
353 }
354 }
355 return value;
356 }
357
358 /* Find the first n contiguous bits clear in b.
359 * b (IN) bitstring to search
360 * n (IN) number of bits needed
361 * RETURN position of first bit in range (-1 if none found)
362 */
363 bitoff_t
bit_nffc(bitstr_t * b,int32_t n)364 bit_nffc(bitstr_t *b, int32_t n)
365 {
366 bitoff_t value = -1;
367 bitoff_t bit;
368 int32_t cnt = 0;
369
370 _assert_bitstr_valid(b);
371 xassert(n > 0 && n < _bitstr_bits(b));
372
373 for (bit = 0; bit < _bitstr_bits(b); bit++) {
374 if (bit_test(b, bit)) { /* fail */
375 cnt = 0;
376 } else {
377 cnt++;
378 if (cnt >= n) {
379 value = bit - (cnt - 1);
380 break;
381 }
382 }
383 }
384
385 return value;
386 }
387
388 /* Find n contiguous bits clear in b starting at some offset.
389 * b (IN) bitstring to search
390 * n (IN) number of bits needed
391 * seed (IN) position at which to begin search
392 * RETURN position of first bit in range (-1 if none found)
393 */
394 bitoff_t
bit_noc(bitstr_t * b,int32_t n,int32_t seed)395 bit_noc(bitstr_t *b, int32_t n, int32_t seed)
396 {
397 bitoff_t value = -1;
398 bitoff_t bit;
399 int32_t cnt = 0;
400
401 _assert_bitstr_valid(b);
402 xassert(n > 0 && n <= _bitstr_bits(b));
403
404 if ((seed + n) >= _bitstr_bits(b))
405 seed = _bitstr_bits(b); /* skip offset test, too small */
406
407 for (bit = seed; bit < _bitstr_bits(b); bit++) { /* start at offset */
408 if (bit_test(b, bit)) { /* fail */
409 cnt = 0;
410 } else {
411 cnt++;
412 if (cnt >= n) {
413 value = bit - (cnt - 1);
414 return value;
415 }
416 }
417 }
418
419 cnt = 0; /* start at beginning */
420 for (bit = 0; bit < _bitstr_bits(b); bit++) {
421 if (bit_test(b, bit)) { /* fail */
422 if (bit >= seed)
423 break;
424 cnt = 0;
425 } else {
426 cnt++;
427 if (cnt >= n) {
428 value = bit - (cnt - 1);
429 return value;
430 }
431 }
432 }
433
434 return -1;
435 }
436
437 /* Find the first n contiguous bits set in b.
438 * b (IN) bitstring to search
439 * n (IN) number of bits needed
440 * RETURN position of first bit in range (-1 if none found)
441 */
442 bitoff_t
bit_nffs(bitstr_t * b,int32_t n)443 bit_nffs(bitstr_t *b, int32_t n)
444 {
445 bitoff_t value = -1;
446 bitoff_t bit;
447 int32_t cnt = 0;
448
449 _assert_bitstr_valid(b);
450 xassert(n > 0 && n <= _bitstr_bits(b));
451
452 for (bit = 0; bit <= _bitstr_bits(b) - n; bit++) {
453 if (!bit_test(b, bit)) { /* fail */
454 cnt = 0;
455 } else {
456 cnt++;
457 if (cnt >= n) {
458 value = bit - (cnt - 1);
459 break;
460 }
461 }
462 }
463
464 return value;
465 }
466
467 /*
468 * Find first bit set in b.
469 * b (IN) bitstring to search
470 * RETURN resulting bit position (-1 if none found)
471 */
472 bitoff_t
bit_ffs(bitstr_t * b)473 bit_ffs(bitstr_t *b)
474 {
475 bitoff_t bit = 0, value = -1;
476
477 _assert_bitstr_valid(b);
478
479 while (bit < _bitstr_bits(b) && value == -1) {
480 int32_t word = _bit_word(bit);
481
482 if (b[word] == 0) {
483 bit += sizeof(bitstr_t)*8;
484 continue;
485 }
486 #if HAVE___BUILTIN_CLZLL && (defined SLURM_BIGENDIAN)
487 value = bit + __builtin_clzll(b[word]);
488 #elif HAVE___BUILTIN_CTZLL && (!defined SLURM_BIGENDIAN)
489 value = bit + __builtin_ctzll(b[word]);
490 #else
491 while (bit < _bitstr_bits(b) && _bit_word(bit) == word) {
492 if (bit_test(b, bit)) {
493 value = bit;
494 break;
495 }
496 bit++;
497 }
498 #endif
499 }
500 if (value < _bitstr_bits(b))
501 return value;
502 else
503 return -1;
504 }
505
506 /*
507 * Find last bit set in b.
508 * b (IN) bitstring to search
509 * RETURN resulting bit position (-1 if none found)
510 */
511 bitoff_t
bit_fls(bitstr_t * b)512 bit_fls(bitstr_t *b)
513 {
514 bitoff_t bit, value = -1;
515 int32_t word;
516
517 _assert_bitstr_valid(b);
518
519 if (_bitstr_bits(b) == 0) /* empty bitstring */
520 return -1;
521
522 bit = _bitstr_bits(b) - 1; /* zero origin */
523
524 while (bit >= 0 && /* test partial words */
525 (_bit_word(bit) == _bit_word(bit + 1))) {
526 if (bit_test(b, bit)) {
527 value = bit;
528 break;
529 }
530 bit--;
531 }
532 while (bit >= 0 && value == -1) { /* test whole words */
533 word = _bit_word(bit);
534 if (b[word] == 0) {
535 bit -= sizeof(bitstr_t) * 8;
536 continue;
537 }
538 #if HAVE___BUILTIN_CTZLL && (defined SLURM_BIGENDIAN)
539 value = bit - __builtin_ctzll(b[word]);
540 #elif HAVE___BUILTIN_CLZLL && (!defined SLURM_BIGENDIAN)
541 value = bit - __builtin_clzll(b[word]);
542 #else
543 while (bit >= 0) {
544 if (bit_test(b, bit)) {
545 value = bit;
546 break;
547 }
548 bit--;
549 }
550 #endif
551 }
552 return value;
553 }
554
555 /*
556 * set all bits between the first and last bits set (i.e. fill in the gaps
557 * to make set bits contiguous)
558 */
559 void
bit_fill_gaps(bitstr_t * b)560 bit_fill_gaps(bitstr_t *b)
561 {
562 bitoff_t first, last;
563
564 _assert_bitstr_valid(b);
565
566 first = bit_ffs(b);
567 if (first == -1)
568 return;
569
570 last = bit_fls(b);
571 bit_nset(b, first, last);
572
573 return;
574 }
575
576 /*
577 * return 1 if all bits set in b1 are also set in b2, 0 0therwise
578 */
579 int
bit_super_set(bitstr_t * b1,bitstr_t * b2)580 bit_super_set(bitstr_t *b1, bitstr_t *b2)
581 {
582 bitoff_t bit;
583
584 _assert_bitstr_valid(b1);
585 _assert_bitstr_valid(b2);
586 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
587
588 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8) {
589 if (b1[_bit_word(bit)] != (b1[_bit_word(bit)] &
590 b2[_bit_word(bit)]))
591 return 0;
592 }
593
594 return 1;
595 }
596
597 /*
598 * return 1 if b1 and b2 are identical, 0 otherwise
599 */
600 extern int
bit_equal(bitstr_t * b1,bitstr_t * b2)601 bit_equal(bitstr_t *b1, bitstr_t *b2)
602 {
603 bitoff_t bit;
604
605 _assert_bitstr_valid(b1);
606 _assert_bitstr_valid(b2);
607
608 if (_bitstr_bits(b1) != _bitstr_bits(b2))
609 return 0;
610
611 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8) {
612 if (b1[_bit_word(bit)] != b2[_bit_word(bit)])
613 return 0;
614 }
615
616 return 1;
617 }
618
619
620
621 /*
622 * b1 &= b2
623 * b1 (IN/OUT) first string
624 * b2 (IN) second bitstring
625 */
626 void
bit_and(bitstr_t * b1,bitstr_t * b2)627 bit_and(bitstr_t *b1, bitstr_t *b2)
628 {
629 bitoff_t bit;
630
631 _assert_bitstr_valid(b1);
632 _assert_bitstr_valid(b2);
633 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
634
635 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8)
636 b1[_bit_word(bit)] &= b2[_bit_word(bit)];
637 }
638
639 /*
640 * b1 &= ~b2
641 * b1 (IN/OUT)
642 * b2 (IN)
643 */
bit_and_not(bitstr_t * b1,bitstr_t * b2)644 void bit_and_not(bitstr_t *b1, bitstr_t *b2)
645 {
646 bitoff_t bit;
647
648 _assert_bitstr_valid(b1);
649 _assert_bitstr_valid(b2);
650 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
651
652 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8)
653 b1[_bit_word(bit)] &= ~b2[_bit_word(bit)];
654 }
655
656 /*
657 * b1 = ~b1 one's complement
658 * b1 (IN/OUT) first bitmap
659 */
660 void
bit_not(bitstr_t * b)661 bit_not(bitstr_t *b)
662 {
663 bitoff_t bit;
664
665 _assert_bitstr_valid(b);
666
667 for (bit = 0; bit < _bitstr_bits(b); bit += sizeof(bitstr_t)*8)
668 b[_bit_word(bit)] = ~b[_bit_word(bit)];
669 }
670
671 /*
672 * b1 |= b2
673 * b1 (IN/OUT) first bitmap
674 * b2 (IN) second bitmap
675 */
676 void
bit_or(bitstr_t * b1,bitstr_t * b2)677 bit_or(bitstr_t *b1, bitstr_t *b2)
678 {
679 bitoff_t bit;
680
681 _assert_bitstr_valid(b1);
682 _assert_bitstr_valid(b2);
683 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
684
685 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8)
686 b1[_bit_word(bit)] |= b2[_bit_word(bit)];
687 }
688
689 /*
690 * b1 |= ~b2
691 * b1 (IN/OUT)
692 * b2 (IN)
693 */
bit_or_not(bitstr_t * b1,bitstr_t * b2)694 void bit_or_not(bitstr_t *b1, bitstr_t *b2)
695 {
696 bitoff_t bit;
697
698 _assert_bitstr_valid(b1);
699 _assert_bitstr_valid(b2);
700 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
701
702 for (bit = 0; bit < _bitstr_bits(b1); bit += sizeof(bitstr_t)*8)
703 b1[_bit_word(bit)] |= ~b2[_bit_word(bit)];
704 }
705
706 /*
707 * return a copy of the supplied bitmap
708 */
709 bitstr_t *
bit_copy(bitstr_t * b)710 bit_copy(bitstr_t *b)
711 {
712 bitstr_t *new;
713 int32_t newsize_bits;
714 size_t len = 0; /* Number of bytes to memcpy() */
715
716 _assert_bitstr_valid(b);
717
718 newsize_bits = bit_size(b);
719 len = (_bitstr_words(newsize_bits) - BITSTR_OVERHEAD)*sizeof(bitstr_t);
720 new = bit_alloc(newsize_bits);
721 if (new)
722 memcpy(&new[BITSTR_OVERHEAD], &b[BITSTR_OVERHEAD], len);
723
724 return new;
725 }
726
727 void
bit_copybits(bitstr_t * dest,bitstr_t * src)728 bit_copybits(bitstr_t *dest, bitstr_t *src)
729 {
730 int32_t len;
731
732 _assert_bitstr_valid(dest);
733 _assert_bitstr_valid(src);
734 xassert(bit_size(src) == bit_size(dest));
735
736 len = (_bitstr_words(bit_size(src)) - BITSTR_OVERHEAD)*sizeof(bitstr_t);
737 memcpy(&dest[BITSTR_OVERHEAD], &src[BITSTR_OVERHEAD], len);
738 }
739
740 #ifdef HAVE___BUILTIN_POPCOUNTLL
741 #define hweight __builtin_popcountll
742 #else
743 /*
744 * Returns the hamming weight (i.e. the number of bits set) in a word.
745 * NOTE: This routine borrowed from Linux 4.9 <tools/lib/hweight.c>.
746 */
747 static uint64_t
hweight(uint64_t w)748 hweight(uint64_t w)
749 {
750 w -= (w >> 1) & 0x5555555555555555ul;
751 w = (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
752 w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
753 return (w * 0x0101010101010101ul) >> 56;
754 }
755 #endif
756
757 /*
758 * Count the number of bits set in bitstring.
759 * b (IN) bitstring to check
760 * RETURN count of set bits
761 */
762 int32_t
bit_set_count(bitstr_t * b)763 bit_set_count(bitstr_t *b)
764 {
765 int32_t count = 0;
766 bitoff_t bit, bit_cnt;
767 int32_t word_size = sizeof(bitstr_t) * 8;
768
769 _assert_bitstr_valid(b);
770
771 bit_cnt = _bitstr_bits(b);
772 for (bit = 0; (bit + word_size) <= bit_cnt; bit += word_size) {
773 count += hweight(b[_bit_word(bit)]);
774 }
775 for ( ; bit < bit_cnt; bit++) {
776 if (bit_test(b, bit))
777 count++;
778 }
779 return count;
780 }
781
782 /*
783 * Count the number of bits set in a range of bitstring.
784 * b (IN) bitstring to check
785 * start (IN) first bit to check
786 * end (IN) last bit to check+1
787 * RETURN count of set bits
788 */
789 int32_t
bit_set_count_range(bitstr_t * b,int32_t start,int32_t end)790 bit_set_count_range(bitstr_t *b, int32_t start, int32_t end)
791 {
792 int32_t count = 0, eow;
793 bitoff_t bit;
794 const int32_t word_size = sizeof(bitstr_t) * 8;
795
796 _assert_bitstr_valid(b);
797 _assert_bit_valid(b,start);
798
799 end = MIN(end, _bitstr_bits(b));
800 eow = ((start+word_size-1)/word_size) * word_size; /* end of word */
801 for ( bit = start; bit < end && bit < eow; bit++) {
802 if (bit_test(b, bit))
803 count++;
804 }
805 for (; (bit + word_size) <= end ; bit += word_size) {
806 count += hweight(b[_bit_word(bit)]);
807 }
808 for ( ; bit < end; bit++) {
809 if (bit_test(b, bit))
810 count++;
811 }
812
813 return count;
814 }
815
_bit_overlap_internal(bitstr_t * b1,bitstr_t * b2,bool count_it)816 static int32_t _bit_overlap_internal(bitstr_t *b1, bitstr_t *b2, bool count_it)
817 {
818 int32_t count = 0;
819 int64_t anded;
820 bitoff_t bit, bit_cnt;
821 int32_t word_size = sizeof(bitstr_t) * 8;
822
823 _assert_bitstr_valid(b1);
824 _assert_bitstr_valid(b2);
825 xassert(_bitstr_bits(b1) == _bitstr_bits(b2));
826
827 bit_cnt = _bitstr_bits(b1);
828 for (bit = 0; bit < bit_cnt; bit += word_size) {
829 if ((bit + word_size - 1) >= bit_cnt)
830 break;
831 anded = b1[_bit_word(bit)] & b2[_bit_word(bit)];
832 if (count_it)
833 count += hweight(anded);
834 else if (anded)
835 return 1;
836 }
837 for ( ; bit < bit_cnt; bit++) {
838 if (bit_test(b1, bit) && bit_test(b2, bit)) {
839 if (count_it)
840 count++;
841 else
842 return 1;
843 }
844 }
845
846 return count;
847 }
848
849 /*
850 * return number of bits set in b1 that are also set in b2, 0 if no overlap
851 */
bit_overlap(bitstr_t * b1,bitstr_t * b2)852 extern int32_t bit_overlap(bitstr_t *b1, bitstr_t *b2)
853 {
854 return _bit_overlap_internal(b1, b2, 1);
855 }
856
857 /*
858 * return 1 if there is at least one bit set in b1 that is also set in b2, 0 if
859 * no overlap
860 */
bit_overlap_any(bitstr_t * b1,bitstr_t * b2)861 extern int32_t bit_overlap_any(bitstr_t *b1, bitstr_t *b2)
862 {
863 return _bit_overlap_internal(b1, b2, 0);
864 }
865
866 /*
867 * Count the number of bits clear in bitstring.
868 * b (IN) bitstring to check
869 * RETURN count of clear bits
870 */
871 int32_t
bit_clear_count(bitstr_t * b)872 bit_clear_count(bitstr_t *b)
873 {
874 _assert_bitstr_valid(b);
875 return (_bitstr_bits(b) - bit_set_count(b));
876 }
877
878 /*
879 * Count the number of bits clear in a range of bitstring.
880 * b (IN) bitstring to check
881 * start (IN) first bit to check
882 * end (IN) last bit to check+1
883 * RETURN count of set bits
884 */
885 int32_t
bit_clear_count_range(bitstr_t * b,int32_t start,int32_t end)886 bit_clear_count_range(bitstr_t *b, int32_t start, int32_t end)
887 {
888 _assert_bitstr_valid(b);
889 int diff = end - start;
890
891 if (diff < 1)
892 return 0;
893
894 return (diff - bit_set_count_range(b, start, end));
895 }
896
897 /* Return the count of the largest number of contiguous bits set in b.
898 * b (IN) bitstring to search
899 * RETURN the largest number of contiguous bits set in b
900 */
901 int32_t
bit_nset_max_count(bitstr_t * b)902 bit_nset_max_count(bitstr_t *b)
903 {
904 bitoff_t bit;
905 int32_t cnt = 0;
906 int32_t maxcnt = 0;
907 uint32_t bitsize;
908
909 _assert_bitstr_valid(b);
910 bitsize = _bitstr_bits(b);
911
912 for (bit = 0; bit < bitsize; bit++) {
913 if (!bit_test(b, bit)) { /* no longer continuous */
914 cnt = 0;
915 } else {
916 cnt++;
917 if (cnt > maxcnt) {
918 maxcnt = cnt;
919 }
920 }
921 if (cnt == 0 && ((bitsize - bit) < maxcnt)) {
922 break; /* already found max */
923 }
924 }
925
926 return maxcnt;
927 }
928
929 /*
930 * rotate b1 by n bits returning a rotated copy
931 * b1 (IN) bitmap to rotate
932 * n (IN) rotation distance (+ = rotate left, - = rotate right)
933 * nbits (IN) size of the new copy (in which the rotation occurs)
934 * note: nbits must be >= bit_size(b1)
935 * RETURN new rotated bitmap
936 */
937 bitstr_t *
bit_rotate_copy(bitstr_t * b1,int32_t n,bitoff_t nbits)938 bit_rotate_copy(bitstr_t *b1, int32_t n, bitoff_t nbits)
939 {
940 bitoff_t bit, dst;
941 bitstr_t *new;
942 bitoff_t bitsize;
943 bitoff_t deltasize, wrapbits;
944
945 _assert_bitstr_valid(b1);
946 bitsize = bit_size(b1);
947 xassert(nbits >= bitsize);
948 deltasize = nbits - bitsize;
949
950 /* normalize n to a single positive rotation */
951 n = n % nbits;
952 if (n < 0) {
953 n += nbits;
954 }
955
956 wrapbits = 0; /* number of bits that will wrap around */
957 if (n > deltasize) {
958 wrapbits = n - deltasize;
959 }
960
961 new = bit_alloc(nbits);
962 bit_nclear(new,0,nbits-1);
963
964 /* bits shifting up */
965 for (bit = 0; bit < (bitsize-wrapbits); bit++) {
966 if (bit_test(b1, bit))
967 bit_set(new, bit+n);
968 }
969 /* continue bit into wrap-around bits, if any */
970 for (dst = 0; bit < bitsize; bit++, dst++) {
971 if (bit_test(b1, bit))
972 bit_set(new, dst);
973 }
974 return(new);
975 }
976
977 /*
978 * rotate b1 by n bits
979 * b1 (IN/OUT) bitmap to rotate
980 * n (IN) rotation distance (+ = rotate left, - = rotate right)
981 */
982 void
bit_rotate(bitstr_t * b1,int32_t n)983 bit_rotate(bitstr_t *b1, int32_t n)
984 {
985 uint32_t bitsize;
986 bitstr_t *new;
987
988 if (n == 0)
989 return;
990
991 _assert_bitstr_valid(b1);
992 bitsize = bit_size(b1);
993
994 new = bit_rotate_copy(b1, n, bitsize);
995 bit_copybits(b1, new);
996 bit_free(new);
997 }
998
999 /*
1000 * build a bitmap containing the first nbits of b which are set
1001 */
1002 bitstr_t *
bit_pick_cnt(bitstr_t * b,bitoff_t nbits)1003 bit_pick_cnt(bitstr_t *b, bitoff_t nbits)
1004 {
1005 bitoff_t bit = 0, new_bits, count = 0;
1006 bitstr_t *new;
1007 int32_t word_size = sizeof(bitstr_t) * 8;
1008
1009 _assert_bitstr_valid(b);
1010
1011 if (_bitstr_bits(b) < nbits)
1012 return NULL;
1013
1014 new = bit_alloc(bit_size(b));
1015 if (new == NULL)
1016 return NULL;
1017
1018 while ((bit < _bitstr_bits(b)) && (count < nbits)) {
1019 int32_t word = _bit_word(bit);
1020
1021 if (b[word] == 0) {
1022 bit += word_size;
1023 continue;
1024 }
1025
1026 new_bits = hweight(b[word]);
1027 if (((count + new_bits) <= nbits) &&
1028 ((bit + word_size - 1) < _bitstr_bits(b))) {
1029 new[word] = b[word];
1030 count += new_bits;
1031 bit += word_size;
1032 continue;
1033 }
1034 while ((bit < _bitstr_bits(b)) && (count < nbits)) {
1035 if (bit_test(b, bit)) {
1036 bit_set(new, bit);
1037 count++;
1038 }
1039 bit++;
1040 }
1041 }
1042 if (count < nbits) {
1043 bit_free (new);
1044 new = NULL;
1045 }
1046
1047 return new;
1048 }
1049
1050 /*
1051 * Convert to range string format, e.g. 0-5,42
1052 */
bit_fmt(char * str,int32_t len,bitstr_t * b)1053 char *bit_fmt(char *str, int32_t len, bitstr_t *b)
1054 {
1055 int32_t count = 0, word;
1056 bitoff_t bit;
1057
1058 _assert_bitstr_valid(b);
1059 xassert(len > 0);
1060 *str = '\0';
1061 for (bit = 0; bit < _bitstr_bits(b); ) {
1062 word = _bit_word(bit);
1063 if (b[word] == 0) {
1064 bit += sizeof(bitstr_t)*8;
1065 continue;
1066 }
1067
1068 if (bit_test(b, bit)) {
1069 int32_t ret, size;
1070 bitoff_t start = bit;
1071
1072 count++;
1073 while (bit+1 < _bitstr_bits(b) && bit_test(b, bit+1)) {
1074 bit++;
1075 count++;
1076 }
1077 size = strlen(str);
1078 if (bit == start) { /* add single bit position */
1079 ret = snprintf(str + size, len - size,
1080 "%"BITSTR_FMT",", start);
1081 } else { /* add bit position range */
1082 ret = snprintf(str + size, len - size,
1083 "%"BITSTR_FMT"-%"BITSTR_FMT",",
1084 start, bit);
1085 }
1086
1087 xassert(ret != -1);
1088 if (ret == -1)
1089 error("failed to write to string -- this should never happen");
1090 }
1091 bit++;
1092 }
1093 if (count > 0)
1094 str[strlen(str) - 1] = '\0'; /* zap trailing comma */
1095 return str;
1096 }
1097
1098 /*
1099 * Convert to range string format, e.g. 0-5,42 with no length restriction
1100 * Call xfree() on return value to avoid memory leak
1101 */
bit_fmt_full(bitstr_t * b)1102 char *bit_fmt_full(bitstr_t *b)
1103 {
1104 int32_t count = 0, word;
1105 bitoff_t start, bit;
1106 char *str = NULL, *comma = "";
1107 _assert_bitstr_valid(b);
1108
1109 for (bit = 0; bit < _bitstr_bits(b); ) {
1110 word = _bit_word(bit);
1111 if (b[word] == 0) {
1112 bit += sizeof(bitstr_t)*8;
1113 continue;
1114 }
1115
1116 if (bit_test(b, bit)) {
1117 count++;
1118 start = bit;
1119 while (bit+1 < _bitstr_bits(b) && bit_test(b, bit+1)) {
1120 bit++;
1121 count++;
1122 }
1123 if (bit == start) /* add single bit position */
1124 xstrfmtcat(str, "%s%"BITSTR_FMT"",
1125 comma, start);
1126 else /* add bit position range */
1127 xstrfmtcat(str, "%s%"BITSTR_FMT"-%"BITSTR_FMT,
1128 comma, start, bit);
1129 comma = ",";
1130 }
1131 bit++;
1132 }
1133
1134 return str;
1135 }
1136
1137 /*
1138 * Convert to range string format, e.g. 0-5,42 with no length restriction
1139 * offset IN - location of bit zero
1140 * len IN - number of bits to test
1141 * Call xfree() on return value to avoid memory leak
1142 */
bit_fmt_range(bitstr_t * b,int offset,int len)1143 char *bit_fmt_range(bitstr_t *b, int offset, int len)
1144 {
1145 int32_t count = 0, word;
1146 bitoff_t start, fini_bit, bit;
1147 char *str = NULL, *comma = "";
1148 _assert_bitstr_valid(b);
1149
1150 fini_bit = MIN(_bitstr_bits(b), offset + len);
1151 for (bit = offset; bit < fini_bit; ) {
1152 word = _bit_word(bit);
1153 if (b[word] == 0) {
1154 bit += sizeof(bitstr_t) * 8;
1155 continue;
1156 }
1157
1158 if (bit_test(b, bit)) {
1159 count++;
1160 start = bit;
1161 while ((bit + 1 < fini_bit) && bit_test(b, bit + 1)) {
1162 bit++;
1163 count++;
1164 }
1165 if (bit == start) { /* add single bit position */
1166 xstrfmtcat(str, "%s%"BITSTR_FMT"",
1167 comma, (start - offset));
1168 } else { /* add bit position range */
1169 xstrfmtcat(str, "%s%"BITSTR_FMT"-%"BITSTR_FMT,
1170 comma, (start - offset),
1171 (bit - offset));
1172 }
1173 comma = ",";
1174 }
1175 bit++;
1176 }
1177
1178 return str;
1179 }
1180
1181 /*
1182 * Convert range string format, e.g. "0-5,42" to bitmap
1183 * Ret 0 on success, -1 on error
1184 */
1185 int
bit_unfmt(bitstr_t * b,char * str)1186 bit_unfmt(bitstr_t *b, char *str)
1187 {
1188 int32_t *intvec;
1189 int rc = 0;
1190
1191 _assert_bitstr_valid(b);
1192 if (!str || str[0] == '\0') /* no bits set */
1193 return rc;
1194 intvec = bitfmt2int(str);
1195 if (intvec == NULL)
1196 return -1;
1197 rc = inx2bitstr(b, intvec);
1198 xfree(intvec);
1199 return rc;
1200 }
1201
1202 /*
1203 * bitfmt2int - convert a string describing bitmap (output from bit_fmt,
1204 * e.g. "0-30,45,50-60") into an array of integer (start/end) pairs
1205 * terminated by -1 (e.g. "0, 30, 45, 45, 50, 60, -1")
1206 * Also supports the "1-17:4" step format ("1, 5, 9, 13, 17, -1").
1207 * input: bitmap string as produced by bitstring.c : bitfmt
1208 * output: an array of integers
1209 * NOTE: the caller must xfree the returned memory
1210 */
bitfmt2int(char * bit_str_ptr)1211 int32_t *bitfmt2int(char *bit_str_ptr)
1212 {
1213 int32_t *bit_int_ptr, i, bit_inx, size, sum, start_val;
1214 char *tmp = NULL;
1215 int32_t start_task_id = -1;
1216 int32_t end_task_id = -1;
1217 int32_t step = -1;
1218
1219 if (bit_str_ptr == NULL)
1220 return NULL;
1221 if (!(xstrchr(bit_str_ptr, ':'))) {
1222 size = strlen(bit_str_ptr) + 1;
1223 /* more than enough space */
1224 bit_int_ptr = xmalloc(sizeof(int32_t) * (size * 2 + 1));
1225 bit_inx = sum = 0;
1226 start_val = -1;
1227 for (i = 0; i < size; i++) {
1228 if (bit_str_ptr[i] >= '0' &&
1229 bit_str_ptr[i] <= '9') {
1230 sum = (sum * 10) + (bit_str_ptr[i] - '0');
1231 } else if (bit_str_ptr[i] == '-') {
1232 start_val = sum;
1233 sum = 0;
1234 } else if (bit_str_ptr[i] == ',' ||
1235 bit_str_ptr[i] == '\0') {
1236 if (i == 0)
1237 break;
1238 if (start_val == -1)
1239 start_val = sum;
1240 bit_int_ptr[bit_inx++] = start_val;
1241 bit_int_ptr[bit_inx++] = sum;
1242 start_val = -1;
1243 sum = 0;
1244 }
1245 }
1246 xassert(bit_inx < (size * 2 + 1));
1247 } else { /* handle step format */
1248 start_task_id = strtol(bit_str_ptr, &tmp, 10);
1249 if (*tmp != '-')
1250 return NULL;
1251 end_task_id = strtol(tmp + 1, &tmp, 10);
1252 if (*tmp != ':')
1253 return NULL;
1254 step = strtol(tmp + 1, &tmp, 10);
1255 if (*tmp != '\0')
1256 return NULL;
1257 if (end_task_id < start_task_id || step <= 0)
1258 return NULL;
1259
1260 size = ((end_task_id - start_task_id) / step) + 1;
1261 bit_int_ptr = xmalloc(sizeof(int32_t) * (size * 2 + 1));
1262 bit_inx = 0;
1263 for(i = start_task_id; i < end_task_id; i += step) {
1264 bit_int_ptr[bit_inx++] = i; /* start of pair */
1265 bit_int_ptr[bit_inx++] = i; /* end of pair */
1266 }
1267 }
1268 bit_int_ptr[bit_inx] = -1;
1269 return bit_int_ptr;
1270 }
1271
1272 /*
1273 * intbitfmt - convert a array of integer (start/end) pairs
1274 * terminated by -1 (e.g. "0, 30, 45, 45, 50, 60, -1") to a
1275 * string describing bitmap (output from bit_fmt, e.g. "0-30,45,50-60")
1276 * input: int array
1277 * output: char *
1278 * NOTE: the caller must xfree the returned memory
1279 */
1280 char *
inx2bitfmt(int32_t * inx)1281 inx2bitfmt (int32_t *inx)
1282 {
1283 int32_t j = 0;
1284 char *bit_char_ptr = NULL;
1285
1286 if (inx == NULL)
1287 return NULL;
1288
1289 while (inx[j] >= 0) {
1290 if (bit_char_ptr)
1291 xstrfmtcat(bit_char_ptr, ",%d-%d", inx[j], inx[j+1]);
1292 else
1293 xstrfmtcat(bit_char_ptr, "%d-%d", inx[j], inx[j+1]);
1294 j += 2;
1295 }
1296
1297 return bit_char_ptr;
1298 }
1299
inx2bitstr(bitstr_t * b,int32_t * inx)1300 int inx2bitstr(bitstr_t *b, int32_t *inx)
1301 {
1302 int32_t *p, bit_cnt;
1303 int rc = 0;
1304
1305 xassert(b);
1306 xassert(inx);
1307
1308 bit_cnt = _bitstr_bits(b);
1309 if (bit_cnt > 0)
1310 bit_nclear(b, 0, bit_cnt - 1);
1311 for (p = inx; *p != -1; p += 2) {
1312 if ((*p < 0) || (*p >= bit_cnt) ||
1313 (*(p + 1) < 0) || (*(p + 1) >= bit_cnt)) {
1314 rc = -1;
1315 break;
1316 }
1317 bit_nset(b, *p, *(p + 1));
1318 }
1319 return rc;
1320 }
1321
1322 /*
1323 * convert a bitstring to inx format
1324 * returns an xmalloc()'d array of int32_t that must be xfree()'d
1325 */
bitstr2inx(bitstr_t * b)1326 int32_t *bitstr2inx(bitstr_t *b)
1327 {
1328 bitoff_t start, bit, pos = 0;
1329 int32_t *bit_inx;
1330
1331 if (!b) {
1332 bit_inx = xmalloc(sizeof(int32_t));
1333 bit_inx[0] = -1;
1334 return bit_inx;
1335 }
1336
1337 /* worst case: every other bit set, resulting in an array of length
1338 * bitstr_bits(b) + 1 (if an odd number of elements)
1339 * + 1 (for trailing -1) */
1340 bit_inx = xmalloc_nz(sizeof(int32_t) * (_bitstr_bits(b) + 2));
1341
1342 for (bit = 0; bit < _bitstr_bits(b); ) {
1343 /* skip past empty words */
1344 if (!b[_bit_word(bit)]) {
1345 bit += sizeof(bitstr_t) * 8;
1346 continue;
1347 }
1348
1349 if (bit_test(b, bit)) {
1350 start = bit;
1351 while (bit + 1 < _bitstr_bits(b)
1352 && bit_test(b, bit + 1))
1353 bit++;
1354 bit_inx[pos++] = start;
1355 bit_inx[pos++] = bit;
1356 }
1357 bit++;
1358 }
1359 /* terminate array with -1 */
1360 bit_inx[pos] = -1;
1361
1362 return bit_inx;
1363 }
1364
1365 /* bit_fmt_hexmask
1366 *
1367 * Given a bitstr_t, allocate and return a string in the form of:
1368 * "0x0123ABC\0"
1369 * ^ ^
1370 * | |
1371 * MSB LSB
1372 * bitmap (IN) bitmap to format
1373 * RETURN formatted string
1374 */
bit_fmt_hexmask(bitstr_t * bitmap)1375 char * bit_fmt_hexmask(bitstr_t * bitmap)
1376 {
1377 char *retstr, *ptr;
1378 char current;
1379 bitoff_t i;
1380 bitoff_t bitsize = bit_size(bitmap);
1381
1382 /* 4 bits per ASCII '0'-'F' */
1383 bitoff_t charsize = (bitsize + 3) / 4;
1384
1385 retstr = xmalloc(charsize + 3);
1386
1387 retstr[0] = '0';
1388 retstr[1] = 'x';
1389 retstr[charsize + 2] = '\0';
1390 ptr = &retstr[charsize + 1];
1391 for (i=0; i < bitsize;) {
1392 current = 0;
1393 if ( bit_test(bitmap,i++)) current |= 0x1;
1394 if ((i < bitsize) && bit_test(bitmap,i++)) current |= 0x2;
1395 if ((i < bitsize) && bit_test(bitmap,i++)) current |= 0x4;
1396 if ((i < bitsize) && bit_test(bitmap,i++)) current |= 0x8;
1397 if (current <= 9) {
1398 current += '0';
1399 } else {
1400 current += 'A' - 10;
1401 }
1402 *ptr-- = current;
1403 }
1404
1405 return retstr;
1406 }
1407
1408 /* bit_unfmt_hexmask
1409 *
1410 * Given a hex mask string "0x0123ABC\0", convert to a bitstr_t *
1411 * ^ ^
1412 * | |
1413 * MSB LSB
1414 * bitmap (OUT) bitmap to update
1415 * str (IN) hex mask string to unformat
1416 * RET: 0 on success, -1 on error
1417 */
bit_unfmt_hexmask(bitstr_t * bitmap,const char * str)1418 int bit_unfmt_hexmask(bitstr_t * bitmap, const char* str)
1419 {
1420 int32_t bit_index = 0, len;
1421 int rc = 0;
1422 const char *curpos;
1423 int32_t current;
1424 bitoff_t bitsize;
1425
1426 if (!bitmap || !str)
1427 return -1;
1428
1429 len = strlen(str);
1430 bitsize = bit_size(bitmap);
1431 curpos = str + len - 1;
1432
1433 bit_nclear(bitmap, 0, bitsize - 1);
1434 if (xstrncmp(str, "0x", 2) == 0) { /* Bypass 0x */
1435 str += 2;
1436 len -= 2;
1437 }
1438
1439 while (curpos >= str) {
1440 current = (int32_t) *curpos;
1441 if (isxdigit(current)) { /* valid hex digit */
1442 if (isdigit(current)) {
1443 current -= '0';
1444 } else {
1445 current = toupper(current);
1446 current -= 'A' - 10;
1447 }
1448 } else { /* not a valid hex digit */
1449 current = 0;
1450 rc = -1;
1451 break;
1452 }
1453
1454 if (current & 1) {
1455 if (bit_index < bitsize)
1456 bit_set(bitmap, bit_index);
1457 else {
1458 rc = -1;
1459 break;
1460 }
1461 }
1462 if (current & 2) {
1463 if ((bit_index + 1) < bitsize)
1464 bit_set(bitmap, bit_index + 1);
1465 else {
1466 rc = -1;
1467 break;
1468 }
1469 }
1470 if (current & 4) {
1471 if ((bit_index + 2) < bitsize)
1472 bit_set(bitmap, bit_index + 2);
1473 else {
1474 rc = -1;
1475 break;
1476 }
1477 }
1478 if (current & 8) {
1479 if ((bit_index + 3) < bitsize)
1480 bit_set(bitmap, bit_index + 3);
1481 else {
1482 rc = -1;
1483 break;
1484 }
1485 }
1486 len--;
1487 curpos--;
1488 bit_index+=4;
1489 }
1490 return rc;
1491 }
1492
1493 /* bit_fmt_binmask
1494 *
1495 * Given a bitstr_t, allocate and return a binary string in the form of:
1496 * "0001010\0"
1497 * ^ ^
1498 * | |
1499 * MSB LSB
1500 * bitmap (IN) bitmap to format
1501 * RETURN formatted string
1502 */
bit_fmt_binmask(bitstr_t * bitmap)1503 char * bit_fmt_binmask(bitstr_t * bitmap)
1504 {
1505 char *retstr, *ptr;
1506 char current;
1507 bitoff_t i;
1508 bitoff_t bitsize = bit_size(bitmap);
1509
1510 /* 1 bits per ASCII '0'-'1' */
1511 bitoff_t charsize = bitsize;
1512
1513 retstr = xmalloc(charsize + 1);
1514
1515 retstr[charsize] = '\0';
1516 ptr = &retstr[charsize - 1];
1517 for (i=0; i < bitsize;) {
1518 current = 0;
1519 if (bit_test(bitmap,i++)) current |= 0x1;
1520 current += '0';
1521 *ptr-- = current;
1522 }
1523
1524 return retstr;
1525 }
1526
1527 /* bit_unfmt_binmask
1528 *
1529 * Given a binary mask string "0001010\0", convert to a bitstr_t *
1530 * ^ ^
1531 * | |
1532 * MSB LSB
1533 * bitmap (OUT) bitmap to update
1534 * str (IN) hex mask string to unformat
1535 */
bit_unfmt_binmask(bitstr_t * bitmap,const char * str)1536 void bit_unfmt_binmask(bitstr_t * bitmap, const char* str)
1537 {
1538 int32_t bit_index = 0, len = strlen(str);
1539 const char *curpos = str + len - 1;
1540 char current;
1541 bitoff_t bitsize = bit_size(bitmap);
1542
1543 bit_nclear(bitmap, 0, bitsize - 1);
1544 while (curpos >= str) {
1545 current = (int32_t) *curpos;
1546 current -= '0';
1547 if ((current & 1) && (bit_index < bitsize))
1548 bit_set(bitmap, bit_index);
1549 len--;
1550 curpos--;
1551 bit_index++;
1552 }
1553 }
1554
1555 /* Find the bit set at pos (0 - bitstr_bits) in bitstr b.
1556 * b (IN) bitstring to search
1557 * pos (IN) bit to search for
1558 * RETURN number bit is set in bitstring (-1 on error)
1559 */
1560
1561 bitoff_t
bit_get_bit_num(bitstr_t * b,int32_t pos)1562 bit_get_bit_num(bitstr_t *b, int32_t pos)
1563 {
1564 bitoff_t bit;
1565 int32_t cnt = 0;
1566 bitoff_t bit_cnt;
1567
1568 _assert_bitstr_valid(b);
1569 bit_cnt = _bitstr_bits(b);
1570 xassert(pos <= bit_cnt);
1571
1572 for (bit = 0; bit < bit_cnt; bit++) {
1573 if (bit_test(b, bit)) { /* we got one */
1574 if (cnt == pos)
1575 break;
1576 cnt++;
1577 }
1578 }
1579
1580 if (bit >= bit_cnt)
1581 bit = -1;
1582
1583 return bit;
1584 }
1585
1586 /* Find want nth the bit pos is set in bitstr b.
1587 * b (IN) bitstring to search
1588 * pos (IN) bit to search to
1589 * RETURN number bit is set in bitstring (-1 on error)
1590 */
1591
1592 int32_t
bit_get_pos_num(bitstr_t * b,bitoff_t pos)1593 bit_get_pos_num(bitstr_t *b, bitoff_t pos)
1594 {
1595 bitoff_t bit;
1596 int32_t cnt = -1;
1597 #ifndef NDEBUG
1598 bitoff_t bit_cnt;
1599 #endif
1600
1601 _assert_bitstr_valid(b);
1602 #ifndef NDEBUG
1603 bit_cnt = _bitstr_bits(b);
1604 xassert(pos <= bit_cnt);
1605 #endif
1606
1607 if (!bit_test(b, pos)) {
1608 error("bit %"BITSTR_FMT" not set", pos);
1609 return cnt;
1610 }
1611 for (bit = 0; bit <= pos; bit++) {
1612 if (bit_test(b, bit)) { /* we got one */
1613 cnt++;
1614 }
1615 }
1616
1617 return cnt;
1618 }
1619