vppinfra/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 /* 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 typedef uword clib_bitmap_t;
  49
  50 /* Returns 1 if the entire bitmap is zero, 0 otherwise */
  51 always_inline uword
  52 clib_bitmap_is_zero (uword * ai)
  53 {
  54   uword i;
  55   for (i = 0; i < vec_len (ai); i++)
  56     if (ai[i] != 0)
  57       return 0;
  58   return 1;
  59 }
  60
  61 /* Returns 1 if two bitmaps are equal, 0 otherwise */
  62 always_inline uword
  63 clib_bitmap_is_equal (uword * a, uword * b)
  64 {
  65   uword i;
  66   if (vec_len (a) != vec_len (b))
  67     return 0;
  68   for (i = 0; i < vec_len (a); i++)
  69     if (a[i] != b[i])
  70       return 0;
  71   return 1;
  72 }
  73
  74 /* Duplicate a bitmap */
  75 #define clib_bitmap_dup(v) vec_dup(v)
  76
  77 /* Free a bitmap */
  78 #define clib_bitmap_free(v) vec_free(v)
  79
  80 /* Returns the number of bytes in a bitmap */
  81 #define clib_bitmap_bytes(v) vec_bytes(v)
  82
  83 /* Clear a bitmap */
  84 #define clib_bitmap_zero(v) vec_zero(v)
  85
  86 /* Allocate bitmap with given number of bits. */
  87 #define clib_bitmap_alloc(v,n_bits) \
  88   v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
  89
  90 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
  91
  92 /* Make sure that a bitmap is at least n_bits in size */
  93 #define clib_bitmap_validate(v,n_bits) \
  94   clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
  95
  96 /* low-level routine to remove trailing zeros from a bitmap */
  97 always_inline uword *
  98 _clib_bitmap_remove_trailing_zeros (uword * a)
  99 {
 100   word i;
 101   if (a)
 102     {
 103       for (i = _vec_len (a) - 1; i >= 0; i--)
 104         if (a[i] != 0)
 105           break;
 106       _vec_len (a) = i + 1;
 107     }
 108   return a;
 109 }
 110
 111 /* Sets the ith bit of a bitmap to new_value.  Returns old value.
 112    No sanity checking. Be careful. */
 113 always_inline uword
 114 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
 115 {
 116   uword i0 = i / BITS (a[0]);
 117   uword i1 = i % BITS (a[0]);
 118   uword bit = (uword) 1 << i1;
 119   uword ai, old_value;
 120
 121   /* Removed ASSERT since uword * a may not be a vector. */
 122   /* ASSERT (i0 < vec_len (a)); */
 123
 124   ai = a[i0];
 125   old_value = (ai & bit) != 0;
 126   ai &= ~ bit;
 127   ai |= ((uword) (new_value != 0)) << i1;
 128   a[i0] = ai;
 129   return old_value;
 130 }
 131
 132 /* Set bit I to value (either non-zero or zero). */
 133 always_inline uword *
 134 clib_bitmap_set (uword * ai, uword i, uword value)
 135 {
 136   uword i0 = i / BITS (ai[0]);
 137   uword i1 = i % BITS (ai[0]);
 138   uword a;
 139
 140   /* Check for writing a zero to beyond end of bitmap. */
 141   if (value == 0 && i0 >= vec_len (ai))
 142     return ai;                  /* Implied trailing zeros. */
 143
 144   clib_bitmap_vec_validate (ai, i0);
 145
 146   a = ai[i0];
 147   a &= ~((uword) 1 << i1);
 148   a |= ((uword) (value != 0)) << i1;
 149   ai[i0] = a;
 150
 151   /* If bits have been cleared, test for zero. */
 152   if (a == 0)
 153     ai = _clib_bitmap_remove_trailing_zeros (ai);
 154
 155   return ai;
 156 }
 157
 158 /* Fetch bit I. */
 159 always_inline uword
 160 clib_bitmap_get (uword * ai, uword i)
 161 {
 162   uword i0 = i / BITS (ai[0]);
 163   uword i1 = i % BITS (ai[0]);
 164   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
 165 }
 166
 167 /* Fetch bit I.
 168
 169     No sanity checking. Be careful.
 170 */
 171 always_inline uword
 172 clib_bitmap_get_no_check (uword * ai, uword i)
 173 {
 174   uword i0 = i / BITS (ai[0]);
 175   uword i1 = i % BITS (ai[0]);
 176   return 0 != ((ai[i0] >> i1) & 1);
 177 }
 178
 179 /* I through I + N_BITS.
 180
 181     No sanity checking. Be careful.
 182 */
 183 always_inline uword
 184 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 185 {
 186   uword i0 = i / BITS (ai[0]);
 187   uword i1 = i % BITS (ai[0]);
 188   ASSERT (i1 + n_bits <= BITS (uword));
 189   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
 190 }
 191
 192 /* Fetch bits I through I + N_BITS. */
 193 always_inline uword
 194 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 195 {
 196   uword i0, i1, result;
 197   uword l = vec_len (bitmap);
 198
 199   ASSERT (n_bits >= 0 && n_bits <= BITS (result));
 200
 201   i0 = i / BITS (bitmap[0]);
 202   i1 = i % BITS (bitmap[0]);
 203
 204   /* Check first word. */
 205   result = 0;
 206   if (i0 < l)
 207     {
 208       result |= (bitmap[i0] >> i1);
 209       if (n_bits < BITS (bitmap[0]))
 210         result &= (((uword) 1 << n_bits) - 1);
 211     }
 212
 213   /* Check for overlap into next word. */
 214   i0++;
 215   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 216     {
 217       n_bits -= BITS (bitmap[0]) - i1;
 218       result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 219     }
 220
 221   return result;
 222 }
 223
 224 /* Set bits I through I + N_BITS to given value.
 225
 226     New bitmap will be returned. */
 227 always_inline uword *
 228 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 229 {
 230   uword i0, i1, l, t, m;
 231
 232   ASSERT (n_bits >= 0 && n_bits <= BITS (value));
 233
 234   i0 = i / BITS (bitmap[0]);
 235   i1 = i % BITS (bitmap[0]);
 236
 237   /* Allocate bitmap. */
 238   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 239   l = vec_len (bitmap);
 240
 241   m = ~0;
 242   if (n_bits < BITS (value))
 243     m = (((uword) 1 << n_bits) - 1);
 244   value &= m;
 245
 246   /* Insert into first word. */
 247   t = bitmap[i0];
 248   t &= ~(m << i1);
 249   t |= value << i1;
 250   bitmap[i0] = t;
 251
 252   /* Insert into second word. */
 253   i0++;
 254   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 255     {
 256       t = BITS (bitmap[0]) - i1;
 257       value >>= t;
 258       n_bits -= t;
 259       t = bitmap[i0];
 260       m = ((uword) 1 << n_bits) - 1;
 261       t &= ~m;
 262       t |= value;
 263       bitmap[i0] = t;
 264     }
 265
 266   return bitmap;
 267 }
 268
 269 /* For a multi-word region set all bits to given value. */
 270 always_inline uword *
 271 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 272 {
 273   uword a0, a1, b0;
 274   uword i_end, mask;
 275
 276   a0 = i / BITS (bitmap[0]);
 277   a1 = i % BITS (bitmap[0]);
 278
 279   i_end = i + n_bits;
 280   b0 = i_end / BITS (bitmap[0]);
 281
 282   clib_bitmap_vec_validate (bitmap, b0);
 283
 284   /* First word. */
 285   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 286   mask <<= a1;
 287
 288   if (value)
 289     bitmap[a0] |= mask;
 290   else
 291     bitmap[a0] &= ~mask;
 292
 293   for (a0++; a0 < b0; a0++)
 294     bitmap[a0] = value ? ~0 : 0;
 295
 296   if (a0 == b0)
 297     {
 298       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 299       mask = pow2_mask (n_bits_left);
 300       if (value)
 301         bitmap[a0] |= mask;
 302       else
 303         bitmap[a0] &= ~mask;
 304     }
 305
 306   return bitmap;
 307 }
 308
 309 /* Iterate through set bits. */
 310 #define clib_bitmap_foreach(i,ai,body)                                  \
 311 do {                                                                    \
 312   uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set;      \
 313   __bitmap_len = vec_len ((ai));                                        \
 314   for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++)         \
 315     {                                                                   \
 316       __bitmap_ai = (ai)[__bitmap_i];                                   \
 317       while (__bitmap_ai != 0)                                          \
 318         {                                                               \
 319           __bitmap_first_set = first_set (__bitmap_ai);                 \
 320           (i) = (__bitmap_i * BITS ((ai)[0])                            \
 321                  + min_log2 (__bitmap_first_set));                      \
 322           do { body; } while (0);                                       \
 323           __bitmap_ai ^= __bitmap_first_set;                            \
 324         }                                                               \
 325     }                                                                   \
 326 } while (0)
 327
 328 /* Return lowest numbered set bit in bitmap.
 329
 330     Return infinity (~0) if bitmap is zero. */
 331 always_inline uword clib_bitmap_first_set (uword * ai)
 332 {
 333   uword i;
 334   for (i = 0; i < vec_len (ai); i++)
 335     {
 336       uword x = ai[i];
 337       if (x != 0)
 338         return i * BITS (ai[0]) + log2_first_set (x);
 339     }
 340   return ~0;
 341 }
 342
 343 /* Return highest numbered set bit in bitmap.
 344
 345     Return infinity (~0) if bitmap is zero. */
 346 always_inline uword clib_bitmap_last_set (uword * ai)
 347 {
 348   uword i;
 349
 350   for (i = vec_len (ai) - 1; i >= 0 ; i--)
 351     {
 352       uword x = ai[i];
 353       if (x != 0)
 354         {
 355           uword first_bit;
 356           count_leading_zeros (first_bit, x);
 357           return (i + 1) * BITS (ai[0]) - first_bit - 1;
 358         }
 359     }
 360   return ~0;
 361 }
 362
 363 /* Return lowest numbered clear bit in bitmap. */
 364 always_inline uword
 365 clib_bitmap_first_clear (uword * ai)
 366 {
 367   uword i;
 368   for (i = 0; i < vec_len (ai); i++)
 369     {
 370       uword x = ~ai[i];
 371       if (x != 0)
 372         return i * BITS (ai[0]) + log2_first_set (x);
 373     }
 374   return i * BITS (ai[0]);
 375 }
 376
 377 /* Count number of set bits in bitmap. */
 378 always_inline uword
 379 clib_bitmap_count_set_bits (uword * ai)
 380 {
 381   uword i;
 382   uword n_set = 0;
 383   for (i = 0; i < vec_len (ai); i++)
 384     n_set += count_set_bits (ai[i]);
 385   return n_set;
 386 }
 387
 388 /* ALU function definition macro for functions taking two bitmaps. */
 389 #define _(name, body, check_zero)                               \
 390 always_inline uword *                                           \
 391 clib_bitmap_##name (uword * ai, uword * bi)                     \
 392 {                                                               \
 393   uword i, a, b, bi_len, n_trailing_zeros;                      \
 394                                                                 \
 395   n_trailing_zeros = 0;                                         \
 396   bi_len = vec_len (bi);                                        \
 397   if (bi_len > 0)                                               \
 398     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 399   for (i = 0; i < vec_len (ai); i++)                            \
 400     {                                                           \
 401       a = ai[i];                                                \
 402       b = i < bi_len ? bi[i] : 0;                               \
 403       do { body; } while (0);                                   \
 404       ai[i] = a;                                                \
 405       if (check_zero)                                           \
 406         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 407     }                                                           \
 408   if (check_zero)                                               \
 409     _vec_len (ai) -= n_trailing_zeros;                          \
 410   return ai;                                                    \
 411 }
 412
 413 /* ALU functions: */
 414 _ (and, a = a & b, 1)
 415 _ (andnot, a = a &~ b, 1)
 416 _ (or,  a = a | b, 0)
 417 _ (xor, a = a ^ b, 1)
 418 #undef _
 419
 420 /* Define functions which duplicate first argument.
 421    (Normal functions over-write first argument.) */
 422 #define _(name)                                         \
 423   always_inline uword *                                 \
 424   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 425 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 426
 427 _ (and);
 428 _ (andnot);
 429 _ (or);
 430 _ (xor);
 431
 432 #undef _
 433
 434 /* ALU function definition macro for functions taking one bitmap and an immediate. */
 435 #define _(name, body, check_zero)                       \
 436 always_inline uword *                                   \
 437 clib_bitmap_##name (uword * ai, uword i)                \
 438 {                                                       \
 439   uword i0 = i / BITS (ai[0]);                          \
 440   uword i1 = i % BITS (ai[0]);                          \
 441   uword a, b;                                           \
 442   clib_bitmap_vec_validate (ai, i0);                    \
 443   a = ai[i0];                                           \
 444   b = (uword) 1 << i1;                                  \
 445   do { body; } while (0);                               \
 446   ai[i0] = a;                                           \
 447   if (check_zero && a == 0)                             \
 448     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 449   return ai;                                            \
 450 }
 451
 452 /* ALU functions immediate: */
 453 _ (andi, a = a & b, 1)
 454 _ (andnoti, a = a &~ b, 1)
 455 _ (ori, a = a | b, 0)
 456 _ (xori, a = a ^ b, 1)
 457
 458 #undef _
 459
 460 /* Returns random bitmap of given length. */
 461 always_inline uword *
 462 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 463 {
 464   vec_reset_length (ai);
 465
 466   if (n_bits > 0)
 467     {
 468       uword i = n_bits - 1;
 469       uword i0, i1;
 470       uword log2_rand_max;
 471
 472       log2_rand_max = min_log2 (random_u32_max ());
 473
 474       i0 = i / BITS (ai[0]);
 475       i1 = i % BITS (ai[0]);
 476
 477       clib_bitmap_vec_validate (ai, i0);
 478       for (i = 0; i <= i0; i++)
 479         {
 480           uword n;
 481           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 482             ai[i] |= random_u32 (seed) << n;
 483         }
 484       if (i1 + 1 < BITS (ai[0]))
 485         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 486     }
 487   return ai;
 488 }
 489
 490 /* Returns next set bit starting at bit i (~0 if not found). */
 491 always_inline uword
 492 clib_bitmap_next_set (uword * ai, uword i)
 493 {
 494   uword i0 = i / BITS (ai[0]);
 495   uword i1 = i % BITS (ai[0]);
 496   uword t;
 497
 498   if (i0 < vec_len (ai))
 499     {
 500       t = (ai[i0] >> i1) << i1;
 501       if (t)
 502         return log2_first_set (t) + i0 * BITS (ai[0]);
 503
 504       for (i0++; i0 < vec_len (ai); i0++)
 505         {
 506           t = ai[i0];
 507           if (t)
 508             return log2_first_set (t) + i0 * BITS (ai[0]);
 509         }
 510     }
 511
 512   return ~0;
 513 }
 514
 515 /* Returns next clear bit at position >= i */
 516 always_inline uword
 517 clib_bitmap_next_clear (uword * ai, uword i)
 518 {
 519   uword i0 = i / BITS (ai[0]);
 520   uword i1 = i % BITS (ai[0]);
 521   uword t;
 522
 523   if (i0 < vec_len (ai))
 524     {
 525       t = (~ai[i0] >> i1) << i1;
 526       if (t)
 527         return log2_first_set (t) + i0 * BITS (ai[0]);
 528
 529       for (i0++; i0 < vec_len (ai); i0++)
 530         {
 531           t = ~ai[i0];
 532           if (t)
 533             return log2_first_set (t) + i0 * BITS (ai[0]);
 534         }
 535     }
 536   return i;
 537 }
 538
 539 /* unformat list of bits into bitmap (eg "0-3,5-7,11" ) */
 540 static inline uword
 541 unformat_bitmap_list(unformat_input_t * input, va_list * va)
 542 {
 543   uword ** bitmap_return = va_arg (* va, uword **);
 544   uword * bitmap = 0;
 545
 546   u32 a,b;
 547
 548   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 549     {
 550       int i;
 551       if (unformat (input, "%u-%u,", &a, &b))
 552         ;
 553       else if (unformat (input, "%u,", &a))
 554         b = a;
 555       else if (unformat (input, "%u-%u", &a, &b))
 556         ;
 557       else if (unformat (input, "%u", &a))
 558         b = a;
 559       else if (bitmap)
 560         {
 561           unformat_put_input(input);
 562           break;
 563         }
 564       else
 565         goto error;
 566
 567       if (b < a)
 568         goto error;
 569
 570       for (i = a; i <= b; i++)
 571         bitmap = clib_bitmap_set(bitmap, i, 1);
 572     }
 573   *bitmap_return = bitmap;
 574   return 1;
 575 error:
 576   clib_bitmap_free(bitmap);
 577   return 0;
 578 }
 579
 580 static inline u8 *
 581 format_bitmap_hex(u8 * s, va_list * args)
 582 {
 583   uword * bitmap = va_arg (*args, uword *);
 584   int i, is_trailing_zero = 1;
 585
 586   if (!bitmap)
 587     return format(s, "0");
 588
 589   i = vec_bytes (bitmap) * 2;
 590
 591   while (i > 0)
 592     {
 593       u8 x = clib_bitmap_get_multiple(bitmap, --i * 4, 4);
 594
 595       if (x && is_trailing_zero)
 596         is_trailing_zero = 0;
 597
 598       if (x || !is_trailing_zero)
 599           s = format(s, "%x", x);
 600     }
 601   return s;
 602 }
 603 #endif /* included_clib_bitmap_h */