Эксперименты с ANS на Z80 от Mr.Spiv

 __/\__ - ---------------------------------------------- -__/  \
\\ oO //  ANS experimentations with Z80 by Mr.Spiv       /  \__/
//_--_\  - ------------------------------------------- - \__/  \
   \/                                                       \__/

С тех пор как в районе 2014 года Ярослав (Ярек) Дуда представил алгоритм ANS (асимметричные числовые системы), мне всегда хотелось его опробовать, но, честно говоря, руки до экспериментов дошли только летом 2025 года. Моя способность прокрастинировать поистине феноменальна, да и математика давно перестала быть моей сильной стороной. Чем старше я становлюсь, тем меньше нового укладывается в голове и задерживается там... К тому же рабочие задачи обычно подчистую выгребают последние оставшиеся клетки мозга. Как бы то ни было, лучший способ чему-то научиться — сделать это на практике. Моей главной целью было написать реализации ANS, декодеры которых подходили бы для 8-битных систем, и прежде всего — для лучшего из всех, Z80.

В итоге я набросал прототипы на Python и C++ для всех трёх основных вариантов ANS:

• rANS — универсальная замена арифметическому кодированию;
• tANS — полностью табличный вариант ANS, который можно рассматривать как замену кодированию Хаффмана;
• rABS — двухсимвольный вариант rANS (0 и 1) с побитовым или побайтовым вводом.

Декодеры на ассемблере Z80 также готовы для кодеров tANS и rABS. Вся кодовая база выложена на GitHub:
https://github.com/jounikor/ans/

Эта скромная статья посвящена табличному ANS, то есть tANS:
https://github.com/jounikor/ans/blob/main/z80_tans_decoder.asm
а также трудностям и выводам, к которым я пришёл в процессе ковыряния ассемблерных декодеров для Z80. На этот раз я снова был готов пожертвовать размером кода и оперативной памятью ради скорости, хотя получившийся код на победу в size coding конкурсах явно не претендует. Процесс сжатия (encoding) эта статья по большей части оставляет читателю в качестве домашнего упражнения ;-) Некоторые термины здесь предполагают, что читатель в общих чертах уже знаком с ANS.

Поскольку нашей целью является Z80 и 8-битные платформы, есть ряд практических ограничений, которые сильно облегчают жизнь. Максимальный размер алфавита я выбрал равным 256, а значения отдельных символов лежат в диапазоне от 0 до 255. Частоты всех символов должны помещаться в 8 бит, что означает: максимальная частота одного символа не превышает 255. Частота 0 зарезервирована как маркер отсутствия символа. Сумма частот всех символов обязательно должна быть степенью двойки. Общая сумма частот всех символов не превышает 256, однако ни один отдельный символ не может иметь максимальную частоту (см. предыдущий пункт). Отсюда следует, что в сжатом файле/данных всегда должно присутствовать как минимум 2 символа.

Я потратил немало времени, размышляя о том, как бы построить таблицу частот, удовлетворяющую вышеописанным условиям, но при этом чтобы частота каждого символа тоже являлась степенью двойки. Это сделало бы сохранение частот в сжатом файле предельно простым: записывались бы только сами степени фиксированной битовой длины. Несмотря на все попытки, этот подход не взлетел, и я остановился на том, чтобы степенью двойки была только общая сумма частот всех символов. Основа моей реализации опирается на алгоритм целочисленной нормализации (Integer Normalization):
https://stackoverflow.com/q/31121591

На стороне декодера всё проще, так как все переданные в выходном файле частоты символов уже нормализованы к общей сумме, равной степени двойки.

Предположим, что общая сумма символов (то есть M) равна 32. Чтобы закодировать частоту каждого символа в выходном файле, нам потребуется 5 бит. Как закодировать частоты символов менее чем в 5 бит, особенно для несуществующих символов (с частотой 0)? С кодами Хаффмана и каноническими кодами это решалось так просто... В общем, интернет подсказал, что можно использовать, например, коды Райса или Райса-Голомба. Я остановился на кодах Райса со сдвигом K=2 бита.

