ryanb@microsoft.UUCP (Danger Mouse) (08/10/90)
Part 3 of 3
- Cut here --- Cut here --- Cut here --- Cut here --- Cut here --- Cut here ---
d. Extensions and Scope. The scope of this block is the Plain Text Data
Block contained in it. This block may be modified by the Graphic Control
Extension.
e. Recommendations. The data in the Plain Text Extension is assumed to be
preformatted. The selection of font and size is left to the discretion of
the decoder. If characters less than 0x20 or greater than 0xf7 are
encountered, it is recommended that the decoder display a Space character
(0x20). The encoder should use grid and cell dimensions such that an
integral number of cells fit in the grid both horizontally as well as
vertically. For broadest compatibility, character cell dimensions should
be around 8x8 or 8x16 (width x height); consider an image for unusual
sized text.
26. Application Extension.
a. Description. The Application Extension contains application-specific
information; it conforms with the extension block syntax, as described
below, and its block label is 0xFF.
b. Required Version. 89a.
22
c. Syntax.
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Extension Introducer Byte
+---------------+
1 | | Extension Label Byte
+---------------+
+---------------+
0 | | Block Size Byte
+---------------+
1 | |
+- -+
2 | |
+- -+
3 | | Application Identifier 8 Bytes
+- -+
4 | |
+- -+
5 | |
+- -+
6 | |
+- -+
7 | |
+- -+
8 | |
+---------------+
9 | |
+- -+
10 | | Appl. Authentication Code 3 Bytes
+- -+
11 | |
+---------------+
+===============+
| |
| | Application Data Data Sub-blocks
| |
| |
+===============+
+---------------+
0 | | Block Terminator Byte
+---------------+
i) Extension Introducer - Defines this block as an extension. This
field contains the fixed value 0x21.
ii) Application Extension Label - Identifies the block as an
Application Extension. This field contains the fixed value 0xFF.
iii) Block Size - Number of bytes in this extension block,
following the Block Size field, up to but not including the
beginning of the Application Data. This field contains the fixed
value 11.
23
iv) Application Identifier - Sequence of eight printable ASCII
characters used to identify the application owning the Application
Extension.
v) Application Authentication Code - Sequence of three bytes used
to authenticate the Application Identifier. An Application program
may use an algorithm to compute a binary code that uniquely
identifies it as the application owning the Application Extension.
d. Extensions and Scope. This block does not have scope. This block
cannot be modified by any extension.
e. Recommendation. None.
27. Trailer.
a. Description. This block is a single-field block indicating the end of
the GIF Data Stream. It contains the fixed value 0x3B.
b. Required Version. 87a.
c. Syntax.
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | GIF Trailer Byte
+---------------+
d. Extensions and Scope. This block does not have scope, it terminates
the GIF Data Stream. This block may not be modified by any extension.
e. Recommendations. None.
24
Appendix
A. Quick Reference Table.
Block Name Required Label Ext. Vers.
Application Extension Opt. (*) 0xFF (255) yes 89a
Comment Extension Opt. (*) 0xFE (254) yes 89a
Global Color Table Opt. (1) none no 87a
Graphic Control Extension Opt. (*) 0xF9 (249) yes 89a
Header Req. (1) none no N/A
Image Descriptor Opt. (*) 0x2C (044) no 87a (89a)
Local Color Table Opt. (*) none no 87a
Logical Screen Descriptor Req. (1) none no 87a (89a)
Plain Text Extension Opt. (*) 0x01 (001) yes 89a
Trailer Req. (1) 0x3B (059) no 87a
Unlabeled Blocks
Header Req. (1) none no N/A
Logical Screen Descriptor Req. (1) none no 87a (89a)
Global Color Table Opt. (1) none no 87a
Local Color Table Opt. (*) none no 87a
Graphic-Rendering Blocks
Plain Text Extension Opt. (*) 0x01 (001) yes 89a
Image Descriptor Opt. (*) 0x2C (044) no 87a (89a)
Control Blocks
Graphic Control Extension Opt. (*) 0xF9 (249) yes 89a
Special Purpose Blocks
Trailer Req. (1) 0x3B (059) no 87a
Comment Extension Opt. (*) 0xFE (254) yes 89a
Application Extension Opt. (*) 0xFF (255) yes 89a
legend: (1) if present, at most one occurrence
(*) zero or more occurrences
(+) one or more occurrences
Notes : The Header is not subject to Version Numbers.
(89a) The Logical Screen Descriptor and the Image Descriptor retained their
syntax from version 87a to version 89a, but some fields reserved under version
87a are used under version 89a.
25
Appendix
B. GIF Grammar.
A Grammar is a form of notation to represent the sequence in which certain
objects form larger objects. A grammar is also used to represent the number of
objects that can occur at a given position. The grammar given here represents
the sequence of blocks that form the GIF Data Stream. A grammar is given by
listing its rules. Each rule consists of the left-hand side, followed by some
form of equals sign, followed by the right-hand side. In a rule, the
right-hand side describes how the left-hand side is defined. The right-hand
side consists of a sequence of entities, with the possible presence of special
symbols. The following legend defines the symbols used in this grammar for GIF.
Legend: <> grammar word
::= defines symbol
* zero or more occurrences
+ one or more occurrences
| alternate element
[] optional element
Example:
<GIF Data Stream> ::= Header <Logical Screen> <Data>* Trailer
This rule defines the entity <GIF Data Stream> as follows. It must begin with a
Header. The Header is followed by an entity called Logical Screen, which is
defined below by another rule. The Logical Screen is followed by the entity
Data, which is also defined below by another rule. Finally, the entity Data is
followed by the Trailer. Since there is no rule defining the Header or the
Trailer, this means that these blocks are defined in the document. The entity
Data has a special symbol (*) following it which means that, at this position,
the entity Data may be repeated any number of times, including 0 times. For
further reading on this subject, refer to a standard text on Programming
Languages.
The Grammar.
<GIF Data Stream> ::= Header <Logical Screen> <Data>* Trailer
<Logical Screen> ::= Logical Screen Descriptor [Global Color Table]
<Data> ::= <Graphic Block> |
<Special-Purpose Block>
<Graphic Block> ::= [Graphic Control Extension] <Graphic-Rendering Block>
<Graphic-Rendering Block> ::= <Table-Based Image> |
Plain Text Extension
<Table-Based Image> ::= Image Descriptor [Local Color Table] Image Data
<Special-Purpose Block> ::= Application Extension |
Comment Extension
26
NOTE : The grammar indicates that it is possible for a GIF Data Stream to
contain the Header, the Logical Screen Descriptor, a Global Color Table and the
GIF Trailer. This special case is used to load a GIF decoder with a Global
Color Table, in preparation for subsequent Data Streams without color tables at
all.
27
Appendix
C. Glossary.
Active Color Table - Color table used to render the next graphic. If the next
graphic is an image which has a Local Color Table associated with it, the
active color table becomes the Local Color Table associated with that image.
If the next graphic is an image without a Local Color Table, or a Plain Text
Extension, the active color table is the Global Color Table associated with the
Data Stream, if there is one; if there is no Global Color Table in the Data
Stream, the active color table is a color table saved from a previous Data
Stream, or one supplied by the decoder.
Block - Collection of bytes forming a protocol unit. In general, the term
includes labeled and unlabeled blocks, as well as Extensions.
Data Stream - The GIF Data Stream is composed of blocks and sub-blocks
representing images and graphics, together with control information to render
them on a display device. All control and data blocks in the Data Stream must
follow the Header and must precede the Trailer.
Decoder - A program capable of processing a GIF Data Stream to render the
images and graphics contained in it.
Encoder - A program capable of capturing and formatting image and graphic
raster data, following the definitions of the Graphics Interchange Format.
Extension - A protocol block labeled by the Extension Introducer 0x21.
Extension Introducer - Label (0x21) defining an Extension.
Graphic - Data which can be rendered on the screen by virtue of some algorithm.
The term graphic is more general than the term image; in addition to images,
the term graphic also includes data such as text, which is rendered using
character bit-maps.
Image - Data representing a picture or a drawing; an image is represented by an
array of pixels called the raster of the image.
Raster - Array of pixel values representing an image.
28
Appendix
D. Conventions.
Animation - The Graphics Interchange Format is not intended as a platform for
animation, even though it can be done in a limited way.
Byte Ordering - Unless otherwise stated, multi-byte numeric fields are ordered
with the Least Significant Byte first.
Color Indices - Color indices always refer to the active color table, either
the Global Color Table or the Local Color Table.
Color Order - Unless otherwise stated, all triple-component RGB color values
are specified in Red-Green-Blue order.
Color Tables - Both color tables, the Global and the Local, are optional; if
present, the Global Color Table is to be used with every image in the Data
Stream for which a Local Color Table is not given; if present, a Local Color
Table overrides the Global Color Table. However, if neither color table is
present, the application program is free to use an arbitrary color table. If
the graphics in several Data Streams are related and all use the same color
table, an encoder could place the color table as the Global Color Table in the
first Data Stream and leave subsequent Data Streams without a Global Color
Table or any Local Color Tables; in this way, the overhead for the table is
eliminated. It is recommended that the decoder save the previous Global Color
Table to be used with the Data Stream that follows, in case it does not contain
either a Global Color Table or any Local Color Tables. In general, this allows
the application program to use past color tables, significantly reducing
transmission overhead.
Extension Blocks - Extensions are defined using the Extension Introducer code
to mark the beginning of the block, followed by a block label, identifying the
type of extension. Extension Codes are numbers in the range from 0x00 to 0xFF,
inclusive. Special purpose extensions are transparent to the decoder and may be
omitted when transmitting the Data Stream on-line. The GIF capabilities
dialogue makes the provision for the receiver to request the transmission of
all blocks; the default state in this regard is no transmission of Special
purpose blocks.
Reserved Fields - All Reserved Fields are expected to have each bit set to zero
(off).
29
Appendix
E. Interlaced Images.
The rows of an Interlaced images are arranged in the following order:
Group 1 : Every 8th. row, starting with row 0. (Pass 1)
Group 2 : Every 8th. row, starting with row 4. (Pass 2)
Group 3 : Every 4th. row, starting with row 2. (Pass 3)
Group 4 : Every 2nd. row, starting with row 1. (Pass 4)
The Following example illustrates how the rows of an interlaced image are
ordered.
Row Number Interlace Pass
0 ----------------------------------------- 1
1 ----------------------------------------- 4
2 ----------------------------------------- 3
3 ----------------------------------------- 4
4 ----------------------------------------- 2
5 ----------------------------------------- 4
6 ----------------------------------------- 3
7 ----------------------------------------- 4
8 ----------------------------------------- 1
9 ----------------------------------------- 4
10 ----------------------------------------- 3
11 ----------------------------------------- 4
12 ----------------------------------------- 2
13 ----------------------------------------- 4
14 ----------------------------------------- 3
15 ----------------------------------------- 4
16 ----------------------------------------- 1
17 ----------------------------------------- 4
18 ----------------------------------------- 3
19 ----------------------------------------- 4
30
Appendix
F. Variable-Length-Code LZW Compression.
The Variable-Length-Code LZW Compression is a variation of the Lempel-Ziv
Compression algorithm in which variable-length codes are used to replace
patterns detected in the original data. The algorithm uses a code or
translation table constructed from the patterns encountered in the original
data; each new pattern is entered into the table and its index is used to
replace it in the compressed stream.
The compressor takes the data from the input stream and builds a code or
translation table with the patterns as it encounters them; each new pattern is
entered into the code table and its index is added to the output stream; when a
pattern is encountered which had been detected since the last code table
refresh, its index from the code table is put on the output stream, thus
achieving the data compression. The expander takes input from the compressed
data stream and builds the code or translation table from it; as the compressed
data stream is processed, codes are used to index into the code table and the
corresponding data is put on the decompressed output stream, thus achieving
data decompression. The details of the algorithm are explained below. The
Variable-Length-Code aspect of the algorithm is based on an initial code size
(LZW-initial code size), which specifies the initial number of bits used for
the compression codes. When the number of patterns detected by the compressor
in the input stream exceeds the number of patterns encodable with the current
number of bits, the number of bits per LZW code is increased by one.
The Raster Data stream that represents the actual output image can be
represented as:
7 6 5 4 3 2 1 0
+---------------+
| LZW code size |
+---------------+
+---------------+ ----+
| block size | |
+---------------+ |
| | +-- Repeated as many
| data bytes | | times as necessary.
| | |
+---------------+ ----+
. . . . . . ------- The code that terminates the LZW
compressed data must appear before
Block Terminator.
+---------------+
|0 0 0 0 0 0 0 0| Block Terminator
+---------------+
The conversion of the image from a series of pixel values to a transmitted or
stored character stream involves several steps. In brief these steps are:
1. Establish the Code Size - Define the number of bits needed to represent the
actual data.
2. Compress the Data - Compress the series of image pixels to a series of
31
compression codes.
3. Build a Series of Bytes - Take the set of compression codes and convert to a
string of 8-bit bytes.
4. Package the Bytes - Package sets of bytes into blocks preceded by character
counts and output.
ESTABLISH CODE SIZE
The first byte of the Compressed Data stream is a value indicating the minimum
number of bits required to represent the set of actual pixel values. Normally
this will be the same as the number of color bits. Because of some algorithmic
constraints however, black & white images which have one color bit must be
indicated as having a code size of 2.
This code size value also implies that the compression codes must start out one
bit longer.
COMPRESSION
The LZW algorithm converts a series of data values into a series of codes which
may be raw values or a code designating a series of values. Using text
characters as an analogy, the output code consists of a character or a code
representing a string of characters.
The LZW algorithm used in GIF matches algorithmically with the standard LZW
algorithm with the following differences:
1. A special Clear code is defined which resets all compression/decompression
parameters and tables to a start-up state. The value of this code is 2**<code
size>. For example if the code size indicated was 4 (image was 4 bits/pixel)
the Clear code value would be 16 (10000 binary). The Clear code can appear at
any point in the image data stream and therefore requires the LZW algorithm to
process succeeding codes as if a new data stream was starting. Encoders should
output a Clear code as the first code of each image data stream.
2. An End of Information code is defined that explicitly indicates the end of
the image data stream. LZW processing terminates when this code is encountered.
It must be the last code output by the encoder for an image. The value of this
code is <Clear code>+1.
3. The first available compression code value is <Clear code>+2.
4. The output codes are of variable length, starting at <code size>+1 bits per
code, up to 12 bits per code. This defines a maximum code value of 4095
(0xFFF). Whenever the LZW code value would exceed the current code length, the
code length is increased by one. The packing/unpacking of these codes must then
be altered to reflect the new code length.
BUILD 8-BIT BYTES
Because the LZW compression used for GIF creates a series of variable length
codes, of between 3 and 12 bits each, these codes must be reformed into a
series of 8-bit bytes that will be the characters actually stored or
transmitted. This provides additional compression of the image. The codes are
formed into a stream of bits as if they were packed right to left and then
32
picked off 8 bits at a time to be output.
Assuming a character array of 8 bits per character and using 5 bit codes to be
packed, an example layout would be similar to:
+---------------+
0 | | bbbaaaaa
+---------------+
1 | | dcccccbb
+---------------+
2 | | eeeedddd
+---------------+
3 | | ggfffffe
+---------------+
4 | | hhhhhggg
+---------------+
. . .
+---------------+
N | |
+---------------+
Note that the physical packing arrangement will change as the number of bits
per compression code change but the concept remains the same.
PACKAGE THE BYTES
Once the bytes have been created, they are grouped into blocks for output by
preceding each block of 0 to 255 bytes with a character count byte. A block
with a zero byte count terminates the Raster Data stream for a given image.
These blocks are what are actually output for the GIF image. This block format
has the side effect of allowing a decoding program the ability to read past the
actual image data if necessary by reading block counts and then skipping over
the data.
FURTHER READING
[1] Ziv, J. and Lempel, A. : "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory, May 1977.
[2] Welch, T. : "A Technique for High-Performance Data Compression", Computer,
June 1984.
[3] Nelson, M.R. : "LZW Data Compression", Dr. Dobb's Journal, October 1989.
33
Appendix
G. On-line Capabilities Dialogue.
NOTE : This section is currently (10 July 1990) under revision; the information
provided here should be used as general guidelines. Code written based on this
information should be designed in a flexible way to accommodate any changes
resulting from the revisions.
The following sequences are defined for use in mediating control between a GIF
sender and GIF receiver over an interactive communications line. These
sequences do not apply to applications that involve downloading of static GIF
files and are not considered part of a GIF file.
GIF CAPABILITIES ENQUIRY
The GIF Capabilities Enquiry sequence is issued from a host and requests an
interactive GIF decoder to return a response message that defines the graphics
parameters for the decoder. This involves returning information about available
screen sizes, number of bits/color supported and the amount of color detail
supported. The escape sequence for the GIF Capabilities Enquiry is defined as:
ESC[>0g 0x1B 0x5B 0x3E 0x30 0x67
GIF CAPABILITIES RESPONSE
The GIF Capabilities Response message is returned by an interactive GIF decoder
and defines the decoder's display capabilities for all graphics modes that are
supported by the software. Note that this can also include graphics printers as
well as a monitor screen. The general format of this message is:
#version;protocol{;dev, width, height, color-bits, color-res}...<CR>
'#' GIF Capabilities Response identifier character.
version GIF format version number; initially '87a'.
protocol='0' No end-to-end protocol supported by decoder Transfer as direct
8-bit data stream.
protocol='1' Can use CIS B+ error correction protocol to transfer GIF data
interactively from the host directly to the display.
dev = '0' Screen parameter set follows.
dev = '1' Printer parameter set follows.
width Maximum supported display width in pixels.
height Maximum supported display height in pixels.
color-bits Number of bits per pixel supported. The number of supported
colors is therefore 2**color-bits.
color-res Number of bits per color component supported in the hardware
color palette. If color-res is '0' then no hardware palette
table is available.
Note that all values in the GIF Capabilities Response are returned as ASCII
decimal numbers and the message is terminated by a Carriage Return character.
The following GIF Capabilities Response message describes three standard IBM PC
Enhanced Graphics Adapter configurations with no printer; the GIF data stream
34
can be processed within an error correcting protocol:
#87a;1;0,320,200,4,0;0,640,200,2,2;0,640,350,4,2<CR>
ENTER GIF GRAPHICS MODE
Two sequences are currently defined to invoke an interactive GIF decoder into
action. The only difference between them is that different output media are
selected. These sequences are:
ESC[>1g Display GIF image on screen
0x1B 0x5B 0x3E 0x31 0x67
ESC[>2g Display image directly to an attached graphics printer. The image may
optionally be displayed on the screen as well.
0x1B 0x5B 0x3E 0x32 0x67
Note that the 'g' character terminating each sequence is in lowercase.
INTERACTIVE ENVIRONMENT
The assumed environment for the transmission of GIF image data from an
interactive application is a full 8-bit data stream from host to micro. All
256 character codes must be transferrable. The establishing of an 8-bit data
path for communications will normally be taken care of by the host application
programs. It is however up to the receiving communications programs supporting
GIF to be able to receive and pass on all 256 8-bit codes to the GIF decoder
software.
- Cut here --- Cut here --- Cut here --- Cut here --- Cut here --- Cut here ---