X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fbitmap.h;h=92205bfc8e8428bf44ccf0f25e82ebb3bf2cee4f;hb=41a54f6a0b16b36f55461f0ce0a2303081a4fb6c;hp=9e1ae49328556ecf31e7b67ab236aeed18cd9ebb;hpb=7cd468a3d7dee7d6c92f69a0bb7061ae208ec727;p=vpp.git

diff --git a/src/vppinfra/bitmap.h b/src/vppinfra/bitmap.h
index 9e1ae493285..92205bfc8e8 100644
--- a/src/vppinfra/bitmap.h
+++ b/src/vppinfra/bitmap.h
@@ -314,7 +314,7 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 }
 
 always_inline uword *
-clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
+clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 {
   uword a0, a1, b0;
   uword i_end, mask;
@@ -358,24 +358,11 @@ clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
     @param ai - the bitmap
     @param body - the expression to evaluate for each set bit
 */
-#define clib_bitmap_foreach(i,ai,body)					\
-do {									\
-  uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set;	\
-  __bitmap_len = vec_len ((ai));					\
-  for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++)		\
-    {									\
-      __bitmap_ai = (ai)[__bitmap_i];					\
-      while (__bitmap_ai != 0)						\
-	{								\
-	  __bitmap_first_set = first_set (__bitmap_ai);			\
-	  (i) = (__bitmap_i * BITS ((ai)[0])				\
-		 + min_log2 (__bitmap_first_set));			\
-	  do { body; } while (0);					\
-	  __bitmap_ai ^= __bitmap_first_set;				\
-	}								\
-    }									\
-} while (0)
-
+#define clib_bitmap_foreach(i,ai)					\
+  if (ai)								\
+    for (i = clib_bitmap_first_set (ai);				\
+	 i != ~0;							\
+	 i = clib_bitmap_next_set (ai, i + 1))
 
 /** Return the lowest numbered set bit in a bitmap
     @param ai - pointer to the bitmap
@@ -384,8 +371,29 @@ do {									\
 always_inline uword
 clib_bitmap_first_set (uword * ai)
 {
-  uword i;
-  for (i = 0; i < vec_len (ai); i++)
+  uword i = 0;
+#if uword_bits == 64
+#if defined(CLIB_HAVE_VEC256)
+  while (i + 7 < vec_len (ai))
+    {
+      u64x4 v;
+      v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
+      if (!u64x4_is_all_zero (v))
+	break;
+      i += 8;
+    }
+#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  while (i + 3 < vec_len (ai))
+    {
+      u64x2 v;
+      v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
+      if (!u64x2_is_all_zero (v))
+	break;
+      i += 4;
+    }
+#endif
+#endif
+  for (; i < vec_len (ai); i++)
     {
       uword x = ai[i];
       if (x != 0)
@@ -409,7 +417,7 @@ clib_bitmap_last_set (uword * ai)
       if (x != 0)
 	{
 	  uword first_bit;
-	  count_leading_zeros (first_bit, x);
+	  first_bit = count_leading_zeros (x);
 	  return (i) * BITS (ai[0]) - first_bit - 1;
 	}
     }
@@ -512,8 +520,12 @@ clib_bitmap_##name (uword * ai, uword * bi)			\
 }
 
 /* ALU functions: */
+/* *INDENT-OFF* */
 _(and, a = a & b, 1)
-_(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
+_(andnot, a = a & ~b, 1)
+_(or, a = a | b, 0)
+_(xor, a = a ^ b, 1)
+/* *INDENT-ON* */
 #undef _
 /** Logical operator across two bitmaps which duplicates the first bitmap
 
@@ -521,8 +533,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
     @param bi - pointer to the source bitmap
     @returns aiDup = ai and bi. Neither ai nor bi are modified
 */
-     always_inline uword *
-     clib_bitmap_dup_and (uword * ai, uword * bi);
+always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
 
 /** Logical operator across two bitmaps which duplicates the first bitmap
 
@@ -530,8 +541,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
     @param bi - pointer to the source bitmap
     @returns aiDup = ai & ~bi. Neither ai nor bi are modified
 */
-     always_inline uword *
-     clib_bitmap_dup_andnot (uword * ai, uword * bi);
+always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
 
 /** Logical operator across two bitmaps which duplicates the first bitmap
 
@@ -539,8 +549,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
     @param bi - pointer to the source bitmap
     @returns aiDup = ai or bi. Neither ai nor bi are modified
 */
-     always_inline uword *
-     clib_bitmap_dup_or (uword * ai, uword * bi);
+always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
 
 /** Logical operator across two bitmaps which duplicates the first bitmap
 
@@ -548,22 +557,23 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
     @param bi - pointer to the source bitmap
     @returns aiDup = ai xor bi. Neither ai nor bi are modified
 */
-     always_inline uword *
-     clib_bitmap_dup_xor (uword * ai, uword * bi);
+always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
 
 #define _(name)						\
   always_inline uword *					\
   clib_bitmap_dup_##name (uword * ai, uword * bi)	\
 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 
+/* *INDENT-OFF* */
 _(and);
 _(andnot);
 _(or);
 _(xor);
-
+/* *INDENT-ON* */
 #undef _
 
-/* ALU function definition macro for functions taking one bitmap and an immediate. */
+/* ALU function definition macro for functions taking one bitmap and an
+ * immediate. */
 #define _(name, body, check_zero)			\
 always_inline uword *					\
 clib_bitmap_##name (uword * ai, uword i)		\
@@ -582,17 +592,48 @@ clib_bitmap_##name (uword * ai, uword i)		\
 }
 
 /* ALU functions immediate: */
