Subject: [rohc] SN Encoding clarification

From: Karthik Balaguru <[email-masked]>
Date: Mon, 13 Jul 2009 20:25:26 +0530

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

______________________________________________________________________

---

From: Ang Way Chuang <[email-masked]>
Date: Tue, 14 Jul 2009 09:46:08 +0800

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:
>                 *max = v_ref + ((1 << k) - 1) - p;        // (1 << k) = 
> 2 to the power of k
>         }
> 
> 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-masked]
> 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.

---

From: Karthik Balaguru <[email-masked]>
Date: Thu, 16 Jul 2009 19:57:50 +0530

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;
   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. 

Thx in advans,
Karthik Balaguru

Ang Way Chuang <[email-masked]> 
Sent by: [email-masked]
07/14/2009 07:16 AM

To
Karthik Balaguru <[email-masked]>
cc
[email-masked]
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.

/**
 
                 for(k = 0; k < vector->bits; k++) {
                                 f_interval(v_ref, k, vector->bits, 
vector->calc_p(vector->bits), &min, 
&max);

                 return k;
}

/**

                 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 (min_mask > m)
                                                 return m;
                                 else
                                                 return min + (m - 
min_mask);
                 }

                 if (val < min)
                                 val += (1 << k);

                 return val;
}

> So, Kindly let me know the method that is inline with RFC 3095 for the 

______________________________________________________________________Note 
on LSB
===========
Interpretation interval is given by this formulae:

 

        vref = 0xfff0
        val = 0x0
        p = 0
 
According to RFC 3095:

 
2.               if (min_mask > m)
3.                               return m;

4.               else 

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]

        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

---

From: Ang Way Chuang <[email-masked]>
Date: Fri, 17 Jul 2009 10:27:10 +0800

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

Didn't notice that before. Thanks.

>    And, for the out of ordered SN, the decoding using d_lsb_decode( ) 
>  has problems.
> 

Sorry about that.

For:

/* 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 <[email-masked]>*