[RFC v2 15/99] utils: Add few more functions to bitfield module

[Andrei Otcheretianski]

From: Ilan Peer <ilan.peer at intel.com>

These would be used by the NAN logic.

Signed-off-by: Ilan Peer <ilan.peer at intel.com>
---
 src/utils/bitfield.c           | 158 +++++++++++++++++++++++++++++++++
 src/utils/bitfield.h           |  12 +++
 src/utils/utils_module_tests.c |  75 +++++++++++++++-
 3 files changed, 244 insertions(+), 1 deletion(-)

diff --git a/src/utils/bitfield.c b/src/utils/bitfield.c
index 8dcec3907e..d10936070a 100644
--- a/src/utils/bitfield.c
+++ b/src/utils/bitfield.c
@@ -87,3 +87,161 @@ int bitfield_get_first_zero(struct bitfield *bf)
 		return -1;
 	return i;
 }
+
+
+struct bitfield * bitfield_alloc_data(const u8 *data, size_t len)
+{
+	struct bitfield *bf;
+
+	bf = os_zalloc(sizeof(*bf) + len);
+	if (!bf)
+		return NULL;
+
+	bf->bits = (u8 *)(bf + 1);
+	os_memcpy(bf->bits, data, len);
+
+	bf->max_bits = len * 8;
+	return bf;
+}
+
+
+struct bitfield * bitfield_dup(const struct bitfield *orig)
+{
+	struct bitfield *bf;
+
+	if (!orig)
+		return NULL;
+
+	bf = os_memdup(orig,
+		       sizeof(*orig) + (orig->max_bits + 7) / 8);
+	if (!bf)
+		return NULL;
+
+	bf->bits = (u8 *)(bf + 1);
+
+	return bf;
+}
+
+
+int bitfield_union_in_place(struct bitfield *a, const struct bitfield *b)
+{
+	size_t i, upper;
+
+	if (!a || !b || a->max_bits < b->max_bits)
+		return -1;
+
+	upper = (b->max_bits + 7) / 8;
+
+	for (i = 0 ; i < upper; i++)
+		a->bits[i] |= b->bits[i];
+
+	return 0;
+}
+
+
+struct bitfield * bitfield_union(const struct bitfield *a,
+				 const struct bitfield *b)
+{
+	struct bitfield *res;
+	int ret;
+
+	if (!a || !b)
+		return NULL;
+
+	if (a->max_bits > b->max_bits) {
+		res = bitfield_dup(a);
+		ret = bitfield_union_in_place(res, b);
+	}  else {
+		res = bitfield_dup(b);
+		ret = bitfield_union_in_place(res, a);
+	}
+
+	if (!ret)
+		return res;
+
+	os_free(res);
+	return NULL;
+}
+
+
+int bitfield_intersect_in_place(struct bitfield *a,
+				const struct bitfield *b)
+{
+	size_t i, upper;
+
+	if (!a || !b)
+		return -1;
+
+	if (a->max_bits < b->max_bits)
+		upper = (a->max_bits + 7) / 8;
+	else
+		upper = (b->max_bits + 7) / 8;
+
+
+	for (i = 0 ; i < upper; i++)
+		a->bits[i] &= b->bits[i];
+
+	upper = (a->max_bits + 7) / 8;
+	for (; i < upper; i++)
+		a->bits[i] = 0;
+
+	return 0;
+}
+
+
+int bitfield_is_subset(const struct bitfield *a, struct bitfield *b)
+{
+	size_t i, upper;
+
+	if (!a || !b)
+		return -1;
+
+	if (a->max_bits < b->max_bits)
+		return 0;
+
+	upper = (b->max_bits + 7) / 8;
+
+	for (i = 0; i < upper; i++) {
+		u8 res = a->bits[i] & b->bits[i];
+
+		if (res != b->bits[i])
+			return 0;
+	}
+
+	return 1;
+}
+
+
+size_t bitfield_size(const struct bitfield *bf)
+{
+	if (!bf)
+		return 0;
+	return bf->max_bits;
+}
+
+
+int bitfield_intersects(const struct bitfield *a, const struct bitfield *b)
+{
+	size_t i, upper;
+
+	if (!a || !b)
+		return -1;
+
+	if (a->max_bits < b->max_bits)
+		upper = (a->max_bits + 7) / 8;
+	else
+		upper = (b->max_bits + 7) / 8;
+
+	for (i = 0; i < upper; i++)
+		if (a->bits[i] & b->bits[i])
+			return 1;
+
+	return 0;
+}
+
+
+void bitfield_dump(struct bitfield *bf, const char *title)
+{
+	wpa_printf(MSG_DEBUG, "bitfield: %s: max_bits=%zu", title, bf->max_bits);
+	wpa_hexdump(MSG_DEBUG, "bits: ", bf->bits, bf->max_bits / 8);
+}
diff --git a/src/utils/bitfield.h b/src/utils/bitfield.h
index 7050a208c8..5b805773d2 100644
--- a/src/utils/bitfield.h
+++ b/src/utils/bitfield.h
@@ -9,6 +9,8 @@
 #ifndef BITFIELD_H
 #define BITFIELD_H
 