Таким образом, мы всегда сохраняем K младших бит значения, а частное от деления (после сдвига значения на K бит вправо) кодируем унарным кодом. Значения от 0 до (1<<K)-1 занимают K+1 бит. В унарной части бит 0 служит маркером окончания. Пример на C, иллюстрирующий кодирование Райса для value с заданным K:

uint32_t r, q;
int total_bits, n = 1;
r = value & ((1 << K) - 1);
q = value >> K;
value = 0;
while (q > 0) {
    value = (value + 1) << 1;
    --q; ++n;
}
value = (value << K) | r;
total_bits = n + K;

Когда нам известны частоты всех символов, а их сумма равна степени двойки, мы можем сгенерировать таблицы для декодирования. Нам понадобятся всего 2 таблицы: таблица L_ для отображения состояния ANS (state_x) в символ s, и таблица Y_ для вычисления следующего состояния state_x после каждого декодированного символа.

Мне очень понравилась вот эта статья (https://medium.com/p/d1bebfc7e076/), где прекрасно объясняется базовый принцип построения таблиц. Визуализация там просто отличная.

Пусть наш алфавит состоит из символов S={a,b,c,d,e,f,g,h}, а общая сумма символов M равна 32. Частоты символов: F={2,6,9,0,0,2,6,7}. Теперь мы сгенерируем две таблицы по M записей в каждой. Заметьте, что размер алфавита может (и должен) быть меньше M, и ему вовсе не обязательно быть степенью двойки(!)

Выбор «функции распределения» (spreading function) для генерации таблиц tANS — целая наука, но я взял кое-что элементарное: простое числовое смещение, позволяющее обойти все ячейки таблицы без коллизий. Простые числа отлично подходят для этой цели. Определим функцию шага как f(state_x) = (state_x + 5) mod M. Также нам нужно выбрать начальное состояние (INITIAL_STATE). Вообще это задача компрессора, но tANS-декодер тоже должен знать его при инициализации таблиц. Я кинул кубик, и моим INITIAL_STATE стало число 3.

Одна из ключевых идей tANS — удерживать значение состояния ANS state_x внутри диапазона [L..2L), где в нашем случае L == M. Если M равно 32, состояние state_x должно находиться в пределах [32..64). Когда мы считываем следующее состояние state_x из таблиц декодирования, записанное там значение всегда меньше L, и нам нужно дочитать ещё k бит из потока, пока state_x снова не попадёт в диапазон [L..2L). И тут кроется приятное упрощение: зачем вообще возиться с диапазоном [L..2L), если по сути это то же самое, что и [0..M)? Это сильно упрощает и декодер, и работу с таблицами. Поэтому мой декодер хранит state_x в пределах [0..M), а не [L..2L).

Для каждого символа s из множества S с частотой f > 0 создаётся n записей (где f <= n < 2f) в таблице Y_[state_x] = n и таблице L_[state_x] = s.

После записи значений в таблицу на каждом шаге мы обновляем состояние: state_x = f(state_x). Таблица для необходимого количества входных бит k нам не нужна — мы можем определить его прямо во время выполнения.

На рисунке ниже показаны таблицы Y_ и L_ для символов из набора S:

state_x (INITIAL_STATE=3)
|0| | |v| | | | | | | | | | | | |1| | | | | | | | | | | | | | |1
|0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
table_Y:                        |
070a06020e080b07030f09090806100a0a0907110b0b0a08020c0c0b09030d0d
table_L:                        |
 h b g a c h b g a c h c g b c h|c g b c h c g b f h c g b f h c
значения k для наглядности:
 3 2 3 4 3 2 2 3 4 3 2 2 2 3 1 2|2 2 3 1 2 2 2 2 4 2 2 2 2 4 2 2

Один из возможных вариантов реализации построения таблиц Y_ и L_ на Z80 приведён ниже. Он не обязательно самый компактный и быстрый, но вполне достойный. Таблицы адресуются через регистр IX со смещением, что ограничивает размер одной таблицы 128 байтами (а значит, M не может быть больше 128). Для большинства практических задач этого более чем достаточно.

Таблицы Y_ и L_ можно расположить в памяти несколькими способами. Когда M не превышает 64, подойдёт следующая раскладка:

L_      EQU     M_
Y_      EQU     0
        org     (($+255) & 0xff00)
table_Y:
        ds      M_
table_L:
        ds      M_

Если M равно 128, сработает такой вариант (дисклеймер: сильно не тестировался):

L_      EQU     0
Y_      EQU     -M_
        ; Выравниваем table_L прямо перед границей 256 байт
        org     (($+255) & 0xff00)-M_
table_Y:
        ds      M_
table_L:
        ds      M_

Код генерации таблиц:

; Входные параметры:
; IX = указатель на таблицы Y_ и L_ (обе по M_ байт,
;      итого 2M_ байт). IX должен быть выровнен на 256 байт.
; A = начальное состояние state_x (INITIAL_STATE)
; B = количество символов в алфавите.
tans_build_decoding_tables:
        ld      de,0x8000
        ; E = символ s, начиная с 0
        ; D на самом деле битовый буфер ввода,
        ;   но работа с ним спрятана внутри макроса
        ;   EXTRACT_NEXT_SYMBOL_FREQ_TO_A..
_main_loop:
        push    bc
        push    af
        EXTRACT_NEXT_SYMBOL_FREQ_TO_A
        jr      z,_zero_symbol
        ld      b,a  ; B = f(частота)
        ld      c,a  ; C = f(частота)
        pop     af
_per_symbol_loop:
        push    ix
        push    af
        ; Позиция в таблицах, соответствующая state_x
        ld      ixl,a
        ; Y_[state_x] = n
        ld      (ix+Y_),c
        inc     c
        ; L_[state_x] = s
        ld      (ix+L_),e
        ; Шаг распределения: state_x = f(state_x)
        pop     af
        pop     ix
        add     a,SPREAD_STEP
        ; гарантируем 0 <= state_x < M
        and     M_-1
        ;
        djnz    _per_symbol_loop
        ; Трюк для пропуска команды без jr (CP nn);
        ; POP AF уже был выполнен
        db      $fe
_zero_symbol:
        pop     af
        pop     bc
        inc     e
        djnz    _main_loop
        ret

После того как обе таблицы Y_ и L_ построены, декодер получается чрезвычайно простым. Так как у нас нет таблицы для k (числа бит, которые нужно дочитать из сжатого потока для обновления state_x), мы просто крутим цикл до тех пор, пока state_x >= M. Декодер обязан всегда прочитать хотя бы 1 бит (то есть неявно k >= 1). Один из вариантов реализации tANS-декодера на Z80 выглядит так. Уверен, опытные Z80-колдуны смогут соптимизировать его ещё сильнее :)

