[PATCH 4/5] 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/OpenBSC@lists.osmocom.org/.

suraev at alumni.ntnu.no suraev at alumni.ntnu.no
Fri Jan 22 15:46:58 UTC 2016


From: Max <msuraev at sysmocom.de>

Add bit filling, shifting and oter functions necessary for bit
compression implementation.

Sponsored-by: On-Waves ehf
---
 include/osmocom/core/bitvec.h |  10 +++-
 src/bitvec.c                  | 128 ++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 131 insertions(+), 7 deletions(-)

diff --git a/include/osmocom/core/bitvec.h b/include/osmocom/core/bitvec.h
index ef65f9e..8078fc8 100644
--- a/include/osmocom/core/bitvec.h
+++ b/include/osmocom/core/bitvec.h
@@ -4,7 +4,7 @@
 
 /* (C) 2009 by Harald Welte <laforge at gnumonks.org>
  * (C) 2012 Ivan Klyuchnikov
- * (C) 2015 by Sysmocom s.f.m.c. GmbH
+ * (C) 2015 by Sysmocom s.f.m.c. GmbH, Author: Max <msuraev at sysmocom.de>
  *
  * All Rights Reserved
  *
@@ -41,6 +41,7 @@
  */
 
 #include <stdint.h>
+#include <stdbool.h>
 
 /*! \brief A single GSM bit
  *
@@ -82,5 +83,12 @@ unsigned int bitvec_pack(struct bitvec *bv, uint8_t *buffer);
 unsigned int bitvec_unpack(struct bitvec *bv, uint8_t *buffer);
 uint64_t bitvec_read_field(struct bitvec *bv, unsigned int read_index, unsigned int len);
 int bitvec_write_field(struct bitvec *bv, unsigned int write_index, uint64_t val, unsigned int len);
+int bitvec_fill(struct bitvec *bv, unsigned int num_bits, enum bit_value fill);
+char bit_value_to_char(enum bit_value v);
+void bitvec_to_string_r(const struct bitvec *bv, char *str);
+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);
 
 /*! @} */
diff --git a/src/bitvec.c b/src/bitvec.c
index 68b8d98..b59d711 100644
--- a/src/bitvec.c
+++ b/src/bitvec.c
@@ -35,7 +35,9 @@
 #include <string.h>
 #include <stdio.h>
 #include <talloc.h>
+#include <stdbool.h>
 
+#include <osmocom/core/bits.h>
 #include <osmocom/core/bitvec.h>
 
 #define BITNUM_FROM_COMP(byte, bit)	((byte*8)+bit)
@@ -225,6 +227,21 @@ int bitvec_set_uint(struct bitvec *bv, unsigned int ui, unsigned int num_bits)
 	return 0;
 }
 
+/*! \brief get multiple bits (num_bits) from beginning of vector (MSB side) */
+int16_t bitvec_get_int16_msb(const struct bitvec *bv, unsigned int num_bits)
+{
+	if (num_bits > 15 || bv->cur_bit < num_bits) return -EINVAL;
+
+	if (num_bits < 9) {
+		return bv->data[0] >> (8 - num_bits);
+	}
+
+	uint8_t tmp[2];
+	memcpy(tmp, bv->data, 2);
+	uint16_t t = osmo_load16be(tmp);
+	return t >> (16 - num_bits);
+}
+
 /*! \brief get multiple bits (based on numeric value) from current pos */
 int bitvec_get_uint(struct bitvec *bv, unsigned int num_bits)
 {
@@ -243,17 +260,26 @@ int bitvec_get_uint(struct bitvec *bv, unsigned int num_bits)
 	return ui;
 }
 
-/*! \brief pad all remaining bits up to num_bits */
-int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit)
+/*! \brief fill num_bits with \fill starting from the current position
+ * returns 0 on success, negative otherwise (out of vector boundary)
+ */
+int bitvec_fill(struct bitvec *bv, unsigned int num_bits, enum bit_value fill)
 {
-	unsigned int i;
-
-	for (i = bv->cur_bit; i <= up_to_bit; i++)
-		bitvec_set_bit(bv, L);
+	unsigned i, stop = bv->cur_bit + num_bits;
+	for (i = bv->cur_bit; i < stop; i++)
+		if (bitvec_set_bit(bv, fill) < 0) return -EINVAL;
 
 	return 0;
 }
 
+/*! \brief pad all remaining bits up to num_bits */
+int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit)
+{
+	int n = up_to_bit - bv->cur_bit + 1;
+	if (n < 1) return 0;
+	return bitvec_fill(bv, n, L);
+}
+
 /*! \brief find first bit set in bit vector */
 int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n,
 			enum bit_value val)
@@ -428,4 +454,94 @@ int bitvec_write_field(struct bitvec *bv, unsigned int write_index, uint64_t val
 	return 0;
 }
 
+/*! \brief convert enum to corresponding character */
+char bit_value_to_char(enum bit_value v)
+{
+	switch (v) {
+	case ZERO: return '0';
+	case ONE: return '1';
+	case L: return 'L';
+	case H: return 'H';
+	}
+	return 'X'; // make compiler happy
+}
+
+/*! \brief prints bit vector to provided string
+ * It's caller's responcibility to ensure that we won't shoot him in the foot.
+ */
+void bitvec_to_string_r(const struct bitvec *bv, char *str)
+{
+	unsigned i, pos = 0;
+	char *cur = str;
+	for (i = 0; i < bv->cur_bit; i++) {
+		if (0 == i % 8) *cur++ = ' ';
+		*cur++ = bit_value_to_char(bitvec_get_bit_pos(bv, i));
+		pos++;
+	}
+	*cur = 0;
+}
+
+/* we assume that x have at least 1 non-b bit */
+static 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 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);
+}
+
+/*! \brief Return number (bits) of uninterrupted run of \b in \bv starting from the MSB */
+unsigned bitvec_rl(const struct bitvec *bv, bool b)
+{
+	unsigned i;
+	for (i = 0; i < (bv->cur_bit % 8 ? bv->cur_bit / 8 + 1 : bv->cur_bit / 8); 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;
+}
+
 /*! @} */
-- 
2.5.0




More information about the OpenBSC mailing list