[PATCH] Fix and expand bitvec interface.

This is merely a historical archive of years 2008-2021, before the migration to mailman3.

A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/baseband-devel@lists.osmocom.org/.

suraev at alumni.ntnu.no suraev at alumni.ntnu.no
Wed Jan 13 14:24:29 UTC 2016


From: Max <msuraev at sysmocom.de>

Fix all bit counters to take unsigned value only.
Add functions for shifting and run length detection.
Add tests and pretty-print function.

Sponsored-by: On-Waves ehf

Signed-off-by: Max <msuraev at sysmocom.de>
---
 .gitignore                    |  1 +
 include/osmocom/core/bitvec.h | 11 ++++--
 src/bitvec.c                  | 89 +++++++++++++++++++++++++++++++++++++++++--
 tests/Makefile.am             | 10 +++--
 tests/bits/bitvec_test.c      | 43 +++++++++++++++++++++
 tests/bits/bitvec_test.ok     | 14 +++++++
 tests/testsuite.at            |  6 +++
 7 files changed, 165 insertions(+), 9 deletions(-)
 create mode 100644 tests/bits/bitvec_test.c
 create mode 100644 tests/bits/bitvec_test.ok

diff --git a/.gitignore b/.gitignore
index 598f88a..25c9d97 100644
--- a/.gitignore
+++ b/.gitignore
@@ -64,6 +64,7 @@ tests/msgfile/msgfile_test
 tests/ussd/ussd_test
 tests/smscb/smscb_test
 tests/bits/bitrev_test
+tests/bits/bitvec_test
 tests/a5/a5_test
 tests/comp128/comp128_test
 tests/auth/milenage_test
diff --git a/include/osmocom/core/bitvec.h b/include/osmocom/core/bitvec.h
index 62e2e7b..3f7f166 100644
--- a/include/osmocom/core/bitvec.h
+++ b/include/osmocom/core/bitvec.h
@@ -31,6 +31,7 @@
  */
 
 #include <stdint.h>
+#include <stdbool.h>
 
 /*! \brief A single GSM bit
  *
@@ -58,10 +59,14 @@ int bitvec_set_bit_pos(struct bitvec *bv, unsigned int bitnum,
 			enum bit_value bit);
 int bitvec_set_bit(struct bitvec *bv, enum bit_value bit);
 int bitvec_get_bit_high(struct bitvec *bv);
-int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, int count);
-int bitvec_set_uint(struct bitvec *bv, unsigned int in, int count);
-int bitvec_get_uint(struct bitvec *bv, int num_bits);
+int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, unsigned count);
+int bitvec_set_uint(struct bitvec *bv, unsigned int in, unsigned count);
+int bitvec_get_uint(struct bitvec *bv, unsigned num_bits);
 int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n, enum bit_value val);
 int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit);
+void bitvec_print(struct bitvec *bv);
+void bitvec_zero(struct bitvec *bv);
+unsigned bitvec_rl(struct bitvec *bv, bool b);
+void bitvec_shiftl(struct bitvec *bv, unsigned n);
 
 /*! @} */
diff --git a/src/bitvec.c b/src/bitvec.c
index 8da5a48..c791926 100644
--- a/src/bitvec.c
+++ b/src/bitvec.c
@@ -30,7 +30,11 @@
 
 #include <errno.h>
 #include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdbool.h>
 
+#include <osmocom/core/bits.h>
 #include <osmocom/core/bitvec.h>
 
 #define BITNUM_FROM_COMP(byte, bit)	((byte*8)+bit)
@@ -188,7 +192,7 @@ int bitvec_get_bit_high(struct bitvec *bv)
  *  \param[in] bits array of \ref bit_value
  *  \param[in] count number of bits to set
  */
-int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, int count)
+int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, unsigned count)
 {
 	int i, rc;
 
@@ -202,7 +206,7 @@ int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, int count)
 }
 
 /*! \brief set multiple bits (based on numeric value) at current pos */
-int bitvec_set_uint(struct bitvec *bv, unsigned int ui, int num_bits)
+int bitvec_set_uint(struct bitvec *bv, unsigned int ui, unsigned num_bits)
 {
 	int i, rc;
 
@@ -219,7 +223,7 @@ int bitvec_set_uint(struct bitvec *bv, unsigned int ui, int num_bits)
 }
 
 /*! \brief get multiple bits (based on numeric value) from current pos */
-int bitvec_get_uint(struct bitvec *bv, int num_bits)
+int bitvec_get_uint(struct bitvec *bv, unsigned num_bits)
 {
 	int i;
 	unsigned int ui = 0;
@@ -261,4 +265,83 @@ int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n,
 	return -1;
 }
 
