lz77.c

压缩算法的C语言源程序

/*
   lz77.c
   LZ77 Algorithm for gsLib
*/
#include <stdlib.h>
#include <string.h>
#include <compress.h>

#define WINDOW_SIZE 32768 // 32k Sliding Window
#define WINDOW_MASK (WINDOW_SIZE - 1)

#define MIN_MATCH 3
#define MAX_MATCH 258

#define HASH_BITS 15
#define HASH_SIZE (1 << HASH_BITS)
#define HASH_MASK (HASH_SIZE - 1)

#define HASH_SHIFT ((HASH_BITS + MIN_MATCH - 1) / MIN_MATCH)

typedef struct LZMatch
{
   int length;
   dword distance;
} LZMatch;

static byte *window;	// sliding window
static dword winpos; // window position
static int *hash;    // hash table
static int *prev;    // previous hash values
static int remaining;// bytes remaining to parse
static dword ihash;  // hash save

static const struct
{
	int goodlength;
	int maxlazy;
	int nicelength;
	int maxchain;
}

// GZIP's config table
configtab[10] =
{
/*		good	lazy	nice	chain */
/*0*/{0,		0,		0,		0		},
/*1*/{4,		0,		8,		4		},
/*2*/{4,		0,		16,	8		},
/*3*/{4,		0,		32,	32		},
/*4*/{4,		4,		16,	16		},
/*5*/{8,		16,	32,	32		},
/*6*/{8,		16,	128,	128	},
/*7*/{8,		32,	128,	256	},
/*8*/{32,	128,	258,	1024	},
/*9*/{32,	258,	258,	4096	}
};

static int maxlazy = 0;
static int nicelength = 0;
static int maxchain = 0;

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 unsigned int readBytes(void *buffer,unsigned int size)
{
   unsigned int read;

   if(bytesread < readlimit) {
      if(bytesread + size >= readlimit) size = readlimit - bytesread;
      read = stream_read(buffer,1,size,in);
      bytesread += read;
      return read;
   }
   return 0;
}

inline static unsigned int writeBytes(void *buffer,unsigned int size)
{
   unsigned int write;

   if(byteswritten < writelimit) {
      if(byteswritten + size >= writelimit) size = writelimit - byteswritten;
      write = stream_write(buffer,1,size,out);
      byteswritten += write;
      return write;
   }
   return 0;
}

inline static void UPDATE_HASH(int key)
{
   ihash = ((ihash << HASH_SHIFT) ^ key) & HASH_MASK;
}

inline static int ADD_HASH(int string)
{
	UPDATE_HASH(window[string + MIN_MATCH-1]);
	prev[string & WINDOW_MASK] = hash[ihash];
	hash[ihash] = string;

	return prev[string & WINDOW_MASK];
}

static int InitLZ77();
static void RemoveLZ77();
static void ReloadWindow();
static int FindMatch(LZMatch *bestmatch,int curmatch);

/*
   static int InitLZ77():
   Sets up LZ77 alogithm, returns 0 on sucess
*/
static int InitLZ77()
{
   window = NULL;
   hash = NULL;
   prev = NULL;

   window = (byte *)malloc(WINDOW_SIZE * 2);
   if(!window) {
      gerror("Not enough memory for sliding window.");
      THROW (E_MEMORY) goto INIT_ERROR;
   }

   hash = (int *)malloc(HASH_SIZE * sizeof(int));
   if(!hash) {
      gerror("Not enough memory for LZ77 hash table.");
      THROW (E_MEMORY) goto INIT_ERROR;
   }
   memset(hash,0xFF,HASH_SIZE * sizeof(int));

   prev = (int *)malloc(WINDOW_SIZE * sizeof(int));
   if(!prev) {
      gerror("Not enough memory for LZ77 chain.");
      THROW (E_MEMORY) goto INIT_ERROR;
   }
   memset(prev,0xFF,WINDOW_SIZE * sizeof(int));

   ihash = 0;
   winpos = 0;

   return 0;
INIT_ERROR:
   RemoveLZ77();
   return -1;
}

/*
   static void RemoveLZ77():
   Deallocates all memory used by LZ77 routines
*/
static void RemoveLZ77()
{
   free(hash);
   free(prev);
   free(window);
}

/*
   static void ReloadWindow():
   Reloads the sliding window with data when if it full
*/
static void ReloadWindow()
{
   register int pos = winpos - WINDOW_SIZE; // beginning of window
   register int size = WINDOW_SIZE * 2 - pos; // size to copy
   register int i;

   if(winpos < (WINDOW_SIZE * 2 - MAX_MATCH)) return;

   memcpy(window,window + pos,size); // shift bytes over
   remaining += readBytes(window + size,WINDOW_SIZE * 2 - size);

   winpos -= pos;

   // reupdate hash tables
   for(i = 0; i < HASH_SIZE; i++)
      hash[i] = hash[i] >= pos ? hash[i] - pos : -1;
   for(i = 0; i < WINDOW_SIZE; i++)
      prev[i] = prev[i] >= pos ? prev[i] - pos : -1;
}

