lzw.c

压缩算法的C语言源程序

/*
   lzw.c
   LZW Encoding and Decoding routines for gsLib
*/

#include <stdlib.h>
#include <compress.h>

typedef struct Dictionary
{
   unsigned char character;
   unsigned short code;
   struct Dictionary *prev,
                     *right,
                     *next;
} Dictionary;

#define DICTIONARY_BITS 12  // 12-bit dictionary
#define DICTIONARY_SIZE (1 << DICTIONARY_BITS) // Maximum Dictionary size
#define DEFAULT_CODE_SIZE 8

static word dindex; // dictionary index
static dword codesize; // Size in bits of encoding

static word cc; // clear code
static word eoi; // end of information code

static Dictionary *dictionary;
static short __lzw_codec_flag;

static int  InitDictionary();
static void ReInitDictionary();
static void RemoveDictionary();
static Dictionary *FindString(Dictionary *P,short C);
static void AddString(Dictionary *P,short C);
static void WriteLink(Dictionary *link);
static word FirstChar(Dictionary *link);

static STREAM *in, *out;
static dword bytesread, byteswritten, readlimit, writelimit;

// defines a few macros for file io transfer
inline static int getByte()
{
   if(bytesread < readlimit) {
      bytesread++;
      return stream_getc(in);
   }
   return -1;
}

inline static void putByte(int ch)
{
   if(byteswritten < writelimit) {
      byteswritten++;
      stream_putc(ch,out);
   }
}

inline static dword ReadBitr(dword size)
{
   int before;
   dword ch;

   if(bytesread < readlimit) {
      before = stream_tell(in);
      ch = stream_read_bitr(in,size);
      bytesread += stream_tell(in) - before;
      return ch;
   }
   return 0;
}

inline static void WriteBitr(dword code,dword size)
{
   int before;

   if(byteswritten < writelimit) {
      before = stream_tell(out);
      stream_write_bitr(out,code,size);
      byteswritten += stream_tell(out) - before;
   }
}

/*
   static int InitDictionary():
   Performs setup for the LZW algorithm
   Returns 0 on success
*/
static int InitDictionary()
{
   int i;

   codesize = DEFAULT_CODE_SIZE + 1;
   cc = 1 << DEFAULT_CODE_SIZE; // setup clear code
   eoi = cc + 1; // setup EOI code

   // allocate DICTIONARY_SIZE entries
   dictionary = (Dictionary *)malloc(DICTIONARY_SIZE * sizeof(Dictionary));
   if(!dictionary) {
      gerror("There is not enough memory for dictionary.");
      THROW (E_MEMORY) return -1;
   }

   // set up dictionary entries
   for(i = 0; i < DICTIONARY_SIZE; i++) {
      dictionary[i].character = i;
      dictionary[i].code = i;
      dictionary[i].next = NULL;
      dictionary[i].right = NULL;
      dictionary[i].prev = NULL;
   }

   dindex = eoi + 1; // set dictionary index to eoi + 1

   return 0;
}

/*
   static void ReInitDictionary():
   ReInitializes the dictionary when the dictionary is full
*/
static void ReInitDictionary()
{
   int i;

   // clears all links etc
   for(i = 0; i < DICTIONARY_SIZE; i++) {
      dictionary[i].character = i;
      dictionary[i].code = i;
      dictionary[i].next = NULL;
      dictionary[i].right = NULL;
      dictionary[i].prev = NULL;
   }
   // reset dindex and codesize
   dindex = eoi + 1;
   codesize = DEFAULT_CODE_SIZE + 1;
}

/*
   static void RemoveDictionary():
   Frees up the memory used by the dictionary
*/
static void RemoveDictionary()
{
   free(dictionary);
}

/*
   static Dictionary *FIndString(Dictionary *P,short C):
   Finds a match from the string PC in the dictionary
   Returns a pointer to the found node, otherwise NULL
*/
static Dictionary *FindString(Dictionary *P,short C)
{
   Dictionary *ptr;

   if(!P->next) return NULL;

   ptr = P->next;  // traverse up one level
   while(ptr->character != C) {
      ptr = ptr->right; // search through all the right nodes
      if(!ptr) return NULL;
   }

   return ptr; // return found ndoe
}