+#include "utils/common.h"
+
 struct bitfield;
 
 struct bitfield * bitfield_alloc(size_t max_bits);
@@ -18,4 +20,14 @@ void bitfield_clear(struct bitfield *bf, size_t bit);
 int bitfield_is_set(struct bitfield *bf, size_t bit);
 int bitfield_get_first_zero(struct bitfield *bf);
 
+struct bitfield * bitfield_alloc_data(const u8 *data, size_t len);
+struct bitfield * bitfield_dup(const struct bitfield *orig);
+int bitfield_union_in_place(struct bitfield *a, const struct bitfield *b);
+struct bitfield * bitfield_union(const struct bitfield *a,
+				 const struct bitfield *b);
+int bitfield_intersect_in_place(struct bitfield *a, const struct bitfield *b);
+int bitfield_is_subset(const struct bitfield *a, struct bitfield *b);
+size_t bitfield_size(const struct bitfield *bf);
+int bitfield_intersects(const struct bitfield *a, const struct bitfield *b);
+void bitfield_dump(struct bitfield *bf, const char *title);
 #endif /* BITFIELD_H */
diff --git a/src/utils/utils_module_tests.c b/src/utils/utils_module_tests.c
index 365f21fb11..58343f86d7 100644
--- a/src/utils/utils_module_tests.c
+++ b/src/utils/utils_module_tests.c
@@ -127,10 +127,13 @@ static int printf_encode_decode_tests(void)
 
 static int bitfield_tests(void)
 {
-	struct bitfield *bf;
+	struct bitfield *bf, *bf_a = NULL, *bf_b = NULL, *bf_c = NULL;
 	int i;
 	int errors = 0;
 
+	u8 data_a[4] = {0xff, 0x3f, 0x01, 0xf0};
+	u8 data_b[4] = {0xff, 0xc0, 0xfe, 0x0f};
+
 	wpa_printf(MSG_INFO, "bitfield tests");
 
 	bf = bitfield_alloc(123);
@@ -210,6 +213,76 @@ static int bitfield_tests(void)
 		errors++;
 	bitfield_free(bf);
 
+	bf_a = bitfield_alloc_data(data_a, sizeof(data_a));
+	if (!bf_a)
+		goto fail;
+
+	bf_b = bitfield_alloc_data(data_b, sizeof(data_b));
+	if (!bf_b)
+		goto fail;
+
+	bf_c = bitfield_dup(bf_a);
+	if (!bf_c)
+		goto fail;
+
+	/* test intersection */
+	if (bitfield_intersect_in_place(bf_c, bf_b))
+		goto fail;
+
+	for (i = 0; i < 8; i++)
+		if (!bitfield_is_set(bf_c, i))
+			goto fail;
+
+	for (; i < 32; i++)
+		if (bitfield_is_set(bf_c, i))
+			goto fail;
+
+	bitfield_free(bf_c);
+
+	/* test union */
+	bf_c = bitfield_union(bf_a, bf_b);
+	if (!bf_c)
+		goto fail;
+
+	if (!bitfield_intersects(bf_a, bf_c) ||
+	    !bitfield_intersects(bf_b, bf_c) ||
+	    !bitfield_intersects(bf_c, bf_a) ||
+	    !bitfield_intersects(bf_c, bf_b) ||
+	    !bitfield_intersects(bf_a, bf_b))
+		goto fail;
+
+	for (i = 0; i < 32; i++)
+		if (!bitfield_is_set(bf_c, i))
+			goto fail;
+
+	if (!bitfield_is_subset(bf_c, bf_a) ||
+	    !bitfield_is_subset(bf_c, bf_b) ||
+	    bitfield_is_subset(bf_a, bf_c) ||
+	    bitfield_is_subset(bf_b, bf_c) ||
+	    bitfield_is_subset(bf_a, bf_b))
+		goto fail;
+
+	/* test in place union */
+	if (bitfield_union_in_place(bf_a, bf_b))
+		goto fail;
+
+	if (bitfield_size(bf_a) != 32 ||
+	    bitfield_size(bf_b) != 32 ||
+	    bitfield_size(bf_c) != 32)
+		goto fail;
+
+	for (i = 0; i < 32; i++)
+		if (!bitfield_is_set(bf_c, i))
+			goto fail;
+	goto out;
+
+fail:
+	errors++;
+out:
+	bitfield_free(bf_a);
+	bitfield_free(bf_c);
+	bitfield_free(bf_b);
+
 	if (errors) {
 		wpa_printf(MSG_ERROR, "%d bitfield test(s) failed", errors);
 		return -1;
-- 
2.49.0