; Входные параметры:
;   IX = указатель на таблицы Y_ и L_ (обе по M_ байт,
;        всего 2M_ байт). IX выровнен по границе 256 байт.
;   HL = указатель на конец сжатых данных (как известно,
;        поток tANS декодируется с конца к началу)
;   C = входной битовый буфер
;   A = state_x
; Выходные данные:
;   A = новое значение state_x
;   B = декодированный символ
; Портит регистры:
;   C и HL
tans_decode_symbol:
        ; Индекс в таблицах согласно state_x
        ld      ixl,a
        ; получаем символ
        ld      b,(ix+L_)  ; B = символ
        ld      a,(ix+Y_)  ; A = следующее state_x
        ; Дочитывание бит без таблицы k,
        ; пока state_x >= M_
_do_while:
        sla     c
        jr      nz,_not_empty
        dec     hl
        ld      c,(hl)
        rl      c
_not_empty:
        adc     a,a
        cp      M_
        jr      c,_do_while
        ; Приводим состояние к диапазону [0..M) (или [L..2L))
        and     M_-1
        ret

Всё оказалось достаточно просто и компактно. Если логика декодирования всё ещё кажется туманной, рекомендую смоделировать процесс построения таблиц на листке бумаги в клеточку с небольшим алфавитом и маленьким значением M.