Сжатие и упаковка. hrum3.5, hrust1, hrust2, laser compact x.x. [Архив] - Speccy

Hrumer

01.04.2014, 19:50

Добрый вечер!

В День Дурака хотелось бы открыть свою новую тему, в которой осветить особенности, хитрости, и прочие радости сабжа, тем более что, в общем то и обещал.

Алгоритмы выдуманные(в т.ч. велосипедные), реализованные, не реализованные и непридуманные(пока еще). Буду пополнять тему, а пока начну с краткого. Вдруг кому пригодится. Буду рад, если кто поделится мыслями.

Совершенно ясно, что писатели пакеров-депакеров, архиваторов берут, придумывают всякие эммм... хорошие вещи, и никому ничего не говорят. Но бывают и говорят, но очень уж редко. Или того хуже, патентуют :(. Но здесь не об этом. Заглянете в какой архиватор(исходники), а там такого напридумано... И никто ниче не пишет, что такого придумал. Высшая математика, теоремы, теория вероятностей и прочее...

Для сабжа все проще! Никакой вышки. 15-19 лет прошло, можно кое что вспомнить ;)

Итак, общее для сабжевых пакеров: в них не все коды задействованы... Почему? Инфу выложу позже...

Для затравки, с хруста1:
Где то в середине 2013г понял, что кое чего пропустил в формате хруста1. Открыл записи, и правда, ага. Светокопию где была зарыта собака выложу завтра. Или в ближайшие полгода. Шутка. Записи 96-97 года. Хех.

Итак, в хрусте1, помимо обычного LZ применяется еще кодирование вида AxC, т.е. такого, когда при ранее встреченной последовательности ABC вдруг(ну надо же!) встречается AEC. Берем, и вместо неё пишем код особый, далее расстояние, а потом и символ "Е". Это позволяет на уж совсем вроде бы непакующихся данных кое что сжимать.

Дистанция при этом кодировалась вариантами 16+32+32-1 = 79. т.е. от 1 до 79. Дистанциям от 1 до 16 присваивался код более короткий. После какого то ветвления (т.е. префикса), в виде 4 бит. Однако, такую же последовательность, AEC, при ранее встреченной последовательности ABC на дистанции от 1 до 8 байт можно было закодировать по другому, в виде <LEN=1, DIST=1..8>. В результате последний вариант проверялся первым, и кодирование типа AxC для дистанций 1..8 не применялось. А значит, для кодирования дистанций для случая 1..16, а фактически для 9..16 хватало бы 3 бит, а не 4. Что привело бы к повышению сжатия.

Продолжу не 1 апреля...

alone

01.04.2014, 20:12

Hrumer

01.04.2014, 20:21

Приклеивать к распаковываемому блоку слева депакер. Т.е. сжатие с опорой на код депакера. (ПЗУ использовать нельзя - оно у всех разное.)

Пробовать паковать не только вперёд, но и назад, и выбирать лучший вариант из двух.

Зачётный словарь! Это свежо и круто! Паковать и из двух направлений выбирать - это да, слыхал, тоже хорошо.

Про варианты laser compact 6 и 7 и hrust3 застолблю, есть интересная инфа, выложу позже.

alone

01.04.2014, 20:26

Ещё можно посмотреть, какие литералы не используются, и засунуть на их место контрольные коды.

introspec

01.04.2014, 20:27

Приклеивать к распаковываемому блоку слева депакер. Т.е. сжатие с опорой на код депакера. (ПЗУ использовать нельзя - оно у всех разное.)

Пробовать паковать не только вперёд, но и назад, и выбирать лучший вариант из двух.Опасные идеи! Первая приведёт к тому, что мелкие правки распаковщика могут испортить сжатый заранее блок. Кроме того, они привяжут сжатый блок к конкретному распаковщику, в то время как в наше время очень часто бывает удобным именно что выбирать распаковщик из нескольких возможных.

Идея с запаковкой в обоих направлениях - правильная, но нужно делать её опцией, а не автоматом, т.к. при сборке загрузчика как правило важно знать, какой вид внахлёста будет применяться при распаковке.

alone

01.04.2014, 20:29

Первая приведёт к тому, что мелкие правки распаковщика могут испортить сжатый заранее блок. Кроме того, они привяжут сжатый блок к конкретному распаковщику, в то время как в наше время очень часто бывает удобным именно что выбирать распаковщик из нескольких возможных.
Использование общего распаковщика на несколько блоков - это одна опция, а затачивание распаковщика под конкретный блок - другая. Просьба не путать.

introspec

01.04.2014, 20:31

Использование общего распаковщика на несколько блоков - это одна опция, а затачивание распаковщика под конкретный блок - другая. Просьба не путать.
Я не путаю. Я прошу не делать это магистральным путём развития.

Hrumer

01.04.2014, 20:34

Я не путаю. Я прошу не делать это магистральным путём развития.

Не боись, тут люди в ветке тему понимают, что для чего.

В депакере лазеркомпакта, я делал еще короче депакер, но выкинул, ибо очень тормозно распаковывает. А надо было приложить вариант, вдруг кому пригодилось бы. Так и тут. Вдруг(!) кому пригодится.

alone

01.04.2014, 20:35

А как же паковать 1K/4K интры, если не делать это магистральным путём развития?

---------- Post added at 20:35 ---------- Previous post was at 20:34 ----------

В других программах экстремальное сжатие по сути и не нужно - сотней байт больше, сотней меньше, разница небольшая.

introspec

01.04.2014, 20:38

А как же паковать 1K/4K интры, если не делать это магистральным путём развития?
Для таких интр, имхо, нужно отступать назад в прошлое, т.е. идти обратно к несложным распаковщикам, т.к. разница в коэффициентах сжатия на небольших файлах нивелируется, а на размере самого распаковщика можно выиграть очень здорово. А вообще, да, нужны комплексные решения, что-то вроде оптимального распаковщика для конкретного бинарника.

Hrumer

01.04.2014, 20:46

Для таких интр, имхо, нужно отступать назад в прошлое, т.е. идти обратно к несложным распаковщикам, т.к. разница в коэффициентах сжатия на небольших файлах нивелируется, а на размере самого распаковщика можно выиграть очень здорово. А вообще, да, нужны комплексные решения, что-то вроде оптимального распаковщика для конкретного бинарника.

Если кратко - удивил. Кратко и отвечу - ну вот будет флажок, мол, опирайся на депакер, и используй выгруженный депакер. И всё. Никаких споров. Хочешь-юзай, опционально же.