/*
   static int FindMatch(LZMatch *bestmatch,int curmatch):
   Searches through the sliding window for the longest match
*/
static int FindMatch(LZMatch *bestmatch,int curmatch)
{
   register byte *readahead = window + winpos;
   register byte *match;
   register int len;
   int chainlen = maxchain;
   int limit = winpos > WINDOW_SIZE ? (int)(winpos - WINDOW_SIZE) : -1;

   bestmatch->length = 2;
   if(winpos - curmatch > WINDOW_SIZE) return 0;

   do {
      match = window + curmatch;
      if(*(word *)match != *(word *)readahead ||
         *(match + bestmatch->length) != *(readahead + bestmatch->length)) continue;

      // compare strings
      for(len = 2; len < 258; len++)
         if(match[len] != readahead[len]) break;

      if(len > bestmatch->length) {
         bestmatch->length = len;
         bestmatch->distance = readahead - match;
         if(len > remaining) bestmatch->length = remaining;
         if(len >= nicelength) break;
      }
   } while((curmatch = prev[curmatch & WINDOW_MASK]) > limit && --chainlen);

   if(bestmatch->length >= 3) return 1;

   return 0;
}

/*
   dword lz77_encode(STREAM *dest,STREAM *src,dword length,int level):
   Compressed src to dest with the lz77 algorithm. The `level' is the the level
   of compression 0-9. Higher the level, the higher the ratio, but is slower.
   Returns the number of bytes compressed or 0 on error
*/
dword lz77_encode(STREAM *dest,STREAM *src,dword length,int level)
{
   LZMatch match, next;
   int mask = 0, bytecnt = 8, pos = 0, lazy = 0;
   int matchhead = -1;
   byte buf[24];

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

   if(level < 0 || level > 9) {
      gerror("LZ77 encoding levels must range from 0 - 9.");
      THROW (E_INVALID) return 0;
   }

   if(InitLZ77()) return 0;

   maxlazy    = configtab[level].maxlazy;
   nicelength = configtab[level].nicelength;
   maxchain   = configtab[level].maxchain;

   // load sliding window
   remaining = readBytes(window,length < WINDOW_SIZE * 2 ? length : WINDOW_SIZE * 2);
   UPDATE_HASH(window[0]);
   UPDATE_HASH(window[1]);

   match.length = MIN_MATCH - 1;
   while(remaining > 0) {
      if(!lazy) matchhead = ADD_HASH(winpos);
      else lazy = 0;

      if(matchhead != -1) {
         FindMatch(&match,matchhead);

         if(match.length >= MIN_MATCH && match.length < maxlazy) {
            winpos++;
            remaining--;
            matchhead = ADD_HASH(winpos);
            FindMatch(&next,matchhead);
            if(match.length < next.length) match.length = MIN_MATCH - 1;
            lazy = 1;
         }
      }

      // is match found
      if(match.length >= MIN_MATCH) {
         mask = (mask << 1) | 1;
         buf[pos] = match.length - 3;
         *(word *)(buf + pos + 1) = match.distance - 1;

         pos += 3;
         bytecnt--;

         remaining -= match.length - lazy;
         match.length -= 1 + lazy;

         do {
            winpos++;
            matchhead = ADD_HASH(winpos);
         } while(--match.length);
         winpos++;
         lazy = 0;
      } else { // output literal byte
         mask <<= 1;
         buf[pos++] = *(window + winpos - lazy);
         bytecnt--;

         if(!lazy) {
            remaining--;
            winpos++;
         }
      }

      if(!bytecnt) {
         putByte(mask);
         writeBytes(buf,pos);
         mask = pos = 0;
         bytecnt = 8;
      }

      if(remaining < MAX_MATCH) ReloadWindow();
   }

   if(bytecnt) {
      mask <<= bytecnt;
      putByte(mask);
      writeBytes(buf,pos);
   }

   RemoveLZ77();
   return byteswritten;
}

/*
   dword lz77_decode(STREAM *dest,STREAM *src,dword length):
   Decompresses src to dest with the lz77 algorithm.
   Returns the number of bytes written or 0 on error
*/
dword lz77_decode(STREAM *dest,STREAM *src,dword length)
{
   int mask = 0, ch, i;
   int len, dist, prefixcnt = 0;
   byte *sw;

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

   sw = (byte *)malloc(WINDOW_SIZE);
   if(!sw) {
      gerror("Not enough memory for sliding window.");
      THROW (E_MEMORY) return 0;
   }

   winpos = 0;
   while(byteswritten < length) {
      if(!prefixcnt) {
         mask = getByte(); // get mask
         prefixcnt = 8;
      }

      if(mask & 0x80) { // is length,dist code
         len = getByte() + 3;
         dist = getByte();
         dist |= (getByte() << 8);
         dist++;

         // go back distance, and copy length bytes
         for(i = 0; i < len; i++) {
            putByte(sw[(winpos - dist) & WINDOW_MASK]);
            sw[winpos] = sw[(winpos - dist) & WINDOW_MASK];
            winpos++;
            winpos &= WINDOW_MASK;
         }
      } else { // otherwise output literal
         ch = getByte();

         putByte(ch);
         sw[winpos] = ch;
         winpos++;
         winpos &= WINDOW_MASK;
      }

      mask <<= 1;
      prefixcnt--;
   }

   free(sw);
   return byteswritten;
}