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.orgHello Max, 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 (#7). 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. 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 --- 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 M tests/tbf/TbfTest.cpp 7 files changed, 490 insertions(+), 38 deletions(-) git pull ssh://gerrit.osmocom.org:29418/osmo-pcu refs/changes/16/416/7 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 7c00ff7..3f8b11b 100644 --- a/src/decoding.cpp +++ b/src/decoding.cpp @@ -651,11 +651,10 @@ int crbb_len = 0; int num_blocks = 0; struct bitvec urbb; - int i; + int i, rc; 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); @@ -695,27 +694,22 @@ 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); - + LOGP(DRLCMACDL, LOGL_DEBUG, "Compress bitmap exist," + "CRBB LEN =%d and Starting color code =%d", + desc->CRBB_LENGTH, desc->CRBB_STARTING_COLOR_CODE); + rc = decompress_crbb(desc->CRBB_LENGTH, desc->CRBB_STARTING_COLOR_CODE, + desc->CRBB, 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)); + "Failed to decode CRBB: length %d, data '%s'\n", + desc->CRBB_LENGTH, osmo_hexdump( + desc->CRBB, (desc->CRBB_LENGTH + 7)/8)); /* We don't know the SSN offset for the URBB, - * return what we have so far and assume the - * bitmap has stopped here */ + * return what we have so far and assume the + * bitmap has stopped here */ goto aborted; } - 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..cb18fcb 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 int 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..b9e15f2 --- /dev/null +++ b/src/egprs_rlc_compression.cpp @@ -0,0 +1,310 @@ +/* egprs_rlc_compression.h +* Routines for EGPRS RLC bitmap compression handling +*/ +#include <egprs_rlc_compression.h> +#include <errno.h> +#include <decoding.h> + +extern "C" { +#include <osmocom/core/talloc.h> +#include <osmocom/core/msgb.h> +#include <osmocom/core/stats.h> +} + +void *tall_tree_ctx; +egprs_compress *egprs_compress::s_instance = 0; +Node *egprs_compress::ones_list = NULL; +Node *egprs_compress::zeros_list = NULL; + +Node *egprs_compress::create_tree_node() +{ + Node *new_node; + new_node = talloc(tall_tree_ctx, Node); + new_node->left = NULL; + new_node->right = NULL; + new_node->run_length = -1; + return new_node; +} + +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 */ + int idx; /* interate index of the code word table */ + + root->left = NULL; + root->right = NULL; + root->run_length = -1; + + 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 = create_tree_node(); + iter = iter->left; + } else if (cdwd[idx][i] == '1') { + if (iter->right == NULL) + iter->right = create_tree_node(); + iter = iter->right; + } + } + if (iter != 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 == -1) { + 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 */ + +int 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 data = 0x0; + node *list = NULL; + 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; + int rc = 0; + egprs_compress *compress = egprs_compress::instance(); + + while (compress_bmap_len > 0) { + if (clr_code_bit == 1) { + data = 0xff; + list = compress->ones_list; + } else { + data = 0x00; + list = compress->zeros_list; + } + rc = search_runlen(list, orig_crbb_buf, + bit_pos, &nbits, &run_length); + if (rc == -1) + return -1; + /*If run length > 64, need makeup and terminating code*/ + if (run_length < 64) + clr_code_bit ? clr_code_bit = 0 : clr_code_bit = 1; + 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, data, 8); + run_length = run_length - 8; + } else { + bitvec_write_field(dest, wp, data, run_length); + run_length = 0; + } + } + bit_pos = bit_pos + nbits; + compress_bmap_len = compress_bmap_len - nbits; + } + return 0; +} /* Decompress_CRBB */ diff --git a/src/egprs_rlc_compression.h b/src/egprs_rlc_compression.h new file mode 100644 index 0000000..78a6d12 --- /dev/null +++ b/src/egprs_rlc_compression.h @@ -0,0 +1,64 @@ +/* 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 <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; + int 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_tree_ctx; + +/* Creating singleton class + */ +class egprs_compress +{ + static egprs_compress *s_instance; + egprs_compress() + { + ones_list = talloc(tall_tree_ctx, Node); + zeros_list = talloc(tall_tree_ctx, Node); + } + Node *create_tree_node(); + void build_codeword(Node *root, const char *cdwd[]); + void free_codeword(Node *root); + ~egprs_compress() + { + s_instance = NULL; + } +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..ea23ba1 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> @@ -168,6 +169,9 @@ if (!tall_pcu_ctx) return -ENOMEM; bv_tall_ctx = tall_pcu_ctx; + tall_tree_ctx = talloc_named_const(tall_pcu_ctx, 0, "decode-tree context"); + if (!tall_tree_ctx) + return -ENOMEM; bts = bts_main_data(); bts->fc_interval = 1; @@ -253,6 +257,8 @@ if (!bts->alloc_algorithm) bts->alloc_algorithm = alloc_algorithm_dynamic; + egprs_compress::instance()->decode_tree_init(); + rc = pcu_l1if_open(); if (rc < 0) @@ -292,6 +298,5 @@ talloc_report_full(tall_pcu_ctx, stderr); talloc_free(tall_pcu_ctx); - return 0; } diff --git a/tests/tbf/TbfTest.cpp b/tests/tbf/TbfTest.cpp index 1071ba3..03658c7 100644 --- a/tests/tbf/TbfTest.cpp +++ b/tests/tbf/TbfTest.cpp @@ -26,10 +26,11 @@ #include "pcu_utils.h" #include "gprs_bssgp_pcu.h" #include "pcu_l1_if.h" - +#include "egprs_rlc_compression.h" +#include "decoding.h" extern "C" { #include "pcu_vty.h" - +#include <osmocom/core/bitcomp.h> #include <osmocom/core/application.h> #include <osmocom/core/msgb.h> #include <osmocom/core/talloc.h> @@ -39,8 +40,41 @@ #include <errno.h> +#define NUMBER_OF_TEST_CASE 9 +#define NEW 1 +#define DELTA 1000 +#define MASK(n) (0xFF << (8-n)) void *tall_pcu_ctx; +extern void *tall_tree_ctx; int16_t spoof_mnc = 0, spoof_mcc = 0; +struct test_data { + int8_t crbb_len; + uint8_t cc; + uint8_t crbb_data[23]; /* compressed data */ + uint8_t ucmp_data[40]; /* uncompressed data */ + int ucmp_len; + int verify; +}test[NUMBER_OF_TEST_CASE] = { { (int8_t)67, (uint8_t)1, {0x02, 0x0c, 0xa0, 0x30, 0xcb, 0x1a, 0x0c, 0xe3, 0x6c}, + {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}, (int)194, 1}, + {(int8_t)40, (uint8_t)1, {0x53, 0x06, 0xc5, 0x40, 0x6d}, {0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, + 0x00, 0x00, 0x00, 0x03}, (int)182, 1}, + { (int8_t)8, (uint8_t)1, {0x02}, {0xff, 0xff, 0xff, 0xf8}, (int)29, 1}, + { (int8_t)103, (uint8_t)1, {0x02, 0x0c, 0xe0, 0x41, 0xa0, 0x0c, 0x36, 0x0d, 0x03, + 0x71, 0xb0, 0x6e, 0x24}, {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}, + (int)288, 1}, + /* Test vector from libosmocore test */ + { (int8_t)32, (uint8_t)0, {0xde, 0x88, 0x75, 0x65, 0x80}, {0x37, 0x47, 0x81, 0xf0}, (int)28}, + { (int8_t)18, (uint8_t)1, {0xdd, 0x41, 0x00}, {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x00, 0x00}, (int)90, 1}, + /*Invalid inputs*/ + { (int8_t)18, (uint8_t)1, {0x1E, 0x70, 0xc0}, {0x0}, (int)0, 0}, + { (int8_t)14, (uint8_t)1, {0x00, 0x1E, 0x7c}, {0x0}, (int)0, 0}, + { (int8_t)24, (uint8_t)0, {0x00, 0x00, 0x00}, {0x0}, (int)0, 0} }; static void check_tbf(gprs_rlcmac_tbf *tbf) { @@ -51,19 +85,52 @@ OSMO_ASSERT(tbf->T != 0); } -/* -static unsigned inc_fn(fn) +/* To verify the result with expected result */ +int check_result(bitvec bits, uint8_t *exp_data, int exp_len) { - unsigned next_fn; - - next_fn = fn + 4; - if ((block_nr % 3) == 2) - next_fn ++; - next_fn = next_fn % 2715648; - - return next_fn; + 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() +{ + bitvec dest; + int init_flag = 1; + int itr; + uint8_t bits_data[RLC_EGPRS_MAX_WS/8]; + + for (itr = 0 ; itr < NUMBER_OF_TEST_CASE ; itr++) { + dest.data = bits_data; + dest.data_len = sizeof(bits_data); + dest.cur_bit = 0; + memset(dest.data, 0, sizeof(bits_data)); + Decoding::decompress_crbb(test[itr].crbb_len, test[itr].cc, test[itr].crbb_data, &dest); + + 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, "Tree based decoding :Error\n"); + OSMO_ASSERT(0); + } + } + } +} static void test_tbf_base() { @@ -1554,7 +1621,9 @@ tall_pcu_ctx = talloc_named_const(NULL, 1, "moiji-mobile TbfTest context"); if (!tall_pcu_ctx) abort(); - + tall_tree_ctx = talloc_named_const(tall_pcu_ctx, 0, "decode-tree context"); + if (!tall_tree_ctx) + abort(); msgb_set_talloc_ctx(tall_pcu_ctx); osmo_init_logging(&debug_log_info); log_set_use_color(osmo_stderr_target, 0); @@ -1563,7 +1632,8 @@ vty_init(&pcu_vty_info); pcu_vty_init(&debug_log_info); - + /*initialization_of_tree*/ + egprs_compress::instance()->decode_tree_init(); test_tbf_base(); test_tbf_tlli_update(); test_tbf_final_ack(TEST_MODE_STANDARD); @@ -1583,9 +1653,10 @@ test_tbf_egprs_two_phase(); test_tbf_egprs_dl(); test_tbf_egprs_retx_dl(); - + test_EPDAN_decode_tree(); if (getenv("TALLOC_REPORT_FULL")) talloc_report_full(tall_pcu_ctx, stderr); + talloc_free(tall_pcu_ctx); return EXIT_SUCCESS; } -- 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: 7 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>