home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume35 / freeze / part02 / huf.c < prev    next >
C/C++ Source or Header  |  1993-02-21  |  9KB  |  453 lines
  1. #include "freeze.h"
  2. #include "huf.h"
  3. #include "bitio.h"
  4.  
  5. /*----------------------------------------------------------------------*/
  6. /*                                    */
  7. /*        HUFFMAN ENCODING                    */
  8. /*                                    */
  9. /*----------------------------------------------------------------------*/
  10.  
  11. /* TABLES OF ENCODE/DECODE for upper 6 bits position information */
  12.  
  13. /* The contents of `Table' are used for freezing only, so we use
  14.  * it freely when melting.
  15.  */
  16.  
  17. #ifndef HUFVALUES
  18. #define HUFVALUES 0,0,1,2,6,19,34,0
  19. #endif
  20.  
  21. uc_t Table2[9] = { 0, HUFVALUES };
  22.  
  23. /* d_len is really the number of bits to read to complete literal
  24.  * part of position information.
  25.  */
  26. uc_t p_len[64];        /* These arrays are built accordingly to values */
  27. uc_t d_len[256];       /* of `Table' above which are default, from the */
  28.               /* command line or from the header of frozen file */
  29. uc_t code[256];
  30.  
  31. /* use arrays of native word-size elements to improve speed */
  32.  
  33. unsigned freq[T2 + 1];          /* frequency table */
  34. int     son[T2];                /* points to son node (son[i],son[i+1]) */
  35. int     prnt[T2 + N_CHAR2];     /* points to parent node */
  36.  
  37. static  int t, r, chars;
  38.  
  39. /* notes :
  40.    prnt[Tx .. Tx + N_CHARx - 1] used by
  41.    indicates leaf position that corresponding to code.
  42. */
  43.  
  44. /* Initializes Huffman tree, bit I/O variables, etc.
  45.    Static array is initialized with `table', dynamic Huffman tree
  46.    has `n_char' leaves.
  47. */
  48.  
  49. void StartHuff (n_char)
  50.     int n_char;
  51. {
  52.     register int i, j;
  53.     t = n_char * 2 - 1;
  54.     r = t - 1;
  55.     chars = n_char;
  56.  
  57. /* A priori frequences are 1 */
  58.  
  59.     for (i = 0; i < n_char; i++) {
  60.         freq[i] = 1;
  61.         son[i] = i + t;
  62.         prnt[i + t] = i;
  63.     }
  64.     i = 0; j = n_char;
  65.  
  66. /* Building the balanced tree */
  67.  
  68.     while (j <= r) {
  69.         freq[j] = freq[i] + freq[i + 1];
  70.         son[j] = i;
  71.         prnt[i] = prnt[i + 1] = j;
  72.         i += 2; j++;
  73.     }
  74.     freq[t] = 0xffff;
  75.     prnt[r] = 0;
  76.     in_count = 1;
  77.     bytes_out = 5;
  78. #if defined(DEBUG) || defined (GATHER_STAT)
  79.     symbols_out = refers_out = 0;
  80. #endif
  81. }
  82.  
  83. /* Reconstructs tree with `chars' leaves */
  84.  
  85. void reconst ()
  86. {
  87.     register int i, j, k;
  88.     register unsigned f;
  89.  
  90. #ifdef DEBUG
  91.     if (quiet < 0)
  92.       fprintf(stderr,
  93.         "Reconstructing Huffman tree: symbols: %ld, references: %ld\n",
  94.         symbols_out, refers_out);
  95. #endif
  96.  
  97. /* correct leaf node into of first half,
  98.    and set these freqency to (freq+1)/2
  99. */
  100.     j = 0;
  101.     for (i = 0; i < t; i++) {
  102.         if (son[i] >= t) {
  103.             freq[j] = (freq[i] + 1) / 2;
  104.             son[j] = son[i];
  105.             j++;
  106.         }
  107.     }
  108. /* Build tree.  Link sons first */
  109.  
  110.     for (i = 0, j = chars; j < t; i += 2, j++) {
  111.         k = i + 1;
  112.         f = freq[j] = freq[i] + freq[k];
  113.         for (k = j - 1; f < freq[k]; k--);
  114.         k++;
  115.         {       register unsigned *p, *e;
  116.             for (p = &freq[j], e = &freq[k]; p > e; p--)
  117.                 p[0] = p[-1];
  118.             freq[k] = f;
  119.         }
  120.         {       register int *p, *e;
  121.             for (p = &son[j], e = &son[k]; p > e; p--)
  122.                 p[0] = p[-1];
  123.             son[k] = i;
  124.         }
  125.     }
  126.  
  127. /* Link parents */
  128.     for (i = 0; i < t; i++) {
  129.         if ((k = son[i]) >= t) {
  130.             prnt[k] = i;
  131.         } else {
  132.             prnt[k] = prnt[k + 1] = i;
  133.         }
  134.     }
  135. }
  136.  
  137.  
  138. /* Updates given code's frequency, and updates tree */
  139.  
  140. void update (c)
  141.     register int c;
  142. {
  143.     register unsigned k, *p;
  144.     register int    i, j, l;
  145.  
  146.     if (freq[r] == MAX_FREQ) {
  147.         reconst();
  148.     }
  149.     c = prnt[c + t];
  150.     do {
  151.         k = ++freq[c];
  152.  
  153.         /* swap nodes when become wrong frequency order. */
  154.         if (k > freq[l = c + 1]) {
  155.             for (p = freq+l+1; k > *p++; ) ;
  156.             l = p - freq - 2;
  157.             freq[c] = p[-2];
  158.             p[-2] = k;
  159.  
  160.             i = son[c];
  161.             prnt[i] = l;
  162.             if (i < t) prnt[i + 1] = l;
  163.  
  164.             j = son[l];
  165.             son[l] = i;
  166.  
  167.             prnt[j] = c;
  168.             if (j < t) prnt[j + 1] = c;
  169.             son[c] = j;
  170.  
  171.             c = l;
  172.         }
  173.     } while ((c = prnt[c]) != 0);    /* loop until reach to root */
  174. }
  175.  
  176. /* Encodes the literal or the length information */
  177.  
  178. void EncodeChar (c)
  179.     int c;
  180. {
  181.     register int k, len = 0;
  182.     register unsigned hcode = 0;
  183. #ifdef INT_16_BITS
  184.     register unsigned hcode2 = 0;
  185. #endif
  186.     DefBits;
  187.  
  188.     k = prnt[c + t];
  189.  
  190. /* trace links from leaf node to root */
  191.     do {
  192. /* if node index is odd, trace larger of sons */
  193. #ifdef INT_16_BITS
  194.         if (len < 16) {
  195. #endif
  196.             hcode |= (unsigned) (k & 1) << len;
  197. #ifdef INT_16_BITS
  198.         } else {
  199.             hcode2 |= (unsigned) (k & 1) << len;
  200.         }
  201. #endif
  202.         len++;
  203.     } while ((k = prnt[k]) != r);
  204.  
  205. #ifdef INT_16_BITS
  206.     if (len > 16) {
  207.         PutNLowBits(hcode2, len - 16);
  208.         FlushBits();
  209.         PutNLowBits(hcode >> 8, 8);
  210.         FlushBits();
  211.         hcode &= 0xFF;
  212.         len = 8;
  213.     } else if (len > 8) {
  214.         PutNLowBits(hcode >> 8, len - 8);
  215.         FlushBits();
  216.         hcode &= 0xFF;
  217.         len = 8;
  218.     }
  219. #endif
  220.     PutNLowBits(hcode, len);
  221.     FlushBits();
  222.     KeepBits();
  223.     if (ferror(stdout))
  224.         writeerr();
  225.     update(c);
  226. }
  227.  
  228. /* Encodes the position information */
  229.  
  230. void EncodePosition (c)
  231.     register int c;
  232. {
  233.     DefBits;
  234.     /* output upper 6 bit from table */
  235.     PutNLowBits(code[c >> 7], p_len[c >> 7]);
  236. #ifdef INT_16_BITS
  237.     FlushBits();
  238. #endif
  239.     /* output lower 7 bit */
  240.     PutNLowBits(c & 0x7f, 7);
  241.     FlushBits();
  242.     KeepBits();
  243. }
  244.  
  245. /* Decodes the literal or length info and returns its value.
  246.     Returns ENDOF, if the file is corrupt.
  247. */
  248.  
  249. int DecodeChar ()
  250. {
  251.     register int c = r;
  252.     DefBits;
  253.  
  254.     if (overrun >= sizeof(bitbuf)) {
  255.         crpt_message();
  256.         return ENDOF;
  257.     }
  258.     /* As far as MAX_FREQ == 32768, maximum length of a Huffman
  259.      * code cannot exceed 23 (consider Fibonacci numbers),
  260.      * so we don't need additional FillBits while decoding
  261.      * if sizeof(int) == 4.
  262.      */
  263.     FillBits();
  264.     /* trace from root to leaf,
  265.        got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
  266.  
  267.     while ((c = son[c]) < t) {
  268.         c += GetBit();
  269. #ifdef INT_16_BITS
  270.         if (loclen == 0)
  271.             FillBits();
  272. #endif
  273.     }
  274.     KeepBits();
  275.     update(c -= t);
  276.     return c;
  277. }
  278.  
  279. /* Decodes the position info and returns it */
  280.  
  281. int DecodePosition ()
  282. {
  283.     register        i, j;
  284.     DefBits;
  285.  
  286.     /* Upper 6 bits can be coded by a byte (8 bits) or less,
  287.      * plus 7 bits literally ...
  288.      */
  289.     FillBits();
  290.     /* decode upper 6 bits from the table */
  291.     i = GetByte();
  292.     j = (code[i] << 7) | (i << d_len[i]) & 0x7F;
  293.  
  294.     /* get lower 7 bits literally */
  295. #ifdef INT_16_BITS
  296.     FillBits();
  297. #endif
  298.     j |= GetNBits(d_len[i]);
  299.     KeepBits();
  300.     return j;
  301. }
  302.  
  303. #ifdef COMPAT
  304.  
  305. uc_t Table1[9] = { 0, 0, 0, 1, 3, 8, 12, 24, 16 };
  306.  
  307. /* Old version of a routine above for handling files made by
  308.     the 1st version of Freeze.
  309. */
  310.  
  311. short DecodePOld ()
  312. {
  313.     register        i, j;
  314.     DefBits;
  315.  
  316.     FillBits();
  317.     i = GetByte();
  318.     j = (code[i] << 6) | (i << d_len[i]) & 0x3F;
  319. #ifdef INT_16_BITS
  320.     FillBits();
  321. #endif
  322.     j |= GetNBits(d_len[i]);
  323.     KeepBits();
  324.     return j;
  325. }
  326. #endif
  327.  
  328. /* Initializes static Huffman arrays */
  329.  
  330. void init(table) uc_t * table; {
  331.     short i, j, k, num;
  332.     num = 0;
  333.  
  334. /* There are `table[i]' `i'-bits Huffman codes */
  335.  
  336.     for(i = 1, j = 0; i <= 8; i++) {
  337.         num += table[i] << (8 - i);
  338.         for(k = table[i]; k; j++, k--)
  339.             p_len[j] = i;
  340.     }
  341.     if (num != 256) {
  342.         fprintf(stderr, "Invalid position table\n");
  343.         exit(1);
  344.     }
  345.     num = j;
  346.     if (do_melt == 0)
  347.  
  348. /* Freezing: building the table for encoding */
  349.  
  350.         for(i = j = 0;;) {
  351.             code[j] = i;
  352.             i++;
  353.             j++;
  354.             if (j == num) break;
  355.             i <<= p_len[j] - p_len[j-1];
  356.         }
  357.     else {
  358.  
  359. /* Melting: building the table for decoding */
  360.  
  361.         for(k = j = 0; j < num; j ++)
  362.             for(i = 1 << (8 - p_len[j]); i--;)
  363.                 code[k++] = j;
  364.  
  365.         for(k = j = 0; j < num; j ++)
  366.             for(i = 1 << (8 - p_len[j]); i--;)
  367.                 d_len[k++] =  p_len[j] - 1
  368. #ifdef COMPAT
  369.                 - (table == Table1)
  370. #endif
  371.                             ;
  372.     }
  373. }
  374.  
  375. /* Writes a 3-byte header into the frozen form of file; Table[7] and
  376.     Table[8] aren't necessary, see `read_header'.
  377. */
  378.  
  379. void write_header() {
  380.     unsigned i;
  381.  
  382.     i = Table2[5] & 0x1F; i <<= 4;
  383.     i |= Table2[4] & 0xF; i <<= 3;
  384.     i |= Table2[3] & 7;   i <<= 2;
  385.     i |= Table2[2] & 3;   i <<= 1;
  386.     i |= Table2[1] & 1;
  387.  
  388.     putchar((int)(i & 0xFF));
  389.     putchar((int)((i >> 8)));
  390.     putchar((int)(Table2[6] & 0x3F));
  391.     if (ferror(stdout))
  392.         writeerr();
  393. }
  394.  
  395. /* Reconstructs `Table' from the header of the frozen file and checks
  396.     its correctness. Returns 0 if OK, EOF otherwise.
  397. */
  398.  
  399. int read_header() {
  400.     int i, j;
  401.     i = getchar() & 0xFF;
  402.     i |= (getchar() & 0xFF) << 8;
  403.     Table2[1] = i & 1; i >>= 1;
  404.     Table2[2] = i & 3; i >>= 2;
  405.     Table2[3] = i & 7; i >>= 3;
  406.     Table2[4] = i & 0xF; i >>= 4;
  407.     Table2[5] = i & 0x1F; i >>= 5;
  408.  
  409.     if (i & 1 || (i = getchar()) & 0xC0) {
  410.         fprintf(stderr, "Unknown header format.\n");
  411.         crpt_message();
  412.         return EOF;
  413.     }
  414.  
  415.     Table2[6] = i & 0x3F;
  416.  
  417.     i = Table2[1] + Table2[2] + Table2[3] + Table2[4] +
  418.     Table2[5] + Table2[6];
  419.  
  420.     i = 62 - i;     /* free variable length codes for 7 & 8 bits */
  421.  
  422.     j = 128 * Table2[1] + 64 * Table2[2] + 32 * Table2[3] +
  423.     16 * Table2[4] + 8 * Table2[5] + 4 * Table2[6];
  424.  
  425.     j = 256 - j;    /* free byte images for these codes */
  426.  
  427. /*      Equation:
  428.         Table[7] + Table[8] = i
  429.     2 * Table[7] + Table[8] = j
  430. */
  431.     j -= i;
  432.     if (j < 0 || i < j) {
  433.         crpt_message();
  434.         return EOF;
  435.     }
  436.     Table2[7] = j;
  437.     Table2[8] = i - j;
  438.  
  439. #ifdef DEBUG
  440.     fprintf(stderr, "Codes: %d %d %d %d %d %d %d %d\n",
  441.         Table2[1], Table2[2], Table2[3], Table2[4],
  442.         Table2[5], Table2[6], Table2[7], Table2[8]);
  443. #endif
  444.     return 0;
  445. }
  446.  
  447. /* File too short or invalid header, print a message */
  448. void crpt_message ( )
  449. {
  450.     fprintf ( stderr, "melt: corrupt input\n" );
  451. }
  452.  
  453.