From 5f349be820b32a5bb312566a4a35ef679fe7e478 Mon Sep 17 00:00:00 2001 From: Jacob Erlbeck Date: Mon, 21 Dec 2015 16:04:03 +0100 Subject: bitvec: Add get/set byte sequences The new functions bitvec_get_bytes and bitvec_set_bytes copy byte sequences from bitvecs to uint8_t arrays and vice versa. While the bytes in the bitvecs do not need to be aligned, the uint8_t arrays always are. In case the bytes in the bitvec are aligned, the implementation uses memcpy. Note that the implementation like the other existing functions assume MSB first encoding. [hfreyther: Squash the comment fix into this commit as well] Sponsored-by: On-Waves ehf --- include/osmocom/core/bitvec.h | 10 ++++++ src/bitvec.c | 75 +++++++++++++++++++++++++++++++++++++++++++ tests/Makefile.am | 9 ++++-- tests/bitvec/bitvec_test.c | 62 +++++++++++++++++++++++++++++++++++ tests/bitvec/bitvec_test.ok | 2 ++ tests/testsuite.at | 6 ++++ 6 files changed, 162 insertions(+), 2 deletions(-) create mode 100644 tests/bitvec/bitvec_test.c create mode 100644 tests/bitvec/bitvec_test.ok diff --git a/include/osmocom/core/bitvec.h b/include/osmocom/core/bitvec.h index 62e2e7b6..89eb7848 100644 --- a/include/osmocom/core/bitvec.h +++ b/include/osmocom/core/bitvec.h @@ -28,6 +28,14 @@ /*! \file bitvec.h * \brief Osmocom bit vector abstraction + * + * These functions assume a MSB (most significant bit) first layout of the + * bits, so that for instance the 5 bit number abcde (a is MSB) can be + * embedded into a byte sequence like in xxxxxxab cdexxxxx. The bit count + * starts with the MSB, so the bits in a byte are numbered (MSB) 01234567 (LSB). + * Note that there are other incompatible encodings, like it is used + * for the EGPRS RLC data block headers (there the bits are numbered from LSB + * to MSB). */ #include @@ -63,5 +71,7 @@ int bitvec_set_uint(struct bitvec *bv, unsigned int in, int count); int bitvec_get_uint(struct bitvec *bv, int 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); +int bitvec_get_bytes(struct bitvec *bv, uint8_t *bytes, int count); +int bitvec_set_bytes(struct bitvec *bv, const uint8_t *bytes, int count); /*! @} */ diff --git a/src/bitvec.c b/src/bitvec.c index 8da5a480..726a7681 100644 --- a/src/bitvec.c +++ b/src/bitvec.c @@ -1,6 +1,7 @@ /* bit vector utility routines */ /* (C) 2009 by Harald Welte + * (C) 2015 by Sysmocom s.f.m.c. GmbH * * All Rights Reserved * @@ -30,6 +31,7 @@ #include #include +#include #include @@ -261,4 +263,77 @@ int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n, return -1; } +/*! \brief get multiple bytes from current pos + * Assumes MSB first encoding. + * \param[in] bv bit vector + * \param[in] bytes array + * \param[in] count number of bytes to copy + */ +int bitvec_get_bytes(struct bitvec *bv, uint8_t *bytes, int count) +{ + int byte_offs = bytenum_from_bitnum(bv->cur_bit); + int bit_offs = bv->cur_bit % 8; + uint8_t c, last_c; + int i; + uint8_t *src; + + if (byte_offs + count + (bit_offs ? 1 : 0) > bv->data_len) + return -EINVAL; + + if (bit_offs == 0) { + memcpy(bytes, bv->data + byte_offs, count); + } else { + src = bv->data + byte_offs; + last_c = *(src++); + for (i = count; i > 0; i--) { + c = *(src++); + *(bytes++) = + (last_c << bit_offs) | + (c >> (8 - bit_offs)); + last_c = c; + } + } + + bv->cur_bit += count * 8; + return 0; +} + +/*! \brief set multiple bytes at current pos + * Assumes MSB first encoding. + * \param[in] bv bit vector + * \param[in] bytes array + * \param[in] count number of bytes to copy + */ +int bitvec_set_bytes(struct bitvec *bv, const uint8_t *bytes, int count) +{ + int byte_offs = bytenum_from_bitnum(bv->cur_bit); + int bit_offs = bv->cur_bit % 8; + uint8_t c, last_c; + int i; + uint8_t *dst; + + if (byte_offs + count + (bit_offs ? 1 : 0) > bv->data_len) + return -EINVAL; + + if (bit_offs == 0) { + memcpy(bv->data + byte_offs, bytes, count); + } else if (count > 0) { + dst = bv->data + byte_offs; + /* Get lower bits of first dst byte */ + last_c = *dst >> (8 - bit_offs); + for (i = count; i > 0; i--) { + c = *(bytes++); + *(dst++) = + (last_c << (8 - bit_offs)) | + (c >> bit_offs); + last_c = c; + } + /* Overwrite lower bits of N+1 dst byte */ + *dst = (*dst & ((1 << (8 - bit_offs)) - 1)) | + (last_c << (8 - bit_offs)); + } + + bv->cur_bit += count * 8; + return 0; +} /*! @} */ diff --git a/tests/Makefile.am b/tests/Makefile.am index 9d14350f..2411afa3 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -11,7 +11,8 @@ check_PROGRAMS = timer/timer_test sms/sms_test ussd/ussd_test \ logging/logging_test fr/fr_test \ loggingrb/loggingrb_test strrb/strrb_test \ vty/vty_test comp128/comp128_test utils/utils_test \ - smscb/gsm0341_test stats/stats_test + smscb/gsm0341_test stats/stats_test \ + bitvec/bitvec_test if ENABLE_MSGFILE check_PROGRAMS += msgfile/msgfile_test @@ -38,6 +39,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 +bitvec_bitvec_test_SOURCES = bitvec/bitvec_test.c +bitvec_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 @@ -128,7 +132,8 @@ EXTRA_DIST = testsuite.at $(srcdir)/package.m4 $(TESTSUITE) \ fr/fr_test.ok loggingrb/logging_test.ok \ loggingrb/logging_test.err strrb/strrb_test.ok \ vty/vty_test.ok comp128/comp128_test.ok \ - utils/utils_test.ok stats/stats_test.ok + utils/utils_test.ok stats/stats_test.ok \ + bitvec/bitvec_test.ok DISTCLEANFILES = atconfig diff --git a/tests/bitvec/bitvec_test.c b/tests/bitvec/bitvec_test.c new file mode 100644 index 00000000..624e3346 --- /dev/null +++ b/tests/bitvec/bitvec_test.c @@ -0,0 +1,62 @@ +#include +#include +#include +#include +#include + +#include +#include + +static void test_byte_ops() +{ + struct bitvec bv; + const uint8_t *in = (const uint8_t *)"ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + uint8_t out[26 + 2]; + uint8_t data[64]; + int i; + int rc; + int in_size = strlen((const char *)in); + + printf("=== start %s ===\n", __func__); + + bv.data = data; + bv.data_len = sizeof(data); + + for (i = 0; i < 32; i++) { + /* Write to bitvec */ + memset(data, 0x00, sizeof(data)); + bv.cur_bit = i; + rc = bitvec_set_uint(&bv, 0x7e, 8); + OSMO_ASSERT(rc >= 0); + rc = bitvec_set_bytes(&bv, in, in_size); + OSMO_ASSERT(rc >= 0); + rc = bitvec_set_uint(&bv, 0x7e, 8); + OSMO_ASSERT(rc >= 0); + + fprintf(stderr, "bitvec: %s\n", osmo_hexdump(bv.data, bv.data_len)); + + /* Read from bitvec */ + memset(out, 0xff, sizeof(out)); + bv.cur_bit = i; + rc = bitvec_get_uint(&bv, 8); + OSMO_ASSERT(rc == 0x7e); + rc = bitvec_get_bytes(&bv, out + 1, in_size); + OSMO_ASSERT(rc >= 0); + rc = bitvec_get_uint(&bv, 8); + OSMO_ASSERT(rc == 0x7e); + + fprintf(stderr, "out: %s\n", osmo_hexdump(out, sizeof(out))); + + OSMO_ASSERT(out[0] == 0xff); + OSMO_ASSERT(out[in_size+1] == 0xff); + OSMO_ASSERT(memcmp(in, out + 1, in_size) == 0); + } + + printf("=== end %s ===\n", __func__); +} + +int main(int argc, char **argv) +{ + test_byte_ops(); + return 0; +} diff --git a/tests/bitvec/bitvec_test.ok b/tests/bitvec/bitvec_test.ok new file mode 100644 index 00000000..1f329aff --- /dev/null +++ b/tests/bitvec/bitvec_test.ok @@ -0,0 +1,2 @@ +=== start test_byte_ops === +=== end test_byte_ops === diff --git a/tests/testsuite.at b/tests/testsuite.at index 85c3e8bd..55e79f19 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/bitvec/bitvec_test.ok > expout +AT_CHECK([$abs_top_builddir/tests/bitvec/bitvec_test], [0], [expout], [ignore]) +AT_CLEANUP + AT_SETUP([conv]) AT_KEYWORDS([conv]) cat $abs_srcdir/conv/conv_test.ok > expout -- cgit v1.2.3