Битовый буфер не ведет себя должным образом в C

Помимо того, что ваш порядок битов будет немного странным, потому что вы добавляете новые биты в верхнюю часть буфера и удаляете их из нижней части, у вас есть ошибка в пути finish.

    if (finish) { 
        buffer = 0; // <<<==== This is a bug I think
        if (offset) {
            *outByte = (char)buffer;
            offset = 0;
            return 1;
        }
        offset = 0;
        return 0;
    }

Когда я запускаю ваши тестовые данные, когда ваш код достигает строки с пометкой «Я думаю, это ошибка», в ней все еще остаются биты. А именно buffer и 0b01001 равны 5. Эти последние пять бит никогда не записываются в выход.

Что касается порядка битов, я думаю, его можно исправить, сдвинув offset влево на buffer, добавив новые биты в нижнюю часть и, если у вас восемь или более бит, взяв верхние восемь битов для следующего выходного байта.

Наверное, это примерно правильно. Это дает ожидаемый результат

int bitsBuffer2(char inByte, char nBits, char* outByte, char finish)
{
    int i;
    static short unsigned buffer = 0;
    static char unsigned totalBits = 0;

    // Note: nBits is assumed to b <= 8 !
    buffer <<= nBits; // Make space for the bits
    buffer |= inByte & ~(~0u << nBits); // Put the bits in the buffer
    totalBits += nBits;
    if (totalBits >= 8) {
        // Slice the top 8 bits off the buffer
        totalBits -= 8;
        *outByte = (char)(buffer >> totalBits); // Note: Shift before cast
        buffer &= ~(~0u << totalBits);
        return 1;
    }
    if (finish) {
        if (totalBits > 0) { // Test if anything is in the buffer
            // Pack the remaining bits at the top of the byte
            *outByte = (char)(buffer << (8 - totalBits));
            // Zap everything
            totalBits = 0;
            buffer = 0;
            return 1;
        }
        return 0;
    }
    return 0;
}

Это может быть не на 100% правильно, если nBits и много битов в буфере.

Во-первых, ваш интерфейс bitsBuffer() (возвращаемое значение истинно, если в *outByte записан один байт) сломан: если вы предоставляете оба ненулевых nBits для отправки и запрашиваете finish true, то вам может потребоваться вывести два байта, но интерфейс может вернуть только один. Вам придется потребовать, чтобы если finish истинно, то nBits должно быть равно нулю. Ваш текущий код будет игнорировать запрос finish, если предоставленный nBits приводит к выводу байта. Вам придется вызвать еще раз с еще одним finish запросом.

Во-вторых, кодирование Хаффмана позволяет легко создавать коды длиной более восьми бит даже при небольшом объеме входных данных. Ваш код должен иметь возможность обрабатывать более длинные коды. В действительности ваш интерфейс может обрабатывать только восьмибитные коды. Например, десять разных символов с частотами 1, 1, 1, 3, 4, 7, 11, 18, 29 и 47, всего 122 символа на входе, дадут два девятибитных кода. Когда вы обрабатываете более длинные коды, вашему интерфейсу также потребуется обрабатывать более одного созданного байта.

В-третьих, в зависимости от желаемого порядка битов из вашего примера вы помещаете биты задом наперед. Для вашего кода второй вызов поместит эти биты выше битов первого вызова. Таким образом, в вашем примере 0110, за которым следует 1, второе будет помещено над первым, что даст 10110. В то время как желаемый результат ставит первые биты выше вторых, 01101.

В-четвертых, ваш finish обнуляется buffer перед отправкой битов buffer! Вы преждевременно стираете свою информацию.

Например, это даст желаемый результат, будет работать с кодами длиной до 57 бит и правильно обрабатывать flush:

#include <stdint.h>

// Write the low n bits of code, 0 <= n <= 57, to out[]. The bits above the low
// n in code must be zeros. If flush is true, then any remaining unwritten bits
// are put in the high bits of the last byte provided in out[], and the
// internal buffer is emptied. The return value is the number of bytes written
// to out[], in 0..8. stuff_bits() is not re-entrant.
int stuff_bits(char *out, uint64_t code, int n, int flush) {
    static uint64_t buf;
    static int bits = 0;
    buf = (buf << n) | code;
    bits += n;
    char *put = out;
    while (bits >= 8) {
        bits -= 8;
        *put++ = buf >> bits;
    }
    if (flush && bits) {
        *put++ = buf << (8 - bits);
        bits = 0;
    }
    return (int)(put - out);
}