форум группы Chief-Net :: Jon Menzies' Megapacker

Цитата:

Не секрет, что в одном отдельном тайле используются не все цвета из палитры.
И, наверно, редко можно встретить тайл, в котором используюся все цвета из палитры.
Это, значит, что мы можем для каждого тайла создать свой алфавит символов, который будет содержать от 1 до 16 символов (цветов).
Для того чтобы хранить информацию об алфавите будем использовать такой тип, как множество, размером в два байта,
где каждый бит множества будет говорить нам о том есть ли во множестве тот или иной цвет пикселя.
Например число 0х8080 в бинарном виде 10000000 10000000, говорит нам о том, что во множестве имеются цвета с индексами 7 и 15,
что в свою очередь означает, что в тайле присутствуют цвета с индексмаи 7 и 15, т.е. всего два цвета. А для того, чтобы
их закодировать достаточно 1 бита, '0' - для цвета 7 и '1' для цвета 15.
Это то, что касается пикселей. Мы также можем повторять идентичные тайлы, можем повторять тайлы, которые отличаются частично,
заменяя те пиксели, которые непохожи, декодируя их из сжатого потока.
Также мы можем повторять строки внутри тайла, если они полностью или частично похожи, также заменяя непохожие пиксели декодированными из потока.
Для повторения строк используются такой параметр как hmap размерностью в 1 байт, где каждый бит соответствует 1 строке.
Если бит = 1, то повторить строку, если = 0, то пиксели строк надо декодировать из потока.

Для повторения пикселей в строке используется параметр vmap размерностью в 1 байт.
При чём параметр vmap общий для всех строк. Если бит = 0, то надо считать 1 бит (персональный бит) из потока и тестировать этот бит, если он равен 0, то
надо декодировать пиксель из потока. Если бит равен 1, то повторяем последний(левый) пиксель.

Почти все значения сжаты методом усечённой бинарной кодировки.
Усечённая кодировка имеет конечный алфавит. Т.е. для кодирования/декодирования
мы должны заранее знать о количестве символов в алфавите. В зависимости от количества
символов меняется длина кода символа.

В алгоритме используются различные методы оптимизации и хитрости.
Например, зная значения последнего пикселя(левого) мы можем удалить его из множества тем самым мы уменьшим кол-во символов
во множестве, а значит сократим длину кодов для оставшихся символов, зная значения двух символов, левого и верхнего, можем удалить из множества
уже два символа и ещё более сократим длины кодов для оставшихся символов во множестве. При определённых условиях, когда во множестве всего 1 символ
длина кода символа составляет 0 бит.
На рисунке ниже представлен пример тайла. Множество для такого тайла [0, 1, 2, 3, 4, 5]. Всего 6 элементов. Очевидно,
для такого множества максимальная длина кода символа будет равна 3, а минимальная 2.
Коды этих символов:
0 - 00
1 - 01
2 - 100
3 - 101
4 - 110
5 - 111
Предположим, что мы сейчас должны декодировать второй пиксель второй строки.
Нам известен верхний пиксель 01 и левый пиксель 03. И мы точно знаем, что искомый пиксель неравен
этим двум пикселям. Тогда мы исключаем эти два пикселя из множества и оно приобретает такой вид [0, 2, 4, 5].
Соответственно, длина кодов этих символов тоже меняется:
0 - 00
2 - 01
4 - 10
5 - 11
таким образом максимальная длина кодов для символов уменьшилась на 1 бит.

В алгоритме используется два способа сжатия:
Первый основан на принципе повторения строк пикселей. 1 строка - 8 пикселей по горизонтали.
Всего 8 строк по 8 пикселей итого 64 пикселя.

Второй - основан на повторении тайлов с частичной заменой пикселей.

Алгоритм декомпрессии по шагам.

1. Сначала идёт 10 бит - кол-во тайлов в архиве.
2. Далее мы должны декодировать количество множеств пикселей, которое закодировано
методом усечённой бинарной кодировки. Количество множеств не может быть больше количества тайлов, но не должно превышать 512.
3. После того как декодировали количество множеств, надо декодировать сами множества.
Каждое множество либо кодируется 16 битами, либо как дельта между предыдущим множеством и декодируемым.
4. Дальше начинается цикл декодирования тайлов.
В цикле сперва декодируется индекс множества в списке множеств, который принадлежит декодируемому тайлу.
Далее читается бит, из которого ясно каким из методов закодирован тайл (методом повторения тайлов или методом повторения строк).
Первый тайл всегда закодирован методом повторения строк.
Дальше, я думаю, всё ясно из кода исходника.