introspec

01.04.2014, 20:55

Приведу пример чтобы не быть голословным. При сжатии графики для недавней 1к интры мне нужно было упаковать файл в 3072 байта. Размер кода по сравнению с размером графики был вторичен. Самое лучшее сжатие было достигнуто Exomizer (638 байт). Остальные упаковщики сгруппировались где-то в районе 670-690 байт. Но самый компактный распаковщик для Exomizer требует 169 байт, в то время как распаковщик для самого примитивного компрессора в моих тестах (zx7) требовал всего 69 байт. Т.е. увеличение размера распаковщика может запросто нивелировать выигрыш от повышенного коэффициента сжатия, раз уж мы думаем о упаковщиках для сайз-кодинга.

Shadow Maker

01.04.2014, 20:55

Еще бы конечно хотелось, чтобы он всегда распаковывал то, что наупаковывал. Что упакованные данные не затираются распакованными. Очень помогло бы, а то упаковываешь бывало блок, и все вроде работает на первый взгляд после распаковки, но на самом деле - где-то в середине что-то наехало и не распаковало. Особо актуально для больших блоков, когда места нет.

Hrumer

01.04.2014, 21:27

alone

01.04.2014, 21:28

Надо давать возможность при распаковке выделять память без наложения, а то сейчас даже не спрашивают.

BlastOff

05.04.2014, 15:43

Краткое описание алгоритма, про который рассказывал Хрумер, в приложении.

jerri

05.04.2014, 16:37

када ждать новую версию ?

Hrumer

07.04.2014, 05:16

Не скоро. Там и так много чего перепроверить надо, а еще и LVD несколько лет назад сделал mhmt с алгоритмом OLZH c с форматом хранения MegaLZ, hrum3.5 or hrust1.x format (default is MegaLZ), чем сильно поднял планку, которую тяжело перепрыгнуть. Буду пока laser compact ускорять.

jerri

07.04.2014, 08:51

Hrumer, а если просто перевыпустить Hrum 3.х под вин?

Hrumer

07.04.2014, 10:39

у hrum3 и так уже есть порт 1:1 и есть с OLZH.(не мои) А если имеешь ввиду hrust3, то вопросы то те же остаются, там надо протестить как дистанции для длины =2 кодировать (768 байт дистанции, похоже, это чересчур, правильнее 256 или 512, настраиваемо(?) с увеличением len при длине дистанций 256 или 512), убрать явную неоптимальность кодирования дистанций для len>2 (там, кажется, вообще перекрытие кодов идет для дистанций <=512), и там еще куча всего...

jerri

07.04.2014, 11:05

Hrumer, не не Хруст это другое... А именно официальная версия. Чтобы с бесстековым форматом как в Hrust 2 и компактным распаковщиком меньше чем в MegaLZ

Hrumer

07.04.2014, 21:05

Hrumer, не не Хруст это другое... А именно официальная версия. Чтобы с бесстековым форматом как в Hrust 2 и компактным распаковщиком меньше чем в MegaLZ

Jerri, я тут взглянул на кодирование hrum и megalz. Последний более универсальный вроде бы. А у hrum формат как бы должен жать лучше плохопакуемые данные, а на включениях текста, графики он начинает проигрывать, так, не? Я протестил на mhmt несколько файлов, вроде megalz лучше сжимает, причем байтов на 100(Несколько байт-десятков байт можно отвести на то, что в hrum окно могло бы быть на 256 больше, всего то вставить надо команду типа DEC H). Или мне попались не те тестовые файлы?

jerri

08.04.2014, 02:05

Hrumer, Хрум лучше жмет код. Да. графику лучше жмет Хруст.
МегаЛЗ хз. я еще статистику не накопил.

Hrumer

08.04.2014, 19:45

jerri, Всё, до меня дошло. Посмотрел внимательно, как устроены депакеры у других. EXX нету. Как будто не для z80 писали. Формат hrum'а+увеличение dist на 256 (т.к. это ограничение фактически придуманное для скорости паковки)+депакер типа hrust2+пакер OLZH и своя ниша есть. Последние X байт явно ведь не надо хранить где нибудь, это же не модно сейчас. :)

jerri

08.04.2014, 22:01

Hrumer, ну последние байты это нужно только если чужой снапшот кусками сжимаешь.
А если свое что-то то тут до бита известно что где лежит

Hrumer

10.04.2014, 08:43

Если кому интересно, (типа похвалюсь!) почему сжатие было быстрым, и почему на некоторых файлах в режиме best тормозилось. Без заумных слов, одни схемы:

Файл: | Таблица зацикленная,
| Указывает на предыдущее
| вхождение символа:

#8000 A<----+ #0000
#8001 B | #0000
#8002 C | #0000
#8003 D | #0000
... |
|
#8010 A<--+ +-- #8000
#8011 E |
#8012 C |
... |
|
#8030 A +---- #8010
#8031 F
#8032 D
...

#8070 A <--- Мы тут.
#8071 B
#8072 C

Таблица последних вхождений символов:

A #8030
B #8001
...
--------------------------

Всё ОК, но есть фейл на таких вот данных:

#8000 A<------+ #0000
#8001 A<----+ +-#8000
#8002 A<--+ +---#8001
#8003 A<+ +-----#8002
.... +---+
|
#8010 A<- +---#8003
#8011 A<- <-#8010
#8012 A<--+ <-#8011
.... |
|
#8030 A +---- #8012
#8031 A #8030
#8032 A #8031
....

#8070 A <--- Мы тут. Впереди печаль.
#8071 A
#8072 A

В пакере в режимах fast и good эти таблицы заполнялись частично, чтобы скорость не падала. В 95 году это типа было крута. Сейчас все проще - в свободном доступе много инфы, в т.ч. на русском. Например, кандидатская Кадача. Там много всего написано, читать в общем, интересно.

В хрусте2 поиск идет не по одному символу, а по символу и нескольким битам следующего символа.

Позже выложу схему, алгоритм, который без потери коэффициента сжатия решает вопрос по скорости с такими "рыхлыми" файлами.

alone

11.04.2014, 23:34

Почитал про нибблы Титуса, и пришла в голову новая идея.

Что если у нас есть ветка, которая вставляет L байтов (i=0..L-1) следующим образом:
mem[pointer+i] = mem[pointer+i-disp] xor <data[i]>
Где <data[i]> - только младшие N битов, причём N вычисляется так (вариация на тему DAKX):

