3 LZW and GIF explained----Steve Blackstock
\r
6 I hope this little document will help enlighten those of you out there
\r
7 who want to know more about the Lempel-Ziv Welch compression algorithm, and,
\r
8 specifically, the implementation that GIF uses.
\r
9 Before we start, here's a little terminology, for the purposes of this
\r
12 "character": a fundamental data element. In normal text files, this is
\r
13 just a single byte. In raster images, which is what we're interested in, it's
\r
14 an index that specifies the color of a given pixel. I'll refer to an arbitray
\r
16 "charstream": a stream of characters, as in a data file.
\r
17 "string": a number of continuous characters, anywhere from one to very
\r
18 many characters in length. I can specify an arbitrary string as "[...]K".
\r
19 "prefix": almost the same as a string, but with the implication that a
\r
20 prefix immediately precedes a character, and a prefix can have a length of
\r
21 zero. So, a prefix and a character make up a string. I will refer to an
\r
22 arbitrary prefix as "[...]".
\r
23 "root": a single-character string. For most purposes, this is a
\r
24 character, but we may occasionally make a distinction. It is [...]K, where
\r
26 "code": a number, specified by a known number of bits, which maps to a
\r
28 "codestream": the output stream of codes, as in the "raster data"
\r
29 "entry": a code and its string.
\r
30 "string table": a list of entries; usually, but not necessarily, unique.
\r
31 That should be enough of that.
\r
33 LZW is a way of compressing data that takes advantage of repetition of
\r
34 strings in the data. Since raster data usually contains a lot of this
\r
35 repetition, LZW is a good way of compressing and decompressing it.
\r
36 For the moment, lets consider normal LZW encoding and decoding. GIF's
\r
37 variation on the concept is just an extension from there.
\r
38 LZW manipulates three objects in both compression and decompression: the
\r
39 charstream, the codestream, and the string table. In compression, the
\r
40 charstream is the input and the codestream is the output. In decompression,
\r
41 the codestream is the input and the charstream is the output. The string table
\r
42 is a product of both compression and decompression, but is never passed from
\r
44 The first thing we do in LZW compression is initialize our string table.
\r
45 To do this, we need to choose a code size (how many bits) and know how many
\r
46 values our characters can possibly take. Let's say our code size is 12 bits,
\r
47 meaning we can store 0->FFF, or 4096 entries in our string table. Lets also
\r
48 say that we have 32 possible different characters. (This corresponds to, say,
\r
49 a picture in which there are 32 different colors possible for each pixel.) To
\r
50 initialize the table, we set code#0 to character#0, code #1 to character#1,
\r
51 and so on, until code#31 to character#31. Actually, we are specifying that
\r
52 each code from 0 to 31 maps to a root. There will be no more entries in the
\r
53 table that have this property.
\r
54 Now we start compressing data. Let's first define something called the
\r
55 "current prefix". It's just a prefix that we'll store things in and compare
\r
56 things to now and then. I will refer to it as "[.c.]". Initially, the current
\r
57 prefix has nothing in it. Let's also define a "current string", which will be
\r
58 the current prefix plus the next character in the charstream. I will refer to
\r
59 the current string as "[.c.]K", where K is some character. OK, look at the
\r
60 first character in the charstream. Call it P. Make [.c.]P the current string.
\r
61 (At this point, of course, it's just the root P.) Now search through the
\r
62 string table to see if [.c.]P appears in it. Of course, it does now, because
\r
63 our string table is initialized to have all roots. So we don't do anything.
\r
64 Now make [.c.]P the current prefix. Look at the next character in the
\r
65 charstream. Call it Q. Add it to the current prefix to form [.c.]Q, the
\r
66 current string. Now search through the string table to see if [.c.]Q appears
\r
67 in it. In this case, of course, it doesn't. Aha! Now we get to do something.
\r
68 Add [.c.]Q (which is PQ in this case) to the string table for code#32, and
\r
69 output the code for [.c.] to the codestream. Now start over again with the
\r
70 current prefix being just the root P. Keep adding characters to [.c.] to form
\r
71 [.c.]K, until you can't find [.c.]K in the string table. Then output the code
\r
72 for [.c.] and add [.c.]K to the string table. In pseudo-code, the algorithm
\r
73 goes something like this:
\r
75 [1] Initialize string table;
\r
77 [3] K <- next character in charstream;
\r
78 [4] Is [.c.]K in string table?
\r
79 (yes: [.c.] <- [.c.]K;
\r
82 (no: add [.c.]K to the string table;
\r
83 output the code for [.c.] to the codestream;
\r
88 It's as simple as that! Of course, when you get to step [3] and there
\r
89 aren't any more characters left, you just output the code for [.c.] and throw
\r
90 the table away. You're done.
\r
91 Wanna do an example? Let's pretend we have a four-character alphabet:
\r
92 A,B,C,D. The charstream looks like ABACABA. Let's compress it. First, we
\r
93 initialize our string table to: #0=A, #1=B, #2=C, #3=D. The first character is
\r
94 A, which is in the string table, so [.c.] becomes A. Next we get AB, which is
\r
95 not in the table, so we output code #0 (for [.c.]),
\r
96 and add AB to the string table as code #4. [.c.] becomes B. Next we get
\r
97 [.c.]A = BA, which is not in the string table, so output code #1, and add BA
\r
98 to the string table as code #5. [.c.] becomes A. Next we get AC, which is not
\r
99 in the string table. Output code #0, and add AC to the string table as code
\r
100 #6. Now [.c.] becomes C. Next we get [.c.]A = CA, which is not in the table.
\r
101 Output #2 for C, and add CA to table as code#7. Now [.c.] becomes A. Next we
\r
102 get AB, which IS in the string table, so [.c.] gets AB, and we look at ABA,
\r
103 which is not in the string table, so output the code for AB, which is #4, and
\r
104 add ABA to the string table as code #8. [.c.] becomes A. We can't get any more
\r
105 characters, so we just output #0 for the code for A, and we're done. So, the
\r
106 codestream is #0#1#0#2#4#0.
\r
107 A few words (four) should be said here about efficiency: use a hashing
\r
108 strategy. The search through the string table can be computationally
\r
109 intensive, and some hashing is well worth the effort. Also, note that
\r
110 "straight LZW" compression runs the risk of overflowing the string table -
\r
111 getting to a code which can't be represented in the number of bits you've set
\r
112 aside for codes. There are several ways of dealing with this problem, and GIF
\r
113 implements a very clever one, but we'll get to that.
\r
114 An important thing to notice is that, at any point during the
\r
115 compression, if [...]K is in the string table, [...] is there also. This fact
\r
116 suggests an efficient method for storing strings in the table. Rather than
\r
117 store the entire string of K's in the table, realize that any string can be
\r
118 expressed as a prefix plus a character: [...]K. If we're about to store [...]K
\r
119 in the table, we know that [...] is already there, so we can just store the
\r
120 code for [...] plus the final character K.
\r
121 Ok, that takes care of compression. Decompression is perhaps more
\r
122 difficult conceptually, but it is really easier to program.
\r
123 Here's how it goes: We again have to start with an initialized string
\r
124 table. This table comes from what knowledge we have about the charstream that
\r
125 we will eventually get, like what possible values the characters can take. In
\r
126 GIF files, this information is in the header as the number of possible pixel
\r
127 values. The beauty of LZW, though, is that this is all we need to know. We
\r
128 will build the rest of the string table as we decompress the codestream. The
\r
129 compression is done in such a way that we will never encounter a code in the
\r
130 codestream that we can't translate into a string.
\r
131 We need to define something called a "current code", which I will refer
\r
132 to as "<code>", and an "old-code", which I will refer to as "<old>". To start
\r
133 things off, look at the first code. This is now <code>. This code will be in
\r
134 the intialized string table as the code for a root. Output the root to the
\r
135 charstream. Make this code the old-code <old>. *Now look at the next code, and
\r
136 make it <code>. It is possible that this code will not be in the string table,
\r
137 but let's assume for now that it is. Output the string corresponding to <code>
\r
138 to the codestream. Now find the first character in the string you just
\r
139 translated. Call this K. Add this to the prefix [...] generated by <old> to
\r
140 form a new string [...]K. Add this string [...]K to the string table, and set
\r
141 the old-code <old> to the current code <code>. Repeat from where I typed the
\r
142 asterisk, and you're all set. Read this paragraph again if you just skimmed
\r
143 it!!! Now let's consider the possibility that <code> is not in the string
\r
144 table. Think back to compression, and try to understand what happens when you
\r
145 have a string like P[...]P[...]PQ appear in the charstream. Suppose P[...] is
\r
146 already in the string table, but P[...]P is not. The compressor will parse out
\r
147 P[...], and find that P[...]P is not in the string table. It will output the
\r
148 code for P[...], and add P[...]P to the string table. Then it will get up to
\r
149 P[...]P for the next string, and find that P[...]P is in the table, as
\r
150 the code just added. So it will output the code for P[...]P if it finds
\r
151 that P[...]PQ is not in the table. The decompressor is always "one step
\r
152 behind" the compressor. When the decompressor sees the code for P[...]P, it
\r
153 will not have added that code to it's string table yet because it needed the
\r
154 beginning character of P[...]P to add to the string for the last code, P[...],
\r
155 to form the code for P[...]P. However, when a decompressor finds a code that
\r
156 it doesn't know yet, it will always be the very next one to be added to the
\r
157 string table. So it can guess at what the string for the code should be, and,
\r
158 in fact, it will always be correct. If I am a decompressor, and I see
\r
159 code#124, and yet my string table has entries only up to code#123, I can
\r
160 figure out what code#124 must be, add it to my string table, and output the
\r
161 string. If code#123 generated the string, which I will refer to here as a
\r
162 prefix, [...], then code#124, in this special case, will be [...] plus the
\r
163 first character of [...]. So just add the first character of [...] to the end
\r
164 of itself. Not too bad. As an example (and a very common one) of this special
\r
165 case, let's assume we have a raster image in which the first three pixels have
\r
166 the same color value. That is, my charstream looks like: QQQ.... For the sake
\r
167 of argument, let's say we have 32 colors, and Q is the color#12. The
\r
168 compressor will generate the code sequence 12,32,.... (if you don't know why,
\r
169 take a minute to understand it.) Remember that #32 is not in the initial
\r
170 table, which goes from #0 to #31. The decompressor will see #12 and translate
\r
171 it just fine as color Q. Then it will see #32 and not yet know what that
\r
172 means. But if it thinks about it long enough, it can figure out that QQ should
\r
173 be entry#32 in the table and QQ should be the next string output. So the
\r
174 decompression pseudo-code goes something like:
\r
176 [1] Initialize string table;
\r
177 [2] get first code: <code>;
\r
178 [3] output the string for <code> to the charstream;
\r
179 [4] <old> = <code>;
\r
180 [5] <code> <- next code in codestream;
\r
181 [6] does <code> exist in the string table?
\r
182 (yes: output the string for <code> to the charstream;
\r
183 [...] <- translation for <old>;
\r
184 K <- first character of translation for <code>;
\r
185 add [...]K to the string table; <old> <- <code>; )
\r
186 (no: [...] <- translation for <old>;
\r
187 K <- first character of [...];
\r
188 output [...]K to charstream and add it to string table;
\r
193 Again, when you get to step [5] and there are no more codes, you're
\r
194 finished. Outputting of strings, and finding of initial characters in strings
\r
195 are efficiency problems all to themselves, but I'm not going to suggest ways
\r
196 to do them here. Half the fun of programming is figuring these things out!
\r
198 Now for the GIF variations on the theme. In part of the header of a GIF
\r
199 file, there is a field, in the Raster Data stream, called "code size". This is
\r
200 a very misleading name for the field, but we have to live with it. What it is
\r
201 really is the "root size". The actual size, in bits, of the compression codes
\r
202 actually changes during compression/decompression, and I will refer to that
\r
203 size here as the "compression size". The initial table is just the codes for
\r
204 all the roots, as usual, but two special codes are added on top of those.
\r
205 Suppose you have a "code size", which is usually the number of bits per pixel
\r
206 in the image, of N. If the number of bits/pixel is one, then N must be 2: the
\r
207 roots take up slots #0 and #1 in the initial table, and the two special codes
\r
208 will take up slots #4 and #5. In any other case, N is the number of bits per
\r
209 pixel, and the roots take up slots #0 through #(2**N-1), and the special codes
\r
210 are (2**N) and (2**N + 1). The initial compression size will be N+1 bits per
\r
211 code. If you're encoding, you output the codes (N+1) bits at a time to start
\r
212 with, and if you're decoding, you grab (N+1) bits from the codestream at a
\r
213 time. As for the special codes: <CC> or the clear code, is (2**N), and <EOI>,
\r
214 or end-of-information, is (2**N + 1). <CC> tells the compressor to re-
\r
215 initialize the string table, and to reset the compression size to (N+1). <EOI>
\r
216 means there's no more in the codestream. If you're encoding or decoding, you
\r
217 should start adding things to the string table at <CC> + 2. If you're
\r
218 encoding, you should output <CC> as the very first code, and then whenever
\r
219 after that you reach code #4095 (hex FFF), because GIF does not allow
\r
220 compression sizes to be greater than 12 bits. If you're decoding, you should
\r
221 reinitialize your string table when you observe <CC>. The variable
\r
222 compression sizes are really no big deal. If you're encoding, you start with a
\r
223 compression size of (N+1) bits, and, whenever you output the code
\r
224 (2**(compression size)-1), you bump the compression size up one bit. So the
\r
225 next code you output will be one bit longer. Remember that the largest
\r
226 compression size is 12 bits, corresponding to a code of 4095. If you get that
\r
227 far, you must output <CC> as the next code, and start over. If you're
\r
228 decoding, you must increase your compression size AS SOON AS YOU write entry
\r
229 #(2**(compression size) - 1) to the string table. The next code you READ will
\r
230 be one bit longer. Don't make the mistake of waiting until you need to add the
\r
231 code (2**compression size) to the table. You'll have already missed a bit from
\r
232 the last code. The packaging of codes into a bitsream for the raster data is
\r
233 also a potential stumbling block for the novice encoder or decoder. The lowest
\r
234 order bit in the code should coincide with the lowest available bit in the
\r
235 first available byte in the codestream. For example, if you're starting with
\r
236 5-bit compression codes, and your first three codes are, say, <abcde>,
\r
237 <fghij>, <klmno>, where e, j, and o are bit#0, then your codestream will start
\r
243 So the differences between straight LZW and GIF LZW are: two additional
\r
244 special codes and variable compression sizes. If you understand LZW, and you
\r
245 understand those variations, you understand it all!
\r
246 Just as sort of a P.S., you may have noticed that a compressor has a
\r
247 little bit of flexibility at compression time. I specified a "greedy" approach
\r
248 to the compression, grabbing as many characters as possible before outputting
\r
249 codes. This is, in fact, the standard LZW way of doing things, and it will
\r
250 yield the best compression ratio. But there's no rule saying you can't stop
\r
251 anywhere along the line and just output the code for the current prefix,
\r
252 whether it's already in the table or not, and add that string plus the next
\r
253 character to the string table. There are various reasons for wanting to do
\r
254 this, especially if the strings get extremely long and make hashing difficult.
\r
255 If you need to, do it.
\r
256 Hope this helps out.----steve blackstock
\r
258 ---------------------------------------------------------------------------
\r
259 Article 5729 of comp.graphics:
\r
260 Path: polya!shelby!labrea!agate!ucbvax!tut.cis.ohio-state.edu!rutgers!cmcl2!phri!cooper!john
\r
261 >From: john@cooper.cooper.EDU (John Barkaus)
\r
262 Newsgroups: comp.graphics
\r
263 Subject: GIF file format responses 4/5
\r
265 Message-ID: <1489@cooper.cooper.EDU>
\r
266 Date: 21 Apr 89 20:56:35 GMT
\r
267 Organization: The Cooper Union (NY, NY)
\r
271 >From: cmcl2!neuron1.Jpl.Nasa.Gov!harry (Harry Langenbacher)
\r
275 Graphics Interchange Format (tm)
\r
277 A standard defining a mechanism
\r
279 for the storage and transmission
\r
281 of raster-based graphics information
\r
285 (c) CompuServe Incorporated, 1987
\r
287 All rights reserved
\r
289 While this document is copyrighted, the information
\r
291 contained within is made available for use in computer
\r
293 software without royalties, or licensing restrictions.
\r
295 GIF and 'Graphics Interchange Format' are trademarks of
\r
297 CompuServe, Incorporated.
\r
299 an H&R Block Company
\r
301 5000 Arlington Centre Blvd.
\r
303 Columbus, Ohio 43220
\r
309 Graphics Interchange Format (GIF) Specification
\r
313 INTRODUCTION . . . . . . . . . . . . . . . . . page 3
\r
315 GENERAL FILE FORMAT . . . . . . . . . . . . . page 3
\r
317 GIF SIGNATURE . . . . . . . . . . . . . . . . page 4
\r
319 SCREEN DESCRIPTOR . . . . . . . . . . . . . . page 4
\r
321 GLOBAL COLOR MAP . . . . . . . . . . . . . . . page 5
\r
323 IMAGE DESCRIPTOR . . . . . . . . . . . . . . . page 6
\r
325 LOCAL COLOR MAP . . . . . . . . . . . . . . . page 7
\r
327 RASTER DATA . . . . . . . . . . . . . . . . . page 7
\r
329 GIF TERMINATOR . . . . . . . . . . . . . . . . page 8
\r
331 GIF EXTENSION BLOCKS . . . . . . . . . . . . . page 8
\r
333 APPENDIX A - GLOSSARY . . . . . . . . . . . . page 9
\r
335 APPENDIX B - INTERACTIVE SEQUENCES . . . . . . page 10
\r
337 APPENDIX C - IMAGE PACKAGING & COMPRESSION . . page 12
\r
339 APPENDIX D - MULTIPLE IMAGE PROCESSING . . . . page 15
\r
341 Graphics Interchange Format (GIF) Page 3
\r
347 'GIF' (tm) is CompuServe's standard for defining generalized color
\r
349 raster images. This 'Graphics Interchange Format' (tm) allows
\r
351 high-quality, high-resolution graphics to be displayed on a variety of
\r
353 graphics hardware and is intended as an exchange and display mechanism
\r
355 for graphics images. The image format described in this document is
\r
357 designed to support current and future image technology and will in
\r
359 addition serve as a basis for future CompuServe graphics products.
\r
361 The main focus of this document is to provide the technical
\r
363 information necessary for a programmer to implement GIF encoders and
\r
365 decoders. As such, some assumptions are made as to terminology relavent
\r
367 to graphics and programming in general.
\r
369 The first section of this document describes the GIF data format
\r
371 and its components and applies to all GIF decoders, either as standalone
\r
373 programs or as part of a communications package. Appendix B is a
\r
375 section relavent to decoders that are part of a communications software
\r
377 package and describes the protocol requirements for entering and exiting
\r
379 GIF mode, and responding to host interrogations. A glossary in Appendix
\r
381 A defines some of the terminology used in this document. Appendix C
\r
383 gives a detailed explanation of how the graphics image itself is
\r
385 packaged as a series of data bytes.
\r
387 Graphics Interchange Format Data Definition
\r
389 GENERAL FILE FORMAT
\r
391 +-----------------------+
\r
393 | +-------------------+ |
\r
395 | | GIF Signature | |
\r
397 | +-------------------+ |
\r
399 | +-------------------+ |
\r
401 | | Screen Descriptor | |
\r
403 | +-------------------+ |
\r
405 | +-------------------+ |
\r
407 | | Global Color Map | |
\r
409 | +-------------------+ |
\r
413 | +-------------------+ | ---+
\r
415 | | Image Descriptor | | |
\r
417 | +-------------------+ | |
\r
419 | +-------------------+ | |
\r
421 | | Local Color Map | | |- Repeated 1 to n times
\r
423 | +-------------------+ | |
\r
425 | +-------------------+ | |
\r
427 | | Raster Data | | |
\r
429 | +-------------------+ | ---+
\r
433 |- GIF Terminator -|
\r
435 +-----------------------+
\r
437 Graphics Interchange Format (GIF) Page 4
\r
443 The following GIF Signature identifies the data following as a
\r
445 valid GIF image stream. It consists of the following six characters:
\r
449 The last three characters '87a' may be viewed as a version number
\r
451 for this particular GIF definition and will be used in general as a
\r
453 reference in documents regarding GIF that address any version
\r
459 The Screen Descriptor describes the overall parameters for all GIF
\r
461 images following. It defines the overall dimensions of the image space
\r
463 or logical screen required, the existance of color mapping information,
\r
465 background screen color, and color depth information. This information
\r
467 is stored in a series of 8-bit bytes as described below.
\r
471 7 6 5 4 3 2 1 0 Byte #
\r
477 +-Screen Width -+ Raster width in pixels (LSB first)
\r
485 +-Screen Height-+ Raster height in pixels (LSB first)
\r
489 +-+-----+-+-----+ M = 1, Global color map follows Descriptor
\r
491 |M| cr |0|pixel| 5 cr+1 = # bits of color resolution
\r
493 +-+-----+-+-----+ pixel+1 = # bits/pixel in image
\r
495 | background | 6 background=Color index of screen background
\r
497 +---------------+ (color is defined from the Global color
\r
499 |0 0 0 0 0 0 0 0| 7 map or default map if none specified)
\r
503 The logical screen width and height can both be larger than the
\r
505 physical display. How images larger than the physical display are
\r
507 handled is implementation dependent and can take advantage of hardware
\r
509 characteristics (e.g. Macintosh scrolling windows). Otherwise images
\r
511 can be clipped to the edges of the display.
\r
513 The value of 'pixel' also defines the maximum number of colors
\r
515 within an image. The range of values for 'pixel' is 0 to 7 which
\r
517 represents 1 to 8 bits. This translates to a range of 2 (B & W) to 256
\r
519 colors. Bit 3 of word 5 is reserved for future definition and must be
\r
523 Graphics Interchange Format (GIF) Page 5
\r
529 The Global Color Map is optional but recommended for images where
\r
531 accurate color rendition is desired. The existence of this color map is
\r
533 indicated in the 'M' field of byte 5 of the Screen Descriptor. A color
\r
535 map can also be associated with each image in a GIF file as described
\r
537 later. However this global map will normally be used because of
\r
539 hardware restrictions in equipment available today. In the individual
\r
541 Image Descriptors the 'M' flag will normally be zero. If the Global
\r
543 Color Map is present, it's definition immediately follows the Screen
\r
545 Descriptor. The number of color map entries following a Screen
\r
547 Descriptor is equal to 2**(# bits per pixel), where each entry consists
\r
549 of three byte values representing the relative intensities of red, green
\r
551 and blue respectively. The structure of the Color Map block is:
\r
555 7 6 5 4 3 2 1 0 Byte #
\r
559 | red intensity | 1 Red value for color index 0
\r
563 |green intensity| 2 Green value for color index 0
\r
567 | blue intensity| 3 Blue value for color index 0
\r
571 | red intensity | 4 Red value for color index 1
\r
575 |green intensity| 5 Green value for color index 1
\r
579 | blue intensity| 6 Blue value for color index 1
\r
583 : : (Continues for remaining colors)
\r
585 Each image pixel value received will be displayed according to its
\r
587 closest match with an available color of the display based on this color
\r
589 map. The color components represent a fractional intensity value from
\r
591 none (0) to full (255). White would be represented as (255,255,255),
\r
593 black as (0,0,0) and medium yellow as (180,180,0). For display, if the
\r
595 device supports fewer than 8 bits per color component, the higher order
\r
597 bits of each component are used. In the creation of a GIF color map
\r
599 entry with hardware supporting fewer than 8 bits per component, the
\r
601 component values for the hardware should be converted to the 8-bit
\r
603 format with the following calculation:
\r
605 <map_value> = <component_value>*255/(2**<nbits> -1)
\r
607 This assures accurate translation of colors for all displays. In
\r
609 the cases of creating GIF images from hardware without color palette
\r
611 capability, a fixed palette should be created based on the available
\r
613 display colors for that hardware. If no Global Color Map is indicated,
\r
615 a default color map is generated internally which maps each possible
\r
617 incoming color index to the same hardware color index modulo <n> where
\r
619 <n> is the number of available hardware colors.
\r
621 Graphics Interchange Format (GIF) Page 6
\r
627 The Image Descriptor defines the actual placement and extents of
\r
629 the following image within the space defined in the Screen Descriptor.
\r
631 Also defined are flags to indicate the presence of a local color lookup
\r
633 map, and to define the pixel display sequence. Each Image Descriptor is
\r
635 introduced by an image separator character. The role of the Image
\r
637 Separator is simply to provide a synchronization character to introduce
\r
639 an Image Descriptor. This is desirable if a GIF file happens to contain
\r
641 more than one image. This character is defined as 0x2C hex or ','
\r
643 (comma). When this character is encountered between images, the Image
\r
645 Descriptor will follow immediately.
\r
647 Any characters encountered between the end of a previous image and
\r
649 the image separator character are to be ignored. This allows future GIF
\r
651 enhancements to be present in newer image formats and yet ignored safely
\r
653 by older software decoders.
\r
657 7 6 5 4 3 2 1 0 Byte #
\r
661 |0 0 1 0 1 1 0 0| 1 ',' - Image separator character
\r
665 | | 2 Start of image in pixels from the
\r
667 +- Image Left -+ left side of the screen (LSB first)
\r
675 +- Image Top -+ Start of image in pixels from the
\r
677 | | 5 top of the screen (LSB first)
\r
683 +- Image Width -+ Width of the image in pixels (LSB first)
\r
691 +- Image Height-+ Height of the image in pixels (LSB first)
\r
695 +-+-+-+-+-+-----+ M=0 - Use global color map, ignore 'pixel'
\r
697 |M|I|0|0|0|pixel| 10 M=1 - Local color map follows, use 'pixel'
\r
699 +-+-+-+-+-+-----+ I=0 - Image formatted in Sequential order
\r
701 I=1 - Image formatted in Interlaced order
\r
703 pixel+1 - # bits per pixel for this image
\r
705 The specifications for the image position and size must be confined
\r
707 to the dimensions defined by the Screen Descriptor. On the other hand
\r
709 it is not necessary that the image fill the entire screen defined.
\r
713 Graphics Interchange Format (GIF) Page 7
\r
717 A Local Color Map is optional and defined here for future use. If
\r
719 the 'M' bit of byte 10 of the Image Descriptor is set, then a color map
\r
721 follows the Image Descriptor that applies only to the following image.
\r
723 At the end of the image, the color map will revert to that defined after
\r
725 the Screen Descriptor. Note that the 'pixel' field of byte 10 of the
\r
727 Image Descriptor is used only if a Local Color Map is indicated. This
\r
729 defines the parameters not only for the image pixel size, but determines
\r
731 the number of color map entries that follow. The bits per pixel value
\r
733 will also revert to the value specified in the Screen Descriptor when
\r
735 processing of the image is complete.
\r
739 The format of the actual image is defined as the series of pixel
\r
741 color index values that make up the image. The pixels are stored left
\r
743 to right sequentially for an image row. By default each image row is
\r
745 written sequentially, top to bottom. In the case that the Interlace or
\r
747 'I' bit is set in byte 10 of the Image Descriptor then the row order of
\r
749 the image display follows a four-pass process in which the image is
\r
751 filled in by widely spaced rows. The first pass writes every 8th row,
\r
753 starting with the top row of the image window. The second pass writes
\r
755 every 8th row starting at the fifth row from the top. The third pass
\r
757 writes every 4th row starting at the third row from the top. The fourth
\r
759 pass completes the image, writing every other row, starting at the
\r
761 second row from the top. A graphic description of this process follows:
\r
765 Row Pass 1 Pass 2 Pass 3 Pass 4 Result
\r
767 ---------------------------------------------------
\r
797 The image pixel values are processed as a series of color indices
\r
799 which map into the existing color map. The resulting color value from
\r
801 the map is what is actually displayed. This series of pixel indices,
\r
803 the number of which is equal to image-width*image-height pixels, are
\r
805 passed to the GIF image data stream one value per pixel, compressed and
\r
807 packaged according to a version of the LZW compression algorithm as
\r
809 defined in Appendix C.
\r
811 Graphics Interchange Format (GIF) Page 8
\r
817 In order to provide a synchronization for the termination of a GIF
\r
819 image file, a GIF decoder will process the end of GIF mode when the
\r
821 character 0x3B hex or ';' is found after an image has been processed.
\r
823 By convention the decoding software will pause and wait for an action
\r
825 indicating that the user is ready to continue. This may be a carriage
\r
827 return entered at the keyboard or a mouse click. For interactive
\r
829 applications this user action must be passed on to the host as a
\r
831 carriage return character so that the host application can continue.
\r
833 The decoding software will then typically leave graphics mode and resume
\r
835 any previous process.
\r
837 GIF EXTENSION BLOCKS
\r
839 To provide for orderly extension of the GIF definition, a mechanism
\r
841 for defining the packaging of extensions within a GIF data stream is
\r
843 necessary. Specific GIF extensions are to be defined and documented by
\r
845 CompuServe in order to provide a controlled enhancement path.
\r
847 GIF Extension Blocks are packaged in a manner similar to that used
\r
849 by the raster data though not compressed. The basic structure is:
\r
851 7 6 5 4 3 2 1 0 Byte #
\r
855 |0 0 1 0 0 0 0 1| 1 '!' - GIF Extension Block Introducer
\r
859 | function code | 2 Extension function code (0 to 255)
\r
861 +---------------+ ---+
\r
865 +---------------+ |
\r
867 : : +-- Repeated as many times as necessary
\r
869 |func data bytes| |
\r
873 +---------------+ ---+
\r
879 |0 0 0 0 0 0 0 0| zero byte count (terminates block)
\r
883 A GIF Extension Block may immediately preceed any Image Descriptor
\r
885 or occur before the GIF Terminator.
\r
887 All GIF decoders must be able to recognize the existence of GIF
\r
889 Extension Blocks and read past them if unable to process the function
\r
891 code. This ensures that older decoders will be able to process extended
\r
893 GIF image files in the future, though without the additional
\r
897 Graphics Interchange Format (GIF) Page 9
\r
899 Appendix A - Glossary
\r
903 Pixel - The smallest picture element of a graphics image. This usually
\r
905 corresponds to a single dot on a graphics screen. Image resolution is
\r
907 typically given in units of pixels. For example a fairly standard
\r
909 graphics screen format is one 320 pixels across and 200 pixels high.
\r
911 Each pixel can appear as one of several colors depending on the
\r
913 capabilities of the graphics hardware.
\r
915 Raster - A horizontal row of pixels representing one line of an image. A
\r
917 typical method of working with images since most hardware is oriented to
\r
919 work most efficiently in this manner.
\r
921 LSB - Least Significant Byte. Refers to a convention for two byte numeric
\r
923 values in which the less significant byte of the value preceeds the more
\r
925 significant byte. This convention is typical on many microcomputers.
\r
927 Color Map - The list of definitions of each color used in a GIF image.
\r
929 These desired colors are converted to available colors through a table
\r
931 which is derived by assigning an incoming color index (from the image)
\r
933 to an output color index (of the hardware). While the color map
\r
935 definitons are specified in a GIF image, the output pixel colors will
\r
937 vary based on the hardware used and its ability to match the defined
\r
941 Interlace - The method of displaying a GIF image in which multiple passes
\r
943 are made, outputting raster lines spaced apart to provide a way of
\r
945 visualizing the general content of an entire image before all of the
\r
947 data has been processed.
\r
949 B Protocol - A CompuServe-developed error-correcting file transfer protocol
\r
951 available in the public domain and implemented in CompuServe VIDTEX
\r
953 products. This error checking mechanism will be used in transfers of
\r
955 GIF images for interactive applications.
\r
957 LZW - A sophisticated data compression algorithm based on work done by
\r
959 Lempel-Ziv & Welch which has the feature of very efficient one-pass
\r
961 encoding and decoding. This allows the image to be decompressed and
\r
963 displayed at the same time. The original article from which this
\r
965 technique was adapted is:
\r
967 Terry A. Welch, "A Technique for High Performance Data
\r
969 Compression", IEEE Computer, vol 17 no 6 (June 1984)
\r
971 This basic algorithm is also used in the public domain ARC file
\r
973 compression utilities. The CompuServe adaptation of LZW for GIF is
\r
975 described in Appendix C.
\r
977 Graphics Interchange Format (GIF) Page 10
\r
979 Appendix B - Interactive Sequences
\r
981 GIF Sequence Exchanges for an Interactive Environment
\r
983 The following sequences are defined for use in mediating control
\r
985 between a GIF sender and GIF receiver over an interactive communications
\r
987 line. These sequences do not apply to applications that involve
\r
989 downloading of static GIF files and are not considered part of a GIF
\r
993 GIF CAPABILITIES ENQUIRY
\r
995 The GCE sequence is issued from a host and requests an interactive
\r
997 GIF decoder to return a response message that defines the graphics
\r
999 parameters for the decoder. This involves returning information about
\r
1001 available screen sizes, number of bits/color supported and the amount of
\r
1003 color detail supported. The escape sequence for the GCE is defined as:
\r
1005 ESC [ > 0 g (g is lower case, spaces inserted for clarity)
\r
1007 (0x1B 0x5B 0x3E 0x30 0x67)
\r
1009 GIF CAPABILITIES RESPONSE
\r
1011 The GIF Capabilities Response message is returned by an interactive
\r
1013 GIF decoder and defines the decoder's display capabilities for all
\r
1015 graphics modes that are supported by the software. Note that this can
\r
1017 also include graphics printers as well as a monitor screen. The general
\r
1019 format of this message is:
\r
1021 #version;protocol{;dev, width, height, color-bits, color-res}... <CR>
\r
1023 '#' - GCR identifier character (Number Sign)
\r
1025 version - GIF format version number; initially '87a'
\r
1027 protocol='0' - No end-to-end protocol supported by decoder
\r
1029 Transfer as direct 8-bit data stream.
\r
1031 protocol='1' - Can use an error correction protocol to transfer GIF data
\r
1033 interactively from the host directly to the display.
\r
1035 dev = '0' - Screen parameter set follows
\r
1037 dev = '1' - Printer parameter set follows
\r
1039 width- Maximum supported display width in pixels
\r
1041 height - Maximum supported display height in pixels
\r
1043 color-bits - Number of bits per pixel supported. The number of
\r
1045 supported colors is therefore 2**color-bits.
\r
1047 color-res - Number of bits per color component supported in the
\r
1049 hardware color palette. If color-res is '0' then no
\r
1051 hardware palette table is available.
\r
1053 Note that all values in the GCR are returned as ASCII decimal
\r
1055 numbers and the message is terminated by a Carriage Return character.
\r
1057 Graphics Interchange Format (GIF) Page 11
\r
1059 Appendix B - Interactive Sequences
\r
1061 The following GCR message describes three standard EGA
\r
1063 configurations with no printer; the GIF data stream can be processed
\r
1065 within an error correcting protocol:
\r
1067 #87a;1 ;0,320,200,4,0 ;0,640,200,2,2 ;0,640,350,4,2<CR>
\r
1069 ENTER GIF GRAPHICS MODE
\r
1071 Two sequences are currently defined to invoke an interactive GIF
\r
1073 decoder into action. The only difference between them is that different
\r
1075 output media are selected. These sequences are:
\r
1077 ESC [ > 1 g Display GIF image on screen
\r
1079 (0x1B 0x5B 0x3E 0x31 0x67)
\r
1081 ESC [ > 2 g Display image directly to an attached graphics printer.
\r
1083 The image may optionally be displayed on the screen as
\r
1087 (0x1B 0x5B 0x3E 0x32 0x67)
\r
1089 Note that the 'g' character terminating each sequence is in lower
\r
1093 INTERACTIVE ENVIRONMENT
\r
1095 The assumed environment for the transmission of GIF image data from
\r
1097 an interactive application is a full 8-bit data stream from host to
\r
1099 micro. All 256 character codes must be transferrable. The establishing
\r
1101 of an 8-bit data path for communications will normally be taken care of
\r
1103 by the host application programs. It is however up to the receiving
\r
1105 communications programs supporting GIF to be able to receive and pass on
\r
1107 all 256 8-bit codes to the GIF decoder software.
\r
1109 Graphics Interchange Format (GIF) Page 12
\r
1111 Appendix C - Image Packaging & Compression
\r
1113 The Raster Data stream that represents the actual output image can
\r
1115 be represented as:
\r
1123 +---------------+ ---+
\r
1125 |blok byte count| |
\r
1127 +---------------+ |
\r
1129 : : +-- Repeated as many times as necessary
\r
1135 +---------------+ ---+
\r
1141 |0 0 0 0 0 0 0 0| zero byte count (terminates data stream)
\r
1145 The conversion of the image from a series of pixel values to a
\r
1147 transmitted or stored character stream involves several steps. In brief
\r
1151 1. Establish the Code Size - Define the number of bits needed to
\r
1153 represent the actual data.
\r
1155 2. Compress the Data - Compress the series of image pixels to a series
\r
1157 of compression codes.
\r
1159 3. Build a Series of Bytes - Take the set of compression codes and
\r
1161 convert to a string of 8-bit bytes.
\r
1163 4. Package the Bytes - Package sets of bytes into blocks preceeded by
\r
1165 character counts and output.
\r
1167 ESTABLISH CODE SIZE
\r
1169 The first byte of the GIF Raster Data stream is a value indicating
\r
1171 the minimum number of bits required to represent the set of actual pixel
\r
1173 values. Normally this will be the same as the number of color bits.
\r
1175 Because of some algorithmic constraints however, black & white images
\r
1177 which have one color bit must be indicated as having a code size of 2.
\r
1179 This code size value also implies that the compression codes must start
\r
1181 out one bit longer.
\r
1185 The LZW algorithm converts a series of data values into a series of
\r
1187 codes which may be raw values or a code designating a series of values.
\r
1189 Using text characters as an analogy, the output code consists of a
\r
1191 character or a code representing a string of characters.
\r
1193 Graphics Interchange Format (GIF) Page 13
\r
1195 Appendix C - Image Packaging & Compression
\r
1197 The LZW algorithm used in GIF matches algorithmically with the
\r
1199 standard LZW algorithm with the following differences:
\r
1201 1. A special Clear code is defined which resets all
\r
1203 compression/decompression parameters and tables to a start-up state.
\r
1205 The value of this code is 2**<code size>. For example if the code
\r
1207 size indicated was 4 (image was 4 bits/pixel) the Clear code value
\r
1209 would be 16 (10000 binary). The Clear code can appear at any point
\r
1211 in the image data stream and therefore requires the LZW algorithm to
\r
1213 process succeeding codes as if a new data stream was starting.
\r
1215 Encoders should output a Clear code as the first code of each image
\r
1219 2. An End of Information code is defined that explicitly indicates the
\r
1221 end of the image data stream. LZW processing terminates when this
\r
1223 code is encountered. It must be the last code output by the encoder
\r
1225 for an image. The value of this code is <Clear code>+1.
\r
1227 3. The first available compression code value is <Clear code>+2.
\r
1229 4. The output codes are of variable length, starting at <code size>+1
\r
1231 bits per code, up to 12 bits per code. This defines a maximum code
\r
1233 value of 4095 (hex FFF). Whenever the LZW code value would exceed
\r
1235 the current code length, the code length is increased by one. The
\r
1237 packing/unpacking of these codes must then be altered to reflect the
\r
1243 Because the LZW compression used for GIF creates a series of
\r
1245 variable length codes, of between 3 and 12 bits each, these codes must
\r
1247 be reformed into a series of 8-bit bytes that will be the characters
\r
1249 actually stored or transmitted. This provides additional compression of
\r
1251 the image. The codes are formed into a stream of bits as if they were
\r
1253 packed right to left and then picked off 8 bits at a time to be output.
\r
1255 Assuming a character array of 8 bits per character and using 5 bit codes
\r
1257 to be packed, an example layout would be similar to:
\r
1259 byte n byte 5 byte 4 byte 3 byte 2 byte 1
\r
1261 +-.....-----+--------+--------+--------+--------+--------+
\r
1263 | and so on |hhhhhggg|ggfffffe|eeeedddd|dcccccbb|bbbaaaaa|
\r
1265 +-.....-----+--------+--------+--------+--------+--------+
\r
1267 Note that the physical packing arrangement will change as the
\r
1269 number of bits per compression code change but the concept remains the
\r
1275 Once the bytes have been created, they are grouped into blocks for
\r
1277 output by preceeding each block of 0 to 255 bytes with a character count
\r
1279 byte. A block with a zero byte count terminates the Raster Data stream
\r
1281 for a given image. These blocks are what are actually output for the
\r
1283 Graphics Interchange Format (GIF) Page 14
\r
1285 Appendix C - Image Packaging & Compression
\r
1287 GIF image. This block format has the side effect of allowing a decoding
\r
1289 program the ability to read past the actual image data if necessary by
\r
1291 reading block counts and then skipping over the data.
\r
1293 Graphics Interchange Format (GIF) Page 15
\r
1295 Appendix D - Multiple Image Processing
\r
1297 Since a GIF data stream can contain multiple images, it is
\r
1299 necessary to describe processing and display of such a file. Because
\r
1301 the image descriptor allows for placement of the image within the
\r
1303 logical screen, it is possible to define a sequence of images that may
\r
1305 each be a partial screen, but in total fill the entire screen. The
\r
1307 guidelines for handling the multiple image situation are:
\r
1309 1. There is no pause between images. Each is processed immediately as
\r
1311 seen by the decoder.
\r
1313 2. Each image explicitly overwrites any image already on the screen
\r
1315 inside of its window. The only screen clears are at the beginning
\r
1317 and end of the GIF image process. See discussion on the GIF
\r
projects / 16.git / blob