Odyssey Magazine #00 11 декабря 1996

Программирование

System - IBM: GIF - FORMAT: description of the graphic format (GIF).

  Now many are committed to
shake their schedule with IBM, the same who do
can not, try to learn, but how
information is not always dense.

   We decided to bring to your attention
description of the graphic format of GIF.

   And in the future this topic, we will also try to pay 
attention. 



              G I F (tm)

   Graphics Interchange Format (tm)

     (Format Graphic Exchange)


   The standard definition of the mechanism

      for storing and transmitting

   Raster graphics


             June 15, 1987

   (C) CompuServe Incorporated, 1987

          All rights reserved


   When copying this document
information contained therein is available to computer users 
without licensing restrictions 


   GIF and 'Graphics Interchange Format'
trademark of CompuServe,
Incorporated. an H'R Block Company 5000
Arlington Centre Blvd. Columbus, Ohio
43220

                         (614) 457-8600



      Translated from the English language made by AS 
Samotohinym Institute of Applied Mathematics of the USSR 


        Moscow, November 1990


        Graphic description of the format
exchange (GIF)



               INTRODUCTION


     'GIF' (tm) - a standard company
CompuServe to determine the raster
color images. This format allows you to highlight to different 
hardware graphics quality images with higher resolution and

implies a mechanism for exchanging and flashing images. 
Described in this document image format was designed to support 
current and future imaging technology and will continue to 
serve as a basis for future graphics products CompuServe.



     The main task of this paper is to provide developers the 
necessary technical information to write the decoders and 
encoders GIF. Therefore, the document uses the terminology 
associated with general issues of graphics and programming. 


     The first section of this document
describes the data format GIF and its components in the annex 
to the decoders GIF, regardless of whether they are

a separate program or part of a package
communication. Appendix B refers to the decoder is part of the 
communication and describes the protocol required for

entry and the existence of the regime GIF and answering a 
series of specific questions. Glossary in Appendix A defines 
certain terms used in the document. Appendix C provides a 
detailed explanation of how the graphics themselves pictures 
are packed in a sequence of bytes. 


    Defining Data Format GIF


          GENERAL FILE FORMAT



       Identifier GIF



        Descriptor screen



   Global Color Table

. . . . . .


     Deskirptor image



   Local color table. Repeats

                       from 1 to n times


        Raster data

. . . . . .

   Terminator GIF



           IDENTIFIER GIF


     The presence of the file special
"Signature" indicates that the subsequent
data are indeed flow
image data in the format of GIF. This
"Signature" consists of the following six
Character:

             G I F 7 August a
The last three characters '87a 'may
regarded as a version number for
given a specific definition of GIF and
will be used later as a reference to a document describing
GIF depending on the version number.


           Descriptors SCREEN


     Screen Descriptor describes general
parameters for all subsequent images in the format of GIF. It 
determines the size of the image space or logical screen 
required, the existence of information about the color table 
and the "depth" of the screen. This information is stored as a 
series of 8-bit bytes, as shown below.



              Bits
 7 6 5 4 3 2 1 0 Number of bytes


                  1
 The width of the screen width in pixels of the raster.

                  2 (first LSB)


                  3
 The height of the screen height in pixels of the raster.

                  4 (snachalo LSB)

                    M = 1, for

                    descriptor
M cr 0 pixel 5 should be global
                    ball-table

   background 6 colors cr +1 =

                    the number of bits
0 0 0 0 0 0 0 0 7 color again
                    solutions pixel +1
= Number of bits per pixel in the image background =
color index screen background (the color is determined from the 
global color table or from the table by default)



     The width and height of the logical screen
may be larger than the physical
screen. Method of flashing images
larger than the size of the physical display
implementation dependent and can take advantage of specific 
hardware (eg, scrolling windows in the Macintosh scrolling 
windows). Otherwise case, the image will be truncated to

edges of the screen.


     The value of 'pixel' also defines a
the number of colors in the image. Range
values ​​of the 'pixel' is 0 to 7,
which corresponds to 1 to 8 bits. This
translated into a range from 2 (black and white images) to 256 
colors. Bit 3 in Byte 5 is reserved for future

definitions and must be zero.


       GLOBAL COLOR CHART


     Global color table is
optional and is recommended for
images that require precise color reproduction. The existence 
of this table indicates a 'M' in Byte 5 descriptor screen. 
Color table may also be associated with each image in GIF-file, 
which will be described later. Usually, however, this global

