}
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;
@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
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)
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;
}
}
}
/* 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
@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
@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
@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
@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) \
}
/* 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);
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 */
/*
Code Review / vpp.git / blobdiff