Info Guide #07 31 мая 2005

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

For Coderz - Пишем архиватор. Практические принципы LZ упаковки.

               Практические принципы LZ упаковки
 

   Прежде  я  рассказывал  вам о распаковке и о структуре упако─
ванных  данных. Пришло  время поговорить и о том, как эти данные 
получаются. 

                               0.
 

   LZ (A. Lempel, J. Ziv) - способ упаковки, при котором в файле
отыскиваются повторяющиеся фрагменты, группируются, как правило,
в ссылки (естественно, не всё можно представить как ссылки - бу─
дут и отдельные символы), параметры  каковых  ссылок кодируются,
 как правило, по Хаффману.
   Ссылка - факт  наличия  повторяющегося фрагмента (подстроки):
содержит расстояние disp (от указателя текущей позиции упаковщи─
ка или распаковщика  назад до момента встречи такого же куска) и
 длину len (сколько, собственно, байт совпало).
   Окно, оно же объём словаря - максимальное расстояние disp для
ссылок. Дальше упаковщик не ищет, а в кодировании обычно не пре─
 дусматривает кодов для указания более далёких ссылок.
   Метод Хаффмана (D.A. Huffman) - способ энтропийного кодирова─
ния, в котором  длины  символов  (литералов) различны (но всегда
имеют  целое  количество бит): для частых - короче, для редких -
длиннее. А отличается он от аналогичных (например, от кода Фано)
тем, что коды (а вернее, длины символов,т.к. все варианты набора
кодов  при  данном  наборе  длин  символов равновыгодны) выбраны
 самым эффективным образом, короче не придумаешь.
   Дерево - совокупность  кодов  всех  используемых символов при
кодировании  по Хаффману. Дерево можно хранить самыми различными
способами. При  распаковке  удобнее  всего  как настоящее дерево
(встретили 0 - переходим на байт вперёд, встретили 1 - переходим
вперёд на столько, сколько указано в текущей ячейке). При упако─
вке - как таблицу (каждому символу соответствует некий код и его
длина). В упакованном файле - в сжатом виде (перечисляются длины
всех символов,и эта последовательность как-то кодируется,хотя бы
тоже по Хаффману, с более коротким деревом - так в RIP и RAR ).
   Пример дерева канонического вида, т. е. где ярусы углубляются
слева  направо, а внутри яруса символы отсортированы по алфавиту
(именно такое дерево применяется в RAR ):

                              корень
                              /   
                            /    /       1-й ярус (в нём пусто)
                           e  / /  /      2-й ярус
                             a b d f h /      3-й ярус
                                     c  g       4-й ярус

   Ход  по дереву  налево  кодируется нулём, направо - единицей.
Здесь код символа "e" - 00, а код символа "h" - 110. И т.п.

                               1.

   Упаковывать, как  мы понимаем, можно из одного места памяти в
другое, можно  в памяти  с нахлёстом на исходные данные (теряя в
качестве  упаковки), можно  из  памяти  в файл, можно из файла в
память, можно из файла в файл. Из файла упаковывать весьма проб─
лематично и медленно, поскольку затрудняется поиск повторяющихся
фрагментов, поэтому в архиваторах практикуют подгрузку обрабаты─
ваемого  файла так, чтобы в памяти всегда имелось его содержимое
от  текущего указателя назад на длину окна. Для этого достаточно
иметь  буфер чуть больше размера окна. Но его не так легко обра─
ботать: при зацикленном окне процедура поиска повторов будет ве─
сьма  сложной, а при  незацикленном  его надо регулярно сдвигать
(и не  только  его, но и хэш-таблицы, о которых ниже), что очень
медленно. Поэтому, а также из-за наложения упакованных данных на
неупакованные, я пока не поддержал зацикленный словарь в ZXRar и
фактически режу файл на кусочки по 127-128 секторов.
   Как искать повторы? Поиск напролом (CPIR или CPDR) - нетороп─
