nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 19 Mar 2024 01:29



Reply to topic  [ 117 posts ]  Go to page 1, 2, 3, 4, 5 ... 8  Next
Недоархиватор SHAFF 
Author Message
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Задумал я тут недоархиватор, чтобы декодер был поменьше чем MegaLZ, степень сжатия не хуже, ну и само-собой опенсорц :)

Идея такая - сжатие на байтовом уровне (хаффмана могу попозже приделать) - байт #FF является ключевым (поэтому SHAFF ; ), после него идёт смещение до копии и длина повторяющегося блока. Если смещение/длина в диапазоне от 1 до 254, то ставим один байт, если больше - то #00 и далее два байта (т.е. всего будет три). Получается команда, начинающаяся с #FF, может занимать от 3 до 7 байт. Если встречается отдельно стоящий байт #FF, то он раздваивается - #FF #FF, чтобы декодер не принял его за начало команды. Некоторые последовательности можно объявить командами, например: #FF #00 #00 #00 #01 (смещение в виде #00 #00 #00 никогда не попадётся) может обозначать маркер конца блока. Повторяющиеся байты описываются последовательностью, которая ссылается сама на себя - например 16 нулей могут быть закодированы так: #00 #FF #01 #0F (сначала отдельный байт #00 далее команда копирования по смещению -1 блока длиной 15 байт).

Архиватор работает с блоками 16К - чтобы охватить все возможные варианты повторений строим в памяти буфер 32Мб, в котором располагаем автокорреляционную матрицу с шагом от 1 до 16383. И далее "жадным" алгоритмом откусываем самые большие куски, пока не останутся только маленькие (3 и менее повторяющихся байт). Жмёт долго, но зато почти оптимально ;)

P.S. Обновление от 7 октября 2013:
Заголовок файла SHAFF может выглядеть примерно так:
0...5 "SHAFF1" - первые 6 байт сигнатура и версия
6,7 - смещение от начала файла до данных первого блока в сетевом формате (big-endian)
8,9 - количество блоков (тоже в сетевом формате)
10,11 - длина последнего блока (она может быть меньше 16K)

P.P.S. Обновление от 11 октября 2013:
Например можно смещение после #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).
Последовательность вида #FF #С0 #00 может являться маркером конца блока, а в будущем ещё и #FF #FF [#41...#FF] можно будет задействовать для задания спец-команд...

P.P.P.S. Обновление от 23 октября 2013 с небольшими уточнениями в январе 2017- окончательный формат для первой версии архиватора (в марте 2021 сделал описание более понятным):
Code:
SHAFF header:

Bytes 0...5 - signature and version ("SHAFF0", "SHAFF1" or "SHAFF2")
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
(for optional Huffman data in header after "HUF" signature see SHAFF2 description below)
Then sequence of encoded 16KB blocks in chosen format:


SHAFF0 data format:

1st byte sets a Key to use further instead of #FF (but usually it's #FF)
then any byte other than Key goes directly to output, but for Key see below
#FF 00000000 - single byte #FF, otherwise
#FF 0xxxxxxx LENGTH - distance 1..127 and LENGTH (see below)
#FF 10xxxxxx LENGTH - distance 128..190 and LENGTH (see below), but
#FF 10111111 LENGTH - reuses previous long distance -191 or longer
#FF 11xxxxxx xxxxxxxx LENGTH - directly encoded long negative distance, but
#FF 11000000 00000000 - end of block (with no length after)
where LENGTH encoded by 1 or 2 bytes:
1xxxxxxx - for 4..131
01xxxxxx - for 132..195
00xxxxxx xxxxxxxx - direcly encoded length 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...255 (0000000...1111111)
11111110xxxxxxxx - for 256...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)


SHAFF2 data format:

00... \
01... - Huffman codes for literals
10... /
11... - Reference that encoded the same way as in SHAFF1 above

Optional Huffman table after "HUF" signature in header:
 #FF N - start section with codes that have length N (1...254)
 XX ... - code for byte XX (Huffman code starts with most significant bit)
 #FF #00 ... - code for byte #FF
 #FF #FF - end of HUF table

If "HUF" signature is not found in the header then it means depacker must use internal
Huffman table for English text in ASCII format. Other internal tables will also be
supported as HUF1 for Russian text in alternative DOS codepage, HUF2 for Russian text
in UTF-8 format with UNIX line ending and HUF3 for C/C++ source code also with UNIX line
ending.


P.P.P.P.S. Исходники тут (к 8 февраля 2017 реализовал оба метода SHAFF0 и SHAFF1, а 12 февраля 2017 добавил экспериментальную поддержку SHAFF2, ну и в июне 2018 это всё переехало с GitHub на GitLab):

https://gitlab.com/shaos/shaff

Code:
SHAFF v1.2 (C) 2013,2017 A.A.Shabarshin <me@shaos.net>


Usage:
   shaff [options] filename

Encoding options:
   -0 to use SHAFF0 file format (by default)
   -1 to use SHAFF1 file format
   -2 to use SHAFF2 file format (experimental)
   -b to compress blocks into separate files
   -bN to compress only block N
   -bN-M to compress blocks N..M
   -lN to limit length of matches (default value is 4 for SHAFF0 and 2 for SHAFF1/2)
   -xHH to set prefix byte other than FF (applicable only to SHAFF0 file format)
   -e to set default table for English text (applicable only to SHAFF2 file format)

Decoding options:
   -d to decode compressed SHAFF file to file
   -c to decode compressed SHAFF file to screen


P.P.P.P.P.S. На самом деле SHAFF не LZ77-like, а LZSS-like паковщик (как и большинство архиваторов и пакеров, существующих в данный момент) т.к. мы работаем с одним потоком данных, в котором перемежаются литералы и ссылки, идентифицирующиеся по префиксам:
https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski
https://ru.wikipedia.org/wiki/LZSS (по русски)


