huffman.c

压缩算法的C语言源程序

   Gets a huffman code from the stream using the lookup table
*/
dword FetchHuffmanCode(STREAM *fp,HuffLookup *lookup)
{
   dword code;
   int bitsToReturn;
   dword value;
   int len;

   code = ReverseBits(stream_read_bitr(fp,9),9); // read 9 bits

   len = lookup->tablelo[code].len;
   if(len > 9) { // if > 9 use hi table
      code = ReverseBits(stream_read_bitr(fp,6),6); // 6 bits
      value = lookup->tablehi[len & 0x7FFF][code].code;
      len = lookup->tablehi[len & 0x7FFF][code].len;
      bitsToReturn = 15 - len;
      code = ReverseBits(code,6) >> (6 - bitsToReturn); // unreverse bits
   } else {
      value = lookup->tablelo[code].code;
      bitsToReturn = 9 - len;
      code = ReverseBits(code,9) >> len;
   }

   stream_unread_bitr(fp,code,bitsToReturn);

   return value;
}

/*
   void WriteHuffmanCode(STREAM *fp,HuffTable tab):
   Writes the huffman code to the stream
*/
void WriteHuffmanCode(STREAM *fp,HuffTable tab)
{
   dword code;

   code = ReverseBits(tab.bits & ((1 << tab.len) - 1),tab.len);
   stream_write_bitr(fp,code,tab.len);
}

/*
   static void ReadCodeLengths(STREAM *fp,HuffLookup *l,HuffTable tab[],int n):
   Reads the huffman code lengths to tab
*/
static void ReadCodeLengths(STREAM *fp,HuffLookup *l,HuffTable tab[],int n)
{
   int i, len, code, lastcode = 0;

   for(i = 0; i < n; i++) {
      code = FetchHuffmanCode(fp,l);
      switch(code) {
         default: tab[i].len = code; lastcode = code; break;
         case 16: len = stream_read_bitr(fp,2) + 3;
                  for(;len;i++,len--) tab[i].len = lastcode;
                  i--;
                  break;
         case 17: len = stream_read_bitr(fp,3) + 3;
                  for(;len;i++,len--) tab[i].len = 0;
                  i--;
                  break;
         case 18: len = stream_read_bitr(fp,7) + 11;
                  for(;len;i++,len--) tab[i].len = 0;
                  i--;
                  break;
      } // end switch
   } // end for
}

/*
   static void WriteCodeLengths(STREAM *fp,HuffTable *lentab,HuffTable *tab,int n,int scan):
   Writes the code lengths to file or builds a frequency of code lengths if
   `scan' = TRUE
*/
static void WriteCodeLengths(STREAM *fp,HuffTable *lentab,HuffTable *tab,int n,int scan)
{
   int i, runcount, current, match = 0;

   current = tab[0].len; // get first length
   for(i = 1; i <= n; i++) {
      runcount = 0;

      for( ; i <= n; i++) {
         runcount++; // increment runcount
         match = tab[i].len;

         if(runcount >= 7 && current != 0) break; // max run is 7 for non zeros
         if(runcount >= 138) break; // max zero rle is 138
         if(match != current) break;
      }

      // if zero runcount
      if(current == 0 && runcount >= 3) {
         if(runcount <= 10) { // write code 17 if < 10
            if(scan) lentab[17].len++;
            else {
               WriteHuffmanCode(fp,lentab[17]);
               stream_write_bitr(fp,runcount - 3,3);
            }
          } else {            // otherwise write code 18 for long zrle code
            if(scan) lentab[18].len++;
            else {
               WriteHuffmanCode(fp,lentab[18]);
               stream_write_bitr(fp,runcount - 11, 7);
            }
          }
      } else if(runcount > 3 && current != 0) {
         // if 3 < runcount < 7, then emit code 16
         if(scan) {
            lentab[current].len++;
            lentab[16].len++;
         } else {
            WriteHuffmanCode(fp,lentab[current]);
            WriteHuffmanCode(fp,lentab[16]);
            stream_write_bitr(fp,runcount - 4, 2);
         }
      } else {
         // emit literals
         for(; runcount; runcount--) {
            if(scan) lentab[current].len++;
            else WriteHuffmanCode(fp,lentab[current]);
         }
      }

      current = match;
   }
}

