# [MS-RDPRFX] Failed in RLGR Entropy Decoding

• ### Question

• Hi all,

I try to decode the image tile in TS_RFX_TILE, but i failed.

My decoder follows rules in the Table 2 of [ARLGR], and starts with the adapting parameters in 3.1.8.1.7.1 in [MS-RDPRFX].

I thought i might misread something, and hope to get help.

I try to explain this decoder.

For the encoded data : 0x0D  0x81  0x70        (First 3 bytes in YData of first TS_RFX_TILE )

In binary : 0000 1101  1000 0001  0111 0000

This decoder works as follows. (Adapting parameters k=kp/L=8/8=1,  kr=krp/L=8/8=1.  Both kp and krp are in range [0,80])

[bit 1]0:  k=1, with a full run, decode to [00], kp=kp+4, new k = kp/L = (8+4)/8 = 1

[bit 2]0:  k=1, with a full run, decode to [00], kp=kp+4, new k = (12+4)/8 = 2

[bit 3]0:  k=2, with a full run, decode to [0000], kp=kp+4, new k = (16+4)/8 = 2

[bit 4]0:  k=2, with a full run, decode to [0000], kp=kp+4, new k = (20+4)/8 = 3

[bit 5]1:  k=3, partial run, read next k bits [101] as the run-length.

run Golomb-Rice decoder to get u in GR(u-1, kr), read [10 0], where p=1, z=0 and u=(p<<kr)+z+1=3.  decode to [00000 11].

kp=kp-6, new k=18/8=2.   p=1, new kr=krp/8=1

[bit 12~15]0000: k=2, 4 full runs, new k = (18+4+4+4+4)/8 = 4

[bit 16]1: k=4, partial run, read next k bits [0111] as the run-length.

To get u in GR(u-1, kr), read [00], where p=0,  z=0 and  u=1, decode to [0000000 1]

kp=kp-6, new k=(34-6)/8=3.   p=0, new kr=(krp-2)/8=0

[bit23~24]00: k=3, 2 full runs, new k = (28+4+4)/8 = 4.

After decoded 201 bytes of YData. It output 56987 bits, not 4*4096 bits.

I know that this output is not correct, because it can't be used to reconstruct 64x64 coefficient array.

I wish to find where i failed in the decoder. Thanks all.

• Edited by Monday, January 3, 2011 9:47 AM add reference links
Monday, January 3, 2011 9:46 AM

• Hi Csaint:

The output of the decoder will be the input to inverse quantization, and then to yuv2rgb color conversion.

So the answer to the question is really implementation specific; it depends on how many bits of precision you want to keep at each stage.  In our implementation we write back a signed 16 bit value as input to the dequant, though the number of significant bits is closer to 8.  Ultimately, during color conversion, the final values are shifted back down to 8-bit unsigned rgb values.

Regards, Obaid Farooqi
Thursday, January 27, 2011 7:01 PM

### All replies

• Hi, CSaint,

Thanks for your question.  One of our team member will work on your question and respond soon.

Hongwei Sun -MSFT
Monday, January 3, 2011 5:00 PM
• Hi Csaint:

I'll help you with this issue and will be in touch as soon as I have an answer.

Regards, Obaid Farooqi
Tuesday, January 4, 2011 5:46 PM
• Thank you :D
Wednesday, January 5, 2011 9:46 AM
• Hi CSaint:

I am still working on your issue and would be in touch as soon as I have an answer.

Regards, Obaid Farooqi
Monday, January 10, 2011 6:04 PM
• Thank you.  I had tried several possible changes in these days, but it still fail.

Tuesday, January 11, 2011 7:46 AM
• Hi Obaid,

May i have another question about RLGR encode/decode?

If there is a string u=[01110101]=117 and k=0, kr=6.

How the algorithm works?

In Table2 of [ARLGR]：k=0(no run mode), input symbol=u, code=GR(u, kr)

By the rule, u=117=1*64+53, p=1, z=53... code=10110101.

But to decode it, the code will be divided into 10 110101,  where p=1, z=110101. u=117=[1110101].

The first symbol 0 disappeared?

