Re: [rohc] SN Encoding clarification

[Ang Way Chuang <[e-mail]>]

Karthik Balaguru wrote:
> 
> Hi,
> 
> Thanks for your reply.
> 
> 1) Yes, the info conveyed by you is correct. In opensource code, it 
> looks that d_lsb_decode( ) function does not handle wrap around cases 
> properly.
> 
>    But, If Sequence number are in sequence, the opensource decoding 
> would work fine for wrap around scenario, because the  following line in 
> the
>    d_lsb_decode( ) will take care of the wrap around condtion.
>         if(sn<lower) sn+= 1 <<k;

Didn't notice that before. Thanks.

>    And, for the out of ordered SN, the decoding using d_lsb_decode( ) 
>  has problems.
> 
> 2) In the method that you have explained using  __lsb_decode( ), the 
> definition for __builtin_expect(curr, 1) and
>     vector->calc_p(vector->bits) functions are missing in the code. Can 
> you please send those definitions. And also can you please explain
>     the method of calculation of the p value dynamically.
> 

Sorry about that.

For:
                  if (__builtin_expect(curr, 1))
                                   val = lsb->val;
                  else
                                   val = lsb->prev_val;


/* decode LSB encoded data using latest reference value and
  * return the decoded value
  * @m: LSB value to be decoded
  * @k: number of bits used by @m
  * if someone can optimize or suggest more elegant, please notify me */
uint32_t lsb_decode(struct lsb_data * lsb, uint32_t m, uint8_t k)
{
	return __lsb_decode(lsb, m, k, 1);
}


/* decode LSB encoded data using prev reference value and return the
  * decoded value
  */
uint32_t lsb_decode_prev(struct lsb_data * lsb, uint32_t m, uint8_t k)
{
	return __lsb_decode(lsb, m, k, 0);	
}

__lsb_decode is an internal function used by 2 other functions shown 
above. The curr variable is used to determine whether LSB is going to 
decoded using latest reference value or otherwise. That is useful for 
CRC correction attempt. __builtin_expect is a built-in function specific 
to gcc to inform compiler to optimize for a particular branch. In 
non-gcc speak, it will be similar to if (curr == 1) .



/* function type to compute the value of p for LSB */
typedef int32_t (*p_func_t)(uint8_t k);

The function calc_p has the signature as shown above. It takes in the k 
(k-bits) and calculate the value of p according to k. For example, SN 
for UDP profile will be something like this:

#define p_constant(name, x) static inline uint32_t 
p_constant_##name(uint8_t k) {return x;}

p_constant(negone, -1)	/* p_constant_negone */

For RTP SN, obviously the p needs to adjust according to k.

We, Universiti Sains Malaysia, plan to release the buggy user space ROHC 
library source code that we modified when it is ready in a few months, I 
hope.

