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
41 /* Bitmaps built as vectors of machine words. */
43 #include <vppinfra/vec.h>
44 #include <vppinfra/random.h>
45 #include <vppinfra/error.h>
46 #include <vppinfra/bitops.h> /* for count_set_bits */
48 /* Returns 1 if the entire bitmap is zero, 0 otherwise */
50 clib_bitmap_is_zero (uword * ai)
53 for (i = 0; i < vec_len (ai); i++)
59 /* Returns 1 if two bitmaps are equal, 0 otherwise */
61 clib_bitmap_is_equal (uword * a, uword * b)
64 if (vec_len (a) != vec_len (b))
66 for (i = 0; i < vec_len (a); i++)
72 /* Duplicate a bitmap */
73 #define clib_bitmap_dup(v) vec_dup(v)
76 #define clib_bitmap_free(v) vec_free(v)
78 /* Returns the number of bytes in a bitmap */
79 #define clib_bitmap_bytes(v) vec_bytes(v)
82 #define clib_bitmap_zero(v) vec_zero(v)
84 /* Allocate bitmap with given number of bits. */
85 #define clib_bitmap_alloc(v,n_bits) \
86 v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
88 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
90 /* Make sure that a bitmap is at least n_bits in size */
91 #define clib_bitmap_validate(v,n_bits) \
92 clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
94 /* low-level routine to remove trailing zeros from a bitmap */
96 _clib_bitmap_remove_trailing_zeros (uword * a)
101 for (i = _vec_len (a) - 1; i >= 0; i--)
104 _vec_len (a) = i + 1;
109 /* Sets the ith bit of a bitmap to new_value. Returns old value.
110 No sanity checking. Be careful. */
112 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
114 uword i0 = i / BITS (a[0]);
115 uword i1 = i % BITS (a[0]);
116 uword bit = (uword) 1 << i1;
119 /* Removed ASSERT since uword * a may not be a vector. */
120 /* ASSERT (i0 < vec_len (a)); */
123 old_value = (ai & bit) != 0;
125 ai |= ((uword) (new_value != 0)) << i1;
130 /* Set bit I to value (either non-zero or zero). */
131 always_inline uword *
132 clib_bitmap_set (uword * ai, uword i, uword value)
134 uword i0 = i / BITS (ai[0]);
135 uword i1 = i % BITS (ai[0]);
138 /* Check for writing a zero to beyond end of bitmap. */
139 if (value == 0 && i0 >= vec_len (ai))
140 return ai; /* Implied trailing zeros. */
142 clib_bitmap_vec_validate (ai, i0);
145 a &= ~((uword) 1 << i1);
146 a |= ((uword) (value != 0)) << i1;
149 /* If bits have been cleared, test for zero. */
151 ai = _clib_bitmap_remove_trailing_zeros (ai);
158 clib_bitmap_get (uword * ai, uword i)
160 uword i0 = i / BITS (ai[0]);
161 uword i1 = i % BITS (ai[0]);
162 return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
167 No sanity checking. Be careful.
170 clib_bitmap_get_no_check (uword * ai, uword i)
172 uword i0 = i / BITS (ai[0]);
173 uword i1 = i % BITS (ai[0]);
174 return 0 != ((ai[i0] >> i1) & 1);
177 /* I through I + N_BITS.
179 No sanity checking. Be careful.
182 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
184 uword i0 = i / BITS (ai[0]);
185 uword i1 = i % BITS (ai[0]);
186 ASSERT (i1 + n_bits <= BITS (uword));
187 return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
190 /* Fetch bits I through I + N_BITS. */
192 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
194 uword i0, i1, result;
195 uword l = vec_len (bitmap);
197 ASSERT (n_bits >= 0 && n_bits <= BITS (result));
199 i0 = i / BITS (bitmap[0]);
200 i1 = i % BITS (bitmap[0]);
202 /* Check first word. */
206 result |= (bitmap[i0] >> i1);
207 if (n_bits < BITS (bitmap[0]))
208 result &= (((uword) 1 << n_bits) - 1);
211 /* Check for overlap into next word. */
213 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
215 n_bits -= BITS (bitmap[0]) - i1;
216 result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
222 /* Set bits I through I + N_BITS to given value.
224 New bitmap will be returned. */
225 always_inline uword *
226 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
228 uword i0, i1, l, t, m;
230 ASSERT (n_bits >= 0 && n_bits <= BITS (value));
232 i0 = i / BITS (bitmap[0]);
233 i1 = i % BITS (bitmap[0]);
235 /* Allocate bitmap. */
236 clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
237 l = vec_len (bitmap);
240 if (n_bits < BITS (value))
241 m = (((uword) 1 << n_bits) - 1);
244 /* Insert into first word. */
250 /* Insert into second word. */
252 if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
254 t = BITS (bitmap[0]) - i1;
258 m = ((uword) 1 << n_bits) - 1;
267 /* For a multi-word region set all bits to given value. */
268 always_inline uword *
269 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
274 a0 = i / BITS (bitmap[0]);
275 a1 = i % BITS (bitmap[0]);
278 b0 = i_end / BITS (bitmap[0]);
280 clib_bitmap_vec_validate (bitmap, b0);
283 mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
291 for (a0++; a0 < b0; a0++)
292 bitmap[a0] = value ? ~0 : 0;
296 word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
297 mask = pow2_mask (n_bits_left);
307 /* Iterate through set bits. */
308 #define clib_bitmap_foreach(i,ai,body) \
310 uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \
311 __bitmap_len = vec_len ((ai)); \
312 for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \
314 __bitmap_ai = (ai)[__bitmap_i]; \
315 while (__bitmap_ai != 0) \
317 __bitmap_first_set = first_set (__bitmap_ai); \
318 (i) = (__bitmap_i * BITS ((ai)[0]) \
319 + min_log2 (__bitmap_first_set)); \
320 do { body; } while (0); \
321 __bitmap_ai ^= __bitmap_first_set; \
326 /* Return lowest numbered set bit in bitmap.
328 Return infinity (~0) if bitmap is zero. */
329 always_inline uword clib_bitmap_first_set (uword * ai)
332 for (i = 0; i < vec_len (ai); i++)
336 return i * BITS (ai[0]) + log2_first_set (x);
341 /* Return lowest numbered clear bit in bitmap. */
343 clib_bitmap_first_clear (uword * ai)
346 for (i = 0; i < vec_len (ai); i++)
350 return i * BITS (ai[0]) + log2_first_set (x);
352 return i * BITS (ai[0]);
355 /* Count number of set bits in bitmap. */
357 clib_bitmap_count_set_bits (uword * ai)
361 for (i = 0; i < vec_len (ai); i++)
362 n_set += count_set_bits (ai[i]);
366 /* ALU function definition macro for functions taking two bitmaps. */
367 #define _(name, body, check_zero) \
368 always_inline uword * \
369 clib_bitmap_##name (uword * ai, uword * bi) \
371 uword i, a, b, bi_len, n_trailing_zeros; \
373 n_trailing_zeros = 0; \
374 bi_len = vec_len (bi); \
376 clib_bitmap_vec_validate (ai, bi_len - 1); \
377 for (i = 0; i < vec_len (ai); i++) \
380 b = i < bi_len ? bi[i] : 0; \
381 do { body; } while (0); \
384 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
387 _vec_len (ai) -= n_trailing_zeros; \
392 _ (and, a = a & b, 1)
393 _ (andnot, a = a &~ b, 1)
395 _ (xor, a = a ^ b, 1)
398 /* Define functions which duplicate first argument.
399 (Normal functions over-write first argument.) */
401 always_inline uword * \
402 clib_bitmap_dup_##name (uword * ai, uword * bi) \
403 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
412 /* ALU function definition macro for functions taking one bitmap and an immediate. */
413 #define _(name, body, check_zero) \
414 always_inline uword * \
415 clib_bitmap_##name (uword * ai, uword i) \
417 uword i0 = i / BITS (ai[0]); \
418 uword i1 = i % BITS (ai[0]); \
420 clib_bitmap_vec_validate (ai, i0); \
422 b = (uword) 1 << i1; \
423 do { body; } while (0); \
425 if (check_zero && a == 0) \
426 ai = _clib_bitmap_remove_trailing_zeros (ai); \
430 /* ALU functions immediate: */
431 _ (andi, a = a & b, 1)
432 _ (andnoti, a = a &~ b, 1)
433 _ (ori, a = a | b, 0)
434 _ (xori, a = a ^ b, 1)
438 /* Returns random bitmap of given length. */
439 always_inline uword *
440 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
442 vec_reset_length (ai);
446 uword i = n_bits - 1;
450 log2_rand_max = min_log2 (random_u32_max ());
452 i0 = i / BITS (ai[0]);
453 i1 = i % BITS (ai[0]);
455 clib_bitmap_vec_validate (ai, i0);
456 for (i = 0; i <= i0; i++)
459 for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
460 ai[i] |= random_u32 (seed) << n;
462 if (i1 + 1 < BITS (ai[0]))
463 ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
468 /* Returns next set bit starting at bit i (~0 if not found). */
470 clib_bitmap_next_set (uword * ai, uword i)
472 uword i0 = i / BITS (ai[0]);
473 uword i1 = i % BITS (ai[0]);
476 if (i0 < vec_len (ai))
478 t = (ai[i0] >> i1) << i1;
480 return log2_first_set (t) + i0 * BITS (ai[0]);
482 for (i0++; i0 < vec_len (ai); i0++)
486 return log2_first_set (t) + i0 * BITS (ai[0]);
493 /* Returns next clear bit at position >= i */
495 clib_bitmap_next_clear (uword * ai, uword i)
497 uword i0 = i / BITS (ai[0]);
498 uword i1 = i % BITS (ai[0]);
501 if (i0 < vec_len (ai))
503 t = (~ai[i0] >> i1) << i1;
505 return log2_first_set (t) + i0 * BITS (ai[0]);
507 for (i0++; i0 < vec_len (ai); i0++)
511 return log2_first_set (t) + i0 * BITS (ai[0]);
517 /* unformat list of bits into bitmap (eg "0-3,5-7,11" ) */
519 unformat_bitmap_list(unformat_input_t * input, va_list * va)
521 uword ** bitmap_return = va_arg (* va, uword **);
526 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
529 if (unformat (input, "%u-%u,", &a, &b))
531 else if (unformat (input, "%u,", &a))
533 else if (unformat (input, "%u-%u", &a, &b))
535 else if (unformat (input, "%u", &a))
539 unformat_put_input(input);
545 if ((b < a) || (b > 63))
548 for (i = a; i <= b; i++)
549 bitmap = clib_bitmap_set(bitmap, i, 1);
551 *bitmap_return = bitmap;
554 clib_bitmap_free(bitmap);
558 #endif /* included_clib_bitmap_h */