Автор несколько лет назад сжимал данные для картриджа SNES с помощью алгоритма LZ4. Потом он написал реализации для процессоров Motorola 6809 и 68000 (для Tandy Color Computer и Sega Genesis), а недавно добавил версии для Z80, Intel 8080, 8086 и 6502. В этой статье он подробно разбирает, как устроен LZ4 и почему он так хорошо ложится на старые 8- и 16-битные платформы.
LZ4 относится к классу LZ77. Алгоритм разбивает поток на последовательности: сначала идут литералы (скопированные байты), затем обратная ссылка (offset + длина, указывающие, откуда в уже распакованном выводе скопировать данные). Первый байт последовательности кодирует длины обеих частей: верхние 4 бита — длина литералов, нижние 4 бита — длина обратной ссылки (плюс 4, так как короче 4 байта копировать невыгодно). Если длины больше 15, добавляются дополнительные байты-расширения. Автор упростил формат, убрав стандартный фрейм: данные просто завершаются двумя нулевыми байтами (нулевой offset служит сигналом остановки).
Главное ограничение LZ4 для декодеров — последняя последовательность в блоке должна содержать только литералы. Это упрощает проверку окончания.
Реализации для разных процессоров отличаются архитектурными особенностями:
— Z80 отлично подходит благодаря инструкции LDIR (блочное копирование). Нужны всего два долгоживущих указателя (source и destination), третий временно заменяет source при обратной ссылке. Стек используется минимально — только для подмены HL через EX (SP),HL.
— Intel 8080 почти копирует Z80, но без LDIR и 16-битного вычитания. Вместо LDIR — ручной цикл, вместо SBC HL,BC — два 8-битных вычитания. Аккумулятор загружен сильнее, чаще приходится сохранять регистры в стек.
— Intel 8086 позволяет вообще не трогать стек для временных значений (достаточно регистров), но ABI требует сохранять BX и BP. Строковые инструкции (LODSB, STOSB, MOVSB с префиксом REP) работают как LDIR, но даже удобнее. Автор добавил поддержку far pointers (сегментная адресация на 1 МБ), что потребовало жонглирования сегментными регистрами.
— MOS Technology 6502 — самый сложный случай. У него нет регистров-указателей, 8-битный стек, слабая поддержка 16-битных операций. Алгоритму неудобно: 6502 предпочитает работать с массивами и индексами, а LZ4 требует несоответствия скоростей продвижения указателей. Пришлось написать отдельную функцию блочного копирования. Четыре байта scratch space в zero page хранят source и destination pointers, ещё четыре — в обычной памяти. Из-за ограничений архитектуры код получился самым громоздким.
Все реализации для 8080, Z80 и 8086 настолько похожи, что автор отслеживает их параллельно, указывая расхождения — например, на Z80 выгоднее использовать 8080-совместимые команды (RRCA вместо SRL A), потому что они короче и быстрее.