P.P.P.P.P.P.S. Пока выложил EXE-шник последней версии 1.2 от 2017 года под винды, кому интересно: https://gitlab.com/shaos/shaff/-/tree/master/binaries/win32

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 25 Oct 2013 16:53, edited 15 times in total.



07 Oct 2013 01:24
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Живой пример - файл chess.sna (49K), который обычный ZIP жмёт в 8.8K (MegaLZ должен жать примерно также). Разбиваем его на 3 блока по 16K и жмём с помощью SHAFF:
Code:
Estimated compression: 11% (16384 -> 1815)
Estimated compression: 51% (16384 -> 8493)
Estimated compression: 1% (16384 -> 228)

В итоге потратив 23 минуты на Pentium-4 получаем 10.5К - и это без Хаффмана :)

Другой пример - файл cybotron.sna (49K), который обычный ZIP жмёт в 5К (игра для 16К спектрума - большая часть снапшота это нули):
Code:
Estimated compression: 35% (16384 -> 5818)
Estimated compression: 0% (16384 -> 27)
Estimated compression: 1% (16384 -> 208)

За 19 минут на Pentium-4 получили 6К :o

P.S. Боюсь представить сколько это будет если сверху пройтись Хаффманом...

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 11 Oct 2013 20:41, edited 3 times in total.



07 Oct 2013 01:33
Profile WWW
Retired

