Лабораторная 2: LZW (TIFF)

Написать функцию, выполняющую декодирование сжатых LZW данных (вариант из стандарта TIFF).

Прототип функции:

size_t lzw_decode(const uint8_t *in, size_t in_size, uint8_t *restrict out, size_t out_size);

Возвращаемое значение: количество декодированных байт или -1 при ошибке.

Детали реализации

Небольшой комментарий по поводу моего (Белоус Д.П.) решения.

Реализация 64-битная, помимо этого никакие расширения не используются.

Таблица кодов (декодированных строк) хранится как (длина, первый_символ, значение), где значение — либо явно хранящаяся строка, либо указатель на место в out, куда эта строка уже когда-то была напечатана. Т.е. в решении используется small-object оптимизация.

• ветка slow — не использует out_size, печатает маленькие строки аккуратно (с помощью switch-case), но медленно;
• ветка main, основная — не выходит за границы out буфера, печатает маленькие строки аккуратно только если мы пишем в конец буфера;
• ветка fast — может вылезти на <= 7 байтов за границу out буфера, печатает всегда по 8 байтов за раз.

Вывод группами по 8 байтов (даже если декодированная строка на самом деле имеет меньшую длину) позволяет существенно ускорить программу. Если строка имела, например, длину 3 байта, то оставшиеся 7 байтов будут заполнены мусором (который потом затрётся корректным выводом следующих декодированных строк).

Другие использованные микро-оптимизации:

• выровненное чтение по 4 байта;
• cache/memory-friendly код, т.е. выравнивание по 8 байт обращений к стеку (добавление padding'а где нужно), alignment констант (dd);
• минимизация условных, абсолютных, и косвенных переходов, особенно switch-case'ов;
• где-то чуть-чуть копипасты (но прирост к производительности), где-то дополнительный условный переход, но зато он хорошо предсказывается и обходит свитч;
• использование lea вместо add/mult с константой и подобные маленькие хитрости;
• breaking regestry dependency chain.

Другие комментарии можно найти непосредственно в lsw64.asm