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 /** 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
 213 */
 214 always_inline uword
 215 clib_bitmap_get (uword * ai, uword i)
 216 {
 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);
 220 }
 221
 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
 227     out of range.
 228 */
 229 always_inline uword
 230 clib_bitmap_get_no_check (uword * ai, uword i)
 231 {
 232   uword i0 = i / BITS (ai[0]);
 233   uword i1 = i % BITS (ai[0]);
 234   return 0 != ((ai[i0] >> i1) & 1);
 235 }
 236
 237 always_inline uword
 238 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 239 {
 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));
 244 }
 245
 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
 251 */
 252 always_inline uword
 253 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 254 {
 255   uword i0, i1, result;
 256   uword l = vec_len (bitmap);
 257
 258   ASSERT (n_bits <= BITS (result));
 259
 260   i0 = i / BITS (bitmap[0]);
 261   i1 = i % BITS (bitmap[0]);
 262
 263   /* Check first word. */
 264   result = 0;
 265   if (i0 < l)
 266     {
 267       result |= (bitmap[i0] >> i1);
 268       if (n_bits < BITS (bitmap[0]))
 269         result &= (((uword) 1 << n_bits) - 1);
 270     }
 271
 272   /* Check for overlap into next word. */
 273   i0++;
 274   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 275     {
 276       n_bits -= BITS (bitmap[0]) - i1;
 277       result |=
 278         (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 279     }
 280
 281   return result;
 282 }
 283
 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
 290 */
 291
 292 always_inline uword *
 293 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 294 {
 295   uword i0, i1, l, t, m;
 296
 297   ASSERT (n_bits <= BITS (value));
 298
 299   i0 = i / BITS (bitmap[0]);
 300   i1 = i % BITS (bitmap[0]);
 301
 302   /* Allocate bitmap. */
 303   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 304   l = vec_len (bitmap);
 305
 306   m = ~0;
 307   if (n_bits < BITS (value))
 308     m = (((uword) 1 << n_bits) - 1);
 309   value &= m;
 310
 311   /* Insert into first word. */
 312   t = bitmap[i0];
 313   t &= ~(m << i1);
 314   t |= value << i1;
 315   bitmap[i0] = t;
 316
 317   /* Insert into second word. */
 318   i0++;
 319   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 320     {
 321       t = BITS (bitmap[0]) - i1;
 322       value >>= t;
 323       n_bits -= t;
 324       t = bitmap[i0];
 325       m = ((uword) 1 << n_bits) - 1;
 326       t &= ~m;
 327       t |= value;
 328       bitmap[i0] = t;
 329     }
 330
 331   return bitmap;
 332 }
 333
 334 always_inline uword *
 335 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 336 {
 337   uword a0, a1, b0;
 338   uword i_end, mask;
 339
 340   a0 = i / BITS (bitmap[0]);
 341   a1 = i % BITS (bitmap[0]);
 342
 343   i_end = i + n_bits;
 344   b0 = i_end / BITS (bitmap[0]);
 345
 346   clib_bitmap_vec_validate (bitmap, b0);
 347
 348   /* First word. */
 349   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 350   mask <<= a1;
 351
 352   if (value)
 353     bitmap[a0] |= mask;
 354   else
 355     bitmap[a0] &= ~mask;
 356
 357   for (a0++; a0 < b0; a0++)
 358     bitmap[a0] = value ? ~0 : 0;
 359
 360   if (a0 == b0)
 361     {
 362       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 363       mask = pow2_mask (n_bits_left);
 364       if (value)
 365         bitmap[a0] |= mask;
 366       else
 367         bitmap[a0] &= ~mask;
 368     }
 369
 370   return bitmap;
 371 }
 372
 373 /** Macro to iterate across set bits in a bitmap
 374
 375     @param i - the current set bit
 376     @param ai - the bitmap
 377     @param body - the expression to evaluate for each set bit
 378 */
 379 #define clib_bitmap_foreach(i,ai)                                       \
 380   if (ai)                                                               \
 381     for (i = clib_bitmap_first_set (ai);                                \
 382          i != ~0;                                                       \
 383          i = clib_bitmap_next_set (ai, i + 1))
 384
 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
 388 */
 389 always_inline uword
 390 clib_bitmap_first_set (uword * ai)
 391 {
 392   uword i = 0;
 393 #if uword_bits == 64
 394 #if defined(CLIB_HAVE_VEC256)
 395   while (i + 7 < vec_len (ai))
 396     {
 397       u64x4 v;
 398       v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
 399       if (!u64x4_is_all_zero (v))
 400         break;
 401       i += 8;
 402     }
 403 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 404   while (i + 3 < vec_len (ai))
 405     {
 406       u64x2 v;
 407       v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
 408       if (!u64x2_is_all_zero (v))
 409         break;
 410       i += 4;
 411     }
 412 #endif
 413 #endif
 414   for (; i < vec_len (ai); i++)
 415     {
 416       uword x = ai[i];
 417       if (x != 0)
 418         return i * BITS (ai[0]) + log2_first_set (x);
 419     }
 420   return ~0;
 421 }
 422
 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
 426 */
 427 always_inline uword
 428 clib_bitmap_last_set (uword * ai)
 429 {
 430   uword i;
 431
 432   for (i = vec_len (ai); i > 0; i--)
 433     {
 434       uword x = ai[i - 1];
 435       if (x != 0)
 436         {
 437           uword first_bit;
 438           first_bit = count_leading_zeros (x);
 439           return (i) * BITS (ai[0]) - first_bit - 1;
 440         }
 441     }
 442   return ~0;
 443 }
 444
 445 /** Return the lowest numbered clear bit in a bitmap
 446     @param ai - pointer to the bitmap
 447     @returns lowest numbered clear bit
 448 */
 449 always_inline uword
 450 clib_bitmap_first_clear (uword * ai)
 451 {
 452   uword i;
 453   for (i = 0; i < vec_len (ai); i++)
 454     {
 455       uword x = ~ai[i];
 456       if (x != 0)
 457         return i * BITS (ai[0]) + log2_first_set (x);
 458     }
 459   return i * BITS (ai[0]);
 460 }
 461
 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
 465 */
 466 always_inline uword
 467 clib_bitmap_count_set_bits (uword * ai)
 468 {
 469   uword i;
 470   uword n_set = 0;
 471   for (i = 0; i < vec_len (ai); i++)
 472     n_set += count_set_bits (ai[i]);
 473   return n_set;
 474 }
 475
 476 /** Logical operator across two bitmaps
 477
 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
 481 */
 482 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
 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 & ~bi. ai is modified, bi is not modified
 489 */
 490 always_inline uword *clib_bitmap_andnot (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_or (uword * ai, uword * bi);
 499 /** Logical operator across two bitmaps
 500
 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
 504 */
 505 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 506
 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 xor bi. ai is modified, bi is not modified
 512 */
 513 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
 514
 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)                     \
 519 {                                                               \
 520   uword i, a, b, bi_len, n_trailing_zeros;                      \
 521                                                                 \
 522   n_trailing_zeros = 0;                                         \
 523   bi_len = vec_len (bi);                                        \
 524   if (bi_len > 0)                                               \
 525     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 526   for (i = 0; i < vec_len (ai); i++)                            \
 527     {                                                           \
 528       a = ai[i];                                                \
 529       b = i < bi_len ? bi[i] : 0;                               \
 530       do { body; } while (0);                                   \
 531       ai[i] = a;                                                \
 532       if (check_zero)                                           \
 533         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 534     }                                                           \
 535   if (check_zero)                                               \
 536     _vec_len (ai) -= n_trailing_zeros;                          \
 537   return ai;                                                    \
 538 }
 539
 540 /* ALU functions: */
 541 /* *INDENT-OFF* */
 542 _(and, a = a & b, 1)
 543 _(andnot, a = a & ~b, 1)
 544 _(or, a = a | b, 0)
 545 _(xor, a = a ^ b, 1)
 546 /* *INDENT-ON* */
 547 #undef _
 548 /** Logical operator across two bitmaps which duplicates the first bitmap
 549
 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
 553 */
 554 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
 555
 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 & ~bi. Neither ai nor bi are modified
 561 */
 562 always_inline uword *clib_bitmap_dup_andnot (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 or bi. Neither ai nor bi are modified
 569 */
 570 always_inline uword *clib_bitmap_dup_or (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 xor bi. Neither ai nor bi are modified
 577 */
 578 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
 579
 580 #define _(name)                                         \
 581   always_inline uword *                                 \
 582   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 583 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 584
 585 /* *INDENT-OFF* */
 586 _(and);
 587 _(andnot);
 588 _(or);
 589 _(xor);
 590 /* *INDENT-ON* */
 591 #undef _
 592
 593 /* ALU function definition macro for functions taking one bitmap and an
 594  * immediate. */
 595 #define _(name, body, check_zero)                       \
 596 always_inline uword *                                   \
 597 clib_bitmap_##name (uword * ai, uword i)                \
 598 {                                                       \
 599   uword i0 = i / BITS (ai[0]);                          \
 600   uword i1 = i % BITS (ai[0]);                          \
 601   uword a, b;                                           \
 602   clib_bitmap_vec_validate (ai, i0);                    \
 603   a = ai[i0];                                           \
 604   b = (uword) 1 << i1;                                  \
 605   do { body; } while (0);                               \
 606   ai[i0] = a;                                           \
 607   if (check_zero && a == 0)                             \
 608     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 609   return ai;                                            \
 610 }
 611
 612 /* ALU functions immediate: */
 613 /* *INDENT-OFF* */
 614 _(andi, a = a & b, 1)
 615 _(andnoti, a = a & ~b, 1)
 616 _(ori, a = a | b, 0)
 617 _(xori, a = a ^ b, 1)
 618 /* *INDENT-ON* */
 619 #undef _
 620
 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)       \
 626 {                                                       \
 627   uword i0 = i / BITS (ai[0]);                          \
 628   uword i1 = i % BITS (ai[0]);                          \
 629   uword a, b;                                           \
 630   clib_bitmap_vec_validate (ai, i0);                    \
 631   a = ai[i0];                                           \
 632   b = (uword) 1 << i1;                                  \
 633   do { body; } while (0);                               \
 634   ai[i0] = a;                                           \
 635   return ai;                                            \
 636 }
 637
 638 /* ALU functions immediate: */
 639 /* *INDENT-OFF* */
 640 _(andi, a = a & b)
 641 _(andnoti, a = a & ~b)
 642 _(ori, a = a | b)
 643 _(xori, a = a ^ b)
 644 #undef _
 645 /* *INDENT-ON* */
 646
 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.
 652 */
 653 always_inline uword *
 654 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 655 {
 656   vec_reset_length (ai);
 657
 658   if (n_bits > 0)
 659     {
 660       uword i = n_bits - 1;
 661       uword i0, i1;
 662       uword log2_rand_max;
 663
 664       log2_rand_max = min_log2 (random_u32_max ());
 665
 666       i0 = i / BITS (ai[0]);
 667       i1 = i % BITS (ai[0]);
 668
 669       clib_bitmap_vec_validate (ai, i0);
 670       for (i = 0; i <= i0; i++)
 671         {
 672           uword n;
 673           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 674             ai[i] |= random_u32 (seed) << n;
 675         }
 676       if (i1 + 1 < BITS (ai[0]))
 677         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 678     }
 679   return ai;
 680 }
 681
 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
 687 */
 688 always_inline uword
 689 clib_bitmap_next_set (uword * ai, uword i)
 690 {
 691   uword i0 = i / BITS (ai[0]);
 692   uword i1 = i % BITS (ai[0]);
 693   uword t;
 694
 695   if (i0 < vec_len (ai))
 696     {
 697       t = (ai[i0] >> i1) << i1;
 698       if (t)
 699         return log2_first_set (t) + i0 * BITS (ai[0]);
 700
 701       for (i0++; i0 < vec_len (ai); i0++)
 702         {
 703           t = ai[i0];
 704           if (t)
 705             return log2_first_set (t) + i0 * BITS (ai[0]);
 706         }
 707     }
 708
 709   return ~0;
 710 }
 711
 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
 716 */
 717 always_inline uword
 718 clib_bitmap_next_clear (uword * ai, uword i)
 719 {
 720   uword i0 = i / BITS (ai[0]);
 721   uword i1 = i % BITS (ai[0]);
 722   uword t;
 723
 724   if (i0 < vec_len (ai))
 725     {
 726       t = (~ai[i0] >> i1) << i1;
 727       if (t)
 728         return log2_first_set (t) + i0 * BITS (ai[0]);
 729
 730       for (i0++; i0 < vec_len (ai); i0++)
 731         {
 732           t = ~ai[i0];
 733           if (t)
 734             return log2_first_set (t) + i0 * BITS (ai[0]);
 735         }
 736
 737       /* no clear bit left in bitmap, return bit just beyond bitmap */
 738       return (i0 * BITS (ai[0])) + 1;
 739     }
 740   return i;
 741 }
 742
 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);
 747
 748 #endif /* included_clib_bitmap_h */
 749
 750 /*
 751  * fd.io coding-style-patch-verification: ON
 752  *
 753  * Local Variables:
 754  * eval: (c-set-style "gnu")
 755  * End:
 756  */