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

Max msuraev at sysmocom.de
Tue Apr 12 12:06:35 UTC 2016


Hi.

Thanks for your contribution. Could you please elaborate on the intent
of this function? Can we replace existing osmo_t4_encode() with it?
Having couple of test cases would be helpful in understanding what this
function do and how it's supposed to be used.

On 04/11/2016 02:48 PM, sangamesh sajjan wrote:
> 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;
> +	}
> +}

-- 
Max Suraev <msuraev at sysmocom.de> http://www.sysmocom.de/
======================================================================= 
* sysmocom - systems for mobile communications GmbH
* Alt-Moabit 93 
* 10559 Berlin, Germany
* Sitz / Registered office: Berlin, HRB 134158 B 
* Geschaeftsfuehrer / Managing Directors: Holger Freyther, Harald Welte 



More information about the osmocom-net-gprs mailing list