[PATCH 1/2] Add function to add bits from array to bitvec

From: Max &lt;msuraev(a)sysmocom.de&gt; Add function which adds specified number of bits from each element of array to the bit vector prefixing each addition with one and finishing entire sequence with adding 0. This is very common patter for various repetitive data structures described with CSN.1 in 3GPP standards. Corresponding test vectors and doxygen headers are added too. --- include/osmocom/core/bitvec.h | 3 +++ src/bitvec.c | 40 ++++++++++++++++++++++++++++++++++++++++ tests/bitvec/bitvec_test.c | 43 +++++++++++++++++++++++++++++++++++++++++++ tests/bitvec/bitvec_test.ok | 33 +++++++++++++++++++++++++++++++++ 4 files changed, 119 insertions(+) diff --git a/include/osmocom/core/bitvec.h b/include/osmocom/core/bitvec.h index 5314cf2..c3c1153 100644 --- a/include/osmocom/core/bitvec.h +++ b/include/osmocom/core/bitvec.h @@ -91,5 +91,8 @@ void bitvec_zero(struct bitvec *bv); unsigned bitvec_rl(const struct bitvec *bv, bool b); void bitvec_shiftl(struct bitvec *bv, unsigned int n); int16_t bitvec_get_int16_msb(const struct bitvec *bv, unsigned int num_bits); +unsigned int bitvec_add_array(struct bitvec *bv, const uint32_t *array, + unsigned int array_len, bool dry_run, + unsigned int num_bits); /*! @} */ diff --git a/src/bitvec.c b/src/bitvec.c index 00ae150..a92fd71 100644 --- a/src/bitvec.c +++ b/src/bitvec.c @@ -570,4 +570,44 @@ void bitvec_shiftl(struct bitvec *bv, unsigned n) bv->cur_bit -= n; } +/*! \brief Add given array to bitvec + * \param[in,out] bv bit vector to work with + * \param[in] array elements to be added + * \param[in] array_len length of array + * \param[in] dry_run indicates whether to return number of bits required + * instead of adding anything to bv for real + * \param[in] num_bits number of bits to consider in each element of array + * \returns number of bits necessary to add array elements if dry_run is true, + * 0 otherwise (only in this case bv is actually changed) + * + * N. B: no length checks are performed on bv - it's caller's job to ensure + * enough space is available - for example by calling with dry_run = true first. + * + * Useful for common pattern in CSN.1 spec which looks like: + * { 1 < XXX : bit (num_bits) > } ** 0 + * which means repeat any times (between 0 and infinity), + * start each repetition with 1, mark end of repetitions with 0 bit + * see app. note in 3GPP TS 24.007 § B.2.1 Rule A2 + */ +unsigned int bitvec_add_array(struct bitvec *bv, const uint32_t *array, + unsigned int array_len, bool dry_run, + unsigned int num_bits) +{ + unsigned i, bits = 1; /* account for stop bit */ + for (i = 0; i < array_len; i++) { + if (dry_run) { + bits += (1 + num_bits); + } else { + bitvec_set_bit(bv, 1); + bitvec_set_uint(bv, array[i], num_bits); + } + } + + if (dry_run) + return bits; + + bitvec_set_bit(bv, 0); /* stop bit - end of the sequence */ + return 0; +} + /*! @} */ diff --git a/tests/bitvec/bitvec_test.c b/tests/bitvec/bitvec_test.c index 76d6773..a98a91c 100644 --- a/tests/bitvec/bitvec_test.c +++ b/tests/bitvec/bitvec_test.c @@ -132,6 +132,43 @@ static void test_unhex(const char *hex) printf("%s\n", hex); } +static inline void test_array_item(unsigned t, struct bitvec *b, unsigned int n, + uint32_t *array, unsigned int p) +{ + unsigned int i, x, y; + bitvec_zero(b); + x = b->cur_bit; + i = bitvec_add_array(b, array, n, true, t); + y = b->cur_bit; + bitvec_add_array(b, array, n, false, t); + printf("\nbits: %u, est: %u, real: %u, x: %u, y: %u\n", + t, i, b->cur_bit, x, y); + for (i = 0; i < p; i++) { + printf(OSMO_BIT_SPEC " ", OSMO_BIT_PRINT(b->data[i])); + if (0 == (i + 1) % 15) + printf("\n"); + } +} + +static void test_array() +{ + struct bitvec b; + uint8_t d[4096]; + b.data = d; + b.data_len = sizeof(d); + + unsigned int i, n = 64; + uint32_t array[n]; + for (i = 0; i < n; i++) { + array[i] = i * i * i + i; + printf("0x%x ", array[i]); + } + + test_array_item(3, &b, n, array, n); + test_array_item(9, &b, n, array, n * 2); + test_array_item(17, &b, n, array, n * 3); +} + int main(int argc, char **argv) { struct bitvec bv; @@ -204,5 +241,11 @@ int main(int argc, char **argv) test_unhex("DEADFACE000000000000000000000000000000BEEFFEED"); test_unhex("FFFFFAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); + printf("arrr...\n"); + + test_array(); + + printf("\nbitvec ok.\n"); + return 0; } diff --git a/tests/bitvec/bitvec_test.ok b/tests/bitvec/bitvec_test.ok index 1c993d3..e256108 100644 --- a/tests/bitvec/bitvec_test.ok +++ b/tests/bitvec/bitvec_test.ok @@ -134,3 +134,36 @@ DEADFACE000000000000000000000000000000BEEFFEED 0 -=> cur_bit=512 fffffaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa FFFFFAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB +arrr... +0x0 0x2 0xa 0x1e 0x44 0x82 0xde 0x15e 0x208 0x2e2 0x3f2 0x53e 0x6cc 0x8a2 0xac6 0xd3e 0x1010 0x1342 0x16da 0x1ade 0x1f54 0x2442 0x29ae 0x2f9e 0x3618 0x3d22 0x44c2 0x4cfe 0x55dc 0x5f62 0x6996 0x747e 0x8020 0x8c82 0x99aa 0xa79e 0xb664 0xc602 0xd67e 0xe7de 0xfa28 0x10d62 0x12192 0x136be 0x14cec 0x16422 0x17c66 0x195be 0x1b030 0x1cbc2 0x1e87a 0x2065e 0x22574 0x245c2 0x2674e 0x28a1e 0x2ae38 0x2d3a2 0x2fa62 0x3227e 0x34bfc 0x376e2 0x3a336 0x3d0fe +bits: 3, est: 257, real: 257, x: 0, y: 0 +1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. 11..1.1. +111.111. 1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. 11..1.1. 111.111. 1...1.1. 1.1.111. +11..1.1. 111.111. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ +bits: 9, est: 641, real: 641, x: 0, y: 0 +1....... ..1..... ..1.1... ..1.1.1. ...1111. 1..1...1 ..1.1... ..1.1.11 .1111.11 .1.1111. 1.....1. ..1.111. ..1.1111 11..1.11 ..11111. +1.11..11 ..1.1.1. ..1.1.11 ...11.11 ..11111. 1....1.. ..11.1.. ..1.1.11 .11.1.1. 11.1111. 11.1.1.1 ..1..1.. ..1.111. 1.111.11 1..1111. +1....11. ..11..1. ..1.1.11 ....1.1. 1111111. 1111.111 ..11.11. ..1.111. .1.11.1. .111111. 1...1... ..1.1... ..1.111. 1.1.1.11 1..1111. +1..11..1 ..1..... ..1.1..1 11111.11 11.1111. 1...1.1. ..11.11. ..1.111. .1..1.1. 1.11111. 1.111.11 ..1...1. ..1.1..1 1..11.11 1.11111. +1...11.. ..1111.. ..1.1..1 111.1.1. .1.1111. 11.111.1 ..1111.. ..1.11.1 ..111.1. ...1111. 1...111. ..111.1. ..1.1..1 1...1.1. .111111. +11111111 ..1.111. ..1.11.. 11.11.1. 1111111. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ +bits: 17, est: 1153, real: 1153, x: 0, y: 0 +1....... ........ ..1..... ........ ..1.1... ........ ..1.1.1. ........ ...1111. 1....... ...1...1 ..1..... ....1... ..1.1... ......11 +.1111.1. .......1 .1.1111. 1....... 1.....1. ..1..... ..1.111. ..1.1... ....1111 11..1.1. .....1.1 ..11111. 1......1 1.11..11 ..1..... +1...1.1. ..1.1... ..1.1.11 ...11.1. ....11.1 ..11111. 1....1.. .....1.. ..1....1 ..11.1.. ..1.1... .1.11.11 .11.1.1. ...11.1. 11.1111. +1....111 11.1.1.1 ..1...1. .1...1.. ..1.1... 1.1..11. 1.111.1. ..1.1111 1..1111. 1...11.1 1....11. ..1...11 11.1..1. ..1.1..1 ...1..11 +....1.1. .1..11.. 1111111. 1..1.1.1 .111.111 ..1..1.1 1111.11. ..1.1..1 1.1..11. .1.11.1. .111.1.. .111111. 1.1..... ....1... ..1.1... +11..1... ..1.1.1. .11..11. 1.1.1.1. 1.1..111 1..1111. 1.1.11.1 1..11..1 ..1.11.. .11..... ..1.1.11 .1.11..1 11111.1. 111..111 11.1111. +1.11111. 1...1.1. ..11.... 11.1.11. ..1.11.. 1....11. .1..1.11 ..11.11. 1.11111. 11.1..11 ..111.11 ..11.11. .1....1. ..1.11.1 1111...1 +1..11.11 1..1.1.1 1.11111. 111.11.. ....11.. ..1111.. 1.1111.. ..1.1111 1.1....1 111.1.1. .....11. .1.1111. 1...1..1 .1.111.1 ..1..1.. +.1.111.. ..1.1..1 1..111.1 ..111.1. 1...1.1. ...1111. 1.1.1.11 1...111. ..1.11.1 ..111.1. ..1.1.11 111.1..1 1...1.11 ..1...1. .111111. +11.1..1. 11111111 ..11.111 .11.111. ..1.111. 1...11.. 11.11.11 11.1.... 1111111. ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ +bitvec ok. -- 2.7.3