+/* *INDENT-OFF* */
 _(andi, a = a & b, 1)
-_(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1)
+_(andnoti, a = a & ~b, 1)
+_(ori, a = a | b, 0)
+_(xori, a = a ^ b, 1)
+/* *INDENT-ON* */
 #undef _
+
+/* ALU function definition macro for functions taking one bitmap and an
+ * immediate. No tail trimming */
+#define _(name, body)					\
+always_inline uword *					\
+clib_bitmap_##name##_notrim (uword * ai, uword i)	\
+{							\
+  uword i0 = i / BITS (ai[0]);				\
+  uword i1 = i % BITS (ai[0]);				\
+  uword a, b;						\
+  clib_bitmap_vec_validate (ai, i0);			\
+  a = ai[i0];						\
+  b = (uword) 1 << i1;					\
+  do { body; } while (0);				\
+  ai[i0] = a;						\
+  return ai;						\
+}
+
+/* ALU functions immediate: */
+/* *INDENT-OFF* */
+_(andi, a = a & b)
+_(andnoti, a = a & ~b)
+_(ori, a = a | b)
+_(xori, a = a ^ b)
+#undef _
+/* *INDENT-ON* */
+
 /** Return a random bitmap of the requested length
     @param ai - pointer to the destination bitmap
     @param n_bits - number of bits to allocate
     @param [in,out] seed - pointer to the random number seed
     @returns a reasonably random bitmap based. See random.h.
 */
-     always_inline uword *
-     clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
+always_inline uword *
+clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 {
   vec_reset_length (ai);
 
@@ -674,95 +715,18 @@ clib_bitmap_next_clear (uword * ai, uword i)
 	  if (t)
 	    return log2_first_set (t) + i0 * BITS (ai[0]);
 	}
-    }
-  return i;
-}
 
-/** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
-
-    uword * bitmap;
-    rv = unformat ("%U", unformat_bitmap_list, &bitmap);
-
-    Standard unformat_function_t arguments
-
-    @param input - pointer an unformat_input_t
-    @param va - varargs list comprising a single uword **
-    @returns 1 on success, 0 on failure
-*/
-static inline uword
-unformat_bitmap_list (unformat_input_t * input, va_list * va)
-{
-  uword **bitmap_return = va_arg (*va, uword **);
-  uword *bitmap = 0;
-
-  u32 a, b;
-
-  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
-    {
-      int i;
-      if (unformat (input, "%u-%u,", &a, &b))
-	;
-      else if (unformat (input, "%u,", &a))
-	b = a;
-      else if (unformat (input, "%u-%u", &a, &b))
-	;
-      else if (unformat (input, "%u", &a))
-	b = a;
-      else if (bitmap)
-	{
-	  unformat_put_input (input);
-	  break;
-	}
-      else
-	goto error;
-
-      if (b < a)
-	goto error;
-
-      for (i = a; i <= b; i++)
-	bitmap = clib_bitmap_set (bitmap, i, 1);
+      /* no clear bit left in bitmap, return bit just beyond bitmap */
+      return (i0 * BITS (ai[0])) + 1;
     }
-  *bitmap_return = bitmap;
-  return 1;
-error:
-  clib_bitmap_free (bitmap);
-  return 0;
+  return i;
 }
 
-/** Format a bitmap as a string of hex bytes
-
-    uword * bitmap;
-    s = format ("%U", format_bitmap_hex, bitmap);
-
-    Standard format_function_t arguments
-
-    @param s - string under construction
-    @param args - varargs list comprising a single uword *
-    @returns string under construction
-*/
-static inline u8 *
-format_bitmap_hex (u8 * s, va_list * args)
-{
-  uword *bitmap = va_arg (*args, uword *);
-  int i, is_trailing_zero = 1;
-
-  if (!bitmap)
-    return format (s, "0");
-
-  i = vec_bytes (bitmap) * 2;
-
-  while (i > 0)
-    {
-      u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
+uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
+uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
+u8 *format_bitmap_hex (u8 *s, va_list *args);
+u8 *format_bitmap_list (u8 *s, va_list *args);
 
-      if (x && is_trailing_zero)
-	is_trailing_zero = 0;
-
-      if (x || !is_trailing_zero)
-	s = format (s, "%x", x);
-    }
-  return s;
-}
 #endif /* included_clib_bitmap_h */
 
 /*