/*
   int ReadHuffmanHeader(STREAM *fp,HuffTable *tab,HuffTable **dist,int *nLit,int *nDist):
   Reads a huffman header from a stream to `tab' and updates `dist' to point to
   the start of the distance table. If `dist' is NULL, it is ignored
   The header follows accordingly to the deflate header. `dist' will point to
   NULL if the distance table is not used.
   The return values returns a set of flags as decribed below:
      if the return is -1 and error has occured
      if the return is 0, the function was successful
      if bit 1 is set, it means that it is the final block
      if bit 2 is set, it means that the block is not compressed
*/
int ReadHuffmanHeader(STREAM *fp,HuffTable *tab,HuffTable **dist,int *nLit,int *nDist)
{
   int hclen, hlit, hdist, bfinal, btype, i;

   HuffLookup *lookup;
   HuffTable codlen[19] = {
      {16, 0}, {17, 0}, {18, 0},
      { 0, 0},	{ 8, 0},	{ 7, 0},
      { 9, 0},	{ 6, 0},	{10, 0},
      { 5, 0},	{11, 0},	{ 4, 0},
      {12, 0},	{ 3, 0},	{13, 0},
      { 2, 0},	{14, 0},	{ 1, 0},
      {15, 0}
   };

   bfinal = stream_read_bitr(fp,1); // read bfinal
   btype = stream_read_bitr(fp,2);

   switch(btype) {
      case 0   :  return 2 | bfinal; // no compression
      case 1   :  // initializes the Huffman Table
                  for(i = 0; i < 286; i++) {
                     tab[i].code = i;
                     tab[i].len = 0;
                     if(i < 30) {
                        tab[286 + i].code = i;
                        tab[286 + i].len = 0;
                     }
                  }

                  if(nLit) *nLit = 286;
                  if(nDist) *nDist = 30;
                  if(dist) *dist = &tab[286];

                  for(i = 0; i <= 143; i++) tab[i].len = 8;
                  for(i = 144; i <= 255; i++) tab[i].len = 9;
                  for(i = 256; i <= 279; i++) tab[i].len = 7;
                  for(i = 280; i <= 285; i++) tab[i].len = 8;
                  if(dist) for(i = 0; i < 30; i++) tab[286 + i].len = 5;
                  BuildHuffTable(tab,286);
                  if(dist) BuildHuffTable(*dist,30);
                  return bfinal;
      case 2   :  break;             // compressed with dynamic huffman codes
      default  :  gerror("BTYPE is unknown in inflation.");
                  THROW (E_FORMAT) return -1;
   }

   hlit = stream_read_bitr(fp,5);
   hdist = stream_read_bitr(fp,5);
   hclen = stream_read_bitr(fp,4);

   if(dist) {
      if(hdist > 0) *dist = &tab[hlit + 257];
      else *dist = NULL;
   }
   if(nLit) *nLit = hlit + 257;
   if(nDist) *nDist = hdist ? hdist + 1 : 0;

   if(!hdist) hdist = -1;

   // initializes the Huffman Table
   for(i = 0; i < hlit + 257; i++) {
      tab[i].code = i;
      tab[i].len = 0;
      if(i < hdist + 1) {
         tab[hlit + 257 + i].code = i;
         tab[hlit + 257 + i].len = 0;
      }
   }

   // read in code lengths
   for(i = 0; i < hclen + 4; i++)
      codlen[i].len = stream_read_bitr(fp,3);

   // build the huffman codes
   qsort(codlen,hclen + 4,sizeof(HuffTable),HuffSortByCode);
   BuildHuffTable(codlen,hclen + 4);
   lookup = BuildHuffmanLookupTable(codlen,hclen + 4);
   if(!lookup) return -1;

   ReadCodeLengths(fp,lookup,tab,hlit + hdist + 258);
   BuildHuffTable(tab,hlit + 257);
   if(dist) {
      if(*dist) BuildHuffTable(*dist,hdist + 1);
   }

   free(lookup);

   return bfinal;
}

/*
   int WriteHuffmanHeader(STREAM *fp,HuffTable *tab,int nLit,int nDist):
   Writes a huffman header to the file. `nLit' is the number of literal values,
   while `nDist' is the number of distance codes.
   Returns 0 on success
*/
int WriteHuffmanHeader(STREAM *fp,HuffTable *tab,int nLit,int nDist)
{
   HuffTable lentab[19]; // len table
   int hlit, hdist, hclen, i, lensav;
   const byte order[19] =
   {
      16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
   };

   hlit = nLit < 257 ? 257 : nLit;
   hdist = nDist == 1 ? 2 : nDist;

   // initializes lentab
   for(i = 0; i < 19; i++) {
      lentab[i].code = i;
      lentab[i].len = 0;
   }

   // pass 1 scan code length
   WriteCodeLengths(fp,lentab,tab,hlit + hdist,TRUE);

   lensav = max_length;
   max_length = 7; // readjust max_length
   CalculateMinimumRedundancy(lentab,19);
   BuildHuffTable(lentab,19);
   max_length = lensav;

   stream_write_bitr(fp,1,1); // BFINAL = 1
   stream_write_bitr(fp,2,2); // BTYPE = dynamic huffman codes

   hclen = 19;

   stream_write_bitr(fp,hlit - 257,5);
   stream_write_bitr(fp,hdist ? hdist - 1 : 0,5);
   stream_write_bitr(fp,hclen - 4,4);

   // write lens
   for(i = 0; i < 19; i++)
      stream_write_bitr(fp,lentab[order[i]].len,3);

   WriteCodeLengths(fp,lentab,tab,hlit + hdist,FALSE);

   return 0;
}