N=curN[L]
Читаем из потока биты и считаем число единиц M - до первого нуля или пока N+M-1 < 8
N=N+M-1
curN[pointer mod disp]=N

Такое кодирование может оптимизировать много вызовов типа:
ld hl,nn
ld a,n
call nn

или развёрнутых лупов типа
add hl,bc
ld a,h
ld e,n
ld (de),a

В последнем случае L=disp.

Titus

12.04.2014, 00:02

mem[pointer+i] = mem[pointer+i-disp] xor <data[i]>
Где <data[i]> - только младшие N битов, причём N вычисляется так (вариация на тему DAKX):

Почему XOR, а не ADD?

alone

12.04.2014, 14:01

Потому что, например, между значениями 2 и 7 нужно ксорить всего 3 бита, а для сложения надо 3 бита и знак, т.е. 4 бита.

---------- Post added at 14:01 ---------- Previous post was at 14:00 ----------

Вообще интересно было бы послушать идеи, как в рамках этой концепции кодировать ксоры типа #80 (1 сдвинутый бит).

Hrumer

13.04.2014, 08:46

Я б тоже предпочел XOR. С одно стороны. С другой - бывают таблицы с увеличивающимися значениями. С третьей - надо же тестировать! И тут возникает вопрос на чем. Предлагаю в соседней ветке обсудить набор тестовых файлов, в т.ч. подброку игр, дем, текстов, графики, смешанных данных.

Но эта ветка о другом. А вы читали http://cbloomrants.blogspot.ru/2010/08/08-20-10-deobfuscating-lzma.html? Вот этот кусок интересен:

ADDENDUM : here's an illustration of how the special LZMA modes help on structured data. Say you have a file of structs; the structs are 72 bytes long. Within each struct are a bunch of uint32, floats, stuff like that. Within something like a float, you will have a byte which is often very correlated, and some bytes that are near random. So we might have something like :

[00,00,40,00] [7F 00 3F 71] ... 72-8 bytes ... [00,00,40,00] [7E 00 4C 2F]
... history ... * start here

we will encode :

00,00,40,00 :
4 byte match at offset 72
(offset 72 is probably offset0 so this is a rep0 match)

7E :
delta literal
encode 7E ^ 7F = 1

00 :
one byte match to offset 72 (rep0)

4C :
delta literal
encode 4C ^ 3F = 0x73

2F :
regular literal

Also because of the position and state-based coding, if certain literals occur often in the same spot in the pattern, that will be captured very well.

Note that this is not really the "holy grail" of compression which is a compressor that figures out the state-structure of the data and uses that, but it is much closer than anything in the past. (eg. it doesn't actually figure out that the first dword of the structure is a float, and you could easily confuse it, if your struct was 73 bytes long for example, the positions would no longer work in simple bottom-bits cycles).

В хруст1, особенно в реализации mhmt подобного рода структурность сжимается кодом вида AxC(вставной байт). Надо бы просчитать закономерность, как изменяется вставной байт, если всего на 1-2бита, то можно выиграть.

А, формат hrum4 расписал. Ннадо сюда?
Это улучшенный hrum3.5:
Нет неиспользованных кодов.
Две переменных, передающихся от кодера к декодеру, для оптимизации дистанций и длин.

Hrumer

13.04.2014, 10:52

На днях встретил: http://www.compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf

В.В. Семенюк, на русском, 2001год. Особенно интересен разбор LZRW 1-4. Рекомендую. Мало что конечно можно применить на спеке, потому как распаковщики будут тормозные, и потребуют лишнюю память.

Hrumer

14.04.2014, 08:59

Что если у нас есть ветка, которая вставляет L байтов (i=0..L-1) следующим образом:
mem[pointer+i] = mem[pointer+i-disp] xor <data[i]>
Где <data[i]> - только младшие N битов, причём N вычисляется так (вариация на тему DAKX):

N=curN[L]
Читаем из потока биты и считаем число единиц M - до первого нуля или пока N+M-1 < 8
N=N+M-1
curN[pointer mod disp]=N

Такое кодирование может оптимизировать много вызовов типа:
ld hl,nn
ld a,n
call nn

или развёрнутых лупов типа
add hl,bc
ld a,h
ld e,n
ld (de),a

В последнем случае L=disp.

Ты прям как Алекс Юстасу, сразу зашифровал и закодил :)

Я так понимаю, на примере:

Ранее встречалось:

00 11 56 92 34 CD

встретилось:

01 10 56 93 36 CD

Кодируем длину, дистанцию, колво бит, от 1 до.. ну, наверное, 4, и далее биты. В результате наложения этих бит по XOR с ранее встреченной строкой получаем текущую строку.

Верно?

---------- Post added at 11:59 ---------- Previous post was at 11:50 ----------

Потому что, например, между значениями 2 и 7 нужно ксорить всего 3 бита, а для сложения надо 3 бита и знак, т.е. 4 бита.

---------- Post added at 14:01 ---------- Previous post was at 14:00 ----------

Вообще интересно было бы послушать идеи, как в рамках этой концепции кодировать ксоры типа #80 (1 сдвинутый бит).

Добавить маску для битов в виде 1 байта. %10000000. Можно вот так даже:
%10101010. Типа, есть данные, где четные биты не меняются.

upd: при таком подходе в 1 байте уже есть инфа как о месте изменяющихся бит, так и о длине бит.

Hrumer

26.10.2014, 18:24

К Laser Compact 5.2 "портированным" на си Никитой Бурнашевым в 2004г добавил Optimal LZH. Выгода от 30 до 100 байт. Осталось прикрутить депакер.

Надо сделать поддержку сжатия 1/3, 2/3 экрана?
Надо сделать депакер еще более коротким, но в 1,5 раза медленнее?
И еще более коротким, но не релоцируемым?

goodboy

26.10.2014, 18:50

Надо сделать депакер еще более коротким, но в 1,5 раза медленнее?
если это относится к выводу картинки, то наверное нет.
(кому нравятся аттрибуты выводимые рывком)

Hrumer

26.10.2014, 18:54

А, кстати, аттрибуты с такой же скоростью будут выводиться.

goodboy

26.10.2014, 19:21

а про `оптимизацию` аттрибутов не-думал ?
http://savepic.org/6339760.png

оригинал
http://savepic.ru/6124201.png

обработка
http://savepic.org/6317232.png

обработанный вариант после упаковки LC5.2 на один сектор меньше

