Inferno #05
30 апреля 2004

Sofтинка - Real Information Packer 0.2x - один из самых мощных компрессоров на ZX.

Real Information Packer 0.2x
 

   Автор программы - Роман Петров (Йошкар-
Ола), тёзка и однофамилец йошкар-олинского 
композитора  Megus'а. Человек-загадка. На- 
писав единственную программу, он скрылся в 
неизвестность, и  тут же возникли вопросы: 
откуда такой уровень программирования? ко- 
гда и как настолько ювелирно настроены па- 
раметры  сжатия? почему условия инкремента 
длины ссылки с точностью до плюс-минус ба- 
йта совпали с аналогичными условиями в фо- 
рмате Rar2.x, хотя к моменту появления RIP 
 этот формат отнюдь не был обнародован? 
   В любом случае,это один из самых мощных
компрессоров на ZX,победить его сейчас мо- 
жет только ZXRar, причём, будь ZXRar напи- 
сан раньше RIP, ещё неизвестно,кто бы кого 
победил... На маленьких файлах RIP принци- 
пиально  выгоднее - из-за  меньшего объёма 
деревьев и длины распаковщика. 

   Существует 3 распаковщика RIP: оригина-
льный v0.21 размером #121, с параметрами в
HL (откуда) и DE (куда); DERIP+++.H разме- 
ром #112 (в отличие от предыдущего, позво-
ляет  задать адрес деревьев независимый от
адреса распаковщика); и v0.25, пришиваемый
к упакованному файлу наподобие Hrum, дово-
льно неоптимальный.
   Гвоздь формата - настоящие произвольные
деревья, хранящиеся  в файле в упакованном
виде, совсем как в архивах Zip, Rar и т.д.
Процедура построения дерева в сущности ге-
ниальна. Приводить её здесь не имеет смыс-
ла,она повторена в исходниках DERIP, mRIP,
RZXSFX и т.п. Без  её невероятной лаконич- 
ности сама идея использования произвольных
деревьев  в кодовых  компрессорах осталась
бы  бессмысленной. Считалось бы, что таких
деревьев достойны лишь архиваторы.
   Вместе с тем, пользователю нового комп-
рессора  пришлось привыкнуть к новой проб-
леме: найти  #5C0 байт (#5C2 в DERIP+++.H)
памяти под деревья.Это уже не 256 байт под
активную часть распаковщика, как в Hrust1.
Нет, такой крупный объём надо где-то выде-
лять. Например,на экране.Не всегда это до-
пустимо. Вероятно, из-за таких проблем RIP
не  получил  большого  распространения при
сборке электронной прессы.
   Другая  проблема - скорость распаковки.
Она значительно ниже,чем у старых компрес-
соров, даже  ниже, чем  у программы UnRar.
Этот недостаток нельзя устранить - он свя-
зан  с принципиальным отсутствием в упако-
ванном  файле  байтового  потока. Начинают
влиять циклы обработки деревьев, а ускоре-
ние  их  возможно лишь ценой существенного
увеличения  распаковщика  и буфера под де-
ревья.

   Биты читаются из байта начиная от 0-го,
т.е. нестандартно. 

   Формат:
+0(2) - UnpLen, распакованная длина; 
 +2(2) - PakLen, упакованная  длина, считая 
 со следующей ячейки (+4);
 +4 - начало  информации о деревьях. 18 че- 
  тырёхбитных  чисел  (тетрад), указывающих
  количество  бит  в хаффмановских  кодах у
  дерева,используемого для извлечения рабо-
  чих деревьев. Для каждого из кодов 0...17
  хранится длина в битах ( 0 - код не испо-
  льзуется; чем чаще код,тем он должен быть
 короче).
   Из  этих тетрад однозначно строится де-
рево,по которому будут считаны аналогичные
данные о 288+32 символах рабочих деревьев.
Конечно, тех аналогичных данных (они лежат
далее) не обязательно 288+32 байт (в смыс-
ле, символов Хаффмана) - они хитро закоди-
рованы: 0..15 - просто код длины, типа тех
тетрад; 16 - конец информации; 17 - повто- 
рить ещё 2 раза предыдущую длину. 

   Дерево из 288 литералов условно назовём
