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 v - 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))
120 @param src - copy from
122 static_always_inline void
123 clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src)
127 clib_bitmap_vec_validate (*dst, vec_len (src) - 1);
128 vec_copy (*dst, src);
132 vec_reset_length (*dst);
136 /* low-level routine to remove trailing zeros from a bitmap */
137 always_inline uword *
138 _clib_bitmap_remove_trailing_zeros (uword * a)
143 for (i = _vec_len (a) - 1; i >= 0; i--)
146 _vec_len (a) = i + 1;
151 /** Sets the ith bit of a bitmap to new_value.
152 No sanity checking. Be careful.
153 @param a - pointer to the bitmap
154 @param i - the bit position to interrogate
155 @param new_value - new value for the bit
156 @returns the old value of the bit
159 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
161 uword i0 = i / BITS (a[0]);
162 uword i1 = i % BITS (a[0]);
163 uword bit = (uword) 1 << i1;
166 /* Removed ASSERT since uword * a may not be a vector. */
167 /* ASSERT (i0 < vec_len (a)); */
170 old_value = (ai & bit) != 0;
172 ai |= ((uword) (new_value != 0)) << i1;
177 /** Sets the ith bit of a bitmap to new_value
178 Removes trailing zeros from the bitmap
179 @param ai - pointer to the bitmap
180 @param i - the bit position to interrogate
181 @param value - new value for the bit
182 @returns the old value of the bit
184 always_inline uword *
185 clib_bitmap_set (uword * ai, uword i, uword value)
187 uword i0 = i / BITS (ai[0]);
188 uword i1 = i % BITS (ai[0]);
191 /* Check for writing a zero to beyond end of bitmap. */
192 if (value == 0 && i0 >= vec_len (ai))
193 return ai; /* Implied trailing zeros. */
195 clib_bitmap_vec_validate (ai, i0);
198 a &= ~((uword) 1 << i1);
199 a |= ((uword) (value != 0)) << i1;
202 /* If bits have been cleared, test for zero. */
204 ai = _clib_bitmap_remove_trailing_zeros (ai);
209 /** Gets the ith bit value from a bitmap
210 @param ai - pointer to the bitmap
211 @param i - the bit position to interrogate
212 @returns the indicated bit value
215 clib_bitmap_get (uword * ai, uword i)
217 uword i0 = i / BITS (ai[0]);
218 uword i1 = i % BITS (ai[0]);
219 return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
222 /** Gets the ith bit value from a bitmap
223 Does not sanity-check the bit position. Be careful.
224 @param ai - pointer to the bitmap
225 @param i - the bit position to interrogate
226 @returns the indicated bit value, or garbage if the bit position is
230 clib_bitmap_get_no_check (uword * ai, uword i)
232 uword i0 = i / BITS (ai[0]);
233 uword i1 = i % BITS (ai[0]);
234 return 0 != ((ai[i0] >> i1) & 1);
238 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
240 uword i0 = i / BITS (ai[0]);
241 uword i1 = i % BITS (ai[0]);
242 ASSERT (i1 + n_bits <= BITS (uword));
243 return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
246 /** Gets the ith through ith + n_bits bit values from a bitmap
247 @param bitmap - pointer to the bitmap
248 @param i - the first bit position to retrieve
249 @param n_bits - the number of bit positions to retrieve
250 @returns the indicated range of bits
253 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
255 uword i0, i1, result;
256 uword l = vec_len (bitmap);
258 ASSERT (n_bits <= BITS (result));
260 i0 = i / BITS (bitmap[0]);
261 i1 = i % BITS (bitmap[0]);
263 /* Check first word. */
267 result |= (bitmap[i0] >> i1);
268 if (n_bits < BITS (bitmap[0]))
269 result &= (((uword) 1 << n_bits) - 1);
272 /* Check for overlap into next word. */
274 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
276 n_bits -= BITS (bitmap[0]) - i1;
278 (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
284 /** sets the ith through ith + n_bits bits in a bitmap
285 @param bitmap - pointer to the bitmap
286 @param i - the first bit position to retrieve
287 @param value - the values to set
288 @param n_bits - the number of bit positions to set
289 @returns a pointer to the updated bitmap, which may expand and move
292 always_inline uword *
293 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
295 uword i0, i1, l, t, m;
297 ASSERT (n_bits <= BITS (value));
299 i0 = i / BITS (bitmap[0]);
300 i1 = i % BITS (bitmap[0]);
302 /* Allocate bitmap. */
303 clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
304 l = vec_len (bitmap);
307 if (n_bits < BITS (value))
308 m = (((uword) 1 << n_bits) - 1);
311 /* Insert into first word. */
317 /* Insert into second word. */
319 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
321 t = BITS (bitmap[0]) - i1;
325 m = ((uword) 1 << n_bits) - 1;
334 always_inline uword *
335 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
340 a0 = i / BITS (bitmap[0]);
341 a1 = i % BITS (bitmap[0]);
344 b0 = i_end / BITS (bitmap[0]);
346 clib_bitmap_vec_validate (bitmap, b0);
349 mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
357 for (a0++; a0 < b0; a0++)
358 bitmap[a0] = value ? ~0 : 0;
362 word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
363 mask = pow2_mask (n_bits_left);
373 /** Macro to iterate across set bits in a bitmap
375 @param i - the current set bit
376 @param ai - the bitmap
377 @param body - the expression to evaluate for each set bit
379 #define clib_bitmap_foreach(i,ai) \
381 for (i = clib_bitmap_first_set (ai); \
383 i = clib_bitmap_next_set (ai, i + 1))
385 /** Return the lowest numbered set bit in a bitmap
386 @param ai - pointer to the bitmap
387 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
390 clib_bitmap_first_set (uword * ai)
394 #if defined(CLIB_HAVE_VEC256)
395 while (i + 7 < vec_len (ai))
398 v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
399 if (!u64x4_is_all_zero (v))
403 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
404 while (i + 3 < vec_len (ai))
407 v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
408 if (!u64x2_is_all_zero (v))
414 for (; i < vec_len (ai); i++)
418 return i * BITS (ai[0]) + log2_first_set (x);
423 /** Return the higest numbered set bit in a bitmap
424 @param ai - pointer to the bitmap
425 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
428 clib_bitmap_last_set (uword * ai)
432 for (i = vec_len (ai); i > 0; i--)
438 first_bit = count_leading_zeros (x);
439 return (i) * BITS (ai[0]) - first_bit - 1;
445 /** Return the lowest numbered clear bit in a bitmap
446 @param ai - pointer to the bitmap
447 @returns lowest numbered clear bit
450 clib_bitmap_first_clear (uword * ai)
453 for (i = 0; i < vec_len (ai); i++)
457 return i * BITS (ai[0]) + log2_first_set (x);
459 return i * BITS (ai[0]);
462 /** Return the number of set bits in a bitmap
463 @param ai - pointer to the bitmap
464 @returns the number of set bits in the bitmap
467 clib_bitmap_count_set_bits (uword * ai)
471 for (i = 0; i < vec_len (ai); i++)
472 n_set += count_set_bits (ai[i]);
476 /** Logical operator across two bitmaps
478 @param ai - pointer to the destination bitmap
479 @param bi - pointer to the source bitmap
480 @returns ai = ai and bi. ai is modified, bi is not modified
482 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
484 /** Logical operator across two bitmaps
486 @param ai - pointer to the destination bitmap
487 @param bi - pointer to the source bitmap
488 @returns ai = ai & ~bi. ai is modified, bi is not modified
490 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
492 /** Logical operator across two bitmaps
494 @param ai - pointer to the destination bitmap
495 @param bi - pointer to the source bitmap
496 @returns ai = ai & ~bi. ai is modified, bi is not modified
498 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
499 /** Logical operator across two bitmaps
501 @param ai - pointer to the destination bitmap
502 @param bi - pointer to the source bitmap
503 @returns ai = ai or bi. ai is modified, bi is not modified
505 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
507 /** Logical operator across two bitmaps
509 @param ai - pointer to the destination bitmap
510 @param bi - pointer to the source bitmap
511 @returns ai = ai xor bi. ai is modified, bi is not modified
513 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
515 /* ALU function definition macro for functions taking two bitmaps. */
516 #define _(name, body, check_zero) \
517 always_inline uword * \
518 clib_bitmap_##name (uword * ai, uword * bi) \
520 uword i, a, b, bi_len, n_trailing_zeros; \
522 n_trailing_zeros = 0; \
523 bi_len = vec_len (bi); \
525 clib_bitmap_vec_validate (ai, bi_len - 1); \
526 for (i = 0; i < vec_len (ai); i++) \
529 b = i < bi_len ? bi[i] : 0; \
530 do { body; } while (0); \
533 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
536 _vec_len (ai) -= n_trailing_zeros; \
543 _(andnot, a = a & ~b, 1)
548 /** Logical operator across two bitmaps which duplicates the first bitmap
550 @param ai - pointer to the destination bitmap
551 @param bi - pointer to the source bitmap
552 @returns aiDup = ai and bi. Neither ai nor bi are modified
554 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
556 /** Logical operator across two bitmaps which duplicates the first bitmap
558 @param ai - pointer to the destination bitmap
559 @param bi - pointer to the source bitmap
560 @returns aiDup = ai & ~bi. Neither ai nor bi are modified
562 always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
564 /** Logical operator across two bitmaps which duplicates the first bitmap
566 @param ai - pointer to the destination bitmap
567 @param bi - pointer to the source bitmap
568 @returns aiDup = ai or bi. Neither ai nor bi are modified
570 always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
572 /** Logical operator across two bitmaps which duplicates the first bitmap
574 @param ai - pointer to the destination bitmap
575 @param bi - pointer to the source bitmap
576 @returns aiDup = ai xor bi. Neither ai nor bi are modified
578 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
581 always_inline uword * \
582 clib_bitmap_dup_##name (uword * ai, uword * bi) \
583 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
593 /* ALU function definition macro for functions taking one bitmap and an
595 #define _(name, body, check_zero) \
596 always_inline uword * \
597 clib_bitmap_##name (uword * ai, uword i) \
599 uword i0 = i / BITS (ai[0]); \
600 uword i1 = i % BITS (ai[0]); \
602 clib_bitmap_vec_validate (ai, i0); \
604 b = (uword) 1 << i1; \
605 do { body; } while (0); \
607 if (check_zero && a == 0) \
608 ai = _clib_bitmap_remove_trailing_zeros (ai); \
612 /* ALU functions immediate: */
614 _(andi, a = a & b, 1)
615 _(andnoti, a = a & ~b, 1)
617 _(xori, a = a ^ b, 1)
621 /* ALU function definition macro for functions taking one bitmap and an
622 * immediate. No tail trimming */
623 #define _(name, body) \
624 always_inline uword * \
625 clib_bitmap_##name##_notrim (uword * ai, uword i) \
627 uword i0 = i / BITS (ai[0]); \
628 uword i1 = i % BITS (ai[0]); \
630 clib_bitmap_vec_validate (ai, i0); \
632 b = (uword) 1 << i1; \
633 do { body; } while (0); \
638 /* ALU functions immediate: */
641 _(andnoti, a = a & ~b)
647 /** Return a random bitmap of the requested length
648 @param ai - pointer to the destination bitmap
649 @param n_bits - number of bits to allocate
650 @param [in,out] seed - pointer to the random number seed
651 @returns a reasonably random bitmap based. See random.h.
653 always_inline uword *
654 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
656 vec_reset_length (ai);
660 uword i = n_bits - 1;
664 log2_rand_max = min_log2 (random_u32_max ());
666 i0 = i / BITS (ai[0]);
667 i1 = i % BITS (ai[0]);
669 clib_bitmap_vec_validate (ai, i0);
670 for (i = 0; i <= i0; i++)
673 for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
674 ai[i] |= random_u32 (seed) << n;
676 if (i1 + 1 < BITS (ai[0]))
677 ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
682 /** Return the next set bit in a bitmap starting at bit i
683 @param ai - pointer to the bitmap
684 @param i - first bit position to test
685 @returns first set bit position at or after i,
686 ~0 if no further set bits are found
689 clib_bitmap_next_set (uword * ai, uword i)
691 uword i0 = i / BITS (ai[0]);
692 uword i1 = i % BITS (ai[0]);
695 if (i0 < vec_len (ai))
697 t = (ai[i0] >> i1) << i1;
699 return log2_first_set (t) + i0 * BITS (ai[0]);
701 for (i0++; i0 < vec_len (ai); i0++)
705 return log2_first_set (t) + i0 * BITS (ai[0]);
712 /** Return the next clear bit in a bitmap starting at bit i
713 @param ai - pointer to the bitmap
714 @param i - first bit position to test
715 @returns first clear bit position at or after i
718 clib_bitmap_next_clear (uword * ai, uword i)
720 uword i0 = i / BITS (ai[0]);
721 uword i1 = i % BITS (ai[0]);
724 if (i0 < vec_len (ai))
726 t = (~ai[i0] >> i1) << i1;
728 return log2_first_set (t) + i0 * BITS (ai[0]);
730 for (i0++; i0 < vec_len (ai); i0++)
734 return log2_first_set (t) + i0 * BITS (ai[0]);
737 /* no clear bit left in bitmap, return bit just beyond bitmap */
738 return (i0 * BITS (ai[0])) + 1;
743 uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
744 uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
745 u8 *format_bitmap_hex (u8 *s, va_list *args);
746 u8 *format_bitmap_list (u8 *s, va_list *args);
748 #endif /* included_clib_bitmap_h */
751 * fd.io coding-style-patch-verification: ON
754 * eval: (c-set-style "gnu")