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

[Shaos]

Итак с исправленным архиватором имеем (без Хаффмана):

zx48.sna - 0.5K

Code: Select all

Estimated compression: 2% (16384 -> 345)
Estimated compression: 0% (16384 -> 6)
Estimated compression: 1% (16384 -> 175)

chess.sna - 10.5K

Code: Select all

Estimated compression: 10% (16384 -> 1745)
Estimated compression: 51% (16384 -> 8508)
Estimated compression: 1% (16384 -> 227)

cybotron.sna - 6.1K

Code: Select all

Estimated compression: 35% (16384 -> 5861)
Estimated compression: 0% (16384 -> 25)
Estimated compression: 1% (16384 -> 206)

Результаты по другим [недо]архиваторам:

zx48.sna (49K):

Code: Select all

SHAFFv1b:
Actual compression: 2% (16384 -> 342)
Actual compression: 0% (16384 -> 8)
Actual compression: 1% (16384 -> 178)
Compressed file size: 570 bytes

SHAFFv1c:
Bitstream compression: 1% (16384 -> 281)
Bitstream compression: 0% (16384 -> 7)
Bitstream compression: 0% (16384 -> 138)
Bitwise compressed file size (v1): 438 bytes

SHAFFv1d:
Bit-stream compression: 1% (16384 -> 277)
Bit-stream compression: 0% (16384 -> 8)
Bit-stream compression: 0% (16384 -> 142)
SHAFF0 compressed file size: 561 bytes
SHAFF1 compressed file size: 439 bytes

SHAFFv1e:
Bit-stream compression: 1% (16384 -> 271)
Bit-stream compression: 0% (16384 -> 8)
Bit-stream compression: 0% (16384 -> 139)
SHAFF0 compressed file size: 555 bytes
SHAFF1 compressed file size: 429 bytes

SHAFFv1f:
Bit-stream compression: 1% (16384 -> 277)
Bit-stream compression: 0% (16384 -> 8)
Bit-stream compression: 0% (16384 -> 138)
SHAFF0 compressed file size: 555 bytes
SHAFF1 compressed file size: 435 bytes

SHAFFv1g:
Bit-stream compression: 1% (16384 -> 272)
Bit-stream compression: 0% (16384 -> 8)
Bit-stream compression: 0% (16384 -> 136)
SHAFF0 compressed file size: 555 bytes
SHAFF1 compressed file size: 428 bytes

SHAFFv1h:
Bit-stream compression: 1% (16384 -> 273)
Bit-stream compression: 0% (16384 -> 8)
Bit-stream compression: 0% (16384 -> 138)
SHAFF0 compressed file size: 555 bytes
SHAFF1 compressed file size: 431 bytes

SHAFFv1h - 431
SHAFFv1g - 428
SHAFFv1f - 435
SHAFFv1e - 429
SHAFFv1d - 439
SHAFFv1c - 438
SHAFFv1b - 570
SHAFFv1a - 526
SHAFFv1a+Huffman - 333
MegzLZ - 1021
Hrum - 926
Hrust - 478
ZIP - 672
GZIP - 547
BZIP2 - 502
RAR 3.80 - 552
XZ (LZMA2) - 548

chess.sna (49K):

Code: Select all

SHAFFv1b:
Actual compression: 10% (16384 -> 1665)
Actual compression: 51% (16384 -> 8427)
Actual compression: 1% (16384 -> 228)
Compressed file size: 10362 bytes

SHAFFv1c:
Bitstream compression: 8% (16384 -> 1330)
Bitstream compression: 44% (16384 -> 7255)
Bitstream compression: 1% (16384 -> 183)
Bitwise compressed file size (v1): 8780 bytes

SHAFFv1d:
Bit-stream compression: 8% (16384 -> 1322)
Bit-stream compression: 44% (16384 -> 7286)
Bit-stream compression: 1% (16384 -> 188)
SHAFF0 compressed file size: 10273 bytes
SHAFF1 compressed file size: 8808 bytes

SHAFFv1e:
Bit-stream compression: 7% (16384 -> 1308)
Bit-stream compression: 44% (16384 -> 7239)
Bit-stream compression: 1% (16384 -> 184)
SHAFF0 compressed file size: 9944 bytes
SHAFF1 compressed file size: 8743 bytes

