2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
18 Permission is hereby granted, free of charge, to any person obtaining
19 a copy of this software and associated documentation files (the
20 "Software"), to deal in the Software without restriction, including
21 without limitation the rights to use, copy, modify, merge, publish,
22 distribute, sublicense, and/or sell copies of the Software, and to
23 permit persons to whom the Software is furnished to do so, subject to
24 the following conditions:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38 #ifndef included_clib_bitmap_h
39 #define included_clib_bitmap_h
42 Bitmaps built as vectors of machine words
45 #include <vppinfra/vec.h>
46 #include <vppinfra/random.h>
47 #include <vppinfra/error.h>
48 #include <vppinfra/bitops.h> /* for count_set_bits */
50 typedef uword clib_bitmap_t;
52 /** predicate function; is an entire bitmap empty?
53 @param ai - pointer to a bitmap
54 @returns 1 if the entire bitmap is zero, 0 otherwise
57 clib_bitmap_is_zero (uword * ai)
60 for (i = 0; i < vec_len (ai); i++)
66 /** predicate function; are two bitmaps equal?
67 @param a - pointer to a bitmap
68 @param b - pointer to a bitmap
69 @returns 1 if the bitmaps are equal, 0 otherwise
72 clib_bitmap_is_equal (uword * a, uword * b)
75 if (vec_len (a) != vec_len (b))
77 for (i = 0; i < vec_len (a); i++)
83 /** Duplicate a bitmap
84 @param ai - pointer to a bitmap
85 @returns a duplicate of the bitmap
87 #define clib_bitmap_dup(v) vec_dup(v)
90 @param v - pointer to the bitmap to free
92 #define clib_bitmap_free(v) vec_free(v)
94 /** Number of bytes in a bitmap
95 @param v - pointer to the bitmap
97 #define clib_bitmap_bytes(v) vec_bytes(v)
100 @param v - pointer to the bitmap to clear
102 #define clib_bitmap_zero(v) vec_zero(v)
104 /** Allocate a bitmap with the supplied number of bits
105 @param [out] v - the resulting bitmap
106 @param n_bits - the required number of bits
109 #define clib_bitmap_alloc(v,n_bits) \
110 v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
112 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
114 /* Make sure that a bitmap is at least n_bits in size */
115 #define clib_bitmap_validate(v,n_bits) \
116 clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
118 /* low-level routine to remove trailing zeros from a bitmap */
119 always_inline uword *
120 _clib_bitmap_remove_trailing_zeros (uword * a)
125 for (i = _vec_len (a) - 1; i >= 0; i--)
128 _vec_len (a) = i + 1;
133 /** Sets the ith bit of a bitmap to new_value.
134 No sanity checking. Be careful.
135 @param a - pointer to the bitmap
136 @param i - the bit position to interrogate
137 @param new_value - new value for the bit
138 @returns the old value of the bit
141 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
143 uword i0 = i / BITS (a[0]);
144 uword i1 = i % BITS (a[0]);
145 uword bit = (uword) 1 << i1;
148 /* Removed ASSERT since uword * a may not be a vector. */
149 /* ASSERT (i0 < vec_len (a)); */
152 old_value = (ai & bit) != 0;
154 ai |= ((uword) (new_value != 0)) << i1;
159 /** Sets the ith bit of a bitmap to new_value
160 Removes trailing zeros from the bitmap
161 @param a - pointer to the bitmap
162 @param i - the bit position to interrogate
163 @param new_value - new value for the bit
164 @returns the old value of the bit
166 always_inline uword *
167 clib_bitmap_set (uword * ai, uword i, uword value)
169 uword i0 = i / BITS (ai[0]);
170 uword i1 = i % BITS (ai[0]);
173 /* Check for writing a zero to beyond end of bitmap. */
174 if (value == 0 && i0 >= vec_len (ai))
175 return ai; /* Implied trailing zeros. */
177 clib_bitmap_vec_validate (ai, i0);
180 a &= ~((uword) 1 << i1);
181 a |= ((uword) (value != 0)) << i1;
184 /* If bits have been cleared, test for zero. */
186 ai = _clib_bitmap_remove_trailing_zeros (ai);
191 /** Gets the ith bit value from a bitmap
192 @param ai - pointer to the bitmap
193 @param i - the bit position to interrogate
194 @returns the indicated bit value
197 clib_bitmap_get (uword * ai, uword i)
199 uword i0 = i / BITS (ai[0]);
200 uword i1 = i % BITS (ai[0]);
201 return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
204 /** Gets the ith bit value from a bitmap
205 Does not sanity-check the bit position. Be careful.
206 @param ai - pointer to the bitmap
207 @param i - the bit position to interrogate
208 @returns the indicated bit value, or garbage if the bit position is
212 clib_bitmap_get_no_check (uword * ai, uword i)
214 uword i0 = i / BITS (ai[0]);
215 uword i1 = i % BITS (ai[0]);
216 return 0 != ((ai[i0] >> i1) & 1);
220 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
222 uword i0 = i / BITS (ai[0]);
223 uword i1 = i % BITS (ai[0]);
224 ASSERT (i1 + n_bits <= BITS (uword));
225 return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
228 /** Gets the ith through ith + n_bits bit values from a bitmap
229 @param bitmap - pointer to the bitmap
230 @param i - the first bit position to retrieve
231 @param n_bits - the number of bit positions to retrieve
232 @returns the indicated range of bits
235 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
237 uword i0, i1, result;
238 uword l = vec_len (bitmap);
240 ASSERT (n_bits <= BITS (result));
242 i0 = i / BITS (bitmap[0]);
243 i1 = i % BITS (bitmap[0]);
245 /* Check first word. */
249 result |= (bitmap[i0] >> i1);
250 if (n_bits < BITS (bitmap[0]))
251 result &= (((uword) 1 << n_bits) - 1);
254 /* Check for overlap into next word. */
256 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
258 n_bits -= BITS (bitmap[0]) - i1;
259 result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
265 /** sets the ith through ith + n_bits bits in a bitmap
266 @param bitmap - pointer to the bitmap
267 @param i - the first bit position to retrieve
268 @param value - the values to set
269 @param n_bits - the number of bit positions to set
270 @returns a pointer to the updated bitmap, which may expand and move
273 always_inline uword *
274 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
276 uword i0, i1, l, t, m;
278 ASSERT (n_bits <= BITS (value));
280 i0 = i / BITS (bitmap[0]);
281 i1 = i % BITS (bitmap[0]);
283 /* Allocate bitmap. */
284 clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
285 l = vec_len (bitmap);
288 if (n_bits < BITS (value))
289 m = (((uword) 1 << n_bits) - 1);
292 /* Insert into first word. */
298 /* Insert into second word. */
300 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
302 t = BITS (bitmap[0]) - i1;
306 m = ((uword) 1 << n_bits) - 1;
315 always_inline uword *
316 clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
321 a0 = i / BITS (bitmap[0]);
322 a1 = i % BITS (bitmap[0]);
325 b0 = i_end / BITS (bitmap[0]);
327 clib_bitmap_vec_validate (bitmap, b0);
330 mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
338 for (a0++; a0 < b0; a0++)
339 bitmap[a0] = value ? ~0 : 0;
343 word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
344 mask = pow2_mask (n_bits_left);
354 /** Macro to iterate across set bits in a bitmap
356 @param i - the current set bit
357 @param ai - the bitmap
358 @param body - the expression to evaluate for each set bit
360 #define clib_bitmap_foreach(i,ai,body) \
362 uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \
363 __bitmap_len = vec_len ((ai)); \
364 for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \
366 __bitmap_ai = (ai)[__bitmap_i]; \
367 while (__bitmap_ai != 0) \
369 __bitmap_first_set = first_set (__bitmap_ai); \
370 (i) = (__bitmap_i * BITS ((ai)[0]) \
371 + min_log2 (__bitmap_first_set)); \
372 do { body; } while (0); \
373 __bitmap_ai ^= __bitmap_first_set; \
379 /** Return the lowest numbered set bit in a bitmap
380 @param ai - pointer to the bitmap
381 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
383 always_inline uword clib_bitmap_first_set (uword * ai)
386 for (i = 0; i < vec_len (ai); i++)
390 return i * BITS (ai[0]) + log2_first_set (x);
395 /** Return the higest numbered set bit in a bitmap
396 @param ai - pointer to the bitmap
397 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
399 always_inline uword clib_bitmap_last_set (uword * ai)
403 for (i = vec_len (ai); i > 0 ; i--)
409 count_leading_zeros (first_bit, x);
410 return (i) * BITS (ai[0]) - first_bit - 1;
416 /** Return the lowest numbered clear bit in a bitmap
417 @param ai - pointer to the bitmap
418 @returns lowest numbered clear bit
421 clib_bitmap_first_clear (uword * ai)
424 for (i = 0; i < vec_len (ai); i++)
428 return i * BITS (ai[0]) + log2_first_set (x);
430 return i * BITS (ai[0]);
433 /** Return the number of set bits in a bitmap
434 @param ai - pointer to the bitmap
435 @returns the number of set bits in the bitmap
438 clib_bitmap_count_set_bits (uword * ai)
442 for (i = 0; i < vec_len (ai); i++)
443 n_set += count_set_bits (ai[i]);
447 /** Logical operator across two bitmaps
449 @param ai - pointer to the destination bitmap
450 @param bi - pointer to the source bitmap
451 @returns ai = ai and bi. ai is modified, bi is not modified
453 always_inline uword *
454 clib_bitmap_and (uword * ai, uword * bi);
456 /** Logical operator across two bitmaps
458 @param ai - pointer to the destination bitmap
459 @param bi - pointer to the source bitmap
460 @returns ai = ai & ~bi. ai is modified, bi is not modified
462 always_inline uword *
463 clib_bitmap_andnot (uword * ai, uword * bi);
465 /** Logical operator across two bitmaps
467 @param ai - pointer to the destination bitmap
468 @param bi - pointer to the source bitmap
469 @returns ai = ai & ~bi. ai is modified, bi is not modified
471 always_inline uword *
472 clib_bitmap_or (uword * ai, uword * bi);
473 /** Logical operator across two bitmaps
475 @param ai - pointer to the destination bitmap
476 @param bi - pointer to the source bitmap
477 @returns ai = ai or bi. ai is modified, bi is not modified
479 always_inline uword *
480 clib_bitmap_or (uword * ai, uword * bi);
482 /** Logical operator across two bitmaps
484 @param ai - pointer to the destination bitmap
485 @param bi - pointer to the source bitmap
486 @returns ai = ai xor bi. ai is modified, bi is not modified
488 always_inline uword *
489 clib_bitmap_xor (uword * ai, uword * bi);
491 /* ALU function definition macro for functions taking two bitmaps. */
492 #define _(name, body, check_zero) \
493 always_inline uword * \
494 clib_bitmap_##name (uword * ai, uword * bi) \
496 uword i, a, b, bi_len, n_trailing_zeros; \
498 n_trailing_zeros = 0; \
499 bi_len = vec_len (bi); \
501 clib_bitmap_vec_validate (ai, bi_len - 1); \
502 for (i = 0; i < vec_len (ai); i++) \
505 b = i < bi_len ? bi[i] : 0; \
506 do { body; } while (0); \
509 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
512 _vec_len (ai) -= n_trailing_zeros; \
517 _ (and, a = a & b, 1)
518 _ (andnot, a = a &~ b, 1)
520 _ (xor, a = a ^ b, 1)
523 /** Logical operator across two bitmaps which duplicates the first bitmap
525 @param ai - pointer to the destination bitmap
526 @param bi - pointer to the source bitmap
527 @returns aiDup = ai and bi. Neither ai nor bi are modified
529 always_inline uword *
530 clib_bitmap_dup_and (uword * ai, uword * bi);
532 /** Logical operator across two bitmaps which duplicates the first bitmap
534 @param ai - pointer to the destination bitmap
535 @param bi - pointer to the source bitmap
536 @returns aiDup = ai & ~bi. Neither ai nor bi are modified
538 always_inline uword *
539 clib_bitmap_dup_andnot (uword * ai, uword * bi);
541 /** Logical operator across two bitmaps which duplicates the first bitmap
543 @param ai - pointer to the destination bitmap
544 @param bi - pointer to the source bitmap
545 @returns aiDup = ai or bi. Neither ai nor bi are modified
547 always_inline uword *
548 clib_bitmap_dup_or (uword * ai, uword * bi);
550 /** Logical operator across two bitmaps which duplicates the first bitmap
552 @param ai - pointer to the destination bitmap
553 @param bi - pointer to the source bitmap
554 @returns aiDup = ai xor bi. Neither ai nor bi are modified
556 always_inline uword *
557 clib_bitmap_dup_xor (uword * ai, uword * bi);
560 always_inline uword * \
561 clib_bitmap_dup_##name (uword * ai, uword * bi) \
562 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
571 /* ALU function definition macro for functions taking one bitmap and an immediate. */
572 #define _(name, body, check_zero) \
573 always_inline uword * \
574 clib_bitmap_##name (uword * ai, uword i) \
576 uword i0 = i / BITS (ai[0]); \
577 uword i1 = i % BITS (ai[0]); \
579 clib_bitmap_vec_validate (ai, i0); \
581 b = (uword) 1 << i1; \
582 do { body; } while (0); \
584 if (check_zero && a == 0) \
585 ai = _clib_bitmap_remove_trailing_zeros (ai); \
589 /* ALU functions immediate: */
590 _ (andi, a = a & b, 1)
591 _ (andnoti, a = a &~ b, 1)
592 _ (ori, a = a | b, 0)
593 _ (xori, a = a ^ b, 1)
597 /** Return a random bitmap of the requested length
598 @param ai - pointer to the destination bitmap
599 @param n_bits - number of bits to allocate
600 @param [in/out] seed - pointer to the random number seed
601 @returns a reasonably random bitmap based. See random.h.
603 always_inline uword *
604 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
606 vec_reset_length (ai);
610 uword i = n_bits - 1;
614 log2_rand_max = min_log2 (random_u32_max ());
616 i0 = i / BITS (ai[0]);
617 i1 = i % BITS (ai[0]);
619 clib_bitmap_vec_validate (ai, i0);
620 for (i = 0; i <= i0; i++)
623 for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
624 ai[i] |= random_u32 (seed) << n;
626 if (i1 + 1 < BITS (ai[0]))
627 ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
632 /** Return the next set bit in a bitmap starting at bit i
633 @param ai - pointer to the bitmap
634 @param i - first bit position to test
635 @returns first set bit position at or after i,
636 ~0 if no further set bits are found
639 clib_bitmap_next_set (uword * ai, uword i)
641 uword i0 = i / BITS (ai[0]);
642 uword i1 = i % BITS (ai[0]);
645 if (i0 < vec_len (ai))
647 t = (ai[i0] >> i1) << i1;
649 return log2_first_set (t) + i0 * BITS (ai[0]);
651 for (i0++; i0 < vec_len (ai); i0++)
655 return log2_first_set (t) + i0 * BITS (ai[0]);
662 /** Return the next clear bit in a bitmap starting at bit i
663 @param ai - pointer to the bitmap
664 @param i - first bit position to test
665 @returns first clear bit position at or after i
668 clib_bitmap_next_clear (uword * ai, uword i)
670 uword i0 = i / BITS (ai[0]);
671 uword i1 = i % BITS (ai[0]);
674 if (i0 < vec_len (ai))
676 t = (~ai[i0] >> i1) << i1;
678 return log2_first_set (t) + i0 * BITS (ai[0]);
680 for (i0++; i0 < vec_len (ai); i0++)
684 return log2_first_set (t) + i0 * BITS (ai[0]);
690 /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
693 rv = unformat ("%U", unformat_bitmap_list, &bitmap);
695 Standard unformat_function_t arguments
697 @param input - pointer an unformat_input_t
698 @param va - varargs list comprising a single uword **
699 @returns 1 on success, 0 on failure
702 unformat_bitmap_list(unformat_input_t * input, va_list * va)
704 uword ** bitmap_return = va_arg (* va, uword **);
709 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
712 if (unformat (input, "%u-%u,", &a, &b))
714 else if (unformat (input, "%u,", &a))
716 else if (unformat (input, "%u-%u", &a, &b))
718 else if (unformat (input, "%u", &a))
722 unformat_put_input(input);
731 for (i = a; i <= b; i++)
732 bitmap = clib_bitmap_set(bitmap, i, 1);
734 *bitmap_return = bitmap;
737 clib_bitmap_free(bitmap);
741 /** Format a bitmap as a string of hex bytes
744 s = format ("%U", format_bitmap_hex, bitmap);
746 Standard format_function_t arguments
748 @param s - string under construction
749 @param args - varargs list comprising a single uword *
750 @returns string under construction
753 format_bitmap_hex(u8 * s, va_list * args)
755 uword * bitmap = va_arg (*args, uword *);
756 int i, is_trailing_zero = 1;
759 return format(s, "0");
761 i = vec_bytes (bitmap) * 2;
765 u8 x = clib_bitmap_get_multiple(bitmap, --i * 4, 4);
767 if (x && is_trailing_zero)
768 is_trailing_zero = 0;
770 if (x || !is_trailing_zero)
771 s = format(s, "%x", x);
775 #endif /* included_clib_bitmap_h */