Subject: Q: LZW-compression and GIF

From: [email-masked] (Johan Levin)
Date: 13 Apr 1997 13:26:08 GMT

I'm trying to make a gif-decoder and need some help about
the LZW compression algorithm. This is the definition of LZW
that I've read:
         
/*********************************************************************
   2.1 LZW Compression

   The  LZW  compressor  reads  8-bit  bytes  from  a data source and
   outputs N-bit codes each of which identifies a previously  defined
   string.   The  value  of  N starts at 9. Thus, codes 0 through 255
   ($ff) correspond with the standard character set, while codes  256
   ($100)  through  511  ($1ff)  correspond  to a byte-byte pair or a
   code-byte pair in the code table. After code 511 is output, 10 bit
   codes are used. This is repeated until the maximum number of  bits
   per code is reached. LZW4P can use a maximum of 12, 13, or 14 bits
   per code. The recommended value is 14.

   The LZW compressor builds a code table as it compresses data.  The
   code table consists of previously encountered strings.

   The basic LZW compression algorithm is as follows:

             STRING = get first input byte
             while there is more input data
               {BYTE = get next input byte
                if STRING+BYTE is in code table
                   STRING=STRING+BYTE
                else
                  {output code for STRING
                   add STRING+BYTE to code table
                   STRING = BYTE
                  }
              }
             output the code for STRING

   2.2 LZW Expansion

   The LZW expansion routine reads the N-bit codes previously created
   by  the  LZW  compressor  and  reconstructs  the  code  table  (as
   previously constructed by the compressor) as it is outputing 8-bit
   bytes.   A  code corresponds to a single byte (the first 256 codes
   from $00 through $ff), or a byte-byte pair in the code table, or a
   code-byte pair in the code table. In the later case, the code part
   of the code-byte pair refers to another defined code pair  in  the
   table.   As  each code is read in, it is located in the code table
   and the corresponding 8-bit bytes are  output.   This  means  that
   codes must be defined before they are needed for expansion. Unlike
   older  dictionary  based  compression schemes, the code dictionary
   produced by the compressor routine does not have to be provided to
   the expansion routine.

   The basic LZW de-compression algorithm is as follows:

             OLDCODE = input first code
             output OLDCODE
             while there is more input data
               {NEWCODE = get next input code
                STRING = translation of NEWCODE
                output STRING
                BYTE = 1st byte of STRING
                add OLDCODE+BYTE to the code table
                OLDCODE = NEWCODE
               }
*********************************************************************/
 
According to these algoriths the stream:

0xff 0xff 0xff 0xff 0xff ...

would generate these (9-bit) codes

0xff 0x100 0x101 ...

When the codes are decoded, this happends:

OLDCODE=0xff (input)
output 0xff (oldcode)
NEWCODE=0x100 (input)
Then I'm suppose to translate the code 0x100, but there
are no entries in the codetable. What am I doing wrong???

(I know that the first two codes are predefined in gif and
that the initial codesize isn't always 9, that isn't the
problem.)

I'd appreciate any help, TIA.

-- 
Johan Levin                         Sweden
------------------------------------------
homepage: http://home2.swipnet.se/~w-21572
mail    : [email-masked]

---

From: [email-masked] (Bevyn Douglas Quiding)
Date: Mon, 14 Apr 1997 18:44:53 +1200

In article <[email-masked]>, [email-masked] (Johan Levin)

> are no entries in the codetable. What am I doing wrong???

if you look at the problem you aren't doing anything wrong it's just a
offshoot with the algo that you have to be aware of. when the decoder
recieves a code which is equal to the next free slot in it's dictionary
(as in this case) it isn't necessarily invalid. but could equal the last
code recieved + the first character of the new code. the first character
of the new code = the first character of the old code. (if the old code
dosen't exist then it is an invalid code ie when the table has just been
cleared ) 

so in this case the decoder should do something like this

get 0xff
output 0xff 
last_first_char = 0xff 
old_code = Oxff
get 0x100
add_to_dictionary (old_code + last_fist_char)
output 0xff 0xff 
last_first_char = 0xff 
old_code = Oxff 0xff
get 0x101
add_to_dictionary (old_code + last_fist_char)
output 0xff 0xff 0xff
last_first_char = 0xff 
old_code = Oxff 0xff 0xff

bevyn.

-- 
email address has been rot 13'd.
please no junk mail (own business blah blah yakkety shmack)

---

From: Timon Marmex Trzepacz <[email-masked]>
Date: Wed, 16 Apr 1997 02:51:23 -0700

> are no entries in the codetable. What am I doing wrong???

When you get an entry beyond the last entry in the current code table,
that is your signal to add a new entry there with whatever the last
actual character (not code) was and the last code.

In this case, the last actual character and the last code are the same
character.

Then follow your algorithm normally.

It's a wierd special case, I know, but it works ...

-- Tim Trzepacz --