Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Два года уже прошло с момента написания последней версии архиватора - пора уже допилить уже...
|
28 Oct 2015 19:34 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
А теперь уже больше трех лет прошло... Можно потом пойти дальше - отдельно кодируемые байты пожать Хаффманом и назвать это SHAFFv2 P.S. Тогда до кучи и оптимальный выбор цепочек можно сделать...
|
24 Jan 2017 19:48 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Создал прожэкт на GitHub - залью туда все версии одну за другой, чтобы можно было видеть диффы между ними по коду: github.com/shaos/shaff Ну и окончательную доводку кода буду уже туда выкладывать... P.S. В июне 2018 года репа переехала на гитлаб: https://gitlab.com/shaos/shaff
|
29 Jan 2017 12:39 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Тут пока исследовал разные алгоритмы для сжатия 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 года http://fileformats.archiveteam.org/wiki/HAP.P.S. Прикинул, что если пожму литералы Хоффманом (SHAFF2), то смогу опуститься до 87K - т.е. обогнать LHA и подобраться вплотную к bzip2, но похоже не смогу догнать LZ4 и RNC Pro Pack (method 1) - их сможет попытаться сделать только SHAFF3
|
30 Jan 2017 23:18 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Выложил (пока в разобранном состоянии) и заодно поподробнее расписал формат SHAFFv1h:
|
31 Jan 2017 18:45 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Я похоже знаю как примерно на порядок ускорить алгоритм сжатия через кеширование промежуточных результатов сканирования автокорреляционной матрицы Но я этим займусь потом - сначала надо выкатить работающую утилитку командной строки, которая может и сжимать, и разжимать...
|
01 Feb 2017 11:42 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Доделал до уровня, когда запаковывается файл в формате SHAFF0 (байтовый поток), но распаковщика пока нету - завтра напишу... P.S. Пока сжимаю всякие файлы, с какими раньше игрался - пока вроде более-менее сходится, например zx48k1.sna (образ памяти с бейсик программкой из одной строки) сжался в 590 байт
|
02 Feb 2017 01:48 |
|
|
angry_troll
Doomed
Joined: 08 Apr 2013 04:04 Posts: 449 Location: 213.247.249.139
|
НАСТОЛЬКО медленно сделать сжатие -- это надо уметь! Интересно, если взять файл и инвертировать все 7ые биты всех байтов -- размер наверное изменится... Кстати, если в твоих xxxxxxxxxxxx выделить байт(ы) и брать его из байтового потока, а не одного только битового -- депакер чуть ускорится. Хотя видно, что под байтовый поток формат не оптимизировался.
_________________ привет засранцу лавру :)
|
02 Feb 2017 03:05 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Я старался SHAFF0 - байтовый поток SHAFF1 - битовый поток (без Хаффмана) будет ещё SHAFF2 - битовый поток с Хаффманом для литералов...
|
02 Feb 2017 06:33 |
|
|
angry_troll
Doomed
Joined: 08 Apr 2013 04:04 Posts: 449 Location: 213.247.249.139
|
Да я не об этом. Посмотри как-нибудь на досуге форматы того же megalzа или хруста. Там если нужно что-то кратное 8 битам -- оно сразу как байты выбирается из байтового потока, а если биты нужны -- они из битового, точнее из 8- или 16-битового сдвигателя, который по опустошению вновь засасывается из байтового потока. Формы ссылок не меняются, меняется только их хранения в запакованном файле, а заодно ОЧЕНЬ ускоряется депак. кстати, а у тебя сейчас оптимальное кодирование или нет?
_________________ привет засранцу лавру :)
|
02 Feb 2017 06:55 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
Получается что у MegaLZ команды всегда выровнены на границу байта? Это же ухудшает сжатие, нет? У меня только блоки выравниваются на границу байта (чтобы в перспективе можно было иметь аля произвольный доступ с шагом в 16К внутри архива ну и на многокоровых машинах можно параллельно и независимо блоки компрессировать - каждый блок всегда с начала байта начинается и добивается нулевыми битами в конце, чтобы добить до конца байта).
У меня не оптимальный алгоритм (в смысле выстраивания цепочек с конца и выбора самого компактоного пути), а жадный (на каждом шаге откусывается самый большой доступный кусок независимо от его местоположения) - пока нету Хаффмана оно и так нормально т.к. у меня в подавляющем большинстве случаев компрессия большого куска будет компактнее нежели компрессия состоставляющих его подмножеств...
|
02 Feb 2017 08:27 |
|
|
angry_troll
Doomed
Joined: 08 Apr 2013 04:04 Posts: 449 Location: 213.247.249.139
|
Омг... ты тогда, что ли, в сорец депакера загляни (есть сишный).
_________________ привет засранцу лавру :)
|
02 Feb 2017 08:41 |
|
|
angry_troll
Doomed
Joined: 08 Apr 2013 04:04 Posts: 449 Location: 213.247.249.139
|
А как ты собрался делать полностью оптимальное кодирование с хафманом, интересно? Как ты будешь при оценке ссылок учитывать, во что они пережмутся хафманом?
_________________ привет засранцу лавру :)
|
02 Feb 2017 08:42 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22607 Location: Silicon Valley
|
а я чего-то сишного декодера не встречал, только Z80 - а вообще ведь mhmt тот же умеет декодить? поглядел - ничо не понял, вроде читает пословно из какого-то wrk.indata[position++], но как оно превращается в биты то? ведь судя по описанию формата мегалз именно с битами работает т.к. команды явно не кратной 8-битам длинной все... ну будет с каким-то допуском оптимальное хаффмана можно по ходу дела пересчитывать, в какой-то момент остановившись...
|
02 Feb 2017 10:12 |
|
|
angry_troll
Doomed
Joined: 08 Apr 2013 04:04 Posts: 449 Location: 213.247.249.139
|
depack_getbyte() vs depack_getbits() и далее сам цикл распаковки
_________________ привет засранцу лавру :)
|
02 Feb 2017 10:49 |
|
|