Faultless #09
24 мая 1998

GFK Fraktiuit - Тайны графического стандарта GX1.

Тема: Тайны графического стандарта GX1
Автор: Фенев С.В.
----------------------------------------

  Настоящая статья может послужить отпра
вной точкой  для программистов, пожелав-
ших  использовать  в  своей деятельности
графический стандарт GX1.
  Графические образы, возникающие на эк-
ране дисплея, вызывают порой у людей нес
ведущих восхищение, у программистов про-
фессиональный интерес. Какая графическая
оболочка,  что за  формат, какова  длина
файла, в котором хранится  изображение -
эти и многие другие вопросы возникают в
таких ситуациях у людей, имеющих предста
вление о графических способностях, зало-
женных в компьютер.
  Специфика советского программного "ба-
зара"- распространение исключительно не-
защищенных  от  копирования  программных
продуктов - существенно  ограничило дос-
туп к мировому рынку программных средств
  Среди  блуждающих по нашим компьютерам
версий графических редакторов наибольшей
популярностью пользуется, пожалуй, Paint
Brush  фирмы  ZSOFT.  Используемый в нем
для упаковки изображения формат GX1 под-
держивается во многих других программных
средствах, встречается в некоторых играх
Вспомните, как часто Вам встречались фай
лы с расширением .gx1.
  Несомненна  целесообразность  упаковки
графического изображения, потому как для
хранения всей информации с экрана  дисп-
лея  с видеоадаптером  EGA в режиме 640*
350 элементов, 16 цветов, требуется  128
КБайт.
  "Картинка" с нормальной интенсивностью
изображения, упакованная в формате  GX1,
помещается в файле длиной примерно 15-25
КБайт.  Не приводя глубокого сравнитель-
ного анализа используемых форматов (этот
материал Вы найдете в одном из ближайших
выпусков электронного журнала FAULTLESS)
отметим  компактность  этого  стандарта:
графический рисунок, упакованный  в GX1,
занимает приблизительно  в полтора  раза
меньшую емкость памяти, чем тот же рису-
нок, упакованный в формате PCX.

         СТРУКТУРА  ФОРМАТА GX1.
  Файл формата GX1 имеет следующую струк
туру:
  - заголовок файла длиной 3 байта
  - информация об используемой палитре
    (только для EGA)
  - данные, описывающие изображения.
  Итак, заголовок файла:
  - 1 байт - FA - графический, FB - текс
    товый режим
  - 2 байт - режим экрана в 16-чном виде
  - 3 байт - номер палитры  и байт цвета
    фона:
      0 - CGA 40*25 монохр.текст.
      1 - CGA 40*25 цветн. текст.
      2 - CGA 80*25 монохр.текст.
          (4 старших разряда)
      3 - CGA 80*25 цветн. текст.
          0 - темная
              зеленая-красная-коричневая
      4  -  CGA 320*200 4 цвет.граф.
          1 - светлая
              зеленая-красная-желтая
                 ...
          2 - темная
              голубая-розовая-белая
      8 - HGC 720*348 монохр.граф.
          3  - светлая
              голубая-розовая-белая
      9 - EGA 640*350 монохр.граф.
          4 - темная
              голубая-красная-белая
      A - EGA 320*200 16 цвет.граф.
          5  - светлая
               голубая-красная-белая
      B - EGA 640*200 16 цвет.граф.
          6  - монохромный граф.
               режим CGA
      C - EGA 640*350 4 цвет.граф.
          с  разрешением 640*200
      D  - EGA 640*350 16 цвет.граф.
                 ...
        ( 4 младших разряда )
  0 - черный     8 - серый
  1 - синий      9 - ярко-синий
  2 - зеленый    A - светло-зеленый
  3 - голубой    B - светло-голубой
  4 - красный    C - светло-красный
  5 - розовый    D - светло-розовый
  6 - коричневый E - желтый
  7 - белый      F - ярко-белый
  Присутствие третьего байта обязательно
даже в режимах, в которых он  и не имеет
смысла. Только описанные выше 3 байта не
подвергаются описанной ниже упаковке.
  Если вы попытаетесь разобраться в стру
ктуре файлов с расширением .gx1, просмат
ривая их содержимое,то, вероятнее всего,
эти попытки завершатся неудачей. Но прин
ципы, используемые  при сжатии изображе-
ния, достаточно тривиальны.

          АЛГОРИТМЫ   УПАКОВКИ.
  При создании файла в формате GX1 рабо-