Hrumer

26.10.2014, 19:51

Раньше думал. Но мой алгоритм оптимизации 1999 года давал отрицательный результат. :) Дай пожалуйста эти 2 варианта в 6912. Результат сюда выложу, сравним всё.

Апдейт:
Не 1999 года, и не для LC5. Я такой алгоритм делал для LC4, где особое отношение к "0". Да и то алгоритм был тупым - инвертировал цвета, если получалось нулей больше.

Апд2: Неужели это такой хитро-простой алгоритм, который в основе своей для решения, чего же делать, опирается не на ч-б картинку, а на аттрибуты, и обработка начинается с аттрибутов???

Апд3: На вскидку и это представление не самое оптимальное, см. верхний правый прямоугольник размером примерно 9*1. надо бы его инвертировать. Но надо тестить.

Апд4: нашел оригинал. На оригинале выигрыш 98 байт. Без изменения картинки, какая есть, такая есть.

Апд5: они просматриваются, например, фаром с плагинами от halfelf.
Апд6: забыл сказать самое главное - 1 сектор это круто, но сколько байтов?

goodboy

26.10.2014, 23:16

Апд6: забыл сказать самое главное - 1 сектор это круто, но сколько байтов?
111

Shadow Maker

26.10.2014, 23:48

А где лежит упаковщик на PC в LC5?

goodboy

27.10.2014, 00:15

даже не ожидал что оптимайзер который я использую оказался таким древним - 1994год.
(у меня все рабочии программы в снэпшотах для быстроты загрузки и заставку с копирайтами я давно не видел)

http://savepic.org/6315259.png

на тот момент это была достаточно мощная программа, 5 вариантов упаковки + красивый вывод картинки
(fade in/out)

http://savepic.ru/6154971.png

сейчас LC 5.x сжимает лучше, но оптимизировав предварительно картинку можно выиграть в размере.

главный минус уничтожение скрытых надписей и нежелательное изменение аттрибутов - если часть картинки (рамка) используется в игре. как пример LastNinjaII,Barbarian

Alexandr Medvedev

27.10.2014, 11:14

А где лежит упаковщик на PC в LC5?Здесь не оно?
http://zx-pk.ru/showpost.php?p=22982&postcount=18

Shadow Maker

27.10.2014, 13:34

Ну я имел ввиду скомпилированный продукт под windows, чтобы можно было пользоваться. Может скомпилируешь лазер компакт? Хруст есть от psb.

Hrumer

27.10.2014, 20:14

goodboy

27.10.2014, 20:29

После Screen Optimizer:
там кстати оптимизацию можно несколько раз применить, иногда ещё что-то правится.
(на мотоциклах смотреть верхний правый угол)

Alexandr Medvedev

28.10.2014, 08:37

Ну я имел ввиду скомпилированный продукт под windowsЛови.

Hrumer

28.10.2014, 12:52

Если это просто скомприлированный исходник Никиты Бурнашева, то он сохраняет файлы без заголовка(и без кода картинки) и без депакера. Плюс поймал баг, при дистанции ровно #300 некорректно код записывается при длине 3 и более. При длине = 2 этот вариант отбрасывается. Надо поправлять дистанция >= 0x300 на дистанция > 0x300 в трех местах.

Апдейт:

Добавил депакер. Готово.
Сжатие лучше, чем оригинальный ZX Laser Compact 5.2 на 30-110 байт.

Barmaley_m

31.10.2014, 01:16

Я думаю, что релоцируемость распаковщика - это расточительство. Нужно просто спросить пользователя о желаемом адресе размещения распаковщика, и настроить его код на этот адрес. Хоть пара байт - а будет сэкономлена.

Если есть возможность уменьшить размер распаковщика, пусть даже ценой его замедления - надо использовать. Для 1к/4к интр это существенно. Малый размер файлов сделает замедление незаметным. Если кому-то не нравится медленное и неравномерное появление картинки - то можно распаковать не в экран, а в другое место, а потом перекинуть данные лдиром.

И вообще, назревает радикальный подход - генерация кода распаковщика. С учетом пожеланий пользователя, характера сжимаемых данных и т.д. Хотя бы компоновка распаковщика из заранее нарезанных кусков.

В режиме "минимизации размера брутто" компрессор может пробовать сжимать файл с отключением некоторых особенностей кодирования, если это приводит к уменьшению размера распаковщика, и сравнивать друг с другом размеры данных+распаковщика, и выбирать наиболее выгодный вариант с точки зрения суммарной длины.

goodboy

31.10.2014, 10:53

Я думаю, что релоцируемость распаковщика - это расточительство.
и скорее всего call на RET в пзу для определения адреса вызова, что многие неодобряют.

---------- Post added at 10:53 ---------- Previous post was at 10:49 ----------

Апдейт:
а полностью автоном можно сделать ?
а то начинается libgcc....dll не найдено

Vitamin

31.10.2014, 11:04

и скорее всего call на RET в пзу для определения адреса вызова, что многие неодобряют.
Из всех известных мне пакеров так делают только CompressorCode4. А вот экранные пакеры- так вообще все.

Hrumer

08.11.2014, 19:58

Скомпилил с нужной опцией. Теперь вроде не ругается на отсутствие библиотек.

Убрать релоцируемость ок - опционально, с ключом буду делать. И для медленного депакера тоже.

Отключение некторых особенностей - проигрыш 30-100 байт(отказ от перевернутого LZ). Попалась одна картинка, где улучшение 19 байт, но это особенная картинка, заставка компрессора MSP.

А так - разве что в других версиях можно типа зашивать таблички длиной в 4-16 байт в сам распаковщик, будет более оптимальное кодирование для конкретного экрана.

Shadow Maker

23.11.2014, 20:32

Буду потестить! Надо каких-нибудь адаптаций под тырдос с заставками поделать-посмотреть.

Eugene85

07.02.2015, 14:34

Всем привет.

От нечего делать решил реализовать на PC оптимальный компрессор для формата Hrust 2. Придумал алгоритм, выполняющий максимальное теоретически возможное сжатие. Думал, что сделаю открытие, а тут оказывается уже придумали optimal lzh :) Ну да ладно, не пропадать же добру. Выкладываю здесь.