+/*! \brief prints bit vector to stdout */
+void bitvec_print(struct bitvec *bv)
+{
+	unsigned i;
+	for (i = 0; i < bv->cur_bit; i++) {
+		if (0 == i % 8) printf(" ");
+		switch (bitvec_get_bit_pos(bv, i)) {
+		case ZERO: printf("0"); break;
+		case ONE: printf("1"); break;
+		case L: printf("L"); break;
+		case H: printf("H"); break;
+		}
+	}
+}
+
+/* we assume that x have at least 1 non-b bit */
+inline unsigned _leading_bits(uint8_t x, bool b)
+{
+	if (b) {
+		if (x < 0x80) return 0;
+		if (x < 0xC0) return 1;
+		if (x < 0xE0) return 2;
+		if (x < 0xF0) return 3;
+		if (x < 0xF8) return 4;
+		if (x < 0xFC) return 5;
+		if (x < 0xFE) return 6;
+	} else {
+		if (x > 0x7F) return 0;
+		if (x > 0x3F) return 1;
+		if (x > 0x1F) return 2;
+		if (x > 0xF) return 3;
+		if (x > 7) return 4;
+		if (x > 3) return 5;
+		if (x > 1) return 6;
+	}
+	return 7;
+}
+
+/*! \brief Return number (bits) of uninterrupted run of \b in \bv starting from the MSB */
+unsigned bitvec_rl(struct bitvec *bv, bool b)
+{
+	unsigned i;
+	for (i = 0; i < bv->data_len; i++) {
+		if ( (b ? 0xFF : 0) != bv->data[i]) return i * 8 + _leading_bits(bv->data[i], b);
+	}
+
+	return bv->cur_bit;
+}
+
+/*! \brief Shifts bitvec to the left, n MSB bits lost */
+void bitvec_shiftl(struct bitvec *bv, unsigned n)
+{
+	if (0 == n) return;
+	if (n >= bv->cur_bit) {
+		bitvec_zero(bv);
+		return;
+	}
+
+	memmove(bv->data, bv->data + n / 8, bv->data_len - n / 8);
+
+	uint8_t tmp[2];
+	unsigned i;
+	for (i = 0; i < bv->data_len - 2; i++) {
+		uint16_t t = osmo_load16be(bv->data + i);
+		osmo_store16be(t << (n % 8), &tmp);
+		bv->data[i] = tmp[0];
+	}
+
+	bv->data[bv->data_len - 1] <<= (n % 8);
+	bv->cur_bit -= n;
+}
+
+/*! \brief force bit vector to all 0 and current bit to the beginnig of the vector */
+void bitvec_zero(struct bitvec *bv)
+{
+	bv->cur_bit = 0;
+	memset(bv->data, 0, bv->data_len);
+}
+
 /*! @} */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 3dc9bd9..eaeda72 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -3,9 +3,9 @@ AM_CFLAGS = -Wall $(TALLOC_CFLAGS)
 AM_LDFLAGS = $(TALLOC_LIBS)
 
 check_PROGRAMS = timer/timer_test sms/sms_test ussd/ussd_test		\
-                 smscb/smscb_test bits/bitrev_test a5/a5_test		\
+                 smscb/smscb_test bits/bitrev_test bits/bitvec_test	\
                  conv/conv_test auth/milenage_test lapd/lapd_test	\
-                 gsm0808/gsm0808_test gsm0408/gsm0408_test		\
+                 gsm0808/gsm0808_test gsm0408/gsm0408_test a5/a5_test	\
 		 gb/bssgp_fc_test gb/gprs_bssgp_test gb/gprs_ns_test	\
 		 kasumi/kasumi_test logging/logging_test fr/fr_test	\
 		 loggingrb/loggingrb_test strrb/strrb_test              \
@@ -37,6 +37,9 @@ auth_milenage_test_LDADD = $(top_builddir)/src/libosmocore.la $(top_builddir)/sr
 bits_bitrev_test_SOURCES = bits/bitrev_test.c
 bits_bitrev_test_LDADD = $(top_builddir)/src/libosmocore.la
 
+bits_bitvec_test_SOURCES = bits/bitvec_test.c
+bits_bitvec_test_LDADD = $(top_builddir)/src/libosmocore.la
+
 conv_conv_test_SOURCES = conv/conv_test.c
 conv_conv_test_LDADD = $(top_builddir)/src/libosmocore.la
 