SHAFFv1f:
Bit-stream compression: 7% (16384 -> 1311)
Bit-stream compression: 43% (16384 -> 7183)
Bit-stream compression: 1% (16384 -> 183)
SHAFF0 compressed file size: 9943 bytes
SHAFF1 compressed file size: 8688 bytes

SHAFFv1g:
Bit-stream compression: 7% (16384 -> 1305)
Bit-stream compression: 43% (16384 -> 7179)
Bit-stream compression: 1% (16384 -> 181)
SHAFF0 compressed file size: 9943 bytes
SHAFF1 compressed file size: 8676 bytes

SHAFFv1h:
Bit-stream compression: 7% (16384 -> 1301)
Bit-stream compression: 43% (16384 -> 7169)
Bit-stream compression: 1% (16384 -> 183)
SHAFF0 compressed file size: 9943 bytes
SHAFF1 compressed file size: 8665 bytes

SHAFFv1h - 8.6K
SHAFFv1g - 8.6K
SHAFFv1f - 8.6K
SHAFFv1e - 8.7K
SHAFFv1d - 8.8K
SHAFFv1c - 8.7K
SHAFFv1b - 10.3K
SHAFFv1a - 10.5K
SHAFFv1a+Huffman - 8.9K
MegaLZ - 9.0K
Hrum - 8.9K
Hrust - 8.5K
ZIP - 8.8K
GZIP - 8.8K
BZIP2 - 9.3K
RAR 3.80 - 8.3K
XZ (LZMA2) - 8.0K

cybotron.sna (49K):

Code: Select all

SHAFFv1b:
Actual compression: 35% (16384 -> 5751)
Actual compression: 0% (16384 -> 32)
Actual compression: 1% (16384 -> 208)
Compressed file size: 6033 bytes

SHAFFv1c:
Bitstream compression: 28% (16384 -> 4690)
Bitstream compression: 0% (16384 -> 20)
Bitstream compression: 1% (16384 -> 167)
Bitwise compressed file size (v1): 4889 bytes

SHAFFv1d:
Bit-stream compression: 28% (16384 -> 4733)
Bit-stream compression: 0% (16384 -> 20)
Bit-stream compression: 1% (16384 -> 171)
SHAFF0 compressed file size: 5968 bytes
SHAFF1 compressed file size: 4935 bytes

SHAFFv1e:
Bit-stream compression: 28% (16384 -> 4690)
Bit-stream compression: 0% (16384 -> 20)
Bit-stream compression: 1% (16384 -> 168)
SHAFF0 compressed file size: 5777 bytes
SHAFF1 compressed file size: 4890 bytes

SHAFFv1f:
Bit-stream compression: 28% (16384 -> 4641)
Bit-stream compression: 0% (16384 -> 21)
Bit-stream compression: 1% (16384 -> 167)
SHAFF0 compressed file size: 5777 bytes
SHAFF1 compressed file size: 4840 bytes

SHAFFv1g:
Bit-stream compression: 28% (16384 -> 4632)
Bit-stream compression: 0% (16384 -> 20)
Bit-stream compression: 1% (16384 -> 166)
SHAFF0 compressed file size: 5777 bytes
SHAFF1 compressed file size: 4829 bytes

SHAFFv1h:
Bit-stream compression: 28% (16384 -> 4629)
Bit-stream compression: 0% (16384 -> 21)
Bit-stream compression: 1% (16384 -> 167)
SHAFF0 compressed file size: 5777 bytes
SHAFF1 compressed file size: 4828 bytes

SHAFFv1h - 4.8K
SHAFFv1g - 4.8K
SHAFFv1f - 4.8K
SHAFFv1e - 4.8K
SHAFFv1d - 4.9K
SHAFFv1c - 4.8K
SHAFFv1b - 6.0K
SHAFFv1a - 6.1K
MegaLZ - 5.2K
Hrum - 5.2K
Hrust - 4.7K
ZIP - 5.0K
GZIP - 4.9K
BZIP2 - 5.2K
RAR 3.80 - 4.7K
XZ (LZMA2) - 4.4K

И оставшиеся SNA-файлы:

tomahawk.sna (49K):

Code: Select all

SHAFFv1a:
Estimated compression: 75% (16384 -> 12298)
Estimated compression: 80% (16384 -> 13185)
Estimated compression: 65% (16384 -> 10711)

SHAFFv1b:
Actual compression: 74% (16384 -> 12194)
Actual compression: 78% (16384 -> 12870)
Actual compression: 64% (16384 -> 10496)
Compressed file size: 35602 bytes