Friday, January 14, 2011 3:05 AM
• Hi CSaint:

I will look into it and will get back to you when I have an answer. My research on this is still underway.

Regards, Obaid Farooqi
Monday, January 17, 2011 10:39 PM
• Hi CSaint:

We have finished our investigation on your question on remote fx decoding (RLGR decoding). The following algorithm will be included in a future release of MS-RDPRFX.

Algorithm for RLGR Entropy Decoding
-----------------------------------------------
// Pseudo code which shows the decoding for RLGR1/RLGR3 algorithm used in RemoteFX

// Constants used within the RLGR1/RLGR3 algorithm

#define KPMAX   (80)       // max value for kp or krp
#define LSGR    (3)        // shift count to convert kp to k
#define UP_GR   (4)        // increase in kp after a zero run in RL mode
#define DN_GR   (6)        // decrease in kp after a non-zero symbol in RL mode
#define UQ_GR   (3)        // increase in kp after non-zero symbol in GR mode
#define DQ_GR   (3)        // decrease in kp after zero symbol in GR mode

//
// Gets (returns) the next nBits from the bitstream
//
UINT GetBits(
UINT nBits
);

//
// From current output pointer, write "value", check and update *termsToDecode
//
VOID
WriteValue(
INT value,
INT *termsToDecode
);

//
// From current output pointer, write next nZeroes terms with value 0, check and update *termsToDecode
//
VOID
WriteZeroes(
UINT nZeroes,
INT *termsToDecode
);

//
// Returns the least number of bits required to represent a given value.
//
UINT
GetMinBits(
UINT val             // returns ceil(log2(val))
);

//
// Converts from (2 * magnitude - sign) to integer
//
INT
GetIntFrom2MagSign(
UINT twoMs
);

//
// Update the passed parameter and clamp it to the range [0,KPMAX].
// Return the value of parameter right shifted by LSGR.
//
INT
UpdateParam(
INT*  param,    // parameter to update
INT   deltaP    // update delta
)
{
*param += deltaP;               // adjust parameter
if (*param > KPMAX) *param = KPMAX;  // max clamp
if (*param < 0) *param = 0;          // min clamp
return (*param >> LSGR);
}

//
// Outputs the Golomb/Rice encoding of a non-negative integer.
//
UINT
GetGRCode(
INT*   krp,
INT*   kr
)
{
INT vk;
UINT mag;

for (vk=0;GetBits(1)==1;)  // chew up/count leading ones and escape 0
{
vk++;
}

// get next *kr bits, and combine with leading 1's
mag = (vk<<*kr) | GetBits(*kr);

// adjust kpr and kr, based on vk
if (!vk)
{
*kr = UpdateParam(kpr, -2);
}
else if (vk!=1) // at 1, no change!
{
*kr = UpdateParam(kpr, vk);
}

return (mag);
}

