deflate.c

压缩算法的C语言源程序

/*
   deflate.c
   Deflate and Inflate Algorithm v1.2 for gsLib
*/
#include <stdlib.h>
#include <string.h>
#include <compress.h>

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

// extra bits in the length table
static const int extra_lenbits[] = {
   0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0
};

// length table bases
static const int lenbase[] =
{
   3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,
   115,131,163,195,227,258,999
};

// extra bits in the distance table
static const int extra_distbits[] = {
   0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
};

// distance table bases
static const int distbase[] = {
   1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,
   1537,2049,3073,4097,6145,8193,12289,16385,24577,99999
};

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;
   }
}

inline static void WriteHuffCode(HuffTable bin)
{
   int before;

   before = stream_tell(out);
   WriteHuffmanCode(out,bin);
   byteswritten += stream_tell(out) - before;
}

inline static void FlushReadBuffer()
{
   stream_flush_read_buffer(in);
}

inline static void FlushWriteBufferR()
{
   stream_flush_write_bufferr(out);
}

/*
   dword deflate(STREAM *dest,STREAM *src,dword length,int level):
   Compresses `src' to `dest' using the deflate algorithm.
*/
dword deflate(STREAM *dest,STREAM *src,dword length,int level)
{
   STREAM *lz;
   HuffTable *littab, *disttab;
   int mask = 0, ch, len, dist, prefixcnt = 0, before, i;
   byte *data;

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

   // allocate temporary memory
   lz = stream_alloc(length + (length >> 3));
   if(!lz) return 0;

   littab = (HuffTable *)malloc((286 + 30) * sizeof(HuffTable));
   if(!littab) {
      stream_close(lz);
      gerror("Not enough memory for literal table.");
      THROW (E_MEMORY) return 0;
   }

   disttab = &littab[286];
   // initialize the table
   for(i = 0; i < 286; i++) {
      littab[i].code = i;
      littab[i].len = 0;
      if(i < 30) {
         disttab[i].code = i;
         disttab[i].len = 0;
      }
   }

   // lz77 encode it first
   length = lz77_encode(lz,in,length,level);
   if(!length) {
      stream_close(lz);
      free(littab);
      return 0;
   }
   readlimit = length;

   // get data
   data = lz->handle.mp;
   // first pass: count number of lit/dist
   while(bytesread < length) {
      if(!prefixcnt) {
         mask = data[bytesread++];  // get prefix
         prefixcnt = 8;
      }
      if(mask & 0x80) { // if prefix is flagged
         len = *(data + bytesread) + 3;
         dist = *(word *)(data + bytesread + 1) + 1;
         bytesread += 3;

         for(i = 0; i < 29; i++) if(len < lenbase[i + 1]) break;
         littab[i + 257].len++;
         for(i = 0; i < 30; i++) if(dist < distbase[i + 1]) break;
         disttab[i].len++;
      } else { // otherwise literal output
         ch = data[bytesread++];
         littab[ch].len++;
      }

      mask <<= 1;
      prefixcnt--;
   }

   littab[256].len = 1; // EOF len = 1

   // generate huffman codes
   CalculateMinimumRedundancy(littab,286);
   BuildHuffTable(littab,286);
   CalculateMinimumRedundancy(disttab,30);
   BuildHuffTable(disttab,30);
   before = stream_tell(out);
   WriteHuffmanHeader(out,littab,286,30); // write deflate header
   byteswritten = stream_tell(out) - before;

   // pass 2: genertae codes
   prefixcnt = 0;
   mask = 0;

   bytesread = 0;
   while(bytesread < length) {
      if(!prefixcnt) {
         mask = data[bytesread++];  // get prefix
         prefixcnt = 8;
      }
      if(mask & 0x80) { // if prefix is flagged
         len = *(data + bytesread) + 3;
         dist = *(word *)(data + bytesread + 1) + 1;
         bytesread += 3;

         for(i = 0; i < 29; i++) if(len < lenbase[i + 1]) break;
         WriteHuffCode(littab[i + 257]);
         len -= lenbase[i];
         if(extra_lenbits[i]) WriteBitr(len,extra_lenbits[i]);
         for(i = 0; i < 30; i++) if(dist < distbase[i + 1]) break;
         WriteHuffCode(disttab[i]);
         dist -= distbase[i];
         if(extra_distbits[i]) WriteBitr(dist,extra_distbits[i]);
      } else { // otherwise literal output
         ch = data[bytesread++];
         WriteHuffCode(littab[ch]);
      }

      mask <<= 1;
      prefixcnt--;
   }

   WriteHuffCode(littab[256]); // write EOF
   before = stream_tell(out);
   FlushWriteBufferR();
   byteswritten = stream_tell(out) - before;

   free(littab);
   stream_close(lz);

   return byteswritten;
}