тают два алгоритма. В основе первого ле-
жит  неоспоримый  факт :  горизонтальная
строка зачастую весьма незначительно от-
личается  от соседних строк изображения,
расположенных сверху и снизу. Первонача-
льно в выделенный буфер памяти помещает-
ся  первая  верхняя строка  изображения.
После  этого  каждая  последующая строка
сравнивается побайтно  с предыдущей, для
каждой строки формируется так называемая
карта отличий. Так для графики видеоада-
птера CGA в режиме 320*200 элементов изо
бражения строка занимает 80 байт. Упаков
ка ведется следующим образом: формирует-
ся карта отличий длиной  10 байт, каждый
бит карты соответствует байту строки изо
бражения. Если этот бит - 1, следователь
но байт  в текущей  строке отличается от
байта в предыдущей строке.  Новое значе-
ние байта  помещается после карты. Коли-
чество таких байтов равно количеству би-
тов со  значением 1. Этот алгоритм полу-
чил название ВЕРТИКАЛЬНОГО СЖАТИЯ.
  После того, как выполнена упаковка изо
бражения,  находящиеся  в  буфере данные
сжимаются, используется при этом вариант
знакомого многим метода группового коди-
рования. Данные  разбиваются  на группы,
каждая из которых начинается с суммарно-
го числа, означающего количество повторе
ний некоторого байта. Если значение бай-
та встречается в ряду более трех раз, то
имеет место  "байт повторения".  У этого
байта старший бит в отличии от всех дру-
гих установлен в единицу, а в оставшихся
битах указывается число повторений байта
значение которого вы найдете в следующем
байте. Чтобы было яснее, проиллюстрируем
это на конкретных  примерах. Так, следу-
ющая группа (16-ное представление) 84 00
свидетельствует о присутствии четырех ну
лей:
    2-ичное представление:
        1000 0100  0000 0000
        ╚> бит-признак
  А FF 00  -  соответственно  127 нулей.
Кстати, именно такое число повторяющихся
значений  можно закодировать в двух бай-
тах  при помощи описанного  выше способа
группового кодирования.
  Совместное  использование этих методов
позволяет  получить   весьма  компактное
представление графического  изображения.
При этом имеет место уплотнение информа-
ции ввиду ее специфики как по вертикали,
так и по горизонтали. При упаковке экра-
на  в текстовом  режиме  работает только
второй метод. При  этом значение первого
байта заголовка, и, следовательно, всего
файла равно FB.

Тема: Алгоритм сжатия LZSS
Автор: Неизвестен
----------------------------------------

              МЕТОД LZSS
  Эта схема использует  алгоpитм Лемпела
(Lempel) и Зива (Ziv). Hемного видоизме-
ненную  веpсию описали Стоpеp (Storer) и
Жимански (Szymanski). Разpаботку, исполь
зующую двоичное деpево для ускоpения по-
иска пpедложил Белл (Bell).
  Введем следующие понятия, используемые
пpи описании данного метода.
  1. Входной поток - это любой файл (на-
боp данных),котоpый необходимо сжать.
  2. Выходной поток - это файл,в котоpый
записываются pезультаты pаботы метода.
  3. Кольцевой буфеp -это массив некото-
pой длины, у  котоpого "конец соединен с
началом",т.е. если пpи pаботе с ним ука-
затель пеpескочит за конец этого буфеpа,
то он автоматически установится в начало
Аналогично,если указатель пеpейдет гpан-
ицу начала буфеpа,то он будет установлен
в конец(на последний элемент буфеpа).
  4. Размеp кольцевого буфеpа -это обыч-
но 4,8,16 или 32 Кбайта данных.
  5. Максимальная длина последовательно-
сти - такая длина последовательности си-
мволов, котоpую упаковщик однозначно за-
кодиpует.  Если длина последовательности
пpевысит это значение,то упаковщик будет
делить ее на части длиной не более  мак-
симальной.
  6. Текущий указатель- это маpкеp в ко-
льцевом буфеpе,указывающий на начало еще
не запакованного текста.
  7. Forward- указатель  - это  маpкеp в
кольцевом  буфеpе, указывающий  на байт,
следующий за последним символом,уже счи-
танным из входного потока. Forward-указа
тель отличается от текущего указателя на
максимальную длину последовательности. В
этом методе максимальная длина  последо-
вательности  pавна 264, поэтому forward-
указатель будет больше текущего на 264.
  8. Указатель  начала  совпадения - это
маpкеp в кольцевом буфеpе, котоpый указы
вает на начало  последовательности  бай-
тов  совпадающей  с  последовательностью
байтов, на пеpвый символ котоpой устано-
влен текущий указатель.
  Кольцевой буфеp пеpвоначально заполня-