//
// Routine that reads and decodes stream of RLGR data
//
VOID
RLGR_Decode(
RLGR_MODE rlgrMode,        // RLGR1 || RLGR3
INT termsToDecode
)
{
// initialize the parameters
INT k = 1;
INT kp = k << LSGR;
INT kr = 1;
INT krp = kr << LSGR;

while (termsToDecode > 0)
{
INT run;

if (k)
{
// RL MODE
while (GetBits(1) == 0)
{
// we have an RL escape "0" which translates to a run (1<<k) of zeroes
WriteZeroes(1<<k, &termsToDecode);
k = UpdateParam(&kp,UpGR); // raise k and kp up because of zero run
}

if (termsToDecode > 0)
{
// next k bits will contain remaining run of zeroes
run = GetBits(k);
WriteZeroes(run, &termsToDecode);
}

if (termsToDecode > 0)
{
// get nonzero value, starting with sign bit and then GRCode for magnitude-1
UINT sign = GetBits(1);
INT mag = (INT)GetGRCode(&krp,&kr) + 1;    // magnitude - 1 was coded (because it was nonzero)
WriteValue(sign ? -mag : mag, &termsToDecode);
k = UpdateParam(&kp, -DnGR);         // lower k and kp because of nonzero term
}
}
else
{
// GR (GOLOMB-RICE) MODE
UINT mag = GetGRCode(&krp, &kr);     // values coded are 2*magnitude - sign

if (rlgrMode == RLGR1)
{
if (!mag)
{
WriteValue(0, &termsToDecode);
k = UpdateParam(&kp, UqGR);     // raise k and kp due to zero
}
else
{
WriteValue(GetIntFrom2MagSign(mag), &termsToDecode);
k = UpdateParam(&kp, -DqGR);    // lower k and kp due to nonzero
}

}
else // rlgrMode == RLGR3
{
// In GR mode FOR RLGR3, we have encoded the sum of two (2*mag-sign) values
UINT nIdx = GetMinBits(mag);    // maximum possible bits for first term
UINT val1 = GetBits(nIdx); // decode val1 is first term's (2*mag-sign) value
UINT val2 = mag - val1;         // val2 is second term's (2*mag-sign) value

if (val1 && val2) {
k = UpdateParam(&kp, -2*DqGR);  // raise k and kp if both terms nonzero
}
else if (!val1 && !val2) {
k = UpdateParam(&kp, 2*UqGR);   // lower k and kp if both terms zero
}

WriteValue(GetIntFrom2MagSign(val1), &termsToDecode);
WriteValue(GetIntFrom2MagSign(val2), &termsToDecode);
}
}
}
}

Please let me know if it answers your question. If it does, I’ll consider this issue resolved.

Regards, Obaid Farooqi
Wednesday, January 26, 2011 6:05 PM
• Hi Obaid,

Thank you for your works in these days.

I find that there are 2 things i didn't considered and I'm still trying it on.

By the way, i have a stupid question about WriteValue function.

If i write a negative value to output by WriteValue(int value).

I should write a 8-bits value (-127~+127) or an 32-bits value (size of int) ?

Thursday, January 27, 2011 9:37 AM
• Hi Csaint:

The output of the decoder will be the input to inverse quantization, and then to yuv2rgb color conversion.

So the answer to the question is really implementation specific; it depends on how many bits of precision you want to keep at each stage.  In our implementation we write back a signed 16 bit value as input to the dequant, though the number of significant bits is closer to 8.  Ultimately, during color conversion, the final values are shifted back down to 8-bit unsigned rgb values.

Regards, Obaid Farooqi
Thursday, January 27, 2011 7:01 PM
• Hi Obaid,

I think it solved a key concept i didn't thought before.

Thank you.

Friday, January 28, 2011 9:02 AM
• Hi CSaint:

Please let me know if the following issue is resolved by my decoder algorithm:

Hi Obaid,

May i have another question about RLGR encode/decode?

If there is a string u=[01110101]=117 and k=0, kr=6.

How the algorithm works?

In Table2 of [ARLGR]：k=0(no run mode), input symbol=u, code=GR(u, kr)

By the rule, u=117=1*64+53, p=1, z=53... code=10110101.

But to decode it, the code will be divided into 10 110101,  where p=1, z=110101. u=117=[1110101].

The first symbol 0 disappeared?

Regards, Obaid Farooqi
Tuesday, February 1, 2011 8:39 PM
• Hi CSaint:

Please let me know if the following issue is resolved by my decoder algorithm:

---------------------------------------------------------------------------

Hi Obaid,

May i have another question about RLGR encode/decode?

If there is a string u=[01110101]=117 and k=0, kr=6.

How the algorithm works?

In Table2 of [ARLGR]：k=0(no run mode), input symbol=u, code=GR(u, kr)

By the rule, u=117=1*64+53, p=1, z=53... code=10110101.

But to decode it, the code will be divided into 10 110101,  where p=1, z=110101. u=117=[1110101].

The first symbol 0 disappeared?

--------------------------------------------------------------------------------
Regards, Obaid Farooqi

Regards, Obaid Farooqi
Wednesday, February 2, 2011 5:09 PM
• Hi Obaid,

Yes, it was solved.

Because I thought that RLGR is a bit-level compressor before.

But it works on the coefficients, not bit stream.

Therefore, that was not even a problem.

Wednesday, February 9, 2011 3:52 AM