16/PCGPE10/GIF.TXT

   1 \r
   2 \r
   3                    LZW and GIF explained----Steve Blackstock\r
   4 \r
   5 \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
  10 document:\r
  11 \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
  15 character as "K".\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
  25 [...] is empty.\r
  26       "code": a number, specified by a known number of bits, which maps to a\r
  27 string.\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
  32 \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
  43 one to the other.\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
  74 \r
  75      [1] Initialize string table;\r
  76      [2] [.c.] <- empty;\r
  77      [3] K <- next character in charstream;\r
  78      [4] Is [.c.]K in string table?\r
  79       (yes: [.c.] <- [.c.]K;\r
  80             go to [3];\r
  81       )\r
  82       (no: add [.c.]K to the string table;\r
  83            output the code for [.c.] to the codestream;\r
  84            [.c.] <- K;\r
  85            go to [3];\r
  86       )\r
  87 \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
 175 \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
 189            <old> <- <code>\r
 190       )\r
 191      [7] go to [5];\r
 192 \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
 197       ---\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
 238 off like:\r
 239 \r
 240        byte#0: hijabcde\r
 241        byte#1: .klmnofg\r
 242 \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
 257 \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
 264 Keywords: GIF LZW\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
 268 Lines: 1050\r
 269 \r
 270 \r
 271 >From: cmcl2!neuron1.Jpl.Nasa.Gov!harry (Harry Langenbacher)\r
 272 \r
 273                                 G I F (tm)\r
 274 \r
 275                      Graphics Interchange Format (tm)\r
 276 \r
 277                       A standard defining a mechanism\r
 278 \r
 279                      for the storage and transmission\r
 280 \r
 281                    of raster-based graphics information\r
 282 \r
 283                                June 15, 1987\r
 284 \r
 285                      (c) CompuServe Incorporated, 1987\r
 286 \r
 287                             All rights reserved\r
 288 \r
 289             While this document is copyrighted, the information\r
 290 \r
 291           contained within is made available for use in computer\r
 292 \r
 293           software without royalties, or licensing restrictions.\r
 294 \r
 295           GIF and 'Graphics Interchange Format' are trademarks of\r
 296 \r
 297                          CompuServe, Incorporated.\r
 298 \r
 299                            an H&R Block Company\r
 300 \r
 301                         5000 Arlington Centre Blvd.\r
 302 \r
 303                            Columbus, Ohio 43220\r
 304 \r
 305                               (614) 457-8600\r
 306 \r
 307                                                                      Page 2\r
 308 \r
 309               Graphics Interchange Format (GIF) Specification\r
 310 \r
 311                              Table of Contents\r
 312 \r
 313         INTRODUCTION . . . . . . . . . . . . . . . . . page 3\r
 314 \r
 315         GENERAL FILE FORMAT  . . . . . . . . . . . . . page 3\r
 316 \r
 317         GIF SIGNATURE  . . . . . . . . . . . . . . . . page 4\r
 318 \r
 319         SCREEN DESCRIPTOR  . . . . . . . . . . . . . . page 4\r
 320 \r
 321         GLOBAL COLOR MAP . . . . . . . . . . . . . . . page 5\r
 322 \r
 323         IMAGE DESCRIPTOR . . . . . . . . . . . . . . . page 6\r
 324 \r
 325         LOCAL COLOR MAP  . . . . . . . . . . . . . . . page 7\r
 326 \r
 327         RASTER DATA  . . . . . . . . . . . . . . . . . page 7\r
 328 \r
 329         GIF TERMINATOR . . . . . . . . . . . . . . . . page 8\r
 330 \r
 331         GIF EXTENSION BLOCKS . . . . . . . . . . . . . page 8\r
 332 \r
 333         APPENDIX A - GLOSSARY  . . . . . . . . . . . . page 9\r
 334 \r
 335         APPENDIX B - INTERACTIVE SEQUENCES . . . . . . page 10\r
 336 \r
 337         APPENDIX C - IMAGE PACKAGING & COMPRESSION . . page 12\r
 338 \r
 339         APPENDIX D - MULTIPLE IMAGE PROCESSING . . . . page 15\r
 340 \r
 341 Graphics Interchange Format (GIF)                                    Page 3\r
 342 \r
 343 Specification\r
 344 \r
 345 INTRODUCTION\r
 346 \r
 347         'GIF' (tm) is CompuServe's standard for defining generalized  color\r
 348 \r
 349    raster   images.    This   'Graphics  Interchange  Format'  (tm)  allows\r
 350 \r
 351    high-quality, high-resolution graphics to be displayed on a  variety  of\r
 352 \r
 353    graphics  hardware  and is intended as an exchange and display mechanism\r
 354 \r
 355    for graphics images.  The image format described  in  this  document  is\r
 356 \r
 357    designed  to  support  current  and  future image technology and will in\r
 358 \r
 359    addition serve as a basis for future CompuServe graphics products.\r
 360 \r
 361         The main focus  of  this  document  is  to  provide  the  technical\r
 362 \r
 363    information  necessary  for  a  programmer to implement GIF encoders and\r
 364 \r
 365    decoders.  As such, some assumptions are made as to terminology relavent\r
 366 \r
 367    to graphics and programming in general.\r
 368 \r
 369         The first section of this document describes the  GIF  data  format\r
 370 \r
 371    and its components and applies to all GIF decoders, either as standalone\r
 372 \r
 373    programs or as part of  a  communications  package.   Appendix  B  is  a\r
 374 \r
 375    section  relavent to decoders that are part of a communications software\r
 376 \r
 377    package and describes the protocol requirements for entering and exiting\r
 378 \r
 379    GIF mode, and responding to host interrogations.  A glossary in Appendix\r
 380 \r
 381    A defines some of the terminology used in  this  document.   Appendix  C\r
 382 \r
 383    gives  a  detailed  explanation  of  how  the  graphics  image itself is\r
 384 \r
 385    packaged as a series of data bytes.\r
 386 \r
 387                 Graphics Interchange Format Data Definition\r
 388 \r
 389  GENERAL FILE FORMAT\r
 390 \r
 391         +-----------------------+\r
 392 \r
 393         | +-------------------+ |\r
 394 \r
 395         | |   GIF Signature   | |\r
 396 \r
 397         | +-------------------+ |\r
 398 \r
 399         | +-------------------+ |\r
 400 \r
 401         | | Screen Descriptor | |\r
 402 \r
 403         | +-------------------+ |\r
 404 \r
 405         | +-------------------+ |\r
 406 \r
 407         | | Global Color Map  | |\r
 408 \r
 409         | +-------------------+ |\r
 410 \r
 411         . . .               . . .\r
 412 \r
 413         | +-------------------+ |    ---+\r
 414 \r
 415         | |  Image Descriptor | |       |\r
 416 \r
 417         | +-------------------+ |       |\r
 418 \r
 419         | +-------------------+ |       |\r
 420 \r
 421         | |  Local Color Map  | |       |-   Repeated 1 to n times\r
 422 \r
 423         | +-------------------+ |       |\r
 424 \r
 425         | +-------------------+ |       |\r
 426 \r
 427         | |    Raster Data    | |       |\r
 428 \r
 429         | +-------------------+ |    ---+\r
 430 \r
 431         . . .               . . .\r
 432 \r
 433         |-    GIF Terminator   -|\r
 434 \r
 435         +-----------------------+\r
 436 \r
 437 Graphics Interchange Format (GIF)                                    Page 4\r
 438 \r
 439 Specification\r
 440 \r
 441  GIF SIGNATURE\r
 442 \r
 443         The following GIF Signature identifies  the  data  following  as  a\r
 444 \r
 445    valid GIF image stream.  It consists of the following six characters:\r
 446 \r
 447              G I F 8 7 a\r
 448 \r
 449         The last three characters '87a' may be viewed as a  version  number\r
 450 \r
 451    for  this  particular  GIF  definition  and will be used in general as a\r
 452 \r
 453    reference  in  documents  regarding  GIF  that   address   any   version\r
 454 \r
 455    dependencies.\r
 456 \r
 457  SCREEN DESCRIPTOR\r
 458 \r
 459         The Screen Descriptor describes the overall parameters for all  GIF\r
 460 \r
 461    images  following.  It defines the overall dimensions of the image space\r
 462 \r
 463    or logical screen required, the existance of color mapping  information,\r
 464 \r
 465    background  screen color, and color depth information.  This information\r
 466 \r
 467    is stored in a series of 8-bit bytes as described below.\r
 468 \r
 469               bits\r
 470 \r
 471          7 6 5 4 3 2 1 0  Byte #\r
 472 \r
 473         +---------------+\r
 474 \r
 475         |               |  1\r
 476 \r
 477         +-Screen Width -+      Raster width in pixels (LSB first)\r
 478 \r
 479         |               |  2\r
 480 \r
 481         +---------------+\r
 482 \r
 483         |               |  3\r
 484 \r
 485         +-Screen Height-+      Raster height in pixels (LSB first)\r
 486 \r
 487         |               |  4\r
 488 \r
 489         +-+-----+-+-----+      M = 1, Global color map follows Descriptor\r
 490 \r
 491         |M|  cr |0|pixel|  5   cr+1 = # bits of color resolution\r
 492 \r
 493         +-+-----+-+-----+      pixel+1 = # bits/pixel in image\r
 494 \r
 495         |   background  |  6   background=Color index of screen background\r
 496 \r
 497         +---------------+          (color is defined from the Global color\r
 498 \r
 499         |0 0 0 0 0 0 0 0|  7        map or default map if none specified)\r
 500 \r
 501         +---------------+\r
 502 \r
 503         The logical screen width and height can both  be  larger  than  the\r
 504 \r
 505    physical  display.   How  images  larger  than  the physical display are\r
 506 \r
 507    handled is implementation dependent and can take advantage  of  hardware\r
 508 \r
 509    characteristics  (e.g.   Macintosh scrolling windows).  Otherwise images\r
 510 \r
 511    can be clipped to the edges of the display.\r
 512 \r
 513         The value of 'pixel' also defines  the  maximum  number  of  colors\r
 514 \r
 515    within  an  image.   The  range  of  values  for 'pixel' is 0 to 7 which\r
 516 \r
 517    represents 1 to 8 bits.  This translates to a range of 2 (B & W) to  256\r
 518 \r
 519    colors.   Bit  3 of word 5 is reserved for future definition and must be\r
 520 \r
 521    zero.\r
 522 \r
 523 Graphics Interchange Format (GIF)                                    Page 5\r
 524 \r
 525 Specification\r
 526 \r
 527  GLOBAL COLOR MAP\r
 528 \r
 529         The Global Color Map is optional but recommended for  images  where\r
 530 \r
 531    accurate color rendition is desired.  The existence of this color map is\r
 532 \r
 533    indicated in the 'M' field of byte 5 of the Screen Descriptor.  A  color\r
 534 \r
 535    map  can  also  be associated with each image in a GIF file as described\r
 536 \r
 537    later.  However this  global  map  will  normally  be  used  because  of\r
 538 \r
 539    hardware  restrictions  in equipment available today.  In the individual\r
 540 \r
 541    Image Descriptors the 'M' flag will normally be  zero.   If  the  Global\r
 542 \r
 543    Color  Map  is  present,  it's definition immediately follows the Screen\r
 544 \r
 545    Descriptor.   The  number  of  color  map  entries  following  a  Screen\r
 546 \r
 547    Descriptor  is equal to 2**(# bits per pixel), where each entry consists\r
 548 \r
 549    of three byte values representing the relative intensities of red, green\r
 550 \r
 551    and blue respectively.  The structure of the Color Map block is:\r
 552 \r
 553               bits\r
 554 \r
 555          7 6 5 4 3 2 1 0  Byte #\r
 556 \r
 557         +---------------+\r
 558 \r
 559         | red intensity |  1    Red value for color index 0\r
 560 \r
 561         +---------------+\r
 562 \r
 563         |green intensity|  2    Green value for color index 0\r
 564 \r
 565         +---------------+\r
 566 \r
 567         | blue intensity|  3    Blue value for color index 0\r
 568 \r
 569         +---------------+\r
 570 \r
 571         | red intensity |  4    Red value for color index 1\r
 572 \r
 573         +---------------+\r
 574 \r
 575         |green intensity|  5    Green value for color index 1\r
 576 \r
 577         +---------------+\r
 578 \r
 579         | blue intensity|  6    Blue value for color index 1\r
 580 \r
 581         +---------------+\r
 582 \r
 583         :               :       (Continues for remaining colors)\r
 584 \r
 585         Each image pixel value received will be displayed according to  its\r
 586 \r
 587    closest match with an available color of the display based on this color\r
 588 \r
 589    map.  The color components represent a fractional intensity  value  from\r
 590 \r
 591    none  (0)  to  full (255).  White would be represented as (255,255,255),\r
 592 \r
 593    black as (0,0,0) and medium yellow as (180,180,0).  For display, if  the\r
 594 \r
 595    device  supports fewer than 8 bits per color component, the higher order\r
 596 \r
 597    bits of each component are used.  In the creation of  a  GIF  color  map\r
 598 \r
 599    entry  with  hardware  supporting  fewer  than 8 bits per component, the\r
 600 \r
 601    component values for the hardware  should  be  converted  to  the  8-bit\r
 602 \r
 603    format with the following calculation:\r
 604 \r
 605         <map_value> = <component_value>*255/(2**<nbits> -1)\r
 606 \r
 607         This assures accurate translation of colors for all  displays.   In\r
 608 \r
 609    the  cases  of  creating  GIF images from hardware without color palette\r
 610 \r
 611    capability, a fixed palette should be created  based  on  the  available\r
 612 \r
 613    display  colors for that hardware.  If no Global Color Map is indicated,\r
 614 \r
 615    a default color map is generated internally  which  maps  each  possible\r
 616 \r
 617    incoming  color  index to the same hardware color index modulo <n> where\r
 618 \r
 619    <n> is the number of available hardware colors.\r
 620 \r
 621 Graphics Interchange Format (GIF)                                    Page 6\r
 622 \r
 623 Specification\r
 624 \r
 625  IMAGE DESCRIPTOR\r
 626 \r
 627         The Image Descriptor defines the actual placement  and  extents  of\r
 628 \r
 629    the  following  image within the space defined in the Screen Descriptor.\r
 630 \r
 631    Also defined are flags to indicate the presence of a local color  lookup\r
 632 \r
 633    map, and to define the pixel display sequence.  Each Image Descriptor is\r
 634 \r
 635    introduced by an image separator  character.   The  role  of  the  Image\r
 636 \r
 637    Separator  is simply to provide a synchronization character to introduce\r
 638 \r
 639    an Image Descriptor.  This is desirable if a GIF file happens to contain\r
 640 \r
 641    more  than  one  image.   This  character  is defined as 0x2C hex or ','\r
 642 \r
 643    (comma).  When this character is encountered between images,  the  Image\r
 644 \r
 645    Descriptor will follow immediately.\r
 646 \r
 647         Any characters encountered between the end of a previous image  and\r
 648 \r
 649    the image separator character are to be ignored.  This allows future GIF\r
 650 \r
 651    enhancements to be present in newer image formats and yet ignored safely\r
 652 \r
 653    by older software decoders.\r
 654 \r
 655               bits\r
 656 \r
 657          7 6 5 4 3 2 1 0  Byte #\r
 658 \r
 659         +---------------+\r
 660 \r
 661         |0 0 1 0 1 1 0 0|  1    ',' - Image separator character\r
 662 \r
 663         +---------------+\r
 664 \r
 665         |               |  2    Start of image in pixels from the\r
 666 \r
 667         +-  Image Left -+       left side of the screen (LSB first)\r
 668 \r
 669         |               |  3\r
 670 \r
 671         +---------------+\r
 672 \r
 673         |               |  4\r
 674 \r
 675         +-  Image Top  -+       Start of image in pixels from the\r
 676 \r
 677         |               |  5    top of the screen (LSB first)\r
 678 \r
 679         +---------------+\r
 680 \r
 681         |               |  6\r
 682 \r
 683         +- Image Width -+       Width of the image in pixels (LSB first)\r
 684 \r
 685         |               |  7\r
 686 \r
 687         +---------------+\r
 688 \r
 689         |               |  8\r
 690 \r
 691         +- Image Height-+       Height of the image in pixels (LSB first)\r
 692 \r
 693         |               |  9\r
 694 \r
 695         +-+-+-+-+-+-----+       M=0 - Use global color map, ignore 'pixel'\r
 696 \r
 697         |M|I|0|0|0|pixel| 10    M=1 - Local color map follows, use 'pixel'\r
 698 \r
 699         +-+-+-+-+-+-----+       I=0 - Image formatted in Sequential order\r
 700 \r
 701                                 I=1 - Image formatted in Interlaced order\r
 702 \r
 703                                 pixel+1 - # bits per pixel for this image\r
 704 \r
 705         The specifications for the image position and size must be confined\r
 706 \r
 707    to  the  dimensions defined by the Screen Descriptor.  On the other hand\r
 708 \r
 709    it is not necessary that the image fill the entire screen defined.\r
 710 \r
 711  LOCAL COLOR MAP\r
 712 \r
 713 Graphics Interchange Format (GIF)                                    Page 7\r
 714 \r
 715 Specification\r
 716 \r
 717         A Local Color Map is optional and defined here for future use.   If\r
 718 \r
 719    the  'M' bit of byte 10 of the Image Descriptor is set, then a color map\r
 720 \r
 721    follows the Image Descriptor that applies only to the  following  image.\r
 722 \r
 723    At the end of the image, the color map will revert to that defined after\r
 724 \r
 725    the Screen Descriptor.  Note that the 'pixel' field of byte  10  of  the\r
 726 \r
 727    Image  Descriptor  is used only if a Local Color Map is indicated.  This\r
 728 \r
 729    defines the parameters not only for the image pixel size, but determines\r
 730 \r
 731    the  number  of color map entries that follow.  The bits per pixel value\r
 732 \r
 733    will also revert to the value specified in the  Screen  Descriptor  when\r
 734 \r
 735    processing of the image is complete.\r
 736 \r
 737  RASTER DATA\r
 738 \r
 739         The format of the actual image is defined as the  series  of  pixel\r
 740 \r
 741    color  index  values that make up the image.  The pixels are stored left\r
 742 \r
 743    to right sequentially for an image row.  By default each  image  row  is\r
 744 \r
 745    written  sequentially, top to bottom.  In the case that the Interlace or\r
 746 \r
 747    'I' bit is set in byte 10 of the Image Descriptor then the row order  of\r
 748 \r
 749    the  image  display  follows  a  four-pass process in which the image is\r
 750 \r
 751    filled in by widely spaced rows.  The first pass writes every  8th  row,\r
 752 \r
 753    starting  with  the top row of the image window.  The second pass writes\r
 754 \r
 755    every 8th row starting at the fifth row from the top.   The  third  pass\r
 756 \r
 757    writes every 4th row starting at the third row from the top.  The fourth\r
 758 \r
 759    pass completes the image, writing  every  other  row,  starting  at  the\r
 760 \r
 761    second row from the top.  A graphic description of this process follows:\r
 762 \r
 763    Image\r
 764 \r
 765    Row  Pass 1  Pass 2  Pass 3  Pass 4          Result\r
 766 \r
 767    ---------------------------------------------------\r
 768 \r
 769      0  **1a**                                  **1a**\r
 770 \r
 771      1                          **4a**          **4a**\r
 772 \r
 773      2                  **3a**                  **3a**\r
 774 \r
 775      3                          **4b**          **4b**\r
 776 \r
 777      4          **2a**                          **2a**\r
 778 \r
 779      5                          **4c**          **4c**\r
 780 \r
 781      6                  **3b**                  **3b**\r
 782 \r
 783      7                          **4d**          **4d**\r
 784 \r
 785      8  **1b**                                  **1b**\r
 786 \r
 787      9                          **4e**          **4e**\r
 788 \r
 789     10                  **3c**                  **3c**\r
 790 \r
 791     11                          **4f**          **4f**\r
 792 \r
 793     12          **2b**                          **2b**\r
 794 \r
 795    . . .\r
 796 \r
 797         The image pixel values are processed as a series of  color  indices\r
 798 \r
 799    which  map  into the existing color map.  The resulting color value from\r
 800 \r
 801    the map is what is actually displayed.  This series  of  pixel  indices,\r
 802 \r
 803    the  number  of  which  is equal to image-width*image-height pixels, are\r
 804 \r
 805    passed to the GIF image data stream one value per pixel, compressed  and\r
 806 \r
 807    packaged  according  to  a  version  of the LZW compression algorithm as\r
 808 \r
 809    defined in Appendix C.\r
 810 \r
 811 Graphics Interchange Format (GIF)                                    Page 8\r
 812 \r
 813 Specification\r
 814 \r
 815  GIF TERMINATOR\r
 816 \r
 817         In order to provide a synchronization for the termination of a  GIF\r
 818 \r
 819    image  file,  a  GIF  decoder  will process the end of GIF mode when the\r
 820 \r
 821    character 0x3B hex or ';' is found after an image  has  been  processed.\r
 822 \r
 823    By  convention  the  decoding software will pause and wait for an action\r
 824 \r
 825    indicating that the user is ready to continue.  This may be  a  carriage\r
 826 \r
 827    return  entered  at  the  keyboard  or  a  mouse click.  For interactive\r
 828 \r
 829    applications this user action must  be  passed  on  to  the  host  as  a\r
 830 \r
 831    carriage  return  character  so  that the host application can continue.\r
 832 \r
 833    The decoding software will then typically leave graphics mode and resume\r
 834 \r
 835    any previous process.\r
 836 \r
 837  GIF EXTENSION BLOCKS\r
 838 \r
 839         To provide for orderly extension of the GIF definition, a mechanism\r
 840 \r
 841    for  defining  the  packaging  of extensions within a GIF data stream is\r
 842 \r
 843    necessary.  Specific GIF extensions are to be defined and documented  by\r
 844 \r
 845    CompuServe in order to provide a controlled enhancement path.\r
 846 \r
 847         GIF Extension Blocks are packaged in a manner similar to that  used\r
 848 \r
 849    by the raster data though not compressed.  The basic structure is:\r
 850 \r
 851          7 6 5 4 3 2 1 0  Byte #\r
 852 \r
 853         +---------------+\r
 854 \r
 855         |0 0 1 0 0 0 0 1|  1       '!' - GIF Extension Block Introducer\r
 856 \r
 857         +---------------+\r
 858 \r
 859         | function code |  2       Extension function code (0 to 255)\r
 860 \r
 861         +---------------+    ---+\r
 862 \r
 863         |  byte count   |       |\r
 864 \r
 865         +---------------+       |\r
 866 \r
 867         :               :       +-- Repeated as many times as necessary\r
 868 \r
 869         |func data bytes|       |\r
 870 \r
 871         :               :       |\r
 872 \r
 873         +---------------+    ---+\r
 874 \r
 875         . . .       . . .\r
 876 \r
 877         +---------------+\r
 878 \r
 879         |0 0 0 0 0 0 0 0|       zero byte count (terminates block)\r
 880 \r
 881         +---------------+\r
 882 \r
 883         A GIF Extension Block may immediately preceed any Image  Descriptor\r
 884 \r
 885    or occur before the GIF Terminator.\r
 886 \r
 887         All GIF decoders must be able to recognize  the  existence  of  GIF\r
 888 \r
 889    Extension  Blocks  and  read past them if unable to process the function\r
 890 \r
 891    code.  This ensures that older decoders will be able to process extended\r
 892 \r
 893    GIF   image   files   in  the  future,  though  without  the  additional\r
 894 \r
 895    functionality.\r
 896 \r
 897 Graphics Interchange Format (GIF)                                    Page 9\r
 898 \r
 899 Appendix A - Glossary\r
 900 \r
 901                                  GLOSSARY\r
 902 \r
 903 Pixel - The smallest picture element of a  graphics  image.   This  usually\r
 904 \r
 905    corresponds  to  a single dot on a graphics screen.  Image resolution is\r
 906 \r
 907    typically given in units of  pixels.   For  example  a  fairly  standard\r
 908 \r
 909    graphics  screen  format  is  one 320 pixels across and 200 pixels high.\r
 910 \r
 911    Each pixel can  appear  as  one  of  several  colors  depending  on  the\r
 912 \r
 913    capabilities of the graphics hardware.\r
 914 \r
 915 Raster - A horizontal row of pixels representing one line of an  image.   A\r
 916 \r
 917    typical method of working with images since most hardware is oriented to\r
 918 \r
 919    work most efficiently in this manner.\r
 920 \r
 921 LSB - Least Significant Byte.  Refers to a convention for two byte  numeric\r
 922 \r
 923    values in which the less significant byte of the value preceeds the more\r
 924 \r
 925    significant byte.  This convention is typical on many microcomputers.\r
 926 \r
 927 Color Map - The list of definitions of each color  used  in  a  GIF  image.\r
 928 \r
 929    These  desired  colors are converted to available colors through a table\r
 930 \r
 931    which is derived by assigning an incoming color index (from  the  image)\r
 932 \r
 933    to  an  output  color  index  (of  the  hardware).   While the color map\r
 934 \r
 935    definitons are specified in a GIF image, the output  pixel  colors  will\r
 936 \r
 937    vary  based  on  the  hardware used and its ability to match the defined\r
 938 \r
 939    color.\r
 940 \r
 941 Interlace - The method of displaying a GIF image in which  multiple  passes\r
 942 \r
 943    are  made,  outputting  raster  lines  spaced  apart to provide a way of\r
 944 \r
 945    visualizing the general content of an entire image  before  all  of  the\r
 946 \r
 947    data has been processed.\r
 948 \r
 949 B Protocol - A CompuServe-developed error-correcting file transfer protocol\r
 950 \r
 951    available  in  the  public  domain  and implemented in CompuServe VIDTEX\r
 952 \r
 953    products.  This error checking mechanism will be used  in  transfers  of\r
 954 \r
 955    GIF images for interactive applications.\r
 956 \r
 957 LZW - A sophisticated data compression algorithm  based  on  work  done  by\r
 958 \r
 959    Lempel-Ziv  &  Welch  which  has  the feature of very efficient one-pass\r
 960 \r
 961    encoding and decoding.  This allows the image  to  be  decompressed  and\r
 962 \r
 963    displayed  at  the  same  time.   The  original  article from which this\r
 964 \r
 965    technique was adapted is:\r
 966 \r
 967           Terry  A.   Welch,  "A  Technique  for  High   Performance   Data\r
 968 \r
 969           Compression", IEEE Computer, vol 17 no 6 (June 1984)\r
 970 \r
 971         This basic algorithm is also used in the  public  domain  ARC  file\r
 972 \r
 973    compression  utilities.   The  CompuServe  adaptation  of LZW for GIF is\r
 974 \r
 975    described in Appendix C.\r
 976 \r
 977 Graphics Interchange Format (GIF)                                   Page 10\r
 978 \r
 979 Appendix B - Interactive Sequences\r
 980 \r
 981            GIF Sequence Exchanges for an Interactive Environment\r
 982 \r
 983         The following sequences are defined for use  in  mediating  control\r
 984 \r
 985    between a GIF sender and GIF receiver over an interactive communications\r
 986 \r
 987    line.  These  sequences  do  not  apply  to  applications  that  involve\r
 988 \r
 989    downloading  of  static  GIF  files and are not considered part of a GIF\r
 990 \r
 991    file.\r
 992 \r
 993  GIF CAPABILITIES ENQUIRY\r
 994 \r
 995         The GCE sequence is issued from a host and requests an  interactive\r
 996 \r
 997    GIF  decoder  to  return  a  response  message that defines the graphics\r
 998 \r
 999    parameters for the decoder.  This involves returning  information  about\r
1000 \r
1001    available screen sizes, number of bits/color supported and the amount of\r
1002 \r
1003    color detail supported.  The escape sequence for the GCE is defined as:\r
1004 \r
1005         ESC [ > 0 g     (g is lower case, spaces inserted for clarity)\r
1006 \r
1007                          (0x1B 0x5B 0x3E 0x30 0x67)\r
1008 \r
1009  GIF CAPABILITIES RESPONSE\r
1010 \r
1011         The GIF Capabilities Response message is returned by an interactive\r
1012 \r
1013    GIF  decoder  and  defines  the  decoder's  display capabilities for all\r
1014 \r
1015    graphics modes that are supported by the software.  Note that  this  can\r
1016 \r
1017    also include graphics printers as well as a monitor screen.  The general\r
1018 \r
1019    format of this message is:\r
1020 \r
1021      #version;protocol{;dev, width, height, color-bits, color-res}... <CR>\r
1022 \r
1023    '#'          - GCR identifier character (Number Sign)\r
1024 \r
1025    version      - GIF format version number;  initially '87a'\r
1026 \r
1027    protocol='0' - No end-to-end protocol supported by decoder\r
1028 \r
1029                   Transfer as direct 8-bit data stream.\r
1030 \r
1031    protocol='1' - Can use an error correction protocol to transfer GIF data\r
1032 \r
1033                interactively from the host directly to the display.\r
1034 \r
1035    dev = '0'    - Screen parameter set follows\r
1036 \r
1037    dev = '1'    - Printer parameter set follows\r
1038 \r
1039    width- Maximum supported display width in pixels\r
1040 \r
1041    height       - Maximum supported display height in pixels\r
1042 \r
1043    color-bits   - Number of  bits  per  pixel  supported.   The  number  of\r
1044 \r
1045                supported colors is therefore 2**color-bits.\r
1046 \r
1047    color-res    - Number of bits  per  color  component  supported  in  the\r
1048 \r
1049                hardware  color  palette.   If  color-res  is  '0'  then  no\r
1050 \r
1051                hardware palette table is available.\r
1052 \r
1053         Note that all values in the  GCR  are  returned  as  ASCII  decimal\r
1054 \r
1055    numbers and the message is terminated by a Carriage Return character.\r
1056 \r
1057 Graphics Interchange Format (GIF)                                   Page 11\r
1058 \r
1059 Appendix B - Interactive Sequences\r
1060 \r
1061         The  following   GCR   message   describes   three   standard   EGA\r
1062 \r
1063    configurations  with  no  printer;  the GIF data stream can be processed\r
1064 \r
1065    within an error correcting protocol:\r
1066 \r
1067         #87a;1 ;0,320,200,4,0 ;0,640,200,2,2 ;0,640,350,4,2<CR>\r
1068 \r
1069  ENTER GIF GRAPHICS MODE\r
1070 \r
1071         Two sequences are currently defined to invoke  an  interactive  GIF\r
1072 \r
1073    decoder into action.  The only difference between them is that different\r
1074 \r
1075    output media are selected.  These sequences are:\r
1076 \r
1077      ESC [ > 1 g   Display GIF image on screen\r
1078 \r
1079                    (0x1B 0x5B 0x3E 0x31 0x67)\r
1080 \r
1081      ESC [ > 2 g   Display image directly to an attached graphics  printer.\r
1082 \r
1083                    The  image  may optionally be displayed on the screen as\r
1084 \r
1085                    well.\r
1086 \r
1087                    (0x1B 0x5B 0x3E 0x32 0x67)\r
1088 \r
1089         Note that the 'g' character terminating each sequence is  in  lower\r
1090 \r
1091    case.\r
1092 \r
1093  INTERACTIVE ENVIRONMENT\r
1094 \r
1095         The assumed environment for the transmission of GIF image data from\r
1096 \r
1097    an  interactive  application  is  a  full 8-bit data stream from host to\r
1098 \r
1099    micro.  All 256 character codes must be transferrable.  The establishing\r
1100 \r
1101    of  an 8-bit data path for communications will normally be taken care of\r
1102 \r
1103    by the host application programs.  It is however  up  to  the  receiving\r
1104 \r
1105    communications programs supporting GIF to be able to receive and pass on\r
1106 \r
1107    all 256 8-bit codes to the GIF decoder software.\r
1108 \r
1109 Graphics Interchange Format (GIF)                                   Page 12\r
1110 \r
1111 Appendix C - Image Packaging & Compression\r
1112 \r
1113         The Raster Data stream that represents the actual output image  can\r
1114 \r
1115    be represented as:\r
1116 \r
1117          7 6 5 4 3 2 1 0\r
1118 \r
1119         +---------------+\r
1120 \r
1121         |   code size   |\r
1122 \r
1123         +---------------+     ---+\r
1124 \r
1125         |blok byte count|        |\r
1126 \r
1127         +---------------+        |\r
1128 \r
1129         :               :        +-- Repeated as many times as necessary\r
1130 \r
1131         |  data bytes   |        |\r
1132 \r
1133         :               :        |\r
1134 \r
1135         +---------------+     ---+\r
1136 \r
1137         . . .       . . .\r
1138 \r
1139         +---------------+\r
1140 \r
1141         |0 0 0 0 0 0 0 0|       zero byte count (terminates data stream)\r
1142 \r
1143         +---------------+\r
1144 \r
1145         The conversion of the image from a series  of  pixel  values  to  a\r
1146 \r
1147    transmitted or stored character stream involves several steps.  In brief\r
1148 \r
1149    these steps are:\r
1150 \r
1151    1.  Establish the Code Size -  Define  the  number  of  bits  needed  to\r
1152 \r
1153        represent the actual data.\r
1154 \r
1155    2.  Compress the Data - Compress the series of image pixels to a  series\r
1156 \r
1157        of compression codes.\r
1158 \r
1159    3.  Build a Series of Bytes - Take the  set  of  compression  codes  and\r
1160 \r
1161        convert to a string of 8-bit bytes.\r
1162 \r
1163    4.  Package the Bytes - Package sets of bytes into blocks  preceeded  by\r
1164 \r
1165        character counts and output.\r
1166 \r
1167 ESTABLISH CODE SIZE\r
1168 \r
1169         The first byte of the GIF Raster Data stream is a value  indicating\r
1170 \r
1171    the minimum number of bits required to represent the set of actual pixel\r
1172 \r
1173    values.  Normally this will be the same as the  number  of  color  bits.\r
1174 \r
1175    Because  of  some  algorithmic constraints however, black & white images\r
1176 \r
1177    which have one color bit must be indicated as having a code size  of  2.\r
1178 \r
1179    This  code size value also implies that the compression codes must start\r
1180 \r
1181    out one bit longer.\r
1182 \r
1183 COMPRESSION\r
1184 \r
1185         The LZW algorithm converts a series of data values into a series of\r
1186 \r
1187    codes  which may be raw values or a code designating a series of values.\r
1188 \r
1189    Using text characters as an analogy,  the  output  code  consists  of  a\r
1190 \r
1191    character or a code representing a string of characters.\r
1192 \r
1193 Graphics Interchange Format (GIF)                                   Page 13\r
1194 \r
1195 Appendix C - Image Packaging & Compression\r
1196 \r
1197         The LZW algorithm used in  GIF  matches  algorithmically  with  the\r
1198 \r
1199    standard LZW algorithm with the following differences:\r
1200 \r
1201    1.  A   special   Clear   code   is    defined    which    resets    all\r
1202 \r
1203        compression/decompression parameters and tables to a start-up state.\r
1204 \r
1205        The value of this code is 2**<code size>.  For example if  the  code\r
1206 \r
1207        size  indicated  was 4 (image was 4 bits/pixel) the Clear code value\r
1208 \r
1209        would be 16 (10000 binary).  The Clear code can appear at any  point\r
1210 \r
1211        in the image data stream and therefore requires the LZW algorithm to\r
1212 \r
1213        process succeeding codes as if  a  new  data  stream  was  starting.\r
1214 \r
1215        Encoders  should output a Clear code as the first code of each image\r
1216 \r
1217        data stream.\r
1218 \r
1219    2.  An End of Information code is defined that explicitly indicates  the\r
1220 \r
1221        end  of  the image data stream.  LZW processing terminates when this\r
1222 \r
1223        code is encountered.  It must be the last code output by the encoder\r
1224 \r
1225        for an image.  The value of this code is <Clear code>+1.\r
1226 \r
1227    3.  The first available compression code value is <Clear code>+2.\r
1228 \r
1229    4.  The output codes are of variable length, starting  at  <code size>+1\r
1230 \r
1231        bits  per code, up to 12 bits per code.  This defines a maximum code\r
1232 \r
1233        value of 4095 (hex FFF).  Whenever the LZW code value  would  exceed\r
1234 \r
1235        the  current  code length, the code length is increased by one.  The\r
1236 \r
1237        packing/unpacking of these codes must then be altered to reflect the\r
1238 \r
1239        new code length.\r
1240 \r
1241 BUILD 8-BIT BYTES\r
1242 \r
1243         Because the LZW compression  used  for  GIF  creates  a  series  of\r
1244 \r
1245    variable  length  codes, of between 3 and 12 bits each, these codes must\r
1246 \r
1247    be reformed into a series of 8-bit bytes that  will  be  the  characters\r
1248 \r
1249    actually stored or transmitted.  This provides additional compression of\r
1250 \r
1251    the image.  The codes are formed into a stream of bits as if  they  were\r
1252 \r
1253    packed  right to left and then picked off 8 bits at a time to be output.\r
1254 \r
1255    Assuming a character array of 8 bits per character and using 5 bit codes\r
1256 \r
1257    to be packed, an example layout would be similar to:\r
1258 \r
1259          byte n       byte 5   byte 4   byte 3   byte 2   byte 1\r
1260 \r
1261         +-.....-----+--------+--------+--------+--------+--------+\r
1262 \r
1263         | and so on |hhhhhggg|ggfffffe|eeeedddd|dcccccbb|bbbaaaaa|\r
1264 \r
1265         +-.....-----+--------+--------+--------+--------+--------+\r
1266 \r
1267         Note that the physical  packing  arrangement  will  change  as  the\r
1268 \r
1269    number  of  bits per compression code change but the concept remains the\r
1270 \r
1271    same.\r
1272 \r
1273 PACKAGE THE BYTES\r
1274 \r
1275         Once the bytes have been created, they are grouped into blocks  for\r
1276 \r
1277    output by preceeding each block of 0 to 255 bytes with a character count\r
1278 \r
1279    byte.  A block with a zero byte count terminates the Raster Data  stream\r
1280 \r
1281    for  a  given  image.  These blocks are what are actually output for the\r
1282 \r
1283 Graphics Interchange Format (GIF)                                   Page 14\r
1284 \r
1285 Appendix C - Image Packaging & Compression\r
1286 \r
1287    GIF image.  This block format has the side effect of allowing a decoding\r
1288 \r
1289    program  the  ability to read past the actual image data if necessary by\r
1290 \r
1291    reading block counts and then skipping over the data.\r
1292 \r
1293 Graphics Interchange Format (GIF)                                   Page 15\r
1294 \r
1295 Appendix D - Multiple Image Processing\r
1296 \r
1297         Since a  GIF  data  stream  can  contain  multiple  images,  it  is\r
1298 \r
1299    necessary  to  describe  processing and display of such a file.  Because\r
1300 \r
1301    the image descriptor allows  for  placement  of  the  image  within  the\r
1302 \r
1303    logical  screen,  it is possible to define a sequence of images that may\r
1304 \r
1305    each be a partial screen, but in total  fill  the  entire  screen.   The\r
1306 \r
1307    guidelines for handling the multiple image situation are:\r
1308 \r
1309    1.  There is no pause between images.  Each is processed immediately  as\r
1310 \r
1311        seen by the decoder.\r
1312 \r
1313    2.  Each image explicitly overwrites any image  already  on  the  screen\r
1314 \r
1315        inside  of  its window.  The only screen clears are at the beginning\r
1316 \r
1317        and end of the  GIF  image  process.   See  discussion  on  the  GIF\r
1318 \r
1319        terminator.\r
1320 \r
1321 \r