ливый  процесс, скорость  которого  падает в квадрате от размера
окна. John  у нас  употребляет  выражение: "пакует медленно, как
PCD" - это  сказано  о поиске напролом. Ускоряют поиск с помощью 
ключей и таблиц хэширования, о которых я сейчас расскажу.
   Таблица ключей.
   Это  очень  распространённая  идея. Суть её в том, что группа
байт (здесь  2 или 3 байта; а в ALASM'е, например, до 58, поско─
льку  ключ  используется  для  поиска меток по имени) кодируется
несколькими  битами ключевой суммы (разумеется, для разных групп
байт  эти  коды могут совпадать). Создаём таблицу, в которой при
каждой  ключевой  сумме  будет  записан адрес, по которому она в
последний  раз встретилась, или адрес ниже начала окна в против─
ном  случае. Таким  образом, прочитав 2-3 байта из-под указателя
текущего положения в файле, мы можем быстро найти адрес,по кото─
рому с высокой вероятностью будут такие же 2-3 байта.
   Подробнее про ALASM:
 ──────────────────────────────────────────────────────────────── 
   Таблица меток состоит из 64 или 128 (зависит от версии) спис─
ков,которые объединяют метки с одинаковыми ключевыми суммами.Это 
 не нужно для показа меток, например, STS плюёт на эту структуру. 
  +0 - младшие 6 бит - длина  всей метки (т.е. длина имени метки
плюс 5 ). Если бит 6=1, то метка - имя макроса, если бит 7=0, то 
метка  определена. STS на это тоже плюёт. Для последней (с точки 
 зрения STS'а ) метки +0 содержит 0. Hа ней STS останавливается. 
  +1,2 - ЧИСЛО, т.е. содержимое метки. STS ползёт по меткам,пока
 число не совпадёт с нужным ему. 
  +3,4 - адрес следующей метки  в  ЭТОМ  списке. STS'у не нужен,
 т.к. он движется по всем спискам и вообще в обратном порядке. 
   +5 - имя метки задом наперёд.
   В STS 5.x, 7.x: в  ячейке  #fe88  номер первой страницы меток
(для порта  #7ffd ), номера  остальных страниц  не передаются; в 
ячейках #fe7c, 7d адрес хвоста таблицы меток, с которого начина─ 
ется поиск (+1). 
   Unreal Speccy (v0.27)  ищет в #17, #57 страницах  STS и берёт
данные о странице и адресе начала таблицы меток из него. 
──────────────────────────────────────────────────────────────── 
   Таблица хэширования.
   Каждой  ячейке  окна приводится в соответствие ещё 2 байта, в
которых  дан адрес СЛЕДУЮЩЕЙ (назад) ячейки, в которой 2-3 байта
 образуют ту же ключевую сумму.
   2 или 3 байта следует выбрать для хэширования? Это на любите─
ля. В Hrust 2.x  было 2 байта, и 2-байтные короткие ссылки (а 2-
байтные ссылки всегда короткие - не дальше 256 байт, иначе выго─ 
днее просто закодировать эти 2 символа) искались в основном цик─
ле поиска. В ZXRar - 3 байта,и 2-байтные ссылки ищутся в отдель─
ном цикле. В этом случае  режим упаковки .rzx (для текстов - там
2-байтных ссылок нет) работает  несколько быстрее, но режим .rar 
(для всего остального,там такие ссылки есть) - несколько медлен─
нее. В исходнике ZXRar  можно включить 2-байтные ключи, но режим
.rar от этого  не ускоряется, он всё равно  организован отдельно 
(поиск 2-байтных ссылок ведётся, если обычным поиском ничего хо─
рошего не найдено). Можно,конечно,организовать две хэш-таблицы и
две таблицы ключей - одна пара  для поиска 2-байтных совпадений,
вторая - для всех остальных. Но нужно больше памяти - 2..5 допо─
лнительных килобайт.
   Итого  получаем  размер  требуемой памяти: window*3+keys, что
для 12-битных ключей и 32-килобайтного словаря даёт 32*3+8=104k.
В Hrust 2.x используются  13-битные ключи (занимают страницу), в
ZXRar - 11-битные (занимают 2/3 экрана).В том же исходнике ZXRar 
можно  включить  13-битные ключи, которые будут лежать в верхней
памяти. Разницы в скорости  между 11- и 13-битными ключами прак─
тически нет (насколько помню, по замерам было около 5% ).
   Как видим, в 128k памяти можно этим методом обработать только
32k, от силы 40k окно. Возможно, поэтому  придётся в скором вре─ 
мени перейти на упаковщики, рассчитанные на 256k машины.
   Метод  поиска  с хэшированием работает медленнее CPIR/CPDR на
длинных  группах  повторяющихся байт. Кто подскажет решение, как
ускорить? В ZXRar это очень заметно! А.В. Кадач предлагает огра─
ничивать поиск по хэшам несколькими десятками прыжков, соответс─
твенно, с потерей качества сжатия...
 Hrumer> 
    Я для Laser Compact думал обойти проблему следующим образом:
   По-особому относиться  к последовательностям байт AAAAAA... и
ABABABAB..., длиной L, больше определенной,подбираемой на тестах 
 (думаю, от 3..5 байт). Они очень часто встречаются в картинках. 
   При  заполнении  таблицы - той, где  лежат  адреса предыдущих
вхождений  символа (или  символов, если  хэширование  идёт не по 
 одному байту): 
   Заполнять  адрес  для  первого А. Вместо адреса для второго А
записываем длину последовательности байтов ААА... (ABAB...). При 
поиске  ранее  записанная  длина последовательности используется 
для  точного  определения  адреса, где находится искомая строка. 
Пример  такой: ранее  встретилась посл. AAAAAAAB. Текущая посл.: 
AAAAC. В результате сравниваем  строки AAAAB и AAAAC. Естествен─ 
но, про  то, что  A  у нас совпадают, мы знаем. Остаётся сравни─ 
вать с символов В и С. А вдруг они совпадут,и длина последовате─ 
 льности будет равна 5, или больше... 
   Ну  а самый большой выигрыш получается из-за того, что в этой
таблице  нет частых ссылок, присущих при обработке вышеуказанных 
последовательностей. По сути, мы не забиваем таблицу в некоторых 
местах. А для  того, чтобы  качество паковки не падало, надо всё 
же  заполнять  таблицу для символов AA, предшествующих символу B 
из последовательности  AAAAAAAB. Хотя это не обязательно, и есть 
несколько вариантов, можно подумать и поэкспериментировать. Мно─ 
 гое зависит от того, по скольким байтам происходит хэширование. 
   Поскольку у LC поиск идет ещё и "вверх ногами", то схема была
чуть сложнее, да и то - расписана только на бумаге. К сожалению, 
я её так и не реализовал.Сейчас всё написано по памяти,некоторые 
 моменты я опустил. 
   Еще могу дополнить: возможно, более оптимальным будет то, что
под  повторяющиеся символы типа AAAAA длиной больше определенной 
лучше завести  отдельную  таблицу  в 256 элементов. Это поле для 
экспериментов, опять же. 

                               2.

   Hrust  кодирует  ссылки сразу же после того, как он их нашёл.
Но его деревья фиксированные. Для серьёзного же архиватора перед
кодированием  нужно строить оптимальные деревья. Где хранить ин─
формацию, на  основе  которой мы будем их строить, и где хранить
информацию, которую  мы, собственно, будем  кодировать? Ведь  мы
кодируем  не сам исходный файл, а LZ поток со ссылками, а искать
ссылки по второму разу накладно, не так ли?
    Поэтому нужно при LZ-просмотре файла запоминать:
  1. Количество  вхождений всех символов текста и всех спецкодов
LZ (статистик  может быть несколько: например, спецкоды смещений 
 в RAR кодируются отдельным деревом). 
  2. ВЕСЬ LZ-поток  в неупакованном виде (для этого нужен допол─
нительный буфер, не совпадающий  с буфером окна. Можно, конечно, 
залезать и на начало буфера окна, следя в LZ-поиске за его изме─ 
няющимся  размером, но  тогда сжатие будет хуже). Всех символов, 
включая спецкоды LZ, может быть больше 256, поэтому я, например, 
в ZXRar храню лишний, 8-й, бит отдельно, для  чего  организуется 
перемежаемый  битовый  поток  а-ля  Hrust. В том байтовом потоке 
(без 8-го бита) должны лежать параметры LZ-спецкодов, т.е. длина 
 ссылки (если она не задана в LZ-спецкоде явно) и смещение. 
   Только  просмотрев  существенную  часть  файла (десятки кило─
байт), можно строить дерево Хаффмана и кодировать полученный LZ- 
поток по Хаффману, записывая в .rar -архив. Потом можно начинать 
новый LZ-поток и новую статистику. 
   Метод Хаффмана я уже описывал в общий чертах в IG#5. Суть его
 вот в чём.
  1. Разные  байты, в зависимости  от их вероятности, кодируются
 кодами разной длины. 
  2. Длины  кодов  в потоке  каждый раз не лежат, взамен имеется
двоичное  дерево  самого  общего  вида: если прочитали из потока 
нуль, то идём по дереву налево, если единицу - направо. Дошли до 
листа - конец; в листе записан символ (байт). Как хранить дерево 
в потоке, я  уже  рассказывал  в  Inferno#4 (в описании  формата 
.rar ).Как его хранить в памяти - дело конкретного распаковщика, 
но  лучше  всего  применять  декодеры из распаковщиков derip или 
smallunr. Дерево в них следующее. Каждый узел - 4 байта ; 2 бли─ 
жайших  его  потомка корня лежат в начале буфера дерева: 2 байта 
для левого  и 2 байта  для правого потомка; в "потомках" записан 
либо символ (тогда 2-й байт <#40 ), либо адрес, где этот потомок 
 хранится как узел (тогда 2-й байт равен старшему байту адреса). 
  3. Коды Хаффмана, в отличие  от  неоптимальных  кодов Шеннона-
Фано, выбираются следующим образом.В неком буфере для сортировки 
имеем  таблицу  символов  и их  вероятностей; объединяем 2 самых 
редких  символа  и сохраняем их в ту же таблицу как узел дерева, 
вероятность которого равна суммарной вероятности этих символов,- 
старые  же  символы  удаляем из списка; далее опять ищем 2 самых 
редких символа (символом можно считать и уже полученный узел де─ 
рева) и так же объединяем их; и так далее,пока не останется один 
узел, который объединять уже не с чем - это и будет наше дерево. 
Хранить список-дерево во время такой сортировки лучше по 4 байта 
на  каждый  элемент. 2 байта  на  частоту, 2 байта на содержимое 
(номер  символа  или  адрес левого потомка, правый же - четырьмя 
байтами дальше). Соответственно,после объединения символов/узлов 
они  переносятся  в другой  буфер, который  организуется в конце 
буфера, где  мы держим символы, и растёт сверху вниз. Символы же 
надо отсортировать по вероятностям (т. е. на практике - частотам 
встречи  в файле) заранее, и вносить  объединённый узел в нужное 
место списка, в соответствии с его вероятностью. 
   После  такой сортировки мы не можем сразу сохранить дерево по
стандарту Rar/Rip. Стандарт у них такой, что (при описании дере─
ва) для каждого символа в упакованный файл сохраняется лишь дли─
на этого символа (от 0 до 15, где 0 - символ отсутствует).А сим─
волы  распределяются на каждом ярусе (совокупности символов рав─
ной длины) в алфавитном  порядке. В Rip - в обратном алфавитном,
но это не суть важно. Поэтому  дерево нужно перестроить, предва─
рительно найдя длины всех литералов. Делается это так.
   В соответствии с первым деревом (полученным после сортировки)
составляем  таблицу: для  каждого  символа - его длина (1..255).
Составляем её от нашего корневого узла (который, как вы понимае─
те, сейчас один-одинёшенек лежит в начале буфера для сортировки)
псевдорекурсивно: в начале обхода сохраняем в стеке "некий код";
идём  налево  и при этом сохраняем в стеке путь направо (адрес и
текущую  глубину); дойдя  до  листа (символа), дальнейшую дорогу
выясняем из стека, а если там "некий код", то дерево кончилось.
   Кадач  говорит  в своей кандидатской диссертации (с. 60), что
есть  способ  нахождения  длин всех литералов без занудного про─
цесса поиска-объединения-выкидывания-сдвига (то есть  вообще без
составления первого дерева), но самого способа не приводит.
   Дальше, каким бы способом мы ни строили первое дерево, всё же
нужно  удалить  ярусы  выше  15-го, потому что 15 - максимальная
длина символа, разрешённая  в Rar, Rip и им  подобных  упаковщи─
ках. Мой  способ  следующий. При вышеописанном построении табли─
цы  длин  символов  параллельно будем строить таблицу количества
символов для каждой конкретной длины. Составили? Прекрасно. Ищем
самую  длинную  длину, которая  вообще есть. Допустим, что такой
длине  (назовём её N+1 ) соответствует C символов. Это нехорошо;
эти  символы  надо  опустить на уровень (ярус) ниже (на N-й ) за
счёт  поднятия  символов  длиной N-1 (поднимаем тоже на N-й уро─
вень). На  каждые  2 опущенных символа длиной N+1 (а их число C,
козе понятно,чётно) приходится 1 поднятый символ длиной N-1. Это
было  бы прекрасно, если бы символы длиной N-1 всегда можно было
найти. Однако  их  иногда  не  хватает (может и вообще не быть),
поэтому  приходится  довольствоваться  поднятием символов длиной
N-2 (поднимаем  на N-1-й уровень): на каждый такой поднятый сим─ 
вол  приходится  4  опущенных  символа  длины N+1. Если нет N-2,
берём N-3 - на каждый такой поднятый приходится 8 опущенных N+1.
И так далее. В конце  концов, после нескольких операций по опус─
канию символов максимальной длины, длин >15 не остаётся.
   Здесь "опускание" на ярус - это движение вверх  по вышеприве─
дённому рисунку. Дело  в том, что деревья принято рисовать вверх 
корнем. 
   Имея  массив  длин символов, упаковщик может составить массив
кодов  символов: начиная с 1-го яруса, идя по ярусу в алфавитном
порядке, присваиваем символам коды от 0 и далее (после 0 следую─
щий код будет 1 - итого два кода,но 1 используется только в слу─ 
чае, если  дерево имеет только 1-й ярус, т. е. имеется всего два 
символа). Допустим, мы  нашли на 1-м ярусе один символ, следова─ 
тельно, не нашли применения коду 1. Приписываем к этому коду но─
лик (итого получаем 10 ) и идём так же по 2-му ярусу, присваивая
символам  коды от 10 до 11 (если бы не было символов на 1-м яру─
се,то мы перебирали бы коды 00, 01, 10, 11 ). Допустим,что мы не 
нашли  на  2-м  ярусе ничего. А наш заготовленный код, как я уже
говорил, 10. Приписываем к нему нолик, идём на следующий ярус...
И т.д. Можно начинать с 15-го яруса и перебирать коды, начиная с
111111111111111. Результат  будет  тот же, потому что наш массив 
длин  символов  взят  не  с потолка - ведь  мы строили полностью
забитое дерево, а значит, все коды обязательно заняты. ZXRar, во
всяком случае, начинает с 15-го.

                               3.

   Стратегий упаковки (т.е. стратегий выбора оптимального разби─
ения текста на "лоскутки") существует несколько.
   Самая простая реализована во всех спектрумовских упаковщиках,
кроме, наверно, RIP (например, она  есть  в ZXRar: режим Fast ).
Стратегия  такова. Ищем  внутри окна (допустим, ищем от текущего
указателя назад, всё дальше и дальше) вхождение подстроки, лежа─
щей под указателем. Допустим, нашли мы его на расстоянии disp, а
совпало  в этом вхождении N символов. Запоминаем этот результат.
Ищем следующее вхождение.Смотрим,ЛУЧШЕ ли оно,чем уже найденное.
Понятие  "лучшести"  для  упаковщиков с фиксированными деревьями
совершенно  однозначно: меньше  бит  нужно для кодирования такой
ссылки  (хорошо)  или больше (плохо)? Для упаковщиков типа RIP и
RAR ситуация сложнее. Во-первых, ясно,что при нашем поиске назад 
нахождение ссылки (вхождения) с той же длиной,какую уже находили
(N), ничего для упаковки не даёт,ибо из двух ссылок равной длины 
(N) выгоднее взять ту,в которой более близкое смещение. Аналоги─ 
чно для ссылок,у которых N ещё меньше. О ссылках длиной 2 вообще
разговор отдельный. Во-вторых, считаем, что увеличение длины (N)
на  2 символа - это  выгодно (хотя, строго говоря, это не всегда
так).Затем (в-третьих) после некоторых экспериментов выясняется,
что  увеличивать  длину  ссылки на 1 выгодно, только если старая
ссылка  имела  большой  disp. Точнее: после  ссылки со смещением
#ff00..#ffff - если новая ссылка не дальше,чем на #f400; а после 
ссылки со смещением  #fe00..#feff - если новая ссылка не дальше,
чем на #e800.
   После  нахождения лучшей ссылки мы должны не только запомнить
саму ссылку в LZ-потоке,но ещё и дополнить хэш-таблицу и таблицу
ключей  для  каждого из символов найденной строки. Если же мы не
нашли  хорошей ссылки и предпочли закодировать символ, то допол─
нить таблицы нужно только для одного текущего байта и только для
одного  ключа, соответствующего  этому месту текста (т.е. ключа,
формируемого  из текущего байта и одного-двух следующих). Старый
адрес, лежавший в таблице ключей по этому ключу, мы должны поло─
жить  в хэш-таблицу  по текущему адресу, а сам текущий адрес - в
то самое место таблицы ключей.Процедура поиска Дмитрия Пьянкова,
переделанная  мною  для  ZXRar, обновляет эту таблицу для одного
текущего  адреса  (см. на  входе и выходе в процедуру). Но можно
сделать это и снаружи процедуры.
   Следующая  стратегия  применяется в пцшной библиотеке Zlib, а
также  в ZXRar (может быть, и в пцшном  Rar ) в режиме Best. Это
"Lazy evaluation". Суть стратегии в том, что, найдя ссылку,мы её 
не сразу вносим в поток, а сперва пробуем посмотреть,что получи─
тся, если мы закодируем текущий символ как символ,а ссылку будем
искать  со следующего байта. Сравнивая две найденные оптимальные
ссылки (одна  от текущего указателя, другая - от следующего бай─
та),принимаем решение,какая из них выгоднее. Может быть,выгоднее
2-я. Что значит "выгоднее" в этом случае? Чешем в затылке и раз─
биваем диапазон всех возможных disp на поддиапазоны, для каждого
из  которых методом научного тыка находим максимальный disp, ко─
торый даст выигрыш при увеличении длины (N) на 1 символ. В ZXRar
до  последних  версий  был настройщик, в котором клиент мог было
подбирать эти пределы для собственного развлечения,но никто,нас─
колько я знаю, этим развлекаться не стал. Поэтому настройщик уб─
ран.Во всяком случае,настройки для метода Rar (для естественного
для него разбиения на диапазоны) приведены в help'е к ZXRar:
──────────────────────────────────────────────────────────────── 
Настройки: 

Верхние две - границы,выше которых разрешается увеличивать длину 
ссылки  на  единицу (в главном цикле) после нахождения ссылок со 
смещением  #ffxx  и #fexx соответственно. Увеличение на 2, 3,... 
происходит без вопросов, так как выгодно. 

Остальные 15 - границы,выше которых разрешается увеличивать дли─ 
ну ссылки на единицу (в lazy evaluation, только для режима best) 
 после нахождения ссылок в диапазонах: 
                           #ff80-#ffff
                           #ff00-#ff7f
                           #fe80-#feff
                           #fe00-#fe7f
                              #fdxx
                              #fcxx
                           #fa00-#fbff
                           #f800-#f9ff
                           #f400-#f7ff
                           #f000-#f3ff
                           #e800-#efff
                           #e000-#e7ff
                           #d000-#dfff
                           #c000-#cfff
                          #a000-#bfff
Учтите, что  при пересечении границы #e000 сдвигается кодируемая 
длина.  Т. е. неизвестно, какую  ссылку  закодировать  выгоднее: 
(#dxxx,5) или (#exxx,4). 
 Старые настройки (до 07-й версии): 
       F0 E8 FE F8 F4 F4 FA FA F8 F4 F0 E8 E0 D0 C0 A0 80
 Новые настройки: 
       F4 F0 FD F4 F0 F0 FA FA F8 F4 F0 E8 E0 D0 C0 A0 80
──────────────────────────────────────────────────────────────── 
   Для RIP диапазоны кодируются так же, поэтому разбиение анало─
гично, и выгоднейшие настройки, видимо, будут близки к этим.
   Сложно сочетать этот метод с хэшированием: приходится восста─
навливать  состояние таблиц после 2-го поиска, если 1-й оказался
выгоднее (ведь дальше выполняется процедура обновления таблиц по
всем символам 1-й ссылки,кроме 1-го! А 2-й как раз туда входит). 
Точнее  говоря, нужно  восстановить  таблицу переходов по ключам
(поиск  занёс туда  текущий  адрес). Хотя поиск ещё занёс старый
адрес, бывший  там, в хэш-таблицу, но  никакого  влияния  это не
оказывает:его всё равно пришлось бы туда занести по самой логике
составления  хэш-таблицы. За обновление таблиц для всех символов
ссылки, кроме 1-го, в ZXRar отвечает цикл FILPO1.
   Стратегия Lazy evaluation  в 1.5Ў2 раза медленнее обычной, но
даёт заметный выигрыш в упаковке.
   Лучшая  стратегия, "Оптимальный LZH", описана  в IG#6. На  ZX
она пока нигде не реализована.
   Обращаю внимание! Распаковщику абсолютно не важно,какой стра─
тегией пользовался архиватор, разница - только в размере архива!
Это  замечание приходится делать, потому что есть люди, путающие
стратегию с методом сжатия (см. об этом в журнале iS-Files ##1 и
3 ). А раз есть такие люди, то,вероятно,есть и источник подобной 
дезинформации. Собственно  говоря, такие  люди тоже представляют
из себя источник дезинформации - для своих читателей.

                               4.

   Следует  сказать немного слов и о том, как создать сам архив,
точнее, содержащий его файл с заголовками.
   Когда от пользователя получена команда на упаковку, наша про─
грамма  должна  проверить  наличие  архива с указанным именем на
диске. Если таковой отсутствует, то нам, по логике вещей,следует
его создать (коротенький файл, состоящий только из заголовка ар─
хива). Если его создать нельзя или же он есть,но не в конце дис─
ка,то самый простой выход - ругнуться и перейти в начальную точ─
ку программы (показ каталога и т.п.). Если его создать можно или
он  уже есть в конце диска, то надо продолжить операцию. Не воз─
браняется  и стереть  одноимённый архив, создав при этом новый в
конце диска. Переносить же старый архив в конец диска - сомните─
льное  удовольствие, поскольку  архивы бывают большие, а дискета
не  резиновая. Продолжая  размышление, можем  предложить создать
новый  сателлит старого архива (сателлит - файл с тем же именем,
но с изменённой  1-й буквой расширения: 0, 1, 2 и т.д., рассмат─ 
риваемый TR-DOS-программами как продолжение предыдущего файла) с 
отрывом от него,хотя обрабатывать такие разделённые куски архива
будет не очень просто. Отдельный разговор - упаковка на HDD, там
можно развернуться во всю силу.
   Для поиска файла на диске  TR-DOS предоставляет функцию #3d13
C=#A, она  возвращает в регистре C номер элемента каталога, сов─ 
падающего с заданным (#5cdd-e5) или #FF, если такого нет.
   Как создать файл? Есть 2 принципиально различных способа. 1-й
опять-таки  предоставляет  TR-DOS: функция #3d13 C=#B, HL= адрес
начала файла в памяти, DE= длина. 2-й - ручное формирование дес─
криптора в каталоге. Номер этого дескриптора берём из ячейки #e4
системного сектора (здесь и далее - 8-й сектор 0-й дорожки, счи─
тая оба числа с нуля),сектор и дорожку - из #e1/2. После ручного
создания  дескриптора  следует  записать  вслед за ним байт #0 и
исправить три значения в системном секторе: free (#e5/6), первый
свободный сектор и его дорожка (#e1/2), количество файлов (#e4). 
   Теперь внимание! Поскольку  в наш архив могут попадать упако─
ванные  блоки  длиннее  объёма непрерывной памяти, то дописывать
файл нам обязательно придётся по частям, верно? Значит,нам нужна
подпрограмма  записи байта в "выходной поток", которая будет пи─
сать в буфер памяти,пока он не переполнится,а когда переполнится
- сваливать его весь на дискету (и переустановить указатель,ука─
зывающий, в  какое  место памяти писать, на начало нашего буфера 
памяти). При  окончании же упаковки - выгружать ту часть буфера, 
которая заполнена (если там действительно что-то заполнено. Выг─
ружать 0 байт бессмысленно), после чего заново сформировать дес─ 
крипторЫ файлОВ (!) и системный сектор. Почему множественное чи─
сло? Потому  что архив при добавлении нового блока мог превысить
255 секторов (или 255*N секторов, смотря  по числу уже имевшихся 
кусков). В его обработке есть опять-таки два варианта: либо счи─
тать за начало файла тот сателлит (кусок), которые был последним
на момент  начала упаковки, либо считать за оное начало действи─
тельное  начало  файла. В последнем случае перед созданием новых
дескрипторов нужно просмотреть все старые.
   Беда ещё такая, что  в нашем архиве, разбитом на куски по 255
секторов, мы априорно не знаем расширение последнего куска. Факт
наличия  архива-то мы определить можем, а вот спозиционироваться
на последний кусок - уже проблемы...Всё-таки нужен ручной поиск.
   Что служит начальным  содержимым буфера? Правильно, служит им
последний  недозаполненный сектор архива, который мы предварите─
льно считаем с диска. Если мы архив создаём, то читать не надо -
этот недозаполненный сектор мы сами только что и записали, а со─
держит он заголовок архива.
   В ZXRar всё это организовано несколько сложнее из нужд скоро─
сти. Но  для начала всё равно пришлось писать медленный вариант,
иначе просто невозможно отладить программу.
   Обработку  переполнения  диска можно организовать по-всякому,
на  любителя. Простейший  вариант - запомнить  положение стека в
начальной точке программы (см. про неё выше) и вываливаться туда
при обнаружении ситуации переполнения. При этом архив, вероятно,
будет  стёрт, а может, и не будет, зависит от того, в каком сос─
тоянии вы оставляли 0-ю дорожку перед упаковкой блока.

                               5.

   Немного  отходя от темы, сделаю небольшое замечание по поводу
swap'а  при  распаковке. Одним  словом, как  это  реализовано  в
ZXUnRar? 
 ──────────────────────────────────────────────────────────────── 
   Подгрузка  с диска  идёт  через LOADBLK (это подгрузка самого
архива, к свапу  она не относится). Свап реализован в нескольких 
 циклах типа 
         out frPG
         ld a,(de)
         out curPG
         ld (hl),a
         inc e
         call z,restore
         inc l
         call z,store
   Это операция копирования  подстроки выходного файла откуда-то
сзади  в текущий  адрес. Здесь  DE - это  входной адрес. В одном 
случае  он  лежит в самом выходном буфере, а в другом - в буфере 
подгрузки. (Трек-сектор для подгрузки вычисляется мудрёно,чем вы 
 можете полюбоваться в исходнике ZXUnRar, я сам там путаюсь :)) 
   restore  занимается  подгрузкой  следующего сектора из свопа.
store увеличивает H, и если оно превысило предел (выходной буфер 
переполнился), записывает  весь  буфер  в файл. Свопом, понятное 
дело, является сам этот самый выходной файл. 
──────────────────────────────────────────────────────────────── 
   Желаю  вам  приятного  архиваторописания  ;)  Включайте  свои
аласмы - и в путь...

A. Coder