FD.io VPP  v16.06
Vector Packet Processing
bitmap.h
Go to the documentation of this file.
1 /*
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:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
17 
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:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
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.
36 */
37 
38 #ifndef included_clib_bitmap_h
39 #define included_clib_bitmap_h
40 
41 /* Bitmaps built as vectors of machine words. */
42 
43 #include <vppinfra/vec.h>
44 #include <vppinfra/random.h>
45 #include <vppinfra/error.h>
46 #include <vppinfra/bitops.h> /* for count_set_bits */
47 
48 /* Returns 1 if the entire bitmap is zero, 0 otherwise */
51 {
52  uword i;
53  for (i = 0; i < vec_len (ai); i++)
54  if (ai[i] != 0)
55  return 0;
56  return 1;
57 }
58 
59 /* Returns 1 if two bitmaps are equal, 0 otherwise */
62 {
63  uword i;
64  if (vec_len (a) != vec_len (b))
65  return 0;
66  for (i = 0; i < vec_len (a); i++)
67  if (a[i] != b[i])
68  return 0;
69  return 1;
70 }
71 
72 /* Duplicate a bitmap */
73 #define clib_bitmap_dup(v) vec_dup(v)
74 
75 /* Free a bitmap */
76 #define clib_bitmap_free(v) vec_free(v)
77 
78 /* Returns the number of bytes in a bitmap */
79 #define clib_bitmap_bytes(v) vec_bytes(v)
80 
81 /* Clear a bitmap */
82 #define clib_bitmap_zero(v) vec_zero(v)
83 
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))
87 
88 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
89 
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))
93 
94 /* low-level routine to remove trailing zeros from a bitmap */
96 _clib_bitmap_remove_trailing_zeros (uword * a)
97 {
98  word i;
99  if (a)
100  {
101  for (i = _vec_len (a) - 1; i >= 0; i--)
102  if (a[i] != 0)
103  break;
104  _vec_len (a) = i + 1;
105  }
106  return a;
107 }
108 
109 /* Sets the ith bit of a bitmap to new_value. Returns old value.
110  No sanity checking. Be careful. */
113 {
114  uword i0 = i / BITS (a[0]);
115  uword i1 = i % BITS (a[0]);
116  uword bit = (uword) 1 << i1;
117  uword ai, old_value;
118 
119  /* Removed ASSERT since uword * a may not be a vector. */
120  /* ASSERT (i0 < vec_len (a)); */
121 
122  ai = a[i0];
123  old_value = (ai & bit) != 0;
124  ai &= ~ bit;
125  ai |= ((uword) (new_value != 0)) << i1;
126  a[i0] = ai;
127  return old_value;
128 }
129 
130 /* Set bit I to value (either non-zero or zero). */
133 {
134  uword i0 = i / BITS (ai[0]);
135  uword i1 = i % BITS (ai[0]);
136  uword a;
137 
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. */
141 
142  clib_bitmap_vec_validate (ai, i0);
143 
144  a = ai[i0];
145  a &= ~((uword) 1 << i1);
146  a |= ((uword) (value != 0)) << i1;
147  ai[i0] = a;
148 
149  /* If bits have been cleared, test for zero. */
150  if (a == 0)
151  ai = _clib_bitmap_remove_trailing_zeros (ai);
152 
153  return ai;
154 }
155 
156 /* Fetch bit I. */
159 {
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);
163 }
164 
165 /* Fetch bit I.
166 
167  No sanity checking. Be careful.
168 */
171 {
172  uword i0 = i / BITS (ai[0]);
173  uword i1 = i % BITS (ai[0]);
174  return 0 != ((ai[i0] >> i1) & 1);
175 }
176 
177 /* I through I + N_BITS.
178 
179  No sanity checking. Be careful.
180 */
183 {
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));
188 }
189 
190 /* Fetch bits I through I + N_BITS. */
193 {
194  uword i0, i1, result;
195  uword l = vec_len (bitmap);
196 
197  ASSERT (n_bits >= 0 && n_bits <= BITS (result));
198 
199  i0 = i / BITS (bitmap[0]);
200  i1 = i % BITS (bitmap[0]);
201 
202  /* Check first word. */
203  result = 0;
204  if (i0 < l)
205  {
206  result |= (bitmap[i0] >> i1);
207  if (n_bits < BITS (bitmap[0]))
208  result &= (((uword) 1 << n_bits) - 1);
209  }
210 
211  /* Check for overlap into next word. */
212  i0++;
213  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
214  {
215  n_bits -= BITS (bitmap[0]) - i1;
216  result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
217  }
218 
219  return result;
220 }
221 
222 /* Set bits I through I + N_BITS to given value.
223 
224  New bitmap will be returned. */
226 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
227 {
228  uword i0, i1, l, t, m;
229 
230  ASSERT (n_bits >= 0 && n_bits <= BITS (value));
231 
232  i0 = i / BITS (bitmap[0]);
233  i1 = i % BITS (bitmap[0]);
234 
235  /* Allocate bitmap. */
236  clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
237  l = vec_len (bitmap);
238 
239  m = ~0;
240  if (n_bits < BITS (value))
241  m = (((uword) 1 << n_bits) - 1);
242  value &= m;
243 
244  /* Insert into first word. */
245  t = bitmap[i0];
246  t &= ~(m << i1);
247  t |= value << i1;
248  bitmap[i0] = t;
249 
250  /* Insert into second word. */
251  i0++;
252  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
253  {
254  t = BITS (bitmap[0]) - i1;
255  value >>= t;
256  n_bits -= t;
257  t = bitmap[i0];
258  m = ((uword) 1 << n_bits) - 1;
259  t &= ~m;
260  t |= value;
261  bitmap[i0] = t;
262  }
263 
264  return bitmap;
265 }
266 
267 /* For a multi-word region set all bits to given value. */
269 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
270 {
271  uword a0, a1, b0;
272  uword i_end, mask;
273 
274  a0 = i / BITS (bitmap[0]);
275  a1 = i % BITS (bitmap[0]);
276 
277  i_end = i + n_bits;
278  b0 = i_end / BITS (bitmap[0]);
279 
280  clib_bitmap_vec_validate (bitmap, b0);
281 
282  /* First word. */
283  mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
284  mask <<= a1;
285 
286  if (value)
287  bitmap[a0] |= mask;
288  else
289  bitmap[a0] &= ~mask;
290 
291  for (a0++; a0 < b0; a0++)
292  bitmap[a0] = value ? ~0 : 0;
293 
294  if (a0 == b0)
295  {
296  word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
297  mask = pow2_mask (n_bits_left);
298  if (value)
299  bitmap[a0] |= mask;
300  else
301  bitmap[a0] &= ~mask;
302  }
303 
304  return bitmap;
305 }
306 
307 /* Iterate through set bits. */
308 #define clib_bitmap_foreach(i,ai,body) \
309 do { \
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++) \
313  { \
314  __bitmap_ai = (ai)[__bitmap_i]; \
315  while (__bitmap_ai != 0) \
316  { \
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; \
322  } \
323  } \
324 } while (0)
325 
326 /* Return lowest numbered set bit in bitmap.
327 
328  Return infinity (~0) if bitmap is zero. */
330 {
331  uword i;
332  for (i = 0; i < vec_len (ai); i++)
333  {
334  uword x = ai[i];
335  if (x != 0)
336  return i * BITS (ai[0]) + log2_first_set (x);
337  }
338  return ~0;
339 }
340 
341 /* Return lowest numbered clear bit in bitmap. */
344 {
345  uword i;
346  for (i = 0; i < vec_len (ai); i++)
347  {
348  uword x = ~ai[i];
349  if (x != 0)
350  return i * BITS (ai[0]) + log2_first_set (x);
351  }
352  return i * BITS (ai[0]);
353 }
354 
355 /* Count number of set bits in bitmap. */
358 {
359  uword i;
360  uword n_set = 0;
361  for (i = 0; i < vec_len (ai); i++)
362  n_set += count_set_bits (ai[i]);
363  return n_set;
364 }
365 
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) \
370 { \
371  uword i, a, b, bi_len, n_trailing_zeros; \
372  \
373  n_trailing_zeros = 0; \
374  bi_len = vec_len (bi); \
375  if (bi_len > 0) \
376  clib_bitmap_vec_validate (ai, bi_len - 1); \
377  for (i = 0; i < vec_len (ai); i++) \
378  { \
379  a = ai[i]; \
380  b = i < bi_len ? bi[i] : 0; \
381  do { body; } while (0); \
382  ai[i] = a; \
383  if (check_zero) \
384  n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
385  } \
386  if (check_zero) \
387  _vec_len (ai) -= n_trailing_zeros; \
388  return ai; \
389 }
390 
391 /* ALU functions: */
392 _ (and, a = a & b, 1)
393 _ (andnot, a = a &~ b, 1)
394 _ (or, a = a | b, 0)
395 _ (xor, a = a ^ b, 1)
396 #undef _
397 
398 /* Define functions which duplicate first argument.
399  (Normal functions over-write first argument.) */
400 #define _(name) \
401  always_inline uword * \
402  clib_bitmap_dup_##name (uword * ai, uword * bi) \
403 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
404 
405 _ (and);
406 _ (andnot);
407 _ (or);
408 _ (xor);
409 
410 #undef _
411 
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) \
416 { \
417  uword i0 = i / BITS (ai[0]); \
418  uword i1 = i % BITS (ai[0]); \
419  uword a, b; \
420  clib_bitmap_vec_validate (ai, i0); \
421  a = ai[i0]; \
422  b = (uword) 1 << i1; \
423  do { body; } while (0); \
424  ai[i0] = a; \
425  if (check_zero && a == 0) \
426  ai = _clib_bitmap_remove_trailing_zeros (ai); \
427  return ai; \
428 }
429 
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)
435 
436 #undef _
437 
438 /* Returns random bitmap of given length. */
440 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
441 {
442  vec_reset_length (ai);
443 
444  if (n_bits > 0)
445  {
446  uword i = n_bits - 1;
447  uword i0, i1;
448  uword log2_rand_max;
449 
450  log2_rand_max = min_log2 (random_u32_max ());
451 
452  i0 = i / BITS (ai[0]);
453  i1 = i % BITS (ai[0]);
454 
455  clib_bitmap_vec_validate (ai, i0);
456  for (i = 0; i <= i0; i++)
457  {
458  uword n;
459  for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
460  ai[i] |= random_u32 (seed) << n;
461  }
462  if (i1 + 1 < BITS (ai[0]))
463  ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
464  }
465  return ai;
466 }
467 
468 /* Returns next set bit starting at bit i (~0 if not found). */
471 {
472  uword i0 = i / BITS (ai[0]);
473  uword i1 = i % BITS (ai[0]);
474  uword t;
475 
476  if (i0 < vec_len (ai))
477  {
478  t = (ai[i0] >> i1) << i1;
479  if (t)
480  return log2_first_set (t) + i0 * BITS (ai[0]);
481 
482  for (i0++; i0 < vec_len (ai); i0++)
483  {
484  t = ai[i0];
485  if (t)
486  return log2_first_set (t) + i0 * BITS (ai[0]);
487  }
488  }
489 
490  return ~0;
491 }
492 
493 /* Returns next clear bit at position >= i */
496 {
497  uword i0 = i / BITS (ai[0]);
498  uword i1 = i % BITS (ai[0]);
499  uword t;
500 
501  if (i0 < vec_len (ai))
502  {
503  t = (~ai[i0] >> i1) << i1;
504  if (t)
505  return log2_first_set (t) + i0 * BITS (ai[0]);
506 
507  for (i0++; i0 < vec_len (ai); i0++)
508  {
509  t = ~ai[i0];
510  if (t)
511  return log2_first_set (t) + i0 * BITS (ai[0]);
512  }
513  }
514  return i;
515 }
516 
517 /* unformat list of bits into bitmap (eg "0-3,5-7,11" ) */
518 static inline uword
520 {
521  uword ** bitmap_return = va_arg (* va, uword **);
522  uword * bitmap = 0;
523 
524  u32 a,b;
525 
527  {
528  int i;
529  if (unformat (input, "%u-%u,", &a, &b))
530  ;
531  else if (unformat (input, "%u,", &a))
532  b = a;
533  else if (unformat (input, "%u-%u", &a, &b))
534  ;
535  else if (unformat (input, "%u", &a))
536  b = a;
537  else if (bitmap)
538  {
539  unformat_put_input(input);
540  break;
541  }
542  else
543  goto error;
544 
545  if (b < a)
546  goto error;
547 
548  for (i = a; i <= b; i++)
549  bitmap = clib_bitmap_set(bitmap, i, 1);
550  }
551  *bitmap_return = bitmap;
552  return 1;
553 error:
554  clib_bitmap_free(bitmap);
555  return 0;
556 }
557 
558 static inline u8 *
559 format_bitmap_hex(u8 * s, va_list * args)
560 {
561  uword * bitmap = va_arg (*args, uword *);
562  int i, is_trailing_zero = 1;
563 
564  if (!bitmap)
565  return format(s, "0");
566 
567  i = vec_bytes (bitmap) * 2;
568 
569  while (i > 0)
570  {
571  u8 x = clib_bitmap_get_multiple(bitmap, --i * 4, 4);
572 
573  if (x && is_trailing_zero)
574  is_trailing_zero = 0;
575 
576  if (x || !is_trailing_zero)
577  s = format(s, "%x", x);
578  }
579  return s;
580 }
581 #endif /* included_clib_bitmap_h */
always_inline uword log2_first_set(uword x)
Definition: clib.h:268
static u8 * format_bitmap_hex(u8 *s, va_list *args)
Definition: bitmap.h:559
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:267
uword unformat(unformat_input_t *i, char *fmt,...)
Definition: unformat.c:942
always_inline uword clib_bitmap_count_set_bits(uword *ai)
Definition: bitmap.h:357
a
Definition: bitmap.h:393
#define UNFORMAT_END_OF_INPUT
Definition: format.h:142
always_inline uword clib_bitmap_get_multiple_no_check(uword *ai, uword i, uword n_bits)
Definition: bitmap.h:182
#define vec_bytes(v)
Number of data bytes in vector.
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
always_inline uword clib_bitmap_is_equal(uword *a, uword *b)
Definition: bitmap.h:61
always_inline uword unformat_check_input(unformat_input_t *i)
Definition: format.h:168
always_inline uword clib_bitmap_next_clear(uword *ai, uword i)
Definition: bitmap.h:495
#define always_inline
Definition: clib.h:84
always_inline uword clib_bitmap_first_set(uword *ai)
Definition: bitmap.h:329
always_inline u32 random_u32(u32 *seed)
32-bit random number generator
Definition: random.h:68
always_inline uword count_set_bits(uword x)
Definition: bitops.h:44
always_inline uword clib_bitmap_set_no_check(uword *a, uword i, uword new_value)
Definition: bitmap.h:112
always_inline uword clib_bitmap_first_clear(uword *ai)
Definition: bitmap.h:343
always_inline uword * clib_bitmap_set(uword *ai, uword i, uword value)
Definition: bitmap.h:132
always_inline uword clib_bitmap_get(uword *ai, uword i)
Definition: bitmap.h:158
always_inline u32 random_u32_max(void)
Maximum value returned by random_u32()
Definition: random.h:77
#define clib_bitmap_vec_validate(v, i)
Definition: bitmap.h:88
always_inline uword * clib_bitmap_set_multiple(uword *bitmap, uword i, uword value, uword n_bits)
Definition: bitmap.h:226
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u8 * format(u8 *s, char *fmt,...)
Definition: format.c:405
always_inline uword * clib_bitmap_random(uword *ai, uword n_bits, u32 *seed)
Definition: bitmap.h:440
#define clib_bitmap_free(v)
Definition: bitmap.h:76
always_inline uword * clib_bitmap_set_region(uword *bitmap, uword i, uword value, uword n_bits)
Definition: bitmap.h:269
u64 uword
Definition: types.h:112
always_inline uword clib_bitmap_is_zero(uword *ai)
Definition: bitmap.h:50
always_inline uword clib_bitmap_get_no_check(uword *ai, uword i)
Definition: bitmap.h:170
i64 word
Definition: types.h:111
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
static uword unformat_bitmap_list(unformat_input_t *input, va_list *va)
Definition: bitmap.h:519
Linear Congruential Random Number Generator.
always_inline uword clib_bitmap_get_multiple(uword *bitmap, uword i, uword n_bits)
Definition: bitmap.h:192
always_inline void unformat_put_input(unformat_input_t *input)
Definition: format.h:203
always_inline uword min_log2(uword x)
Definition: clib.h:181
struct _unformat_input_t unformat_input_t
always_inline uword pow2_mask(uword x)
Definition: clib.h:242
#define BITS(x)
Definition: clib.h:58
always_inline uword clib_bitmap_next_set(uword *ai, uword i)
Definition: bitmap.h:470
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".