[PATCH] osmo-pcu[master]: Add decoding of compressed bitmap in EPDAN

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/gerrit-log@lists.osmocom.org/.

pravin gerrit-no-reply at lists.osmocom.org
Tue Jul 12 12:14:05 UTC 2016


Hello Jenkins Builder, Holger Freyther,

I'd like you to reexamine a change.  Please visit

    https://gerrit.osmocom.org/416

to look at the new patch set (#2).

Add decoding of compressed bitmap in EPDAN

Implemented tree based algorithm to decode compressed bitmap in EPDAN
as described in section 9.1.10 of 3GPP 44.060.
This algorithm intends to improve the performance over existing method.

Change-Id: Ieae1992ed4b02bb1e09eec2d3de1a030eabd16ce
---
M src/Makefile.am
M src/decoding.cpp
M src/decoding.h
A src/egprs_rlc_compression.cpp
A src/egprs_rlc_compression.h
M src/pcu_main.cpp
6 files changed, 398 insertions(+), 25 deletions(-)


  git pull ssh://gerrit.osmocom.org:29418/osmo-pcu refs/changes/16/416/2

diff --git a/src/Makefile.am b/src/Makefile.am
index 9bdec2f..9b047e7 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -62,7 +62,8 @@
 	rlc.cpp \
 	osmobts_sock.cpp \
 	gprs_codel.c \
-	gprs_coding_scheme.cpp
+	gprs_coding_scheme.cpp \
+	egprs_rlc_compression.cpp
 
 bin_PROGRAMS = \
 	osmo-pcu
@@ -94,7 +95,8 @@
 	pcu_utils.h \
 	cxx_linuxlist.h \
 	gprs_codel.h \
-	gprs_coding_scheme.h
+	gprs_coding_scheme.h \
+	egprs_rlc_compression.h
 
 osmo_pcu_SOURCES = pcu_main.cpp
 
diff --git a/src/decoding.cpp b/src/decoding.cpp
index 7865be0..eeccd72 100644
--- a/src/decoding.cpp
+++ b/src/decoding.cpp
@@ -654,7 +654,6 @@
 	bool have_bitmap;
 	int implicitly_acked_blocks;
 	int ssn = desc->STARTING_SEQUENCE_NUMBER;
-	int rc;
 
 	if (desc->FINAL_ACK_INDICATION)
 		return handle_final_ack(bits, bsn_begin, bsn_end, window);
@@ -694,27 +693,11 @@
 
 	if (crbb_len > 0) {
 		int old_len = bits->cur_bit;
-		struct bitvec crbb;
 
-		crbb.data = (uint8_t *)desc->CRBB;
-		crbb.data_len = sizeof(desc->CRBB);
-		crbb.cur_bit = desc->CRBB_LENGTH;
-
-		rc = osmo_t4_decode(&crbb, desc->CRBB_STARTING_COLOR_CODE,
-			bits);
-
-		if (rc < 0) {
-			LOGP(DRLCMACUL, LOGL_NOTICE,
-				"Failed to decode CRBB: "
-				"length %d, data '%s'\n",
-				desc->CRBB_LENGTH,
-				osmo_hexdump(crbb.data, crbb.data_len));
-			/* We don't know the SSN offset for the URBB,
-			 * return what we have so far and assume the
-			 * bitmap has stopped here */
-			goto aborted;
-		}
-
+		LOGP(DRLCMACDL, LOGL_DEBUG, "Compress bitmap exist,"
+			"CRBB LEN =%d and Starting color code =%d",
+			desc->CRBB_LENGTH, desc->CRBB_STARTING_COLOR_CODE);
+		decompress_crbb(desc->CRBB_LENGTH, desc->CRBB_STARTING_COLOR_CODE, desc->CRBB, bits);
 		LOGP(DRLCMACDL, LOGL_DEBUG,
 			"CRBB len: %d, decoded len: %d, cc: %d, crbb: '%s'\n",
 			desc->CRBB_LENGTH, bits->cur_bit - old_len,
diff --git a/src/decoding.h b/src/decoding.h
index d1371d5..7df0a93 100644
--- a/src/decoding.h
+++ b/src/decoding.h
@@ -76,6 +76,12 @@
 		struct gprs_rlc_dl_window *window);
 	static int decode_gprs_acknack_bits(
 		const Ack_Nack_Description_t *desc,
-		bitvec *bits, int *bsn_begin, int *bsn_end,
-		gprs_rlc_dl_window *window);
+		bitvec * bits, int *bsn_begin, int *bsn_end,
+		gprs_rlc_dl_window * window);
+	static void decompress_crbb(
+			int8_t compress_bmap_len,
+			uint8_t clr_code_bit,
+			const uint8_t *orig_buf,
+			bitvec * dest
+			);
 };