/*
   dword inflate(STREAM *dest,STREAM *src,dword length):
   Decompress `src' to `dest' by the method inflate
*/
dword inflate(STREAM *dest,STREAM *src,dword length)
{
   int i, nlit, ndist, len, dist, code, final = 0;
   byte *sw;
   HuffTable *littab, *disttab;
   HuffLookup *litlk, *distlk;
   dword winoffset = 0;

   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;
   }

   littab = (HuffTable *)malloc((286 + 30) * sizeof(HuffTable));
   if(!littab) {
      free(sw);
      gerror("Not enough memory for Literal/Distance Tables.");
      THROW (E_MEMORY) return 0;
   }

   while(!(final & 1)) {
      final = ReadHuffmanHeader(in,littab,&disttab,&nlit,&ndist);

      if(final & 2) {            // if literal data
         FlushReadBuffer();      // clear remaining bits
         len = getByte();
         len |= getByte() << 8;  // read Len
         code = getByte();
         code |= getByte() << 8;  // read length compliment
         if(len + code != 0xFFFF) {
            gerror("Len and nLen are not compliment! Please report bug.");
            free(sw); free(littab);
            THROW (E_UNKNOWN) return 0;
         }
         // copy literal byte to output
         for(i = 0; i < len; i++) {
            code = getByte();
            putByte(code);
            sw[winoffset] = code;
            winoffset++;
            winoffset &= WINDOW_MASK;
         }
         continue;
      }

      litlk = BuildHuffmanLookupTable(littab,nlit);
      if(!litlk) {
         free(sw); free(littab);
         gerror("Not enough memory for literal lookup table.");
         THROW (E_MEMORY) return 0;
      }
      distlk = BuildHuffmanLookupTable(disttab,ndist);
      if(!distlk) {
         free(sw); free(littab); free(litlk);
         gerror("Not enough memory for distance lookup table.");
         THROW (E_MEMORY) return 0;
      }

      while(byteswritten < length) {
         code = FetchHuffmanCode(in,litlk);

         if(code == 256) break; // eof code
         else {
            if(code > 256) { // len code
               // decode len
               len = lenbase[code - 257];
               if(extra_lenbits[code - 257])
                  len += ReadBitr(extra_lenbits[code - 257]);

               // decode distance
               code = FetchHuffmanCode(in,distlk);

               dist = distbase[code];
               if(extra_distbits[code])
                  dist += ReadBitr(extra_distbits[code]);

               // go bask dist bytes, and copy len bytes to the output
               for(i = 0; i < len; i++) {
                  putByte(sw[(winoffset - dist) & WINDOW_MASK]);
                  sw[winoffset] = sw[(winoffset - dist) & WINDOW_MASK];
                  winoffset++;
                  winoffset &= WINDOW_MASK;
               }
            } else { // code is < 256 mean its a literal
               putByte(code);
               sw[winoffset] = code;
               winoffset++;
               winoffset &= WINDOW_MASK;
            }
         }
      } // end while

      free(litlk);
      free(distlk);
   } // end while

   free(sw);
   free(littab);

   return byteswritten;
}