SHAFFv1c:
Bitstream compression: 63% (16384 -> 10350)
Bitstream compression: 65% (16384 -> 10786)
Bitstream compression: 53% (16384 -> 8831)
Bitwise compressed file size (v1): 29979 bytes

SHAFFv1d:
Bit-stream compression: 63% (16384 -> 10376)
Bit-stream compression: 66% (16384 -> 10842)
Bit-stream compression: 53% (16384 -> 8840)
SHAFF0 compressed file size: 35204 bytes
SHAFF1 compressed file size: 30070 bytes

SHAFFv1e:
Bit-stream compression: 62% (16384 -> 10318)
Bit-stream compression: 65% (16384 -> 10800)
Bit-stream compression: 53% (16384 -> 8777)
SHAFF0 compressed file size: 33938 bytes
SHAFF1 compressed file size: 29906 bytes

SHAFFv1f:
Bit-stream compression: 62% (16384 -> 10252)
Bit-stream compression: 65% (16384 -> 10680)
Bit-stream compression: 53% (16384 -> 8736)
SHAFF0 compressed file size: 33930 bytes
SHAFF1 compressed file size: 29680 bytes

SHAFFv1g:
Bit-stream compression: 62% (16384 -> 10245)
Bit-stream compression: 65% (16384 -> 10685)
Bit-stream compression: 53% (16384 -> 8717)
SHAFF0 compressed file size: 33935 bytes
SHAFF1 compressed file size: 29659 bytes

SHAFFv1h:
Bit-stream compression: 62% (16384 -> 10218)
Bit-stream compression: 65% (16384 -> 10654)
Bit-stream compression: 53% (16384 -> 8704)
SHAFF0 compressed file size: 33935 bytes
SHAFF1 compressed file size: 29588 bytes

SHAFFv1h - 29.5K
SHAFFv1g - 29.6K
SHAFFv1f - 29.6K
SHAFFv1e - 29.9K
SHAFFv1d - 30.0K
SHAFFv1c - 29.9K
SHAFFv1b - 35.6K
SHAFFv1a - 36.2K
MegaLZ - 29.0K
Hrum - 29.2K
Hrust - 28.4K
ZIP - 28.8K
GZIP - 28.7K
BZIP2 - 30.1K
RAR 3.80 - 27.5K
XZ (LZMA2) - 25.6K

exolon.sna (49K):

Code: Select all

SHAFFv1a:
Estimated compression: 54% (16384 -> 9011)
Estimated compression: 66% (16384 -> 10920)
Estimated compression: 69% (16384 -> 11378)

SHAFFv1b:
Actual compression: 54% (16384 -> 8872)
Actual compression: 66% (16384 -> 10917)
Actual compression: 69% (16384 -> 11351)
Compressed file size: 31182 bytes

SHAFFv1c:
Bitstream compression: 45% (16384 -> 7408)
Bitstream compression: 56% (16384 -> 9311)
Bitstream compression: 60% (16384 -> 9832)
Bitwise compressed file size (v1): 26562 bytes

SHAFFv1d:
Bit-stream compression: 45% (16384 -> 7441)
Bit-stream compression: 56% (16384 -> 9332)
Bit-stream compression: 60% (16384 -> 9865)
SHAFF0 compressed file size: 30810 bytes
SHAFF1 compressed file size: 26649 bytes

SHAFFv1e:
Bit-stream compression: 44% (16384 -> 7367)
Bit-stream compression: 56% (16384 -> 9287)
Bit-stream compression: 59% (16384 -> 9772)
SHAFF0 compressed file size: 29797 bytes
SHAFF1 compressed file size: 26438 bytes

SHAFFv1f:
Bit-stream compression: 44% (16384 -> 7337)
Bit-stream compression: 56% (16384 -> 9250)
Bit-stream compression: 59% (16384 -> 9709)
SHAFF0 compressed file size: 29776 bytes
SHAFF1 compressed file size: 26307 bytes

SHAFFv1g:
Bit-stream compression: 44% (16384 -> 7331)
Bit-stream compression: 56% (16384 -> 9241)
Bit-stream compression: 59% (16384 -> 9706)
SHAFF0 compressed file size: 29794 bytes
SHAFF1 compressed file size: 26290 bytes

