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 /* low-level routine to remove trailing zeros from a bitmap */
 119 always_inline uword *
 120 _clib_bitmap_remove_trailing_zeros (uword * a)
 121 {
 122   word i;
 123   if (a)
 124     {
 125       for (i = _vec_len (a) - 1; i >= 0; i--)
 126         if (a[i] != 0)
 127           break;
 128       _vec_len (a) = i + 1;
 129     }
 130   return a;
 131 }
 132
 133 /** Sets the ith bit of a bitmap to new_value.
 134     No sanity checking. Be careful.
 135     @param a - pointer to the bitmap
 136     @param i - the bit position to interrogate
 137     @param new_value - new value for the bit
 138     @returns the old value of the bit
 139 */
 140 always_inline uword
 141 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
 142 {
 143   uword i0 = i / BITS (a[0]);
 144   uword i1 = i % BITS (a[0]);
 145   uword bit = (uword) 1 << i1;
 146   uword ai, old_value;
 147
 148   /* Removed ASSERT since uword * a may not be a vector. */
 149   /* ASSERT (i0 < vec_len (a)); */
 150
 151   ai = a[i0];
 152   old_value = (ai & bit) != 0;
 153   ai &= ~bit;
 154   ai |= ((uword) (new_value != 0)) << i1;
 155   a[i0] = ai;
 156   return old_value;
 157 }
 158
 159 /** Sets the ith bit of a bitmap to new_value
 160     Removes trailing zeros from the bitmap
 161     @param ai - pointer to the bitmap
 162     @param i - the bit position to interrogate
 163     @param value - new value for the bit
 164     @returns the old value of the bit
 165 */
 166 always_inline uword *
 167 clib_bitmap_set (uword * ai, uword i, uword value)
 168 {
 169   uword i0 = i / BITS (ai[0]);
 170   uword i1 = i % BITS (ai[0]);
 171   uword a;
 172
 173   /* Check for writing a zero to beyond end of bitmap. */
 174   if (value == 0 && i0 >= vec_len (ai))
 175     return ai;                  /* Implied trailing zeros. */
 176
 177   clib_bitmap_vec_validate (ai, i0);
 178
 179   a = ai[i0];
 180   a &= ~((uword) 1 << i1);
 181   a |= ((uword) (value != 0)) << i1;
 182   ai[i0] = a;
 183
 184   /* If bits have been cleared, test for zero. */
 185   if (a == 0)
 186     ai = _clib_bitmap_remove_trailing_zeros (ai);
 187
 188   return ai;
 189 }
 190
 191 /** Gets the ith bit value from a bitmap
 192     @param ai - pointer to the bitmap
 193     @param i - the bit position to interrogate
 194     @returns the indicated bit value
 195 */
 196 always_inline uword
 197 clib_bitmap_get (uword * ai, uword i)
 198 {
 199   uword i0 = i / BITS (ai[0]);
 200   uword i1 = i % BITS (ai[0]);
 201   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
 202 }
 203
 204 /** Gets the ith bit value from a bitmap
 205     Does not sanity-check the bit position. Be careful.
 206     @param ai - pointer to the bitmap
 207     @param i - the bit position to interrogate
 208     @returns the indicated bit value, or garbage if the bit position is
 209     out of range.
 210 */
 211 always_inline uword
 212 clib_bitmap_get_no_check (uword * ai, uword i)
 213 {
 214   uword i0 = i / BITS (ai[0]);
 215   uword i1 = i % BITS (ai[0]);
 216   return 0 != ((ai[i0] >> i1) & 1);
 217 }
 218
 219 always_inline uword
 220 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 221 {
 222   uword i0 = i / BITS (ai[0]);
 223   uword i1 = i % BITS (ai[0]);
 224   ASSERT (i1 + n_bits <= BITS (uword));
 225   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
 226 }
 227
 228 /** Gets the ith through ith + n_bits bit values from a bitmap
 229     @param bitmap - pointer to the bitmap
 230     @param i - the first bit position to retrieve
 231     @param n_bits - the number of bit positions to retrieve
 232     @returns the indicated range of bits
 233 */
 234 always_inline uword
 235 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 236 {
 237   uword i0, i1, result;
 238   uword l = vec_len (bitmap);
 239
 240   ASSERT (n_bits <= BITS (result));
 241
 242   i0 = i / BITS (bitmap[0]);
 243   i1 = i % BITS (bitmap[0]);
 244
 245   /* Check first word. */
 246   result = 0;
 247   if (i0 < l)
 248     {
 249       result |= (bitmap[i0] >> i1);
 250       if (n_bits < BITS (bitmap[0]))
 251         result &= (((uword) 1 << n_bits) - 1);
 252     }
 253
 254   /* Check for overlap into next word. */
 255   i0++;
 256   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 257     {
 258       n_bits -= BITS (bitmap[0]) - i1;
 259       result |=
 260         (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 261     }
 262
 263   return result;
 264 }
 265
 266 /** sets the ith through ith + n_bits bits in a bitmap
 267     @param bitmap - pointer to the bitmap
 268     @param i - the first bit position to retrieve
 269     @param value - the values to set
 270     @param n_bits - the number of bit positions to set
 271     @returns a pointer to the updated bitmap, which may expand and move
 272 */
 273
 274 always_inline uword *
 275 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 276 {
 277   uword i0, i1, l, t, m;
 278
 279   ASSERT (n_bits <= BITS (value));
 280
 281   i0 = i / BITS (bitmap[0]);
 282   i1 = i % BITS (bitmap[0]);
 283
 284   /* Allocate bitmap. */
 285   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 286   l = vec_len (bitmap);
 287
 288   m = ~0;
 289   if (n_bits < BITS (value))
 290     m = (((uword) 1 << n_bits) - 1);
 291   value &= m;
 292
 293   /* Insert into first word. */
 294   t = bitmap[i0];
 295   t &= ~(m << i1);
 296   t |= value << i1;
 297   bitmap[i0] = t;
 298
 299   /* Insert into second word. */
 300   i0++;
 301   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 302     {
 303       t = BITS (bitmap[0]) - i1;
 304       value >>= t;
 305       n_bits -= t;
 306       t = bitmap[i0];
 307       m = ((uword) 1 << n_bits) - 1;
 308       t &= ~m;
 309       t |= value;
 310       bitmap[i0] = t;
 311     }
 312
 313   return bitmap;
 314 }
 315
 316 always_inline uword *
 317 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 318 {
 319   uword a0, a1, b0;
 320   uword i_end, mask;
 321
 322   a0 = i / BITS (bitmap[0]);
 323   a1 = i % BITS (bitmap[0]);
 324
 325   i_end = i + n_bits;
 326   b0 = i_end / BITS (bitmap[0]);
 327
 328   clib_bitmap_vec_validate (bitmap, b0);
 329
 330   /* First word. */
 331   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 332   mask <<= a1;
 333
 334   if (value)
 335     bitmap[a0] |= mask;
 336   else
 337     bitmap[a0] &= ~mask;
 338
 339   for (a0++; a0 < b0; a0++)
 340     bitmap[a0] = value ? ~0 : 0;
 341
 342   if (a0 == b0)
 343     {
 344       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 345       mask = pow2_mask (n_bits_left);
 346       if (value)
 347         bitmap[a0] |= mask;
 348       else
 349         bitmap[a0] &= ~mask;
 350     }
 351
 352   return bitmap;
 353 }
 354
 355 /** Macro to iterate across set bits in a bitmap
 356
 357     @param i - the current set bit
 358     @param ai - the bitmap
 359     @param body - the expression to evaluate for each set bit
 360 */
 361 #define clib_bitmap_foreach(i,ai)                                       \
 362   if (ai)                                                               \
 363     for (i = clib_bitmap_first_set (ai);                                \
 364          i != ~0;                                                       \
 365          i = clib_bitmap_next_set (ai, i + 1))
 366
 367 #define clib_bitmap_foreach_old(i,ai,body)                              \
 368 do {                                                                    \
 369   uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set;      \
 370   __bitmap_len = vec_len ((ai));                                        \
 371   for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++)         \
 372     {                                                                   \
 373       __bitmap_ai = (ai)[__bitmap_i];                                   \
 374       while (__bitmap_ai != 0)                                          \
 375         {                                                               \
 376           __bitmap_first_set = first_set (__bitmap_ai);                 \
 377           (i) = (__bitmap_i * BITS ((ai)[0])                            \
 378                  + min_log2 (__bitmap_first_set));                      \
 379           do { body; } while (0);                                       \
 380           __bitmap_ai ^= __bitmap_first_set;                            \
 381         }                                                               \
 382     }                                                                   \
 383 } while (0)
 384
 385
 386 /** Return the lowest numbered set bit in a bitmap
 387     @param ai - pointer to the bitmap
 388     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 389 */
 390 always_inline uword
 391 clib_bitmap_first_set (uword * ai)
 392 {
 393   uword i = 0;
 394 #if uword_bits == 64
 395 #if defined(CLIB_HAVE_VEC256)
 396   while (i + 7 < vec_len (ai))
 397     {
 398       u64x4 v;
 399       v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
 400       if (!u64x4_is_all_zero (v))
 401         break;
 402       i += 8;
 403     }
 404 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 405   while (i + 3 < vec_len (ai))
 406     {
 407       u64x2 v;
 408       v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
 409       if (!u64x2_is_all_zero (v))
 410         break;
 411       i += 4;
 412     }
 413 #endif
 414 #endif
 415   for (; i < vec_len (ai); i++)
 416     {
 417       uword x = ai[i];
 418       if (x != 0)
 419         return i * BITS (ai[0]) + log2_first_set (x);
 420     }
 421   return ~0;
 422 }
 423
 424 /** Return the higest numbered set bit in a bitmap
 425     @param ai - pointer to the bitmap
 426     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 427 */
 428 always_inline uword
 429 clib_bitmap_last_set (uword * ai)
 430 {
 431   uword i;
 432
 433   for (i = vec_len (ai); i > 0; i--)
 434     {
 435       uword x = ai[i - 1];
 436       if (x != 0)
 437         {
 438           uword first_bit;
 439           first_bit = count_leading_zeros (x);
 440           return (i) * BITS (ai[0]) - first_bit - 1;
 441         }
 442     }
 443   return ~0;
 444 }
 445
 446 /** Return the lowest numbered clear bit in a bitmap
 447     @param ai - pointer to the bitmap
 448     @returns lowest numbered clear bit
 449 */
 450 always_inline uword
 451 clib_bitmap_first_clear (uword * ai)
 452 {
 453   uword i;
 454   for (i = 0; i < vec_len (ai); i++)
 455     {
 456       uword x = ~ai[i];
 457       if (x != 0)
 458         return i * BITS (ai[0]) + log2_first_set (x);
 459     }
 460   return i * BITS (ai[0]);
 461 }
 462
 463 /** Return the number of set bits in a bitmap
 464     @param ai - pointer to the bitmap
 465     @returns the number of set bits in the bitmap
 466 */
 467 always_inline uword
 468 clib_bitmap_count_set_bits (uword * ai)
 469 {
 470   uword i;
 471   uword n_set = 0;
 472   for (i = 0; i < vec_len (ai); i++)
 473     n_set += count_set_bits (ai[i]);
 474   return n_set;
 475 }
 476
 477 /** Logical operator across two bitmaps
 478
 479     @param ai - pointer to the destination bitmap
 480     @param bi - pointer to the source bitmap
 481     @returns ai = ai and bi. ai is modified, bi is not modified
 482 */
 483 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
 484
 485 /** Logical operator across two bitmaps
 486
 487     @param ai - pointer to the destination bitmap
 488     @param bi - pointer to the source bitmap
 489     @returns ai = ai & ~bi. ai is modified, bi is not modified
 490 */
 491 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
 492
 493 /** Logical operator across two bitmaps
 494
 495     @param ai - pointer to the destination bitmap
 496     @param bi - pointer to the source bitmap
 497     @returns ai = ai & ~bi. ai is modified, bi is not modified
 498 */
 499 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 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 or bi. ai is modified, bi is not modified
 505 */
 506 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 507
 508 /** Logical operator across two bitmaps
 509
 510     @param ai - pointer to the destination bitmap
 511     @param bi - pointer to the source bitmap
 512     @returns ai = ai xor bi. ai is modified, bi is not modified
 513 */
 514 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
 515
 516 /* ALU function definition macro for functions taking two bitmaps. */
 517 #define _(name, body, check_zero)                               \
 518 always_inline uword *                                           \
 519 clib_bitmap_##name (uword * ai, uword * bi)                     \
 520 {                                                               \
 521   uword i, a, b, bi_len, n_trailing_zeros;                      \
 522                                                                 \
 523   n_trailing_zeros = 0;                                         \
 524   bi_len = vec_len (bi);                                        \
 525   if (bi_len > 0)                                               \
 526     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 527   for (i = 0; i < vec_len (ai); i++)                            \
 528     {                                                           \
 529       a = ai[i];                                                \
 530       b = i < bi_len ? bi[i] : 0;                               \
 531       do { body; } while (0);                                   \
 532       ai[i] = a;                                                \
 533       if (check_zero)                                           \
 534         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 535     }                                                           \
 536   if (check_zero)                                               \
 537     _vec_len (ai) -= n_trailing_zeros;                          \
 538   return ai;                                                    \
 539 }
 540
 541 /* ALU functions: */
 542 /* *INDENT-OFF* */
 543 _(and, a = a & b, 1)
 544 _(andnot, a = a & ~b, 1)
 545 _(or, a = a | b, 0)
 546 _(xor, a = a ^ b, 1)
 547 /* *INDENT-ON* */
 548 #undef _
 549 /** Logical operator across two bitmaps which duplicates the first bitmap
 550
 551     @param ai - pointer to the destination bitmap
 552     @param bi - pointer to the source bitmap
 553     @returns aiDup = ai and bi. Neither ai nor bi are modified
 554 */
 555 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
 556
 557 /** Logical operator across two bitmaps which duplicates the first bitmap
 558
 559     @param ai - pointer to the destination bitmap
 560     @param bi - pointer to the source bitmap
 561     @returns aiDup = ai & ~bi. Neither ai nor bi are modified
 562 */
 563 always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
 564
 565 /** Logical operator across two bitmaps which duplicates the first bitmap
 566
 567     @param ai - pointer to the destination bitmap
 568     @param bi - pointer to the source bitmap
 569     @returns aiDup = ai or bi. Neither ai nor bi are modified
 570 */
 571 always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
 572
 573 /** Logical operator across two bitmaps which duplicates the first bitmap
 574
 575     @param ai - pointer to the destination bitmap
 576     @param bi - pointer to the source bitmap
 577     @returns aiDup = ai xor bi. Neither ai nor bi are modified
 578 */
 579 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
 580
 581 #define _(name)                                         \
 582   always_inline uword *                                 \
 583   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 584 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 585
 586 /* *INDENT-OFF* */
 587 _(and);
 588 _(andnot);
 589 _(or);
 590 _(xor);
 591 /* *INDENT-ON* */
 592 #undef _
 593
 594 /* ALU function definition macro for functions taking one bitmap and an
 595  * immediate. */
 596 #define _(name, body, check_zero)                       \
 597 always_inline uword *                                   \
 598 clib_bitmap_##name (uword * ai, uword i)                \
 599 {                                                       \
 600   uword i0 = i / BITS (ai[0]);                          \
 601   uword i1 = i % BITS (ai[0]);                          \
 602   uword a, b;                                           \
 603   clib_bitmap_vec_validate (ai, i0);                    \
 604   a = ai[i0];                                           \
 605   b = (uword) 1 << i1;                                  \
 606   do { body; } while (0);                               \
 607   ai[i0] = a;                                           \
 608   if (check_zero && a == 0)                             \
 609     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 610   return ai;                                            \
 611 }
 612
 613 /* ALU functions immediate: */
 614 /* *INDENT-OFF* */
 615 _(andi, a = a & b, 1)
 616 _(andnoti, a = a & ~b, 1)
 617 _(ori, a = a | b, 0)
 618 _(xori, a = a ^ b, 1)
 619 /* *INDENT-ON* */
 620 #undef _
 621
 622 /* ALU function definition macro for functions taking one bitmap and an
 623  * immediate. No tail trimming */
 624 #define _(name, body)                                   \
 625 always_inline uword *                                   \
 626 clib_bitmap_##name##_notrim (uword * ai, uword i)       \
 627 {                                                       \
 628   uword i0 = i / BITS (ai[0]);                          \
 629   uword i1 = i % BITS (ai[0]);                          \
 630   uword a, b;                                           \
 631   clib_bitmap_vec_validate (ai, i0);                    \
 632   a = ai[i0];                                           \
 633   b = (uword) 1 << i1;                                  \
 634   do { body; } while (0);                               \
 635   ai[i0] = a;                                           \
 636   return ai;                                            \
 637 }
 638
 639 /* ALU functions immediate: */
 640 /* *INDENT-OFF* */
 641 _(andi, a = a & b)
 642 _(andnoti, a = a & ~b)
 643 _(ori, a = a | b)
 644 _(xori, a = a ^ b)
 645 #undef _
 646 /* *INDENT-ON* */
 647
 648 /** Return a random bitmap of the requested length
 649     @param ai - pointer to the destination bitmap
 650     @param n_bits - number of bits to allocate
 651     @param [in,out] seed - pointer to the random number seed
 652     @returns a reasonably random bitmap based. See random.h.
 653 */
 654 always_inline uword *
 655 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 656 {
 657   vec_reset_length (ai);
 658
 659   if (n_bits > 0)
 660     {
 661       uword i = n_bits - 1;
 662       uword i0, i1;
 663       uword log2_rand_max;
 664
 665       log2_rand_max = min_log2 (random_u32_max ());
 666
 667       i0 = i / BITS (ai[0]);
 668       i1 = i % BITS (ai[0]);
 669
 670       clib_bitmap_vec_validate (ai, i0);
 671       for (i = 0; i <= i0; i++)
 672         {
 673           uword n;
 674           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 675             ai[i] |= random_u32 (seed) << n;
 676         }
 677       if (i1 + 1 < BITS (ai[0]))
 678         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 679     }
 680   return ai;
 681 }
 682
 683 /** Return the next set bit in a bitmap starting at bit i
 684     @param ai - pointer to the bitmap
 685     @param i - first bit position to test
 686     @returns first set bit position at or after i,
 687     ~0 if no further set bits are found
 688 */
 689 always_inline uword
 690 clib_bitmap_next_set (uword * ai, uword i)
 691 {
 692   uword i0 = i / BITS (ai[0]);
 693   uword i1 = i % BITS (ai[0]);
 694   uword t;
 695
 696   if (i0 < vec_len (ai))
 697     {
 698       t = (ai[i0] >> i1) << i1;
 699       if (t)
 700         return log2_first_set (t) + i0 * BITS (ai[0]);
 701
 702       for (i0++; i0 < vec_len (ai); i0++)
 703         {
 704           t = ai[i0];
 705           if (t)
 706             return log2_first_set (t) + i0 * BITS (ai[0]);
 707         }
 708     }
 709
 710   return ~0;
 711 }
 712
 713 /** Return the next clear bit in a bitmap starting at bit i
 714     @param ai - pointer to the bitmap
 715     @param i - first bit position to test
 716     @returns first clear bit position at or after i
 717 */
 718 always_inline uword
 719 clib_bitmap_next_clear (uword * ai, uword i)
 720 {
 721   uword i0 = i / BITS (ai[0]);
 722   uword i1 = i % BITS (ai[0]);
 723   uword t;
 724
 725   if (i0 < vec_len (ai))
 726     {
 727       t = (~ai[i0] >> i1) << i1;
 728       if (t)
 729         return log2_first_set (t) + i0 * BITS (ai[0]);
 730
 731       for (i0++; i0 < vec_len (ai); i0++)
 732         {
 733           t = ~ai[i0];
 734           if (t)
 735             return log2_first_set (t) + i0 * BITS (ai[0]);
 736         }
 737
 738       /* no clear bit left in bitmap, return bit just beyond bitmap */
 739       return (i0 * BITS (ai[0])) + 1;
 740     }
 741   return i;
 742 }
 743
 744 /** unformat an any sized hexadecimal bitmask into a bitmap
 745
 746     uword * bitmap;
 747     rv = unformat ("%U", unformat_bitmap_mask, &bitmap);
 748
 749     Standard unformat_function_t arguments
 750
 751     @param input - pointer an unformat_input_t
 752     @param va - varargs list comprising a single uword **
 753     @returns 1 on success, 0 on failure
 754 */
 755 static inline uword
 756 unformat_bitmap_mask (unformat_input_t * input, va_list * va)
 757 {
 758   u8 *v = 0;                    /* hexadecimal vector */
 759   uword **bitmap_return = va_arg (*va, uword **);
 760   uword *bitmap = 0;
 761
 762   if (unformat (input, "%U", unformat_hex_string, &v))
 763     {
 764       int i, s = vec_len (v) - 1;       /* 's' for significance or shift */
 765
 766       /* v[0] holds the most significant byte */
 767       for (i = 0; s >= 0; i++, s--)
 768         bitmap = clib_bitmap_set_multiple (bitmap,
 769                                            s * BITS (v[i]), v[i],
 770                                            BITS (v[i]));
 771
 772       vec_free (v);
 773       *bitmap_return = bitmap;
 774       return 1;
 775     }
 776
 777   return 0;
 778 }
 779
 780 /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
 781
 782     uword * bitmap;
 783     rv = unformat ("%U", unformat_bitmap_list, &bitmap);
 784
 785     Standard unformat_function_t arguments
 786
 787     @param input - pointer an unformat_input_t
 788     @param va - varargs list comprising a single uword **
 789     @returns 1 on success, 0 on failure
 790 */
 791 static inline uword
 792 unformat_bitmap_list (unformat_input_t * input, va_list * va)
 793 {
 794   uword **bitmap_return = va_arg (*va, uword **);
 795   uword *bitmap = 0;
 796
 797   u32 a, b;
 798
 799   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 800     {
 801       int i;
 802       if (unformat (input, "%u-%u,", &a, &b))
 803         ;
 804       else if (unformat (input, "%u,", &a))
 805         b = a;
 806       else if (unformat (input, "%u-%u", &a, &b))
 807         ;
 808       else if (unformat (input, "%u", &a))
 809         b = a;
 810       else if (bitmap)
 811         {
 812           unformat_put_input (input);
 813           break;
 814         }
 815       else
 816         goto error;
 817
 818       if (b < a)
 819         goto error;
 820
 821       for (i = a; i <= b; i++)
 822         bitmap = clib_bitmap_set (bitmap, i, 1);
 823     }
 824   *bitmap_return = bitmap;
 825   return 1;
 826 error:
 827   clib_bitmap_free (bitmap);
 828   return 0;
 829 }
 830
 831 /** Format a bitmap as a string of hex bytes
 832
 833     uword * bitmap;
 834     s = format ("%U", format_bitmap_hex, bitmap);
 835
 836     Standard format_function_t arguments
 837
 838     @param s - string under construction
 839     @param args - varargs list comprising a single uword *
 840     @returns string under construction
 841 */
 842 static inline u8 *
 843 format_bitmap_hex (u8 * s, va_list * args)
 844 {
 845   uword *bitmap = va_arg (*args, uword *);
 846   int i, is_trailing_zero = 1;
 847
 848   if (!bitmap)
 849     return format (s, "0");
 850
 851   i = vec_bytes (bitmap) * 2;
 852
 853   while (i > 0)
 854     {
 855       u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
 856
 857       if (x && is_trailing_zero)
 858         is_trailing_zero = 0;
 859
 860       if (x || !is_trailing_zero)
 861         s = format (s, "%x", x);
 862     }
 863   return s;
 864 }
 865 #endif /* included_clib_bitmap_h */
 866
 867 /*
 868  * fd.io coding-style-patch-verification: ON
 869  *
 870  * Local Variables:
 871  * eval: (c-set-style "gnu")
 872  * End:
 873  */