Re: 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
> [email protected]
> https://www.ietf.org/mailman/listinfo/rohc

_______________________________________________
Rohc mailing list
[email protected]
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.