[PATCH] Fix and expand bitvec interface.

From: Max &lt;msuraev(a)sysmocom.de&gt; 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 &lt;msuraev(a)sysmocom.de&gt; --- .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