/*
   static void AddString(Dictionary *P,short C):
   Adds the string PC into the dictionary
*/
static void AddString(Dictionary *P,short C)
{
   Dictionary *ptr;

   if(dindex < DICTIONARY_SIZE) {
      // create a new node for C
      dictionary[dindex].code = dindex;
      dictionary[dindex].character = C;
      dictionary[dindex].next = NULL;
      dictionary[dindex].right = NULL;
      dictionary[dindex].prev = P; // chain back to previouse node

      // insert new node at the right of the chain
      if(!P->next) P->next = &dictionary[dindex];
      else {
         ptr = P->next;
         while(ptr->right) ptr = ptr->right;
         ptr->right = &dictionary[dindex];
      }

      // increment codesize as soon as dindex hit 2**codesize
      // 1 is also added on decoding which is corrected by the __lzw_codec_flag
      if(dindex + __lzw_codec_flag >= (1 << codesize)) codesize++;
      dindex++;
   }
}

/*
   static void WriteLink(Dictionary *link):
   Writes the chain of strings associated with link to the output stream
*/
static void WriteLink(Dictionary *link)
{
   if(!link) return;

   WriteLink(link->prev);
   putByte(link->character);
}

/*
   static word FirstChar(Dictionary *link):
   Returns the first character of the chain of strings
*/
static word FirstChar(Dictionary *link)
{
   while(link->prev) link = link->prev;
   return link->character;
}

/*
   dword lzw_encode(STREAM *dest,STREAM *src,dword length):
   Compresses the data stream from `src' to `dest'. The `length' field is the
   number of bytes to compress. Returns the compressed byte size or 0 on error
*/
dword lzw_encode(STREAM *dest,STREAM *src,dword length)
{
   Dictionary *P, *PC;
   short C;

   in = src;
   out = dest;
   bytesread = byteswritten = 0;
   readlimit = length;
   writelimit = 0xFFFFFFFF;

   __lzw_codec_flag = 0;

   if(InitDictionary()) return 0;
   WriteBitr(cc,codesize); // emit clear code as first character
   P = &dictionary[getByte()]; // get first character
   while(bytesread < length) {
      C = getByte();  // get next character
      PC = FindString(P,C); // find the string PC
      if(PC) P = PC; // if found assign PC to P
      else {
         WriteBitr(P->code,codesize); // write codeP
         AddString(P,C); // add the string PC to the dictionary
         if(dindex > DICTIONARY_SIZE) { // reinit dictionary if full
            WriteBitr(cc,codesize);
            ReInitDictionary();
         }
         P = &dictionary[C]; // P = C
      }
   }
   WriteBitr(P->code,codesize);
   WriteBitr(eoi,codesize); // Write EOI
   stream_flush_write_bufferr(out); // flushes output
   RemoveDictionary();

   return byteswritten;
}

/*
   dword lzw_decode(STREAM *dest,STREAM *src,dword length):
   Decompresses the data from `src' to `dest'. `length' specifies the number of
   byte to decompress. Returns the number of bytes written to the stream or 0 on
   error
*/
dword lzw_decode(STREAM *dest,STREAM *src,dword length)
{
   Dictionary *pW, *P;
   short cW, C;

   in = src;
   out = dest;
   bytesread = byteswritten = 0;
   readlimit = 0xFFFFFFFF;
   writelimit = length;

   __lzw_codec_flag = 1; // set up flag

   if(InitDictionary()) return 0;

   cW = ReadBitr(codesize); // read first character
   if(cW != cc) { // if it's not the clear code
      RemoveDictionary();
      gerror("LZW error: Clear-code is not the first code in stream.");
      THROW (E_FORMAT) return 0;
   }

   cW = ReadBitr(codesize); // get next character
   WriteLink(&dictionary[cW]); // write cW
   pW = &dictionary[cW]; // pW = cW

   while(byteswritten < length) {
      cW = ReadBitr(codesize); // read next character
      if(cW < dindex) { //if cW is in the dictionary
         if(cW == cc) { // if clearcode
            ReInitDictionary(); // reinitialze the dictionary
            cW = ReadBitr(codesize);
            WriteLink(&dictionary[cW]);
            pW = &dictionary[cW];
            continue;
         }
         if(cW == eoi) break;

         WriteLink(&dictionary[cW]); // write the string at cW
         P = pW;
         C = FirstChar(&dictionary[cW]); // get first character
         AddString(P,C); // add the string PC
         pW = &dictionary[cW];
      } else if(cW == dindex) { // if cW is the next entry of the dictionary
         P = pW;
         C = FirstChar(pW);
         WriteLink(P);   // write P+first char of C
         putByte(C);
         AddString(P,C);
         pW = &dictionary[cW];
      } else { // we got problems if cW > dindex
         gerror("LZW error: Invalid LZW code\n"
                "Program terminated!\n"
                "DEBUG DUMP:\n"
                "Read=%d Written=%d Index=%u cW=%d\n",
                bytesread, byteswritten, dindex, cW);
         RemoveDictionary();
         THROW (E_INVALID) return 0;
      }
   }

   RemoveDictionary();

   return byteswritten;
}