Я начал готовить графику для игры Apple на Rust, и сделал спрайт яблока в виде PNG-файла. Но забыл, что для загрузки графики из файла нужна дополнительная библиотека SDL_image, которую нужно собирать и линковать. А так как сразу сборка не взлетела, то мне наскучило с ней возиться.
В то же время оригинальная игра Apple на БК-0010 не использует никакой загрузки графики из файлов и понятия не имеет про формат PNG.
И чтобы скрыть собственную беспомощность поддержать дух старой школы, я решил тоже хранить спрайты в собственном формате.
Подсчёт байтов
Я могу побайтово сохранить спрайт размером 32x30 пикселов в статической памяти программы, но он займёт почти четыре килобайта, так как каждый пиксел это RGB+alpha (прозрачность). Да и наплевать бы, но надо идти до конца.
Для более наглядного примера я возьму из интернета картинку размером 900x700 пикселов:
Это уже 2.5 мегабайта.
Палитра
Так как БК-0010 может рисовать всего 4 цвета, информацию о каждом цвете можно перенести в палитру. Палитра хранит каждый цвет в виде RGB ровно по одному разу. А в значениях пикселов мы вместо RGB указываем индекс цвета в палитре. Таким образом, каждый пиксел можно сократить до одного байта (при условии, что цветов не более 256), и картинка будет занимать "всего" 630 килобайт.
Этот шаг требуется для подготовки сжатия RLE, поэтому я оформлю его как отдельный этап.
Данный PHP-код получает из командной строки название png-файла, считывает данные из файла в объект $img и получает ширину и высоту изображения $w и $h.
Далее в цикле по координатам $y и $x нужно пройти по каждому пикселу в изображении и записать его цвет в палитру $color_lut. А параллельно записать индекс этого цвета из палитры в выходной массив $linear, который будет содержать одну длинную цепочку индексов (т.е. двумерную картинку вытягиваем, как распустившийся вязаный свитер, в одномерный массив).
На каждом шаге проверяется: если текущий цвет уже добавлен в $color_lut, то мы берём оттуда его индекс. Если же нет, то добавляем его туда с новым индексом. Нетрудно видеть, что $color_lut это хэш-таблица, где ключ это RGB-цвет, а значение – его индекс.
При этом пикселы с прозрачностью в палитру не добавляются и у них индекс зарезервирован как 0. Прозрачность будет обрабатываться отдельно.
RLE-сжатие
Получив цепочку индексов цвета в массиве $linear, можно заметить, что очень часто одни и те же индексы повторяются много раз подряд.
RLE обозначает Run-Length Encoding, и его суть в том, чтобы заменять цепочки одинаковых значений парами (V, N), где V это значение, а N – количество повторений. Нетрудно видеть, что последовательность, например, из 1000 единиц кодируется как (1, 1000), то есть объём данных уменьшается в 500 раз!
В то же время, если в данных нет цепочек одинаковых значений, кодирование пойдёт по худшему сценарию. Каждое значение будет выглядеть как (V, 1), и объём данных не уменьшится, а увеличится в 2 раза.
Чтобы этого не произошло, используется компромисс. Один бит в V выделяется как индикатор наличия повторов. В RLE значения V и N могут быть любого выбранного размера, например, 8, 16 или 32 бита. В нашем случае они по 8 бит.
Использовав один бит на служебные цели, мы уменьшаем диапазон V до 128 значений. Но это всё равно больше, чем 4. Для текущего проекта вполне подойдёт.
Итак, для начала надо написать саму функцию кодирования.
На вход она принимает массив $rle (по ссылке, так как будет модифицировать его), индекс цвета $index и длину фрагмента $len.
Далее, если $len равна 1, то $index просто записывается в $rle как есть, и готово.
Если же $len > 1, то мы устанавливаем служебный 8-й бит в индексе ($index |= 128) и должны записать в $rle сначала $index, затем $len. Но есть нюанс: в $rle длина фрагмента должна помещаться в байт, т.е. быть не более 255. При этом $len может хранить любую длину. Так что $len нарубается на куски ($chunk) меньше либо равно 255 и пишутся пары ($index, $chunk) до тех пор, пока $len не кончится.
Теперь, имея функцию encode(), пройдём по исходному массиву $linear, посчитаем цепочки одинаковых значений и закодируем их в выходной массив $rle:
И если теперь узнать длину полученного массива $rle, то она будет чуть менее 9 килобайт. Напомню, что мы начали с 2.5 мегабайта.
Для проверки сделаю разворачивание картинки из массива $rle.
Создам новый объект-изображение нужного размера и заполню его фон белым цветом:
Далее готовлю палитру $palette как инверсию хэш-таблицы $color_lut. То есть получается новая хэш-таблица (технически просто массив), где ключи это индексы 1, 2, 3, ..., а значения это RGB.
Затем последовательно из $rle читается индекс $index и определяется, включён ли в нём служебный бит. Если включён, то дополнительно читается длина фрагмента $len, иначе она равна 1.
Далее нужно просто получить RGB-цвет из палитры по индексу и записать его в картинку $len раз. В случае, если это прозрачный цвет ($index == 0), ничего не пишется, а только лишь двигаются текущие координаты пиксела.
Здесь есть одна неприятность. Нужно распущенную нить связать обратно в двумерную картинку, поэтому требуется проверять, когда координата $x дошла до края, чтобы увеличить координату $y и обнулить $x. И значит, в очередной раз требуется нарубить $len на подходящие куски.
Затем то, что получилось, сохраню как 'out.png':
imagepng($imgout, 'out.png');
И вот что получилось:
Данный алгоритм можно использовать для рисования картинок прямо на лету. В нём есть даже какая-никакая оптимизация, так как вместо рисования по одному пикселу можно рисовать целые горизонтальные фрагменты одного цвета. Кроме того, он очень быстро работает с прозрачностью, просто пропуская все прозрачные участки.
Но также можно использовать его, чтобы распаковать картинки в нормальные битмапы в памяти и затем уже использовать их как обычно.
Заключение
Сжатие RLE можно модифицировать многими способами – менять размер данных, порядок V и N, использовать служебные биты либо в V, либо в N, либо как-то более хитро и адаптивно, сортировать V по частоте использования, объединять V и N и т.п. Также можно исправить ситуацию с переносом координаты $x, если на этапе кодирования ограничивать длину фрагмента текущей строкой.
В общем, если рассмотреть, какие конкретно данные будут использоваться, алгоритм можно оптимизировать конкретно под них.
Ну а мне пока особо оптимизировать нечего, будy переносить это дело в Rust.
