Inferno #05
30 апреля 2004

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

                                  А. Кодер



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

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 июля