31 декабря 2017

         Компрессия
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 прямо в 
потоке, ага.