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.orgReview 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>