nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 12:42



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

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Два года уже прошло с момента написания последней версии архиватора - пора уже допилить уже...

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


28 Oct 2015 19:34
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Post Re:
А теперь уже больше трех лет прошло...

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

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

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

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


24 Jan 2017 19:48
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Post Re:
Shaos wrote:
Чего-то замотался я и окончательную сжимающе-разжимающую версию так и не выкатил - там осталось буквально на вечер-два работы...

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

github.com/shaos/shaff

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

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

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


29 Jan 2017 12:39
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Тут пока исследовал разные алгоритмы для сжатия 8086/8088 кода для суперкартриджа с 8 играми для IBM PCjr, попробовал разные архиваторы (и старые, и новые, и ретро-демо-сценерские) - заодно и свой SHAFF для сравнения :)

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

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

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

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

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


30 Jan 2017 23:18
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Shaos wrote:
https://github.com/shaos/shaff

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

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

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


SHAFF0 data format:

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

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


SHAFF1 data format:

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

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

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


31 Jan 2017 18:45
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Post Re:
Shaos wrote:
У меня ещё есть много мест для оптимизации т.к. сжимает SHAFFv1h оооочень долго :)
Code:
zx48.sna        2 min
zx48k1.sna      2 min
jswilly16k.sna 35 min
chess16k.sna   21 min
chess.sna      47 min
cybotron.sna   28 min
tomahawk.sna  158 min 
exolon.sna    141 min 
buzzsaw.sna    93 min
bozxle.sna    102 min

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

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

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


01 Feb 2017 11:42
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Shaos wrote:
Но я этим займусь потом - сначала надо выкатить работающую утилитку командной строки, которая может и сжимать, и разжимать...

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

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

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


02 Feb 2017 01:48
Profile WWW
Doomed

Joined: 08 Apr 2013 04:04
Posts: 449
Location: 213.247.249.139
Reply with quote
Shaos wrote:
zx48.sna 2 min
zx48k1.sna 2 min
jswilly16k.sna 35 min
chess16k.sna 21 min
chess.sna 47 min
cybotron.sna 28 min
tomahawk.sna 158 min
exolon.sna 141 min
buzzsaw.sna 93 min
bozxle.sna 102 min

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


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

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

_________________
привет засранцу лавру :)


02 Feb 2017 03:05
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Я старался :)

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

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

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

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


02 Feb 2017 06:33
Profile WWW
Doomed

Joined: 08 Apr 2013 04:04
Posts: 449
Location: 213.247.249.139
Reply with quote
Да я не об этом. Посмотри как-нибудь на досуге форматы того же megalzа или хруста. Там если нужно что-то кратное 8 битам -- оно сразу как байты выбирается из байтового потока, а если биты нужны -- они из битового, точнее из 8- или 16-битового сдвигателя, который по опустошению вновь засасывается из байтового потока.
Формы ссылок не меняются, меняется только их хранения в запакованном файле, а заодно ОЧЕНЬ ускоряется депак.

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

_________________
привет засранцу лавру :)


02 Feb 2017 06:55
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Получается что у MegaLZ команды всегда выровнены на границу байта? Это же ухудшает сжатие, нет? У меня только блоки выравниваются на границу байта (чтобы в перспективе можно было иметь аля произвольный доступ с шагом в 16К внутри архива ну и на многокоровых машинах можно параллельно и независимо блоки компрессировать - каждый блок всегда с начала байта начинается и добивается нулевыми битами в конце, чтобы добить до конца байта).

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

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


02 Feb 2017 08:27
Profile WWW
Doomed

Joined: 08 Apr 2013 04:04
Posts: 449
Location: 213.247.249.139
Reply with quote
Омг... ты тогда, что ли, в сорец депакера загляни (есть сишный).

_________________
привет засранцу лавру :)


02 Feb 2017 08:41
Profile
Doomed

Joined: 08 Apr 2013 04:04
Posts: 449
Location: 213.247.249.139
Reply with quote
Quote:
пока нету Хаффмана оно и так нормально

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

_________________
привет засранцу лавру :)


02 Feb 2017 08:42
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
angry_troll wrote:
Омг... ты тогда, что ли, в сорец депакера загляни (есть сишный).

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

angry_troll wrote:
Quote:
пока нету Хаффмана оно и так нормально

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

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

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


02 Feb 2017 10:12
Profile WWW
Doomed

Joined: 08 Apr 2013 04:04
Posts: 449
Location: 213.247.249.139
Reply with quote
depack_getbyte() vs depack_getbits()
и далее сам цикл распаковки

_________________
привет засранцу лавру :)


02 Feb 2017 10:49
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 117 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next

Who is online

Users browsing this forum: No registered users and 21 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.