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/.
Max msuraev at sysmocom.deHi 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 complexity. 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