Форматы упакованных данных на 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, где это про-
исходит наоборот. Но об этом будет написа-
но отдельно.
А. Кодер
