Компрессия
Alone Coder
Первые компрессоры графики на Speccy
были, наверно, в Screen Machine by Joe
Gillespie(5'84) и в комплекте The Artist
I(6'85). Возможно, была ещё более старая
программа,но от неё не сохранилось ничего,
кроме названия - Fill-Compressor by Base
Two Software(1983).
Но в фирменных играх результат работы
экранных компрессоров мне не попадался.
Первый известный спектрумовский комп─
рессор текста (токенами)- Text Compression
System, опубликованный в виде листинга в
сентябре1984. Такие системы использова─
лись в некоторых текстовых адвентюрах.
В80-х были и программы непонятного
происхождения (из Восточной Европы?), нап─
ример,какой-то странный древний компрессор
экранов с4 методами - COMPRES+.
Потом пошли отечественные разработки:
- компрессор Балясова COMPRESS (1990,
Москва)
- ZX ARC(CoCo, Compressor v1.01 - 1991,
Mike Studio S.Peterburg 1782908)
- ASC packer Сендецкого(1991, Львов)
Исторически на Speccy (уже в первой ре─
кламе Screen Machine ) сжатие файлов назы─
ваетсякомпрессией (to compress),а не упа─
ковкой илиархивацией. Но слово "упаковка"
прижилось на постсоветском пространстве.
На C64 известен упаковщик с депакером
1986 года Cruncherhttp://csdb.dk/release/
?id=19112 (возможно, были и древнее). Тут
видна другая традиция наименования,которая
отразилась и на Амиге.
Самые популярные отечественные компрес─
соры разобраны в Inferno Guide #5. Основ─
ное семейство использует LZ77 (см. Info
Guide #7) с кодированием параметров чем-то
типаGamma Code или Elias Delta Code, что─
бы короткие числа занимали меньше бит.Т.к.
хранить ни деревья, ни таблицы не надо, а
распаковку обычно ведут прямо поверх упа─
кованного файла, дополнительная память та─
ким декомпрессорам не требуется. История
спектрумовских компрессоров почти закончи─
лась с появлением небольшого семейства
компрессоров с кодомХаффмана (RIP, mRIP,
ZXRar), дальше обычно просто брали готовые
разработки с других платформ. Арифметичес─
кое кодирование (см. пример в Info Guide
#6) оказалось слишком медленным для Z80.
Но спектрумовские компрессоры всё ещё
можно улучшить. Можно начинать с развития
кроссплатформенных компрессоров, тем более
что жадные методики легче реализовать там.
В этом случае задача стоит в основном в
разработке хорошего распаковщика.
В этой статье я перечислю идеи, кото─
рые всплывали в долгих обсуждениях на
irc.forestnet.org #mhm с lvd, hrumer'ом,
jtn'ом и другими.
1. Optimal LZ (см. Info Guide #6)
Для форматов MegaLZ и Hrum реализовано
в mhmt. Для Хаффмана всё сложнее - поэтому
в RIP и ZXRar два пресета - для текста и
кодов, плюс тонкие настройки в ZXRar/mRIP.
Сделать бы оптимальный mRIP - для одно─
го блока долго не понадобятся новые пакеры
в жанре "медленная распаковка с буфером".
lvd>памяти надо N*размер файла (где N=50
..100), быстродействие нужно M*ГГц, где M
неизвестно) не зря я обещал ящик кока-колы
тому, кто на спеке получит такой же размер
в мегалзе, как на пц мой пакер.
lvd>как должен выглядеть оптимальный LZH
для пост-хаффмана?перед кодированием имеем
список всех ссылок на КАЖДЫЙ байт. для LZH
рисуем цены каждой и сзаду наперёд строим
путь,а спереду назад его кодируем в выход.
для Хаффмана - кодируем им выход LZH.
alone> сначала пакуем, чтобы узнать длины
кодов, потом перепаковываем с учётом этой
статистики. можно много раз. а цены те же.
lvd>то есть строим опт. LZH, кодируем
Хаффманом,потом перестраиваем LZH с учётом
новых цен? а где гарантия, что такое
сойдётся к оптимуму?
alone> нет гарантии.
lvd>и ещё, не каждая из всех ссылок может
в Хаффмана попасть. вот ты составил список
всех ссылок, а потом оптимальный путь. и у
тебя в выход попадают не все ссылки из
всех возможных! потому Хаффман назначит
новую цену токо тем,что на него свалились.
alone> дай не попавшим фальшивую длину 15.
иначе не сможешь следующий проход пройти.
Это нормальный штраф.на последнем проходе,
естественно, все непопавшие исключаются.
lvd>если они непопавшие,это не значит,что
за них штраф. вдруг если перетасовать
ссылки с учётом новых цен, вылезут много
повторяющихся других, а ты их штрапом.
alone> ну, 15 даст им шанс. а 255 не даст.
можно медианный фильтр по длинам ссылок
прогнать. если, например, 5 и 7 юзались, а
6 нет, то ей назначится та же длина кода.
lvd>а может, Хаффмана построить по всем
вообще ссылкам, которые на каждый байт, и
по резалтам назначить цену.потом опт,потом
перехаффман и коррекция цен. и так далее.
lvd>hrumer: а есть что-то типа Дейкстры
для LZ+Хаффман? или даже LZ+ексомайзер?
hrumer> Да наверняка есть. Кажется, ещё
круче есть,в 2014 году zip чуток улучшили,
подзабыл, как алгоритм называется. Формат
зипа остаётся. Но времени раз в 10 больше
надо.Екзомайзер уже внутри имеет LZ.А если
ты про то, есть ли в нём оптимальное коди─
рование для вычисленных кодов Хаффмана -
думаю,что есть. А вот хитро ли подбираются
коды Хаффмана или нет - я даже не пред─
положу. Надо исходники ковырять.
lvd>а там точно Хаффман? я депакер зырил,
там что-то типа фикс номер из потока
выбирается,лукап в таблице, из неё ссылка.
кол-во разных ссылок ограничено таблицей.
оптимальное кодирование есть на 100%
только для голого LZ. а в случае Хаффман
овер LZ? неужто надо запоминать все ссылки
для всех позиций, чтоб опт. хф+LZ потом
строить? так никаких гигабайтов не хватит.
hrumer> Насколько помню, там отдельно коды
Хаффмана для дистанций длины 2 и дистанций
больше длины 2. Для символов коды Хаффмана
не используются. И хитро, а скорее всего
стандартно канонически, упакованы деревья
типа табличек,по которым эти коды Хаффмана
декодируют.Там коды Хаффмана для длин ещё.
lvd>ну, то есть, он эвристику изобрёл
какую-то или решил проблему подбора
оптимального сжатия в случае хф овер LZ?
hrumer> Как я понял, второе. Но полностью
оптимальное или нет - не знаю. Видимо, с
каким-то приближением к оптимальному. А
может,просто перебор с несколькими
итерациями. Нашёл:http://dml.compkaluga.
ru/forum/index.php?showtopic=74084
hrumer> а кто такой Роман Петров? автор
рипа первого? круто же товарищ сделал RIP!
alx_bw>RIP Packer от Романа Петрова.
отсюда из Йошки.
alone> mRIP пакует обычно лучше RIP'а, и
депакер влезает в бейсик. Формат от RIP'а,
но упрощён.Алгоритм из ZXRar.В mRIP'е юза─
ется стратегия упаковки lazy evaluation, а
в RIP'е нет. Это когда не ставится ссылка,
если выгоднее поставить символ и другую
ссылку. Результаты по глюксервису: на трёх
блоках суммой 18К mRIP выиграл 17 байт.
alx_bw>а максимальная длина блока какая?
#a000 умеет?
alone> #8800,наверно.Там сделано по живому
из ZXRar'а. Это для версии с оболочкой,а в
версии из автосборщика всё зависит от
всего. Ибо результат поверх пишется.
alx_bw>потому как такие блоки я предвари─
тельно жму своей RLE.грубо говоря,оно жмёт
одинаковые байты.таблицу прерываний ту же,
если не инициализится, а уже готовая.
Роман Петров>
Я разрабатывал этот упаковщик в школь─
ные годы,а затем после поступления в ВУЗ у
меня не было возможности им заниматься, и
я передал исходники Петрову Роману, моему
тёзке и хорошему знакомому.
alone>
А ходили слухи,что это дипломная работа
8) Если не секрет, как разрабатывался фор─
мат? Почему оказалось так похоже на Rar?
Роман Петров>
Да уж, хотя дипломной работой это и не
было,думаю,на диплом бы там вполне хватило
- учитывая то, какие дипломы сейчас пишут
на специальностях,обучающих программирова─
нию :) Формат никак,собственно,не разраба─
тывался: учась в школе и освоив Z80 и ас─
семблер, я уж не помню с чего вдруг решил
разработать упаковщик данных - и, конечно
же,он должен был стать самым эффективным:)
В начале разработки вообще ничего не
знал об алгоритмах сжатия, прочитал уж не
помню где о Lempel-Ziv,начал разрабатывать
свой паковщик.О кодах переменной длины то─
же ничего не знал, подсмотрел, вроде,как у
HRUST'а сделано,начал придумывать свои ко─
ды. Когда уже в интернете, которого тогда
было мало, узнал про коды Хаффмана - заго─
релся, конечно, реализовал.
Вообще я буквально жил этим "проектом"
(в школе я,конечно,не знал,что такое прог─
раммный проект). Ночами, на уроках,в любое
свободное время искал новые решения, думал
над улучшениями качества/скорости сжатия.
Каждое улучшение было настоящей победой :)
Думаю, таких энтузиастов среди спектрумис─
тов было немало. Вообще я искал путь напи─
сать идеальный упаковщик, что, как сейчас
уже понимаю,вряд ли возможно. Одной из са─
мых интересных частей проекта был,конечно,
распаковщик, его оптимизация по размеру и
скорости, битва шла за каждый байт и такт
процессора,в основном за байты,т.к.я хотел
уместить его в 256(?) байт (сколько там
нужно было для бейсик-блока). Задачу так и
не решил, но бился над ней много :)
Насчёт похожести на формат RAR - даже
не знаю, почему так вышло:) Скорее всего,
совпадение:) Я,конечно,на последних этапах
разработки, получив какой-никакой доступ в
интернет,с жадностью добывал информацию,но
не помню, чтобы я использовал формат RAR -
вроде бы,тогда он ещё не был опубликован.
Позже почитал про арифметическое коди─
рование, BWT, было интересно, но до реали─
зации этих алгоритмов руки так и не дошли
- поступил в вуз, пересел на ненавистный
всем спектрумистам писи :) Была ещё пара
интересных программ, мною разработанных,
но которые так никто и не увидел:
- программа копирования защищённых дис─
кет. в последнее время дискеты стали защи─
щать, я поставил себе задачу написать уни─
версальный копировщик, который просто счи─
тывает всю информацию с дискеты, включая
межсекторную,и копирует. Такую программу я
написал, всё работало вполне неплохо, даже
учитывая глючность контроллера дисковода
(ВГ93). Но нашёлся серьёзный глюк в конт─
роллере, 41-ю дорожку он упорно считывал с
ошибками, тестировал на разных компах.
Т.е. копирование диска полностью станови─
лось невозможным, тут я ничего сделать не
смог, забросил проект.
- загрузчик - не знаю, как они называют─
ся, обычно на дисках с играми были такие
для быстрой загрузки игры (курсор + меню).
Как это принято, 7 секторов, ну, и макси─
мум функционала и быстродействия туда пос─
тарался уместить, в целом был лучше всех
распространённых, виденных мной.
Вообще для меня это было время, когда я
программировал с наибольшей эффективнос─
тью, работая сейчас, эффективность ниже,
наверное, раз в 5-10.
В настоящее время у меня нет исходников
RIP'a, а мне было бы интересно взгянуть на
них, поностальгировать и посмотреть, как я
кодил, будучи в школе :)
alone>
Я пытался связаться с Megus'ом. Исход─
ники он не распространял. Himik's ZxZ де─
компилировал программу и выпустил несколь─
ко версий.Вот эти декомпилированные исход─
ники:http://opensourcezx.untergrund.net/
c_soft-packer-rip_src.html
Я декомпилировал ZXUnRar, который за─
бросил AIG, и некоторое время развивал
программу.Потом у меня сломался PC и стало
неоткуда брать архивы для тестирования. Я
написал сначала генератор архивов без упа─
ковки, потом с упаковкой (ZXRar). Чтобы
программа занимала как можно меньше (чтобы
пцшники завидовали:)),я её решил упаковать
RIP'ом. Но у него распаковщик не умещался
в бейсик-блок. Поэтому я немного упростил
формат и сделал свой RIP (mRIP) из того же
ZXRar, при этом оказалось, что форматы RIP
и Rar мало чем отличаются. Этот mRIP я за─
релизил в качестве исходника-автосборщика
программ (он есть здесь:http://
alonecoder.nedopc.com/zx/SYS.rar ) - его
надо INCLUDE'ить к своим программам, и он
сам их упакует,приклеит бейсик-загрузчик и
запишет на диск.Ещё есть версия mRIP прос─
то для упаковки отдельных файлов. Она тоже
есть на том диске. Её исходники в журнале:
alonecoder.nedopc.com/zx/books/IG10.rar
Роман Петров>
Странно, что RIP развивался таким обра─
зом, так-то я передал исходники Megus'у и
думал, что он отдаст их всем на пользова─
ние. Странно, кстати,что на Спектруме тема
Open Source не продвинулось,там ведь очень
сплочённое community было и практически
никаких рынков и бизнеса :)
alone>
Для настоящего RIP'а я ковырял распако─
вщик (сократил его на сколько-то байт).
Роман Петров>
Это круто! Для меня каждый байт там был
на счету, я чуть голову не сломал, пытаясь
впихнуть его в 256 байт :)
2. Опора на внешние данные
При упаковке можно использовать данные
распаковщика - подцеплять его слева к фай─
лу.Юзабельно для 4К интро.Данные ПЗУ лучше
не использовать - бывает разное. Релизовал
lvd в mhmt в2013 году.Пока не релизилось.
Эта идея применима и для сжатия текстов
любыми методами, вплоть доPPMd - при упа─
ковке приклеить слева типичную "Войну и
мир",а при распаковке привести распаковщик
в состояние после её распаковки.Может ока─
заться выгодным просто распаковать её ко─
пию. Евгений Рошал в курсе :) Просто для
универсального UnRar в этом мало смысла.
hrumer> словарь в виде депакера. круто:)
alone> для кодов самое то )
hrumer> если сам депакер паковать,то ваще
все ахнут от степени сжатия.
alone> рекурсивно? )
hrumer> ага. впрочем,там всегда на примере
RLE - LZ рекурсивен.
3. Использовать тонкости ОС
Для sizecoding можно использовать в ра─
спаковщике состояние памяти и регистров в
момент запуска файла,учесть адрес запуска,
имя файла и т.п. Можно также генерировать
бейсик-загрузчик с кодом внутри номера и
длины строки,неиспользуемой части чисел...
lvd>я когда 4к на омиге писал,тоже мудрил
с екзешником. т.е.брал екзешник непакован─
ный и мудрил с секциями амижными. чтобы,
например, выделение всей памяти было
описано в секциях. дата и код были в одной
секции,но указанный размер был дата+код, а
кода в ехе было мало.
crinkler is navigating inside internal
windows process structure in order to
directly get the address of the functions
from the in-memory import table.
ну вот, в виндоз 8 (9,10) не заработает.
4. Автоподбор метода
hrumer> пока делал оптимизацию
дехруста, я,на каком то этапе рассматривая
3 варианта кодирования, всё же один на
потом оставил и забыл про него.Из-за этого
у хруста могло быть сжатие лучше.
lvd>а вообще твои пакеры опирались на
какие-нибудь теор. исследования?
hrumer> если у тебя есть возможность упра─
влять форматом сохраненных данных,то наво─
ротить можно кучу. вот и наворотил. взял
десяток игрушек,которые нравились мне,и на
них тестил, что лучше работает,а что хуже.
hrumer> нашёл знатный фейл в хрусте1. там
много чего неиспользованного, но то, что
нашёл где-то полгода назад - это айяйяй.:)
alone> может, в mhmt исправлено? )
hrumer> в mhmt это частично исправлено,
коды наверняка юзаются, но главное - это
проблема формата, а в оригинальном хрусте1
в одной из веток коды сохраняются в виде 4
бит,т.е.1-16,а используются только 9-16.:)
ну, и в хрусте до кучи неиспользуемых
кодов...но это-то я знаю,а вот про то, что
глюканул и не проверил кое-чего, это да...
т.е. ё-мое, 1 бит экономим. а сколько раз
встречается такая штука..наверное,много...
надо хоть версию, где подсчет этой фигни
ведётся. на сколько байт получился промах.
alone> надо ещё сделать вторую версию
пакера и депакера - для распаковки задом
наперёд. и выбирать ту, которая выгоднее.
hrumer> ага, читал извраты металбрайна и
товарищей на примере exomizer2.
alone> насчёт оптимизации под пакер - я
одно время код оптимизировал под пакер.
вместо циклов дупы, а процедур - макросы.
hrumer> + Рощин еще написал статью про то,
что любят пакеры.
lvd>если взять 2 файла разных (например,
код и графику), то ехомизер по отдельности
их сожмёт лучше, чем если как один жать.
alone> В mRIP'е тоже так будет.
lvd>софт не обязательно должен быть
многопоточный. просто его надо запустить
одновременно 10 штук. или 100. распарал─
лелить проще простого - каждый цпу ищет
совпадения в своём куске файла. потом надо
только склеить то, что они напонаходили.
5. Настройка распаковщика под файл
Например,в компрессоре PuCrunch эскейп-
коды настраиваются под файл (и могут меня─
ться на лету), а коды для заполненияRLE
берутся из таблицы (16(?) отсортированных
по частоте значений) - см.http://www.
ffd2.com/fridge/chacking/c=hacking17.txt
Этот принцип можно применить и для упа─
ковки кодов команд (сейчас они обычно хра─
нятся как байты).
Для статистики, самые частые коды в ПЗУ
48K Бейсика (при его эмуляции):exx (6%),
call (4.7%),jr z (5.6%),jr nz (3.5%), пре─
фиксed (5.5%), префикс cb (5.4%), префикс
дляiy (4.8%) - в сумме 35%. Можно предус─
мотреть несколько контекстов 4-битных ко─
манд.Например,где-то надо многоld (hl),n:
inc hl, а где-то многоcall nn:ld (nn),hl.
alone> Ты ещё не экспериментировал с
короткими байтами?
hrumer> не. но думаю заняться ночным
кодингом :)
alone> Я вот думаю:все пакеры пакуют файл
подряд. А можно ли выиграть, если паковать
в каком-то сложном порядке? Типа как
картинку рисуют во всяких хоббитах.
hrumer> накладные расходы появятся. но
должны окупиться. но сложность возрастет.
была мысль, да впрочем она реализована -
паковать экран. при распаковке не распако─
вывать нули :)
alone> Ещё чисто для сжатия кода старая
идея - отделять команды от данных, хоть
грубо. Было несколько идей:
А) честно смотреть длину команд - это
160 байт кода примерно.
Б) сделать в пакере правила, по которым
можно будет подгонять код.
В) ловить данные только в командах ld.
С LZ надо 2 потока каждый со своей адреса─
цией,которые потом склеивать.Но если будут
правила, по которым можно будет подгонять
код, то,может,и с общей адресацией выйдет.
Параметры jr, кстати, сильно отличаются по
распределению от параметров ld. Jp/call -
тоже своё, причём младший байт рандомный,
а старший коррелирует со старшим байтом
адреса и старшим байтом прошлого jp/call.
Младший байт можно сделать, чтобы делился
на 4, например. Руками.
hrumer> вот из-за этого в хрусте появился
"вставной байт". На PC, как я понял, в бо─
льшинстве случаев не заморачиваются,просто
относительную адресацию заменяют на пря─
мую, а потом после распаковки,видимо,обра─
тно. остальное замудрённо реализовывать.
из реальных вариантов тока сброс окна при
смене кода/графики/текста с #4000 до,
например, #100 с последующим возрастанием.
alone> Ещё идея - считать на каждом байте
эвристику (допустим, 4 бита), лезть по ней
в массив и брать оттуда данные коротким
кодом. Можно ещё обновлять на лету.
LeafS874> По скрипту - есть мысль сделать
команду callmacro n,где n - номер макроса.
И в макросе одна команда или несколько,
можно читать параметры. Их будет немного.
Так можно и все команды описать, но тогда
надо Хаффманом кодировать - будет жырный
интерпретатор.По уму компилятор должен сам
найти статистику команд и выбрать для них
длины кодов. Как пакер.
Ещё интересное наблюдение - много call
идёт непосредственно после следующего ret.
Вызов непосредственно примыкающей подпрог─
раммы,а остальные сделать с отн. адресом с
расширяемым кодом. Можно все команды скри─
пта сделать через callmacro, тогда n надо
кодировать Хаффманом (код может подобрать
компилятор).По сути упакованная программа,
но при этом исполняемая!
hrumer> LeafS874: Alone, я тебя уже узнаю
по почерку! )
LeafS874> Выравнивание на байт надо только
для целых процедур. Макросы с параметрами
можно через call interpreter_getNbits.
Походу достаточно всего около 20 универса─
льных макросов, как в пи-коде у компилято─
ров.Обращение к переменным в скрипте деше─
вле,чем в машкоде - нужен только их номер,
а не адрес. 7 бит может хватить для прог─
раммы типа ACEdit'а.Их номера,конечно,тоже
можно Хаффманом,но где-то надо таблицу ) А
по поводу упаковки ещё есть идея:разделять
команды и данные. Но чтобы не искать, где
что, самим депакером, можно кодировать их
в самом коде. Например,выравниваем все
команды на 4 байта.
0 0 0 кмд - однобайтная команда
0 0 кмд парам - команда с 1-байтным
параметром или 2-байтная
0 кмд парам парам - понятно
Кмд кмд кмд кмд - 4-байтная
Смещения будут делиться на 4. Два бита
срезаем. Генерить такой код можно любым
макроассемблером. Для 4-байтной может быть
лучше разбирать как кмд кмд парам кмд.
hrumer> Извращенная идея! ) Рабочая. )
hrumer> коды для длин не все брать, а, на─
пример,исключить нечётные длины 7,9,11,13,
и тому подобное.сэкономим 1 бит на кодиро─
вании длин 6,8,10,12.в 50% случаев без на─
кладок,а с учетом оптимального кодирования
будет не 50% без накладок, а выше, до 80%.
а оставшиеся 20% или на самотёк пустить,
или сделать repeat distance для длины в 1.
hrumer> lvd: я смотрел exomizer. хорошо
придумано с деревьями, с распаковщиком.
Автор может ещё выпустить версию 3,возьмёт
и введёт код, который отвечает за
обновление деревьев :)
lvd>я в депакере увидел заполнение
таблички, из которой потом выбираются
смещения. это и есть те самые деревья?
hrumer> ага, я их деревьями называю.
таблички и есть.
alone> какой сам принцип екзомизера?
hrumer> экзомизер - деревья только для
длин и смещений. вся хитрость в пакере,
который пытается вычсчитать оптимальные
деревья, а потом оптимально закодировать.
я внутри пакера экзомизера не копался,
но в депакере все уши торчат :)
alone> У меня была идея пересчитывать
литералы по табличке в сортированные по
частоте,а потом битовые длины делать через
код.Можно несколько вариантов такого кода.
Это не Хаффман,но всё равно круто, и всего
256 байт на дерево.
lvd>ну вот ехомизер так и делает, видимо.
или похоже как-то.
lvd>а zx7? говорят, жмёт круче ехомизера.
hrumer> zx7, вроде, обычный, особенность в
том,что смещение длиной до 128 байт короче
кодируется.+ пакер оптимальные пары ищет.
hrumer> Alone, crinkler смотрел? :)
alone> а что там?
hrumer> а там..а у меня неругательных слов
нет, что там.
alone> он вообще хорошо пакует?
hrumer> Хорошо пакует. на 4к демы
рассчитан. на уровне линковки, что ли,
подбирается,где что хранить.при распаковке
тучу памяти использует. депакер короткий.
это то,что я помню. пару лет назад смотрел
подробнее. но там взрыв мозга. будешь
заглядывать - крепись :)
alone> использовать память при 4к логично.
там можно и LZ78 сделать.
alone> кстати, ты не разбирался с LZMA?
hrumer> LZMA - не, но так, читал слегка.
Там какой то буржуй в своем блоге офигевал
от хитростей, которые там есть. там пара
хитростей,а потом какое то умопомрачитель─
ное еще и дожатие... атас... лови ссылку:
http://cbloomrants.blogspot.ru/
2010/08/08-20-10-deobfuscating-lzma.html
lvd>есть одна задачка. для хруста есть 2
депукера. один быстрый, но через стек (поп
хл данные выбирает). другой медленный, но
без стека.медленный аж настолько,что выби─
рает из IX.сделан заменой поп хл на загру─
зку hl из ix.ну так вот.вместо pop hl надо
приделать ld a,[hl]:inc hl. намётки были
(в svn есть),но упёрлось в сохранение фла─
гов овер длинных кусков кода.благо МОЙ па─
кер позволяет менять формат таким макаром
:) вместо 16-битных наборов битов делать
8-битные. двойной профит - быстрый и
бесстековый депакер хруста выйдет.
6. Упаковщик для листалок
При упаковке текста для использования в
листалке нет смысла загонять буквы в4 би─
та (в5 бит было в листалке ZX Time ). Вы─
годнее кодировать слоги (или моры соглас─
ная-гласная) одним числом (это может быть
больше, чем байт) и сжимать Хаффманом.
jtn> я в з80-6 делал токены двухбуквенные.
считал все и сортировал.
alone> у тебя депакинг в реалтайме?
jtn> да. там рле+токены в реалтайме.
alone> и сильно жмёт?
jtn> процентов 30, если не вру.
alone> у мну Хаффман реалтаймовый сжал
146К в 97К. ZX-Guide #3 "Понедельник-2".
jtn> так там скролл почти фреймовый.
alone> у меня совсем фреймовый. 23 строки.
jtn> как ты Хаффман в рилтайме разожмёшь?
alone> там у меня длина Хаффмана
ограничена 8 битами.
jtn> ну,значит,зачот.у мну без подзагрузок
+ 2 фонта. 4х8 и пропорциональный
(сдвинутый 8 раз). и всё в 128к. текста
вроде чистого около 70к.
alone> нефреймово можно и 200К, я
когда-то считал. но это всё 128-е времена.
Ещё вариант: Fast Recursive Coding
Based on Grouping of Symbolshttp://arxiv.
org/ftp/arxiv/papers/0708/0708.2893.pdf
7. Расширяемые коды ссылок
Можно сужать и расширять коды ссылок
в разных местах файла. Один пример был в
Hrust1, но варианты неисчислимы.
hrumer> у меня была идея делать коды для
смещений и длин разной длины, но с ограни─
чением на то,что их длины возрастают,и ак─
куратно использовать в депакере(+обновлять
по мере продвижения по файлу).но я не смог
написать компактной реализации на z80 :(
alone> я писал упаковку звука по методу
DAKX, сжимает иногда раза в два.
но для кода неизвестно что будет.
hrumer> я вот чёт не до конца въехал
насчёт DAKX. это типа просто кодируем
число,и чем больше число,тем больше битов?
1 - %1. 2 - %10, 3 - 110. и т.д.
а последнее число все единицы. так?
alone> нет,там хранится текущая ширина ко─
да,она обновляется в зависимости от числа.
если идут маленькие числа - сужаем код,ес─
ли большие - расширяем:http://alonecoder.
nedopc.com/zx/books/zxgЧhtml/dakx.htm
это можно применить и для ссылок в LZ!
hrumer> скинул себе, буду осмысливать.
я, кстати, параллельно над лазекомпактом
голову ломаю. есть ли короткое исполнение
на z80 таких кодов: 0,1x0,1x1x0,1x1x1xx
(как в LCS) но! при урезании длины кода до
1,2,3,4,5,6,7 бит.
alone> такого не видел.
hrumer> в LC можно отлично выиграть на
этом. но короткая реализация такого - это
надо голову ломать.
alone> Можно ли выиграть, если все метки и
переходы будут по чётным адресам?
hrumer> не, ковыряю и собираю статистику
по Бурнашевскому сишному hrumЗ.5. смотрел,
длины как распределяются. на некоторых
файлах при только чётных длинах от 6 можно
выиграть. но сколько - пока не посчитал.
с длинами = 1 тоже всё зависит от файла.
на некоторых можно выиграть, если длину
брать макисимум = 4, а не 8.
alone> А можно выиграть, если не юзать
длины 1,2 и кодировать 3 и т.д. как старые
1 и т.д.?
hrumer> весь предполагаемый выигрыш сожрут
"непакуемые" байты, кодируемые 9 битами.
кстати, нашел более выигрышное (по
скорости распаковки) кодирование длин.
биты просто по-другому записывать.
;альтернативный вариант:
LD B,256-16
DPCЧ LD A,%01000000
DPC2
SLA C
JR NZ,$+6
LD C,(HL)
INC HL
RL C
RLA
JR NC,DPC2
;--
JR NZ,LENXX;12/7 закончили с длинами
INC B ;4
INC B ;4
INC B ;4
JR NZ,DPCЧ ;12/7 если не 16, то ещё
;берем. тут 16, но А = 0,
;и далее в В результат уже.
DEC B ;4 тут ещё можно сделать
;DJNZ на этот адрес. но это
;длиннее на 1 байт, но,
;возможно, быстрее
LENXX
ADD A,B ;4
DEC A ;4 ;или это убрать и выше
;загрузить B,15 с переходом.
CP 256-16+4;7 extended number.
JR Z,DPCS;B<>1;B=4 ;12/7
ADC A,256-16-1;корректировка. ;7
alone> И какие коды получаются?
hrumer> да по длинам те же самые.
alone> А если b в цикле не инкрементить, а
декрементить, выигрыша нет? В цикле только
djnz,а на выходе 3 раза add a,b(или sub b)
hrumer> декрементить думал, но там после
этого править длину надо через вычитание.
hrumer> ещё из реальных, но не реализован─
ных - непакуемые байты: если "А" не упако─
вался,а за ним "BCDEFG..." не упаковались,
то не должно быть такого, что А идёт отде─
льно,а BCDEF...отдельно.Значит,код,который
показывает непакованный блок, не должен
идти за непакованным байтом. Значит, этот
код что-то другое может кодировать. но это
копейки... ещё из реальных,но копеечных -
вставной символ. если вставной символ
совпадает с символом, который был D байт
назад,то это что-то могло бы значить...
alone> В этой ситуации можно сдвинуть
все коды длин ссылок на 1.
hrumer> кстати, для текста, видимо, после
паковки байтов 100-300 можно длину не с 1
брать,а с 2. и для графики надо потестить.
т.е. min len сначала = 1, потом =2.
alone> А если вообще без длины 1? Сколько
проигрыш? В RIP длины вообще от 3
начинаются. Но там Хаффман.
hrumer> без длины = 1 - на текстах даже
выигрыш, причем без дожатия Хаффаном. на
графике тоже.
alone> тогда надо менять формат хруста )
hrumer> корректировать minlen прямо в
потоке, ага.
Other articles:
