src/vppinfra/bitmap.h

   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 /** \file
  42     Bitmaps built as vectors of machine words
  43 */
  44
  45 #include <vppinfra/vec.h>
  46 #include <vppinfra/random.h>
  47 #include <vppinfra/error.h>
  48 #include <vppinfra/bitops.h>    /* for count_set_bits */
  49
  50 typedef uword clib_bitmap_t;
  51
  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
  55 */
  56 always_inline uword
  57 clib_bitmap_is_zero (uword * ai)
  58 {
  59   uword i;
  60   for (i = 0; i < vec_len (ai); i++)
  61     if (ai[i] != 0)
  62       return 0;
  63   return 1;
  64 }
  65
  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
  70 */
  71 always_inline uword
  72 clib_bitmap_is_equal (uword * a, uword * b)
  73 {
  74   uword i;
  75   if (vec_len (a) != vec_len (b))
  76     return 0;
  77   for (i = 0; i < vec_len (a); i++)
  78     if (a[i] != b[i])
  79       return 0;
  80   return 1;
  81 }
  82
  83 /** Duplicate a bitmap
  84     @param v - pointer to a bitmap
  85     @returns a duplicate of the bitmap
  86 */
  87 #define clib_bitmap_dup(v) vec_dup(v)
  88
  89 /** Free a bitmap
  90     @param v - pointer to the bitmap to free
  91 */
  92 #define clib_bitmap_free(v) vec_free(v)
  93
  94 /** Number of bytes in a bitmap
  95     @param v - pointer to the bitmap
  96 */
  97 #define clib_bitmap_bytes(v) vec_bytes(v)
  98
  99 /** Clear a bitmap
 100     @param v - pointer to the bitmap to clear
 101 */
 102 #define clib_bitmap_zero(v) vec_zero(v)
 103
 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
 107 */
 108
 109 #define clib_bitmap_alloc(v,n_bits) \
 110   v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
 111
 112 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
 113
 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))
 117
 118 /** Copy a bitmap
 119     @param dst - copy to
 120     @param src - copy from
 121 */
 122 static_always_inline void
 123 clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src)
 124 {
 125   if (vec_len (src))
 126     {
 127       clib_bitmap_vec_validate (*dst, vec_len (src) - 1);
 128       vec_copy (*dst, src);
 129     }
 130   else
 131     {
 132       vec_reset_length (*dst);
 133     }
 134 }
 135
 136 /* low-level routine to remove trailing zeros from a bitmap */
 137 always_inline uword *
 138 _clib_bitmap_remove_trailing_zeros (uword * a)
 139 {
 140   word i;
 141   if (a)
 142     {
 143       for (i = _vec_len (a) - 1; i >= 0; i--)
 144         if (a[i] != 0)
 145           break;
 146       _vec_len (a) = i + 1;
 147     }
 148   return a;
 149 }
 150
 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
 157 */
 158 always_inline uword
 159 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
 160 {
 161   uword i0 = i / BITS (a[0]);
 162   uword i1 = i % BITS (a[0]);
 163   uword bit = (uword) 1 << i1;
 164   uword ai, old_value;
 165
 166   /* Removed ASSERT since uword * a may not be a vector. */
 167   /* ASSERT (i0 < vec_len (a)); */
 168
 169   ai = a[i0];
 170   old_value = (ai & bit) != 0;
 171   ai &= ~bit;
 172   ai |= ((uword) (new_value != 0)) << i1;
 173   a[i0] = ai;
 174   return old_value;
 175 }
 176
 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
 183 */
 184 always_inline uword *
 185 clib_bitmap_set (uword * ai, uword i, uword value)
 186 {
 187   uword i0 = i / BITS (ai[0]);
 188   uword i1 = i % BITS (ai[0]);
 189   uword a;
 190
 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. */
 194
 195   clib_bitmap_vec_validate (ai, i0);
 196
 197   a = ai[i0];
 198   a &= ~((uword) 1 << i1);
 199   a |= ((uword) (value != 0)) << i1;
 200   ai[i0] = a;
 201
 202   /* If bits have been cleared, test for zero. */
 203   if (a == 0)
 204     ai = _clib_bitmap_remove_trailing_zeros (ai);
 205
 206   return ai;
 207 }
 208
 209 always_inline u8
 210 clib_bitmap_will_expand (uword *ai, uword i)
 211 {
 212   uword i0 = i / BITS (ai[0]);
 213   return _vec_resize_will_expand (ai, 1, i0 * sizeof (ai[0]), 0,
 214                                   sizeof (uword));
 215 }
 216
 217 /** Gets the ith bit value from a bitmap
 218     @param ai - pointer to the bitmap
 219     @param i - the bit position to interrogate
 220     @returns the indicated bit value
 221 */
 222 always_inline uword
 223 clib_bitmap_get (uword * ai, uword i)
 224 {
 225   uword i0 = i / BITS (ai[0]);
 226   uword i1 = i % BITS (ai[0]);
 227   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
 228 }
 229
 230 /** Gets the ith bit value from a bitmap
 231     Does not sanity-check the bit position. Be careful.
 232     @param ai - pointer to the bitmap
 233     @param i - the bit position to interrogate
 234     @returns the indicated bit value, or garbage if the bit position is
 235     out of range.
 236 */
 237 always_inline uword
 238 clib_bitmap_get_no_check (uword * ai, uword i)
 239 {
 240   uword i0 = i / BITS (ai[0]);
 241   uword i1 = i % BITS (ai[0]);
 242   return 0 != ((ai[i0] >> i1) & 1);
 243 }
 244
 245 always_inline uword
 246 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 247 {
 248   uword i0 = i / BITS (ai[0]);
 249   uword i1 = i % BITS (ai[0]);
 250   ASSERT (i1 + n_bits <= BITS (uword));
 251   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
 252 }
 253
 254 /** Gets the ith through ith + n_bits bit values from a bitmap
 255     @param bitmap - pointer to the bitmap
 256     @param i - the first bit position to retrieve
 257     @param n_bits - the number of bit positions to retrieve
 258     @returns the indicated range of bits
 259 */
 260 always_inline uword
 261 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 262 {
 263   uword i0, i1, result;
 264   uword l = vec_len (bitmap);
 265
 266   ASSERT (n_bits <= BITS (result));
 267
 268   i0 = i / BITS (bitmap[0]);
 269   i1 = i % BITS (bitmap[0]);
 270
 271   /* Check first word. */
 272   result = 0;
 273   if (i0 < l)
 274     {
 275       result |= (bitmap[i0] >> i1);
 276       if (n_bits < BITS (bitmap[0]))
 277         result &= (((uword) 1 << n_bits) - 1);
 278     }
 279
 280   /* Check for overlap into next word. */
 281   i0++;
 282   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 283     {
 284       n_bits -= BITS (bitmap[0]) - i1;
 285       result |=
 286         (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 287     }
 288
 289   return result;
 290 }
 291
 292 /** sets the ith through ith + n_bits bits in a bitmap
 293     @param bitmap - pointer to the bitmap
 294     @param i - the first bit position to retrieve
 295     @param value - the values to set
 296     @param n_bits - the number of bit positions to set
 297     @returns a pointer to the updated bitmap, which may expand and move
 298 */
 299
 300 always_inline uword *
 301 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 302 {
 303   uword i0, i1, l, t, m;
 304
 305   ASSERT (n_bits <= BITS (value));
 306
 307   i0 = i / BITS (bitmap[0]);
 308   i1 = i % BITS (bitmap[0]);
 309
 310   /* Allocate bitmap. */
 311   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 312   l = vec_len (bitmap);
 313
 314   m = ~0;
 315   if (n_bits < BITS (value))
 316     m = (((uword) 1 << n_bits) - 1);
 317   value &= m;
 318
 319   /* Insert into first word. */
 320   t = bitmap[i0];
 321   t &= ~(m << i1);
 322   t |= value << i1;
 323   bitmap[i0] = t;
 324
 325   /* Insert into second word. */
 326   i0++;
 327   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 328     {
 329       t = BITS (bitmap[0]) - i1;
 330       value >>= t;
 331       n_bits -= t;
 332       t = bitmap[i0];
 333       m = ((uword) 1 << n_bits) - 1;
 334       t &= ~m;
 335       t |= value;
 336       bitmap[i0] = t;
 337     }
 338
 339   return bitmap;
 340 }
 341
 342 always_inline uword *
 343 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 344 {
 345   uword a0, a1, b0;
 346   uword i_end, mask;
 347
 348   a0 = i / BITS (bitmap[0]);
 349   a1 = i % BITS (bitmap[0]);
 350
 351   i_end = i + n_bits;
 352   b0 = i_end / BITS (bitmap[0]);
 353
 354   clib_bitmap_vec_validate (bitmap, b0);
 355
 356   /* First word. */
 357   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 358   mask <<= a1;
 359
 360   if (value)
 361     bitmap[a0] |= mask;
 362   else
 363     bitmap[a0] &= ~mask;
 364
 365   for (a0++; a0 < b0; a0++)
 366     bitmap[a0] = value ? ~0 : 0;
 367
 368   if (a0 == b0)
 369     {
 370       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 371       mask = pow2_mask (n_bits_left);
 372       if (value)
 373         bitmap[a0] |= mask;
 374       else
 375         bitmap[a0] &= ~mask;
 376     }
 377
 378   return bitmap;
 379 }
 380
 381 /** Macro to iterate across set bits in a bitmap
 382
 383     @param i - the current set bit
 384     @param ai - the bitmap
 385     @param body - the expression to evaluate for each set bit
 386 */
 387 #define clib_bitmap_foreach(i,ai)                                       \
 388   if (ai)                                                               \
 389     for (i = clib_bitmap_first_set (ai);                                \
 390          i != ~0;                                                       \
 391          i = clib_bitmap_next_set (ai, i + 1))
 392
 393 /** Return the lowest numbered set bit in a bitmap
 394     @param ai - pointer to the bitmap
 395     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 396 */
 397 always_inline uword
 398 clib_bitmap_first_set (uword * ai)
 399 {
 400   uword i = 0;
 401 #if uword_bits == 64
 402 #if defined(CLIB_HAVE_VEC256)
 403   while (i + 7 < vec_len (ai))
 404     {
 405       u64x4 v;
 406       v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
 407       if (!u64x4_is_all_zero (v))
 408         break;
 409       i += 8;
 410     }
 411 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 412   while (i + 3 < vec_len (ai))
 413     {
 414       u64x2 v;
 415       v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
 416       if (!u64x2_is_all_zero (v))
 417         break;
 418       i += 4;
 419     }
 420 #endif
 421 #endif
 422   for (; i < vec_len (ai); i++)
 423     {
 424       uword x = ai[i];
 425       if (x != 0)
 426         return i * BITS (ai[0]) + log2_first_set (x);
 427     }
 428   return ~0;
 429 }
 430
 431 /** Return the higest numbered set bit in a bitmap
 432     @param ai - pointer to the bitmap
 433     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 434 */
 435 always_inline uword
 436 clib_bitmap_last_set (uword * ai)
 437 {
 438   uword i;
 439
 440   for (i = vec_len (ai); i > 0; i--)
 441     {
 442       uword x = ai[i - 1];
 443       if (x != 0)
 444         {
 445           uword first_bit;
 446           first_bit = count_leading_zeros (x);
 447           return (i) * BITS (ai[0]) - first_bit - 1;
 448         }
 449     }
 450   return ~0;
 451 }
 452
 453 /** Return the lowest numbered clear bit in a bitmap
 454     @param ai - pointer to the bitmap
 455     @returns lowest numbered clear bit
 456 */
 457 always_inline uword
 458 clib_bitmap_first_clear (uword * ai)
 459 {
 460   uword i;
 461   for (i = 0; i < vec_len (ai); i++)
 462     {
 463       uword x = ~ai[i];
 464       if (x != 0)
 465         return i * BITS (ai[0]) + log2_first_set (x);
 466     }
 467   return i * BITS (ai[0]);
 468 }
 469
 470 /** Return the number of set bits in a bitmap
 471     @param ai - pointer to the bitmap
 472     @returns the number of set bits in the bitmap
 473 */
 474 always_inline uword
 475 clib_bitmap_count_set_bits (uword * ai)
 476 {
 477   uword i;
 478   uword n_set = 0;
 479   for (i = 0; i < vec_len (ai); i++)
 480     n_set += count_set_bits (ai[i]);
 481   return n_set;
 482 }
 483
 484 /** Logical operator across two bitmaps
 485
 486     @param ai - pointer to the destination bitmap
 487     @param bi - pointer to the source bitmap
 488     @returns ai = ai and bi. ai is modified, bi is not modified
 489 */
 490 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
 491
 492 /** Logical operator across two bitmaps
 493
 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
 497 */
 498 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
 499
 500 /** Logical operator across two bitmaps
 501
 502     @param ai - pointer to the destination bitmap
 503     @param bi - pointer to the source bitmap
 504     @returns ai = ai & ~bi. ai is modified, bi is not modified
 505 */
 506 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 507 /** Logical operator across two bitmaps
 508
 509     @param ai - pointer to the destination bitmap
 510     @param bi - pointer to the source bitmap
 511     @returns ai = ai or bi. ai is modified, bi is not modified
 512 */
 513 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 514
 515 /** Logical operator across two bitmaps
 516
 517     @param ai - pointer to the destination bitmap
 518     @param bi - pointer to the source bitmap
 519     @returns ai = ai xor bi. ai is modified, bi is not modified
 520 */
 521 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
 522
 523 /* ALU function definition macro for functions taking two bitmaps. */
 524 #define _(name, body, check_zero)                               \
 525 always_inline uword *                                           \
 526 clib_bitmap_##name (uword * ai, uword * bi)                     \
 527 {                                                               \
 528   uword i, a, b, bi_len, n_trailing_zeros;                      \
 529                                                                 \
 530   n_trailing_zeros = 0;                                         \
 531   bi_len = vec_len (bi);                                        \
 532   if (bi_len > 0)                                               \
 533     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 534   for (i = 0; i < vec_len (ai); i++)                            \
 535     {                                                           \
 536       a = ai[i];                                                \
 537       b = i < bi_len ? bi[i] : 0;                               \
 538       do { body; } while (0);                                   \
 539       ai[i] = a;                                                \
 540       if (check_zero)                                           \
 541         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 542     }                                                           \
 543   if (check_zero)                                               \
 544     _vec_len (ai) -= n_trailing_zeros;                          \
 545   return ai;                                                    \
 546 }
 547
 548 /* ALU functions: */
 549 /* *INDENT-OFF* */
 550 _(and, a = a & b, 1)
 551 _(andnot, a = a & ~b, 1)
 552 _(or, a = a | b, 0)
 553 _(xor, a = a ^ b, 1)
 554 /* *INDENT-ON* */
 555 #undef _
 556 /** Logical operator across two bitmaps which duplicates the first bitmap
 557
 558     @param ai - pointer to the destination bitmap
 559     @param bi - pointer to the source bitmap
 560     @returns aiDup = ai and bi. Neither ai nor bi are modified
 561 */
 562 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
 563
 564 /** Logical operator across two bitmaps which duplicates the first bitmap
 565
 566     @param ai - pointer to the destination bitmap
 567     @param bi - pointer to the source bitmap
 568     @returns aiDup = ai & ~bi. Neither ai nor bi are modified
 569 */
 570 always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
 571
 572 /** Logical operator across two bitmaps which duplicates the first bitmap
 573
 574     @param ai - pointer to the destination bitmap
 575     @param bi - pointer to the source bitmap
 576     @returns aiDup = ai or bi. Neither ai nor bi are modified
 577 */
 578 always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
 579
 580 /** Logical operator across two bitmaps which duplicates the first bitmap
 581
 582     @param ai - pointer to the destination bitmap
 583     @param bi - pointer to the source bitmap
 584     @returns aiDup = ai xor bi. Neither ai nor bi are modified
 585 */
 586 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
 587
 588 #define _(name)                                         \
 589   always_inline uword *                                 \
 590   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 591 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 592
 593 /* *INDENT-OFF* */
 594 _(and);
 595 _(andnot);
 596 _(or);
 597 _(xor);
 598 /* *INDENT-ON* */
 599 #undef _
 600
 601 /* ALU function definition macro for functions taking one bitmap and an
 602  * immediate. */
 603 #define _(name, body, check_zero)                       \
 604 always_inline uword *                                   \
 605 clib_bitmap_##name (uword * ai, uword i)                \
 606 {                                                       \
 607   uword i0 = i / BITS (ai[0]);                          \
 608   uword i1 = i % BITS (ai[0]);                          \
 609   uword a, b;                                           \
 610   clib_bitmap_vec_validate (ai, i0);                    \
 611   a = ai[i0];                                           \
 612   b = (uword) 1 << i1;                                  \
 613   do { body; } while (0);                               \
 614   ai[i0] = a;                                           \
 615   if (check_zero && a == 0)                             \
 616     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 617   return ai;                                            \
 618 }
 619
 620 /* ALU functions immediate: */
 621 /* *INDENT-OFF* */
 622 _(andi, a = a & b, 1)
 623 _(andnoti, a = a & ~b, 1)
 624 _(ori, a = a | b, 0)
 625 _(xori, a = a ^ b, 1)
 626 /* *INDENT-ON* */
 627 #undef _
 628
 629 /* ALU function definition macro for functions taking one bitmap and an
 630  * immediate. No tail trimming */
 631 #define _(name, body)                                   \
 632 always_inline uword *                                   \
 633 clib_bitmap_##name##_notrim (uword * ai, uword i)       \
 634 {                                                       \
 635   uword i0 = i / BITS (ai[0]);                          \
 636   uword i1 = i % BITS (ai[0]);                          \
 637   uword a, b;                                           \
 638   clib_bitmap_vec_validate (ai, i0);                    \
 639   a = ai[i0];                                           \
 640   b = (uword) 1 << i1;                                  \
 641   do { body; } while (0);                               \
 642   ai[i0] = a;                                           \
 643   return ai;                                            \
 644 }
 645
 646 /* ALU functions immediate: */
 647 /* *INDENT-OFF* */
 648 _(andi, a = a & b)
 649 _(andnoti, a = a & ~b)
 650 _(ori, a = a | b)
 651 _(xori, a = a ^ b)
 652 #undef _
 653 /* *INDENT-ON* */
 654
 655 /** Return a random bitmap of the requested length
 656     @param ai - pointer to the destination bitmap
 657     @param n_bits - number of bits to allocate
 658     @param [in,out] seed - pointer to the random number seed
 659     @returns a reasonably random bitmap based. See random.h.
 660 */
 661 always_inline uword *
 662 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 663 {
 664   vec_reset_length (ai);
 665
 666   if (n_bits > 0)
 667     {
 668       uword i = n_bits - 1;
 669       uword i0, i1;
 670       uword log2_rand_max;
 671
 672       log2_rand_max = min_log2 (random_u32_max ());
 673
 674       i0 = i / BITS (ai[0]);
 675       i1 = i % BITS (ai[0]);
 676
 677       clib_bitmap_vec_validate (ai, i0);
 678       for (i = 0; i <= i0; i++)
 679         {
 680           uword n;
 681           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 682             ai[i] |= random_u32 (seed) << n;
 683         }
 684       if (i1 + 1 < BITS (ai[0]))
 685         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 686     }
 687   return ai;
 688 }
 689
 690 /** Return the next set bit in a bitmap starting at bit i
 691     @param ai - pointer to the bitmap
 692     @param i - first bit position to test
 693     @returns first set bit position at or after i,
 694     ~0 if no further set bits are found
 695 */
 696 always_inline uword
 697 clib_bitmap_next_set (uword * ai, uword i)
 698 {
 699   uword i0 = i / BITS (ai[0]);
 700   uword i1 = i % BITS (ai[0]);
 701   uword t;
 702
 703   if (i0 < vec_len (ai))
 704     {
 705       t = (ai[i0] >> i1) << i1;
 706       if (t)
 707         return log2_first_set (t) + i0 * BITS (ai[0]);
 708
 709       for (i0++; i0 < vec_len (ai); i0++)
 710         {
 711           t = ai[i0];
 712           if (t)
 713             return log2_first_set (t) + i0 * BITS (ai[0]);
 714         }
 715     }
 716
 717   return ~0;
 718 }
 719
 720 /** Return the next clear bit in a bitmap starting at bit i
 721     @param ai - pointer to the bitmap
 722     @param i - first bit position to test
 723     @returns first clear bit position at or after i
 724 */
 725 always_inline uword
 726 clib_bitmap_next_clear (uword * ai, uword i)
 727 {
 728   uword i0 = i / BITS (ai[0]);
 729   uword i1 = i % BITS (ai[0]);
 730   uword t;
 731
 732   if (i0 < vec_len (ai))
 733     {
 734       t = (~ai[i0] >> i1) << i1;
 735       if (t)
 736         return log2_first_set (t) + i0 * BITS (ai[0]);
 737
 738       for (i0++; i0 < vec_len (ai); i0++)
 739         {
 740           t = ~ai[i0];
 741           if (t)
 742             return log2_first_set (t) + i0 * BITS (ai[0]);
 743         }
 744
 745       return i0 * BITS (ai[0]);
 746     }
 747   return i;
 748 }
 749
 750 uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
 751 uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
 752 u8 *format_bitmap_hex (u8 *s, va_list *args);
 753 u8 *format_bitmap_list (u8 *s, va_list *args);
 754
 755 #endif /* included_clib_bitmap_h */
 756
 757 /*
 758  * fd.io coding-style-patch-verification: ON
 759  *
 760  * Local Variables:
 761  * eval: (c-set-style "gnu")
 762  * End:
 763  */