Недоархиватор SHAFF

[Shaos]

Два года уже прошло с момента написания последней версии архиватора - пора уже допилить уже...

[Shaos]

А теперь уже больше трех лет прошло...

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
11101xxxxxxxxxx (10) - от -322 до -1345
1111xxxxxxxxxxxxxx (14) - от -1346 до -16383

Можно потом пойти дальше - отдельно кодируемые байты пожать Хаффманом и назвать это SHAFFv2

P.S. Тогда до кучи и оптимальный выбор цепочек можно сделать...

[Shaos]

Чего-то замотался я и окончательную сжимающе-разжимающую версию так и не выкатил - там осталось буквально на вечер-два работы...

Создал прожэкт на GitHub - залью туда все версии одну за другой, чтобы можно было видеть диффы между ними по коду:

github.com/shaos/shaff

Ну и окончательную доводку кода буду уже туда выкладывать...

P.S. В июне 2018 года репа переехала на гитлаб: https://gitlab.com/shaos/shaff

[Shaos]

Тут пока исследовал разные алгоритмы для сжатия 8086/8088 кода для суперкартриджа с 8 играми для IBM PCjr, попробовал разные архиваторы (и старые, и новые, и ретро-демо-сценерские) - заодно и свой SHAFF для сравнения

Code: Select all

    147,456 JRCARTS7.IMG - оригинальный файл до сжатия
    130,281 JRCARTS8.IMG - простое сжатие, заменяющее последовательность из #HILO нулей на 00-00-00-LO-HI
    112,715 JRCARTS7.SHA - мой SHAFF v0 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    103,307 JRCARTS7.PP2 - RNC Pro Pack (method 2 без Хаффмана)
    101,009 JRCARTS7.ZX7
    100,180 JRCARTS7.IMG.hrm - Hrum
     99,974 JRCARTS7.IMG.mlz - MegaLZ
     98,077 JRCARTS7.SHA - мой SHAFF v1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
     98,006 JRCARTS7.LZH - LHA v2.13
     80,016 JRCARTS7.IMG.bz2 - bzip2
     79,098 JRCARTS7.LZ4
     72,959 JRCARTS7.PP1 - RNC Pro Pack (method 1 с Хаффманом)
     71,950 JRCARTS7.zip - ZIP from Debian
     71,925 JRCARTS7.ARJ - ARJ v2.41a
     71,865 JRCARTS7.AIN - Russian archiver from 90s
     71,855 JRCARTS7.ZIP - PKZIP v2.06
     71,808 JRCARTS7.IMG.gz - gzip
     70,041 JRCARTS7.HA - HA 0.98 (Harri Hirvola)
     67,437 JRCARTS7.IMG.hst - Hrust
     66,970 JRCARTS7.RAR - RAR v1
     65,765 JRCARTS7.RAR - RAR v5
     62,543 JRCARTS7.7z - 7-zip
     62,508 JRCARTS7.IMG.xz - LZMA2

Как видно побитовый SHAFF (v1) обогнал Hrum и MegaLZ (но отстал от Hrust, а также от LZ4 и RNC-PP1, относительно простые декодеры которых существуют для нескольких ретро-платформ) - с Хаффманом (будущий SHAFF v2) должно быть получше...

P.S. Исходники архиватора HA ("an arithmetic/Markov coder" от Harri Hirvola) оказывается доступны под GPLv2 с 1995 года http://fileformats.archiveteam.org/wiki/HA

P.P.S. Прикинул, что если пожму литералы Хоффманом (SHAFF2), то смогу опуститься до 87K - т.е. обогнать LHA и подобраться вплотную к bzip2, но похоже не смогу догнать LZ4 и RNC Pro Pack (method 1) - их сможет попытаться сделать только SHAFF3

[Shaos]

https://github.com/shaos/shaff

Ну и окончательную доводку кода буду уже туда выкладывать...

Выложил (пока в разобранном состоянии) и заодно поподробнее расписал формат SHAFFv1h:

Code: Select all

SHAFF header:

Bytes 0...5 - signature and version ("SHAFF0" or "SHAFF1")
Bytes 6,7 - offset to the 1st block of encoded data (big-endian)
Bytes 8,9 - number of 16K blocks (big-endian)
Bytes 10,11 - size of the last block (less or equal to 16384, also big-endian)
Then optional uncompressed auxilary data, for example in case of SNA-file:
Bytes 12...14 "SNA" - signature to identify SNA header
Bytes 15...41 - SNA 27-byte header itself


SHAFF0 data format:

XX - any byte other than #FF is a single data byte
#FF #00 - single byte #FF
#FF 0xxxxxxx LENGTH (distance -1...-127)
#FF 10xxxxxx LENGTH (distance -128...-190 and -191 means last distance longer or equal to -191)
#FF 11xxxxxx xxxxxxxx LENGTH (directly encoded distance from -191 to -16383)
special case without LENGTH:
#FF #C0 #00 - end of block (instead of distance -16384)

LENGTH is 1 or 2 bytes:
1xxxxxxx - for 4...131
01xxxxxx - for 132..195
00xxxxxx xxxxxxxx - for up to 16383


SHAFF1 data format:

