home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_progs / fileutil / scan.lha / src / lzhuf.c < prev    next >
C/C++ Source or Header  |  1992-05-21  |  17KB  |  533 lines
  1. /*----------------------------------------------------------------------*/
  2. /*              LHarc Encoding/Decoding module                          */
  3. /*                                                                      */
  4. /*      LZSS Algorithm                  Haruhiko.Okumura                */
  5. /*      Adaptic Huffman Encoding        1989.05.27  Haruyasu.Yoshizaki  */
  6. /*                                                                      */
  7. /*----------------------------------------------------------------------*/
  8.  
  9. #include <stdio.h>
  10. #include "lhio.h"
  11.  
  12. extern int      NotInterruptedCall;
  13. extern int      ForceReturn;
  14. static FILE     *infile, *outfile;
  15. static long     textsize, codesize;
  16. static int      PutNum;
  17.  
  18. long            count; /* number of bytes decoded at present time */
  19.  
  20. #define SETUP_GETC_CRC(fp)      crc_infile = fp
  21. #define PUTC_CRC(c)             putc_crc(c)
  22. #define GETC_CRC()              getc_crc()
  23. #define END_PUTC_CRC()
  24. #define END_GETC_CRC()
  25.  
  26. /*----------------------------------------------------------------------*/
  27. /*                                                                      */
  28. /*              LZSS ENCODING                                           */
  29. /*                                                                      */
  30. /*----------------------------------------------------------------------*/
  31.  
  32. #define N       4096    /* buffer size */
  33. #define F               60      /* pre-sence buffer size */
  34. #define THRESHOLD       2
  35. #define NIL             N       /* term of tree */
  36.  
  37. static unsigned char    text_buf[N + F - 1];
  38. static unsigned int     match_position, match_length;
  39. static int              lson[N + 1], rson[N + 1 + N], dad[N + 1];
  40. static unsigned char    same[N + 1];
  41.  
  42.  
  43. /*----------------------------------------------------------------------*/
  44. /*                                                                      */
  45. /*              HUFFMAN ENCODING                                        */
  46. /*                                                                      */
  47. /*----------------------------------------------------------------------*/
  48.  
  49. #define N_CHAR          (256 - THRESHOLD + F) /* {code : 0 .. N_CHAR-1} */
  50. #define T               (N_CHAR * 2 - 1)        /* size of table */
  51. #define R               (T - 1)                 /* root position */
  52. #define MAX_FREQ        0x8000  /* tree update timing from frequency */
  53.  
  54. typedef unsigned char uchar;
  55.  
  56. /* TABLE OF DECODE for upper 6bits position information */
  57.  
  58. /* for decode */
  59. static uchar d_code[256] = {
  60.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  61.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  62.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  63.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  64.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  65.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  66.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  67.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  68.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  69.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  70.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  71.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  72.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  73.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  74.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  75.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  76.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  77.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  78.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  79.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  80.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  81.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  82.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  83.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  84.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  85.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  86.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  87.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  88.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  89.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  90.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  91.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  92. };
  93.  
  94. static uchar d_len[256] = {
  95.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  96.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  97.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  98.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  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.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  103.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  104.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  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.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  111.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  112.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  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.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  117.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  118.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  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.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  123.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  124.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  125.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  126.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  127. };
  128.  
  129. static unsigned freq[T + 1];    /* frequency table */
  130.  
  131. static int prnt[T + N_CHAR];    /* points to parent node */
  132. /* notes :
  133.    prnt[T .. T + N_CHAR - 1] used by
  134.    indicates leaf position that corresponding to code */
  135.  
  136. static int son[T];              /* points to son node (son[i],son[i+]) */
  137.  
  138. static unsigned getbuf = 0;
  139. static uchar getlen = 0;
  140.  
  141.  
  142. /* get one bit */
  143. /* returning in Bit 0 */
  144. static int GetBit ()
  145. {
  146.         register unsigned int dx = getbuf;
  147.         register unsigned int c;
  148.  
  149.         if (getlen <= 8)
  150.                 {
  151.                         c = getc (infile);
  152.                         if ((int)c < 0) c = 0;
  153.                         dx |= c << (8 - getlen);
  154.                         getlen += 8;
  155.                 }
  156.         getbuf = dx << 1;
  157.         getlen--;
  158.         return (dx & 0x8000) ? 1 : 0;
  159. }
  160.  
  161. /* get one byte */
  162. /* returning in Bit7...0 */
  163. static int GetByte ()
  164. {
  165.         register unsigned int dx = getbuf;
  166.         register unsigned c;
  167.  
  168.         if (getlen <= 8) {
  169.                 c = getc (infile);
  170.                 if ((int)c < 0) c = 0;
  171.                 dx |= c << (8 - getlen);
  172.                 getlen += 8;
  173.         }
  174.         getbuf = dx << 8;
  175.         getlen -= 8;
  176.         return (dx >> 8) & 0xff;
  177. }
  178.  
  179. /* get N bit */
  180. /* returning in Bit(N-1)...Bit 0 */
  181. static int GetNBits (n)
  182.         register unsigned int n;
  183. {
  184.         register unsigned int dx = getbuf;
  185.         register unsigned int c;
  186.         static int mask[17] = {
  187.                 0x0000,
  188.                 0x0001, 0x0003, 0x0007, 0x000f,
  189.                 0x001f, 0x003f, 0x007f, 0x00ff,
  190.                 0x01ff, 0x03ff, 0x07ff, 0x0fff,
  191.                 0x1fff, 0x3fff, 0x0fff, 0xffff };
  192.         static int shift[17] = {
  193.                 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
  194.  
  195.         if (getlen <= 8)
  196.                 {
  197.                         c = getc (infile);
  198.                         if ((int)c < 0) c = 0;
  199.                         dx |= c << (8 - getlen);
  200.                         getlen += 8;
  201.                 }
  202.         getbuf = dx << n;
  203.         getlen -= n;
  204.         return (dx >> shift[n]) & mask[n];
  205. }
  206.  
  207. /* Initialize tree */
  208.  
  209. static StartHuff ()
  210. {
  211.         register int i, j;
  212.  
  213.         for (i = 0; i < N_CHAR; i++) {
  214.                 freq[i] = 1;
  215.                 son[i] = i + T;
  216.                 prnt[i + T] = i;
  217.         }
  218.         i = 0; j = N_CHAR;
  219.         while (j <= R) {
  220.                 freq[j] = freq[i] + freq[i + 1];
  221.                 son[j] = i;
  222.                 prnt[i] = prnt[i + 1] = j;
  223.                 i += 2; j++;
  224.         }
  225.         freq[T] = 0xffff;
  226.         prnt[R] = 0;
  227.         getlen = 0;
  228.         getbuf = 0;
  229. }
  230.  
  231.  
  232. /* reconstruct tree */
  233. static reconst ()
  234. {
  235.         register int i, j, k;
  236.         register unsigned f;
  237.  
  238.         /* correct leaf node into of first half,
  239.            and set these freqency to (freq+1)/2       */
  240.         j = 0;
  241.         for (i = 0; i < T; i++) {
  242.                 if (son[i] >= T) {
  243.                         freq[j] = (freq[i] + 1) / 2;
  244.                         son[j] = son[i];
  245.                         j++;
  246.                 }
  247.         }
  248.         /* build tree.  Link sons first */
  249.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  250.                 k = i + 1;
  251.                 f = freq[j] = freq[i] + freq[k];
  252.                 for (k = j - 1; f < freq[k]; k--);
  253.                 k++;
  254.                 {       register unsigned *p, *e;
  255.                         for (p = &freq[j], e = &freq[k]; p > e; p--)
  256.                                 p[0] = p[-1];
  257.                         freq[k] = f;
  258.                 }
  259.                 {       register int *p, *e;
  260.                         for (p = &son[j], e = &son[k]; p > e; p--)
  261.                                 p[0] = p[-1];
  262.                         son[k] = i;
  263.                 }
  264.         }
  265.         /* link parents */
  266.         for (i = 0; i < T; i++) {
  267.                 if ((k = son[i]) >= T) {
  268.                         prnt[k] = i;
  269.                 } else {
  270.                         prnt[k] = prnt[k + 1] = i;
  271.                 }
  272.         }
  273. }
  274.  
  275.  
  276. /* update given code's frequency, and update tree */
  277.  
  278. static update (c)
  279.         unsigned int    c;
  280. {
  281.         register unsigned *p;
  282.         register int i, j, k, l;
  283.  
  284.         if (freq[R] == MAX_FREQ) {
  285.                 reconst();
  286.         }
  287.         c = prnt[c + T];
  288.         do {
  289.                 k = ++freq[c];
  290.  
  291.                 /* swap nodes when become wrong frequency order. */
  292.                 if (k > freq[l = c + 1]) {
  293.                         for (p = freq+l+1; k > *p++; ) ;
  294.                         l = p - freq - 2;
  295.                         freq[c] = p[-2];
  296.                         p[-2] = k;
  297.  
  298.                         i = son[c];
  299.                         prnt[i] = l;
  300.                         if (i < T) prnt[i + 1] = l;
  301.  
  302.                         j = son[l];
  303.                         son[l] = i;
  304.  
  305.                         prnt[j] = c;
  306.                         if (j < T) prnt[j + 1] = c;
  307.                         son[c] = j;
  308.  
  309.                         c = l;
  310.                 }
  311.         } while ((c = prnt[c]) != 0);   /* loop until reach to root */
  312. }
  313.  
  314. /* static unsigned code, len; */
  315.  
  316. static int DecodeChar ()
  317. {
  318.         register unsigned c;
  319.  
  320.         c = son[R];
  321.  
  322.         /* trace from root to leaf,
  323.            got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
  324.         while (c < T) {
  325.                 c += GetBit();
  326.                 c = son[c];
  327.         }
  328.         c -= T;
  329.         update(c);
  330.         return c;
  331. }
  332.  
  333. static int DecodePosition ()
  334. {
  335.         unsigned i, j, c;
  336.  
  337.         /* decode upper 6bit from table */
  338.         i = GetByte();
  339.         c = (unsigned)d_code[i] << 6;
  340.         j = d_len[i];
  341.  
  342.         /* get lower 6bit */
  343.         j -= 2;
  344.         return c | (((i << j) | GetNBits (j)) & 0x3f);
  345. }
  346.  
  347.  
  348. static Decode ()
  349. {
  350.         static int    i, j, k, r, c;
  351.  
  352.         if( NotInterruptedCall ) {
  353.            StartHuff();
  354.            for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  355.            r = N - F;
  356.            count = 0;
  357.         }
  358.         else {
  359.            NotInterruptedCall = 1;
  360.            if( PutNum ) {
  361.               /* Note: cannot use Manx -sf optimization here */
  362.               for ( ; k < j; k++) {
  363.                  c = text_buf[(i + k) & (N - 1)];
  364.                  PUTC_CRC (c);
  365.                  text_buf[r++] = c;
  366.                  r &= (N - 1);
  367.                  count++;
  368.                  if( ForceReturn ) {
  369.                     k++;
  370.                     if( count >= textsize && k >= j ) ForceReturn = 0;
  371.                     PutNum = 1;
  372.                     return;
  373.                  }
  374.               }
  375.            }
  376.         }
  377.         /* Note: cannot use Manx -sf optimization here */
  378.         for ( ; count < textsize; ) {
  379.            c = DecodeChar();
  380.            if (c < 256) {
  381.               PUTC_CRC (c);
  382.               text_buf[r++] = c;
  383.               r &= (N - 1);
  384.               count++;
  385.               if( ForceReturn ) {
  386.                  if( count >= textsize ) ForceReturn = 0;
  387.                  PutNum = 0;
  388.                  return;
  389.               }
  390.            } else {
  391.               i = (r - DecodePosition() - 1) & (N - 1);
  392.               j = c - 255 + THRESHOLD;
  393.               for (k = 0; k < j; k++) {
  394.                  c = text_buf[(i + k) & (N - 1)];
  395.                  PUTC_CRC (c);
  396.                  text_buf[r++] = c;
  397.                  r &= (N - 1);
  398.                  count++;
  399.                  if( ForceReturn ) {
  400.                     k++;
  401.                     if( count >= textsize && k >= j ) ForceReturn = 0;
  402.                     PutNum = 1;
  403.                     return;
  404.                  }
  405.               }
  406.            }
  407.         }
  408.         END_PUTC_CRC ();
  409. }
  410.  
  411.  
  412. /*----------------------------------------------------------------------*/
  413. /*                                                                      */
  414. /*              LARC                                                    */
  415. /*                                                                      */
  416. /*----------------------------------------------------------------------*/
  417.  
  418. #define F_OLD   18      /* look ahead buffer size for LArc */
  419.  
  420. /* intialize buffer for LArc type 5 */
  421. static InitBuf ()
  422. {
  423.         register unsigned char *p = text_buf;
  424.         register int i, j;
  425.         for (i = 0; i < 256; i ++)
  426.                 for (j = 0; j < 13; j ++)
  427.                         *p ++ = i;
  428.         for (i = 0; i < 256; i ++)
  429.                 *p ++ = i;
  430.         for (i = 0; i < 256; i ++)
  431.                 *p ++ = 255 - i;
  432.         for (i = 0; i < 128; i ++)
  433.                 *p ++ = 0;
  434.         for (i = 0; i < 128; i ++)
  435.                 *p ++ = 0x20;
  436. }
  437.  
  438. /* Decode LArc type 5 */
  439. static DecodeOld ()
  440. {
  441.         static int si, di;
  442.         static int     dl, dh, al, cx;
  443.  
  444.         if( NotInterruptedCall ) {
  445.            if (textsize == 0) return;
  446.            InitBuf ();
  447.            di = N - F_OLD;
  448.            dl = 0x80;
  449.            count = 0;
  450.         }
  451.         else {
  452.            NotInterruptedCall = 1;
  453.            if( PutNum ) {
  454.               do {
  455.                  text_buf[di] = al = text_buf[si];
  456.                  PUTC_CRC (al);
  457.                  si = (si + 1) & (N - 1);
  458.                  di = (di + 1) & (N - 1);
  459.                  if( ForceReturn ) {
  460.                     if( count >= textsize && cx == 1 ) ForceReturn = 0;
  461.                     PutNum = 1;
  462.                     return;
  463.                  }
  464.               } while (--cx != 0) ;
  465.            }
  466.         }
  467.  
  468.         for ( ; count < textsize; ) {
  469.            dl = ((dl << 1) | (dl >> 7)) & 0xff;
  470.            if (dl & 0x01) dh = getc (infile);
  471.            al = getc (infile);
  472.            if ((dh & dl) != 0) {
  473.               PUTC_CRC (al);
  474.               text_buf[di] = al;
  475.               di = (di + 1) & (N - 1);
  476.               count ++;
  477.               if( ForceReturn ) {
  478.                  if( count >= textsize ) ForceReturn = 0;
  479.                  PutNum = 0;
  480.                  return;
  481.               }
  482.            } else {
  483.               cx = getc (infile);
  484.               si = (al & 0x00ff) | ((cx << 4) & 0x0f00);
  485.               cx = (cx & 0x000f) + 3;
  486.               count += cx;
  487.               do {
  488.                  text_buf[di] = al = text_buf[si];
  489.                  PUTC_CRC (al);
  490.                  si = (si + 1) & (N - 1);
  491.                  di = (di + 1) & (N - 1);
  492.                  if( ForceReturn ) {
  493.                     if( count >= textsize && cx == 1 ) ForceReturn = 0;
  494.                     PutNum = 1;
  495.                     return;
  496.                  }
  497.               } while (--cx != 0) ;
  498.            }
  499.  
  500.         }
  501.         END_PUTC_CRC ();
  502. }
  503.  
  504.  
  505. int decode_lzhuf (infp, original_size, name)
  506.         FILE *infp;
  507.         long original_size;
  508.         char *name;
  509. {
  510.         if( NotInterruptedCall ) {
  511.            infile = infp;
  512.            textsize = original_size;
  513.            init_crc ();
  514.         }
  515.         Decode ();
  516.         return crc_value;
  517. }
  518.  
  519.  
  520. int decode_larc (infp, original_size, name)
  521.         FILE *infp;
  522.         long original_size;
  523.         char *name;
  524. {
  525.         if( NotInterruptedCall ) {
  526.            infile = infp;
  527.            textsize = original_size;
  528.            init_crc ();
  529.         }
  530.         DecodeOld ();
  531.         return crc_value;
  532. }
  533.