[PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

A new routine bitmap_majority_test allows to test that bitmap
a "majorates" bitmap b, i.e. test that a have at least all b bits.
We need it to test compatibility of required fields bitmap with
another one that is built for tuple on tuple_init_field_map.

Needed for #1012
---
 src/lib/bit/bit.h    | 45 ++++++++++++++++++++++++++++++++++++++
 test/unit/bit.c      | 52 ++++++++++++++++++++++++++++++++++++++++++++
 test/unit/bit.result |  2 ++
 3 files changed, 99 insertions(+)

diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
index 370a0cc5d..2146a0452 100644
--- a/src/lib/bit/bit.h
+++ b/src/lib/bit/bit.h
@@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it)
 	return it->word_base + bit;
 }
 
+/**
+ * Check if the passed bitmap a "majorates" bitmap b (test that
+ * a contains at least all b bits). Compare first len memory
+ * blocks of sizeof(uint32_t).
+ * Return 0 when a majorates b. Otherwise -1 is returned and
+ * diff_bit_id is set - the index of first bit that present in
+ * bitmap b, but doesn't present in bitmap a.
+ */
+static inline int
+bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id)
+{
+	int match_cnt = 0;
+	uint32_t *a_ptr = a, *b_ptr = b;
+	uint32_t neg_impl;
+	/*
+	 * "Inverted material implication" ~(~x | y) = x & ~y test
+	 * is used to find the first bit that differ
+	 *
+	 * Example:
+	 * step 0 -- skip compatible bytes
+	 * x:      0b01111101
+	 * y:      0b00111101
+	 * x & ~y: 0b00000000 == 0 -- next, goto step 0
+	 *
+	 * step 1 -- the first byte that differ:
+	 * x:      0b01011001
+	 * y:      0b00111101
+	 * x & ~y: 0b00100100
+	 *
+	 * step 2 -- calculate relative bit index with ctz:
+	 * bit_ctz_u32(0b00100100) = 2 -- return diff_bit_id
+	 */
+	while (bit_likely((neg_impl = *b_ptr & ~*a_ptr) == 0)) {
+		if (bit_unlikely(++match_cnt >= len)) {
+			return 0;
+		}
+		a_ptr++;
+		b_ptr++;
+	}
+	assert(neg_impl != 0);
+	uint32_t trailing_zeros = bit_ctz_u32(neg_impl);
+	*diff_bit_id = match_cnt * sizeof(uint32_t) * CHAR_BIT + trailing_zeros;
+	return -1;
+}
+
 #undef ITER_CTZ
 #undef ITER_UINT
 
diff --git a/test/unit/bit.c b/test/unit/bit.c
index beb89a7e4..10074c412 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -206,6 +206,57 @@ test_bit_iter_empty(void)
 	footer();
 }
 
+static void
+test_bitmap_majority(void)
+{
+	header();
+
+	uint32_t id;
+	uint32_t req_bitmap[5];
+	memset(req_bitmap, 0, sizeof(req_bitmap));
+	bit_set(req_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(req_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(req_bitmap, 8);
+	fail_if(bitmap_majority_test(req_bitmap, req_bitmap, 5, &id) != 0);
+
+	/*
+	 * Verify that bitmap_majority_test returns difference
+	 * bits ids in incremental order ignoring test extra bits.
+	 */
+	uint32_t test_bitmap[5];
+	memset(test_bitmap, 0, sizeof(test_bitmap));
+	bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 8);
+	bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 8);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 8);
+	bit_set(&test_bitmap, 8);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(&test_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(&test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+	/* All different bits have been fixed. */
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 4, &id) != 0);
+
+	footer();
+}
+
 int
 main(void)
 {
@@ -216,4 +267,5 @@ main(void)
 	test_index();
 	test_bit_iter();
 	test_bit_iter_empty();
+	test_bitmap_majority();
 }
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..6123bc58a 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3
 	*** test_bit_iter: done ***
 	*** test_bit_iter_empty ***
 	*** test_bit_iter_empty: done ***
+	*** test_bitmap_majority ***
+	*** test_bitmap_majority: done ***
-- 
2.19.2