Click above to get retro games delivered to your door ever month!

 Image Packaging & Compression

 The Raster Data stream that represents the actual output image  can be
 represented as:

         7 6 5 4 3 2 1 0
        +---------------+
        |   code size   |
        |---------------|     ---+
        |blok byte count|        |
        |---------------|        |
        |               |        |-- Repeated as many times as necessary
        |  data bytes   |        |
        |               |        |
        |---------------|     ---+
        | . .       . . |
        |---------------|
        |0 0 0 0 0 0 0 0|       zero byte count (terminates data stream)
        +---------------+

 The conversion of the image from a series  of  pixel  values  to  a
 transmitted or stored character stream involves several steps.  In brief
 these steps are:

   1.  Establish the Code Size -  Define  the  number  of  bits  needed  to
       represent the actual data.

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

   3.  Build a Series of Bytes - Take the  set  of  compression  codes  and
       convert to a string of 8-bit bytes.

   4.  Package the Bytes - Package sets of bytes into blocks  preceeded  by
       character counts and output.



 ESTABLISH CODE SIZE
   The first byte of the GIF Raster Data stream is a value  indicating the
   minimum number of bits required to represent the set of actual pixel
   values.  Normally this will be the same as the  number  of  colour  bits.
   Because  of  some  algorithmic constraints however, black & white images
   which have one colour bit must be indicated as having a code size  of  2.
   This  code size value also implies that the compression codes must start
   out one bit longer.


 COMPRESSION
   The LZW algorithm converts a series of data values into a series of
   codes  which may be raw values or a code designating a series of values.
   Using text characters as an analogy,  the  output  code  consists  of  a
   character or a code representing a string of characters.

   The LZW algorithm used in  GIF  matches  algorithmically  with  the
   standard LZW algorithm with the following differences:

   1.  A   special   Clear   code   is    defined    which    resets    all
       compression/decompression parameters and tables to a start-up state.
       The value of this code is 2**<code size>.  For example if  the  code
       size  indicated  was 4 (image was 4 bits/pixel) the Clear code value
       would be 16 (10000 binary).  The Clear code can appear at any  point
       in the image data stream and therefore requires the LZW algorithm to
       process succeeding codes as if  a  new  data  stream  was  starting.
       Encoders  should output a Clear code as the first code of each image
       data stream.

   2.  An End of Information code is defined that explicitly indicates  the
       end  of  the image data stream.  LZW processing terminates when this
       code is encountered.  It must be the last code output by the encoder
       for an image.  The value of this code is <Clear code>+1.

   3.  The first available compression code value is <Clear code>+2.

   4.  The output codes are of variable length, starting  at  <code size>+1
       bits  per code, up to 12 bits per code.  This defines a maximum code
       value of 4095 (hex FFF).  Whenever the LZW code value  would  exceed
       the  current  code length, the code length is increased by one.  The
       packing/unpacking of these codes must then be altered to reflect the
       new code length.


 BUILD 8-BIT BYTES
   Because the LZW compression  used  for  GIF  creates  a  series  of
   variable  length  codes, of between 3 and 12 bits each, these codes must
   be reformed into a series of 8-bit bytes that  will  be  the  characters
   actually stored or transmitted.  This provides additional compression of
   the image.  The codes are formed into a stream of bits as if  they  were
   packed  right to left and then picked off 8 bits at a time to be output.
   Assuming a character array of 8 bits per character and using 5 bit codes
   to be packed, an example layout would be similar to:

         byte n       byte 5   byte 4   byte 3   byte 2   byte 1
        +--------------------------------------------------------+
        | and so on |hhhhhggg|ggfffffe|eeeedddd|dcccccbb|bbbaaaaa|
        +--------------------------------------------------------+

   Note that the physical  packing  arrangement  will  change  as  the
   number  of  bits per compression code change but the concept remains the
   same.

 PACKAGE THE BYTES
   Once the bytes have been created, they are grouped into blocks  for
   output by preceeding each block of 0 to 255 bytes with a character count
   byte.  A block with a zero byte count terminates the Raster Data  stream
   for  a  given  image.  These blocks are what are actually output for the

   GIF image.  This block format has the side effect of allowing a decoding
   program  the  ability to read past the actual image data if necessary by
   reading block counts and then skipping over the data.