Opus Range Encoder Implementation

#include <stdint.h>

#include "rcode.h"

#define RCODE_N 256

/*
 * INTERNAL MEMBERS
 */

void carryout(uint_fast16_t c, int_fast16_t* rem, uint_fast16_t* ext
        , unsigned char* output, size_t* out_index);

/*
 * EXTERNAL MEMBERS
 */

size_t range_encode(unsigned char* input, unsigned char* output, size_t in_length)
{
    /* Model */
    size_t f[RCODE_N]  = { 0 };
    size_t fl[RCODE_N] = { 0 };
    size_t fh[RCODE_N] = { 0 };
    size_t ft          = 0;

    /* State */
    uint_fast32_t val = 0;
    uint_fast32_t rng = 2147483648;
    int_fast16_t  rem = -1;
    uint_fast16_t ext = 0;

    size_t out_index   = 0;

    /*
     * Compute frequency values.
     */

    for (size_t index = 0; index < in_length; index++)
        f[input[index]]++;

    for (size_t k = 0; k < RCODE_N; k++)
        for (size_t i = 0; i < k; i++)
            fl[k] += f[i];

    for (size_t k = 0; k < RCODE_N; k++)
        fh[k] = fl[k] + f[k];

    for (size_t i = 0; i < RCODE_N; i++)
        ft += f[i];

    /*
     * Main loop
     */

    for (size_t in_index = 0; in_index < in_length; in_index++)
    {
        /*
         * Encode
         */

        unsigned char k = input[in_index];

        if (fl[k] > 0)
        {
            val = val + rng - (rng / ft) * (ft - fl[k]);
            rng = (rng / ft) * (fh[k] - fl[k]);
        }
        else
        {
            rng = rng - (rng / ft) * (fh[k] - fl[k]);
        }

        /*
         * Renormalize
         */

        while (rng <= 8388608)
        {
            carryout(val >> 23, &rem, &ext, output, &out_index);

            val = (val << 8) & 0x7fffffff;
            rng <<= 8;
        }
    }

    /*
     * Finalize
     */

    uint_fast32_t end = val;

    while (end)
    {
        carryout(end >> 23, &rem, &ext, output, &out_index);

        end = (end << 8) & 0x7fffffff;
    }

    if ((rem && rem != -1) || ext > 0)
        carryout(0, &rem, &ext, output, &out_index);

    return out_index;
}

void carryout(uint_fast16_t c, int_fast16_t* rem, uint_fast16_t* ext
        , unsigned char* output, size_t* out_index)
{
    if (c == 255)
    {
        *ext = *ext + 1;
    }
    else
    {
        uint_fast16_t b = c >> 8;

        if (*rem != -1)
            output[*out_index = *out_index + 1] = *rem + b;

        if (*ext)
        {
            if (b)
                for (uint_fast16_t count = 0; count < *ext; count++)
                    output[*out_index = *out_index + 1] = 0;
            else
                for (uint_fast16_t count = 0; count < *ext; count++)
                    output[*out_index = *out_index + 1] = 255;

            *ext = 0;
        }

        *rem = c & 255;
    }
}