Joined: 27 Mar 2013 04:55
Posts: 587
Location: 62.192.229.16
Reply with quote
Post 
Перед тем как мне дали в руки MegaLZ, я написал свой архиватор по алгоритму LZW (http://ru.wikipedia.org/wiki/LZW)

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

Но алгоритм требовал место в памяти под словарь. Вроде бы 512 байт, я сейчас не помню точно.

У MegaLZ есть гигантское преимущество - он не требует доп памяти и исходный архив читает строго последовательно.


07 Oct 2013 01:36
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
У меня тоже словаря нет - по сути это сильно упрощённый MegaLZ (а точнее что-то типа LZ77, но где "окно" никуда не "скользит", а растёт от начала кодируемого буфера), где убрана вся алхимия с битовыми последовательностями. Кстати я могу этот архиватор заставить опционально сохранять файл в формате MegaLZ...

_________________
:dj: https://mastodon.social/@Shaos


07 Oct 2013 01:39
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Ещё примеры:

Файл tomahawk.sna (49K) - сжимается ZIP в 28.8K, а у нас:
Code:
Estimated compression: 74% (16384 -> 12269)
Estimated compression: 80% (16384 -> 13123)
Estimated compression: 64% (16384 -> 10587)

получилось 35.9К за 93 минуты.

Файл exolon.sna (49K) - сжимается ZIP в 25.6К, а у нас:
Code:
Estimated compression: 54% (16384 -> 9000)
Estimated compression: 66% (16384 -> 10911)
Estimated compression: 69% (16384 -> 11336)

получилось 31.2К за 67 минут.

Файл buzzsaw.sna (49K) - сжимается ZIP в 24.4К, а у нас:
Code:
Estimated compression: 54% (16384 -> 8856)
Estimated compression: 72% (16384 -> 11861)
Estimated compression: 47% (16384 -> 7763)

получилось 28.5К за 55 минут.

т.е. в 32К не влез только Tomahawk (надо попробовать Хаффманом по нему пройтись)...

P.S. зная вероятности появления символов можно прикинуть хаффмановскую таблицу в онлайне: http://planetcalc.com/2481/

_________________
:dj: https://mastodon.social/@Shaos


07 Oct 2013 05:49
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Заголовок файла SHAFF может выглядеть примерно так:
0...5 "SHAFF1" - первые 6 байт сигнатура и версия
6,7 - смещение от начала файла до данных первого блока в сетевом формате (big-endian)
8,9 - количество блоков (тоже в сетевом формате)
10,11 - длина последнего блока (она может быть меньше 16K)
12,13... - далее 2-байтовые контрольные суммы по одной на блок
перед непосредственно данными может идти дополнительная информация, например содержимое регистров для снапшота и/или таблица кодирования по Хаффману...

P.S. Вот так выглядит процесс сжатия снапшота пустого бейсика (в алгоритме есть косяк - разбираюсь):
Code:
./shaff zx48.sna

Block 1:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 9010 bytes in #1CCF is identical to offset -1/#FFFF (estimation: 7379)
Sequence 4320 bytes in #1CCE is identical to offset -7374/#E332 (estimation: 3066)
Sequence 767 bytes in #1801 is identical to offset -1/#FFFF (estimation: 2304)
Sequence 256 bytes in #1CCE is identical to offset -462/#FE32 (estimation: 2055)
Sequence 255 bytes in #1B00 is identical to offset -2591/#F5E1 (estimation: 1805)
Sequence 235 bytes in #15F5 is identical to offset -256/#FF00 (estimation: 1575)
Sequence 231 bytes in #13FC is identical to offset -256/#FF00 (estimation: 1349)
Sequence 230 bytes in #14FC is identical to offset -768/#FD00 (estimation: 1124)
Sequence 229 bytes in #16FB is identical to offset -768/#FD00 (estimation: 900)
Sequence 228 bytes in #16FC is identical to offset -256/#FF00 (estimation: 677)
Sequence 228 bytes in #1B00 is identical to offset -1028/#FBFC (estimation: 454)
Sequence 34 bytes in #1CCE is identical to offset -62/#FFC2 (estimation: 423)
Sequence 31 bytes in #1B00 is identical to offset -799/#FCE1 (estimation: 397)
Sequence 26 bytes in #1C90 is identical to offset -115/#FF8D (estimation: 374)
Sequence 12 bytes in #1C90 is identical to offset -36/#FFDC (estimation: 365)
Sequence 9 bytes in #1C6C is identical to offset -45/#FFD3 (estimation: 359)
Sequence 6 bytes in #11FC is identical to offset -11/#FFF5 (estimation: 356)
Sequence 5 bytes in #1C17 is identical to offset -8/#FFF8 (estimation: 354)
Sequence 5 bytes in #1C3E is identical to offset -58/#FFC6 (estimation: 352)
Sequence 4 bytes in #1C6C is identical to offset -15/#FFF1 (estimation: 351)
Sequence 4 bytes in #1C0C is identical to offset -1/#FFFF (estimation: 350)
Sequence 4 bytes in #1C63 is identical to offset -2/#FFFE (estimation: 349)
Sequence 4 bytes in #1C04 is identical to offset -4/#FFFC (estimation: 348)
Sequence 4 bytes in #1C53 is identical to offset -8/#FFF8 (estimation: 347)
Sequence 4 bytes in #1CC5 is identical to offset -10/#FFF6 (estimation: 346)
Estimated compression: 2% (16384 -> 346)

Block 2:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16383 bytes in #0001 is identical to offset -1/#FFFF (estimation: 6)
Estimated compression: 0% (16384 -> 6)

Block 3:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16183 bytes in #0001 is identical to offset -1/#FFFF (estimation: 206)
Sequence 7 bytes in #3F7F is identical to offset -8/#FFF8 (estimation: 202)
Sequence 7 bytes in #3FDE is identical to offset -16/#FFF0 (estimation: 198)
Sequence 6 bytes in #3FD5 is identical to offset -80/#FFB0 (estimation: 195)
Sequence 5 bytes in #3FD7 is identical to offset -16/#FFF0 (estimation: 193)
Sequence 5 bytes in #3F87 is identical to offset -32/#FFE0 (estimation: 191)
Sequence 5 bytes in #3FBC is identical to offset -40/#FFD8 (estimation: 189)
Sequence 5 bytes in #3FCC is identical to offset -40/#FFD8 (estimation: 187)
Sequence 5 bytes in #3F91 is identical to offset -55/#FFC9 (estimation: 185)
Sequence 4 bytes in #3FCF is identical to offset -112/#FF90 (estimation: 184)
Sequence 4 bytes in #3FB2 is identical to offset -1/#FFFF (estimation: 183)
Sequence 4 bytes in #3FF3 is identical to offset -1/#FFFF (estimation: 182)
Sequence 4 bytes in #3FFA is identical to offset -1/#FFFF (estimation: 181)
Sequence 4 bytes in #3FA5 is identical to offset -24/#FFE8 (estimation: 180)
Sequence 4 bytes in #3F8D is identical to offset -32/#FFE0 (estimation: 179)
Sequence 4 bytes in #3FE5 is identical to offset -56/#FFC8 (estimation: 178)
Sequence 4 bytes in #3FD1 is identical to offset -110/#FF92 (estimation: 177)
Estimated compression: 1% (16384 -> 177)

Good bye!


P.S. Всё-таки надо постараться обойтись без Хаффмана - можно попробовать сильнее разнообразить способ представления аргументов команды #FF - не так разнообразно как в MegaLZ, но лучше чем только 1 vs 3 байта, как озвучено в первом посте этого топика - для этого можно проанализировать распределение размеров и смещений на нескольких реальных примерах, чтобы определить оптимальный битовый размер этих двух параметров...

_________________
:dj: https://mastodon.social/@Shaos


07 Oct 2013 17:54
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Косяк исправил - вот правильное сжатие памяти ZX-48K:
Code:
SHAFF v1.0 (C) 2013, Alexander A. Shabarshin <ashabarshin@gmail.com>

Block 1:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 9009 bytes from #1CCF is identical to offset -1/#FFFF (estimation: 7380)
Sequence 4319 bytes from #0001 is identical to offset -1/#FFFF (estimation: 3066)
Sequence 767 bytes from #1801 is identical to offset -1/#FFFF (estimation: 2304)
Sequence 260 bytes from #16FC is identical to offset -1792/#F900 (estimation: 2051)
Sequence 256 bytes from #1B00 is identical to offset -2848/#F4E0 (estimation: 1802)
Sequence 255 bytes from #10E1 is identical to offset -256/#FF00 (estimation: 1554)
Sequence 235 bytes from #15F5 is identical to offset -256/#FF00 (estimation: 1324)
Sequence 231 bytes from #13FC is identical to offset -256/#FF00 (estimation: 1098)
Sequence 230 bytes from #14FC is identical to offset -768/#FD00 (estimation: 873)
Sequence 229 bytes from #12FB is identical to offset -256/#FF00 (estimation: 649)
Sequence 228 bytes from #11FC is identical to offset -256/#FF00 (estimation: 426)
Sequence 35 bytes from #1C8F is identical to offset -400/#FE70 (estimation: 396)
Sequence 27 bytes from #1C1D is identical to offset -1111/#FBA9 (estimation: 374)
Sequence 12 bytes from #1C6C is identical to offset -76/#FFB4 (estimation: 365)
Sequence 10 bytes from #1C3F is identical to offset -1096/#FBB8 (estimation: 360)
Sequence 7 bytes from #1C01 is identical to offset -4/#FFFC (estimation: 356)
Sequence 6 bytes from #11F1 is identical to offset -23/#FFE9 (estimation: 353)
Sequence 5 bytes from #1C0B is identical to offset -16/#FFF0 (estimation: 351)
Sequence 5 bytes from #1C17 is identical to offset -8/#FFF8 (estimation: 349)
Sequence 4 bytes from #1C5D is identical to offset -29/#FFE3 (estimation: 348)
Sequence 4 bytes from #1C63 is identical to offset -2/#FFFE (estimation: 347)
Sequence 4 bytes from #1C53 is identical to offset -8/#FFF8 (estimation: 346)
Sequence 4 bytes from #1CC5 is identical to offset -10/#FFF6 (estimation: 345)
Number of commands: 23
Estimated compression: 2% (16384 -> 345)
Actual compression: 2% (16384 -> 345)

Block 2:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16383 bytes from #0001 is identical to offset -1/#FFFF (estimation: 6)
Number of commands: 1
Estimated compression: 0% (16384 -> 6)
Actual compression: 0% (16384 -> 6)

Block 3:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16183 bytes from #0001 is identical to offset -1/#FFFF (estimation: 206)
Sequence 7 bytes from #3F7F is identical to offset -8/#FFF8 (estimation: 202)
Sequence 7 bytes from #3FDE is identical to offset -16/#FFF0 (estimation: 198)
Sequence 6 bytes from #3FFA is identical to offset -48/#FFD0 (estimation: 195)
Sequence 6 bytes from #3FD5 is identical to offset -80/#FFB0 (estimation: 192)
Sequence 5 bytes from #3FB4 is identical to offset -56/#FFC8 (estimation: 190)
Sequence 5 bytes from #3F87 is identical to offset -32/#FFE0 (estimation: 188)
Sequence 5 bytes from #3FBC is identical to offset -40/#FFD8 (estimation: 186)
Sequence 5 bytes from #3FCC is identical to offset -40/#FFD8 (estimation: 184)
Sequence 5 bytes from #3F91 is identical to offset -55/#FFC9 (estimation: 182)
Sequence 4 bytes from #3FF3 is identical to offset -1/#FFFF (estimation: 181)
Sequence 4 bytes from #3FA5 is identical to offset -24/#FFE8 (estimation: 180)
Sequence 4 bytes from #3F8D is identical to offset -32/#FFE0 (estimation: 179)
Sequence 4 bytes from #3FE6 is identical to offset -32/#FFE0 (estimation: 178)
Sequence 4 bytes from #3FED is identical to offset -32/#FFE0 (estimation: 177)
Sequence 4 bytes from #3FC7 is identical to offset -64/#FFC0 (estimation: 176)
Sequence 4 bytes from #3FD1 is identical to offset -110/#FF92 (estimation: 175)
Number of commands: 17
Estimated compression: 1% (16384 -> 175)
Actual compression: 1% (16384 -> 175)

0x00;84
0x01;11
0x02;12
0x04;17
0x05;10
0x06;4
0x07;3
0x08;9
0x09;2
0x0A;2
0x0B;1
0x0C;3
0x0D;1
0x0F;2
0x10;23
0x12;1
0x15;4
0x17;3
0x18;3
0x1B;1
0x1C;6
0x1D;1
0x20;16
0x21;3
0x23;3
0x28;3
0x30;3
0x31;1
0x33;1
0x37;2
0x38;13
0x3B;1
0x3C;23
0x3E;5
0x3F;2
0x40;24
0x42;32
0x44;17
0x46;1
0x48;2
0x4A;2
0x4B;1
0x4C;1
0x4D;1
0x4E;1
0x50;4
0x52;3
0x53;1
0x54;1
0x57;1
0x58;1
0x5A;1
0x5B;1
0x5C;10
0x62;1
0x66;1
0x6E;1
0x70;2
0x78;7
0x7C;6
0x7E;5
0x7F;1
0x80;3
0x81;1
0x92;1
0x99;1
0xA1;1
0xA8;2
0xA9;1
0xB4;1
0xB6;2
0xB8;1
0xB9;1
0xC4;2
0xCA;1
0xCB;1
0xCC;2
0xCE;1
0xDB;2
0xDF;1
0xE0;1
0xE1;1
0xE4;1
0xE5;1
0xE6;1
0xE7;1
0xEB;2
0xF4;3
0xF9;1
0xFB;2
0xFC;1
0xFD;1
0xFE;2
0xFF;15
0x100;41

Good bye!


В конце видно таблицу вероятностей - по ней можно построить таблицу Хаффмана и прикинуть насколько оно ещё сожмётся:
Code:
0x00   111
0x100   1100
0x42   1001
0x40   0100
0x3C   0001
0x10   0000
0x44   10110
0x04   10101
0x20   10100
0xFF   01100
0x38   01010
0x02   00101
0x01   110111
0x5C   110101
0x05   110100
0x08   101111
0x78   010110
0x7C   001101
0x1C   001100
0x7E   1101100
0x3E   1011101
0x50   1011100
0x15   0111101
0x06   0111100
0x80   11011011
0x52   11011010
0xF4   0101110
0x0C   0011111
0x07   0011110
0x18   0011101
0x17   0011100
0x23   0010011
0x21   0010010
0x30   0010001
0x28   0010000
0x37   10000111
0x0F   10000110
0x48   10000101
0x3F   10000100
0x0A   10000001
0x09   10000000
0xCC   01101111
0xC4   01101110
0xEB   01101101
0xDB   01101100
0x70   01101011
0x4A   01101010
0xB6   01101001
0xA8   01101000
0xFE   01011111
0xFB   01011110
0x4B   100011111
0x46   100011110
0x4D   100011101
0x4C   100011100
0x31   100011011
0x1D   100011010
0x3B   100011001
0x33   100011000
0x5A   100010111
0x58   100010110
0x62   100010101
0x5B   100010100
0x53   100010011
0x4E   100010010
0x57   100010001
0x54   100010000
0x0D   100000111
0x0B   100000110
0x1B   100000101
0x12   100000100
0xF9   011111111
0xE7   011111110
0xFD   011111101
0xFC   011111100
0xE4   011111011
0xE1   011111010
0xE6   011111001
0xE5   011111000
0x99   011101111
0x92   011101110
0xA9   011101101
0xA1   011101100
0x6E   011101011
0x66   011101010
0x81   011101001
0x7F   011101000
0xCE   011100111
0xCB   011100110
0xE0   011100101
0xDF   011100100
0xB8   011100011
0xB4   011100010
0xCA   011100001
0xB9   011100000


P.S. В таблице 0x100 это на самом деле команда #FF - просто я её отдельно от символа #FF учитываю, чтобы посмотреть имеет смысл её отдельно в Хаффмане считать или нет...

P.P.S. С раздельными FF получилось 526 без Хаффмана и 334 с Хаффманом. Теперь пробуем объединённые коды #FF (15 и 41 будет 2*15+41=71 для #FF):
Code:
0x00   111
0xFF   101
0x42   1000
0x40   0011
0x10   11011
0x3C   0000
0x44   10011
0x04   10010
0x20   01011
0x38   01000
0x02   00011
0x01   110101
0x5C   110011
0x05   110010
0x08   110001
0x78   010011
0x7C   001001
0x1C   001000
0x7E   1101000
0x3E   1100001
0x50   1100000
0x15   0101001
0x06   0101000
0x80   11010011
0x52   11010010
0xF4   0100100
0x0C   0010111
0x07   0010110
0x18   0010101
0x17   0010100
0x23   0001011
0x21   0001010
0x30   0001001
0x28   0001000
0x37   01111111
0x0F   01111110
0x48   01111101
0x3F   01111100
0x0A   01111001
0x09   01111000
0xCC   01110111
0xC4   01110110
0xEB   01110101
0xDB   01110100
0x70   01110011
0x4A   01110010
0xB6   01110001
0xA8   01110000
0xFE   01001011
0xFB   01001010
0x0D   011110111
0x0B   011110110
0x1B   011110101
0x12   011110100
0x99   011011111
0x92   011011110
0xA9   011011101
0xA1   011011100
0x6E   011011011
0x66   011011010
0x81   011011001
0x7F   011011000
0xCE   011010111
0xCB   011010110
0xE0   011010101
0xDF   011010100
0xB8   011010011
0xB4   011010010
0xCA   011010001
0xB9   011010000
0x4B   011001111
0x46   011001110
0x4D   011001101
0x4C   011001100
0x31   011001011
0x1D   011001010
0x3B   011001001
0x33   011001000
0x5A   011000111
0x58   011000110
0x62   011000101
0x5B   011000100
0x53   011000011
0x4E   011000010
0x57   011000001
0x54   011000000
0xF9   010101111
0xE7   010101110
0xFD   010101101
0xFC   010101100
0xE4   010101011
0xE1   010101010
0xE6   010101001
0xE5   010101000

Подсчёт показывает те же 334 байта, т.е. выгоды в разделении команды #FF и символа #FF практически нет...

P.P.P.S. Кстати ZIP сжимает zx48.sna в 672 байта - выходит SHAFF даже без Хаффмана сжимает лучше ;)
С другой стороны для Хаффмана ещё и таблицу надо хранить...