0xxxxxxx - single byte #00...#7F
10xxxxxxx - single byte #80...#FF
110000 - repeat last single byte (no LENGTH after that)
110001 LENGTH - repeat last distance longer than -1 and not equal to previous
110010 LENGTH - repeat previous last distance longer than -1
110011 LENGTH - distance -1 (that basically means copy of the last byte LENGTH times)
1101xxxxxx LENGTH - distance from -2 (000000) to -65 (111111)
11100xxxxxxxx LENGTH - distance from -66 (00000000) to -321 (11111111)
11101xxxxxxxxxx LENGTH - distance from -322 (0000000000) to -1345 (1111111111)
1111xxxxxxxxxxxxxx LENGTH - distance up to -16383 (directly encoded with prefix 11)
special case without LENGTH:
111100000000000000 - end of block (after that last byte padded by zero bits)
and anything above 111111101010111110 is reserved!

LENGTH is a sequence of 2...26 bits that encode length of the copy:
0x - for 2 (encoded by 0) and 3 (encoded by 1)
10xx - for 4 (00), 5 (01), 6 (10), 7 (11)
110xxx - for 8...15 (000...111)
1110xxxx - for 16...31 (0000...1111)
11110xxxxx - for 32...63 (00000...11111)
111110xxxxxx - for 64...127 (000000...111111)
1111110xxxxxxx - for 128...254 (0000000...1111111)
11111110xxxxxxxx - for 255...511 (00000000...11111111)
111111110xxxxxxxxx - for 512...1023 (000000000...111111111)
1111111110xxxxxxxxxx - for 1024...2047 (0000000000...1111111111)
11111111110xxxxxxxxxxx - for 2048...4095 (00000000000...11111111111)
111111111110xxxxxxxxxxxx - for 4096...8191 (000000000000...111111111111)
1111111111110xxxxxxxxxxxxx - for 8192...16383 (0000000000000...1111111111111)

[Shaos]

У меня ещё есть много мест для оптимизации т.к. сжимает SHAFFv1h оооочень долго

Code: Select all

zx48.sna        2 min
zx48k1.sna      2 min
jswilly16k.sna 35 min
chess16k.sna   21 min
chess.sna      47 min
cybotron.sna   28 min
tomahawk.sna  158 min  
exolon.sna    141 min  
buzzsaw.sna    93 min
bozxle.sna    102 min

Замеры делались на Intel Core Duo 2008 года...

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

[Shaos]

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

Доделал до уровня, когда запаковывается файл в формате SHAFF0 (байтовый поток), но распаковщика пока нету - завтра напишу...

P.S. Пока сжимаю всякие файлы, с какими раньше игрался - пока вроде более-менее сходится, например zx48k1.sna (образ памяти с бейсик программкой из одной строки) сжался в 590 байт

[angry_troll]

zx48.sna 2 min
zx48k1.sna 2 min
jswilly16k.sna 35 min
chess16k.sna 21 min
chess.sna 47 min
cybotron.sna 28 min
tomahawk.sna 158 min
exolon.sna 141 min
buzzsaw.sna 93 min
bozxle.sna 102 min

НАСТОЛЬКО медленно сделать сжатие -- это надо уметь!


Интересно, если взять файл и инвертировать все 7ые биты всех байтов -- размер наверное изменится...

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

[Shaos]

Я старался

SHAFF0 - байтовый поток

SHAFF1 - битовый поток (без Хаффмана)

будет ещё SHAFF2 - битовый поток с Хаффманом для литералов...

[angry_troll]

Да я не об этом. Посмотри как-нибудь на досуге форматы того же megalzа или хруста. Там если нужно что-то кратное 8 битам -- оно сразу как байты выбирается из байтового потока, а если биты нужны -- они из битового, точнее из 8- или 16-битового сдвигателя, который по опустошению вновь засасывается из байтового потока.
Формы ссылок не меняются, меняется только их хранения в запакованном файле, а заодно ОЧЕНЬ ускоряется депак.

кстати, а у тебя сейчас оптимальное кодирование или нет?

[Shaos]

Получается что у MegaLZ команды всегда выровнены на границу байта? Это же ухудшает сжатие, нет? У меня только блоки выравниваются на границу байта (чтобы в перспективе можно было иметь аля произвольный доступ с шагом в 16К внутри архива ну и на многокоровых машинах можно параллельно и независимо блоки компрессировать - каждый блок всегда с начала байта начинается и добивается нулевыми битами в конце, чтобы добить до конца байта).

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

[angry_troll]

Омг... ты тогда, что ли, в сорец депакера загляни (есть сишный).

[angry_troll]

пока нету Хаффмана оно и так нормально

А как ты собрался делать полностью оптимальное кодирование с хафманом, интересно?
Как ты будешь при оценке ссылок учитывать, во что они пережмутся хафманом?

[Shaos]

Омг... ты тогда, что ли, в сорец депакера загляни (есть сишный).

а я чего-то сишного декодера не встречал, только Z80 - а вообще ведь mhmt тот же умеет декодить?
поглядел - ничо не понял, вроде читает пословно из какого-то wrk.indata[position++], но как оно превращается в биты то?
ведь судя по описанию формата мегалз именно с битами работает т.к. команды явно не кратной 8-битам длинной все...

пока нету Хаффмана оно и так нормально

А как ты собрался делать полностью оптимальное кодирование с хафманом, интересно?
Как ты будешь при оценке ссылок учитывать, во что они пережмутся хафманом?

ну будет с каким-то допуском оптимальное
хаффмана можно по ходу дела пересчитывать, в какой-то момент остановившись...

[angry_troll]

depack_getbyte() vs depack_getbits()
и далее сам цикл распаковки