@@ -112,7 +115,8 @@ $(srcdir)/package.m4: $(top_srcdir)/configure.ac
 
 EXTRA_DIST = testsuite.at $(srcdir)/package.m4 $(TESTSUITE)		\
              timer/timer_test.ok sms/sms_test.ok ussd/ussd_test.ok	\
-             smscb/smscb_test.ok bits/bitrev_test.ok a5/a5_test.ok	\
+             bits/bitrev_test.ok bits/bitvec_test.ok			\
+             smscb/smscb_test.ok a5/a5_test.ok				\
              conv/conv_test.ok auth/milenage_test.ok			\
              lapd/lapd_test.ok gsm0408/gsm0408_test.ok			\
              gsm0808/gsm0808_test.ok gb/bssgp_fc_tests.err		\
diff --git a/tests/bits/bitvec_test.c b/tests/bits/bitvec_test.c
new file mode 100644
index 0000000..c53e011
--- /dev/null
+++ b/tests/bits/bitvec_test.c
@@ -0,0 +1,43 @@
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <time.h>
+#include <stdbool.h>
+
+#include <osmocom/core/utils.h>
+#include <osmocom/core/bits.h>
+#include <osmocom/core/bitvec.h>
+
+int main(int argc, char **argv)
+{
+	srand(time(NULL));
+
+	struct bitvec bv;
+	uint8_t i = 8, test[i];
+
+	memset(test, 0, i);
+	bv.data_len = i;
+	bv.data = test;
+	bv.cur_bit = 0;
+
+	printf("checking RL functions...\n");
+
+	bitvec_zero(&bv); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+	bitvec_set_uint(&bv, 0x000F, 32); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+	bitvec_shiftl(&bv, 18); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+	bitvec_set_uint(&bv, 0x0F, 8); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+	bitvec_zero(&bv);
+	bitvec_set_uint(&bv, 0xFF, 8); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+	bitvec_set_uint(&bv, 0xFE, 7); bitvec_print(&bv); printf(" RL0=%d, RL1=%d\n", bitvec_rl(&bv, false), bitvec_rl(&bv, true));
+
+	printf("test shifting...\n");
+
+	bitvec_set_uint(&bv, 0x0E, 7); bitvec_print(&bv);  printf(" << 3:\n");	bitvec_shiftl(&bv, 3); bitvec_print(&bv); printf("\n");
+	bitvec_print(&bv);  printf(" << 17:\n"); bitvec_shiftl(&bv, 17); bitvec_print(&bv); printf("\n");
+	bitvec_set_uint(&bv, 0, 32); bitvec_set_uint(&bv, 0x0A, 7);
+	bitvec_print(&bv);  printf(" << 24:\n"); bitvec_shiftl(&bv, 24); bitvec_print(&bv); printf("\n");
+
+	return 0;
+}
diff --git a/tests/bits/bitvec_test.ok b/tests/bits/bitvec_test.ok
new file mode 100644
index 0000000..e72ae34
--- /dev/null
+++ b/tests/bits/bitvec_test.ok
@@ -0,0 +1,14 @@
+checking RL functions...
+ RL0=0, RL1=0
+ 00000000 00000000 00000000 00001111 RL0=28, RL1=0
+ 00000000 001111 RL0=10, RL1=0
+ 00000000 00111100 001111 RL0=10, RL1=0
+ 11111111 RL0=0, RL1=8
+ 11111111 1111110 RL0=0, RL1=14
+test shifting...
+ 11111111 11111100 001110 << 3:
+ 11111111 11100001 110
+ 11111111 11100001 110 << 17:
+ 10
+ 10000000 00000000 00000000 00000000 00000101 0 << 24:
+ 00000000 00000101 0
diff --git a/tests/testsuite.at b/tests/testsuite.at
index a542798..84ae2c9 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -21,6 +21,12 @@ cat $abs_srcdir/bits/bitrev_test.ok > expout
 AT_CHECK([$abs_top_builddir/tests/bits/bitrev_test], [0], [expout])
 AT_CLEANUP
 
+AT_SETUP([bitvec])
+AT_KEYWORDS([bitvec])
+cat $abs_srcdir/bits/bitvec_test.ok > expout
+AT_CHECK([$abs_top_builddir/tests/bits/bitvec_test], [0], [expout])
+AT_CLEANUP
+
 AT_SETUP([conv])
 AT_KEYWORDS([conv])
 cat $abs_srcdir/conv/conv_test.ok > expout
-- 
2.5.0




More information about the baseband-devel mailing list