3.1.8.1.7.3.2 RLGR1/RLGR3 Encode

// 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);
                }

            }
        }
    }
}