Re: SN Encoding clarification
Ang Way Chuang <[email protected]> Fri, 17 Jul 2009 10:27:10 +0800
| Newsgroups | gmane.ietf.rohc |
|---|---|
| Message-ID | <[email protected]> |
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 <[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