P.P.P.P.S. GZIP сжимает в 547, BZIP2 в 502, а XZ в 548...

_________________
:dj: https://mastodon.social/@Shaos


10 Oct 2013 16:50
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
А теперь попробуем пойти на маленькую хитрость - разрешим 3-байтовые последовательности, которые без Хаффмана не имеют смысла:
Code:
SHAFF v1.0 (C) 2013, Alexander A. Shabarshin <ashabarshin@gmail.com>

Block 1:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 9009 bytes from #1CCF is identical to offset -1/#FFFF (estimation: 7380)
Sequence 4319 bytes from #0001 is identical to offset -1/#FFFF (estimation: 3066)
Sequence 767 bytes from #1801 is identical to offset -1/#FFFF (estimation: 2304)
Sequence 260 bytes from #16FC is identical to offset -1792/#F900 (estimation: 2051)
Sequence 256 bytes from #1B00 is identical to offset -2848/#F4E0 (estimation: 1802)
Sequence 255 bytes from #10E1 is identical to offset -256/#FF00 (estimation: 1554)
Sequence 235 bytes from #15F5 is identical to offset -256/#FF00 (estimation: 1324)
Sequence 231 bytes from #13FC is identical to offset -256/#FF00 (estimation: 1098)
Sequence 230 bytes from #14FC is identical to offset -768/#FD00 (estimation: 873)
Sequence 229 bytes from #12FB is identical to offset -256/#FF00 (estimation: 649)
Sequence 228 bytes from #11FC is identical to offset -256/#FF00 (estimation: 426)
Sequence 35 bytes from #1C8F is identical to offset -400/#FE70 (estimation: 396)
Sequence 27 bytes from #1C1D is identical to offset -1111/#FBA9 (estimation: 374)
Sequence 12 bytes from #1C6C is identical to offset -76/#FFB4 (estimation: 365)
Sequence 10 bytes from #1C3F is identical to offset -1096/#FBB8 (estimation: 360)
Sequence 7 bytes from #1C01 is identical to offset -4/#FFFC (estimation: 356)
Sequence 6 bytes from #11F1 is identical to offset -23/#FFE9 (estimation: 353)
Sequence 5 bytes from #1C0B is identical to offset -16/#FFF0 (estimation: 351)
Sequence 5 bytes from #1C17 is identical to offset -8/#FFF8 (estimation: 349)
Sequence 4 bytes from #1C5D is identical to offset -29/#FFE3 (estimation: 348)
Sequence 4 bytes from #1C63 is identical to offset -2/#FFFE (estimation: 347)
Sequence 4 bytes from #1C53 is identical to offset -8/#FFF8 (estimation: 346)
Sequence 4 bytes from #1CC5 is identical to offset -10/#FFF6 (estimation: 345)
Sequence 3 bytes from #1C39 is identical to offset -26/#FFE6 (estimation: 345)
Sequence 3 bytes from #1C7C is identical to offset -62/#FFC2 (estimation: 345)
Sequence 3 bytes from #12F2 is identical to offset -1/#FFFF (estimation: 345)
Sequence 3 bytes from #11EC is identical to offset -2/#FFFE (estimation: 345)
Sequence 3 bytes from #1C5A is identical to offset -2/#FFFE (estimation: 345)
Sequence 3 bytes from #12E6 is identical to offset -240/#FF10 (estimation: 345)
Number of commands: 29
Estimated compression: 2% (16384 -> 345)
Actual compression: 2% (16384 -> 345)

