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

<b>GFK Fraktiuit</b> - Тайны графического стандарта 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

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