Беда со сжатием в LZW

Question

У меня возникли проблемы при реализации компрессора LZW. Компрессор, кажется, работает нормально, но при обработке некоторых потоков он не помещает символ конца потока (определенный со значением 256), в результате декомпрессор зацикливается бесконечно. Код компрессора следующий:

int compress1(FILE* input, BIT_FILE* output) {
CODE next_code;         // next node
CODE current_code;      // current node
CODE index;             // node of the found character
int character;
int ret;

next_code = FIRST_CODE;

dictionary_init();

if ((current_code = getc(input)) == EOF)
    current_code = EOS;

while ((character = getc(input)) != EOF) {
    index  = dictionary_lookup(current_code, (SYMBOL)character);
    if (dictionary[index].code != UNUSED) {
        current_code = dictionary[index].code;
    }
    else {
        if (next_code <= MAX_CODE-1) {
            dictionary[index].code = next_code++;
            dictionary[index].parent = current_code;
            dictionary[index].symbol = (SYMBOL)character;
        }
        else {
            // handling full dictionary
            dictionary_init();
            next_code = FIRST_CODE;
        }
        ret = bit_write(output, (uint64_t) current_code, BITS);
        if( ret != 0)
            return -1;

        current_code = (CODE)character;
    }
}
ret = bit_write(output, (uint64_t) current_code, BITS);
if (ret != 0)
    return -1;

ret = bit_write(output, (uint64_t) EOS, BITS);
if (ret != 0)
    return -1;

if (bit_close(output) == -1) {
    printf("Ops: error during closing\n");
    return -1;
}

return 0;
}

CODE а также SYMBOL являются typedef соответственно uint32_t а также uint16_t, FIRST_CODE определяется как 257. Функция dictionary_init() просто инициализирует словарь, dictionary_lookup() возвращает индекс ребенка, имеющего символ character "родительского узла" current_node "(если он существует).

Запись двоичного файла определяется как:

int bit_write(BIT_FILE* bf, uint64_t data, int len)
{
int space, result, offset, wbits, udata;
uint64_t* p;
uint64_t tmp;

udata = (int)data;

if (bf == NULL || len < 1 || len > (8* sizeof(data)))
    return -1;

if (bf->reading == true)
    return -1;

while (len > 0) {
    space = bf->end - bf->next;
    if (space < 0) {
        return -1;
    }
    // if buffer is full, flush data to file and reinit BIT_IO struct
    if (space == 0) {
        result = bit_flush(bf);
        if (result < 0)
            return -1;
    }

    p = bf->buf + (bf->next/64);
    offset = bf->next % 64;
    wbits = 64 - offset;

    if (len < wbits)
        wbits = len;

    tmp = le64toh(*p);
    tmp |= (data << offset);
    *p = htole64(tmp);

    bf->next += wbits;
    len -= wbits;
    data >>= wbits;
}

return 0;
}

Я уже открыл файл с помощью другой функции, поэтому bit_write взять в качестве входных данных указатель на bf состав. Может кто-нибудь помочь мне найти ошибку?

Пример возникновения этой проблемы:

Если входная строка " Nel mezzo del cammi ", все работает нормально, и у меня есть следующий сжатый файл (в шестнадцатеричном формате, использующий 12 бит для кодирования символов):

4E 50 06 6C 00 02 6D 50 06 7A A0 07 6F 00 02 64
20 10 20 30 06 61 D0 06 6D 90 06 0D A0 00 00 01

Если я добавлю еще один символ в строку, в частности " Nel mezzo del cammin ", я получу следующий результат:

4E 50 06 6C 00 02 6D 50 06 7A A0 07 6F 00 02 64
20 10 20 30 06 61 D0 06 6D 90 06 6E D0 00 0A 00
10

Во втором случае он не записывает конец потока правильно.

РЕШЕНИЕ: убедитесь, что в буфере достаточно места для всего закодированного символа, который я собираюсь написать. Просто измените:

if (space == 0)

чтобы:

if(space == 0 && space < len)