home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / arc_lbr / lhx.arc / lzhufd.c < prev    next >
C/C++ Source or Header  |  1989-04-15  |  9KB  |  386 lines
  1. /* lzhufd.c -- lzhuf decoding routines.  These are taken with minimal changes
  2.                from the usenet distribution of lzhuf.c  */
  3.  
  4. /**************************************************************
  5.     lzhuf.c
  6.     written by Haruyasu Yoshizaki 11/20/1988
  7.     some minor changes 4/6/1989
  8.     comments translated by Haruhiko Okumura 4/7/1989
  9.  
  10. **************************************************************/
  11.  
  12. static char copyright[] = "@(#)"
  13. "LZHUF.C Copyright 1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji "
  14. "Rikitake. All rights reserved. Permission granted for non-commercial use.";
  15.  
  16.  
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20. #include <ctype.h>
  21.  
  22. #include "lhx.h"
  23.  
  24.  
  25.  
  26. PRIVATE unsigned long int printcount = 0;
  27.  
  28.  
  29.  
  30. /********** LZSS compression **********/
  31.  
  32. #define N        4096    /* buffer size */
  33. #define F        60    /* lookahead buffer size */
  34. #define THRESHOLD    2
  35. #define NIL        N    /* leaf of tree */
  36.  
  37. unsigned char
  38.         text_buf[N + F - 1];
  39. int        match_position, match_length,
  40.         lson[N + 1], rson[N + 257], dad[N + 1];
  41.  
  42.  
  43. /* Huffman coding */
  44.  
  45. #define N_CHAR      (256 - THRESHOLD + F)
  46.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  47. #define T         (N_CHAR * 2 - 1)    /* size of table */
  48. #define R         (T - 1)            /* position of root */
  49. #define MAX_FREQ    0x8000        /* updates tree when the */
  50.                     /* root frequency comes to this value. */
  51. typedef unsigned char uchar;
  52.  
  53.  
  54. /* table for decoding the upper 6 bits of position */
  55.  
  56. PRIVATE uchar d_code[256] = {
  57.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  58.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  59.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  60.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  61.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  62.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  63.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  64.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  65.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  66.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  67.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  68.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  69.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  70.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  71.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  72.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  73.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  74.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  75.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  76.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  77.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  78.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  79.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  80.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  81.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  82.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  83.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  84.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  85.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  86.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  87.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  88.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  89. };
  90.  
  91. PRIVATE uchar d_len[256] = {
  92.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  93.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  94.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  95.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  96.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  97.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  98.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  99.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  100.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  101.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  102.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  103.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  104.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  105.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  106.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  107.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  108.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  109.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  110.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  111.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  112.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  113.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  114.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  115.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  116.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  117.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  118.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  119.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  120.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  121.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  122.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  123.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  124. };
  125.  
  126. PRIVATE unsigned freq[T + 1];    /* frequency table */
  127.  
  128. PRIVATE int prnt[T + N_CHAR];    /* pointers to parent nodes, except for the */
  129.             /* elements [T..T + N_CHAR - 1] which are used to get */
  130.             /* the positions of leaves corresponding to the codes. */
  131.  
  132. PRIVATE int son[T];        /* pointers to child nodes (son[], son[] + 1) */
  133.  
  134. PRIVATE int bp = 0;
  135.  
  136. PRIVATE int Bufputc(int   c)
  137. {
  138.     buffer[bp++] = (char) c;
  139.     if (bp >= BUFF_LEN) {
  140.         addbfcrc (buffer, bp);
  141.         if (outfile) {
  142.             if ( ! fwrite (buffer, bp, 1, outfile))
  143.                 return 1;
  144.         }
  145.         bp=0;
  146.     }
  147.     return 0;
  148. }
  149.  
  150.  
  151. PRIVATE int FlushBuf (void)
  152. {
  153.     if (bp > 0) {
  154.         addbfcrc (buffer, bp);
  155.         if (outfile) {
  156.             if ( ! fwrite (buffer, bp, 1, outfile))
  157.                 return 1;
  158.         }
  159.         bp=0;
  160.     }
  161.     return 0;
  162. }
  163.  
  164.  
  165. PRIVATE unsigned getbuf = 0;
  166. PRIVATE uchar getlen = 0;
  167.  
  168. PRIVATE int GetBit(void)    /* get one bit */
  169. {
  170.     int i;
  171.  
  172.     while (getlen <= 8) {
  173.         if ((i = getc(infile)) < 0) i = 0;
  174.         getbuf |= i << (8 - getlen);
  175.         getlen += 8;
  176.     }
  177.     i = getbuf;
  178.     getbuf <<= 1;
  179.     getlen--;
  180.     return (i < 0);
  181. }
  182.  
  183. PRIVATE int GetByte(void)    /* get one byte */
  184. {
  185.     unsigned i;
  186.  
  187.     while (getlen <= 8) {
  188.         if ((i = getc(infile)) < 0) i = 0;
  189.         getbuf |= i << (8 - getlen);
  190.         getlen += 8;
  191.     }
  192.     i = getbuf;
  193.     getbuf <<= 8;
  194.     getlen -= 8;
  195.     return i >> 8;
  196. }
  197.  
  198.  
  199.  
  200. /* initialization of tree */
  201.  
  202. PRIVATE void StartHuff(void)
  203. {
  204.     int i, j;
  205.  
  206.     for (i = 0; i < N_CHAR; i++) {
  207.         freq[i] = 1;
  208.         son[i] = i + T;
  209.         prnt[i + T] = i;
  210.     }
  211.     i = 0; j = N_CHAR;
  212.     while (j <= R) {
  213.         freq[j] = freq[i] + freq[i + 1];
  214.         son[j] = i;
  215.         prnt[i] = prnt[i + 1] = j;
  216.         i += 2; j++;
  217.     }
  218.     freq[T] = 0xffff;
  219.     prnt[R] = 0;
  220. }
  221.  
  222.  
  223. /* reconstruction of tree */
  224.  
  225. PRIVATE void reconst(void)
  226. {
  227.     int i, j, k;
  228.     unsigned f, l;
  229.  
  230.     /* collect leaf nodes in the first half of the table */
  231.     /* and replace the freq by (freq + 1) / 2. */
  232.     j = 0;
  233.     for (i = 0; i < T; i++) {
  234.         if (son[i] >= T) {
  235.             freq[j] = (freq[i] + 1) / 2;
  236.             son[j] = son[i];
  237.             j++;
  238.         }
  239.     }
  240.     /* begin constructing tree by connecting sons */
  241.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  242.         k = i + 1;
  243.         f = freq[j] = freq[i] + freq[k];
  244.         for (k = j - 1; f < freq[k]; k--);
  245.         k++;
  246.         l = (j - k) * 2;
  247.         memmove(&freq[k + 1], &freq[k], l);
  248.         freq[k] = f;
  249.         memmove(&son[k + 1], &son[k], l);
  250.         son[k] = i;
  251.     }
  252.     /* connect prnt */
  253.     for (i = 0; i < T; i++) {
  254.         if ((k = son[i]) >= T) {
  255.             prnt[k] = i;
  256.         } else {
  257.             prnt[k] = prnt[k + 1] = i;
  258.         }
  259.     }
  260. }
  261.  
  262.  
  263. /* increment frequency of given code by one, and update tree */
  264.  
  265. PRIVATE void update(int c)
  266. {
  267.     int i, j, k, l;
  268.  
  269.     if (freq[R] == MAX_FREQ) {
  270.         reconst();
  271.     }
  272.     c = prnt[c + T];
  273.     do {
  274.         k = ++freq[c];
  275.  
  276.         /* if the order is disturbed, exchange nodes */
  277.         if (k > freq[l = c + 1]) {
  278.             while (k > freq[++l]);
  279.             l--;
  280.             freq[c] = freq[l];
  281.             freq[l] = k;
  282.  
  283.             i = son[c];
  284.             prnt[i] = l;
  285.             if (i < T) prnt[i + 1] = l;
  286.  
  287.             j = son[l];
  288.             son[l] = i;
  289.  
  290.             prnt[j] = c;
  291.             if (j < T) prnt[j + 1] = c;
  292.             son[c] = j;
  293.  
  294.             c = l;
  295.         }
  296.     } while ((c = prnt[c]) != 0);    /* repeat up to root */
  297. }
  298.  
  299.  
  300. PRIVATE int DecodeChar(void)
  301. {
  302.     unsigned c;
  303.  
  304.     c = son[R];
  305.  
  306.     /* travel from root to leaf, */
  307.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  308.     /* the bigger (son[]+1} if 1 */
  309.     while (c < T) {
  310.         c += GetBit();
  311.         c = son[c];
  312.     }
  313.     c -= T;
  314.     update(c);
  315.     return c;
  316. }
  317.  
  318. PRIVATE int DecodePosition(void)
  319. {
  320.     unsigned i, j, c;
  321.  
  322.     /* recover upper 6 bits from table */
  323.     i = GetByte();
  324.     c = (unsigned)d_code[i] << 6;
  325.     j = d_len[i];
  326.  
  327.     /* read lower 6 bits verbatim */
  328.     j -= 2;
  329.     while (j--) {
  330.         i = (i << 1) + GetBit();
  331.     }
  332.     return c | (i & 0x3f);
  333. }
  334.  
  335.  
  336. PUBLIC int Decode()  /* recover */
  337. {
  338.     int  i, j, k, r, c;
  339.     unsigned long int  count;
  340.  
  341.     bp = 0;        /* make sure input/output buffers are empty */
  342.     getbuf = 0;
  343.     getlen = 0;
  344.     printcount = 0;
  345.  
  346.     if (textsize == 0)
  347.         return 0;
  348.     StartHuff();
  349.     for (i = 0; i < N - F; i++)
  350.         text_buf[i] = ' ';
  351.     r = N - F;
  352.     for (count = 0; count < textsize; ) {
  353.         c = DecodeChar();
  354.         if (c < 256) {
  355.             if (Bufputc(c)) {
  356.                 FlushBuf();
  357.                 return 1;
  358.             }
  359.             text_buf[r++] = (char) c;
  360.             r &= (N - 1);
  361.             count++;
  362.         } else {
  363.             i = (r - DecodePosition() - 1) & (N - 1);
  364.             j = c - 255 + THRESHOLD;
  365.             for (k = 0; k < j; k++) {
  366.                 c = text_buf[(i + k) & (N - 1)];
  367.                 if (Bufputc(c)) {
  368.                     FlushBuf();
  369.                     return 1;
  370.                 }
  371.                 text_buf[r++] = (char) c;
  372.                 r &= (N - 1);
  373.                 count++;
  374.             }
  375.         }
  376.         if (count > printcount) {
  377. /*            printf("."); */
  378.             printcount += 1024;
  379.         }
  380.     }
  381.     FlushBuf();
  382.     return 0;
  383. }
  384.  
  385.  
  386.