home *** CD-ROM | disk | FTP | other *** search
/ gondwana.ecr.mu.oz.au/pub/ / Graphics.tar / Graphics / graphics.formats / lzw.and.gif.doc.Z / lzw.and.gif.doc
Text File  |  1991-09-24  |  45KB  |  1,330 lines
  1.  
  2. >From: john@cooper.cooper.EDU (John Barkaus)
  3. Newsgroups: comp.graphics
  4. Subject: GIF file format responses 5/5
  5.  
  6. Date: 21 Apr 89 20:58:01 GMT
  7. Organization: The Cooper Union (NY, NY)
  8.  
  9.  
  10.  
  11.                    LZW and GIF explained----Steve Blackstock
  12.  
  13.  
  14.       I hope this little document will help enlighten those of you out there
  15. who want to know more about the Lempel-Ziv Welch compression algorithm, and,
  16. specifically, the implementation that GIF uses.
  17.      Before we start, here's a little terminology, for the purposes of this
  18. document:
  19.  
  20.       "character": a fundamental data element. In normal text files, this is
  21. just a single byte. In raster images, which is what we're interested in, it's
  22. an index that specifies the color of a given pixel. I'll refer to an arbitray
  23. character as "K".
  24.       "charstream": a stream of characters, as in a data file.
  25.       "string": a number of continuous characters, anywhere from one to very
  26. many characters in length. I can specify an arbitrary string as "[...]K".
  27.       "prefix": almost the same as a string, but with the implication that a
  28. prefix immediately precedes a character, and a prefix can have a length of
  29. zero. So, a prefix and a character make up a string. I will refer to an
  30. arbitrary prefix as "[...]".
  31.       "root": a single-character string. For most purposes, this is a
  32. character, but we may occasionally make a distinction. It is [...]K, where
  33. [...] is empty.
  34.       "code": a number, specified by a known number of bits, which maps to a
  35. string.
  36.       "codestream": the output stream of codes, as in the "raster data"
  37.       "entry": a code and its string.
  38.       "string table": a list of entries; usually, but not necessarily, unique.
  39.       That should be enough of that.
  40.  
  41.      LZW is a way of compressing data that takes advantage of repetition of
  42. strings in the data. Since raster data usually contains a lot of this
  43. repetition, LZW is a good way of compressing and decompressing it.
  44.      For the moment, lets consider normal LZW encoding and decoding. GIF's
  45. variation on the concept is just an extension from there.
  46.      LZW manipulates three objects in both compression and decompression: the
  47. charstream, the codestream, and the string table. In compression, the
  48. charstream is the input and the codestream is the output. In decompression,
  49. the codestream is the input and the charstream is the output. The string table
  50. is a product of both compression and decompression, but is never passed from
  51. one to the other.
  52.      The first thing we do in LZW compression is initialize our string table.
  53. To do this, we need to choose a code size (how many bits) and know how many
  54. values our characters can possibly take. Let's say our code size is 12 bits,
  55. meaning we can store 0->FFF, or 4096 entries in our string table. Lets also
  56. say that we have 32 possible different characters. (This corresponds to, say,
  57. a picture in which there are 32 different colors possible for each pixel.) To
  58. initialize the table, we set code#0 to character#0, code #1 to character#1,
  59. and so on, until code#31 to character#31. Actually, we are specifying that
  60. each code from 0 to 31 maps to a root. There will be no more entries in the
  61. table that have this property.
  62.      Now we start compressing data. Let's first define something called the
  63. "current prefix". It's just a prefix that we'll store things in and compare
  64. things to now and then. I will refer to it as "[.c.]". Initially, the current
  65. prefix has nothing in it. Let's also define a "current string", which will be
  66. the current prefix plus the next character in the charstream. I will refer to
  67. the current string as "[.c.]K", where K is some character. OK, look at the
  68. first character in the charstream. Call it P. Make [.c.]P the current string.
  69. (At this point, of course, it's just the root P.) Now search through the
  70. string table to see if [.c.]P appears in it. Of course, it does now, because
  71. our string table is initialized to have all roots. So we don't do anything.
  72. Now make [.c.]P the current prefix. Look at the next character in the
  73. charstream. Call it Q. Add it to the current prefix to form [.c.]Q, the
  74. current string. Now search through the string table to see if [.c.]Q appears
  75. in it. In this case, of course, it doesn't. Aha! Now we get to do something.
  76. Add [.c.]Q (which is PQ in this case) to the string table for code#32, and
  77. output the code for [.c.] to the codestream. Now start over again with the
  78. current prefix being just the root P. Keep adding characters to [.c.] to form
  79. [.c.]K, until you can't find [.c.]K in the string table. Then output the code
  80. for [.c.] and add [.c.]K to the string table. In pseudo-code, the algorithm
  81. goes something like this:
  82.  
  83.      [1] Initialize string table;
  84.      [2] [.c.] <- empty;
  85.      [3] K <- next character in charstream;
  86.      [4] Is [.c.]K in string table?
  87.       (yes: [.c.] <- [.c.]K;
  88.             go to [3];
  89.       )
  90.       (no: add [.c.]K to the string table;
  91.            output the code for [.c.] to the codestream;
  92.            [.c.] <- K;
  93.            go to [3];
  94.       )
  95.  
  96.        It's as simple as that! Of course, when you get to step [3] and there
  97. aren't any more characters left, you just output the code for [.c.] and throw
  98. the table away. You're done.
  99.       Wanna do an example? Let's pretend we have a four-character alphabet:
  100. A,B,C,D. The charstream looks like ABACABA. Let's compress it. First, we
  101. initialize our string table to: #0=A, #1=B, #2=C, #3=D. The first character is
  102. A, which is in the string table, so [.c.] becomes A. Next we get AB, which is
  103. not in the table, so we output code #0 (for [.c.]),
  104.      and add AB to the string table as code #4. [.c.] becomes B. Next we get
  105. [.c.]A = BA, which is not in the string table, so output code #1, and add BA
  106. to the string table as code #5. [.c.] becomes A. Next we get AC, which is not
  107. in the string table. Output code #0, and add AC to the string table as code
  108. #6. Now [.c.] becomes C. Next we get [.c.]A = CA, which is not in the table.
  109. Output #2 for C, and add CA to table as code#7. Now [.c.] becomes A. Next we
  110. get AB, which IS in the string table, so [.c.] gets AB, and we look at ABA,
  111. which is not in the string table, so output the code for AB, which is #4, and
  112. add ABA to the string table as code #8. [.c.] becomes A. We can't get any more
  113. characters, so we just output #0 for the code for A, and we're done. So, the
  114. codestream is #0#1#0#2#4#0.
  115.       A few words (four) should be said here about efficiency: use a hashing
  116. strategy. The search through the string table can be computationally
  117. intensive, and some hashing is well worth the effort. Also, note that
  118. "straight LZW" compression runs the risk of overflowing the string table -
  119. getting to a code which can't be represented in the number of bits you've set
  120. aside for codes. There are several ways of dealing with this problem, and GIF
  121. implements a very clever one, but we'll get to that.
  122.       An important thing to notice is that, at any point during the
  123. compression, if [...]K is in the string table, [...] is there also. This fact
  124. suggests an efficient method for storing strings in the table. Rather than
  125. store the entire string of K's in the table, realize that any string can be
  126. expressed as a prefix plus a character: [...]K. If we're about to store [...]K
  127. in the table, we know that [...] is already there, so we can just store the
  128. code for [...] plus the final character K.
  129.       Ok, that takes care of compression. Decompression is perhaps more
  130. difficult conceptually, but it is really easier to program.
  131.       Here's how it goes: We again have to start with an initialized string
  132. table. This table comes from what knowledge we have about the charstream that
  133. we will eventually get, like what possible values the characters can take. In
  134. GIF files, this information is in the header as the number of possible pixel
  135. values. The beauty of LZW, though, is that this is all we need to know. We
  136. will build the rest of the string table as we decompress the codestream. The
  137. compression is done in such a way that we will never encounter a code in the
  138. codestream that we can't translate into a string.
  139.       We need to define something called a "current code", which I will refer
  140. to as "<code>", and an "old-code", which I will refer to as "<old>". To start
  141. things off, look at the first code. This is now <code>. This code will be in
  142. the intialized string table as the code for a root. Output the root to the
  143. charstream. Make this code the old-code <old>. *Now look at the next code, and
  144. make it <code>. It is possible that this code will not be in the string table,
  145. but let's assume for now that it is. Output the string corresponding to <code>
  146. to the codestream. Now find the first character in the string you just
  147. translated. Call this K. Add this to the prefix [...] generated by <old> to
  148. form a new string [...]K. Add this string [...]K to the string table, and set
  149. the old-code <old> to the current code <code>. Repeat from where I typed the
  150. asterisk, and you're all set. Read this paragraph again if you just skimmed
  151. it!!!  Now let's consider the possibility that <code> is not in the string
  152. table. Think back to compression, and try to understand what happens when you
  153. have a string like P[...]P[...]PQ appear in the charstream. Suppose P[...] is
  154. already in the string table, but P[...]P is not. The compressor will parse out
  155. P[...], and find that P[...]P is not in the string table. It will output the
  156. code for P[...], and add P[...]P to the string table. Then it will get up to
  157. P[...]P for the next string, and find that P[...]P is in the table, as
  158.      the code just added. So it will output the code for P[...]P if it finds
  159. that P[...]PQ is not in the table. The decompressor is always "one step
  160. behind" the compressor. When the decompressor sees the code for P[...]P, it
  161. will not have added that code to it's string table yet because it needed the
  162. beginning character of P[...]P to add to the string for the last code, P[...],
  163. to form the code for P[...]P. However, when a decompressor finds a code that
  164. it doesn't know yet, it will always be the very next one to be added to the
  165. string table. So it can guess at what the string for the code should be, and,
  166. in fact, it will always be correct. If I am a decompressor, and I see
  167. code#124, and yet my string table has entries only up to code#123, I can
  168. figure out what code#124 must be, add it to my string table, and output the
  169. string. If code#123 generated the string, which I will refer to here as a
  170. prefix, [...], then code#124, in this special case, will be [...] plus the
  171. first character of [...]. So just add the first character of [...] to the end
  172. of itself. Not too bad.  As an example (and a very common one) of this special
  173. case, let's assume we have a raster image in which the first three pixels have
  174. the same color value. That is, my charstream looks like: QQQ.... For the sake
  175. of argument, let's say we have 32 colors, and Q is the color#12. The
  176. compressor will generate the code sequence 12,32,.... (if you don't know why,
  177. take a minute to understand it.) Remember that #32 is not in the initial
  178. table, which goes from #0 to #31. The decompressor will see #12 and translate
  179. it just fine as color Q. Then it will see #32 and not yet know what that
  180. means. But if it thinks about it long enough, it can figure out that QQ should
  181. be entry#32 in the table and QQ should be the next string output.  So the
  182. decompression pseudo-code goes something like:
  183.  
  184.       [1] Initialize string table;
  185.      [2] get first code: <code>;
  186.      [3] output the string for <code> to the charstream;
  187.      [4] <old> = <code>;
  188.      [5] <code> <- next code in codestream;
  189.      [6] does <code> exist in the string table?
  190.       (yes: output the string for <code> to the charstream;
  191.             [...] <- translation for <old>;
  192.             K <- first character of translation for <code>;
  193.             add [...]K to the string table;        <old> <- <code>;  )
  194.       (no: [...] <- translation for <old>;
  195.            K <- first character of [...];
  196.            output [...]K to charstream and add it to string table;
  197.            <old> <- <code>
  198.       )
  199.      [7] go to [5];
  200.  
  201.       Again, when you get to step [5] and there are no more codes, you're
  202. finished.  Outputting of strings, and finding of initial characters in strings
  203. are efficiency problems all to themselves, but I'm not going to suggest ways
  204. to do them here. Half the fun of programming is figuring these things out!
  205.       ---
  206.       Now for the GIF variations on the theme. In part of the header of a GIF
  207. file, there is a field, in the Raster Data stream, called "code size". This is
  208. a very misleading name for the field, but we have to live with it. What it is
  209. really is the "root size". The actual size, in bits, of the compression codes
  210. actually changes during compression/decompression, and I will refer to that
  211. size here as the "compression size". The initial table is just the codes for
  212. all the roots, as usual, but two special codes are added on top of those.
  213. Suppose you have a "code size", which is usually the number of bits per pixel
  214. in the image, of N. If the number of bits/pixel is one, then N must be 2: the
  215. roots take up slots #0 and #1 in the initial table, and the two special codes
  216. will take up slots #4 and #5. In any other case, N is the number of bits per
  217. pixel, and the roots take up slots #0 through #(2**N-1), and the special codes
  218. are (2**N) and (2**N + 1). The initial compression size will be N+1 bits per
  219. code. If you're encoding, you output the codes (N+1) bits at a time to start
  220. with, and if you're decoding, you grab (N+1) bits from the codestream at a
  221. time.  As for the special codes: <CC> or the clear code, is (2**N), and <EOI>,
  222. or end-of-information, is (2**N + 1). <CC> tells the compressor to re-
  223. initialize the string table, and to reset the compression size to (N+1). <EOI>
  224. means there's no more in the codestream.  If you're encoding or decoding, you
  225. should start adding things to the string table at <CC> + 2. If you're
  226. encoding, you should output <CC> as the very first code, and then whenever
  227. after that you reach code #4095 (hex FFF), because GIF does not allow
  228. compression sizes to be greater than 12 bits. If you're decoding, you should
  229. reinitialize your string table when you observe <CC>.  The variable
  230. compression sizes are really no big deal. If you're encoding, you start with a
  231. compression size of (N+1) bits, and, whenever you output the code
  232. (2**(compression size)-1), you bump the compression size up one bit. So the
  233. next code you output will be one bit longer. Remember that the largest
  234. compression size is 12 bits, corresponding to a code of 4095. If you get that
  235. far, you must output <CC> as the next code, and start over.  If you're
  236. decoding, you must increase your compression size AS SOON AS YOU write entry
  237. #(2**(compression size) - 1) to the string table. The next code you READ will
  238. be one bit longer. Don't make the mistake of waiting until you need to add the
  239. code (2**compression size) to the table. You'll have already missed a bit from
  240. the last code.  The packaging of codes into a bitsream for the raster data is
  241. also a potential stumbling block for the novice encoder or decoder. The lowest
  242. order bit in the code should coincide with the lowest available bit in the
  243. first available byte in the codestream. For example, if you're starting with
  244. 5-bit compression codes, and your first three codes are, say, <abcde>,
  245. <fghij>, <klmno>, where e, j, and o are bit#0, then your codestream will start
  246. off like:
  247.  
  248.        byte#0: hijabcde
  249.        byte#1: .klmnofg
  250.  
  251.       So the differences between straight LZW and GIF LZW are: two additional
  252. special codes and variable compression sizes. If you understand LZW, and you
  253. understand those variations, you understand it all!
  254.       Just as sort of a P.S., you may have noticed that a compressor has a
  255. little bit of flexibility at compression time. I specified a "greedy" approach
  256. to the compression, grabbing as many characters as possible before outputting
  257. codes. This is, in fact, the standard LZW way of doing things, and it will
  258. yield the best compression ratio. But there's no rule saying you can't stop
  259. anywhere along the line and just output the code for the current prefix,
  260. whether it's already in the table or not, and add that string plus the next
  261. character to the string table. There are various reasons for wanting to do
  262. this, especially if the strings get extremely long and make hashing difficult.
  263. If you need to, do it.
  264.       Hope this helps out.----steve blackstock
  265.  
  266. ---------------------------------------------------------------------------
  267. Article 5729 of comp.graphics:
  268. Path: polya!shelby!labrea!agate!ucbvax!tut.cis.ohio-state.edu!rutgers!cmcl2!phri!cooper!john
  269. >From: john@cooper.cooper.EDU (John Barkaus)
  270. Newsgroups: comp.graphics
  271. Subject: GIF file format responses 4/5
  272. Keywords: GIF LZW
  273. Message-ID: <1489@cooper.cooper.EDU>
  274. Date: 21 Apr 89 20:56:35 GMT
  275. Organization: The Cooper Union (NY, NY)
  276. Lines: 1050
  277.  
  278.  
  279. >From: cmcl2!neuron1.Jpl.Nasa.Gov!harry (Harry Langenbacher)
  280.  
  281.                 G I F (tm)
  282.  
  283.              Graphics Interchange Format (tm)
  284.  
  285.               A standard defining a mechanism
  286.  
  287.              for the storage and transmission
  288.  
  289.            of raster-based graphics information
  290.  
  291.                    June 15, 1987
  292.  
  293.              (c) CompuServe Incorporated, 1987
  294.  
  295.                 All rights reserved
  296.  
  297.         While this document is copyrighted, the information
  298.  
  299.       contained within is made available for use in computer
  300.  
  301.       software without royalties, or licensing restrictions.
  302.  
  303.       GIF and 'Graphics Interchange Format' are trademarks of
  304.  
  305.              CompuServe, Incorporated.
  306.  
  307.                an H&R Block Company
  308.  
  309.             5000 Arlington Centre Blvd.
  310.  
  311.                Columbus, Ohio 43220
  312.  
  313.                   (614) 457-8600
  314.  
  315.                                      Page 2
  316.  
  317.           Graphics Interchange Format (GIF) Specification
  318.  
  319.                  Table of Contents
  320.  
  321.     INTRODUCTION . . . . . . . . . . . . . . . . . page 3
  322.  
  323.     GENERAL FILE FORMAT  . . . . . . . . . . . . . page 3
  324.  
  325.     GIF SIGNATURE  . . . . . . . . . . . . . . . . page 4
  326.  
  327.     SCREEN DESCRIPTOR  . . . . . . . . . . . . . . page 4
  328.  
  329.     GLOBAL COLOR MAP . . . . . . . . . . . . . . . page 5
  330.  
  331.     IMAGE DESCRIPTOR . . . . . . . . . . . . . . . page 6
  332.  
  333.     LOCAL COLOR MAP  . . . . . . . . . . . . . . . page 7
  334.  
  335.     RASTER DATA  . . . . . . . . . . . . . . . . . page 7
  336.  
  337.     GIF TERMINATOR . . . . . . . . . . . . . . . . page 8
  338.  
  339.     GIF EXTENSION BLOCKS . . . . . . . . . . . . . page 8
  340.  
  341.     APPENDIX A - GLOSSARY  . . . . . . . . . . . . page 9
  342.  
  343.     APPENDIX B - INTERACTIVE SEQUENCES . . . . . . page 10
  344.  
  345.     APPENDIX C - IMAGE PACKAGING & COMPRESSION . . page 12
  346.  
  347.     APPENDIX D - MULTIPLE IMAGE PROCESSING . . . . page 15
  348.  
  349. Graphics Interchange Format (GIF)                     Page 3
  350.  
  351. Specification
  352.  
  353. INTRODUCTION
  354.  
  355.     'GIF' (tm) is CompuServe's standard for defining generalized  color
  356.  
  357.    raster   images.    This   'Graphics  Interchange  Format'  (tm)  allows
  358.  
  359.    high-quality, high-resolution graphics to be displayed on a    variety  of
  360.  
  361.    graphics  hardware  and is intended as an exchange and display mechanism
  362.  
  363.    for graphics images.  The image format described  in  this  document  is
  364.  
  365.    designed  to  support  current  and    future image technology and will in
  366.  
  367.    addition serve as a basis for future CompuServe graphics products.
  368.  
  369.     The main focus    of  this  document  is    to  provide  the  technical
  370.  
  371.    information    necessary  for    a  programmer to implement GIF encoders and
  372.  
  373.    decoders.  As such, some assumptions are made as to terminology relavent
  374.  
  375.    to graphics and programming in general.
  376.  
  377.     The first section of this document describes the  GIF  data  format
  378.  
  379.    and its components and applies to all GIF decoders, either as standalone
  380.  
  381.    programs or as part of  a  communications  package.     Appendix  B  is  a
  382.  
  383.    section  relavent to decoders that are part of a communications software
  384.  
  385.    package and describes the protocol requirements for entering and exiting
  386.  
  387.    GIF mode, and responding to host interrogations.  A glossary in Appendix
  388.  
  389.    A defines some of the terminology used in  this  document.    Appendix  C
  390.  
  391.    gives  a  detailed  explanation  of    how  the  graphics  image itself is
  392.  
  393.    packaged as a series of data bytes.
  394.  
  395.         Graphics Interchange Format Data Definition
  396.  
  397.  GENERAL FILE FORMAT
  398.  
  399.     +-----------------------+
  400.  
  401.     | +-------------------+ |
  402.  
  403.     | |   GIF Signature   | |
  404.  
  405.     | +-------------------+ |
  406.  
  407.     | +-------------------+ |
  408.  
  409.     | | Screen Descriptor | |
  410.  
  411.     | +-------------------+ |
  412.  
  413.     | +-------------------+ |
  414.  
  415.     | | Global Color Map  | |
  416.  
  417.     | +-------------------+ |
  418.  
  419.     . . .            . . .
  420.  
  421.     | +-------------------+ |    ---+
  422.  
  423.     | |  Image Descriptor | |    |
  424.  
  425.     | +-------------------+ |    |
  426.  
  427.     | +-------------------+ |    |
  428.  
  429.     | |  Local Color Map  | |    |-   Repeated 1 to n times
  430.  
  431.     | +-------------------+ |    |
  432.  
  433.     | +-------------------+ |    |
  434.  
  435.     | |    Raster Data    | |    |
  436.  
  437.     | +-------------------+ |    ---+
  438.  
  439.     . . .            . . .
  440.  
  441.     |-    GIF Terminator   -|
  442.  
  443.     +-----------------------+
  444.  
  445. Graphics Interchange Format (GIF)                     Page 4
  446.  
  447. Specification
  448.  
  449.  GIF SIGNATURE
  450.  
  451.     The following GIF Signature identifies    the  data  following  as  a
  452.  
  453.    valid GIF image stream.  It consists of the following six characters:
  454.  
  455.          G I F 8 7 a
  456.  
  457.     The last three characters '87a' may be viewed as a  version  number
  458.  
  459.    for    this  particular  GIF  definition  and will be used in general as a
  460.  
  461.    reference  in  documents  regarding    GIF  that   address   any   version
  462.  
  463.    dependencies.
  464.  
  465.  SCREEN DESCRIPTOR
  466.  
  467.     The Screen Descriptor describes the overall parameters for all    GIF
  468.  
  469.    images  following.  It defines the overall dimensions of the image space
  470.  
  471.    or logical screen required, the existance of color mapping  information,
  472.  
  473.    background  screen color, and color depth information.  This information
  474.  
  475.    is stored in a series of 8-bit bytes as described below.
  476.  
  477.           bits
  478.  
  479.      7 6 5 4 3 2 1 0  Byte #
  480.  
  481.     +---------------+
  482.  
  483.     |        |  1
  484.  
  485.     +-Screen Width -+      Raster width in pixels (LSB first)
  486.  
  487.     |        |  2
  488.  
  489.     +---------------+
  490.  
  491.     |        |  3
  492.  
  493.     +-Screen Height-+      Raster height in pixels (LSB first)
  494.  
  495.     |        |  4
  496.  
  497.     +-+-----+-+-----+      M = 1, Global color map follows Descriptor
  498.  
  499.     |M|  cr |0|pixel|  5   cr+1 = # bits of color resolution
  500.  
  501.     +-+-----+-+-----+      pixel+1 = # bits/pixel in image
  502.  
  503.     |   background    |  6   background=Color index of screen background
  504.  
  505.     +---------------+       (color is defined from the Global color
  506.  
  507.     |0 0 0 0 0 0 0 0|  7        map or default map if none specified)
  508.  
  509.     +---------------+
  510.  
  511.     The logical screen width and height can both  be  larger  than    the
  512.  
  513.    physical  display.    How  images  larger  than  the physical display are
  514.  
  515.    handled is implementation dependent and can take advantage  of  hardware
  516.  
  517.    characteristics  (e.g.   Macintosh scrolling windows).  Otherwise images
  518.  
  519.    can be clipped to the edges of the display.
  520.  
  521.     The value of 'pixel' also defines  the    maximum  number  of  colors
  522.  
  523.    within  an  image.    The  range  of    values    for 'pixel' is 0 to 7 which
  524.  
  525.    represents 1 to 8 bits.  This translates to a range of 2 (B & W) to    256
  526.  
  527.    colors.   Bit  3 of word 5 is reserved for future definition and must be
  528.  
  529.    zero.
  530.  
  531. Graphics Interchange Format (GIF)                     Page 5
  532.  
  533. Specification
  534.  
  535.  GLOBAL COLOR MAP
  536.  
  537.     The Global Color Map is optional but recommended for  images  where
  538.  
  539.    accurate color rendition is desired.  The existence of this color map is
  540.  
  541.    indicated in the 'M' field of byte 5 of the Screen Descriptor.  A  color
  542.  
  543.    map    can  also  be associated with each image in a GIF file as described
  544.  
  545.    later.  However this  global  map  will  normally  be  used    because  of
  546.  
  547.    hardware  restrictions  in equipment available today.  In the individual
  548.  
  549.    Image Descriptors the 'M' flag will normally be  zero.   If    the  Global
  550.  
  551.    Color  Map  is  present,  it's definition immediately follows the Screen
  552.  
  553.    Descriptor.     The  number  of  color  map  entries  following  a  Screen
  554.  
  555.    Descriptor  is equal to 2**(# bits per pixel), where each entry consists
  556.  
  557.    of three byte values representing the relative intensities of red, green
  558.  
  559.    and blue respectively.  The structure of the Color Map block is:
  560.  
  561.           bits
  562.  
  563.      7 6 5 4 3 2 1 0  Byte #
  564.  
  565.     +---------------+
  566.  
  567.     | red intensity |  1    Red value for color index 0
  568.  
  569.     +---------------+
  570.  
  571.     |green intensity|  2    Green value for color index 0
  572.  
  573.     +---------------+
  574.  
  575.     | blue intensity|  3    Blue value for color index 0
  576.  
  577.     +---------------+
  578.  
  579.     | red intensity |  4    Red value for color index 1
  580.  
  581.     +---------------+
  582.  
  583.     |green intensity|  5    Green value for color index 1
  584.  
  585.     +---------------+
  586.  
  587.     | blue intensity|  6    Blue value for color index 1
  588.  
  589.     +---------------+
  590.  
  591.     :        :    (Continues for remaining colors)
  592.  
  593.     Each image pixel value received will be displayed according to    its
  594.  
  595.    closest match with an available color of the display based on this color
  596.  
  597.    map.  The color components represent a fractional intensity    value  from
  598.  
  599.    none  (0)  to  full (255).  White would be represented as (255,255,255),
  600.  
  601.    black as (0,0,0) and medium yellow as (180,180,0).  For display, if    the
  602.  
  603.    device  supports fewer than 8 bits per color component, the higher order
  604.  
  605.    bits of each component are used.  In the creation of  a  GIF  color    map
  606.  
  607.    entry  with    hardware  supporting  fewer  than 8 bits per component, the
  608.  
  609.    component values for the hardware  should  be  converted  to  the  8-bit
  610.  
  611.    format with the following calculation:
  612.  
  613.     <map_value> = <component_value>*255/(2**<nbits> -1)
  614.  
  615.     This assures accurate translation of colors for all  displays.     In
  616.  
  617.    the    cases  of  creating  GIF images from hardware without color palette
  618.  
  619.    capability, a fixed palette should be created  based  on  the  available
  620.  
  621.    display  colors for that hardware.  If no Global Color Map is indicated,
  622.  
  623.    a default color map is generated internally    which  maps  each  possible
  624.  
  625.    incoming  color  index to the same hardware color index modulo <n> where
  626.  
  627.    <n> is the number of available hardware colors.
  628.  
  629. Graphics Interchange Format (GIF)                     Page 6
  630.  
  631. Specification
  632.  
  633.  IMAGE DESCRIPTOR
  634.  
  635.     The Image Descriptor defines the actual placement  and    extents  of
  636.  
  637.    the    following  image within the space defined in the Screen Descriptor.
  638.  
  639.    Also defined are flags to indicate the presence of a local color  lookup
  640.  
  641.    map, and to define the pixel display sequence.  Each Image Descriptor is
  642.  
  643.    introduced by an image separator  character.   The  role  of  the  Image
  644.  
  645.    Separator  is simply to provide a synchronization character to introduce
  646.  
  647.    an Image Descriptor.  This is desirable if a GIF file happens to contain
  648.  
  649.    more  than  one  image.   This  character  is defined as 0x2C hex or ','
  650.  
  651.    (comma).  When this character is encountered between images,  the  Image
  652.  
  653.    Descriptor will follow immediately.
  654.  
  655.     Any characters encountered between the end of a previous image    and
  656.  
  657.    the image separator character are to be ignored.  This allows future GIF
  658.  
  659.    enhancements to be present in newer image formats and yet ignored safely
  660.  
  661.    by older software decoders.
  662.  
  663.           bits
  664.  
  665.      7 6 5 4 3 2 1 0  Byte #
  666.  
  667.     +---------------+
  668.  
  669.     |0 0 1 0 1 1 0 0|  1    ',' - Image separator character
  670.  
  671.     +---------------+
  672.  
  673.     |        |  2    Start of image in pixels from the
  674.  
  675.     +-  Image Left -+    left side of the screen (LSB first)
  676.  
  677.     |        |  3
  678.  
  679.     +---------------+
  680.  
  681.     |        |  4
  682.  
  683.     +-  Image Top  -+    Start of image in pixels from the
  684.  
  685.     |        |  5    top of the screen (LSB first)
  686.  
  687.     +---------------+
  688.  
  689.     |        |  6
  690.  
  691.     +- Image Width -+    Width of the image in pixels (LSB first)
  692.  
  693.     |        |  7
  694.  
  695.     +---------------+
  696.  
  697.     |        |  8
  698.  
  699.     +- Image Height-+    Height of the image in pixels (LSB first)
  700.  
  701.     |        |  9
  702.  
  703.     +-+-+-+-+-+-----+    M=0 - Use global color map, ignore 'pixel'
  704.  
  705.     |M|I|0|0|0|pixel| 10    M=1 - Local color map follows, use 'pixel'
  706.  
  707.     +-+-+-+-+-+-----+    I=0 - Image formatted in Sequential order
  708.  
  709.                 I=1 - Image formatted in Interlaced order
  710.  
  711.                 pixel+1 - # bits per pixel for this image
  712.  
  713.     The specifications for the image position and size must be confined
  714.  
  715.    to  the  dimensions defined by the Screen Descriptor.  On the other hand
  716.  
  717.    it is not necessary that the image fill the entire screen defined.
  718.  
  719.  LOCAL COLOR MAP
  720.  
  721. Graphics Interchange Format (GIF)                     Page 7
  722.  
  723. Specification
  724.  
  725.     A Local Color Map is optional and defined here for future use.     If
  726.  
  727.    the    'M' bit of byte 10 of the Image Descriptor is set, then a color map
  728.  
  729.    follows the Image Descriptor that applies only to the  following  image.
  730.  
  731.    At the end of the image, the color map will revert to that defined after
  732.  
  733.    the Screen Descriptor.  Note that the 'pixel' field of byte    10  of    the
  734.  
  735.    Image  Descriptor  is used only if a Local Color Map is indicated.  This
  736.  
  737.    defines the parameters not only for the image pixel size, but determines
  738.  
  739.    the    number    of color map entries that follow.  The bits per pixel value
  740.  
  741.    will also revert to the value specified in the  Screen  Descriptor  when
  742.  
  743.    processing of the image is complete.
  744.  
  745.  RASTER DATA
  746.  
  747.     The format of the actual image is defined as the  series  of  pixel
  748.  
  749.    color  index  values that make up the image.  The pixels are stored left
  750.  
  751.    to right sequentially for an image row.  By default each  image  row  is
  752.  
  753.    written  sequentially, top to bottom.  In the case that the Interlace or
  754.  
  755.    'I' bit is set in byte 10 of the Image Descriptor then the row order  of
  756.  
  757.    the    image  display    follows  a  four-pass process in which the image is
  758.  
  759.    filled in by widely spaced rows.  The first pass writes every  8th  row,
  760.  
  761.    starting  with  the top row of the image window.  The second pass writes
  762.  
  763.    every 8th row starting at the fifth row from the top.   The    third  pass
  764.  
  765.    writes every 4th row starting at the third row from the top.  The fourth
  766.  
  767.    pass completes the image, writing  every  other  row,  starting  at    the
  768.  
  769.    second row from the top.  A graphic description of this process follows:
  770.  
  771.    Image
  772.  
  773.    Row    Pass 1    Pass 2    Pass 3    Pass 4        Result
  774.  
  775.    ---------------------------------------------------
  776.  
  777.      0    **1a**                    **1a**
  778.  
  779.      1                **4a**        **4a**
  780.  
  781.      2            **3a**            **3a**
  782.  
  783.      3                **4b**        **4b**
  784.  
  785.      4        **2a**                **2a**
  786.  
  787.      5                **4c**        **4c**
  788.  
  789.      6            **3b**            **3b**
  790.  
  791.      7                **4d**        **4d**
  792.  
  793.      8    **1b**                    **1b**
  794.  
  795.      9                **4e**        **4e**
  796.  
  797.     10            **3c**            **3c**
  798.  
  799.     11                **4f**        **4f**
  800.  
  801.     12        **2b**                **2b**
  802.  
  803.    . . .
  804.  
  805.     The image pixel values are processed as a series of  color  indices
  806.  
  807.    which  map  into the existing color map.  The resulting color value from
  808.  
  809.    the map is what is actually displayed.  This series    of  pixel  indices,
  810.  
  811.    the    number    of  which  is equal to image-width*image-height pixels, are
  812.  
  813.    passed to the GIF image data stream one value per pixel, compressed    and
  814.  
  815.    packaged  according    to  a  version    of the LZW compression algorithm as
  816.  
  817.    defined in Appendix C.
  818.  
  819. Graphics Interchange Format (GIF)                     Page 8
  820.  
  821. Specification
  822.  
  823.  GIF TERMINATOR
  824.  
  825.     In order to provide a synchronization for the termination of a    GIF
  826.  
  827.    image  file,  a  GIF  decoder  will process the end of GIF mode when the
  828.  
  829.    character 0x3B hex or ';' is found after an image  has  been  processed.
  830.  
  831.    By  convention  the    decoding software will pause and wait for an action
  832.  
  833.    indicating that the user is ready to continue.  This may be    a  carriage
  834.  
  835.    return  entered  at    the  keyboard  or  a  mouse click.  For interactive
  836.  
  837.    applications this user action must  be  passed  on  to  the    host  as  a
  838.  
  839.    carriage  return  character    so  that the host application can continue.
  840.  
  841.    The decoding software will then typically leave graphics mode and resume
  842.  
  843.    any previous process.
  844.  
  845.  GIF EXTENSION BLOCKS
  846.  
  847.     To provide for orderly extension of the GIF definition, a mechanism
  848.  
  849.    for    defining  the  packaging  of extensions within a GIF data stream is
  850.  
  851.    necessary.  Specific GIF extensions are to be defined and documented  by
  852.  
  853.    CompuServe in order to provide a controlled enhancement path.
  854.  
  855.     GIF Extension Blocks are packaged in a manner similar to that  used
  856.  
  857.    by the raster data though not compressed.  The basic structure is:
  858.  
  859.      7 6 5 4 3 2 1 0  Byte #
  860.  
  861.     +---------------+
  862.  
  863.     |0 0 1 0 0 0 0 1|  1       '!' - GIF Extension Block Introducer
  864.  
  865.     +---------------+
  866.  
  867.     | function code |  2       Extension function code (0 to 255)
  868.  
  869.     +---------------+    ---+
  870.  
  871.     |  byte count    |    |
  872.  
  873.     +---------------+    |
  874.  
  875.     :        :    +-- Repeated as many times as necessary
  876.  
  877.     |func data bytes|    |
  878.  
  879.     :        :    |
  880.  
  881.     +---------------+    ---+
  882.  
  883.     . . .        . . .
  884.  
  885.     +---------------+
  886.  
  887.     |0 0 0 0 0 0 0 0|    zero byte count (terminates block)
  888.  
  889.     +---------------+
  890.  
  891.     A GIF Extension Block may immediately preceed any Image  Descriptor
  892.  
  893.    or occur before the GIF Terminator.
  894.  
  895.     All GIF decoders must be able to recognize  the  existence  of    GIF
  896.  
  897.    Extension  Blocks  and  read past them if unable to process the function
  898.  
  899.    code.  This ensures that older decoders will be able to process extended
  900.  
  901.    GIF     image     files     in  the  future,  though  without  the  additional
  902.  
  903.    functionality.
  904.  
  905. Graphics Interchange Format (GIF)                     Page 9
  906.  
  907. Appendix A - Glossary
  908.  
  909.                  GLOSSARY
  910.  
  911. Pixel - The smallest picture element of a  graphics  image.   This  usually
  912.  
  913.    corresponds    to  a single dot on a graphics screen.    Image resolution is
  914.  
  915.    typically given in units of    pixels.   For  example    a  fairly  standard
  916.  
  917.    graphics  screen  format  is  one 320 pixels across and 200 pixels high.
  918.  
  919.    Each pixel can  appear  as  one  of    several  colors  depending  on    the
  920.  
  921.    capabilities of the graphics hardware.
  922.  
  923. Raster - A horizontal row of pixels representing one line of an  image.   A
  924.  
  925.    typical method of working with images since most hardware is oriented to
  926.  
  927.    work most efficiently in this manner.
  928.  
  929. LSB - Least Significant Byte.  Refers to a convention for two byte  numeric
  930.  
  931.    values in which the less significant byte of the value preceeds the more
  932.  
  933.    significant byte.  This convention is typical on many microcomputers.
  934.  
  935. Color Map - The list of definitions of each color  used  in  a    GIF  image.
  936.  
  937.    These  desired  colors are converted to available colors through a table
  938.  
  939.    which is derived by assigning an incoming color index (from    the  image)
  940.  
  941.    to  an  output  color  index  (of  the  hardware).    While the color map
  942.  
  943.    definitons are specified in a GIF image, the output    pixel  colors  will
  944.  
  945.    vary  based    on  the  hardware used and its ability to match the defined
  946.  
  947.    color.
  948.  
  949. Interlace - The method of displaying a GIF image in which  multiple  passes
  950.  
  951.    are    made,  outputting  raster  lines  spaced  apart to provide a way of
  952.  
  953.    visualizing the general content of an entire image  before  all  of    the
  954.  
  955.    data has been processed.
  956.  
  957. B Protocol - A CompuServe-developed error-correcting file transfer protocol
  958.  
  959.    available  in  the  public  domain  and implemented in CompuServe VIDTEX
  960.  
  961.    products.  This error checking mechanism will be used  in  transfers  of
  962.  
  963.    GIF images for interactive applications.
  964.  
  965. LZW - A sophisticated data compression algorithm  based  on  work  done  by
  966.  
  967.    Lempel-Ziv  &  Welch  which    has  the feature of very efficient one-pass
  968.  
  969.    encoding and decoding.  This allows the image  to  be  decompressed    and
  970.  
  971.    displayed  at  the  same  time.   The  original  article from which this
  972.  
  973.    technique was adapted is:
  974.  
  975.       Terry  A.   Welch,  "A  Technique  for  High     Performance   Data
  976.  
  977.       Compression", IEEE Computer, vol 17 no 6 (June 1984)
  978.  
  979.     This basic algorithm is also used in the  public  domain  ARC  file
  980.  
  981.    compression    utilities.   The  CompuServe  adaptation  of LZW for GIF is
  982.  
  983.    described in Appendix C.
  984.  
  985. Graphics Interchange Format (GIF)                    Page 10
  986.  
  987. Appendix B - Interactive Sequences
  988.  
  989.        GIF Sequence Exchanges for an Interactive Environment
  990.  
  991.     The following sequences are defined for use  in  mediating  control
  992.  
  993.    between a GIF sender and GIF receiver over an interactive communications
  994.  
  995.    line.  These  sequences  do    not  apply  to    applications  that  involve
  996.  
  997.    downloading    of  static  GIF  files and are not considered part of a GIF
  998.  
  999.    file.
  1000.  
  1001.  GIF CAPABILITIES ENQUIRY
  1002.  
  1003.     The GCE sequence is issued from a host and requests an    interactive
  1004.  
  1005.    GIF    decoder  to  return  a    response  message that defines the graphics
  1006.  
  1007.    parameters for the decoder.    This involves returning  information  about
  1008.  
  1009.    available screen sizes, number of bits/color supported and the amount of
  1010.  
  1011.    color detail supported.  The escape sequence for the GCE is defined as:
  1012.  
  1013.     ESC [ > 0 g    (g is lower case, spaces inserted for clarity)
  1014.  
  1015.              (0x1B 0x5B 0x3E 0x30 0x67)
  1016.  
  1017.  GIF CAPABILITIES RESPONSE
  1018.  
  1019.     The GIF Capabilities Response message is returned by an interactive
  1020.  
  1021.    GIF    decoder  and  defines  the  decoder's  display capabilities for all
  1022.  
  1023.    graphics modes that are supported by the software.  Note that  this    can
  1024.  
  1025.    also include graphics printers as well as a monitor screen.    The general
  1026.  
  1027.    format of this message is:
  1028.  
  1029.      #version;protocol{;dev, width, height, color-bits, color-res}... <CR>
  1030.  
  1031.    '#'        - GCR identifier character (Number Sign)
  1032.  
  1033.    version    - GIF format version number;  initially '87a'
  1034.  
  1035.    protocol='0' - No end-to-end protocol supported by decoder
  1036.  
  1037.           Transfer as direct 8-bit data stream.
  1038.  
  1039.    protocol='1' - Can use an error correction protocol to transfer GIF data
  1040.  
  1041.            interactively from the host directly to the display.
  1042.  
  1043.    dev = '0'    - Screen parameter set follows
  1044.  
  1045.    dev = '1'    - Printer parameter set follows
  1046.  
  1047.    width    - Maximum supported display width in pixels
  1048.  
  1049.    height    - Maximum supported display height in pixels
  1050.  
  1051.    color-bits    - Number of  bits  per    pixel  supported.   The  number  of
  1052.  
  1053.            supported colors is therefore 2**color-bits.
  1054.  
  1055.    color-res    - Number of bits  per  color  component  supported  in    the
  1056.  
  1057.            hardware  color    palette.   If  color-res  is  '0'  then  no
  1058.  
  1059.            hardware palette table is available.
  1060.  
  1061.     Note that all values in the  GCR  are  returned  as  ASCII  decimal
  1062.  
  1063.    numbers and the message is terminated by a Carriage Return character.
  1064.  
  1065. Graphics Interchange Format (GIF)                    Page 11
  1066.  
  1067. Appendix B - Interactive Sequences
  1068.  
  1069.     The  following     GCR   message     describes   three   standard    EGA
  1070.  
  1071.    configurations  with  no  printer;  the GIF data stream can be processed
  1072.  
  1073.    within an error correcting protocol:
  1074.  
  1075.     #87a;1 ;0,320,200,4,0 ;0,640,200,2,2 ;0,640,350,4,2<CR>
  1076.  
  1077.  ENTER GIF GRAPHICS MODE
  1078.  
  1079.     Two sequences are currently defined to invoke  an  interactive    GIF
  1080.  
  1081.    decoder into action.  The only difference between them is that different
  1082.  
  1083.    output media are selected.  These sequences are:
  1084.  
  1085.      ESC [ > 1 g   Display GIF image on screen
  1086.  
  1087.            (0x1B 0x5B 0x3E 0x31 0x67)
  1088.  
  1089.      ESC [ > 2 g   Display image directly to an attached graphics  printer.
  1090.  
  1091.            The    image  may optionally be displayed on the screen as
  1092.  
  1093.            well.
  1094.  
  1095.            (0x1B 0x5B 0x3E 0x32 0x67)
  1096.  
  1097.     Note that the 'g' character terminating each sequence is  in  lower
  1098.  
  1099.    case.
  1100.  
  1101.  INTERACTIVE ENVIRONMENT
  1102.  
  1103.     The assumed environment for the transmission of GIF image data from
  1104.  
  1105.    an  interactive  application  is  a    full 8-bit data stream from host to
  1106.  
  1107.    micro.  All 256 character codes must be transferrable.  The establishing
  1108.  
  1109.    of  an 8-bit data path for communications will normally be taken care of
  1110.  
  1111.    by the host application programs.  It is however  up  to  the  receiving
  1112.  
  1113.    communications programs supporting GIF to be able to receive and pass on
  1114.  
  1115.    all 256 8-bit codes to the GIF decoder software.
  1116.  
  1117. Graphics Interchange Format (GIF)                    Page 12
  1118.  
  1119. Appendix C - Image Packaging & Compression
  1120.  
  1121.     The Raster Data stream that represents the actual output image    can
  1122.  
  1123.    be represented as:
  1124.  
  1125.      7 6 5 4 3 2 1 0
  1126.  
  1127.     +---------------+
  1128.  
  1129.     |   code size    |
  1130.  
  1131.     +---------------+     ---+
  1132.  
  1133.     |blok byte count|     |
  1134.  
  1135.     +---------------+     |
  1136.  
  1137.     :        :     +-- Repeated as many times as necessary
  1138.  
  1139.     |  data bytes    |     |
  1140.  
  1141.     :        :     |
  1142.  
  1143.     +---------------+     ---+
  1144.  
  1145.     . . .        . . .
  1146.  
  1147.     +---------------+
  1148.  
  1149.     |0 0 0 0 0 0 0 0|    zero byte count (terminates data stream)
  1150.  
  1151.     +---------------+
  1152.  
  1153.     The conversion of the image from a series  of  pixel  values  to  a
  1154.  
  1155.    transmitted or stored character stream involves several steps.  In brief
  1156.  
  1157.    these steps are:
  1158.  
  1159.    1.  Establish the Code Size -  Define  the  number  of  bits  needed  to
  1160.  
  1161.        represent the actual data.
  1162.  
  1163.    2.  Compress the Data - Compress the series of image pixels to a  series
  1164.  
  1165.        of compression codes.
  1166.  
  1167.    3.  Build a Series of Bytes - Take the  set    of  compression  codes    and
  1168.  
  1169.        convert to a string of 8-bit bytes.
  1170.  
  1171.    4.  Package the Bytes - Package sets of bytes into blocks  preceeded  by
  1172.  
  1173.        character counts and output.
  1174.  
  1175. ESTABLISH CODE SIZE
  1176.  
  1177.     The first byte of the GIF Raster Data stream is a value  indicating
  1178.  
  1179.    the minimum number of bits required to represent the set of actual pixel
  1180.  
  1181.    values.  Normally this will be the same as the  number  of  color  bits.
  1182.  
  1183.    Because  of    some  algorithmic constraints however, black & white images
  1184.  
  1185.    which have one color bit must be indicated as having a code size  of  2.
  1186.  
  1187.    This  code size value also implies that the compression codes must start
  1188.  
  1189.    out one bit longer.
  1190.  
  1191. COMPRESSION
  1192.  
  1193.     The LZW algorithm converts a series of data values into a series of
  1194.  
  1195.    codes  which may be raw values or a code designating a series of values.
  1196.  
  1197.    Using text characters as an analogy,  the  output  code  consists  of  a
  1198.  
  1199.    character or a code representing a string of characters.
  1200.  
  1201. Graphics Interchange Format (GIF)                    Page 13
  1202.  
  1203. Appendix C - Image Packaging & Compression
  1204.  
  1205.     The LZW algorithm used in  GIF    matches  algorithmically  with    the
  1206.  
  1207.    standard LZW algorithm with the following differences:
  1208.  
  1209.    1.  A   special   Clear   code   is      defined    which    resets    all
  1210.  
  1211.        compression/decompression parameters and tables to a start-up state.
  1212.  
  1213.        The value of this code is 2**<code size>.  For example if  the  code
  1214.  
  1215.        size  indicated    was 4 (image was 4 bits/pixel) the Clear code value
  1216.  
  1217.        would be 16 (10000 binary).  The Clear code can appear at any  point
  1218.  
  1219.        in the image data stream and therefore requires the LZW algorithm to
  1220.  
  1221.        process succeeding codes as if  a  new  data  stream  was  starting.
  1222.  
  1223.        Encoders  should output a Clear code as the first code of each image
  1224.  
  1225.        data stream.
  1226.  
  1227.    2.  An End of Information code is defined that explicitly indicates    the
  1228.  
  1229.        end  of    the image data stream.    LZW processing terminates when this
  1230.  
  1231.        code is encountered.  It must be the last code output by the encoder
  1232.  
  1233.        for an image.  The value of this code is <Clear code>+1.
  1234.  
  1235.    3.  The first available compression code value is <Clear code>+2.
  1236.  
  1237.    4.  The output codes are of variable length, starting  at  <code size>+1
  1238.  
  1239.        bits  per code, up to 12 bits per code.    This defines a maximum code
  1240.  
  1241.        value of 4095 (hex FFF).  Whenever the LZW code value  would  exceed
  1242.  
  1243.        the  current  code length, the code length is increased by one.    The
  1244.  
  1245.        packing/unpacking of these codes must then be altered to reflect the
  1246.  
  1247.        new code length.
  1248.  
  1249. BUILD 8-BIT BYTES
  1250.  
  1251.     Because the LZW compression  used  for    GIF  creates  a  series  of
  1252.  
  1253.    variable  length  codes, of between 3 and 12 bits each, these codes must
  1254.  
  1255.    be reformed into a series of 8-bit bytes that  will    be  the  characters
  1256.  
  1257.    actually stored or transmitted.  This provides additional compression of
  1258.  
  1259.    the image.  The codes are formed into a stream of bits as if  they  were
  1260.  
  1261.    packed  right to left and then picked off 8 bits at a time to be output.
  1262.  
  1263.    Assuming a character array of 8 bits per character and using 5 bit codes
  1264.  
  1265.    to be packed, an example layout would be similar to:
  1266.  
  1267.      byte n       byte 5   byte 4    byte 3     byte 2   byte 1
  1268.  
  1269.     +-.....-----+--------+--------+--------+--------+--------+
  1270.  
  1271.     | and so on |hhhhhggg|ggfffffe|eeeedddd|dcccccbb|bbbaaaaa|
  1272.  
  1273.     +-.....-----+--------+--------+--------+--------+--------+
  1274.  
  1275.     Note that the physical    packing  arrangement  will  change  as    the
  1276.  
  1277.    number  of  bits per compression code change but the concept remains the
  1278.  
  1279.    same.
  1280.  
  1281. PACKAGE THE BYTES
  1282.  
  1283.     Once the bytes have been created, they are grouped into blocks    for
  1284.  
  1285.    output by preceeding each block of 0 to 255 bytes with a character count
  1286.  
  1287.    byte.  A block with a zero byte count terminates the Raster Data  stream
  1288.  
  1289.    for    a  given  image.  These blocks are what are actually output for the
  1290.  
  1291. Graphics Interchange Format (GIF)                    Page 14
  1292.  
  1293. Appendix C - Image Packaging & Compression
  1294.  
  1295.    GIF image.  This block format has the side effect of allowing a decoding
  1296.  
  1297.    program  the  ability to read past the actual image data if necessary by
  1298.  
  1299.    reading block counts and then skipping over the data.
  1300.  
  1301. Graphics Interchange Format (GIF)                    Page 15
  1302.  
  1303. Appendix D - Multiple Image Processing
  1304.  
  1305.     Since a  GIF  data  stream  can  contain  multiple  images,  it  is
  1306.  
  1307.    necessary  to  describe  processing and display of such a file.  Because
  1308.  
  1309.    the image descriptor allows    for  placement    of  the  image    within    the
  1310.  
  1311.    logical  screen,  it is possible to define a sequence of images that may
  1312.  
  1313.    each be a partial screen, but in total  fill  the  entire  screen.    The
  1314.  
  1315.    guidelines for handling the multiple image situation are:
  1316.  
  1317.    1.  There is no pause between images.  Each is processed immediately  as
  1318.  
  1319.        seen by the decoder.
  1320.  
  1321.    2.  Each image explicitly overwrites any image  already  on    the  screen
  1322.  
  1323.        inside  of  its window.    The only screen clears are at the beginning
  1324.  
  1325.        and end of the  GIF  image  process.   See  discussion  on  the    GIF
  1326.  
  1327.        terminator.
  1328.  
  1329.  
  1330.