Re: [rohc] SN Encoding clarification

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

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