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

[Shaos]

Самая большая - это не оптимальный алгоритм. Оптимальный учитывает и способ кодирования с точностью до бита. Это реально реализовано в 7zip и MegaLZ.

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

[Shaos]

У меня всегда выкусывается самая большая из оставшихся повторяющихся последовательностей - в этом смысле алгоритм "оптимален", однако представление информации, когда команда имеет в виде префикса целый байт #FF, не совсем годится для кодирования коротких последовательностей. Сейчас рассматриваю варианты "постобработки" без скатывания в побитовую алхимию (Хаффман и т.д.) - например после LZ77 (со "скользящим" окном) можно применить табличный LZ на оставшиеся непожатые данные, ищущий и кодирующий часто повторяющиеся "триады" (тройки байтов) одним байтом (для подстановки выбираются не встречающиеся или редко встречающиеся байты). Сейчас у меня задача любой SNA упаковывать в 32К (пока из тех что я пробую не уталкивается в 32К только файл tomahawk.sna).

Предварительные прикидки показывают, что tomahawk.sna может после такой "постобработки" уменьшиться с 35.6К до примерно 31К, т.е. после этого он сможет влезть в 32К! Напомню, что MegaLZ сжимает его лучше - 29К, однако если пройтись по моим данным Хаффманом, то будет ещё компактнее

P.S. Альтернативный вариант постобработки - прикладывать Хаффмана не только к отдельным байтам, но и двойкам и тройкам байт, тогда создание отдельного словаря "триад" не понадобится...

[Shaos]

Подсмотрел в LZMA хитрость интересную - один из вариантов записи ссылки использует предыдущее значение смещения - это полезно например если повторяется строка, в середине которой отличается один символ, тогда первая половина идёт со смещением, потом отдельный байт (новый символ), потом оставшаяся строка со смещением, которое использовалось ранее. Решил посмотреть может ли дать какую бы то ни было выгоду использование этого момента (0), а также -1,-2,-3,+1,+2,+3 от предыдущего смещения. Вот какая статистика по tomahawk.sna:
1st block: 0:72 (58 with small size) +1:6 +2:4 +3:4 -3:6 -2:5 -1:6
2nd block: 0:107 (97 with small size) +1:6 +2:8 +3:3 -3:4 -2:7 -1:5
3rd block: 0:89 (68 with small size) +1:5 +2:5 +3:4 -3:2 -2:4 -1:5
По сути мелочь - полкило максимум это может дать, т.е. остаёмся в ранее оговоренном русле...

[Shaos]

