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