3.1.8.1.7.3.2 RLGR1/RLGR3 Encode

The following pseudocode sample shows how to encode a stream of input symbols using the RLGR1/RLGR3 algorithm.

 // 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 nonzero symbol in RL mode
 #define UQ_GR   (3)    // increase in kp after nonzero symbol in GR mode
 #define DQ_GR   (3)    // decrease in kp after zero symbol in GR mode
  
  
 //
 // Returns the next coefficient (a signed int) to encode, from the input stream
 //
 INT 
 GetNextInput();
  
  
 //
 // Emit bitPattern to the output bitstream.
 // The bitPattern value represents a bit sequence that is generated by shifting 
 // new bits in from the right. If we take the binary representation of bitPattern, 
 // with N(numBits-1) being the leftmost bit position and 0 being the rightmost bit position, 
 // the mapping of bitPattern to the output bytes is as follows:
 //
 //     bitPattern[N..0] -> byte[MSB..LSB] .. byte[MSB..LSB]
 //
 VOID 
 OutputBits(
     INT numBits,      // number of bits in bitPattern
     INT  bitPattern   // bit pattern
     );
  
 //
 // Emit a bit (0 or 1), count number of times, to the output bitstream
 //
 VOID 
 OutputBit(
     INT count,     // number of times to emit the bit
     INT bit        // 0 or 1
     );
  
 //
 // Returns the least number of bits required to represent a given value
 // 
 UINT 
 GetMinBits(
     INT val      // returns ceil(log2(val))
     );
  
 // 
 // Converts the input value to (2 * abs(input) - sign(input)), 
 // where sign(input) = (input < 0 ? 1 : 0) and returns it
 //
 UINT
 Get2MagSign(
     INT input    // input value
     );
  
  
 //
 // 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;
     if (*param > KPMAX) *param = KPMAX;
     if (*param < 0) *param = 0;
     return (*param >> LSGR);
 }
  
  
 //
 // Outputs the Golomb/Rice encoding of a non-negative integer
 //
 VOID
 CodeGR(
     INT*   krp,   // GR parameter, used and updated based on the input value
     UINT  val     // input non-negative value to be encoded
     )
 {
     INT kr = *krp >> LSGR;
  
     // unary part of GR code
  
     UINT vk = val >> kr;
     OuputBit(vk, 1);
     OutputBit(1, 0);
  
     // remainder part of GR code, if needed
     if (kr) {
         OutputBits(kr, val & ((1 << kr) - 1));
     }
  
     // update krp, only if it is not equal to 1
     if (vk == 0) {
         UpdateParam(krp, -2);
     } 
     else if (vk > 1) {
         UpdateParam(krp, vk);
     }
 }
  
  
 //
 // Routine that outputs a stream of RLGR1/RLGR3-encoded bits
 //
 VOID 
 RLGR_Encode(
     RLGR_MODE rlgrMode    // RLGR1 || RLGR3
     )
 {
     // initialize the parameters
     INT k = 1;
     INT kp = 1 << LSGR;
     INT kr = 1;
     INT krp = 1 << LSGR;
  
     // process all the input coefficients
     while (1)
     {
         INT input;
  
         if (k)
         {
             // RUN-LENGTH MODE
  
             // collect the run of zeros in the input stream
             INT numZeros = 0;
             while ((input = GetNextInput()) == 0) {
                 ++ numZeros;
             }
  
             // emit output zeros
             INT runmax = 1 << k;
             while (numZeros >= runmax)
             {
                 OutputBit(1, 0);             // output a zero bit
                 numZeros -= runmax;
                 k = UpdateParam(&kp, UpGR);  // update kp, k 
                 runmax = 1 << k;
             }
  
             // output a 1 to terminate runs
             OuputBit(1, 1);
  
             // output the remaining run length using k bits
             OutputBits(k, numZeros);
  
             // encode the nonzero value using GR coding
  
             INT mag = abs(input);            // absolute value of input coefficient
             INT sign = (input < 0 ? 1 : 0);  // sign of input coefficient
  
             OutputBit(1, sign);      // output the sign bit
             CodeGR(&krp, mag - 1);   // output GR code for (mag - 1)
  
             k = UpdateParam(&kp, -DnGR);
         }
         else 
         {
             // GOLOMB-RICE MODE
  
             if (rlgrMode == RLGR1)
             {
                 // RLGR1 variant
  
                 // convert input to (2*magnitude - sign), encode using GR code
                 UINT twoMs = Get2MagSign(GetNextInput());
                 CodeGR(&krp, twoMs); 
  
                 // update k, kp
                 if (!twoMs) {
                     k = UpdateParam(&kp, UqGR);
                 } 
                 else {
                     k = UpdateParam(&kp, -DqGR);
                 }
             }
             else // rlgrMode == RLGR3
             {
                 // RLGR3 variant
  
                 // convert the next two input values to (2*magnitude - sign) and
                 // encode their sum using GR code
  
                 UINT twoMs1 = Get2MagSign(GetNextInput());
                 UINT twoMs2 = Get2MagSign(GetNextInput());
                 UINT sum2Ms = twoMs1 + twoMs2;
                 
                 CodeGR(&krp, sum2Ms);
  
                 // encode binary representation of the first input (twoMs1).  
                 OutputBits(GetMinBits(sum2Ms), twoMs1);
  
                 // update k,kp for the two input values
  
                 if (twoMs1 && twoMs2) {
                     k = UpdateParam(&kp, -2*DqGR);
                 } 
                 else if (!twoMs1 && !twoMs2) {
                     k = UpdateParam(&kp, 2*UqGR);
                 }
  
             }
         }
     }
 }