table will be used, because of the limitations of the present
time in the equipment available. Flag
'M' to handle a specific image is usually equal to 0. If the 
global color table is present, it's definition immediately 
follows the handle to the screen. The number of elements

color table following the screen descriptor is 2 ** (number of 
bits per pixel) where each element consists of three

byte values ​​which describe the relative intensity of red, 
green and blue. Structure of the block of color table: 


      Bits
 7 6 5 4 3 2 1 0 Byte #

intensity. red a red value

                      for color 0
intensity. 2 The value of green green

                      for color 0
intensity. 3 The value of blue blue

                      for color 0
intensity. 4 The value of red red

                      for color 1
intensity. green 5 green value

                      for color 1
intensity. Blue 6 Blue value

                      for color 1
:: (Continued

           for the other colors)

     Get the value of each pixel lights up when the image is
correspond to the closest available
color from the color table display. Color components are
the relative intensity of
zero (0) to full (255). White
can be represented as
(255,255,255), as black as (0,0,0) and
as yellow (180,180,0). Lights up when the displays that support
less than 8 bits per color component, used high-order bits. 
When you create a elements of the GIF color table on the 
equipment that supports at least 8 bits component, the value of 
the hardware components must be converted to 8-bit format using 
the following formula: 


   <Znachenie_v_tablitse> =  * 255 / (2 ** 
 -1) 


     This ensures accurate translation
colors for all displays. If you are creating GIF images on the 
equipment without features a color palette should

be created at a fixed palette
basis of the available colors for this equipment. If you 
specify no global color table, color

default table is generated internally, so that each color
index is a hardware color index modulo <n>, where <n> - number 
dos 

        Descriptors IMAGES


     Descriptor of the image determines
actual locations and sizes
subsequent images within
space defined in the descriptor screen. Also determined by the 
flag indicating the presence of local

lookup table of colors and definition
sequence of flashing pixels. Each descriptor begins with an 
image-splitter image. The role of the separator image is simply 
to synchronize at the entrance to handle images. This is 
desirable if the GIF-file consists of more than one image. This 
symbol defined as 0x2C hex

or ',' (comma). Once this symbol is encountered between images,
immediately followed by the image descriptor.


     Any character that is encountered between
end of the previous image and the delimiter character image is 
ignored. This will allow for subsequent modifications to allow 
the presence of GIF multiple formats and properly ignore their 
old decoders. 


      Bits
 7 6 5 4 3 2 1 0 Byte #

0 0 1 0 1 1 0 0 1 ',' - symbol
                    separator image.

                  2 First Images

  The left edge in pixels relative to
                  3 with respect to the left edge

                   screen (the first LSB)

                  4

  The upper edge of Home Image

                  5c piks.otnositelno

                    verh.kraya screen

                  6 (first LSB)

     Width Width of image

                  7 pixels

                    (Snaalo LSB)

                  8

     Height Height izobr.v pix

                  9 (first LSB)

M I 0 0 0 10 pixel

 M = 0 - Use global table
colors, ignore 'pixel'
 M = 1 - The following is a local table
colors, use 'pixel'
 I = 0 - The image is formatted
sequential order
 I = 1 - The image is formatted
Order weave
 pixel +1 - the number of bits per pixel in this
image


     Description of the position and size of the screen should 
be placed within the matrix defined in the descriptor of the 
screen. On the other hand, there is no need to image completely 
fills the screen. 


        LOCAL COLOR CHART


     Local color table is optional and defined here for future
use. If the bit is set 'M'
byte 10 in the handle images,
followed by the image descriptor to be a local color table, 
which applies only to a subsequent image. After processing the 
image color table should be brought to that which was 
determined after the descriptor screen. Note that the field 
'pixel' byte 10 in the image descriptor is used only if

specify a local color table. She
determines not only the pixel size
(Number of bits in it), but the number of elements
follow the color table. The number of bits per pixel and should 
be restored to that value which has been defined in the 
descriptor screen, after how to finish processing the image.



           Raster data


     The format of the image itself is defined as a series of 
values ​​of the numbers of pixels that form the image. Pixels 
are stored sequentially from left to right along the lines of 
the image. By default row is written sequentially, top to 
bottom. In that case, if the bit is set 'I' in byte 10

handle images, then the order
rows when recording the image corresponds to four bushing 
process. At first pass, each written