Block 2:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16383 bytes from #0001 is identical to offset -1/#FFFF (estimation: 6)
Number of commands: 1
Estimated compression: 0% (16384 -> 6)
Actual compression: 0% (16384 -> 6)

Block 3:
Cleaning 8388608 words...
Cleaning Ok
Reading 16384 bytes
Analysis...
Sequence 16183 bytes from #0001 is identical to offset -1/#FFFF (estimation: 206)
Sequence 7 bytes from #3F7F is identical to offset -8/#FFF8 (estimation: 202)
Sequence 7 bytes from #3FDE is identical to offset -16/#FFF0 (estimation: 198)
Sequence 6 bytes from #3FFA is identical to offset -48/#FFD0 (estimation: 195)
Sequence 6 bytes from #3FD5 is identical to offset -80/#FFB0 (estimation: 192)
Sequence 5 bytes from #3FB4 is identical to offset -56/#FFC8 (estimation: 190)
Sequence 5 bytes from #3F87 is identical to offset -32/#FFE0 (estimation: 188)
Sequence 5 bytes from #3FBC is identical to offset -40/#FFD8 (estimation: 186)
Sequence 5 bytes from #3FCC is identical to offset -40/#FFD8 (estimation: 184)
Sequence 5 bytes from #3F91 is identical to offset -55/#FFC9 (estimation: 182)
Sequence 4 bytes from #3FF3 is identical to offset -1/#FFFF (estimation: 181)
Sequence 4 bytes from #3FA5 is identical to offset -24/#FFE8 (estimation: 180)
Sequence 4 bytes from #3F8D is identical to offset -32/#FFE0 (estimation: 179)
Sequence 4 bytes from #3FE6 is identical to offset -32/#FFE0 (estimation: 178)
Sequence 4 bytes from #3FED is identical to offset -32/#FFE0 (estimation: 177)
Sequence 4 bytes from #3FC7 is identical to offset -64/#FFC0 (estimation: 176)
Sequence 4 bytes from #3FD1 is identical to offset -110/#FF92 (estimation: 175)
Sequence 3 bytes from #3F96 is identical to offset -56/#FFC8 (estimation: 175)
Sequence 3 bytes from #3FF7 is identical to offset -56/#FFC8 (estimation: 175)
Sequence 3 bytes from #3FAE is identical to offset -80/#FFB0 (estimation: 175)
Sequence 3 bytes from #3F9B is identical to offset -1/#FFFF (estimation: 175)
Sequence 3 bytes from #3F68 is identical to offset -16/#FFF0 (estimation: 175)
Sequence 3 bytes from #3FB1 is identical to offset -45/#FFD3 (estimation: 175)
Number of commands: 23
Estimated compression: 1% (16384 -> 175)
Actual compression: 1% (16384 -> 175)

