ipsec: huge anti-replay window support

[vpp.git] / src / vppinfra / bitmap.h

diff --git a/src/vppinfra/bitmap.h b/src/vppinfra/bitmap.h
index af651ef..99d6595 100644 (file)
--- a/src/vppinfra/bitmap.h
+++ b/src/vppinfra/bitmap.h
@@ -45,7 +45,6 @@
 #include <vppinfra/vec.h>
 #include <vppinfra/random.h>
 #include <vppinfra/error.h>
-#include <vppinfra/bitops.h>   /* for count_set_bits */
 
 typedef uword clib_bitmap_t;
 
@@ -143,7 +142,7 @@ _clib_bitmap_remove_trailing_zeros (uword * a)
       for (i = _vec_len (a) - 1; i >= 0; i--)
        if (a[i] != 0)
          break;
-      _vec_len (a) = i + 1;
+      vec_set_len (a, i + 1);
     }
   return a;
 }
@@ -179,7 +178,7 @@ clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
     @param ai - pointer to the bitmap
     @param i - the bit position to interrogate
     @param value - new value for the bit
-    @returns the old value of the bit
+    @returns the (possibly reallocated) bitmap object pointer
 */
 always_inline uword *
 clib_bitmap_set (uword * ai, uword i, uword value)
@@ -206,6 +205,12 @@ clib_bitmap_set (uword * ai, uword i, uword value)
   return ai;
 }
 
+always_inline u8
+clib_bitmap_will_expand (uword *ai, uword i)
+{
+  return (i / BITS (ai[0])) >= vec_max_len (ai);
+}
+
 /** Gets the ith bit value from a bitmap
     @param ai - pointer to the bitmap
     @param i - the bit position to interrogate
@@ -240,7 +245,7 @@ clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
   uword i0 = i / BITS (ai[0]);
   uword i1 = i % BITS (ai[0]);
   ASSERT (i1 + n_bits <= BITS (uword));
-  return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
+  return ((ai[i0] >> i1) & pow2_mask (n_bits));
 }
 
 /** Gets the ith through ith + n_bits bit values from a bitmap
@@ -300,7 +305,7 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
   i1 = i % BITS (bitmap[0]);
 
   /* Allocate bitmap. */
-  clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
+  clib_bitmap_vec_validate (bitmap, (i + n_bits - 1) / BITS (bitmap[0]));
   l = vec_len (bitmap);
 
   m = ~0;
@@ -334,14 +339,15 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 always_inline uword *
 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 {
-  uword a0, a1, b0;
+  uword a0, a1, b0, b1;
   uword i_end, mask;
 
   a0 = i / BITS (bitmap[0]);
   a1 = i % BITS (bitmap[0]);
 
-  i_end = i + n_bits;
+  i_end = i + n_bits - 1;
   b0 = i_end / BITS (bitmap[0]);
+  b1 = i_end % BITS (bitmap[0]);
 
   clib_bitmap_vec_validate (bitmap, b0);
 
@@ -359,8 +365,7 @@ clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 
   if (a0 == b0)
     {
-      word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
-      mask = pow2_mask (n_bits_left);
+      mask = (uword) ~0 >> (BITS (bitmap[0]) - b1 - 1);
       if (value)
        bitmap[a0] |= mask;
       else
@@ -513,29 +518,32 @@ always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
 
 /* ALU function definition macro for functions taking two bitmaps. */
-#define _(name, body, check_zero)                              \
-always_inline uword *                                          \
-clib_bitmap_##name (uword * ai, uword * bi)                    \
-{                                                              \
-  uword i, a, b, bi_len, n_trailing_zeros;                     \
-                                                               \
-  n_trailing_zeros = 0;                                                \
-  bi_len = vec_len (bi);                                       \
-  if (bi_len > 0)                                              \
-    clib_bitmap_vec_validate (ai, bi_len - 1);                 \
-  for (i = 0; i < vec_len (ai); i++)                           \
-    {                                                          \
-      a = ai[i];                                               \
-      b = i < bi_len ? bi[i] : 0;                              \
-      do { body; } while (0);                                  \
-      ai[i] = a;                                               \
-      if (check_zero)                                          \
-       n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
-    }                                                          \
-  if (check_zero)                                              \
-    _vec_len (ai) -= n_trailing_zeros;                         \
-  return ai;                                                   \
-}
+#define _(name, body, check_zero)                                             \
+  always_inline uword *clib_bitmap_##name (uword *ai, uword *bi)              \
+  {                                                                           \
+    uword i, a, b, bi_len, n_trailing_zeros;                                  \
+                                                                              \
+    n_trailing_zeros = 0;                                                     \
+    bi_len = vec_len (bi);                                                    \
+    if (bi_len > 0)                                                           \
+      clib_bitmap_vec_validate (ai, bi_len - 1);                              \
+    for (i = 0; i < vec_len (ai); i++)                                        \
+      {                                                                       \
+       a = ai[i];                                                            \
+       b = i < bi_len ? bi[i] : 0;                                           \
+       do                                                                    \
+         {                                                                   \
+           body;                                                             \
+         }                                                                   \
+       while (0);                                                            \
+       ai[i] = a;                                                            \
+       if (check_zero)                                                       \
+         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);                  \
+      }                                                                       \
+    if (check_zero)                                                           \
+      vec_dec_len (ai, n_trailing_zeros);                                     \
+    return ai;                                                                \
+  }
 
 /* ALU functions: */
 /* *INDENT-OFF* */
@@ -734,8 +742,7 @@ clib_bitmap_next_clear (uword * ai, uword i)
            return log2_first_set (t) + i0 * BITS (ai[0]);
        }
 
-      /* no clear bit left in bitmap, return bit just beyond bitmap */
-      return (i0 * BITS (ai[0])) + 1;
+      return i0 * BITS (ai[0]);
     }
   return i;
 }