[PATCH 3/3] Decompress the CRBB bitmap using tree based approach

Max msuraev at sysmocom.de
Thu Mar 31 11:04:36 UTC 2016

Hi and thanks for detailed write-up.

So the code do exactly the same thing just more efficiently under the
assumption that gcc optimization is not working.
Is there a way to quantify this potential difference?

More specifically - is there a test-case which could demonstrate that
this difference actually matters in practice?

I mean if the code in question constitute, for example, 10% of cpu time
spent by osmo-pcu and the replacement would shrink it to 2% it's one thing.
If it's 0.1% and 0.001% it's another: the relative gain in the latter
case is bigger but I'm not sure it justifies allegedly higher code

On 03/31/2016 12:51 PM, Sangamesh Sajjan wrote:
> Hello Max,
> On Wednesday, March 30, 2016 9:05 PM, Max Suraev wrote:
>> Thank you for your contribution. Could you clarify - what's the advantage of this approach over existing osmo_t4_decode() function?
> To highlight the difference between osmo_t4_decode and Tree based approach consider the example below,
> if the received code word from the bitmap is “0111” and 0’s color code, then following steps involved to find run length using osmo_t4_decode
> 1.	Initially it finds the number of bits based on the color code ( i.e if it is 0 color code, then read 2 bits  or  4 bits if it is 1 color code )
> 2.	Since it is 0’s color code, read 2 bits from the  received encoded bitmap
> 3.	Check whether received 2 bits matches to any of the table entry ( i.e Makeup or  Terminating table), if it doesn’t match then increment one more bit.
> o	This will require loop of 15 followed by 64, So total of 79 comparison 
> 4.	Repeat the 3rd step if there is no matching code word
> Hence to find 0111 code word from the table, osmo_t4_decode would require
> Two iterations of makeup table ( i.e 15 times each ) and terminating table ( i.e 64 times each) = ((15 + 64 )* 2 ) = 158
> Third iteration where in exact match of code word is found in terminating table 3rd  position = 15+3  
>  So total 176 comparisons required to find the run length.
>  Usually there will be multiple code words in the received bitmap and each require multiple iterations to find run length as explained above.
> Whereas In tree based approach two trees (i.e. ones list and zero list ) are used and entire code word traversing shall be done in respective tree in single traversal based on color code.
> •	Read every bit from the received encoded bitmap and traverse the tree generated in init, If the bit is 0 traverse left and if it is 1 traverse right, Repeat this procedure till we find valid run length.
> •	In example above for “0111” only 4 comparisons are required 
> Hence we see advantage in using tree based approach for CRBB decoding.
>> Is there some test case which works for one but not the other?
> Currently we don’t have this specific test.
> Regards,
> Sangamesh

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