Re: [PATCH] Add compression algorithm based on T.4 procedure

This patch includes the changes for compression algorithm and the compression is carried out using T.4 run length coding and the code words used are based on 3GPP 44.060 --- include/osmocom/core/bitcomp.h | 7 +++ src/bitcomp.c | 129 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 136 insertions(+) diff --git a/include/osmocom/core/bitcomp.h b/include/osmocom/core/bitcomp.h index 89eccbc..c5c223c 100644 --- a/include/osmocom/core/bitcomp.h +++ b/include/osmocom/core/bitcomp.h @@ -39,4 +39,11 @@ 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, + uint16_t *ucmp_bmplen, //Uncompressed bitmap len + uint8_t *cmp_bmplen, //Compressed bitmap len + uint8_t *crbb_bitmap //Compressed bitmap + ); /*! @} */ diff --git a/src/bitcomp.c b/src/bitcomp.c index bf35927..f3326b2 100644 --- a/src/bitcomp.c +++ b/src/bitcomp.c @@ -476,5 +476,134 @@ int osmo_t4_encode(struct bitvec *bv) } return -1; } +void compress_bitmap( + uint16_t *run_len_cnt, /* cnt: run length count */ + uint16_t *codewrd_bitmap, /* code word */ + uint8_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; + } + } +} + +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 */ + ) +{ + char run_len_bit; + int buflen = *ucmp_bmplen; + uint16_t rlen; + uint16_t temprl = 0; + uint16_t cbmap; /* Compressed code word */ + uint8_t nbits; /* Length of code word */ + uint16_t cstrtbits = 0; + uint8_t cstrtocts = 0; + uint16_t uclen = 0; + uint8_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(rbb_vec, true); + else + rlen = bitvec_rl(rbb_vec, false); + + buflen = buflen - rlen; + /* if rlen> 64 need 2 code words */ + //Compress the bits + if (run_len_bit == 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 { + if (rlen >= 64) { + temprl = (rlen/64)*64; + clr_code = 1; + 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; + } + *cmp_bmplen = clen; + if (clen >= uclen) { + /* No Gain is observed, So no need to compress, copy original + * bitmap in uncompressed bitmap + */ + return 0; + } else { + /* Add compressed bitmap to final buffer */ + return 1; + } +}