diff --git a/src/egprs_rlc_compression.cpp b/src/egprs_rlc_compression.cpp
new file mode 100644
index 0000000..7bb7042
--- /dev/null
+++ b/src/egprs_rlc_compression.cpp
@@ -0,0 +1,313 @@
+/* egprs_rlc_compression.h
+*  Routines for EGPRS RLC bitmap compression handling
+*/
+#include <egprs_rlc_compression.h>
+#include <errno.h>
+#include <decoding.h>
+
+egprs_compress *egprs_compress::s_instance = 0;
+Node *egprs_compress::ones_list = NULL;
+Node *egprs_compress::zeros_list = NULL;
+
+void egprs_compress::build_codeword(Node *root, const char *cdwd[])
+{
+	Node *iter; /* iterate the node on the tree */
+	int  len;    /* length of the code word */
+	int  i;      /* iterater */
+	uint16_t  idx;    /* interate index of the code word table */
+
+	root->left = NULL;
+	root->right = NULL;
+	root->run_length = NULL;
+
+	for (idx = 0; idx < MAX_CDWDTBL_LEN; idx++) {
+		len = strlen((const char *)cdwd[idx]);
+		iter = root;
+		for (i = 0;  i < len;  i++) {
+			if (cdwd[idx][i] == '0') {
+				if (iter->left == NULL) {
+					iter->left = (Node *)malloc(sizeof(Node));
+				 /* create a clean node */
+					iter->left->left = NULL;
+					iter->left->right = NULL;
+					iter->left->run_length = NULL;
+				}
+				iter = iter->left;
+			} else if (cdwd[idx][i] == '1') {
+				if (iter->right == NULL) {
+				iter->right = (Node *)malloc(sizeof(Node));
+				/* create a clean node */
+				iter->right->left = NULL;
+				iter->right->right = NULL;
+				iter->right->run_length = NULL;
+				}
+				iter = iter->right;
+			}
+		}
+		if (iter != NULL) {
+			iter->run_length = (uint16_t *)malloc(sizeof(uint16_t));
+			*(iter->run_length) = (uint16_t)NULL;
+			if (idx < 64)
+				*(iter->run_length) = idx;
+			else
+				*(iter->run_length) = (idx - 63) * 64;
+		}
+	}
+}
+
+const char *one_run_len_code_list[MAX_CDWDTBL_LEN] = {
+	"00110101",
+	"000111",
+	"0111",
+	"1000",
+	"1011",
+	"1100",
+	"1110",
+	"1111",
+	"10011",
+	"10100",
+	"00111",
+	"01000",
+	"001000",
+	"000011",
+	"110100",
+	"110101",
+	"101010",
+	"101011",
+	"0100111",
+	"0001100",
+	"0001000",
+	"0010111",
+	"0000011",
+	"0000100",
+	"0101000",
+	"0101011",
+	"0010011",
+	"0100100",
+	"0011000",
+	"00000010",
+	"00000011",
+	"00011010",
+	"00011011",
+	"00010010",
+	"00010011",
+	"00010100",
+	"00010101",
+	"00010110",
+	"00010111",
+	"00101000",
+	"00101001",
+	"00101010",
+	"00101011",
+	"00101100",
+	"00101101",
+	"00000100",
+	"00000101",
+	"00001010",
+	"00001011",
+	"01010010",
+	"01010011",
+	"01010100",
+	"01010101",
+	"00100100",
+	"00100101",
+	"01011000",
+	"01011001",
+	"01011010",
+	"01011011",
+	"01001010",
+	"01001011",
+	"00110010",
+	"00110011",
+	"00110100",
+	"11011",
+	"10010",
+	"010111",
+	"0110111",
+	"00110110",
+	"00110111",
+	"01100100",
+	"01100101",
+	"01101000",
+	"01100111",
+	"011001100",
+	"011001101",
+	"011010010",
+	"011010011",
+	"011010100"
+};
+
+const char *zero_run_len_code_list[MAX_CDWDTBL_LEN] = {
+	"0000110111",
+	"10",
+	"11",
+	"010",
+	"011",
+	"0011",
+	"0010",
+	"00011",
+	"000101",
+	"000100",
+	"0000100",
+	"0000101",
+	"0000111",
+	"00000100",
+	"00000111",
+	"000011000",
+	"0000010111",
+	"0000011000",
+	"0000001000",
+	"00001100111",
+	"00001101000",
+	"00001101100",
+	"00000110111",
+	"00000101000",
+	"00000010111",
+	"00000011000",
+	"000011001010",
+	"000011001011",
+	"000011001100",
+	"000011001101",
+	"000001101000",
+	"000001101001",
+	"000001101010",
+	"000001101011",
+	"000011010010",
+	"000011010011",
+	"000011010100",
+	"000011010101",
+	"000011010110",
+	"000011010111",
+	"000001101100",
+	"000001101101",
+	"000011011010",
+	"000011011011",
+	"000001010100",
+	"000001010101",
+	"000001010110",
+	"000001010111",
+	"000001100100",
+	"000001100101",
+	"000001010010",
+	"000001010011",
+	"000000100100",
+	"000000110111",
+	"000000111000",
+	"000000100111",
+	"000000101000",
+	"000001011000",
+	"000001011001",
+	"000000101011",
+	"000000101100",
+	"000001011010",
+	"000001100110",
+	"000001100111",
+	"0000001111",
+	"000011001000",
+	"000011001001",
+	"000001011011",
+	"000000110011",
+	"000000110100",
+	"000000110101",
+	"0000001101100",
+	"0000001101101",
+	"0000001001010",
+	"0000001001011",
+	"0000001001100",
+	"0000001001101",
+	"0000001110010",
+	"0000001110011"
+};
+
+int search_runlen(
+		Node    *root,		/* root of Ones or Zeros tree */
+		const uint8_t *bmbuf,	/* Received compressed bitmap buf */
+		uint8_t bit_pos,	/* the start bit pos to read codeword */
+		uint8_t *len_codewd,    /* length of code word */
+		uint16_t *rlen)
+{
+	Node *iter;
+	uint8_t dir;
+
+	iter = root;
+	*len_codewd = 0;
+
+	while (iter->run_length == 0) {
+		if ((iter->left == NULL) && (iter->right == NULL))
+			return -1;
+
+	/* get the bit value at the bitpos and put it in right most of dir */
+		dir = ((bmbuf[BITS_TO_BYTES(bit_pos)-1]
+				>>(7-(MOD8(bit_pos)))) & 0x01);
+		(bit_pos)++;
+		(*len_codewd)++;
+
+		if (((dir&0x01) == 0) && (iter->left != NULL))
+			iter = iter->left;
+
+		else if (((dir&0x01) == 1) && (iter->right != NULL))
+			iter = iter->right;
+		else
+			return -1;
+	}
+	(*rlen) = *(iter->run_length);
+
+	return 1;
+} /* search_runlen */
+
+void Decoding::decompress_crbb(
+	int8_t compress_bmap_len, /* compressed bitmap length */
+	uint8_t clr_code_bit, /* run length of Ones or Zeros */
+	const uint8_t *orig_crbb_buf, /* received block crbb bitmap */
+	bitvec * dest)
+{
+
+	uint8_t bit_pos = 0;
+	uint8_t nbits = 0; /* number of bits of codeword */
+	uint16_t run_length = 0;
+	uint16_t cbmaplen = 0; /* compressed bitmap part after decompression */
+	unsigned wp = dest->cur_bit;
+	egprs_compress *compress = egprs_compress::instance();
+
+	while (compress_bmap_len > 0) {
+		if (clr_code_bit == 1) {
+			search_runlen(compress->ones_list, orig_crbb_buf,
+					bit_pos, &nbits, &run_length);
+		       /*If run length > 64, need makeup and terminating code*/
+			if (run_length < 64)
+				clr_code_bit = 0;
+			cbmaplen = cbmaplen + run_length;
+			/* put run length of Ones in uncompressed bitmap */
+			while (run_length != 0) {
+				if (run_length > 8) {
+					bitvec_write_field(dest, wp, 0xff, 8);
+					run_length = run_length - 8;
+				} else {
+					bitvec_write_field(dest, wp, 0xff,
+								run_length);
+					run_length = 0;
+				}
+			}
+		} else {
+			search_runlen(compress->zeros_list, orig_crbb_buf,
+					 bit_pos, &nbits, &run_length);
+			/*If run length > 64, need makeup and terminating code*/
+			if (run_length < 64)
+				clr_code_bit = 1;
+			cbmaplen = cbmaplen + run_length;
+			/* put run length of Zeros in uncompressed bitmap */
+			while (run_length != 0) {
+				if (run_length > 8) {
+					bitvec_write_field(dest, wp, 0x00, 8);
+					run_length = run_length - 8;
+				} else {
+					bitvec_write_field(dest, wp, 0x00,
+								 run_length);
+					run_length = 0;
+				}
+			}
+		}
+		bit_pos = bit_pos + nbits;
+		compress_bmap_len = compress_bmap_len - nbits;
+	}
+} /* Decompress_CRBB */
diff --git a/src/egprs_rlc_compression.h b/src/egprs_rlc_compression.h
new file mode 100644
index 0000000..1d21531
--- /dev/null
+++ b/src/egprs_rlc_compression.h
@@ -0,0 +1,66 @@
+/* egprs_rlc_compression.h
+ *  Routines for EGPRS RLC bitmap compression handling
+ */
+#include <gprs_rlcmac.h>
+#include <gprs_debug.h>
+
+extern "C" {
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/msgb.h>
+#include <osmocom/core/stats.h>
+}
+
+#include <arpa/inet.h>
+#include <errno.h>
+#include <string.h>
+
+#define	MAX_CDWDTBL_LEN          79        /* total number of codewords */
+#define	BITS_TO_BYTES(X)      ((X ? (X/8):0)+1)
+#define	MOD8(X)             (((X)+8) & (0x07))
+
+typedef struct node {
+	struct node *left;
+	struct node *right;
+	uint16_t *run_length;
+} Node;
+
+extern const char *one_run_len_code_list[MAX_CDWDTBL_LEN];
+extern const char *zero_run_len_code_list[MAX_CDWDTBL_LEN];		
+extern void *tall_pcu_ctx;
+
+/* Creating singleton class
+ */
+class egprs_compress
+{
+	static egprs_compress *s_instance;
+	
+	egprs_compress()
+	{
+		ones_list = talloc(tall_pcu_ctx, Node);
+		zeros_list = talloc(tall_pcu_ctx, Node);
+	}
+	void build_codeword(Node *root, const char *cdwd[]);
+	~egprs_compress()
+	{
+		talloc_free(ones_list);
+		talloc_free(zeros_list);
+	}
+public:
+	static Node *ones_list;
+	static Node *zeros_list;
+
+	void decode_tree_init(void)
+	{
+		instance()->build_codeword(
+			ones_list, one_run_len_code_list);
+		instance()->build_codeword(
+			zeros_list, zero_run_len_code_list);
+	}
+	static egprs_compress *instance()
+	{
+		if (!s_instance)
+			s_instance = new egprs_compress;
+
+		return s_instance;
+	}
+};
diff --git a/src/pcu_main.cpp b/src/pcu_main.cpp
index 2d86cda..c3e4a7f 100644
--- a/src/pcu_main.cpp
+++ b/src/pcu_main.cpp
@@ -28,6 +28,7 @@
 #include <signal.h>
 #include <sched.h>
 #include <bts.h>
+#include <egprs_rlc_compression.h>
 extern "C" {
 #include "pcu_vty.h"
 #include <osmocom/vty/telnet_interface.h>
@@ -253,6 +254,8 @@
 	if (!bts->alloc_algorithm)
 		bts->alloc_algorithm = alloc_algorithm_dynamic;
 
+	egprs_compress::instance()->decode_tree_init();
+
 	rc = pcu_l1if_open();
 
 	if (rc < 0)

-- 
To view, visit https://gerrit.osmocom.org/416
To unsubscribe, visit https://gerrit.osmocom.org/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ieae1992ed4b02bb1e09eec2d3de1a030eabd16ce
Gerrit-PatchSet: 2
Gerrit-Project: osmo-pcu
Gerrit-Branch: master
Gerrit-Owner: pravin <pravin.manoharan at radisys.com>
Gerrit-Reviewer: Holger Freyther <holger at freyther.de>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: Max <msuraev at sysmocom.de>
Gerrit-Reviewer: pravin <pravin.manoharan at radisys.com>



More information about the gerrit-log mailing list