X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=src%2Fvppinfra%2Fbitops.h;h=3d17f0d5ace69bdb95a78ee1820446fbcc5a5ee5;hb=0e2f188f7;hp=ab91b8ae443ae8d84b9b9a8eb8066e9f0875c5e0;hpb=7cd468a3d7dee7d6c92f69a0bb7061ae208ec727;p=vpp.git

diff --git a/src/vppinfra/bitops.h b/src/vppinfra/bitops.h
index ab91b8ae443..3d17f0d5ace 100644
--- a/src/vppinfra/bitops.h
+++ b/src/vppinfra/bitops.h
@@ -38,12 +38,42 @@
 #ifndef included_clib_bitops_h
 #define included_clib_bitops_h
 
-#include <vppinfra/clib.h>
+#define SET_BIT(i)    (1 << i)
+#define GET_BIT(n, i) (n >> i) & 1U
+
+static_always_inline uword
+clear_lowest_set_bit (uword x)
+{
+#ifdef __BMI__
+  return uword_bits > 32 ? _blsr_u64 (x) : _blsr_u32 (x);
+#else
+  return x & (x - 1);
+#endif
+}
+
+static_always_inline uword
+get_lowest_set_bit (uword x)
+{
+#ifdef __BMI__
+  return uword_bits > 32 ? _blsi_u64 (x) : _blsi_u32 (x);
+#else
+  return x & -x;
+#endif
+}
+
+static_always_inline u8
+get_lowest_set_bit_index (uword x)
+{
+  return uword_bits > 32 ? __builtin_ctzll (x) : __builtin_ctz (x);
+}
 
 /* Population count from Hacker's Delight. */
 always_inline uword
 count_set_bits (uword x)
 {
+#ifdef __POPCNT__
+  return uword_bits > 32 ? __builtin_popcountll (x) : __builtin_popcount (x);
+#else
 #if uword_bits == 64
   const uword c1 = 0x5555555555555555;
   const uword c2 = 0x3333333333333333;
@@ -71,8 +101,18 @@ count_set_bits (uword x)
 #endif
 
   return x & (2 * BITS (uword) - 1);
+#endif
 }
 
+#if uword_bits == 64
+#define count_leading_zeros(x) __builtin_clzll (x)
+#else
+#define count_leading_zeros(x) __builtin_clzll (x)
+#endif
+
+#define count_trailing_zeros(x) get_lowest_set_bit_index (x)
+#define log2_first_set(x)	get_lowest_set_bit_index (x)
+
 /* Based on "Hacker's Delight" code from GLS. */
 typedef struct
 {
@@ -155,19 +195,128 @@ next_with_same_number_of_set_bits (uword x)
   return ripple | ones;
 }
 
-#define foreach_set_bit(var,mask,body)					\
-do {									\
-  uword _foreach_set_bit_m_##var = (mask);				\
-  uword _foreach_set_bit_f_##var;					\
-  while (_foreach_set_bit_m_##var != 0)					\
-    {									\
-      _foreach_set_bit_f_##var = first_set (_foreach_set_bit_m_##var);	\
-      _foreach_set_bit_m_##var ^= _foreach_set_bit_f_##var;		\
-      (var) = min_log2 (_foreach_set_bit_f_##var);			\
-      do { body; } while (0);						\
-    }									\
-} while (0)
+#define foreach_set_bit_index(i, v)                                           \
+  for (uword _tmp = (v) + 0 * (uword) (i = get_lowest_set_bit_index (v));     \
+       _tmp;                                                                  \
+       i = get_lowest_set_bit_index (_tmp = clear_lowest_set_bit (_tmp)))
+
+static_always_inline uword
+uword_bitmap_count_set_bits (uword *bmp, uword n_uwords)
+{
+  uword count = 0;
+  while (n_uwords--)
+    count += count_set_bits (bmp++[0]);
+  return count;
+}
+
+static_always_inline uword
+uword_bitmap_is_bit_set (uword *bmp, uword bit_index)
+{
+  bmp += bit_index / uword_bits;
+  bit_index %= uword_bits;
+  return (bmp[0] >> bit_index) & 1;
+}
 
+static_always_inline void
+uword_bitmap_set_bits_at_index (uword *bmp, uword bit_index, uword n_bits)
+{
+  bmp += bit_index / uword_bits;
+  bit_index %= uword_bits;
+  uword max_bits = uword_bits - bit_index;
+
+  if (n_bits < max_bits)
+    {
+      bmp[0] |= pow2_mask (n_bits) << bit_index;
+      return;
+    }
+
+  bmp++[0] |= pow2_mask (max_bits) << bit_index;
+  n_bits -= max_bits;
+
+  for (; n_bits >= uword_bits; bmp++, n_bits -= uword_bits)
+    bmp[0] = ~0ULL;
+
+  if (n_bits)
+    bmp[0] |= pow2_mask (n_bits);
+}
+
+static_always_inline void
+uword_bitmap_clear_bits_at_index (uword *bmp, uword bit_index, uword n_bits)
+{
+  bmp += bit_index / uword_bits;
+  bit_index %= uword_bits;
+  uword max_bits = uword_bits - bit_index;
+
+  if (n_bits < max_bits)
+    {
+      bmp[0] &= ~(pow2_mask (n_bits) << bit_index);
+      return;
+    }
+
+  bmp++[0] &= ~(pow2_mask (max_bits) << bit_index);
+  n_bits -= max_bits;
+
+  for (; n_bits >= uword_bits; bmp++, n_bits -= uword_bits)
+    bmp[0] = 0ULL;
+
+  if (n_bits)
+    bmp[0] &= ~pow2_mask (n_bits);
+}
+
+static_always_inline int
+uword_bitmap_find_first_set (uword *bmp)
+{
+  uword *b = bmp;
+  while (b[0] == 0)
+    b++;
+
+  return (b - bmp) * uword_bits + get_lowest_set_bit_index (b[0]);
+}
+
+static_always_inline u32
+bit_extract_u32 (u32 v, u32 mask)
+{
+#ifdef __BMI2__
+  return _pext_u32 (v, mask);
+#else
+  u32 rv = 0;
+  u32 bit = 1;
+
+  while (mask)
+    {
+      u32 lowest_mask_bit = get_lowest_set_bit (mask);
+      mask ^= lowest_mask_bit;
+      rv |= (v & lowest_mask_bit) ? bit : 0;
+      bit <<= 1;
+    }
+
+  return rv;
+#endif
+}
+
+static_always_inline u64
+bit_extract_u64 (u64 v, u64 mask)
+{
+#ifdef __BMI2__
+  return _pext_u64 (v, mask);
+#else
+  u64 rv = 0;
+  u64 bit = 1;
+
+  while (mask)
+    {
+      u64 lowest_mask_bit = get_lowest_set_bit (mask);
+      mask ^= lowest_mask_bit;
+      rv |= (v & lowest_mask_bit) ? bit : 0;
+      bit <<= 1;
+    }
+
+  return rv;
+#endif
+}
+
+#else
+#warning "already included"
 #endif /* included_clib_bitops_h */
 
 /*