Хотя кое-что интересное в моей реализации всё же есть. Когда делал перебор дистанций для выбора наилучшей ссылки, я задумался о том, как сделать это красивее, чем полным перебором со сравнением строк в каждой позиции. В mhmt это сделано почти прямо: цикл по дистанциям, а в нём цикл, сканирующий строку до первого расхождения. "Почти", потому что реализовано раннее отсечение с помощью хэш-функции. На определённом виде входных файлов (с большой избыточностью) mhmt подвисает надолго. Я нашёл способ сделать это один проход (использовав т.н. Z-функцию).

Но практический результат получился не очень ценный, т.к. на типичных данных работает медленнее чем mhmt. Время работы алгоритма пропорционально квадрату размера файла и практически не зависит от характера данных. В плюсы можно записать простоту реализации: собственно ядро компрессора весьма простое, с минимумом ветвлений.

Напоследок изложу результаты сравнения сжатия Hrust 1 (mhmt) и Hrust 2, полученную на ~3500 типичных спектрумовских файлах. Разница в размере сжатых файлов - от -6% до +6%; в среднем Hrust 2 проигрывает 0.8%.

В сравнении с оригинальным компрессором Hrust 2 оптимальный выигрывает в среднем 3.5%.

Hrumer

10.02.2015, 07:01

Eugene85, Огого! :) и через 15 лет новые версии :). Если требуется более высокая скорость, посмотри на MMC - Morphing Match Chain.(вроде в 2010 году придумали). Например, вот тут: http://fastcompression.blogspot.ru/p/mmc-morphing-match-chain.html. Я пока не разбирался что и как оно там подробно устроено, но скорость сжатия вырастает значительно.

Если тормозит только на последовательностях байт типа "AAAAAA", то можно ускорить поиск по особому. Вот тут немного затронут этот вопрос: http://www.zxpress.ru/article.php?id=8569.

Eugene85

12.02.2015, 19:52

посмотри на MMC

Не представляю, как он может помочь. Как я понял, оно позволяет найти одну или несколько лучших совпадений, а мне нужно перебрать ВСЕ совпадения.

Если тормозит только на последовательностях байт типа "AAAAAA"
Да нет, как я уже сказал, в моей реализации скорость не зависит от характера данных. Вот mhmt, например, подвисает на таких.

Shadow Maker

20.02.2015, 14:50

А можно реализовать еще и идентичный hrust2.1? Чтобы получались одинаковые с hrust2.1 файлы.

Eugene85

20.02.2015, 20:55

Shadow Maker,
теоретически, конечно, можно, но я это делать не хочу, т.к. не вижу смысла. Простите, а зачем оно вам? Любопытно просто...

Shadow Maker

20.02.2015, 21:40

Для идентичности сборки всяких старых проектов :) Чтобы компилялось красиво.

Eugene85

23.02.2015, 11:58

Shadow Maker,
Сделай мне снапшот (.sna), я прикручу к нему эмулятор z80 и оформлю всё это в exe'шник :) Задача будет решена

Alexandr Medvedev

23.02.2015, 14:46

я прикручу к нему эмулятор z80 и оформлю всё это в exe'шник :) Задача будет решенаУже давно прекрутили. http://zx-pk.ru/showpost.php?p=88926&postcount=7

Eugene85

04.03.2015, 15:27

Сделал оптимальный компрессор для формата Hrust 1. Жмёт чуть лучше, чем mhmt (в среднем на 0.4%).

drbars

07.03.2015, 06:02

Eugene85, можно ли сделать оптимальный упаковщик для формата mlz ?

Eugene85

07.03.2015, 17:39

drbars,
в mhmt и так реализовано оптимальное сжатие для MegaLZ и Hrum; а для Hrust1 - почти оптимальное.

Hrumer

10.03.2015, 08:09

Eugene85, WinXP. При запуске /Win32/oh1c.exe выдается сообщение: oh1c.exe не является приложением Win32.
Под gcc не компилится. А где бы мне взять visual studio? Кто подскажет?

Vitamin

10.03.2015, 09:57

Надо линковать с флагами

/SUBSYSTEM:console,5.01

Для 64 битной версии надо 5.02 ставить.

Eugene85

11.03.2015, 15:57

WinXP. При запуске /Win32/oh1c.exe выдается сообщение: oh1c.exe не является приложением Win32.

Да, действительно, не доглядел настройки проекта. Прилагаю исправленные.

А где бы мне взять visual studio?