0x00;68
0x01;13
0x02;14
0x03;12
0x04;17
0x05;10
0x06;4
0x07;3
0x08;6
0x09;2
0x0A;2
0x0B;1
0x0C;3
0x0D;1
0x0F;2
0x10;23
0x12;1
0x15;4
0x17;3
0x18;3
0x1A;1
0x1B;1
0x1C;6
0x1D;1
0x20;16
0x21;3
0x23;3
0x28;3
0x2D;1
0x30;3
0x31;1
0x33;1
0x37;2
0x38;12
0x3B;1
0x3C;22
0x3E;6
0x3F;2
0x40;20
0x42;28
0x44;17
0x46;1
0x48;2
0x4A;2
0x4B;1
0x4C;1
0x4D;1
0x4E;1
0x50;5
0x52;3
0x53;1
0x54;1
0x57;1
0x58;1
0x5A;1
0x5B;1
0x5C;8
0x62;1
0x66;1
0x6E;1
0x70;2
0x78;7
0x7C;6
0x7E;5
0x7F;1
0x80;3
0x81;1
0x92;1
0x99;1
0xA1;1
0xA8;2
0xA9;1
0xB4;1
0xB6;2
0xB8;1
0xB9;1
0xC4;2
0xCA;1
0xCB;1
0xCC;1
0xCE;1
0xDB;2
0xDF;1
0xE0;1
0xE1;1
0xE4;1
0xE5;1
0xE6;1
0xE7;1
0xEB;2
0xF0;1
0xF4;3
0xF9;1
0xFB;2
0xFC;1
0xFD;1
0xFE;2
0xFF;14
0x100;53

Good bye!


