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>
49 typedef uword clib_bitmap_t;
51 /** predicate function; is an entire bitmap empty?
52 @param ai - pointer to a bitmap
53 @returns 1 if the entire bitmap is zero, 0 otherwise
56 clib_bitmap_is_zero (uword * ai)
59 for (i = 0; i < vec_len (ai); i++)
65 /** predicate function; are two bitmaps equal?
66 @param a - pointer to a bitmap
67 @param b - pointer to a bitmap
68 @returns 1 if the bitmaps are equal, 0 otherwise
71 clib_bitmap_is_equal (uword * a, uword * b)
74 if (vec_len (a) != vec_len (b))
76 for (i = 0; i < vec_len (a); i++)
82 /** Duplicate a bitmap
83 @param v - pointer to a bitmap
84 @returns a duplicate of the bitmap
86 #define clib_bitmap_dup(v) vec_dup(v)
89 @param v - pointer to the bitmap to free
91 #define clib_bitmap_free(v) vec_free(v)
93 /** Number of bytes in a bitmap
94 @param v - pointer to the bitmap
96 #define clib_bitmap_bytes(v) vec_bytes(v)
99 @param v - pointer to the bitmap to clear
101 #define clib_bitmap_zero(v) vec_zero(v)
103 /** Allocate a bitmap with the supplied number of bits
104 @param [out] v - the resulting bitmap
105 @param n_bits - the required number of bits
108 #define clib_bitmap_alloc(v,n_bits) \
109 v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
111 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
113 /* Make sure that a bitmap is at least n_bits in size */
114 #define clib_bitmap_validate(v,n_bits) \
115 clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
119 @param src - copy from
121 static_always_inline void
122 clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src)
126 clib_bitmap_vec_validate (*dst, vec_len (src) - 1);
127 vec_copy (*dst, src);
131 vec_reset_length (*dst);
135 /* low-level routine to remove trailing zeros from a bitmap */
136 always_inline uword *
137 _clib_bitmap_remove_trailing_zeros (uword * a)
142 for (i = _vec_len (a) - 1; i >= 0; i--)
145 vec_set_len (a, i + 1);
150 /** Sets the ith bit of a bitmap to new_value.
151 No sanity checking. Be careful.
152 @param a - pointer to the bitmap
153 @param i - the bit position to interrogate
154 @param new_value - new value for the bit
155 @returns the old value of the bit
158 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
160 uword i0 = i / BITS (a[0]);
161 uword i1 = i % BITS (a[0]);
162 uword bit = (uword) 1 << i1;
165 /* Removed ASSERT since uword * a may not be a vector. */
166 /* ASSERT (i0 < vec_len (a)); */
169 old_value = (ai & bit) != 0;
171 ai |= ((uword) (new_value != 0)) << i1;
176 /** Sets the ith bit of a bitmap to new_value
177 Removes trailing zeros from the bitmap
178 @param ai - pointer to the bitmap
179 @param i - the bit position to interrogate
180 @param value - new value for the bit
181 @returns the (possibly reallocated) bitmap object pointer
183 always_inline uword *
184 clib_bitmap_set (uword * ai, uword i, uword value)
186 uword i0 = i / BITS (ai[0]);
187 uword i1 = i % BITS (ai[0]);
190 /* Check for writing a zero to beyond end of bitmap. */
191 if (value == 0 && i0 >= vec_len (ai))
192 return ai; /* Implied trailing zeros. */
194 clib_bitmap_vec_validate (ai, i0);
197 a &= ~((uword) 1 << i1);
198 a |= ((uword) (value != 0)) << i1;
201 /* If bits have been cleared, test for zero. */
203 ai = _clib_bitmap_remove_trailing_zeros (ai);
209 clib_bitmap_will_expand (uword *ai, uword i)
211 return (i / BITS (ai[0])) >= vec_max_len (ai);
214 /** Gets the ith bit value from a bitmap
215 @param ai - pointer to the bitmap
216 @param i - the bit position to interrogate
217 @returns the indicated bit value
220 clib_bitmap_get (uword * ai, uword i)
222 uword i0 = i / BITS (ai[0]);
223 uword i1 = i % BITS (ai[0]);
224 return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
227 /** Gets the ith bit value from a bitmap
228 Does not sanity-check the bit position. Be careful.
229 @param ai - pointer to the bitmap
230 @param i - the bit position to interrogate
231 @returns the indicated bit value, or garbage if the bit position is
235 clib_bitmap_get_no_check (uword * ai, uword i)
237 uword i0 = i / BITS (ai[0]);
238 uword i1 = i % BITS (ai[0]);
239 return 0 != ((ai[i0] >> i1) & 1);
243 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
245 uword i0 = i / BITS (ai[0]);
246 uword i1 = i % BITS (ai[0]);
247 ASSERT (i1 + n_bits <= BITS (uword));
248 return ((ai[i0] >> i1) & pow2_mask (n_bits));
251 /** Gets the ith through ith + n_bits bit values from a bitmap
252 @param bitmap - pointer to the bitmap
253 @param i - the first bit position to retrieve
254 @param n_bits - the number of bit positions to retrieve
255 @returns the indicated range of bits
258 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
260 uword i0, i1, result;
261 uword l = vec_len (bitmap);
263 ASSERT (n_bits <= BITS (result));
265 i0 = i / BITS (bitmap[0]);
266 i1 = i % BITS (bitmap[0]);
268 /* Check first word. */
272 result |= (bitmap[i0] >> i1);
273 if (n_bits < BITS (bitmap[0]))
274 result &= (((uword) 1 << n_bits) - 1);
277 /* Check for overlap into next word. */
279 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
281 n_bits -= BITS (bitmap[0]) - i1;
283 (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
289 /** sets the ith through ith + n_bits bits in a bitmap
290 @param bitmap - pointer to the bitmap
291 @param i - the first bit position to retrieve
292 @param value - the values to set
293 @param n_bits - the number of bit positions to set
294 @returns a pointer to the updated bitmap, which may expand and move
297 always_inline uword *
298 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
300 uword i0, i1, l, t, m;
302 ASSERT (n_bits <= BITS (value));
304 i0 = i / BITS (bitmap[0]);
305 i1 = i % BITS (bitmap[0]);
307 /* Allocate bitmap. */
308 clib_bitmap_vec_validate (bitmap, (i + n_bits - 1) / BITS (bitmap[0]));
309 l = vec_len (bitmap);
312 if (n_bits < BITS (value))
313 m = (((uword) 1 << n_bits) - 1);
316 /* Insert into first word. */
322 /* Insert into second word. */
324 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
326 t = BITS (bitmap[0]) - i1;
330 m = ((uword) 1 << n_bits) - 1;
339 always_inline uword *
340 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
342 uword a0, a1, b0, b1;
345 a0 = i / BITS (bitmap[0]);
346 a1 = i % BITS (bitmap[0]);
348 i_end = i + n_bits - 1;
349 b0 = i_end / BITS (bitmap[0]);
350 b1 = i_end % BITS (bitmap[0]);
352 clib_bitmap_vec_validate (bitmap, b0);
355 mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
363 for (a0++; a0 < b0; a0++)
364 bitmap[a0] = value ? ~0 : 0;
368 mask = (uword) ~0 >> (BITS (bitmap[0]) - b1 - 1);
378 /** Macro to iterate across set bits in a bitmap
380 @param i - the current set bit
381 @param ai - the bitmap
382 @param body - the expression to evaluate for each set bit
384 #define clib_bitmap_foreach(i,ai) \
386 for (i = clib_bitmap_first_set (ai); \
388 i = clib_bitmap_next_set (ai, i + 1))
390 /** Return the lowest numbered set bit in a bitmap
391 @param ai - pointer to the bitmap
392 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
395 clib_bitmap_first_set (uword * ai)
399 #if defined(CLIB_HAVE_VEC256)
400 while (i + 7 < vec_len (ai))
403 v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
404 if (!u64x4_is_all_zero (v))
408 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
409 while (i + 3 < vec_len (ai))
412 v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
413 if (!u64x2_is_all_zero (v))
419 for (; i < vec_len (ai); i++)
423 return i * BITS (ai[0]) + log2_first_set (x);
428 /** Return the higest numbered set bit in a bitmap
429 @param ai - pointer to the bitmap
430 @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
433 clib_bitmap_last_set (uword * ai)
437 for (i = vec_len (ai); i > 0; i--)
443 first_bit = count_leading_zeros (x);
444 return (i) * BITS (ai[0]) - first_bit - 1;
450 /** Return the lowest numbered clear bit in a bitmap
451 @param ai - pointer to the bitmap
452 @returns lowest numbered clear bit
455 clib_bitmap_first_clear (uword * ai)
458 for (i = 0; i < vec_len (ai); i++)
462 return i * BITS (ai[0]) + log2_first_set (x);
464 return i * BITS (ai[0]);
467 /** Return the number of set bits in a bitmap
468 @param ai - pointer to the bitmap
469 @returns the number of set bits in the bitmap
472 clib_bitmap_count_set_bits (uword * ai)
476 for (i = 0; i < vec_len (ai); i++)
477 n_set += count_set_bits (ai[i]);
481 /** Logical operator across two bitmaps
483 @param ai - pointer to the destination bitmap
484 @param bi - pointer to the source bitmap
485 @returns ai = ai and bi. ai is modified, bi is not modified
487 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
489 /** Logical operator across two bitmaps
491 @param ai - pointer to the destination bitmap
492 @param bi - pointer to the source bitmap
493 @returns ai = ai & ~bi. ai is modified, bi is not modified
495 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
497 /** Logical operator across two bitmaps
499 @param ai - pointer to the destination bitmap
500 @param bi - pointer to the source bitmap
501 @returns ai = ai & ~bi. ai is modified, bi is not modified
503 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
504 /** Logical operator across two bitmaps
506 @param ai - pointer to the destination bitmap
507 @param bi - pointer to the source bitmap
508 @returns ai = ai or bi. ai is modified, bi is not modified
510 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
512 /** Logical operator across two bitmaps
514 @param ai - pointer to the destination bitmap
515 @param bi - pointer to the source bitmap
516 @returns ai = ai xor bi. ai is modified, bi is not modified
518 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
520 /* ALU function definition macro for functions taking two bitmaps. */
521 #define _(name, body, check_zero) \
522 always_inline uword *clib_bitmap_##name (uword *ai, uword *bi) \
524 uword i, a, b, bi_len, n_trailing_zeros; \
526 n_trailing_zeros = 0; \
527 bi_len = vec_len (bi); \
529 clib_bitmap_vec_validate (ai, bi_len - 1); \
530 for (i = 0; i < vec_len (ai); i++) \
533 b = i < bi_len ? bi[i] : 0; \
541 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
544 vec_dec_len (ai, n_trailing_zeros); \
550 _(andnot, a = a & ~b, 1)
554 /** Logical operator across two bitmaps which duplicates the first bitmap
556 @param ai - pointer to the destination bitmap
557 @param bi - pointer to the source bitmap
558 @returns aiDup = ai and bi. Neither ai nor bi are modified
560 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
562 /** Logical operator across two bitmaps which duplicates the first bitmap
564 @param ai - pointer to the destination bitmap
565 @param bi - pointer to the source bitmap
566 @returns aiDup = ai & ~bi. Neither ai nor bi are modified
568 always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
570 /** Logical operator across two bitmaps which duplicates the first bitmap
572 @param ai - pointer to the destination bitmap
573 @param bi - pointer to the source bitmap
574 @returns aiDup = ai or bi. Neither ai nor bi are modified
576 always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
578 /** Logical operator across two bitmaps which duplicates the first bitmap
580 @param ai - pointer to the destination bitmap
581 @param bi - pointer to the source bitmap
582 @returns aiDup = ai xor bi. Neither ai nor bi are modified
584 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
587 always_inline uword * \
588 clib_bitmap_dup_##name (uword * ai, uword * bi) \
589 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
597 /* ALU function definition macro for functions taking one bitmap and an
599 #define _(name, body, check_zero) \
600 always_inline uword * \
601 clib_bitmap_##name (uword * ai, uword i) \
603 uword i0 = i / BITS (ai[0]); \
604 uword i1 = i % BITS (ai[0]); \
606 clib_bitmap_vec_validate (ai, i0); \
608 b = (uword) 1 << i1; \
609 do { body; } while (0); \
611 if (check_zero && a == 0) \
612 ai = _clib_bitmap_remove_trailing_zeros (ai); \
616 /* ALU functions immediate: */
617 _(andi, a = a & b, 1)
618 _(andnoti, a = a & ~b, 1)
620 _(xori, a = a ^ b, 1)
623 /* ALU function definition macro for functions taking one bitmap and an
624 * immediate. No tail trimming */
625 #define _(name, body) \
626 always_inline uword * \
627 clib_bitmap_##name##_notrim (uword * ai, uword i) \
629 uword i0 = i / BITS (ai[0]); \
630 uword i1 = i % BITS (ai[0]); \
632 clib_bitmap_vec_validate (ai, i0); \
634 b = (uword) 1 << i1; \
635 do { body; } while (0); \
640 /* ALU functions immediate: */
642 _(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 return i0 * BITS (ai[0]);
742 uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
743 uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
744 u8 *format_bitmap_hex (u8 *s, va_list *args);
745 u8 *format_bitmap_list (u8 *s, va_list *args);
747 #endif /* included_clib_bitmap_h */
750 * fd.io coding-style-patch-verification: ON
753 * eval: (c-set-style "gnu")