EGPRS: Add EPDAN CRBB Tree based decoding

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.
New Regression test is added under bitcomp directory.
Test case is added to validate decompressed result of the bitmap
Present in EPDAN.
Test is done for multiple bitmaps of varying length.
Invalid inputs are also part of the test vector.

Change-Id: Ieae1992ed4b02bb1e09eec2d3de1a030eabd16ce

5 files changed, 384 insertions, 1 deletions

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 2a3415e..a24f4ea 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1,7 +1,7 @@
 AM_CPPFLAGS = $(STD_DEFINES_AND_INCLUDES) $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGB_CFLAGS) $(LIBOSMOGSM_CFLAGS) -I$(top_srcdir)/src/
 AM_LDFLAGS = -lrt
 
-check_PROGRAMS = rlcmac/RLCMACTest alloc/AllocTest tbf/TbfTest types/TypesTest ms/MsTest llist/LListTest llc/LlcTest codel/codel_test edge/EdgeTest
+check_PROGRAMS = rlcmac/RLCMACTest alloc/AllocTest tbf/TbfTest types/TypesTest ms/MsTest llist/LListTest llc/LlcTest codel/codel_test edge/EdgeTest bitcomp/BitcompTest
 noinst_PROGRAMS = emu/pcu_emu
 
 rlcmac_RLCMACTest_SOURCES = rlcmac/RLCMACTest.cpp
@@ -26,6 +26,11 @@ tbf_TbfTest_LDADD = \
 	$(LIBOSMOCORE_LIBS) \
 	$(COMMON_LA)
 
+bitcomp_BitcompTest_SOURCES = bitcomp/BitcompTest.cpp ../src/egprs_rlc_compression.cpp
+bitcomp_BitcompTest_LDADD = \
+	$(LIBOSMOCORE_LIBS) \
+	$(COMMON_LA)
+
 edge_EdgeTest_SOURCES = edge/EdgeTest.cpp
 edge_EdgeTest_LDADD = \
 	$(top_builddir)/src/libgprs.la \
@@ -108,6 +113,7 @@ EXTRA_DIST = \
 	rlcmac/RLCMACTest.ok rlcmac/RLCMACTest.err \
 	alloc/AllocTest.ok alloc/AllocTest.err \
 	tbf/TbfTest.ok tbf/TbfTest.err \
+	bitcomp/BitcompTest.ok bitcomp/BitcompTest.err \
 	types/TypesTest.ok types/TypesTest.err \
 	ms/MsTest.ok ms/MsTest.err \
 	llc/LlcTest.ok llc/LlcTest.err \