Такую, чтобы по WinXP работала? Это надо версию 2010. Express версию можно взять здесь (https://www.visualstudio.com/downloads/download-visual-studio-vs#d-2010-express).

Sayman

24.03.2015, 20:26

извините если не в тему, я в пакерах совсем ни в зуб ногой. вопрос у меня есть: есть пакованный файл, точнее два. один пожат megalz версией 4.89 и весит 33.5кб. второй пожат hrust 1.3 и весит 35.3кб. оба файла при всём моём желании не влезают разом в область tpa или какой ещё буфер. грузить нужно и распаковывать только частями. если я верно понял. оба пакера (депакера) не любят когда данные фрагментированы. что с этим можно поделать? может есть версия, где можно фрагментировать, бить на куски или ещё какой-то пакер/депакер с этой возможностью?

Hrumer

26.03.2015, 12:34

Sayman, megalz - лучше паковать не на zx, а с помощью mhmt от LVD. + насколько слышал, LVD сделал депакер для megalz с буфером кольцевым(это экономит объем буфера). Это то, что есть и можно использовать. Сам депакер я не видел. Интересно бы посмотреть. Если формат хруста1 хочешь, то лучше пакуй oh1c_20150310.zip - чуть выше был. Я его тестил, он отлично справился с тестовыми файлами. В отличие от mhmt (в режиме хруст1), он сохраняет пакованный файл с заголовком хруста1.

Lethargeek

18.05.2015, 19:36

Погодите чуток, приаттачу депакер и выложу завтра-послезавтра.

По картинке с мотоциклами такая ситуация:

LC5.2 на ZX: 4254
Новый LC5.2.1: 4156

После Screen Optimizer:

LC5.2 на ZX: 4152 (4143, если оптимизацию несколько раз применить)
Новый LC5.2.1: 4050 (4042, если оптимизацию несколько раз применить)
это цифры уже все с пришитым депакером?
и рекорд для пакеров спекографики?
а то я прикинул тут один способ...
получается примерно 3500 байт :cool:

Hrumer

20.05.2015, 08:26

это цифры уже все с пришитым депакером?
и рекорд для пакеров спекографики?
а то я прикинул тут один способ...
получается примерно 3500 байт :cool:

Без депакера и без заголовка. Депакер релоцируемый ~150 байт.
Вроде как рекорд для депакеров, не использующих буфер.

Давай угадаю способ: перекодируем по столбцам в третях экрана, далее самый простой RLE, потом Exomizer2? Или другой? Вообще, для именно заставок, когда есть место для буфера, надо бы более крутой пакер сделать. Будешь делать?

Lethargeek

20.05.2015, 21:53

Давай угадаю способ: перекодируем по столбцам в третях экрана, далее самый простой RLE, потом Exomizer2?
Не. Принцип сам довольно тупой, никакого поиска даже нет (хотя можно при желании и добавить) - паковать не байты, а квадраты пиксельные префиксным кодом, начиная с минимального 2x2, потом группы из 4 соседних, дальше получается знакоместо (если очень много пустого места - можно укрупнять дальше). Важна хитрость - упаковка не исходного знакоместа, а его ксорки со сдвигом на пиксельную строку или столбец, что для большинства "нормальных" картинок очень сильно увеличит кол-во пустот и перекосит вероятности вхождений непустых чанков. Недостаток - плохо пакуются текстуры, если их особо не обрабатывать (но пока я этим не занимался). Атрибуты жмутся по своим правилам, со сравнением с предыдущим по строке или по столбцу (что переключается на ходу).

Или другой? Вообще, для именно заставок,
Вообще метод годен для любого прямоугольника с размерами, кратными максимальной группе.
Можно из кусочков экран составить, хранить так крупные шрифты, графику для неактивных уровней в играх...

когда есть место для буфера, надо бы более крутой пакер сделать. Будешь делать?
Пока пакер запланирован был только для песюка, но и до него еще далеко.
Я сейчас лишь на этапе экспериментов, только накропал на сях программку считать размеры.
Будет время - буду заниматься по настроению. Может, здесь еще идей каких-то подкинут...

troosh

21.05.2015, 13:58

Будет время - буду заниматься по настроению. Может, здесь еще идей каких-то подкинут...

В спецификациях методов сжатия PNG, JBIG2, JB2 и даже в JPEG-LS, WebP-lossless, PCIF/BCIF и прочих столько идей, аж глаза разбегаются...
Только проблема может быть в том, что распаковщик будет размером в пару десятков килобайт и отрабатывать одну картинку будет за пару минут.

Lethargeek

21.05.2015, 15:42

troosh, да понятно, что депакер попроще нужен
и совсем неочевидна ценность упомянутых алгоритмов
так, png и tiff хуже жмут нецветные контрольные скрины
у zx-картинок своя специфика

troosh

21.05.2015, 16:08

Речь про то, что для лучшего сжатия применяют различные обратимые фильтры. Да, для монохромных картинок переход в частотную область за счет DCT мало что даст, но повышение локальности в обработываемых данных вполне себе работает: на некоторых SCR файлов будет заметный прирост, если сжимать не в линейном порядке исходные данные, а вертикальными столбцами 8x64 пикселя или другими тайлами.

В этом плане в PNG понапридумывали много способов порядка обхода исходного изображения, плюс простейшие предсказатели, тот же XOR с предыдущим байтом.

Ну а в таких методах как JBIG2 там вообще доходит до того, что распознавание образов используют для раздельного кодирования объектов и различных заливок по патернам (шашечками).

Lethargeek

21.05.2015, 19:13

я так понял, jbig-и больше для текстов и достаточно больших разрешений
столбцы это очевидно и примитивно, ну, и png я делал из bmp, жми как хочешь
а вот поди ж ты... архиваторы обычные по столбцам получше, но недостаточно
хотя, может, это примитивный paint в png так хреново жмёт? вопрос залу:
подскажите простенький portable lossless конвертер с лучшей компрессией
сложный софт ставить и осваивать влом, да и места нет

creator

21.05.2015, 19:59

это примитивный paint в png так хреново жмёт?
Прикалываешься? Эта пакость в 32 бита сохраняет, вот и кажется что плохо жмёт, впрочем, вполне возможно что и сжатие не на полную катушку.

подскажите простенький portable lossless конвертер с лучшей компрессией
Да обычный XnView запусти и выбери в нём максимальную степень сжатия для сохранения в PNG.

P.S. PNG лучший!

Lethargeek

21.05.2015, 22:02

Прикалываешься? Эта пакость в 32 бита сохраняет, вот и кажется что плохо жмёт, впрочем, вполне возможно что и сжатие не на полную катушку.
с какой стати в 32 бита, раз на входе монохромная бмпшка?

Да обычный XnView запусти и выбери в нём максимальную степень сжатия для сохранения в PNG.
ну, давай...
SCR 6144 для LC
BMP 6206 для paint/xnview
и моей считалочки (Lgk)
6144 (по столбцам) для RAR

мотоциклы (еще мною обработанная слегка)
http://zx-pk.ru/showpost.php?p=748482&postcount=36
Paint PNG: 4328
XnView PNG: 4261
LC5.2.1: 3809
RAR: 3503
Lgk: 3269

сильно текстурированная картинка (необработанная)
http://zxart.ee/eng/graphics/authors/v/vassa/town/
Paint PNG: 4701
XnView PNG: 4625
LC5.2.1: 4517
RAR: 4140
Lgk: 3919

P.S. PNG лучший!
для ZX, выходит, не лучший :p

troosh

21.05.2015, 22:40

Ещё можно прогнать PNG-шки через http://optipng.sourceforge.net (с -o7)
Тут: http://optipng.sourceforge.net/pngtech/optipng.html как он работает и ссылки на аналоги.

Lethargeek

21.05.2015, 23:26

optipng (из bmp, из уже готового png результат почему-то хуже)
мотоциклы: 3877
город: 4577

всё еще слабей чем LC

creator

21.05.2015, 23:40

с какой стати в 32 бита, раз на входе монохромная бмпшка?
Я тупо открыл 16-цветную финальную картинку Barbarian.png и сохранил. Она 32 бита оказалась. :) Затем пересохранил её в XnView — она стала 24 бита (цветность специально не уменьшал). Итого:
4 бита — 4661
32 бита — 9893
24 бита — 7079
Сейчас открыл в Paint ч/б Clive.png и сохранил. Она снова 32 бита стала. Если ручками в свойствах Paint выбрать ч/б, то ч/б и сохранит со вполне неплохим результатом:
1 бит оригинал — 3122
1 бит Paint — 3183
32 бита — 8700
24 бита — 6059

для ZX, выходит, не лучший :p
Согласен. :)