SHAFFv1h:
Bit-stream compression: 44% (16384 -> 7328)
Bit-stream compression: 56% (16384 -> 9248)
Bit-stream compression: 59% (16384 -> 9688)
SHAFF0 compressed file size: 29794 bytes
SHAFF1 compressed file size: 26276 bytes

SHAFFv1h - 26.2K
SHAFFv1g - 26.2K
SHAFFv1f - 26.3K
SHAFFv1e - 26.4K
SHAFFv1d - 26.6K
SHAFFv1c - 26.5K
SHAFFv1b - 31.2K
SHAFFv1a - 31.3K
MegaLZ - 25.7K
Hrum - 25.9K
Hrust - 25.1K
ZIP - 25.6K
GZIP - 25.5K
BZIP2 - 27.8K
RAR 3.80 - 24.5K
XZ (LZMA2) - 22.9K

buzzsaw.sna (49K):

Code: Select all

SHAFFv1a:
Estimated compression: 53% (16384 -> 8846)
Estimated compression: 72% (16384 -> 11850)
Estimated compression: 47% (16384 -> 7716)

SHAFFv1b:
Actual compression: 54% (16384 -> 8940)
Actual compression: 71% (16384 -> 11789)
Actual compression: 46% (16384 -> 7698)
Compressed file size: 28469 bytes

SHAFFv1c:
Bitstream compression: 50% (16384 -> 8332)
Bitstream compression: 66% (16384 -> 10888)
Bitstream compression: 36% (16384 -> 6001)
Bitwise compressed file size (v1): 25233 bytes

SHAFFv1d:
Bit-stream compression: 50% (16384 -> 8332)
Bit-stream compression: 66% (16384 -> 10942)
Bit-stream compression: 37% (16384 -> 6128)
SHAFF0 compressed file size: 28290 bytes
SHAFF1 compressed file size: 25414 bytes

SHAFFv1e:
Bit-stream compression: 50% (16384 -> 8307)
Bit-stream compression: 66% (16384 -> 10894)
Bit-stream compression: 36% (16384 -> 5970)
SHAFF0 compressed file size: 27888 bytes
SHAFF1 compressed file size: 25182 bytes

SHAFFv1f:
Bit-stream compression: 50% (16384 -> 8279)
Bit-stream compression: 66% (16384 -> 10844)
Bit-stream compression: 36% (16384 -> 5962)
SHAFF0 compressed file size: 27878 bytes
SHAFF1 compressed file size: 25097 bytes

SHAFFv1g:
Bit-stream compression: 50% (16384 -> 8274)
Bit-stream compression: 66% (16384 -> 10841)
Bit-stream compression: 36% (16384 -> 5953)
SHAFF0 compressed file size: 27884 bytes
SHAFF1 compressed file size: 25080 bytes

SHAFFv1h:
Bit-stream compression: 50% (16384 -> 8289)
Bit-stream compression: 66% (16384 -> 10841)
Bit-stream compression: 36% (16384 -> 5959)
SHAFF0 compressed file size: 27887 bytes
SHAFF1 compressed file size: 25101 bytes

SHAFFv1h - 25.1K
SHAFFv1g - 25.0K
SHAFFv1f - 25.0K
SHAFFv1e - 25.1K
SHAFFv1d - 25.4K
SHAFFv1c - 25.2K
SHAFFv1b - 28.5K
SHAFFv1a - 28.4K
MegaLZ - 24.3K
Hrum - 24.3K
Hrust - 23.1K
ZIP - 24.4K
GZIP - 24.2K
BZIP2 - 25.1K
RAR 3.80 - 15.1K
XZ (LZMA2) - 17.1K

bozxle.sna (49K):

Code: Select all

SHAFFv1b:
Actual compression: 41% (16384 -> 6808)
Actual compression: 66% (16384 -> 10828)
Actual compression: 41% (16384 -> 6843)
Compressed file size: 24521 bytes

SHAFFv1c:
Bitstream compression: 32% (16384 -> 5300)
Bitstream compression: 60% (16384 -> 9991)
Bitstream compression: 31% (16384 -> 5184)
Bitwise compressed file size (v1): 20486 bytes

SHAFFv1e:
Bit-stream compression: 31% (16384 -> 5222)
Bit-stream compression: 60% (16384 -> 9969)
Bit-stream compression: 32% (16384 -> 5260)
SHAFF0 compressed file size: 23306 bytes
SHAFF1 compressed file size: 20463 bytes