diff --git a/tests/bitcomp/BitcompTest.cpp b/tests/bitcomp/BitcompTest.cpp
new file mode 100644
index 0000000..fd3b0df
--- /dev/null
+++ b/tests/bitcomp/BitcompTest.cpp
@@ -0,0 +1,236 @@
+#include <stdint.h>
+#include <string.h>
+
+#include "rlc.h"
+#include "gprs_debug.h"
+#include <gprs_rlcmac.h>
+#include "egprs_rlc_compression.h"
+
+extern "C" {
+#include <osmocom/core/logging.h>
+#include <osmocom/core/bitvec.h>
+#include <osmocom/core/utils.h>
+#include <osmocom/core/application.h>
+}
+
+#define NEW 1
+#define MASK(n) (0xFF << (8-n))
+#define MAX_CRBB_LEN 23
+#define MAX_URBB_LEN 40
+
+void *tall_pcu_ctx;
+
+struct test_data {
+	int8_t crbb_len;
+	uint8_t cc;
+	uint8_t crbb_data[MAX_CRBB_LEN]; /* compressed data */
+	uint8_t ucmp_data[MAX_URBB_LEN]; /* uncompressed data */
+	int ucmp_len;
+	int verify;
+} test[] = {
+		{ .crbb_len = 67, .cc = 1,
+			.crbb_data = {
+			0x02, 0x0c, 0xa0, 0x30, 0xcb, 0x1a, 0x0c, 0xe3, 0x6c
+			},
+			.ucmp_data = {
+			0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x01, 0xff, 0xff,
+			0xff, 0xf8, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfe,
+			0x00, 0x00, 0x3f, 0xff, 0xff, 0xff, 0xdb
+			},
+			.ucmp_len = 194, .verify = 1
+		},
+		{ .crbb_len = 40, .cc = 1,
+			.crbb_data = {
+			0x53, 0x06, 0xc5, 0x40, 0x6d
+			},
+			.ucmp_data = {
+			0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00,
+			0x00, 0x00, 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8,
+			0x00, 0x00, 0x00, 0x00, 0x03
+			},
+			.ucmp_len = 182, .verify = 1
+		},
+		{ .crbb_len = 8, .cc = 1,
+			.crbb_data = {0x02},
+			.ucmp_data = {0xff, 0xff, 0xff, 0xf8},
+			.ucmp_len = 29, .verify = 1
+		},
+		{ .crbb_len = 103, .cc = 1,
+			.crbb_data = {
+			0x02, 0x0c, 0xe0, 0x41, 0xa0, 0x0c, 0x36, 0x0d, 0x03,
+			0x71, 0xb0, 0x6e, 0x24
+			},
+			.ucmp_data = {
+			0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0xff, 0xff, 0xff,
+			0xf8, 0x00, 0x00, 0x7f, 0xff, 0xff, 0xfe, 0x00, 0x00,
+			0x0f, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x7f, 0xff,
+			0xff, 0xff, 0x80, 0x00, 0x01, 0xff, 0xff, 0xff, 0xff
+			},
+			.ucmp_len = 288, .verify = 1
+		},
+		/* Test vector from libosmocore test */
+		{ .crbb_len = 35, .cc = 0,
+			.crbb_data = {0xde, 0x88, 0x75, 0x65, 0x80},
+			.ucmp_data = {0x37, 0x47, 0x81, 0xf0},
+			.ucmp_len = 28, .verify = 1
+		},
+		{ .crbb_len = 18, .cc = 1,
+			.crbb_data = {0xdd, 0x41, 0x00},
+			.ucmp_data = {
+			0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+			0xff, 0x00, 0x00
+			},
+			.ucmp_len = 90, .verify = 1
+		},
+		/*Invalid inputs*/
+		{ .crbb_len = 18, .cc = 1,
+			.crbb_data = {0x1E, 0x70, 0xc0},
+			.ucmp_data = {0x0},
+			.ucmp_len = 0, .verify = 0
+		},
+		{ .crbb_len = 14, .cc = 1,
+			.crbb_data = {0x00, 0x1E, 0x7c},
+			.ucmp_data = {0x0},
+			.ucmp_len = 0, .verify = 0
+		},
+		{ .crbb_len = 24, .cc = 0,
+			.crbb_data = {0x00, 0x00, 0x00},
+			.ucmp_data = {0x0},
+			.ucmp_len = 0, .verify = 0
+		}
+	};
+
+static const struct log_info_cat default_categories[] = {
+	{"DCSN1", "\033[1;31m", "Concrete Syntax Notation One (CSN1)", LOGL_INFO, 0},
+	{"DL1IF", "\033[1;32m", "GPRS PCU L1 interface (L1IF)", LOGL_DEBUG, 1},
+	{"DRLCMAC", "\033[0;33m", "GPRS RLC/MAC layer (RLCMAC)", LOGL_DEBUG, 1},
+	{"DRLCMACDATA", "\033[0;33m", "GPRS RLC/MAC layer Data (RLCMAC)", LOGL_DEBUG, 1},
+	{"DRLCMACDL", "\033[1;33m", "GPRS RLC/MAC layer Downlink (RLCMAC)", LOGL_DEBUG, 1},
+	{"DRLCMACUL", "\033[1;36m", "GPRS RLC/MAC layer Uplink (RLCMAC)", LOGL_DEBUG, 1},
+	{"DRLCMACSCHED", "\033[0;36m", "GPRS RLC/MAC layer Scheduling (RLCMAC)", LOGL_DEBUG, 1},
+	{"DRLCMACMEAS", "\033[1;31m", "GPRS RLC/MAC layer Measurements (RLCMAC)", LOGL_INFO, 1},
+	{"DNS", "\033[1;34m", "GPRS Network Service Protocol (NS)", LOGL_INFO, 1},
+	{"DBSSGP", "\033[1;34m", "GPRS BSS Gateway Protocol (BSSGP)", LOGL_INFO, 1},
+	{"DPCU", "\033[1;35m", "GPRS Packet Control Unit (PCU)", LOGL_NOTICE, 1},
+};
+
+static int filter_fn(const struct log_context *ctx,
+			struct log_target *tar)
+{
+	return 1;
+}
+
+/* To verify the result with expected result */
+int check_result(bitvec bits, uint8_t *exp_data, int exp_len)
+{
+	if (bits.cur_bit != exp_len)
+		return 0;
+	size_t n = (exp_len / 8);
+	int rem = (exp_len % 8);
+
+	if (memcmp(exp_data, bits.data, n) == 0) {
+		if (rem == 0)
+			return 1;
+		if ((bits.data[n] & MASK(rem)) == ((*(exp_data + n)) & MASK(rem)))
+			return 1;
+		else
+			return 0;
+	} else
+		return 0;
+}
+
+/*  To test decoding of compressed bitmap by Tree based method
+ *  and to verify the result with expected result
+ *  for invalid input verfication is suppressed
+ */
+static void test_EPDAN_decode_tree(void)
+{
+	bitvec dest;
+	int init_flag = 1;
+	int itr;
+	int rc;
+	uint8_t bits_data[RLC_EGPRS_MAX_WS/8];
+
+	printf("=== start %s ===\n", __func__);
+
+	for (itr = 0 ; itr < (sizeof(test) / sizeof(test_data)) ; itr++) {
+		dest.data = bits_data;
+		dest.data_len = sizeof(bits_data);
+		dest.cur_bit = 0;
+		memset(dest.data, 0, sizeof(bits_data));
+		LOGP(DRLCMACDL, LOGL_DEBUG, "\nTest:%d\nTree based decoding:"
+			"\nuncompressed data = %s\nlen = %d\n", itr + 1,
+			osmo_hexdump(test[itr].crbb_data,
+			(test[itr].crbb_len + 7)/8), test[itr].crbb_len
+		);
+		rc = egprs_compress::decompress_crbb(test[itr].crbb_len,
+			test[itr].cc, test[itr].crbb_data, &dest);
+		if (rc < 0) {
+			LOGP(DRLCMACUL, LOGL_NOTICE,
+				"\nFailed to decode CRBB: length %d, data %s",
+				test[itr].crbb_len, osmo_hexdump(
+				test[itr].crbb_data, (test[itr].crbb_len + 7)/8));
+		}
+		if (init_flag)
+			init_flag = 0;
+		if (test[itr].verify) {
+			if (check_result(dest, test[itr].ucmp_data,
+				test[itr].ucmp_len) == 0) {
+				LOGP(DRLCMACDL, LOGL_DEBUG, "\nTree based decoding"
+					":Error\nexpected data = %s\nexpected"
+					" len = %d\ndecoded data = %s\n"
+					"decoded len = %d\n",
+					osmo_hexdump(test[itr].ucmp_data,
+						(test[itr].ucmp_len + 7)/8),
+					test[itr].ucmp_len, osmo_hexdump(dest.data,
+						(dest.cur_bit + 7)/8), dest.cur_bit
+				);
+				OSMO_ASSERT(0);
+			}
+		}
+		LOGP(DRLCMACDL, LOGL_DEBUG, "\nexpected data = %s\nexpected len = %d"
+			"\ndecoded data = %s\ndecoded len = %d\n",
+			osmo_hexdump(test[itr].ucmp_data,
+			(test[itr].ucmp_len + 7)/8),
+			test[itr].ucmp_len, osmo_hexdump(dest.data,
+			(dest.cur_bit + 7)/8), dest.cur_bit
+		);
+	}
+
+	printf("=== end %s ===\n", __func__);
+}
+
+const struct log_info debug_log_info = {
+	filter_fn,
+	(struct log_info_cat *)default_categories,
+	ARRAY_SIZE(default_categories),
+};
+
+int main(int argc, char **argv)
+{
+	osmo_init_logging(&debug_log_info);
+	log_set_use_color(osmo_stderr_target, 0);
+	log_set_print_filename(osmo_stderr_target, 0);
+
+	tall_pcu_ctx = talloc_named_const(NULL, 1, "moiji-mobile bitcompTest context");
+	if (!tall_pcu_ctx)
+		abort();
+
+	test_EPDAN_decode_tree();
+
+	if (getenv("TALLOC_REPORT_FULL"))
+		talloc_report_full(tall_pcu_ctx, stderr);
+	talloc_free(tall_pcu_ctx);
+	return EXIT_SUCCESS;
+}
+
+/*
+ * stubs that should not be reached
+ */
+extern "C" {
+void l1if_pdch_req() { abort(); }
+void l1if_connect_pdch() { abort(); }
+void l1if_close_pdch() { abort(); }
+void l1if_open_pdch() { abort(); }
+}
+
diff --git a/tests/bitcomp/BitcompTest.err b/tests/bitcomp/BitcompTest.err
new file mode 100644
index 0000000..7481d72
--- /dev/null
+++ b/tests/bitcomp/BitcompTest.err
@@ -0,0 +1,132 @@
+
+Test:1
+Tree based decoding:
+uncompressed data = 02 0c a0 30 cb 1a 0c e3 6c 
+len = 67
+Run_length = 29
+Run_length = 26
+Run_length = 30
+Run_length = 27
+Run_length = 31
+Run_length = 19
+Run_length = 32
+
+expected data = ff ff ff f8 00 00 01 ff ff ff f8 00 00 00 ff ff ff fe 00 00 3f ff ff ff db 
+expected len = 194
+decoded data = ff ff ff f8 00 00 01 ff ff ff f8 00 00 00 ff ff ff fe 00 00 3f ff ff ff db 
+decoded len = 194
+
+Test:2
+Tree based decoding:
+uncompressed data = 53 06 c5 40 6d 
+len = 40
+Run_length = 50
+Run_length = 40
+Run_length = 51
+Run_length = 41
+
+expected data = ff ff ff ff ff ff c0 00 00 00 00 3f ff ff ff ff ff f8 00 00 00 00 03 
+expected len = 182
+decoded data = ff ff ff ff ff ff c0 00 00 00 00 3f ff ff ff ff ff f8 00 00 00 00 03 
+decoded len = 182
+
+Test:3
+Tree based decoding:
+uncompressed data = 02 
+len = 8
+Run_length = 29
+
+expected data = ff ff ff f8 
+expected len = 29
+decoded data = ff ff ff f8 
+decoded len = 29
+
+Test:4
+Tree based decoding:
+uncompressed data = 02 0c e0 41 a0 0c 36 0d 03 71 b0 6e 24 
+len = 103
+Run_length = 29
+Run_length = 19
+Run_length = 29
+Run_length = 20
+Run_length = 30
+Run_length = 21
+Run_length = 31
+Run_length = 22
+Run_length = 32
+Run_length = 22
+Run_length = 33
+
+expected data = ff ff ff f8 00 00 ff ff ff f8 00 00 7f ff ff fe 00 00 0f ff ff ff e0 00 00 7f ff ff ff 80 00 01 ff ff ff ff 
+expected len = 288
+decoded data = ff ff ff f8 00 00 ff ff ff f8 00 00 7f ff ff fe 00 00 0f ff ff ff e0 00 00 7f ff ff ff 80 00 01 ff ff ff ff 
+decoded len = 288
+
+Test:5
+Tree based decoding:
+uncompressed data = de 88 75 65 80 
+len = 35
+Run_length = 2
+Run_length = 2
+Run_length = 1
+Run_length = 3
+Run_length = 1
+Run_length = 1
+Run_length = 3
+Run_length = 4
+Run_length = 6
+Run_length = 5
+
+expected data = 37 47 81 f0 
+expected len = 28
+decoded data = 37 47 81 f0 
+decoded len = 28
+
+Test:6
+Tree based decoding:
+uncompressed data = dd 41 00 
+len = 18
+Run_length = 64
+Run_length = 16
+Run_length = 10
+
+expected data = ff ff ff ff ff ff ff ff ff ff 00 00 
+expected len = 90
+decoded data = ff ff ff ff ff ff ff ff ff ff 00 00 
+decoded len = 90
+
+Test:7
+Tree based decoding:
+uncompressed data = 1e 70 c0 
+len = 18
+Run_length = 1
+Run_length = 1
+Run_length = 2
+Run_length = 15
+
+expected data = 
+expected len = 0
+decoded data = 
+decoded len = 19
+
+Test:8
+Tree based decoding:
+uncompressed data = 00 1e 
+len = 14
+
+Failed to decode CRBB: length 14, data 00 1e 
+expected data = 
+expected len = 0
+decoded data = 
+decoded len = 0
+
+Test:9
+Tree based decoding:
+uncompressed data = 00 00 00 
+len = 24
+
+Failed to decode CRBB: length 24, data 00 00 00 
+expected data = 
+expected len = 0
+decoded data = 
+decoded len = 0
diff --git a/tests/bitcomp/BitcompTest.ok b/tests/bitcomp/BitcompTest.ok
new file mode 100644
index 0000000..f7720fc
--- /dev/null
+++ b/tests/bitcomp/BitcompTest.ok
@@ -0,0 +1,2 @@
+=== start test_EPDAN_decode_tree ===
+=== end test_EPDAN_decode_tree ===
diff --git a/tests/testsuite.at b/tests/testsuite.at
index 1049b31..e42a0fd 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -23,6 +23,13 @@ cat $abs_srcdir/tbf/TbfTest.err > experr
 AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/tbf/TbfTest], [0], [expout], [experr])
 AT_CLEANUP
 
+AT_SETUP([bitcomp])
+AT_KEYWORDS([bitcomp])
+cat $abs_srcdir/bitcomp/BitcompTest.ok > expout
+cat $abs_srcdir/bitcomp/BitcompTest.err > experr
+AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/bitcomp/BitcompTest], [0], [expout], [experr])
+AT_CLEANUP
+
 AT_SETUP([edge])
 AT_KEYWORDS([edge])
 cat $abs_srcdir/edge/EdgeTest.ok > expout