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