diff mbox

Fix and expand bitvec interface.

Message ID 1452695069-22186-1-git-send-email-suraev@alumni.ntnu.no
State New
Headers show

Commit Message

Suraev Jan. 13, 2016, 2:24 p.m. UTC 
From: Max <msuraev@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@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

Comments

Suraev Jan. 13, 2016, 2:35 p.m. UTC | #1 
This patch lays out ground work for implementing compressed bitmap support.

cheers,
Max.
Harald Welte Jan. 14, 2016, 10:23 a.m. UTC | #2 
Hi Max,

On Wed, Jan 13, 2016 at 03:24:29PM +0100, suraev@alumni.ntnu.no wrote:
> +int bitvec_set_uint(struct bitvec *bv, unsigned int in, unsigned count);

we generally don't use 'unsigned' in the code so far, but 'unsigned
int'.  So it's a bit odd to see 'unsigned' without int here.  In
general, I probably wouldn't care too much.  However, given that it is a
single function that has one 'unsigned int' and one 'unsigned' argument,
it seems a bit odd.

> +		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;

If you're printing a single character only, using fputc() should be
much more efficient.  I'm not sure if gcc is good to detect that and
replace it by itself.  If yes, no need to change the code.  If not,
better use fputc.

Also, the library should generally not just printf.  For the majority of
the programs running as daemons this doesn't make sense.  

The general way to deal with this is to offer a function that generates
the string, i.e. 'char *bitvec_to_string(bitvec *bv)'.  Since we assume
single-threaded useres only, having a static buffer and always returning
that buffer has so far been the the generally accepted form.  If you
don't like that, offer a bitvec_to_string_r() using a caller-allocated
string, or maybe even better, something that take a talloc context as
first argument, form where the output-string is then allocated.
Suraev Jan. 14, 2016, 1:10 p.m. UTC | #3 
14.01.2016 11:23, Harald Welte пишет:

> we generally don't use 'unsigned' in the code so far, but 'unsigned
> int'.  So it's a bit odd to see 'unsigned' without int here.  In
> general, I probably wouldn't care too much.  However, given that it is a
> single function that has one 'unsigned int' and one 'unsigned' argument,
> it seems a bit odd.

I prefer 'unsigned' because it's less to type and neither provides any guarantees
with regards to size of the type. I think size_t and uintXX_t would be better
technically.

On a related note, what's the status of https://patchwork.ozlabs.org/patch/559571/ ?
Cause merging it would result in conflict with this patch so I'd prefer to rebase
mine earlier if possible.

cheers,
Max.
diff mbox

Patch

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