SHAFFv1f:
Bit-stream compression: 31% (16384 -> 5153)
Bit-stream compression: 60% (16384 -> 9901)
Bit-stream compression: 31% (16384 -> 5196)
SHAFF0 compressed file size: 23279 bytes
SHAFF1 compressed file size: 20262 bytes

SHAFFv1g:
Bit-stream compression: 31% (16384 -> 5193)
Bit-stream compression: 60% (16384 -> 9945)
Bit-stream compression: 31% (16384 -> 5196)
SHAFF0 compressed file size: 23297 bytes
SHAFF1 compressed file size: 20345 bytes

SHAFFv1h:
Bit-stream compression: 31% (16384 -> 5141)
Bit-stream compression: 60% (16384 -> 9919)
Bit-stream compression: 31% (16384 -> 5185)
SHAFF0 compressed file size: 23299 bytes
SHAFF1 compressed file size: 20257 bytes

SHAFFv1h - 20.2K
SHAFFv1g - 20.3K
SHAFFv1f - 20.2K
SHAFFv1e - 20.4K
SHAFFv1c - 20.4K
SHAFFv1b - 24.5K
MegaLZ - 20.1K
Hrum - 20.1K
Hrust - 19.5K
ZIP - 19.5K
GZIP - 19.3K
BZIP2 - 21.0K
RAR 3.80 - 18.9K
XZ (LZMA2) - 17.1K

Возникает вопрос - выкатывать архиватор в таком виде как версию 1 и думать над более компактным представлением в следующих версиях либо поресёрчить ещё?...

P.S. Например можно смещение после #FF представлять иначе:
- если смещение равно нулю (#00), то это команда, заменяющая один символ #FF;
- если старший бит 0, то смещение занимает 1 байт и может принимать значения от -1 до -127 (представляемые величинами от #01 до #7F);
- если старшие два бита 1 и 0, то смещение занимает 1 байт и может принимать значения от -128 до -191 (представляемые величинами от #80 до #BF);
- если старшие два бита 1 и 1, то смещение занимает 2 байта и может принимать значения от -192/#FF40 до -16383/#C001 (величины #C000 и #FF41...#FFFF не используются).
Далее идёт размер блока - на нём также можно сэкономить, т.к. размеров больше 16383 (#3FFF) быть не может:
- если старший бит 1, то размер занимает один байт и задаёт значения от 4 до 131 ( представляемые величинами от #80 до #FF или S+124 );
- если старшие два бита 0 и 1, то размер занимает 1 байт и задаёт значения от 132 до 195 ( представляемые величинами от #40 до #7F или S-68 );
- если старшие два бита 0 и 0, то размер занимает 2 байта и может принимать значения от 196/#00С4 до 16383/#3FFF (величины #0000...#00С3 не используются).
В результате без особых усилий мы уменьшили максимальную длину FF-команды до 5 байтов (1+2+2).

P.P.S. Последовательность вида #FF #С0 #00 может являться маркером конца блока, а в будущем ещё и #FF #FF [#41...#FF] можно будет задействовать для задания спец-команд...

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

P.P.P.P.S. 15 октября добавил сюда результаты по битовопоточному SHAFF под названием SHAFFv1c - он даже MegaLZ бывает обгоняет, но вот Hrust похоже недосягаем...

P.P.P.P.P.S. 17 октября добавляю результаты SHAFFv1d - финальный прототип для версии 1. Хотя чего-то он худшие результаты показывает, чем SHAFFv1c - видимо надо подкорректировать формат ещё раз

P.P.P.P.P.P.S. 20 октября добавляю результаты SHAFFv1e - на этот раз точно финальный прототип для версии 1. Он обгоняет MegaLZ на данных, где есть много повторяющихся байтов, но отстаёт, если их мало. Но зато все имеющиеся SNA-файлы влезают в 32К...

P.P.P.P.P.P.P.S. 21 октября добавляю результаты SHAFFv1f - он чуть лучше, а затем и SHAFFv1g - он ещё лучше...

P.P.P.P.P.P.P.P.S. 24 октября добавил результаты по SHAFFv1h - он где-то лучше, а где-то хуже...

[alone]

А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.

[Shaos]

А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.

Это оптимальный LZ77-like, но не совсем оптимальное представление (без Хаффмана - с Хаффманом как раз всё хорошо)

[alone]

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

[Shaos]

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

[alone]

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

[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 практически не дало выигрыша.