Lethargeek

22.05.2015, 00:59

Если ручками в свойствах Paint выбрать ч/б, то ч/б и сохранит со вполне неплохим результатом
у меня если такое проделать, то размер увеличится по сравнению с цветным png
причём созданные раньше именно моим пайнтом - увеличиваются ровно на 21 байт))

2636 = Clive LC5.2.1
2425 ~ Clive Lgk

troosh

22.05.2015, 14:48

Выложу, пожалуй, результаты сжатия в JBIG2. Готовые бинарники под linux взял тут: http://bfo.com/products/pdf/jbig2/ (это не самая последняя версия упаковщика). Привожу два варианта по jbig2: без опций и с опциями "-s -t 0.9", - в первом случае размер меньше, т.к. упаковщик допускает больше потерь при сжатии.

Хоть стандарт и допускает использование кодов Хаффмана вместо арифметического кодирования (распаковщики это поддерживают, как, например, этот на Javascript: https://github.com/igstan/jbig2.js), но заставить используемый кодировщик использовать кодирование Хаффмана я не могу.

Картинки для тестов брал в этой теме (пришлось некоторые масштабировать до оригинального размера), и ещё некоторые взял из инета (192x256, без атрибутов). Цветную картинку 6339760_.png сжало в черный квадрат, поэтому размеров не привожу.

jbig2 jbig2/s optipng
3350 3485 4002 6124201_.png (мотоциклы оригинал?)
596 623 689 6315259_.png (скриншот текстового меню)
3177 3320 3957 6317232_.png (мотоциклы оптимизированные?)
- - 6019 6339760_.png (мотоциклы в цвете)
2005 2384 4659 Barbarian.png (хоть и в цвете, но не малевич)
2283 2505 3116 Clive.png
1667 1754 2510 Moran-Kinder_Tripman.png
4645 4948 4977 Moran-Throughme.png
1392 1488 2041 RoboNIX-Dangerous_Temptation.png
2056 2372 2904 Surfin'Bird-New_Old_Frontier.png

P.S. PNG хорош тем, что он универсальный, быстрый и относительно простой, пиксель там может быть от 1 бита до 3*16, поддерживается альфа канал. Используемый метод сжатия zlib(deflate) стандартный, без заморочек на то, что файлы будут малого размера ~6k. Отсюда и проигрывает сильно заточенным под специфику SCR изображений.

Lethargeek

22.05.2015, 15:38

Привожу два варианта по jbig2: без опций и с опциями "-s -t 0.9", - в первом случае размер меньше, т.к. упаковщик допускает больше потерь при сжатии.
я не понял, так потери для всех случаев возможны, без опций тоже?
вижу разницу 6317232_.png.s.pbm и 6317232_.png.s_t09.pbm (тройка сдвинута)
но у 6317232_.png._.pbm с оригиналом видимых расхождений нет :confused_std:

Barbarian.png (хоть и в цвете, но не малевич)
не, так обесцвечивать не годится
нужно из эмуля выгрузить бинарь без атрибутов
потом после резета в 48k бейсик загрузить обратно
потом сохранить текущий экран в картинку
и потом уже в редакторе инвертировать

troosh

22.05.2015, 16:04

По стандарту можно как lossless, так и lossy (это от кодека зависит, а не особенность математики). Как я понимаю, это открытый референсный кодек через параметр -t позволяет регулировать степень потерь. Если бы можно было задать "-t 1.0", то наверное это бы означало без потерь, но вот он таки ругается, если попытать задать более 0.9. Кроме того, может это просто ошибка в программе.

Этот стандарт только для монохромных изображений (факсов и сканов текстов без полутонов). Там они допускают, что можно пожертвовать какой-нибудь пылинкой, ради лучшего сжатия. То, что он обесцветил сам меня это сильно удивило.

Живой спектрум не включал лет 20, да и до эмулятора пока не созрел. Мне проще обрезать последние 768 байт атрибутов у SCR и конвертировать сырые данные в какой-то подходящий формат. А ещё проще, что я и сделал, сразу же поискать готовые файлы в нужном размере и глубине цвета для этого, в общем-то, пока чисто теоретического сравнения форматов (и понимания, где пределы дозволенного энтропией).

Lethargeek

22.05.2015, 18:06

Схему оптимального (в рамках замысла) депакера вижу так: после распаковки знакоместа по чанкам его ксорить с любым блоком из уже отображённых с точностью до пикселя в общем случае (в правильном порядке попиксельно при частичном наложении на себя). Соответственно, оптимальный пакер ищет самую выгодную ксорку по уже запакованному участку. Но для спектрума получится слишком сложно, ссылки занимать будут много места, да и точность редко нужна такая. Потому планирую ограничиться ксорками со сдвигом на 1-2 пикселя по осям и на целое кол-во знакомест. Также выбор каждой новой ксорки в общем случае требует пересчета хаффмановского кода, а при ограниченном выборе - нескольких наборов, что сложнее (и для снижения общего размера, а тем более с приклеенным депакером - не всегда лучше) подгонки под универсальный префиксный код, да и разница для типичной спектрумовской графики небольшая.

Titus

22.05.2015, 18:57

Выложу, пожалуй, результаты сжатия в JBIG2.
Картинки предварительно преобразовывал по столбцам?

troosh

22.05.2015, 19:14

Нет, просто подсунул .png файлы компресору jbig2, он там уже сам как-то - я не вникал. В zip архиве доступны оригинальные файлы, что я использовал.

Lethargeek

23.05.2015, 00:25

прогнал новые картинки через считалку

2239 ~ испорченный Barbarian
1883 ~ Moran-Kinder_Tripman
4513 ~ Moran-Throughme
1445 ~ RoboNIX-Dangerous_Temptation
2253 ~ Surfin'Bird-New_Old_Frontier
750 -- менюшка))

видно, что все резервы для простых картинок еще не выбраны
нету групп больше одного знакоместа (запланировано вплоть до 8x8)
не "пакуется" служебная информация (лишних байт несколько десятков)
что опять-таки относительно заметней на картинках попроще
текст вообще ссылками на ксорки должен кодироваться

Lethargeek

27.05.2015, 12:36

опыты потихоньку продолжаются, а тем временем хочу задать вопрос нашим игроделам,
демомейкерам и езинщикам: чем (или как) вы жали графику в играх/демах/дискмагах?
и не только задники или заставки, но и динамику (например, шрифты бегущих строк);
пакеры универсальные (мб с подгонкой под них картинок) или самодельные под задачу?
думаю, будет интересно не только мне

