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

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/osmocom-net-gprs@lists.osmocom.org/.

sangamesh sajjan sangamesh.sajjan at radisys.com
Mon Apr 11 12:48:32 UTC 2016


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;
+	}
+}
-- 
1.7.9.5





More information about the osmocom-net-gprs mailing list