home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3600 / huf.c < prev    next >
C/C++ Source or Header  |  1991-07-10  |  4KB  |  148 lines
  1. /*$Source: /usr/home/dhesi/booz/RCS/huf.c,v $*/
  2. /*$Id: huf.c,v 1.8 91/07/08 12:06:53 dhesi Exp $*/
  3. /***********************************************************
  4. Static Huffman
  5.  
  6. Adapted from "ar" archiver written by Haruhiko Okumura.
  7. ***********************************************************/
  8. #include "booz.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12.  
  13. #define NP (DICBIT + 1)
  14. #define NT (CODE_BIT + 3)
  15. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  16. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  17. #if NT > NP
  18. # define NPT NT
  19. #else
  20. # define NPT NP
  21. #endif
  22.  
  23. int decoded;        /* for use in decode.c */
  24.  
  25. ushort left[2 * NC - 1], right[2 * NC - 1];
  26. static uchar c_len[NC], pt_len[NPT];
  27. static uint  blocksize;
  28. static ushort c_table[4096], pt_table[256];
  29.  
  30. static int read_pt_len(nn, nbit, i_special)
  31. int nn;
  32. int nbit;
  33. int i_special;
  34. {
  35.    int i, c, n;
  36.    uint mask;
  37.  
  38.    n = getbits(nbit);
  39.    if (n == 0) {
  40.       c = getbits(nbit);
  41.       for (i = 0; i < nn; i++) pt_len[i] = 0;
  42.       for (i = 0; i < 256; i++) pt_table[i] = c;
  43.    } else {
  44.       i = 0;
  45.       while (i < n) {
  46.          c = bitbuf >> (BITBUFSIZ - 3);
  47.          if (c == 7) {
  48.             mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  49.             while (mask & bitbuf) {  mask >>= 1;  c++;  }
  50.          }
  51.          fillbuf((c < 7) ? 3 : c - 3);
  52.          pt_len[i++] = c;
  53.          if (i == i_special) {
  54.             c = getbits(2);
  55.             while (--c >= 0) pt_len[i++] = 0;
  56.          }
  57.       }
  58.       while (i < nn) pt_len[i++] = 0;
  59.       make_table(nn, pt_len, 8, pt_table);
  60.    }
  61. }
  62.  
  63. static int read_c_len()
  64. {
  65.    int i, c, n;
  66.    uint mask;
  67.  
  68.    n = getbits(CBIT);
  69.    if (n == 0) {
  70.       c = getbits(CBIT);
  71.       for (i = 0; i < NC; i++) c_len[i] = 0;
  72.       for (i = 0; i < 4096; i++) c_table[i] = c;
  73.    } else {
  74.       i = 0;
  75.       while (i < n) {
  76.          c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  77.          if (c >= NT) {
  78.             mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  79.             do {
  80.                if (bitbuf & mask) c = right[c];
  81.                else               c = left [c];
  82.                mask >>= 1;
  83.             } while (c >= NT);
  84.          }
  85.          fillbuf((int) pt_len[c]);
  86.          if (c <= 2) {
  87.             if      (c == 0) c = 1;
  88.             else if (c == 1) c = getbits(4) + 3;
  89.             else             c = getbits(CBIT) + 20;
  90.             while (--c >= 0) c_len[i++] = 0;
  91.          } else c_len[i++] = c - 2;
  92.       }
  93.       while (i < NC) c_len[i++] = 0;
  94.       make_table(NC, c_len, 12, c_table);
  95.    }
  96. }
  97.  
  98. uint decode_c()
  99. {
  100.     uint j, mask;
  101.  
  102.    if (blocksize == 0) {
  103.       blocksize = getbits(16);
  104.       if (blocksize == 0) {
  105.          decoded = 1;
  106.          return 0;
  107.       }
  108.       read_pt_len(NT, TBIT, 3);
  109.       read_c_len();
  110.       read_pt_len(NP, PBIT, -1);
  111.    }
  112.    blocksize--;
  113.    j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  114.    if (j >= NC) {
  115.       mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  116.       do {
  117.          if (bitbuf & mask) j = right[j];
  118.          else               j = left [j];
  119.          mask >>= 1;
  120.       } while (j >= NC);
  121.    }
  122.    fillbuf((int) c_len[j]);
  123.    return j;
  124. }
  125.  
  126. uint decode_p()
  127. {
  128.    uint j, mask;
  129.  
  130.    j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  131.    if (j >= NP) {
  132.       mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  133.       do {
  134.          if (bitbuf & mask) j = right[j];
  135.          else               j = left [j];
  136.          mask >>= 1;
  137.       } while (j >= NP);
  138.    }
  139.    fillbuf((int) pt_len[j]);
  140.    if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
  141.    return j;
  142. }
  143.  
  144. int huf_decode_start()
  145. {
  146.    init_getbits();  blocksize = 0;
  147. }
  148.