WLSB encoding incorrect

[Chris Pearson]

I wrote a unit test app for the RoHC library's W-LSB implementation.

The app creates a 16-bit W-LSB window (bits = 16, width = 4, p = ROHC_LSB_SHIFT_IP_ID) and adds 0xfc, 0xfd, 0xfe, and 0xff to fill the window (so that v_min = 0xfc and v_max = 0xff). It then calls wlsb_get_k_16bits() with value 0x100.

I expected the returned nr_bits to be 9, since the decompressor would need to replace the 9 least significant bits of v_min to reconstitute v:

    0000 0000 1111 1100 v_min (0x00fc)
    0000 0001 0000 0000 v (0x0100)

However, wlsb_get_k_16bits() sets nr_bits to 3. That implies that the decompressor would need to be able to reconstruct 0x100 from 0xfc and three zero bits. I don't see how that can be correct.

I've tried this with other values. It appears that wlsb_get_k_16bits() is returning the minimum number of bits required to express the *difference* between v and v_ref. (In other words, it's returning log2(abs(v - v_ref)) + 1.)

What I think wlsb_get_k_16bits() should return is the minimum number of bits that includes the most-significant bit that differs between v and v_ref. That number is given by the following 'C' statement (ignoring 'p' here):

    floor(log2(v ^ v_ref)) + 1

XOR is the key operation here, and I don't see that in the RoHC library code.

-- Chris

P.S. I would use a non-floating-point equivalent to log2() in real code.

[Didier Barvaux (didier-barvaux)]

Hi Chris,

> What I think wlsb_get_k_16bits() should return is the minimum number
> of bits that includes the most-significant bit that differs between v and
> v_ref.

That's the LSB algorithm. The W-LSB algorithm uses a window of values that
helps reducing the number of required bits. With your example, 3 bits are
enough to distinguish the correct value between the other values in the
window. With only 2 bits, the 0xfc and 0x100 values could not be distinguished,
but with 3 bits they can.

With the shift parameter p = ROHC_LSB_SHIFT_IP_ID = 0, the value you encode
with the W-LSB scheme is expected to stay unchanged or increase by a small
number. If you chose p = -1, the value is expected to always increase, so the
0xfc value would not have been taken into account, and only 2 bits would have
been enough.

Regards,
Didier

[Chris Pearson (chriscpearson)]

Hi Didier,

Ah, now I see the light! Thanks for explaining this.

-- Chris