maintree, а дерево из 32 - просто tree. 
   Деревья  строятся  из длин по следующим
 правилам:
  1. Если дерево нарисовать так,что корень
будет сверху, единицы справа,а нули слева, 
то  левые  подветви должны быть не длиннее 
правых. Нижняя же кромка веток дерева дол- 
жна плавно  опускаться (глубина увеличива- 
 ться) слева направо. 
  2. Внутри ярусов (совокупностей листьев,
имещих  одинаковую глубину) действует сор- 
тировка: меньшие  коды  символов справа от 
больших.Т.е.наоборот относительно Rar. Это 
связано с сокращением распаковщика. 
   После того,как вся информация о деревь-
ях считана, извлекаются байты конца архива
(в  обратном  порядке) по дереву maintree,
сразу же закидываются в стек.Любой литерал
Є256 - конец этого  процесса, и начинается 
собственно распаковка.

   Распаковка происходит циклами,каждый из
которых начинается с чтения символа по де-
реву maintree:

 0..255 - просто байт.Поместить его в выхо- 
 дной поток;
 257..260 - puts=1..4. Далее по дереву tree 
  считывается код длины disp:
   0 - использовать старый disp;
   1..4 - disp=1..4
   5,7,...,31 - disp вида %10.., от 3 до 16
    бит.Дочитываются недостающие биты disp,
    начиная со старших;
   6,8,...,30 - disp вида %11.., от 3 до 15
    бит. Аналогично. Отсюда видно, что раз-
    мер окна не превышает 49151.
  Эта кодировка disp полностью соответству-
  ет формату Rar (см. Inferno#4). Более то-
  го, почти (256<>257) совпадает следующее:
  При dispЄ256  инкрементируется  puts. При
  dispЄ#2000 ещё раз инкрементируется puts!
 Реализуется копирование.
 261,263,...,287 - коды  длин  puts  (puts= 
  =%10..) от 3 до 16.  Дополнительно считы-
  ваются (соответственно) 1..14 бит для по-
  дцепления к %10.. Далее считывается disp,
 как выше;
 262,264,...,286 - аналогично,но puts=%11.. 
 От 3 до 15 бит. Далее disp, как выше;
256 - окончить распаковку. 

   После  распаковки  из  стека вынимаются
байты  конца файла (максимальное число мне
неизвестно).

              mRIP (mrip4.H)

   Формат  отличается от оригинального RIP
 следующими деталями:
   1. Нет UnpLen, PakLen в начале;
   2. Нет байтов конца файла в начале;
   3. Нет кода "повторить предыдущий disp";
   4. Нет коррекции puts при dispЄ#2000;
  5. Тетрады длин кодов дерева для постро-
ения рабочих деревьев лежат в обратном по- 
рядке. 
   В  результате  депакер уместился в бей-
сик-блоке,и был создан удобный автосборщик
для системных программ. На маленьких прог-
раммах  он  выигрывает у RIP'а один сектор
за  счёт  размера распаковщика. На длинных
теоретически  может проиграть. Но на прак-
тике до этого не доходит из-за ограничений
на  размер  файла, пакуемого mRIP. Вот что
его ограничивает:
   mRIP не перемещает блок перед распаков-
кой, поэтому  адрес окончания упакованного
блока  должен  быть  выше адреса окончания
распаковки. А адрес окончания упакованного
блока  зависит не от вас, а от длины этого
упакованного  блока  плюс  метка OTKUDA. А
эта метка (в текущей версии #AA00 ) в свою
очередь  зависит  от максимального размера
блока  и метки  maintree (в текущей версии
#f881 ), т.к. при  распаковке генерируются 
деревья,которые где-то нужно хранить,а за-
чернить  экран  не  получается: не хватает
места в секторе бейсика.
   Ограничения есть не только при распако-
вке, но и при упаковке: при упаковке очень
большого  файла  может  не хватить памяти.
Можете надеяться упаковать память от #6000
до #E000 (pg0), но никак не всю память.

   Для подключения mRIP к программе нужно:
 

  1. Определить метки begin, end, GO - ра-
 змеры программы и адрес её запуска; 
   2. Сформировать имя программы в #5CDD;
  3. В  начале  программы установить стек,
раскрасить  экран  и бордюр, разобраться с 
константами клавиатуры: REPPER и REPDEL... 
Желательно LD (IY+1),#CC для безбоязненно- 
го использования  вашей  программой памяти 
 #5bxx. Сам mRIP всего этого не делает; 
  4. В  конце главного исходника поместить
INCLUDE "mrip*". 
   Рекомендуется  писать именно "mrip*", а
не "mrip4", поскольку  версия  mRIP  может
меняться. Если вы будете,например,распрос-
транять свои исходники, у получателя может
оказаться другая версия,ему придётся куда-
то лезть,что-то исправлять... (Большинство
народу терпеть  не может всякие телодвиже-
ния.) И вам же будет удобнее обновлять ве-
рсии mRIP на своих дисках.Зачем обновлять?
Иногда очень неприятно рыться,искать САМУЮ
РАСПОСЛЕДНЮЮ  версию по всем дискам, а там 
сплошь всё старые да древние...

   Если определена метка make, сборка про-
изойдёт  и без нажатия Caps Shift - можете
использовать  для распространения с mkace-
подобными сборщиками.
   Для организации отладочного запуска,ко-
торый меняет код программы,вписывайте (ес-
ли нужно) после INCLUDE следующее:
 

                 ORG $
                 CALL 8026
                 JP NC,nenado
                 <ваши pokes>
                JP GO

   Ограничение на  размер - не пересекайте
адрес #5c00.

                       подготовил А. Кодер



Другие статьи номера:

CacheVox - Пакет программ для импорта и последующего проигрывания с дискет цифровой музыки.

For Coderz - RAYCASTING - сделай себе немного DOOM'a. Алгоритм трассировки 3D лабиринта как в игре WOLF.

Inferno - О журнале.

DIY - Приспосабливаем мышь от Amiga к ZX Spectrum.

Sofтинка - обзор экранных упаковщиков для ZX Spectrum.

Inferno - Авторы и контакты редакции.

Gameland - описание игры Stronghold (Бастион).

Sofтинка - Пакет CacheVox v1.0 для импорта и проигрывания с дискет цифровой музыки.

Интервью - интервью с Disabler'ом - кодером, художником и железячником из Ростова-на-Дону.

Others - Глюки записи на дискеты. Причины и методы борьбы.

Gameland - Краткое описание проблем игры Dune: Imperia 2.

Inferno - Ошибки в предыдущих номерах.

For Coderz - Маленькие программерские хитрости.

Spectrum - Форматы упакованных данных на ZX Spectrum.

Gameland - об игре Hexagonal Filler.

Sofтинка - Hrum 3.5i - самый быстрый LZ-распаковщик с битовым потоком.

DIY - Изготовление хвоста для мышки.

Железо - Исследуем микросхему К561ИЕ10A.

Железо - Исследуем микросхему КР1533ИЕ7.

Железо - Исследуем микросхему К561ТЛ1. .

Sofтинка - экранный компрессор Laser Compact 4.0.

Inferno - Письма в редакцию.

Sofтинка - компрессор текстов MS Pack 01.96.

Inferno - Об оболочке.

Sofтинка - преимущества архиватора Rar.

Sofтинка - Упаковщик RGB картинок Powerful Code Decreaser v6.2.

Ликбез - Что такое плюс и минус напряжения.

Ликбез - Как работает защита элементов цепи.

For Coderz - Нюансы Raycasting-а.

Sofтинка - Real Information Packer 0.2x - один из самых мощных компрессоров на ZX.

For Coderz - Автосборка программы. Оптимизируем процесс сборки.

Inferno - Вступление.

Others - Результаты анкетирования.

Others - The Compo. Об анкетировании.

О Спектруме - размышления о будущем спектрума.

Железо - Еще раз о защите микросхемы КР1818ВГ93.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Тема - Теория журналостроения.
Разное - Без непоняток.
Реклама - Реклама и обьявления ...

В этот день...   17 июля