Titus

27.05.2015, 12:49

опыты потихоньку продолжаются, а тем временем хочу задать вопрос нашим игроделам,
демомейкерам и езинщикам: чем (или как) вы жали графику в играх/демах/дискмагах?

Я жал своим собственным пакером, а до 95 года ASCLZSS и ZYX.

jerri

27.05.2015, 14:11

Shadow Maker

27.05.2015, 17:21

Я жал графику каким-то LZ от Медноногова (jerri вроде его и посоветовал).

jerri

27.05.2015, 18:36

Медноногов переписывал ASCLZPACK на пц

Lethargeek

28.05.2015, 19:38

жал своим собственным пакером

Переписанный
а в что не устраивало в чужих?
скорость распаковки, размер, удобство?
что конкретно жали - скрины, фрагменты?
моар подробностей пжл :v2_dizzy_write:

Titus

28.05.2015, 21:01

а в что не устраивало в чужих?
скорость распаковки, размер, удобство?
что конкретно жали - скрины, фрагменты?
моар подробностей пжл :v2_dizzy_write:

Меня интересовала сверхбыстрая распаковка, с качеством не хуже, чем у пакера Сендетского, а то и лучше. Я это получил, и использовал в Great Codemasters Collection и более поздних продуктах. Паковал все - код, графику (предварительно сконвертированную по столбцам, скрины).

jerri

28.05.2015, 23:07

а в что не устраивало в чужих?
скорость распаковки, размер, удобство?
что конкретно жали - скрины, фрагменты?
моар подробностей пжл :v2_dizzy_write:

Hrum 3.5 как и Hrust 1.x использует стек для досткпа к данным
Hrust 2.x использует более эффективную систему хранения.

я просто перенес способ хранения данных из Hrust2 в Hrum

жал то что делал

Alex Rider

29.05.2015, 00:35

Меня интересовала сверхбыстрая распаковка
Подтверждаю: пакер, а особенно депакер Титуса творит чудеса.

Titus

29.05.2015, 00:45

Подтверждаю: пакер, а особенно депакер Титуса творит чудеса.

По скорости распаковки готов принять комплимент) От LDIR до 2 LDIR) А в упаковке какое чудо?

Alex Rider

29.05.2015, 01:16

А в упаковке какое чудо?
Погорячился по поводу качества распаковщика. Ему б PC-шный пакер... Но у меня пока нет задач чтобы его написать.

Titus

29.05.2015, 01:20

Погорячился по поводу качества распаковщика. Ему б PC-шный пакер... Но у меня пока нет задач чтобы его написать.

Упаковщика)

Да, на ПЦ можно запаковать лучше, и проверить заодно. И файлы большего размера можно паковать.

Alex Rider

29.05.2015, 01:47

Упаковщика)
Распаковщика. Это имнно он обеспечивает на ZX 1-2 x ldir.

goodboy

26.12.2015, 12:19

вспомнил про ещё один упаковщик данных из Сербии - 1996г.
(работает с лентой, управление 8,9,0)

http://savepic.ru/8186031.png

уверенно обходит LZ от ASC, но проигрывает Hrust2.x
(работает с лентой)

Eugene85

17.02.2016, 19:27

Прошу прощения, если боян, но: почему Хаффман? Почему не арифметическое кодирование?

А есть быстрый вариант без умножений-делений?

А это точно проблема? Кто-нибудь пробовал на практике?

Точно. Я пробовал. ~4кб/с скорость распаковки.
Ок.
А упрощённый вариант - без делений (заменяется сдвигами вправо) - пробовали?

Vitamin

18.02.2016, 00:31

А упрощённый вариант - без делений (заменяется сдвигами вправо) - пробовали?
Это какой? Не смущает, что сдвигами вправо заменяется только деление на степени двойки?

Eugene85

19.02.2016, 11:51

Да, на это упрощение идут сознательно, чтобы избавиться от деления, которое на PC является тяжёлой операцией, в отличие от умножения. При этом, конечно, сужение интервала кодера происходит отчасти в холостую, т.е. сжатие несколько ухудшается, но, видимо, размен стОящий, т.к. большинство компрессоров на PC используют именно такой вариант.

Hrumer

19.02.2016, 12:02

Вот, кстати, тут есть инфа: http://compression.ru/sh http://compression.ru/ds/

Vitamin

19.02.2016, 12:48

Lethargeek

19.02.2016, 18:33

А можно пример реализации арифметического кодирования, где надо делить только на степени двойки?
да, и с матобоснованием, что результат "несколько ухудшенного" АК всё еще останется лучше хаффмана

Hrumer

19.02.2016, 18:59

Чур не ругаться:) выше ссылки на реализации 1999-2003г. Фидо, рукомпресс.

Eugene85

21.02.2016, 12:41

Из того, что нашлось под рукой - исходники LZMA. Там деления нет, ни в компрессоре, ни в декомпрессоре.

Vitamin

22.02.2016, 21:35

Из того, что нашлось под рукой - исходники LZMA. Там деления нет, ни в компрессоре, ни в декомпрессоре.
Это который 7-zip? И в каком месте там арифметическое кодирование?

Eugene85

23.02.2016, 11:30

Вам конкретно номер строки назвать? Или намекаете, что range coding и арифметическое кодирование - это не одно и то же?

Vitamin

23.02.2016, 11:58

Вам конкретно номер строки назвать? Или намекаете, что range coding и арифметическое кодирование - это не одно и то же?
Если не затруднит. Лично я во внутренностях lzma не копался, только юзал через API.

Eugene85

29.02.2016, 23:28

Я покопал подробнее, оказывается range coder в LZMA кодирует только однобитные значения. Т.е. упрощён донельзя. А уже на его базе реализуется всё остальное. Например, кодирование произвольного алфавита делается так: таблица символов представляется деревом, спускаемся по дереву, кодируя на каждом шаге направление спуска влево или вправо.

Интересно, что байты-литералы тоже кодируются побитно: на каждый бит своя модель (вероятность), зависящая от предыдущих бит.

Неплохое описание нашлось в английской википедии (https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algorithm).

Если всё ещё интересны исходники, берём LZMA SDK (http://www.7-zip.org/sdk.html). Ядро кодера находится в файле \C\LzmaEnc.c, функции RangeEnc_*, LitEnc_*, RcTree_*. Декодер - в файле C\LzmaDec.c, первые 67 строк.