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