> Thx in advans,
> Karthik Balaguru
> 
> 
> 
> 
> *Ang Way Chuang <[e-mail]>*
> Sent by: [e-mail]
> 
> 07/14/2009 07:16 AM
> 
> 	
> To
> 	Karthik Balaguru <[e-mail]>
> cc
> 	[e-mail]
> Subject
> 	Re: [rohc] SN Encoding clarification
> 
> 
> 	
> 
> 
> 
> 
> 
> Hi,
> 
>                 If my understanding is correct, the g function is 
> rohc.sourceforge.net
> is incorrect when there is wraparound. d_lsb_decode is also incorrect
> when there is a wraparound.
> 
> 
> 1. Modifying the GPL'ed, rohc.sourceforge.net. Here is, in my opinion,
> how g function should look like:
> /* Calculates the f(vref, k) interval for LSB
>  * @vref: reference that will be used to calculate interval
>  * @bits: is the number of bits that actual vref carry
>  * @k: number of bits that is used to encode LSB
>  * @min: the minimum will be stored here after function returns
>  * @max: the maximum of the range will be stored here.
>  *
>  * Note that it is possible for max < min if wraparound occurs which
>  * is correct according RFC 3905 (or at least according to my
>  * interpretation of the RFC :) )
>  */
> static inline void f_interval(uint32_t vref, uint8_t k, uint8_t bits,
> int32_t p, uint32_t * min, uint32_t * max)
> {
>                 uint32_t bitmask;
> 
>                 bitmask = ((((uint64_t) 1 << bits) - 1) & 0xffffffff);
>                 *min = (vref - p) & bitmask;
>                 *max = (vref + (1 << k) - 1 - p) & bitmask;
> }
> 
> /**
>  * finds minimum k so that v falls into the interval f(v_ref, k)
>  * Part of the LSB calculation algorithm
>  * @vector: wlsb_vector object itself
>  * @v_ref: reference value to create LSB
>  * @v: actual value to be encoded
>  */
> static inline uint8_t g(struct wlsb_vector * vector, uint32_t v_ref,
> uint32_t v)
> {
>                 uint8_t k;
>                 uint32_t min, max;
>                
>                 for(k = 0; k < vector->bits; k++) {
>                                  f_interval(v_ref, k, vector->bits, 
> vector->calc_p(vector->bits), &min,
> &max);
> 
>                                  if (min > max) { /* wrap-around */
>                                                   if (v >= min || v <= max)
>                                                                    break;
>                                  }
> 
>                                  if ((v <= max) && (v >= min))
>                                                   break;
>                 }
> 
>                 return k;
> }
> 
> 2. Here is in my opinion, how LSB decoding should look like taking into
> account the possibility of wrap around:
> 
> /**
>  * struct lsb_data - LSB decoding data structure
>  * @val: current value
>  * @prev_valu: previous value
>  * @calc_p: function that calculate the value of p
>  * @bits: the number of bits of the contained value
>  */
> struct lsb_data
> {
>                 uint32_t val;
>                 uint32_t prev_val;
>                 p_func_t calc_p;
>                 uint8_t bits;
> };
> 
> static inline uint32_t __lsb_decode(struct lsb_data * lsb, uint32_t m,
> uint8_t k, int curr)
> {
>                 uint32_t bitmask;
>                 uint32_t val;
>                 uint32_t min;
>                 uint32_t max;
>                 uint32_t min_mask;
> 
>                 if (__builtin_expect(curr, 1))
>                                  val = lsb->val;
>                 else
>                                  val = lsb->prev_val;
> 
>                 f_interval(val, k, lsb->bits, lsb->calc_p(k), &min, &max);
>                 bitmask = ~((((uint64_t) 1 << k) - 1) & 0xffffffff);
>                 val = (val & bitmask) | (m & ~bitmask);
> 
>                 if (max < min) { /* wraparound */
>                                  /* extract LSB of min */
>                                  min_mask = (min & ((1 << k) - 1));
>                                  
>                                  if (min_mask > m)
>                                                   return m;
>                                  else
>                                                   return min + (m - 
> min_mask);
>                 }
> 
>                 /* non wraparound from now on */
>                 if (val > max)
>                                  val -= (1 << k);
> 
>                 if (val < min)
>                                  val += (1 << k);
> 
>                 return val;
> }
> 
> The logic behind __lsb_decode function is described in the attached
> text. The note was written by myself for myself in case I forget. Sorry
> if it is incomprehensible to others. It's good if some of the expert
> ROHCers can verify whether this code is correct according to ROHC.
> 
> 
> Karthik Balaguru wrote:
>  >
>  > Hi,
>  >
>  > Need clarifications on SN Encoding.
>  >
>  > I wonder why the 'g funtion' has not been very explicitly defined in the
>  > RFC 3095.
>  >
>  > For SN WLSB -
>  > 1. As per the understanding & also based on the IETF mailing list
>  > discussions , the 'g function' in
>  >     the Compressor for K bit calculation looks as below -
>  >     ( Reference -
>  > http://www.ietf.org/mail-archive/web/rohc/old-archive/msg02263.html )
>  >
>  >         g(v_minmax, v)
>  >         {
>  >                FLOOR( log2 ( v_minmax XOR v ) ) + 1;
>  >         }
>  >         k1 = g(v_min, v);
>  >         k2 = g(v_max, v);
>  >         Sn_k = max(k1, k2);
>  >         Here, v is Received SN , v_min & v_max are the minimum SN &
>  > maximum SN repectively in the window
>  >
>  >              And in the Decompressor, packet it looks as below :-
>  >         mask = ~((1 << Sn_k) - 1);    // mask is uint16
>  >         rtpSeq = ((v_ref & mask) | ESn);
>  >         Here, ESn is the Extracted SN bits from the Compressed packets.
>  >
>  >
>  > 2.  But, from the opensource RoHC code , the below info was obtained :-
>  >      ( Reference - http://rohc.sourceforge.net/download.php )
>  >
>  >         On the compressor side, the 'g function' is as below -
>  >         static void f(int v_ref, int k, int p, int * min, int * max)
>  >         {
>  >                 *min = v_ref - p;
>  >                 *max = v_ref + ((1 << k) - 1) - p;        // (1 << k) =
>  > 2 to the power of k
>  >         }
>  >
>  >         static int g(int v_ref, int v, int p, int bits)
>  >         {
>  >                 int k, min, max;
>  >                 for(k = 0; k < bits; k++){
>  >                         f(v_ref, k, p, &min, &max);
>  >                         if( (v <= max) && (v >= min) ) break;
>  >                 }
>  >                 return k;
>  >         }
>  >
>  >         And in the decompressor , it is as below -
>  >         int d_lsb_decode(struct sd_lsb_decode * s, int m, int k)
>  >         {        
>  >                 int lower = (s->v_ref_d - s->p);
>  >         //        int higher = (ref - s->p) + 1 << k - 1;
>  >                 int bitmask = ~((1 << k) - 1);
>  >                  int sn = (s->v_ref_d & bitmask) | m;
>  >                 if (sn < lower) sn += 1 << k;
>  >                 return sn & 0xFFFF;
>  >         }
>  >
>  > So, Kindly let me know the method that is inline with RFC 3095 for the
>  > 'g function' .
>  >
>  > Thx in advans,
>  > Karthik Balaguru
>  > ______________________________________________________________________
>  >
>  >
>  > ------------------------------------------------------------------------
>  >
>  > _______________________________________________
>  > Rohc mailing list
>  > [e-mail]
>  > https://www.ietf.org/mailman/listinfo/rohc
> 
> 
> 
> ______________________________________________________________________Note 
> on LSB
> ===========
> Interpretation interval is given by this formulae:
> 
>        f(v_ref, k) = [v_ref - p, v_ref + (2^k - 1) - p]
>        
> When receiving m-bits LSBs, the decompressor uses the interpretation
> interval f(v_ref_d, m), called interval_d. It picks as the
> decompressed value the one in interval_d whose LSBs match the
> received m bits.
>        
> Case study of value wraparound
> ---------------------------------
> Let's analyse the case where the value of to be encoded is of 16
> bits long. Let's say that,
> 
>        vref = 0xfff0
>        val = 0x0
>        p = 0
>        
> According to RFC 3095:
> 
> "The scheme is guaranteed to be correct if the compressor and the
> decompressor each use interpretation intervals
> 1) in which the original value resides, and
> 2) in which the original value is the only value that has the
> exact same k least significant bits as those transmitted."
> 
> To fulfill statement 1, k=5 bits is good enough assuming that the
> interpretation interval wraps around in which the interpretation
> interval will be 0xfff0 - 0x000f. If 5 bits is used, the
> encoded value will be 0 for uncompressed value of 0. Statement 2 is
> also fulfilled because the LSB of 0xfff0 is 10000b instead of 00000b.
> 
> The full list of encoded values and its uncompressed values for
> these parameters are:
>        vref = 0xfff0
>        k = 5
>        p = 0
> m=0, v=0
> m=1, v=1
> .
> .
> .
> m=0xf, v=0xf
> m=0x10, v=0xfff0
> m=0x11, v=0xfff1
> .
> .
> .
> m=0x1f, v=0xffff
> 
> 
> So in the case of where parameters are like this:
>        vref = 0x0
>        k = 3
>        p = 5
> The list of encoded values and its uncompressed values:
> m=0b, v=0               m=100b, v=0xfffc
> m=1b, v=1               m=101b, v=0xfffd
> m=10b, v=2              m=110b, v=0xfffe
> m=11b, v=0xfffb         m=111b, v=0xffff
> 
> Now comes the interesting part -- to put this into algorithm.
> For wraparound case, minimum value in the interpretation interval is
> greater than maximum value in the interpretation interval. Notice
> the examples above, the minimum value (0xfff0 and 0xfffb) becomes
> the threshold in itself. So to get the threshold value for m which
> is equivalent masking minimum value:
> 
> 1.                 min_mask = (min & ((1 << k) - 1));
> 
> If m is less than min_mask (threshold), then nothing need to be done
> since that is the decoded value.                
>                
> 2.                 if (min_mask > m)
> 3.                                  return m;
> 
> However, m is greater to or equal threshold value, then decoded
> value can be calculated by adding the difference between m and
> threshold value (min_mask) to minimum value in the interpretation
> interval (min).
> 
> 4.                 else
> 5.                                  return min + (m - min_mask);
> 
> 
> 
> 
> Non-wraparound value
> --------------------
> Potential to downgrade/upgrade using AND 0xffff bitmask against vref
> ---------------------------------------------------------------
> Suppose 16-bits value is used again, but with these parameters
>        vref = 10                       (potential to upgrade m=111b to v=15)
>        k = 3
>        p = 5
>        f(v_ref, k) = [5, 12]
> 
> The list of encoded values and its uncompressed values:
> m=0b, v=8               m=100b, v=12
> m=1b, v=9               m=101b, v=5
> m=10b, v=10                     vref = 0xfff0
>        val = 0x0
>        p = 0m=110b, v=6
> m=11b, v=11             m=111b, v=7
> 
>        If vref = 7                     (potential to downgrade m=0 to v=0)
>        k = 3                           (potential to upgrade m=111b to v=15)
>        p = 5
>        f(v_ref, k) = [2, 9]
> The list of encoded values and its uncompressed values:
> m=0b, v=8               m=100b, v=4
> m=1b, v=9               m=101b, v=5
> m=10b, v=2              m=110b, v=6
> m=11b, v=3              m=111b, v=7
> 
>        If vref = 11                    (potential to upgrade m=111b to v=15)
>        k = 3
>        p = 5
>        f(v_ref, k) = [6, 13]
> The list of encoded values and its uncompressed values:
> m=0b, v=8               m=100b, v=12
> m=1b, v=9               m=101b, v=13
> m=10b, v=10             m=110b, v=6
> m=11b, v=11             m=111b, v=7
> 
>        If vref = 14                    (potential to downgrade m=0 to v=8)
>        k = 3
>        p = 5
>        f(v_ref, k) = [9, 16]
> The list of encoded values and its uncompressed values:
> m=0b, v=16              m=100b, v=12
> m=1b, v=9               m=101b, v=13
> m=10b, v=10             m=110b, v=14
> m=11b, v=11             m=111b, v=15
> 
> Do note that the downgrade problem can be fixed by adding 2^k to
> decoded value if the decoded value is found to be less than minimum
> value.
> 
> Upgrade problem can be fixed by deducting 2^k to decoded value if
> the decoded value is found to be greater than maximum value.
> 
> 
> 
> 
> _______________________________________________
> Rohc mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/rohc
> 
> 
> ______________________________________________________________________
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Rohc mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/rohc