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

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

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

   Как я успел понять, моим статьям хвата-
ет сухости изложения. В силу этого,как мне
удалось  прикинуть, даже будучи склеенными
вместе, они не соберутся и в самую малень-
кую книжку. Возможно, это происходит из-за
того, что  я  опускаю  незаметные для себя
детали? Если так, тогда то, что я пишу,без
моей консультации не прочитать...
   Прискорбно.
   Тем  не  менее, я отважился на создание
ещё одного пространного опуса,претендующе-
го на полезность в смысле общего развития.
Не беда,если ничего в нём написанное вы не
сможете запомнить (я и сам мало что оттуда
помню, оттого  и начал записывать). Это не
стихотворение,  которое  надо  выучить  на
урок, и не похождения с мечом и бластером.
Тут просто даётся некоторая рассеянная ин-
формация  относительно возможности выраже-
ния в словах (назовём этот процесс "верба-
лизацией") некоторых структур,которые тру-
дно в определённом смысле "пощупать".Заод-
но по прочтении  читатель сможет отдалённо
представить себе сам метод анализа и,собс-
твенно,изложения такого рода структур,хотя
я, как автор,на указанном особенно не кон-
центрировался.
   Обратите также внимание,что материал не
исчерпывающ.

   Следует, помимо всего прочего, избегать
взглядов типа "а на самом деле...",особен- 
но касательно терминологии. Использованную 
терминологию я приведу здесь же, она обра- 
зована  в контексте лично моего мышления и 
может  не  соответствовать интуитивной для 
читателя,тем более если он обладает специ- 
фическим образованием в этой области.Одна- 
ко,насколько известно мне,ранее опытов по- 
добного  рода вербализации почти не произ- 
водилось, и в силу этого общепринятой тер- 
минологии не существует. Исходные же текс- 
ты, распространявшиеся на аналогичных пра- 
вах, читабельными не являются. 

    Итак, мои термины:
   disp (displacement - смещение) или dist
(distance  -  расстояние) - характеристика 
смещения  от текущей позиции выходного по- 
тока (восстанавливаемого  файла) до повто- 
ряемого  фрагмента в LZ77-основанных мето- 
дах.(Каковые методы,собственно,и состоят в 
том,чтобы время от времени копировать фра- 
гменты  откуда-то  сзади куда-то вперёд, а 
именно "под курсор",то есть в оную текущую 
позицию.)  Если перед disp я ставлю минус, 
это означает,что данная характеристика уже 
имеет  отрицательный  знак и для получения 
адреса фрагмента  ПРИБАВЛЯЕТСЯ, а не отни- 
 мается из текущего адреса. 
   dispH, dispL - старший  и младший байты
 disp. 
   puts или len - длина повторяемого фраг-
мента. Фрагмент  может копироваться поверх 
себя. Самый  типичный  такого  рода случай 
возникает  при disp=1 и сводится к повтору 
одного и того же байта. 

   За указаниями типа disp4 или len7 скры-
вается количество бит в данном числе.
 

   дерево (tree) - структура, используемая
для хранения информации о том,как двоичные 
коды различных длин представляют некий на- 
бор  символов (литералов). Рассматривались 
Фано и Хаффманом. Метод построения дерева, 
предложенный Фано,в общем случае хуже Хаф- 
фмановского, т. к. для последнего доказана 
оптимальность. По Хаффману дерево строится 
последовательным объединением двух редчай- 
ших  узлов  с суммированием их частоты для 
использования  этой  суммарной  частоты на 
последующих  объединениях.  По  Фано, если 
читателя это заинтересует, дерево строится 
последовательным разделением отсортирован- 
ного  по частотам списка литералов ПРИБЛИ- 
ЗИТЕЛЬНО ПОРОВНУ на левую (нулевую) и пра- 
вую (единичную) подветвь. Деревья же, если 
перейти к практике,могут храниться множес- 
твом  способов - указателями, ярусами  или 
 вообще неявно. 
    % - двоичное представление;
    # - шестнадцатиричное представление.
   битовый поток - данные, извлекаемые по-
 битно (например,сдвигом); 
   байтовый поток - данные,извлекаемые по-
байтно (что,очевидно,быстрее). 

   Существует  несколько способов совмест-
ного  использования  обоих типов потоков в
одном  файле  с последовательным доступом.
(Кем эта идея реализована впервые, предпо- 
ложить  трудно.) Это, например, простейший 
 способ:
  1. Из  файла  извлекается байт-буфер для
 битового потока, и указатель смещается; 
  2 и далее. Байты адресуются  указателем.
Биты же извлекают из байта-буфера, при его 
исчерпывании действуют аналогично п.1. 
   ...и его вариация,где вместо "байта-бу-
фера  битового  потока" фигурирует "слово-
буфер" (16 бит).

   В  форматах, использующих  оба потока в
смешанном  виде, важен  порядок извлечения
данных из них. Я не уточняю этот порядок в
текстах, просто пишу структуру кода именно
в нужном порядке. Т.е. если написано:
                 ─────────
   %xxxx,dispH3 - ссылка такая-то. dispL в
байтовом потоке. puts=столько-то, 
                ─────────
   то понимать следует, что сначала из би-
тового потока  считывается %xxxx,dispH3, и
уже потом из байтового - dispL.

   Как правило,биты извлекаются слева нап-
раво (7,6,... или 15,14,... ). Исключением
является компрессор RIP 0.2x, где это про-
исходит наоборот. Но об этом будет написа-
но отдельно.

                                  А. Кодер