Хаффмановский калькулятор на это выдал вот такую табличку:
Code:
0x00   101
0x100   001
0x42   0110
0x10   11110
0x3C   11101
0x40   11100
0x44   11001
0x04   11000
0x20   01111
0xFF   01011
0x02   01010
0x01   01001
0x38   111111
0x03   111110
0x05   110111
0x5C   110100
0x78   010001
0x7C   010000
0x08   000111
0x3E   000101
0x1C   000100
0x7E   1101101
0x50   1101100
0x15   1101010
0x06   0111001
0x07   11010111
0x17   0001101
0x0C   0001100
0x52   0000111
0x30   0000110
0xF4   0000101
0x80   0000100
0x21   0000011
0x18   0000010
0x28   0000001
0x23   0000000
0xFE   11010110
0x37   10011111
0x0F   10011110
0x48   10011101
0x3F   10011100
0x0A   10011001
0x09   10011000
0xDB   10010111
0xC4   10010110
0xFB   10010101
0xEB   10010100
0x70   10010011
0x4A   10010010
0xB6   10010001
0xA8   10010000
0x0D   100110111
0x0B   100110110
0x1A   100110101
0x12   100110100
0x81   100011111
0x7F   100011110
0x99   100011101
0x92   100011100
0x62   100011011
0x5B   100011010
0x6E   100011001
0x66   100011000
0xCA   100010111
0xB9   100010110
0xCC   100010101
0xCB   100010100
0xA9   100010011
0xA1   100010010
0xB8   100010001
0xB4   100010000
0x3B   100001111
0x33   100001110
0x4B   100001101
0x46   100001100
0x1D   100001011
0x1B   100001010
0x31   100001001
0x2D   100001000
0x57   100000111
0x54   100000110
0x5A   100000101
0x58   100000100
0x4D   100000011
0x4C   100000010
0x53   100000001
0x4E   100000000
0xE5   011101111
0xE4   011101110
0xE7   011101101
0xE6   011101100
0xDF   011101011
0xCE   011101010
0xE1   011101001
0xE0   011101000
0xF9   011100011
0xF0   011100010
0xFD   011100001
0xFC   011100000


Что даёт 341 байт - даже больше, где мы остановились на 4-байтовых комбинациях...

_________________
:dj: https://mastodon.social/@Shaos


10 Oct 2013 19:04
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Итак с исправленным архиватором имеем (без Хаффмана):

zx48.sna - 0.5K
Code:
Estimated compression: 2% (16384 -> 345)
Estimated compression: 0% (16384 -> 6)
Estimated compression: 1% (16384 -> 175)


chess.sna - 10.5K
Code:
Estimated compression: 10% (16384 -> 1745)
Estimated compression: 51% (16384 -> 8508)
Estimated compression: 1% (16384 -> 227)


cybotron.sna - 6.1K
Code:
Estimated compression: 35% (16384 -> 5861)
Estimated compression: 0% (16384 -> 25)
Estimated compression: 1% (16384 -> 206)


Для примера захаффманим chess:
Code:
0x100   000
0x00   11000
0x03   10110
0x88   00110
0x04   00100
0x20   111100
0x05   111000
0x06   110010
0x01   101000
0xFE   100001
0x21   011110
0x08   011101
0xCD   011001
0x07   010111
0x3A   010010
0x32   010001
0x10   001010
0x28   1111011
0x02   1110110
0x18   1110010
0x23   1101100
0x40   1101011
0x3E   1010101
0x11   1010010
0xDD   1000110
0xCB   1000101
0xFF   1000001
0x09   1000000
0x0A   0111110
0xA7   0111000
0x38   0110111
0xC9   0110110
0x0F   0110001
0x0E   0110000
0x80   0101100
0x7E   0101010
0x89   0101000
0x30   0100110
0x44   0011110
0xC0   0010110
0xAF   11111110
0x0D   11111101
0x36   11101000
0x22   11011101
0x0B   11011100
0xF1   11011011
0x78   11011010
0x19   11010001
0x42   11001111
0x2C   11001110
0xF0   11001100
0x1F   10111111
0xED   10111101
0xF8   10111010
0xE1   10111001
0x12   10111000
0xFB   10101001
0xF5   10101000
0xE6   10100111
0xE0   10100110
0xB0   10011101
0xFD   10011010
0xC1   10011001
0x6F   10011000
0x2A   10010111
0x3C   10010110
0x77   10001110
0xC3   01110010
0x13   01101001
0xFC   01011010
0xE5   01010111
0x2B   01010110
0x1E   01010011
0xCA   01010010
0x50   01000010
0x4E   01000001
0x16   01000000
0xAE   00111110
0x2D   111111111
0x0C   111111110
0x34   00101110
0xC5   111110011
0x31   111110010
0xF6   111110000
0x14   111101011
0xEB   111101001
0x72   111101000
0xA9   111010101
0x3F   111010100
0x29   111010011
0x47   111010010
0x52   110111111
0x79   110111101
0x73   110111100
0x35   110101011
0x1C   110101010
0x65   110101001
0x49   110101000
0x15   110100101
0xD5   110011011
0xC6   110011010
0xBE   101111100
0x41   101111001
0x3D   101111000
0x6C   101110111
0x60   101110110
0x5F   101011111
0x33   101011110
0xC8   101011101
0xB2   101011100
0x24   101011001
0x1A   101011000
0x4F   100111111
0x43   100111110
0x57   100111101
0x53   100111100
0x17   100111001
0x7B   100110111
0x7A   100110110
0x87   100101011
0x74   100101010
0x96   100101001
0x93   100101000
0x37   100100111
0x56   100100101
0x4B   100100100
0xF3   100011111
0xD1   100011110
0xFA   100010010
0x2E   100010001
0x1B   100010000
0x62   011111111
0x45   011111110
0x83   011111101
0x63   011111100
0xF9   011100111
0xA8   011100110
0x51   011010111
0xF2   011010101
0x5E   011010100
0x70   010011111
0x61   010011110
0x92   010011101
0x8D   010011100
0xE7   010000111
0x9F   010000110
0x55   001111111
0xF4   001111110
0x39   001110111
0x2F   001110110
0x4A   001110101
0x46   001110100
0x9D   001011111
0x4C   001011110
0xB1   1111110011
0xA0   1111110010
0xB7   1111110001
0xB4   1111110000
0x7C   1111101111
0x75   1111101110
0x9C   1111101101
0x8E   1111101100
0x4D   1111101011
0x3B   1111101010
0x67   1111101001
0x58   1111101000
0xE8   1111100011
0xB8   1111100010
0xDA   1111010100
0x98   1110111111
0x94   1110111110
0xAB   1110111101
0xA6   1110111100
0x71   1110111011
0x69   1110111010
0x90   1110111001
0x8F   1110111000
0x5C   1110101101
0x48   1110101100
0xA1   1110011111
0x6E   1110011110
0xDB   1110011101
0xC2   1110011100
0x26   1110011011
0x1D   1110011010
0x68   1110011001
0x5B   1110011000
0xEF   1101111100
0x54   1101001111
0x27   1101001110
0x7F   1101001101
0x6D   1101001100
0xA3   1101000011
0x81   1101000010
0xEC   1101000001
0xCC   1101000000
0xAA   1010110111
0xA5   1010110110
0xF7   1010110101
0xAC   1010110100
0x5D   1001110001
0xD9   1001110000
0x91   1001000111
0x8A   1001000110
0xD0   1001000101
0x9B   1001000100
0x5A   1001000011
0x82   1001000001
0x76   1001000000
0xD6   1000100111
0xD3   1000100110
0x84   0110101101
0x66   0110101100
0x97   0110100011
0x86   0110100010
0x9A   0110100001
0x99   0110100000
0xEA   0101101111
0xE2   0101101110
0x25   0101101101
0xBD   0011100111
0xA4   0011100110
0xD8   0011100101
0xCE   0011100100
0x85   0011100011
0xA2   0011100001
0x95   0011100000
0xD2   11110101010
0xB6   11101011111
0x9E   11101011110
0xC4   11101011101
0xBA   11101011100
0x7D   11011111011
0xEE   11011111010
0x8C   11010010011
0x6B   11010010010
0xBC   11010010001
0xB3   11010010000
0xD7   10111110111
0xCF   10111110110
0xE4   10111110100
0xBB   10010011011
0xB5   10010011010
0xDE   10010011001
0xDC   10010011000
0x8B   10010000101
0x64   10010000100
0x59   01011011001
0xE3   111101010111
0xDF   111101010110
0xE9   01011011000
0xB9   00111000101
0xAD   101111101011
0x6A   1011111010101
0xC7   001110001001
0xBF   001110001000
0xD4   1011111010100