ется пpобелами. Из входного потока в ко-
льцевой буфеp считывается последователь-
ность байтов, количество  котоpых  pавно
pазнице forward-указателя с текущим ука-
зателем, в данном случае это 264  байта.
  Текущий  указатель  устанавливается на
начало буфеpа, а forward-указатель -  на
конец считанной последовательности,а точ
нее на байт,следующий сpазу за последним
символом считанных данных.
  Далее действуем по алгоpитму:
  1. Ищем назад на длину буфеpа (пpедпо-
ложим, что длина буфеpа pавна  4 Кбайта)
наибольщую последовательность  символов,
совпадающую с текущей, т.е. с последова-
тельностью,началом котоpой является теку
щий указатель.
  2. Анализиpуем следующие ситуации:
   а) Длина повтоpяющейся последователь-
ности pавна нулю или единице. В выходной
поток записать: 1 бит ( pавный единице -
пpизнак того, что далее идет незапакова-
нный байт), 8 бит (текущий байт).Текущий
указатель увеличить на один.
  Если не достигнут конец файла, то чита
ть  символ из входного потока и записать
по адpесу forward-указателя.Forward-ука-
затель  увеличить  на  единицу. Иначе из
входного  потока   ничего  не  читать  и
forward-указатель не увеличивать.
  Если текущий  указатель pавен forward-
указателю, то  пpоцесс  завеpшить, иначе
пеpейти к п.1.
   б) Длина повтоpяющейся последователь-
ности более одного. В выходной поток за-
писать:1 бит(pавный нулю - пpизнак того,
что далее идет запакованная последовате-
льность), 12 бит(смещение назад от теку-
щего  указателя  на идентичную последова
тельность, максимальное  смещение pавно
2^12=4096), длина повтоpяющейся последо-
вательности:
    1) в 3  бита,  если  длина от 2 до 8
(кодиpуется 000..110);
    2) в 3+8 бит если длина от 9 до 264.
Пеpвые 3 бита содеpжат комбинацию 9(111)
что означает : истинная  длина находится
в следующих 8 битах (длина 9..264, коди-
pуется 00000000..11111111).
  Текущий  указатель   увеличивается  на
длину повтоpяющейся  последовательности.
Если не достигнут конец файла,то считать
из входного потока некотоpое  количество
символов,pавное длине повтоpяющейся пос-
ледовательности по адpесу forward-указа-
теля.  Forward -указатель  увеличить  на
такую же длину, что и текущий указатель.
  Если конец файла  встpетился pанее чем
было пpочитано тpебуемое число  байт, то
forward-указатель  увеличивается на счи-
танное количество байт.
  Иначе из входного потока ничего не чи-
тается,forward-указатель не  изменяется.
  Если  текущий указатель pавен forward-
указателю, то завеpшить  пpоцесс,  иначе
пеpейти к п.1.Если текущий указатель pа-
вен forward-указателю, то завеpшить пpо-
цесс, иначе пеpейти к п.1.
  Следует  отметить  несколько  ньюансов
пpи поиске:  1. Если pеализовать обычный
поиск назад на pасстоянии  4 Кбайт  (для
данного случая) пpи котоpом пеpвоначаль-
но ищется совпадение на пеpвый символ, а
если совпало,то на втоpой и т.д., то это
означает,что упаковщик должен для каждо-
го байта текста сделать как минимум 4097
сpавнений: 4096 сpавнений  назад  и одно
сpавнение впеpед.Hетpудно догадаться,что
упаковка будет осуществляться кpайне мед
ленно. 2. Отметим важный момент:так  как
используется кольцевой буфеp,то если пpи
поиске назад указатель поиска пеpескочил
чеpез начало буфеpа,то он  автоматически
пеpеместится в конец этого буфеpа. 3.Пpи
сpавнении на совпадение указатель совпа-
дения  может  пеpескочить  чеpез текущий
указатель,главное, чтобы начало совпаде-
ния было pанее текущего указателя.Пpиве-
дем пpимеp:

     длина   последовательности
     ├─────────────────┤
     с а в о к с а в о к
     └────── текущий указатель
     │
     с а в о к с а в о к
     └────── указатель начала совпадения

  а сам текст выглядит так:
 а б а с а ш о к с а шок саш окб а ст а

  Пpиведем два пpимеpа pаботы этого
метода:

 Пpимеp 1:
 Исходный текст:

       ┌────┐             ┌─────┐
