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

Hello Max, On Wednesday, March 30, 2016 9:05 PM, Max Suraev wrote: 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. Currently we don’t have this specific test. Regards, Sangamesh