LZW parameter tuning MAX bits, hash tbl size, code word

Folks,

I am trying to understand the relationships between some of the LZW
parameters found in ImageMagick's coders/gif.c, so that I can alter
them and still produce a valid LZW output stream e.g. GIF image for an
embedded app. If I want my string table to be no larger than 256, then
my max code word must be less than 2^8. TIFF uncompressed data, for
example, is an index into a 256 3-tuple (RGB) color palette, meaning 8
bits worth of index.

ImageMagick's coders/gif.c lists function EncodeImage, which performs
the LZW compression. Typically the function is invoked with data to be
converted, and the output encoded in the second arg, Image *image. The
third arg contains is set to value of 9 is the data size for typical
input data.  

The MaxHashTable is set to 5003, which appears and works, but I don't
understand why? If the MaxGIFBits size is 12-bits, then that implies
that the string 2^12 = 4096. I want to set MaxGIFBits to 9, 10, and 11
bits, respectively and set MaxHashTable to a corresponding size value
that works. 

Any hints?

Thanks,
O. Usifer

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   E n c o d e I m a g e                                                     %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  EncodeImage compresses an image via GIF-coding.
%
%  The format of the EncodeImage method is:
%
%      MagickBooleanType EncodeImage(const ImageInfo *image_info,Image *image,
%        const unsigned long data_size)
%
%  A description of each parameter follows:
%
%    o image_info: The image info.
%
%    o image: The address of a structure of type Image.
%
%    o data_size:  The number of bits in the compressed packet.
%
%
*/

#define MaxCode(number_bits)  ((1UL << (number_bits))-1)
#define MaxHashTable  5003
#define MaxGIFBits  12UL
#define MaxGIFTable  (1UL << MaxGIFBits)

...

static MagickBooleanType EncodeImage(const ImageInfo *image_info,Image *image,
  const unsigned long data_size)
{
...
  offset=0;
  pass=0;
  waiting_code=0;
  for (y=0; y < (long) image->rows; y++)
  {
    p=AcquireImagePixels(image,0,offset,image->columns,1,&image->exception);
    if (p == (const PixelPacket *) NULL)
      break;
    indexes=GetIndexes(image);
    if (y == 0)
      waiting_code=(short) (*indexes);
    for (x=(y == 0) ? 1 : 0; x < (long) image->columns; x++)
    {
      /*
        Probe hash table.
      */
      index=indexes[x] & 0xff;
      p++;
      k=(long) (index << (MaxGIFBits-8))+waiting_code;
      if (k >= MaxHashTable)
        k-=MaxHashTable;
      next_pixel=MagickFalse;
      displacement=1;
      if (hash_code[k] > 0)
        {
          if ((hash_prefix[k] == waiting_code) &&
              (hash_suffix[k] == (unsigned char) index))
            {
              waiting_code=hash_code[k];
              continue;
            }
          if (k != 0)
            displacement=MaxHashTable-k;
          for ( ; ; )
          {
            k-=displacement;
            if (k < 0)
              k+=MaxHashTable;
            if (hash_code[k] == 0)
              break;
            if ((hash_prefix[k] == waiting_code) &&
                (hash_suffix[k] == (unsigned char) index))
              {
                waiting_code=hash_code[k];
                next_pixel=MagickTrue;
                break;
              }
          }
          if (next_pixel == MagickTrue)
            continue;
        }
      GIFOutputCode((unsigned long) waiting_code,
		    &bits, &datum, packet, &length, image, free_code, &max_code, &number_bits);
      if (free_code < MaxGIFTable)
        {
          hash_code[k]=(short) free_code++;
          hash_prefix[k]=waiting_code;
          hash_suffix[k]=(unsigned char) index;
        }
      else
        {
          /*
            Fill the hash table with empty entries.
          */
          for (k=0; k < MaxHashTable; k++)
            hash_code[k]=0;
          /*
            Reset compressor and issue a clear code.
          */
          free_code=clear_code+2;
          GIFOutputCode
	    (clear_code,
	     &bits, &datum, packet, &length, image, free_code, &max_code, &number_bits);
          number_bits=data_size;
          max_code=MaxCode(number_bits);
        }
      waiting_code=(short) index;
    }
...
}


-- 

Search for products and services at: 
http://search.mail.com