Re: SN Encoding clarification
Karthik Balaguru <[email protected]> Thu, 16 Jul 2009 19:57:50 +0530
| Newsgroups | gmane.ietf.rohc |
|---|---|
| Message-ID | <OFA961666C.233250EC-ON652575F4.0044E5B0-652575F5.004F73EB@lntinfotech.com> |
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 protected]>
Sent by: [email protected]
07/14/2009 07:16 AM
To
Karthik Balaguru <[email protected]>
cc
[email protected]
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
> [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.
_______________________________________________
Rohc mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rohc
______________________________________________________________________
_______________________________________________
Rohc mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rohc