Дикий ум - алгоритм сжатия видео - 16 цветов на точку.

<b>Дикий ум</b> - алгоритм сжатия видео - 16
цветов на точку.

Сжатие видео - цвет на точку
   Было уже много исследований по упаковке
видео  в режиме6912.Например, см. статью 
в Info Guide #7, метод  из которой годится 
даже  для  оригинального ZX Spectrum 48K и 
действительно  применялся  в демо New Wave 
48K.  Или  последние  эксперименты  DDp  с 
перегонкой  видео  про  кота  Саймона  под 
128-256K - он  паковал  поток знакомест (с
командами пропуска знакомест,очистки кадра 
и пропуска кадра) с помощью пакера MegaLZ, 
используя  распаковщик с циклическим буфе─ 
ром. 
   А вот  упаковка видео под другие видео─
режимы  Спектрумов,  в  частности, под  16 
цветов на точку ( Pentagon с известной до─ 
работкой,  ATM Turbo,  ATM Turbo 2 / 2+  и 
современные   их  реализации   на  FPGA  - 
ZX Evo baseconf,  Pentagon 2.6ббLE;  можно 
также вспомнить Sam Coupe', живущий в сво─ 
ём  отдельном мире) с годами почти не раз─ 
вивалась. 
   Первой попыткой была игра Time Gal, где
видео просто сохранялось по знакоместам, у 
каждого  из  которых были указаны экранные 
координаты. Поток  получался настолько бо─ 
льшой, что  его  невозможно было хранить в 
памяти - игра требовала CD-ROM... 
   В  этой  статье предлагается другой ме─
тод,успешно использованный в демо Personal 
Nightmare by Omega Hackers Group. 

                  * * *

Screw/OHG 

Сжатие анимации в демо Personal Nightmare 
     для экранов 320x200x16 ATM Turbo

   Вся дема Personal Nightmare писалась на
PC в IAR'е, там  же  собиралась и линкова─
лась,и проверялась на Unreal Speccy. Фина─
льная  проверка  была  на  реалах - ATM1 и
ATM2. Сжимались  все  данные на PC, там же 
происходила проверка,что всё сжато коррек─
тно.
   При сжатии анимации основной целью пре─
следовалась скорость вывода, т.к.экран за─
нимает32000 байт, при этом он организован
неудобно, в 4 плоскостях по8000 байт каж─
дая. Один байт - пиксельная пара. 4 сосед─
ние пиксельные пары располагаются последо─
вательно  в плоскостях 0,1,2,3. (Подробнее
см. в  документации на АТМ/АТМ2, например, 
http://alonecoder.nedopc.com/zx/books/
ATMHW.rar )
   Получается, что  для отрисовки горизон─
тальных линий придётся прыгать по плоскос─
тям. В принципе-то это всего лишь переклю─
чение  одного  или двух бит адреса, но это
медленно. Поэтому  было решено организовы─
вать вертикальную отрисовку. В этом случае
переход  на  следующий пиксель достигается
добавлением 40  к экранному  адресу: ведь
(320/2)/4 == 40.

   Вертикальная отрисовка умеет делать две
вещи:
1)рисовать линию вниз.
2)пропускать некоторое количество точек.
   Отрисовка происходит байтами, т.е. по 2
точки  за раз. Это хорошо для производите─
льности, но  не очень хорошо для упаковки.
Например, вот  такие  переходы  получаются
очень дорогими:

                AA
                AA
                AX<===
                XX
                XX
                XX

   Код  отрисовки выглядит следующим обра─
зом:

       LD (HL),A
       ADD HL,BC ;bc = 40
       ...
       LD (HL),A
       ADD HL,BC
       JP _обратно_

   Чтобы  отрисовать нужное количество то─
чек (или, другими словами,вертикальную ли─
нию нужной высоты) прыгаем сразу в середи─
ну этого кода,чтобы исполнить нужное коли─
чество инструкций.
   Чтобы  пропустить нужное количество то─
