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/.
prasadkg gerrit-no-reply at lists.osmocom.org
Review at https://gerrit.osmocom.org/415
Add T.4 compression routines
Functions for bitmap compression for PUAN is added
The compression algorithm is as described in 44.060
Change-Id: Iae153d3639ea6b891c1fc10d7801a435c9492e26
---
M include/osmocom/core/bitcomp.h
M include/osmocom/core/bitvec.h
M src/bitcomp.c
M src/bitvec.c
4 files changed, 190 insertions(+), 0 deletions(-)
git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/15/415/1
diff --git a/include/osmocom/core/bitcomp.h b/include/osmocom/core/bitcomp.h
index 89eccbc..13a6d08 100644
--- a/include/osmocom/core/bitcomp.h
+++ b/include/osmocom/core/bitcomp.h
@@ -39,4 +39,13 @@
int osmo_t4_encode(struct bitvec *bv);
int osmo_t4_decode(const struct bitvec *in, bool cc, struct bitvec *out);
+#define MOD64(X) ((X + 64) & 0x3F)
+int osmo_bitmap_compress(
+ struct bitvec *rbb_vec,/*!< input bitvector to compress */
+ uint16_t *ucmp_bmplen, /*!< Uncompressed bitmap len */
+ uint8_t *cmp_bmplen, /*!< Compressed bitmap len */
+ uint8_t *crbb_bitmap, /*!< Compressed bitmap */
+ uint16_t *uclen_crbb, /*!< Uncompressed bitmap len in CRBB */
+ uint16_t max_bits /*!< Maximum remaining bits */
+ );
/*! @} */
diff --git a/include/osmocom/core/bitvec.h b/include/osmocom/core/bitvec.h
index c3c1153..29e2f10 100644
--- a/include/osmocom/core/bitvec.h
+++ b/include/osmocom/core/bitvec.h
@@ -89,6 +89,7 @@
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);
+unsigned bitvec_rl_curbit(struct bitvec *bv, bool b, int max_bits);
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,
diff --git a/src/bitcomp.c b/src/bitcomp.c
index 8b3090e..d3b40d6 100644
--- a/src/bitcomp.c
+++ b/src/bitcomp.c
@@ -479,4 +479,141 @@
return -1;
}
+void compress_bitmap(
+ uint16_t *run_len_cnt, /* cnt: run length count */
+ uint16_t *codewrd_bitmap, /* code word */
+ int16_t *codewrd_len, /* number of bits in the code word */
+ uint8_t *cbmbuf, /* bitmap buffer to put code word in */
+ uint16_t *cstrtbits, /* start bits to put codeword. start from
+ * 0, the first bit in the first octets
+ * and increment without octets
+ * consideration. i.e. can be more than 7.
+ */
+ uint8_t *cstrtocts, /* start octets to put codeword. start from 0*/
+ uint8_t clr_code)
+{
+ int i = 0;
+ uint16_t bitsleft = 0;
+ uint16_t temp = 0;
+ *codewrd_bitmap = 0;
+ *codewrd_len = 0;
+ if ((*run_len_cnt) >= 64) {
+ for (i = 0; i < 15; i++) {
+ if (t4_make_up_ind[i] == *run_len_cnt) {
+ *codewrd_bitmap = t4_make_up[clr_code][i];
+ *codewrd_len = t4_make_up_length[clr_code][i];
+ }
+ }
+ } else {
+ *codewrd_bitmap = t4_term[clr_code][*run_len_cnt];
+ *codewrd_len = t4_term_length[clr_code][*run_len_cnt];
+ }
+ bitsleft = *codewrd_len;
+ /* Move the codeword_bitmap to left in two bytes*/
+ (*codewrd_bitmap) = (*codewrd_bitmap)<<(16-(*codewrd_len));
+ while (bitsleft != 0) {
+ /* Bring left most bits to right and start shifting by cstrtbits,
+ * we get each bit to update in compressed buffer
+ */
+ temp = (((*codewrd_bitmap) & 0x8000)>>15)<<(7-(*cstrtbits));
+ cbmbuf[*cstrtocts] = cbmbuf[*cstrtocts]|temp;
+
+ (*codewrd_bitmap) = (*codewrd_bitmap)<<1;
+ (*cstrtbits)++;
+ bitsleft--;
+ if ((*cstrtbits) >= 8) {
+ (*cstrtbits) = (*cstrtbits)-8;
+ (*cstrtocts)++;
+ /* init buf */
+ cbmbuf[*cstrtocts] = 0x00;
+ }
+ }
+}
+
+/*! \brief compression algorithm using T4 encoding
+ * the compressed bitmap's are copied in crbb_bitmap
+ * \param[in] rbb_vec bit vector to be encoded
+ * \return 1 if compression is success or 0 for failure
+ */
+int osmo_bitmap_compress(
+ struct bitvec *rbb_vec,
+ uint16_t *ucmp_bmplen, /* Uncompressed bitmap len */
+ uint8_t *cmp_bmplen, /* Compressed bitmap len */
+ uint8_t *crbb_bitmap, /* Compressed bitmap */
+ uint16_t *uclen_crbb, /* Uncompressed bitmap len in CRBB */
+ uint16_t max_bits) /* max remaining bits */
+{
+ bool run_len_bit;
+ int buflen = *ucmp_bmplen;
+ int total_bits = *ucmp_bmplen;
+ uint16_t rlen;
+ uint16_t temprl = 0;
+ uint16_t cbmap = 0; /* Compressed code word */
+ int16_t nbits; /* Length of code word */
+ uint16_t cstrtbits = 0;
+ uint8_t cstrtocts = 0;
+ uint16_t uclen = 0;
+ int16_t clen = 0;
+ uint8_t clr_code = 0;
+
+ run_len_bit = (rbb_vec->data[0] & 0x80)>>7;
+ while (buflen > 0) {
+ temprl = 0;
+ /* Find Run length */
+ if (run_len_bit == 1)
+ rlen = bitvec_rl_curbit(rbb_vec, true, total_bits);
+ else
+ rlen = bitvec_rl_curbit(rbb_vec, false, total_bits);
+ buflen = buflen - rlen;
+ /* if rlen> 64 need 2 code words */
+ /*Compress the bits */
+ if (run_len_bit == 0) {
+ clr_code = 0;
+ if (rlen >= 64) {
+ temprl = (rlen/64)*64;
+ compress_bitmap(&temprl, &cbmap, &nbits,
+ crbb_bitmap, &cstrtbits,
+ &cstrtocts, clr_code);
+ }
+ temprl = MOD64(rlen);
+ compress_bitmap(&temprl,
+ &cbmap, &nbits, crbb_bitmap,
+ &cstrtbits, &cstrtocts, clr_code);
+ /* next time the run length will be Ones */
+ run_len_bit = 1;
+ } else {
+ clr_code = 1;
+ if (rlen >= 64) {
+ temprl = (rlen/64)*64;
+ compress_bitmap(&temprl, &cbmap,
+ &nbits, crbb_bitmap,
+ &cstrtbits, &cstrtocts,
+ clr_code);
+ }
+ temprl = MOD64(rlen);
+ compress_bitmap(&temprl, &cbmap,
+ &nbits, crbb_bitmap,
+ &cstrtbits, &cstrtocts, clr_code);
+
+ /* next time the run length will be Zeros */
+ run_len_bit = 0;
+ }
+ uclen = uclen + (rlen);
+ clen = clen + nbits;
+ /*compressed bitmap exceeds the buffer space */
+ if (clen > max_bits) {
+ uclen = uclen - rlen;
+ clen = clen - nbits;
+ break;
+ }
+ }
+ *cmp_bmplen = clen;
+ *uclen_crbb = uclen;
+ if (clen >= uclen)
+ /* No Gain is observed, So no need to compress */
+ return 0;
+ else
+ /* Add compressed bitmap to final buffer */
+ return 1;
+}
diff --git a/src/bitvec.c b/src/bitvec.c
index 88343c4..4c413ae 100644
--- a/src/bitvec.c
+++ b/src/bitvec.c
@@ -575,6 +575,49 @@
return bv->cur_bit;
}
+/*! \brief Return number (bits) of uninterrupted bit run in vector starting from the current bit
+ * \param[in] bv The boolean vector to work on
+ * \param[in] b The boolean, sequence of 1's or 0's to be checked
+ * \returns Number of consecutive bits of \p b in \p bv
+ */
+unsigned bitvec_rl_curbit(struct bitvec *bv, bool b, int max_bits)
+{
+ unsigned i = 0;
+ int temp_res = 0;
+ int count = 0;
+
+ if (bv->cur_bit % 8 == 0) {
+ for (i = (bv->cur_bit/8); i < (max_bits % 8 ? max_bits/8 + 1 : max_bits/8); i++, count++) {
+ if ((b ? 0xFF : 0) != bv->data[i]) {
+ bv->cur_bit = (count * 8 + leading_bits(bv->data[i], b));
+ return count * 8 + leading_bits(bv->data[i], b);
+ }
+ }
+ bv->cur_bit = (count * 8);
+ return (count * 8);
+ } else {
+ unsigned readIndex = bv->cur_bit;
+ int pos = bv->cur_bit/8;
+ while (bitvec_read_field(bv, &readIndex, 1) == b) {
+ if( bv->cur_bit % 8 > 0)
+ temp_res++;
+ else {
+ pos++;
+ for (i = pos; i < (max_bits % 8 ? max_bits/8 + 1 : max_bits/8); i++, count++) {
+ if ((b ? 0xFF : 0) != bv->data[i]) {
+ bv->cur_bit = (count * 8 + leading_bits(bv->data[i], b) + temp_res) - 1;
+ return count * 8 + leading_bits(bv->data[i], b) + temp_res;
+ }
+ }
+ bv->cur_bit = (temp_res + (count * 8))-1;
+ return temp_res + (count * 8);
+ }
+ }
+ bv->cur_bit--;
+ return temp_res;
+ }
+}
+
/*! \brief Shifts bitvec to the left, n MSB bits lost */
void bitvec_shiftl(struct bitvec *bv, unsigned n)
{
--
To view, visit https://gerrit.osmocom.org/415
To unsubscribe, visit https://gerrit.osmocom.org/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: Iae153d3639ea6b891c1fc10d7801a435c9492e26
Gerrit-PatchSet: 1
Gerrit-Project: libosmocore
Gerrit-Branch: master
Gerrit-Owner: prasadkg <Prasad.Kaup at radisys.com>