Экспериментирую ещё с одним способом представления - когда работаем на уровне битов, но попроще:
- если из стрима идёт один бит 0, то со следующими 7 битами он формирует значение байта от #00 до #7F;
- если из стрима идёт два бита 1 и 0, то следующие 7 битов задают значение байта от #80 до #FF;
- если из стрима идёт два бита 1 и 1, то это является командой (аналог #FF), за которой может идти от 2 до 4 байтов, задающих смещение и размер (чуть ранее описано каким образом задающих).
Пока получается несколько компактнее, чем оригинальный "байтовый" SHAFF - пробую прогнать все экспериментальные SNA-файлы (назвать это SHAFFv1c?).

P.S. Размер на самом деле в битовом потоке можно совсем гибко сделать (т.к. меньшие размеры чаще встречаются) - от 2 до 26 битов:

Code: Select all

0x - задаёт размеры 2 и 3
10xx - задаёт размеры 4, 5, 6, 7
110xxx - размеры 8...15
1110xxxx - 16...31
11110xxxxx - 32...63
111110xxxxxx - 64...127
1111110xxxxxxx - 128...254
11111110xxxxxxxx - 255...511
111111110xxxxxxxxx - 512...1023
1111111110xxxxxxxxxx - 1024...2047
11111111110xxxxxxxxxxx - 2048...4095
111111111110xxxxxxxxxxxx - 4096...8191
1111111111110xxxxxxxxxxxxx - 8192...16383

[b2m]

Экспериментирую ещё с одним способом представления - когда работаем на уровне битов, но попроще:
- если из стрима идёт один бит 0, то со следующими 7 битами он формирует значение байта от #00 до #7F;
- если из стрима идёт два бита 1 и 0, то следующие 7 битов задают значение байта от #80 до #FF;
- если из стрима идёт два бита 1 и 1, то это является командой (аналог #FF), за которой может идти от 2 до 4 байтов, задающих смещение и размер

Если не учитывать команды, а байты равномерно распределены между интервалами от #00 до #7F и от #80 до #FF, то на обычные байты у тебя будет примерно полтора бита лишних.

Тогда как другие архиваторы используют такой метод: сначала идёт байт, указывающий, чем будут следующие 8 элементов (по биту на каждый, 0 - байт, 1 - команда), а затем сами байты/команды.

При таком методе лишним будет лишь один бит на байт. Да и скорость распаковки на 8-ми битных компах больше, т.к. не надо возиться с битовыми потоками данных.

[Shaos]

почему полтора бита? полбита

[b2m]

Согласен. Проклятая инерционность мышления

[Shaos]

На самом деле вариант с байтом, задающим типы следующих восьми единиц компрессии, кажется интересным - его тоже можно прикинуть, пользуясь теми данными, что у меня уже имеются. Думаю он будет лучше чем байтовопоточный SHAFF, но хуже чем битовопоточный SHAFF (соответственно сложность декодера тоже будет промежуточная). Пока размещаю результаты по битовому потоку на предыдущей странице под наименованием SHAFFv1c, пока он побеждает всех, кроме XZ (даже MegaLZ жмёт хуже)!

P.S. В расчёты закралась ошибка - в реальности побитовое представление даёт несколько худшие результаты (хуже чем Hrust, но лучше чем MegaLZ) - поправляю данные на предыдущей странице...

P.P.S. Результаты поправил - заодно добавил короткую команду использование смещения -1 и предыдущего смещения

[alone]

Подсмотрел в LZMA хитрость интересную - один из вариантов записи ссылки использует предыдущее значение смещения

В ZXRar практически не дало выигрыша.

[Shaos]

Подсмотрел в LZMA хитрость интересную - один из вариантов записи ссылки использует предыдущее значение смещения

В ZXRar практически не дало выигрыша.

Ну мне вроде чего-то даёт:

Code: Select all

zx48k1.sna           49179
zx48k1.zip             718
zx48k1.sna.gz          594
zx48k1.sna.bz2         535
zx48k1.sna.7z          632
zx48k1.sna.mlz        1023
zx48k1.sna.hrm         930
zx48k1.sna.hst         502
zx48k1.sna.xz          576
SHAFFv0*               590
SHAFFv1*               456
SHAFFv1-128            459
SHAFFv1-noshorts       467
SHAFFv1-noshorts-128   471
SHAFFv1d               455
SHAFFv1e               450
SHAFFv1f               452
SHAFFv1g               448
SHAFFv1h               452

chess16k.sna         49179
chess16k.zip          7481
chess16k.sna.gz       7378
chess16k.sna.bz2      7921
chess16k.sna.7z       6947
chess16k.sna.mlz      7752
chess16k.sna.hrm      7702
chess16k.sna.hst      7066
chess16k.sna.xz       6860
SHAFFv0*              7666
SHAFFv1*              7199
SHAFFv1-128           7237
SHAFFv1-noshorts      7252
SHAFFv1-noshorts-128  7295
SHAFFv1d              7182
SHAFFv1e              7163
SHAFFv1f              7162
SHAFFv1g              7156
SHAFFv1h              7157

jswilly16k.sna       49179
jswilly16k.zip        6708
jswilly16k.sna.gz     6570
jswilly16k.sna.bz2    6901
jswilly16k.sna.7z     6014
jswilly16k.sna.mlz    6826
jswilly16k.sna.hrm    6767
jswilly16k.sna.hst    6230
jswilly16k.sna.xz     5956
SHAFFv0*              7792
SHAFFv1*              6528
SHAFFv1-128           6596
SHAFFv1-noshorts      6597
SHAFFv1-noshorts-128  6667
SHAFFv1d              6522
SHAFFv1e              6500
SHAFFv1f              6472
SHAFFv1g              6453
SHAFFv1h              6462

Выше дана инфа по двум играм для ZX-16K (jswilly16k.sna и chess16k.sna) и снапшоте памяти спектрума (zx48k1.sna) с введённой одностроковой программкой на бейсике (10 PRINT "Hello"). SHAFFv0 - байтовый поток. SHAFFv1 - битовый поток где суффикс -128 означает, что все смещения дальше -128 представляются двумя байтами, а суффикс noshorts означает отсутствие спецкодов, задающих предыдущее смещение, смещение которое было до предыдущего и смещение -1. Как видим оно даёт выгоду порядка 60-70 байтов для таких маленьких игр...

P.S. Использованные версии архиваторов:
zip - Copyright (c) 1990-2008 Info-ZIP - Zip 3.0 (July 5th 2008)
7-Zip (A) [64] 9.20 Copyright (c) 1999-2010 Igor Pavlov 2010-11-18

P.P.S. Где бы ещё 300 байтов взять? Тогда я смогу победить Hrust

P.P.P.S. 17 октября добавил сюда результаты по SHAFFv1d (см. ниже)

P.P.P.P.S. 20 октября добавил сюда результаты по SHAFFv1e (см. ниже)

P.P.P.P.P.S. 21 октября добавил сюда результаты по SHAFFv1f и чуть позже - SHAFFv1g (см. ниже)

P.P.P.P.P.P.S. 22 октября добавляю результаты по SHAFFv1h у которого статистически подобранно кодирующее дерево для дистанций...

[Shaos]

Подсмотрел в LZMA хитрость интересную - один из вариантов записи ссылки использует предыдущее значение смещения

В ZXRar практически не дало выигрыша.

Ну мне вроде чего-то даёт

Ещё один трюк - короткая команда повторения последнего обработанного байта - даёт какую-то мелочь, но приятно

P.S. Вот последний вариант побитного представления (прототип SHAFFv1d), который показывает неплохие результаты и наверное именно его я и объявлю окончательной версией 1:

Code: Select all

SHAFF1 data format:

0+7bits (byte #00...#7F)
10+7bits (byte #80...#FF)
110+4bits+size* (0 for last byte, 1 for -1, 2 for -2 etc., but 15 means last distance greater or equal to 15)
1110+8bits+size (distance -15...-270)
1111+14bits+size* (distance up to -16383)

* no size after:
1100000 - use last byte (no size required)
111100000000000000 - end of block (instead of distance -16384)

size is a sequence of 2 - 26 bits:
0x - for 2 and 3
10xx - for 4, 5, 6, 7
110xxx - for 8...15
1110xxxx - for 16...31
11110xxxxx - for 32...63
111110xxxxxx - for 64...127
1111110xxxxxxx - for 128...254
11111110xxxxxxxx - for 255...511
111111110xxxxxxxxx - for 512...1023
1111111110xxxxxxxxxx - for 1024...2047
11111111110xxxxxxxxxxx - for 2048...4095
111111111110xxxxxxxxxxxx - for 4096...8191
1111111111110xxxxxxxxxxxxx - for 8192...16383 

P.P.S. А вот аналогичное описание версии 0 (от более раннего отличает особое отношение к короткой записи дистанции -191, которое теперь означает последнюю использованную дистанцию дальше или равную 191):

Code: Select all

SHAFF0 data format:

XX - any byte other than #FF is data byte 
#FF #00 - one byte #FF
#FF 0xxxxxxx size (distance -1...-127)
#FF 10xxxxxx size (distance -128...-190, and -191 means last distance greater or equal to 191)
#FF 11xxxxxx xxxxxxxx size* (distance up to -16383)

* no size after:
#FF #C0 #00 - end of block (instead of distance -16384)

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

[Shaos]

Вот формат прототипа SHAFFv1e:

Code: Select all

SHAFF1 data format:

0 xxxxxxx (byte #00...#7F)
10 xxxxxxx (byte #80...#FF)
1100 xx size* (00 for last byte, 01 and 10 for two unequal last distances longer than -1, 11 for distance -1)
1101 xxxx size (distance -2...-17)
1110 xxxxxxxx size (distance -18...-273)
1111 xxxxxxxxxxxxxx size* (distance up to -16383)

* no size after:
110000 - use last byte (no size required)
111100000000000000 - end of block (instead of distance -16384)

size is a sequence of 2...26 bits:
0x - for 2 and 3
10xx - for 4, 5, 6, 7
110xxx - for 8...15
1110xxxx - for 16...31
11110xxxxx - for 32...63
111110xxxxxx - for 64...127
1111110xxxxxxx - for 128...254
11111110xxxxxxxx - for 255...511
111111110xxxxxxxxx - for 512...1023
1111111110xxxxxxxxxx - for 1024...2047
11111111110xxxxxxxxxxx - for 2048...4095
111111111110xxxxxxxxxxxx - for 4096...8191
1111111111110xxxxxxxxxxxxx - for 8192...16383 

Хотел было его объявить финальным, но внезапно обнаружил ещё более компактное представление у которого дерево получается более сбалансированным (на примере одного 16К блока из tomahawk.sna)...

[Shaos]

Вот более сбалансированный формат SHAFFv1f:

Code: Select all

SHAFF1 data format:

0 xxxxxxx (byte #00...#7F)
10 xxxxxxx (byte #80...#FF)
1100 xx size* (00 for last byte, 01 and 10 for two unequal last distances longer than -1, 11 for distance -1)
1101 xxxxxx size (distance -2...-65)
1110 xxxxxxxxx size (distance -67...-577)
1111 xxxxxxxxxxxxxx size* (distance up to -16383)

* no size after:
110000 - use last byte (no size required)
111100000000000000 - end of block (instead of distance -16384)

size is a sequence of 2...26 bits:
0x - for 2 and 3
10xx - for 4, 5, 6, 7
110xxx - for 8...15
1110xxxx - for 16...31
11110xxxxx - for 32...63
111110xxxxxx - for 64...127
1111110xxxxxxx - for 128...254
11111110xxxxxxxx - for 255...511
111111110xxxxxxxxx - for 512...1023
1111111110xxxxxxxxxx - for 1024...2047
11111111110xxxxxxxxxxx - for 2048...4095
111111111110xxxxxxxxxxxx - for 4096...8191
1111111111110xxxxxxxxxxxxx - for 8192...16383 

[Shaos]

Вот ещё более сбалансированный формат SHAFFv1g (как минимум tomahawk.sna должен стать меньше):

Code: Select all

SHAFF1 data format:

0xxxxxxx (byte #00...#7F)
10xxxxxxx (byte #80...#FF)
1100xx size* (00 for last byte, 01 and 10 for two unequal last distances longer than -1, 11 for distance -1)
1101xxxxx (distance from -2 to -33)
11100xxxxxx (distance from -34 to -97)
111010xxxxxxxx (distance from -98 to -353)
111011xxxxxxxxxx (distance from -354 to -1377)
1111xxxxxxxxxxxxxx  size* (distance up to -16383)

* no size after:
110000 - use last byte (no size required)
111100000000000000 - end of block (instead of distance -16384)

size is a sequence of 2...26 bits:
0x - for 2 and 3
10xx - for 4, 5, 6, 7
110xxx - for 8...15
1110xxxx - for 16...31
11110xxxxx - for 32...63
111110xxxxxx - for 64...127
1111110xxxxxxx - for 128...254
11111110xxxxxxxx - for 255...511
111111110xxxxxxxxx - for 512...1023
1111111110xxxxxxxxxx - for 1024...2047
11111111110xxxxxxxxxxx - for 2048...4095
111111111110xxxxxxxxxxxx - for 4096...8191
1111111111110xxxxxxxxxxxxx - for 8192...16383 

[Shaos]

Написал программку, которая вычисляет по итогам сжатия оптимальное дерево для кодирования дистанций (правда с заморозкой размера первой и последней ветви - соответственно 2 и 14 бит):

Code: Select all

   1100xx (2)
   1101xx...xx (A)
   11100xx...xx (B)
   111010xx...xxxx (C)
   111011xxx...xxxxx (D)
   1111xxxxxxxxxxxxxx (14)

Вот какие результаты у меня получились:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 2-5-6-7-9-14
Min for 'chess16k.sna' is 2-5-7-7-8-14
Min for 'chess.sna' is 2-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 2-5-7-7-9-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Пожалуй выберу тогда 2-6-8-8-10-14:

Code: Select all

   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxxx (8)
   111010xxxxxxxx (8)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14)

Вот так будет выглядеть статистика tomahawk.sna:

6 8 8 10
k1=-2
k2=-66
k3=-322
k4=-578
k5=-1602
87950 bits (10993 bytes)
7182 bits for 1
24980 bits for 2
21528 bits for 3
7896 bits for 4
11568 bits for 5
14796 bits for 6

по сравнению с SHAFFv1g:

5 6 8 10
k1=-2
k2=-34
k3=-98
k4=-354
k5=-1378
88793 bits (11099 bytes)
7182 bits for 1
15588 bits for 2
12133 bits for 3
19740 bits for 4
17392 bits for 5
16758 bits for 6

разница - 106 байт...

P.S. Проверим к примеру exolon.sna, у которого другое оптимальное дерево:

5 7 7 9
k1=-2
k2=-34
k3=-162
k4=-290
k5=-802
77377 bits (9672 bytes)
6240 bits for 1
14589 bits for 2
14928 bits for 3
7852 bits for 4
13140 bits for 5
20628 bits for 6

для дерева 2-6-8-8-10-14 оценки будут такими:

6 8 8 10
k1=-2
k2=-66
k3=-322
k4=-578
k5=-1602
77471 bits (9683 bytes)
6240 bits for 1
21140 bits for 2
18993 bits for 3
8330 bits for 4
8080 bits for 5
14688 bits for 6

как видим потеряли только 11 байт - так что можно делать общее дерево 2-6-8-8-10-14, назвав его SHAFFv1h...