чек, просто  прибавляем к экранному адресу
40*количество_точек.

   Отрисовка производится во все плоскости
независимо. Т.е. отрисовали плоскость пол─
ностью - рисуем следующую.

   Первый  кадр сжимается полностью и, со─
ответственно,много "весит". Для всех оста─
льных кадров сжимаются только различия ме─
жду  кадрами. В том числе и различия между
последним  и первым кадром - чтобы заколь─
цевать анимацию,не прибегая к дорогой рас─
паковке первого кадра.
   Повторюсь, что формат сжатых данных оп─
тимизирован  под отрисовку, не под оптима─
льность сжатия. Также он очень прост, есть
где развернуться и что улучшить ещё.

   Формат:
 +0 (byte) x -сдвиг по оси X первого
столбца сжатых пикселей 
 +1 (byte) cnt -количество сжатых
столбцов (ноль означает, что распаковывать 
нечего) 
 +2 (byte) ymin -минимальная
вертикальная координата среди всех сжатых 
столбцов 
 +3 (byte) ymax -максимальная
вертикальная координата среди всех сжатых 
столбцов 

   Нетрудно видеть,что первые 4 байта опи─
сывают Bounding Box, прямоугольник,который
заключает в себя область экрана, в которую
будут распаковываться сжатые данные. Разу─
меется, не вся эта область будет изменена,
скорее  даже будет изменена очень малая её
часть. Но  будет  хотя  бы один пиксель по
каждой из границ данной области.

   Далее  идут  данные сжатых столбцов. На
каждую группу пикселей внутри одного стол─
бца тратится по 2 байта:
 +0 (byte) ctrl -управляющий байт
 +1 (byte) col -цвет отрисовываемого
столбца (обоих пикселей, из которых 
состоит этот столбец). 

   Для ctrl допустимы три варианта значе─
ний:
 OxFF -все столбцы для данной
X-координаты отрисованы. 
 >=0  -высота отрисовываемой линии-1.
Т.е. ctrl==0 означает, что рисовать будем 
линию высотой в 1 точку. 
Байт цвета появляется только если ctrl>=0. 
 <0 -пропуск линий-1.
Т.е. ctrl==0x80 означает, что пропустим 
линию высотой в 1 точку. 

   Для быстрого пропуска линий организова─
на таблица умножения на 40
(GFX_UNPACK_MULTTABLE_HIBYTE).

   Основной  проблемой при реализации этой
идеи  стало сжатие. Алгоритм надо реализо─
вывать  крайне  аккуратно. Ошибочно сжатые
данные  могут завесить распаковку и испор─
тить собой всю память.

                  * * *

   Пару  слов ещё скажу об организации са─
мой  анимации. К  самому  сжатию это имеет
опосредованное отношение, но будет полезно
для понимания приложенных исходных кодов.
   Блок  сжатых кадров имеет дескриптор, в
котором  хранится текущее состояние (адрес
следующего кадра и т.д.).
   Перед  распаковкой  очередного  кадра в
экран  я был  вынужден  копировать  сжатый
блок  из верхних  страниц, т.к. изначально
это всё  писалось под ATM1, где нет полно─
ценного диспетчера памяти.

   Описание приложенных исходников:

  -VideoModeAtmЗ20x200.h(.cpp)
Пакер на Си, сжимает как кадр целиком, так 
и междукадровый дифф. Имеет код для тесто─ 
вой распаковки:UncompressFrame/
UncompressBitplane.
LookupCompressArea  -  функция определения
X-координат Bounding Box. 
  -gfx_unpack.asm
Распаковщик и генератор таблиц/развёрнуто─ 
го кода. 

   Эти файлы к распаковке не относятся, но
показывают, как организована анимация:
  -animation.asm
Описание  дескриптора анимации и организа─ 
ция распаковки всех плоскостей. 
  -pageO.asm
Начало системного кода, размещаемого в 0-й 
странице.Описаны все рестарты (для понима─ 
ния механизма переключения экранов). 

  Все исходники  находятся в приложении к
журналу - в архивеvideo_pack.zip.