Info Guide #05 30 апреля 2004

Программирование

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

                Hrum 3.5i
 

   Для  распаковщика Hrum автором заявлена
особенно высокая скорость: 33 k/с. К сожа- 
лению,я не обладаю информацией,какие имен- 
но типы данных имелись в виду,но в общем и 
целом  автор  прав - это самый быстрый LZ- 
распаковщик с битовым потоком. За счёт уп- 
рощенного  в связи с этим формата он также 
и чрезвычайно короткий. К несчастью,автор- 
ский  пакет не предлагает распаковщика без 
перекидывания для использования его на не- 
сколько блоков. 

   Перекидывание  -  функциональная  черта
очевидных  предшественников  Hrum  на ниве
сжатия 48k игрушек.Идеология этого процес-
са  такова: кодовый блок ОБЯЗАН находиться
непосредственно за распаковщиком;распаков-
щик при запуске перекидывает свою активную
часть в тихое место (как правило,#5bxx), а
упакованный  блок - в конец выделенной па-
мяти  для распаковки; все адреса для этого
рассчитаны заранее (пакером) и лежат в те-
ле распаковщика.
 

   В Hrum введено три оригинальных ухищре-
 ния: 
  1. 5 байт конца файла (это  важная часть
файла, создаваемая для разрыва между адре- 
сами "откуда" и "куда  распаковывать") ко- 
пируются вместе  с распаковщиком  в "тихое 
 место" одной командой LDIR. 
  2. Предложен  ещё  более короткий способ
реализации стандартного дерева из 16 вари- 
антов, с которым мы ещё встретимся: 
────────────────────────────────────────── 
                LD E,1
        pair    LD A,#80 
        pair0   <getbit> 
                RLA
                JR C,pair0 ;2 прохода
                CP 3       ;A=0..3
                JR C,treeend
                ADD A,E
                LD E,A
                XOR C      ;=#10 !!!
                JR NZ,pair
        treeend ADD A,E
────────────────────────────────────────── 
   Хитрость  в команде XOR C. Т.е. получи-
лось короче,чем в PCD6.2 (там было SUB 15) 
и тем более чем в MS Pack (там не было ци- 
кла  и был лишний XOR A ). Kонстанта C=#10 
используется и в другом месте: при обрабо- 
 тке битового потока. 
  3. Один  и  тот  же  цикл взятия 3-4 бит
(ближе  к концу  распаковщика)  используе- 
тся как для взятия dispH (при putsЄ4 ),так 
и для взятия dispL (при puts=1 ),причём за 
всю работу этого цикла ни разу не портится 
флаг Z! В этом  флаге и лежит признак, что 
делать с результатом... 

   Словарь (окно) всего 4k.
   Имеется два чередующихся потока данных:
битовый и байтовый. Битовый поток хранится
кусками  по 16 бит и снимается в регистро-
вую  пару  HL. Пока  HL сдвигается, 16 бит
отсчитываются  в регистре B командой DJNZ.
Когда они кончаются, из потока берётся но-
вое значение HL.
 

   Упакованный блок с распаковщиком содер-
жит: 
Инициализацию распаковщика. 
Активную часть распаковщика. 
5 байт конца файла. 
2 байта начала битового потока. 
 1 байт - первый байт файла. 
   И далее согласно битовому потоку:
%1 - вставить байт из байтового потока. 
 %000,-disp3 - копировать  1 байт  с адреса 
 минус 1..8.
 %001 - копировать  2 байта: -disp8 берется 
 из байтового потока.
%010 - копировать 3 байта аналогично. 
 %01100 - копировать  N байт ( N берётся из 
  битового потока, N=0 - конец файла).Здесь
  и далее  после определения длины произво-
  дидся гадание по биту из битового потока:
  %0 - -dispL берётся  из байтового потока;
  %1 - аналогично, но перед  этим  -dispH в
  количестве  4 бит берётся из битового по-
  тока. Обратите внимание,избыточность фор-
  мата: -dispH=#FF кодируется двояко, автор
  сэкономил  1 байт распаковщика. Непонятен
  также юмор автора с командой RES 5,A, ко-
 торая могла бы выглядеть как LD A,#1f.
%01101 - копировать 4 байта как выше. 
%01110 - копировать 5. 
%0111100 - копировать 6. 
%0111101 - копировать 7. 
%0111110 - копировать 8. 
%011111100 - копировать 9. 
%011111101 - копировать 10. 
%011111110 - копировать 11. 
%01111111100 - копировать 12. 
%01111111101 - копировать 13. 
%01111111110 - копировать 14. 
%01111111111 - копировать 15. 

                Hrust 1.x
 

   Распаковщик  Hrust 1.x  -  самый хитрый
распаковщик  на  ZX. Несмотря на небольшой 
размер, он вполне способен запутать любого 
заглянувшего. 

   Уникальность формата в том,что он прямо
предназначен для сжатия кодов.Для этого он
снабжён кодами копирования с разрывом, ка-
ких больше нигде нет. Дополнительно приме-
нены расширяющиеся коды смещений,которые в
начале  файла короткие и указывают недале-
ко, а ближе к концу - длинные.
   В авторском  комплекте имеется два рас-
паковщика - с входным потоком в стеке  и с
входным потоком в IX. Еще один распаковщик
в виде бейсик-загрузчика сделал из первого
Alone Coder. Все они эквивалентны. 
   Распаковщик  начинается   с  переброски
упакованного блока в конец памяти,выделен-
ной для распаковки. Переброска идёт только
в случае, если  адрес  конца  упакованного
блока изначально меньше адреса конца памя-
ти  для  распаковки. Бейсик-вариант  этого
фрагмента не содержит,там нужно самому ко-
нтролировать,чтобы упакованный блок в про-
цессе распаковки не портился.Тем не менее,
есть шанс, что он запорется  и в авторских
распаковщиках, после переброски. Для этого
конец блока должен плохо паковаться.

   Битовый  поток  берётся  кусками  по 16
бит. C  содержит  константу 16. D содержит
один сброшенный бит,положение которого от-
носительно  левого  края  байта определяет
длину расширяемых ссылок. Изначально D=#bf
(назовём это состояние "2 бита расширяемой
ссылки"),далее периодическо происходит RRC
D ("3..8 бит расширяемой ссылки"). 

   Упакованные блоки имеют заголовок:

+0 "HR". 
+2 распакованная длина. 
+4 упакованная длина. 
+6 шесть последних байт блока. 
+12 два байта начала битового потока. 
+13 первый байт блока. 
+14 сами упакованные данные. 

   Обработка  упакованных данных осуществ-
ляется согласно указаниям битового потока:

 %1 - получить  байт  из байтового потока и 
 поместить куда распаковываем.
 %000,-disp3 - копировать  1 байт со смеще- 
 ния -1..8
 %001 - копировать C=2 байта. disp кодируе- 
  тся так:
  %00Ў%01: -dispH=#fdЎ#fe, -dispL в битовом
   потоке;
  %10: -dispH=#ff, далее исходя из байтово-
   го  потока: числа  <#e0  понимаются  как
  -dispL  (ссылка  обычная),  Є#e0  хитро:
   RLCA:XOR C, при  A=-1  расширяется длина
   ссылки, иначе  SUB 15 и получаем -dispL=
   =#b2Ў#ee (ссылка со вставным байтом:байт
   из $-disp, байт из байтового потока,байт
   из $+2-disp );
  %11,-disp5: обычная ссылка (через %10 та-
  кие короткие disp описать нельзя);
 %010 - копировать C=3 байта. Здесь и далее 
  disp кодируется так:
  %00: -dispH=#fe, -dispL в битовом потоке;
  %01: -dispH=#ff, далее исходя из байтово-
   го  потока: числа  <#e0  понимаются  как
  -dispL  (ссылка  обычная),  Є#e0  хитро:
   RLCA:XOR C, при  A=-1  расширяется длина
   ссылки  (на самом деле не используется),
   иначе  SUB 15  и получаем -dispL=#b1Ў#ef
   (со вставным байтом:байт из $-disp, байт
   из байтового потока, байт из $+2-disp );
  %10,-disp5;
  %11: расширяющаяся ссылка. -dispH берётся
   из битового потока, число битов согласно
   D  (#bf..#fe  соответствует  2..8  бит).
   -dispL  берётся  из  байтового потока. В
  остальном ссылка как ссылка.
 %01100 - копировать  C=4  байта  как выше. 
  Здесь и далее коды ссылок со вставным ба-
 йтом невыгодны, но есть.
%01110 - копировать 5. 
%0111100 - копировать 6. 
%0111101 - копировать 7. 
%0111110 - копировать 8. 
%011111100 - копировать 9. 
%011111101 - копировать 10. 
%011111110 - копировать 11. 
%01111111100 - копировать 12. 
%01111111101 - копировать 13. 
%01111111110 - копировать 14. 
%01111111111 - копировать 15. 
   И особенные случаи:
%01101000001111 - конец файла. 
 %0110100,len7 - если len7>15, то len будет 
  равно  len7*256+байт_из_байтового_потока.
  В  любом  случае  результат ляжет в BC, а
 далее см. случаи с len=3..15.
 %0110101xxxx - 12Ў42 (чётное число) байтов 
 из байтового потока.
 %011011,-disp4: ссылка со вставным байтом: 
  байт из $-disp, байт из байтового потока,
  байт из $+2-disp. Сделано из-за того, что
  в %001 предусмотрены  только -dispL=#b2..
  #ee, причем чётные, а в %010 только #b1..
 #ef, нечётные.

                Hrust 2.x
 

   Формат  предназначался для сжатия текс-
тов.Несмотря на то,что авторский упаковщик 
был неудобный,а формат (1998) с появлением 
RIP (2000)  и ZXRar (2003) устарел, он всё 
же стал единственным действительно СТАНДА- 
РТНЫМ форматом упакованных данных на ZX. И 
 не только для текстов. 
   Одних  упаковщиков Hrust 2.x сейчас из-
вестно девять (!), все они выросли из кода 
оригинального  упаковщика.  Количество  же 
программ,поддерживающих формат на распако- 
 вку, я не определил. 
   Идеология принята противоположная Hrum:
выгрузка упакованных блоков ТОЛЬКО без ра- 
спаковщика, распаковщик отдельный,не испо- 
льзует  стек. Может  быть, из-за сочетания 
этих идей формат победил остальные? 

   На практике имеется две версии заголов-
ков упакованных блоков: v2.1 и v2.3. Стан-
дартом является первая.Вторая используется
только в архивах Hrip.

                  v2.1:
 смещение  длина 
   +0       3     "hr2";
  +3       1     "1". Если bit7=1, то файл
                 был просто "сохранен";
                  (а значит - w[+4]=w[+6])
   +4       2     длина исходного файла;
   +6       2     длина упакованного файла;
  +8     w[+6]   упакованный файл.

   Перед  упакованным блоком хранятся пос-
ледние 6 байт файла,сами эти 6 байт не па-
куются.
   Максимальная длина повторяющегося фраг-
мента,кодируемого одной ссылкой: 4095 байт
(#fff). Максимальная  ссылка назад: -65535 
байт (окно  в авторском  упаковщике: 16384
байт, в других  известных упаковщиках дос-
тигает 32768, но уменьшается при приближе-
нии  упакованного  куска к непакованному -
упаковка идет в тот же буфер)

 011000nnnn - несколько  непакованных байт, 
  а точнее, 12+nnnn*2 (не более 42, как ви-
 дно), в байтовом потоке - эти байты.
 1 - просто  один непакованный байт (в бай- 
 товом потоке - этот байт).
000xxx - 1 повтор (xxx=disp3). 
001 - 2 повтора (в байтовом потоке disp8). 
010... - 3 повтора. 
01101... - 4 повтора. 
01110... - 5 повторов. 
0111100... - 6 повторов. 
0111101... - 7 повторов. 
   и т.д.
01111111110... - 14 повторов. 
01111111111... - 15 повторов. 
 011001... - от 16 до 255  повторов (в бай- 
 товом потоке - число этих повторов).
 011001... - от 256 до 4097 повторов (в ба- 
  йтовом потоке: сначала старший байт,потом
  младший байт числа повторов. Очевидно,что
  старший байт всегда меньше 16, что позво-
  ляет  отличить последовательность от пре-
 дыдущего случая).
 011001 - это также конец файла,если байт в 
  байтовом  потоке  равен нулю. Из этого, в
  частности,следует,что последний байт упа-
 кованного блока всегда равен нулю.

   Выше под многоточием понималось следую-
щее указание disp'а (отрицательного):

1 - disp8 (#ff00-ffff) в байтовом потоке. 
 011x - disp9 (#fd00-feff), где x - старший 
  разряд (0 соответствует #fd), остальные 8
 - в байтовом потоке.
 010xx - disp10 (#f900-fcff), где xx - ста- 
  ршие  разряды (00 соответствует #f9), ос-
 тальные 8 - в байтовом потоке.
 001xxx - disp11 (#f100-#f8ff),  где  xxx - 
  старшие  разряды (000 соответствует #f1),
 остальные 8 - в байтовом потоке.
 000xxxx - disp12 (#e200-#f0ff), где xxxx - 
  старшие разряды (0000 соответствует #e2),
 остальные 8 - в байтовом потоке.
 0000000 - disp16, хранится в байтовом по- 
 токе,сначала старший байт,потом младший.

                v2.3/Hrip:

   Файл  разбивается  на  блоки. У каждого
блока свой заголовок.Блоки могут быть раз-
ной длины. Желательно, однако, чтобы длина
блока была кратна #100. Просто упакованный
файл  длиной более #а000 также разбивается
на блоки. Последовательно записанные блоки
образуют упакованный файл,а последователь-
ность упакованных файлов - архив.

              Заголовок блока:
           --------------------
+0(5) - "Hrst2". 
 +5(1) - байт флагов: 
  bit0=1: блок сохранен без сжатия;
  bit1=1: блок в файле был последним;
 bit5=1: файл удален.
+6(2) - длина исходного блока. 
 +8(2) - длина упакованного блока (без дли- 
 ны заголовка).
 +10(1) - длина дополнительной информации: 
                  -----
 +11(2) - CRC16  упакованного  блока (можно 
 быстро проверить сохранность архива);
+13(2) - CRC16 исходного блока; 
 +15(14) - дескриптор файла (как в TR-DOS). 
                  -----
+[+10]+11 (берем байт из [+10], прибавляем 
 11) - упакованный блок.

   Длина дополнительной информации равна:
=0  для просто пакованных файлов; 
=2  +хотим иметь CRC16 упакованного блока; 
=4  +еще и знаем CRC16 исходного блока; 
=18 +знаем имя файла. 

   В  Hrip максимальный размер блока - 16k
без заголовка. Заголовок занимает 29 байт.
В заголовке блока хранится следующая допо-
лнительная информация: CRC пакованного,CRC
исходного, копия заголовка из каталога.
   Параметр  в заголовке файла, отвечающий
за реальную длину блока,должен быть кратен
256. 

             Заголовок архива:
           --------------------
IDARCH  DB "HRi" 
 IDALL   DB 0 ;количество файлов в архиве 
  ;(используется в Hrip'е при дополнении
 ;архива, чтобы не было больше 255 файлов)
SMESH   DB 0 ;см.далее 
LAST    DW 0 ;см.далее 
CAT     DB 0 ;1 - каталог есть в архиве, 
             ;0 - каталог отсутствует.

   Следующая формула показывает, как можно
определить конец архива (в байтах от нача-
ла архива):
 END_ARCH=[LAST]*256-(256-[SMESH]) bytes
   Расположение каталога,если таков прису-
тствует,можно определить по формуле:
        START_CAT=[LAST]*256 bytes

              Формат каталога:
           --------------------
   Заголовок каталога:

IDCAT   DB "Hrip" 
FILES   DB 0 ;файлов в архиве = IDALL 
SECLEN  DB 0 ;длина каталога в секторах. 

   Далее  идет  список  файлов в архиве, в
следующем формате:

IDFILE  DS 11 ;имя файла 
SMSEC   DW 0 ;на сколько секторов от 
             ;начала архива находится файл
SMBYTE  DB 0 ;в каком байте в этом секторе 
LENPACK DB 0 ;длина упак. файла в секторах 
LENREAL DB 0 ;реальная длина файла в сект. 

   Смещение  файла относительно начала ар-
хива вычисляется по следующей формуле:
    SM_FILE=[SMSEC]*256+[SMBYTE] bytes

   Количество файлов задается в переменной
FILES (в заголовке каталога), но этого ма- 
ло,необходимо,чтобы был 0 после последнего
описателя файла.

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