C Хаффиманом получается 8.9К, т.е. почти как ZIP

_________________
:dj: https://mastodon.social/@Shaos


10 Oct 2013 19:39
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
Итак с исправленным архиватором имеем (без Хаффмана):

zx48.sna - 0.5K
Code:
Estimated compression: 2% (16384 -> 345)
Estimated compression: 0% (16384 -> 6)
Estimated compression: 1% (16384 -> 175)


chess.sna - 10.5K
Code:
Estimated compression: 10% (16384 -> 1745)
Estimated compression: 51% (16384 -> 8508)
Estimated compression: 1% (16384 -> 227)


cybotron.sna - 6.1K
Code:
Estimated compression: 35% (16384 -> 5861)
Estimated compression: 0% (16384 -> 25)
Estimated compression: 1% (16384 -> 206)



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

zx48.sna (49K):
Code:
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:
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:
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:
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:
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:
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:
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 - он где-то лучше, а где-то хуже...

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 24 Oct 2013 05:51, edited 33 times in total.



11 Oct 2013 05:09
Profile WWW
Writer

Joined: 06 Sep 2007 07:05
Posts: 19
Location: 212.26.238.228
Reply with quote
Post 
А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.


12 Oct 2013 00:26
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
alone wrote:
А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.

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

_________________
:dj: https://mastodon.social/@Shaos


12 Oct 2013 01:05
Profile WWW
Writer

Joined: 06 Sep 2007 07:05
Posts: 19
Location: 212.26.238.228
Reply with quote
Post 
Оптимальный в том смысле, что из всех способов разбиения последовательности на литералы и ссылки выбирается самый оптимальный (идёт обсчёт всех путей, потом выбирается самый короткий).


12 Oct 2013 02:56
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Post 
У меня всегда выкусывается самая большая из оставшихся повторяющихся последовательностей - в этом смысле алгоритм "оптимален", однако представление информации, когда команда имеет в виде префикса целый байт #FF, не совсем годится для кодирования коротких последовательностей. Сейчас рассматриваю варианты "постобработки" без скатывания в побитовую алхимию (Хаффман и т.д.) - например после LZ77 (со "скользящим" окном) можно применить табличный LZ на оставшиеся непожатые данные, ищущий и кодирующий часто повторяющиеся "триады" (тройки байтов) одним байтом (для подстановки выбираются не встречающиеся или редко встречающиеся байты). Сейчас у меня задача любой SNA упаковывать в 32К (пока из тех что я пробую не уталкивается в 32К только файл tomahawk.sna).

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 13 Oct 2013 09:45, edited 3 times in total.



13 Oct 2013 08:29
Profile WWW
Writer

Joined: 06 Sep 2007 07:05
Posts: 19
Location: 212.26.238.228
Reply with quote
Post 
Самая большая - это не оптимальный алгоритм. Оптимальный учитывает и способ кодирования с точностью до бита. Это реально реализовано в 7zip и MegaLZ.


13 Oct 2013 08:45
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 117 posts ]  Go to page 1, 2, 3, 4, 5 ... 8  Next

Who is online

Users browsing this forum: No registered users and 11 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.