8th row, starting with top row
image window. The second pass
recorded every 8th row, starting from the fifth row from the 
top. In the third pass written every fourth row beginning with 
the third row of the window. The fourth pass completes the 
picture, recording every second line, starting

the second row from the top. Below is a graphic description of 
this process. 


   Image

   Pp. Proh.1 Proh.2 Proh.3 Proh.4


     0 ** 1a **

     1 ** 4a **

     2 ** 3a **

     3 ** 4b **

     4 ** 2a **

     5 ** 4c **

     6 ** 3b **

     7 ** 4d **

     8 ** 1b **

     9 ** 4e **

    10 ** 3c **

    11 ** 4f **

    12 ** 2b **

   . . .


                   Result


                   ** 1a **

                   ** 4a **

                   ** 3a **

                   ** 4b **

                   ** 2a **

                   ** 4c **

                   ** 3b **

                   ** 4d **

                   ** 1b **

                   ** 4e **

                   ** 3c **

                   ** 4f **

                   ** 2b **


     Values ​​of image pixels are processed as color indices, 
indicating the existing color table. The resulting color value 
from the table, which really reproduced on the screen. These 
series color indices, of which there

shirine_izobrazheniya * vysotu_izobrazheniya,
passed through the data stream GIF images on a single value per 
pixel, compressed and packaged in accordance with the version 
of the compression algorithm LZW, as defined in Appendix C.



             TERMINATOR GIF


     In order to ensure synchronization with the end of image 
file GIF, GIF decoder must handle

ending the regime GIF on the symbol
0x3B hex or ';', which was found after the image processing. 
Under the agreement decoding software must pause and wait 
action, indicating that the user ready to continue. This may be

carriage return entered from the keyboard
or mouse click. For interactive applications, these user 
actions should be transferred to the nucleus program as a 
carriage return, so that the computational process could 
continue. Typically, a decoder program leaves the graphics mode 
and returns to the previous process.



        ADVANCED BLOCK GIF


     In order to ensure the orderly expansion of the definition 
of GIF, we need a mechanism for determining the packing within 
the data stream GIF. The said the extension was defined and 
documented by CompuServe in order to provide a managed way of 
improvements. 


     Advanced GIF unit is packed in a manner similar to the one 
used for raster data, but not compressed. The basic structure 
of the unit: 

 7 6 5 4 3 2 1 0 Byte #

0 0 1 0 0 0 0 1 1 '! " - ID

                  Extended block
 Extras. Package 2 - Advanced

                  functional

                  code (0-255)

 byte-count


                           Repeats

  function. bytes so many times

   data as

                           must
. . . . . .

0 0 0 0 0 0 0 0 null byte
                       counter

                  (Terminator block)


     Advanced GIF block can immediately precede the descriptor
image or in front of the terminator GIF.


     All GIF decoders must be able to detect the presence of an 
extended block GIF and then read it if they can not handle the 
functional code. This ensures that older decoders will be able 
to handle files GIF images in the future, though without

additional functionality.

                       Appendix A


               GLOSSARY


   Pixel - The smallest element of a graphical image. Usually 
corresponds to a single point on the graphical display. Image 
resolution usually specified in pixels. For example,

a fairly standard screen
graphical formats is 320 pixels horizontally by 200 vertically. 
Each pixel can be colored one of several colors depending on 
the capabilities of graphics hardware. 


   Raster - the horizontal pixel level representing one line of 
the image. A typical method of generating the image, since most 
samples videoborudovaniya focused on the most effective work is 
so manner.



   LSB - Abbreviation for Least Significant Byte (Jr. 
meaningfully bytes). Refers to an agreement for the two bytes

numeric value, according to which
Junior meaningfully byte precedes
more senior. Such agreement is typical for microcomputers.


   Color Table - List of Definitions
for each color used in image GIF. Desirable colors are 
converted to available colors through a table, and the color 
indices of the input images are formed Weekend color indices of 
the equipment. If GIF image specified color table

a color output pixels will be modified based on the equipment 
used and its ability to meet specified color.



    Intertwined - The method of flashing
Image GIF, which makes several passes with the conclusion of 
spaced rows of the raster, which allows visualization of total 
the entire image before all the data processed. 


    Protocol B - redistributable file transfer protocol with 
error correction, developed by CompuServe and implemented in a 
product company VIDTEX CompuServe. Such a detection mechanism

errors will be used to transfer
GIF images for interactive applications.


    LZW - perfect compression algorithm
