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

 Endcoding LZW GIF

 Consider the following input data stream in a 4 color (A, B, C, D)
 system. We will build a table of codes which represent strings of colors.
 Each time we  find a new string, we will give it the next code, and break
 it  into  a prefix string and a suffix color. The symbols \ or ---
 represent the prefix string, and / represents the suffix color. The first
 4 entries in the table are  the  4 colors with codes 0 thru 3, each of
 which represents  a  single color.  The next 2 codes (4 and 5) are the
 clear code and the end of  image code.  The first available code to
 represent a string of colors is 6.  Each time  we  find  a new code, we
 will send the prefix for that  code  to  the output data stream.

  A B A B A B A B B B A B A B A  A  C  D A C D A D  C A B A A A B A B ...
  \/\/---/-----/\/---/-------/\/ \/ \ /\/---/---/\ /\/-----/---/---/
  6 7   8     9 10 11      12 13 14 15 16  17 18 19 20   21  22  23   Code
      6    8      10    8                14  16        8    13  7     Prefix

 The  encoder table is built from input data stream. Always start  with
 the suffix  of  last  code,  and  keep getting colors  until  you  have  a
 new combination.
--------------------------------------------------------------------------
 Colour  | Code    | Prefix | Suffix |  String | Output
-------------------+--------+--------+---------+--------------------------
  A        0       |        |        |  -      |
  B        1       |        |        |  -      |
  C        2       |        |        |  -      |
  D        3       |        |        |  -      |
 Clear     4       |        |        |  -      |
 End       5       |        |        |  -      |
  A \              |   A    |   A    |         | First col is a special case.
  B /  \   6       |   A    |   B    |  AB     | A
  A |  /   7       |   B    |   A    |  BA     | B
  B |              |        |        |         |
  A /  |   8       |   6    |   A    |  ABA    | 6
  B    |           |        |        |         |
  A    |           |        |        |         |
  B \  /   9       |   8    |   B    |  ABAB   | 8
  B /  |   10      |   B    |   B    |  BB     | B
  B    |           |        |        |         |
  A |  /   11      |   10   |   A    |  BBA    | 10
  B |              |        |        |         |
  A |              |        |        |         |
  B |              |        |        |         |
  A /  \   12      |   9    |   A    |  ABABA  | 9
  A \  /   13      |   A    |   A    |  AA     | A
  C /  \   14      |   A    |   C    |  AC     | A
  D \  /   15      |   C    |   D    |  CD     | C
  A /  |   16      |   D    |   A    |  DA     | D
  C    |           |        |        |         |
  D |  /   17      |   14   |   D    |  ACD    | 14
  A |              |        |        |         |
  D /  \   18      |   16   |   D    |  DAD    | 16
  C \  /   19      |   D    |   C    |  DC     | D
  A /  |   20      |   C    |   A    |  CA     | C
  B    |           |        |        |         |
  A    |           |        |        |         |
  A |  /   21      |   8    |   A    |  ABAA   | 8
  A |              |        |        |         |
  B /  |   22      |   13   |   B    |  AAB    | 13
  A    |           |        |        |         |
  B    /   23      |   7    |   B    |  BAB    | 7
--------------------------------------------------------------------------

 The  resultant  output stream is: A B 6 8 B 10 9 A A C D 14 16 D C 8 ....
 The  GIF encoder starts with a code length of 2+1=3 bits for 4  colours,
 so when  the code reaches 8 we will have to increase the code size to 4
 bits. Similarly,  when the code gets to 16 we will have to increse the
 code size to 5 bits, etc. If the code gets to 13 bits, we send a clear
 code and start over.   See GIFENCOD.GIF for a flow diagram of the encoding
 process. This uses a tree method to search if a new string is already in
 the table, which is much simpler, faster, and easier to understand than
 hashing.