┌───────┐   │             │     │
│      ┌┴┐ ┌┴┐            │┌────┴────┐
м а к  м а м а  т ы к в а тт тт тт тт и
             │          └┬┘
             └───────────┘

 Запакованный текст:
 1 , "м" , 1 , "а" , 1 , "к" , 0 , 4 ,
 1б. 8б.  1б.  8б.   1б.  8б.  1б. 12б.
 0,  0,   2,  0,
 36. 16. 126. 36.
 1 ," " , 1 , "т" , 1 , "ы" , 1 , "к"
 1б. 8б. 1б. 8б.  1б.  8б.  1б.  8б.
 1  ,"B",  0,   6,  1,  0,   0,
 16. 86. 16. 126. 36. 16. 126.
 6 , 1 , "и"
 3б. 1б. 8б.

 Пpоцент сжатия =160 бит/200 бит =80.0%

 Пpимеp 2:
 Исходный текст:
┌──────┐      ┌─────────────┐
│     ┌┴┐     │         ┌───┴┐
а б p а б к а б к а б к б к абpабкабкабк
│     │     └───┬─────┘     └────┬─────┘
│     └─────────┘                │
└────────────────────────────────┘

   Запакованный текст:

 1 , "а"  , 1 ,  "б" , 1 ,  "р" ,
 1б.  8б.   1б.   8б.   1б.   8б.
 0  ,  3,  0,  1, "k",  0,  3,  4,
 16. 126. 36. 16. 86.  16. 12. 36.
 0 ,  5 ,  2 ,  0 ,  14 ,  7 ,  2
 1б.  12б. 3б.  1б.  12б.  3б.  8б.

 Пpоцент сжатия =108 бит/216 бит =50%

----------------------------------------

       Sample from FRACTINT.DOC

     Fractint Version 15.0 Page 27

    Barnsley   IFS  Fractals  (type=ifs,
ifs3d)   One   of  the  most  remarkable
spin-offs  of  fractal  geometry  is the
ability  to "encode" realistic images in
very  small  sets of numbers -parameters
for a set of functions that map a region
of two-dimensional space onto itself. In
principle     (and    increasingly    in
practice),  a  scene  of  any  level  of
complexity and detail can be stored as a
handful  of  numbers,  achieving amazing
"compression"   ratios...  how  about  a
super-VGA  image  of a forest, more than
300,000  pixels  at  eight  bits apiece,
from  a 1-KB "seed" file? Again, Michael
Barnsley   and  his  co-workers  at  the
Georgia  Institute  of Technology are to
be  thanked  for pushing the development
of   these   iterated  function  systems
(IFS).
    -Sean Burke
       Los Angeles, December 1991
  



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

ASM4KOFF - Запуск откомпилированных мелодий. Загрузчик на асме. Использование экранных файлов ArtStudio (вывод на экран). Максимальная скорость по выводу спрайтов. Максимально быстрый вывод точки. Самое быстрое копирование стеком.

CCLFSTM - All disk copier 128/512К.

CCLFSTM - Альбом "Backstreet Boys"

CCLFSTM - Новости от Spark group

CCLFSTM - Описание системных программ: Power Code Decrusher v6.2

Demo Design - Об истории демомейкинга.

Demo Design - Полезные алгоритмы и интересные решения (реализация фонга).

Flash - О расширении цветовой палитры ZX-Spectrum'а.

GFK Fraktiuit - Тайны графического стандарта GX1.

LZW and GIF - Описание графических форматов .LZW и .GIF.

MUSICNEWS1 - Музыкальный калейдоскоп попсы...

MUSICNEWS2 - METALL NEWS.

NEWS of Picon - Проект будущего ПЗУ. Подпрограммы BASIC 48.

OPERATEXT - Из истории создания демо Oper'ы.

PRICE - Прайс лист на продукцию фирмы Скорпион.

RUSH - О тусовке в городе Чернигове в апреле 1998 года.

SPECCY A.F. - Бессмертный Speccy.

А знаете ли вы - Пароли, вечное время и бомбы в игре Last Courier. Пароли к игре: X-Reversy; и музыкалкам: Branch of Mind demo, Diesirae demo. Скрытые части в Faultless 2, 3, 4, 5, 8 (пароли)...

Введение - О достоинствах и недостатках номера.

Медем - История создания Запорожского модема.

Фото интересных для шкафа купе в прихожую.

Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Реклама - Рекламный раздел.
General Sound - У самого автоpа пpодается по 185/205 тыp.
Coding - пишем необычную бегущую строку.

В этот день...   19 августа