Data is based on work done
Lempel-Ziv and Welch, which enables highly efficient 
single-pass encoding and decoding. This allows you to discover 
and highlight the image. The original article, which was 
described this method: 


   Terry A. Welch, "A Technique for
High Performance Data Compression ",
IEEE Computer, vol 17 no 6 (June 1984)


        This basic algorithm is also used in the freely 
distributed ARC utilities to compress files. Adaptation 
algorithm LZW, made for CompuServe GIF is described in the 
application w. 

NPRILOZHENIE w


     IMAGE COMPRESSION AND PACKAGING


     The flow of raster data, which
describe the actual output image can be represented as follows:

 7 6 5 4 3 2 1 0


  code size

 byte-count

    block


                          Repeats

  bytes of data many times

                          as

                          must
. . . . . .

0 0 0 0 0 0 0 0

                 ^

      zero-byte-count

     (Ends data stream)

      Converting an image from a series of pixel values ​​to 
the transmitted or store character stream involves several 
steps. Briefly, these steps are as follows:


1. Installing the package size - Specifies
number of bits needed to represent the actual data.

2. Data Compression - Compress the series of image pixels in a 
series of compression codes. 

3. Construction of a series of bytes - will take a series of 
compression codes and convert them into string of 8-bit data.


4. Packing bytes - Packing set
byte blocks, which are preceded by
character-count and withdrawal.


        INSTALLATION CODE SIZE


     The first byte in the bitmap
GIF data has a value that indicates
minimum number of bits needed
for submission for presentation
real values ​​of pixels. As
Typically it will be the same as the number of
bits of color. However, due to some limitations of the 
algorithm black and white images, which have one bit of color, 
should have a code size of 2. This value of the code size 
implies also that the compression codes must be

one bit longer.


                COMPRESSION


     LZW algorithm converts a series of
data values ​​in a series of codes that
may be by the values ​​or codes that describe a series of 
values. If use the analogy with word symbols, the output codes 
are composed of symbols and codes that describe the chain of 
characters. 

     LZW-algorithm used in GIF
algorithmically corresponds to the standard LZW algorithm with 
the following differences:


1. Defined a special code cleanup
which resets all options compression / decompression and table 
in its original state. The value of this code is 2 ** . For example, if the code size equal to 4 (the image is 4 
bits per pixel), the cleanup code is 16 (binary

10000). Clear code can appear in
anywhere in the data flow and, therefore, requires that the 
LZW-algorithm processed following codes as

allegedly began a new data stream.
Encoder should output a Clear code
as the first code in each thread
image data.

2. Defined the end of the code information, which clearly 
indicates the end of the stream image data. If you meet this 
code, LZW-processing stops. This code should be the last code

formed by the encoder for an image. The value of this code is 
<Kod_ochistki> 1. 

3. The value of the first available code
Compression is <Kod_ochistki> 2.

4. Weekend codes are of variable length, ranging from 
<kod_razmera> a bit on code to 12 bits per code. Thus the 
maximum value of the code is determined equal to 4095 (hex FFF).

Once the value of LZW-package may exceed the current code 
length, code length incremented. Packer and

unpacking of these codes should be changed to match the new
code length.


      Construction of the 8-bit byte


     Since the LZW-compression used
for GIF, creates a series of codes of variable
dlinyiyu 8-bit bytes, so that at
actually happened, or remembering
transmitted symbols. This provides additional compression of 
the image. Cheats formed in a stream of bits as s

compression.
3. Constructing images of veins 16 (binary in such a way as if 
they were packed right to left, and then selected for 8

bits for output. Considered an array of 8-bit characters in 
packaging codes of length 5 bits should be similar the 
following example: 


    byte n byte 5 byte 4

     ..... + + + ..

     and so on hhhhhggg ggfffffe ..

     ..... + + + ..


     byte 3 byte 2 byte 1

  .. + + +

  .. eeeedddd dcccccbb bbbaaaaa

  .. + + +

     Note that the physical mechanism
Packaging will be changed to the extent that
how the number of bits in the code compression, but 
conceptually it remains the same.



            PACKING BYTES


     Once the bytes are created, they
grouped into blocks for output, and
each block is preceded by a byte-count
with a value from 0 to 255. Block with a null byte-counter 
finishes flow Data for this photo. These

blocks are what is displayed on the
Indeed in the format GIF. This format
block provides additional efficiency by ensuring that allows
decoder to read the data as
required reading first byte counter, and then passing the data 
itself to image.