none
[MS-RDPRFX] Failed in RLGR Entropy Decoding RRS feed

  • Question

  • Hi all,

    After read [MS-RDPRFX] and [ARLGR]

    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 CSaint Monday, January 3, 2011 9:47 AM add reference links
    Monday, January 3, 2011 9:46 AM

Answers

  • 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. 

    Please let me know if it answers your question.


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

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
    Owner
  • 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
    Owner
  • 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
    Owner
  • 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
    Owner
  • 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. 

    Please let me know if it answers your question.


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

       Thank you for the answer.  

       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
    Owner
  • 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
    Owner
  • 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