home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c019 / 1.ddi / FLZH_RN / FLZH_RN.C
Encoding:
C/C++ Source or Header  |  1989-05-24  |  28.0 KB  |  869 lines
  1. /*
  2. Posting-number: Volume 02, Issue 098
  3. Submitted-by: Russ Nelson <nelson@sun.soe.clarkson.edu>
  4. Archive-name: flzh/flzh_rn.c
  5. */
  6. /*
  7. Here is another text posting.  It speaks for itself.  Just in case
  8. others come up with further revisions, I have named this one
  9. "flzh_rn.c" after "Faster LZHuf by Russ Nelson".   Note that I have
  10. added the copyright statement as requested by Kenji Rikitake in an
  11. earlier Usenet article.  There seems to be a compiler dependency here,
  12. because it won't execute correctly if compiled with Turbo C 1.0, but
  13. Russ Nelson tells me it does work with later versions of Turbo C,
  14. 1.5 or 2, but I don't remember which.  -- R.D
  15. */
  16.  
  17. #ifdef USE_ASM
  18. #pragma inline
  19. #endif
  20.  
  21. /*
  22. LZHUF.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
  23. All rights reserved. Permission granted for non-commercial use.
  24. */
  25.  
  26. /*
  27.  * LZHUF.C English version 1.0
  28.  * Based on Japanese version 29-NOV-1988
  29.  * LZSS coded by Haruhiko OKUMURA
  30.  * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI
  31.  * Edited and translated to English by Kenji RIKITAKE
  32.  * Assembly language added by Russell Nelson (nelson@clutx.clarkson.edu)
  33.  *   Makes it 1.56 times faster in compression,
  34.  *   and 1.53 times faster in decompression.
  35.  * Warning!  If you change anything, verify that the register use doesn't
  36.  * change.
  37.  * Some C optimization added by Russell Nelson.
  38.  */
  39.  
  40. #include <stdio.h>
  41. #include <stdlib.h>
  42. #include <string.h>
  43. #include <ctype.h>
  44.  
  45. /* These values are Turbo-C dependent;
  46.    EXIT_SUCCESS, EXIT_FAILURE
  47.    renamed by Kenji */
  48.  
  49. #define EXIT_OK 0
  50. #define EXIT_FAILED -1
  51.  
  52. FILE  *infile, *outfile;
  53. unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  54.  
  55. void Error(char *message)
  56. {
  57.         printf("\n%s\n", message);
  58.         exit(EXIT_FAILED);
  59. }
  60.  
  61. /* LZSS Parameters */
  62.  
  63. #define N               4096    /* Size of string buffer */
  64. #define F               60      /* Size of look-ahead buffer */
  65. #define THRESHOLD       2
  66. #define NIL             N       /* End of tree's node  */
  67.  
  68. unsigned char
  69.                 text_buf[N + F - 1];
  70. int             match_position, match_length,
  71.                 lson[N + 1], rson[N + 257], dad[N + 1];
  72.  
  73. void InitTree(void)  /* Initializing tree */
  74. {
  75.         int  i;
  76.  
  77.         for (i = N + 1; i <= N + 256; i++)
  78.                 rson[i] = NIL;                  /* root */
  79.         for (i = 0; i < N; i++)
  80.                 dad[i] = NIL;                   /* node */
  81. }
  82.  
  83. void InsertNode(int r)  /* Inserting node to the tree */
  84. {
  85.         int  i, p, cmp;
  86.         unsigned char  *key, keychar;
  87.         unsigned c;
  88.  
  89.         cmp = 1;
  90.         key = &text_buf[r];
  91.         keychar = key[1];
  92.         p = N + 1 + key[0];
  93.         rson[r] = lson[r] = NIL;
  94.         match_length = 0;
  95.  
  96. #ifdef USE_ASM
  97.  
  98. /* for speed's sake, we use a bunch of hacks.  If you change this code, be
  99.  * sure to tcc -S it before you attempt to run it.  If you can't figure
  100.  * out what something's doing, look at the standard C version of it in the
  101.  * #else clause.
  102.  */
  103.  
  104. #define SF 0x1000                       /* 8086 sign flag */
  105.  
  106. /* We're going to hold p in _SI.  Turbo C would ordinarily put it in a
  107.  * register for us, but it refuses to do so if it sees any mention of
  108.  * the register, either in a 'asm' statement or the _SI pseudovariable.
  109.  * When we actually use _SI, we push it first.
  110.  *
  111.  * Similarly for r in _DI.  Note that the algorithm doesn't change r.
  112.  */
  113.  
  114.         _SI = p;
  115. #define p _SI
  116.         _DI = r;
  117. #define r _DI
  118.  
  119.         _ES = _DS;                      /* we're going to use cmpsb */
  120.         asm cld
  121.  
  122. /* many times the initial characters don't match, so we spend a fair amount
  123.  * of time in the following unstructured code.
  124.  */
  125.  
  126.         for ( ; ; ) {
  127.                 if ((cmp & SF) == 0) {
  128. right:
  129.                         asm mov bx,si
  130.                         asm mov ax,rson[bx+si]
  131.                         if (_AX != NIL) {
  132.                                 asm mov si,ax;
  133.                                 asm mov al,text_buf[si+1];
  134.                                 asm cmp keychar,al;
  135.                                 asm jg right;
  136.                                 asm jl left;
  137.                         } else {
  138.                                 rson[p] = r;
  139.                                 dad[r] = p;
  140.                                 return;
  141.                         }
  142.                 } else {
  143. left:
  144.                         asm mov bx,si
  145.                         asm mov ax,lson[bx+si]
  146.                         if (_AX != NIL) {
  147.                                 asm mov si,ax;
  148.                                 asm mov al,text_buf[si+1];
  149.                                 asm cmp keychar,al;
  150.                                 asm jg right;
  151.                                 asm jl left;
  152.                         } else {
  153.                                 lson[p] = r;
  154.                                 dad[r] = p;
  155.                                 return;
  156.                         }
  157.                 }
  158. equal:
  159.                 asm push si
  160.                 asm push di
  161.                 _DI = (unsigned) &text_buf[p+1];
  162.                 _SI = (unsigned) &key[1];
  163.                 _CX = F - 1;
  164. /* The semantics of cmpsb are not well understood.  Every comparison decrements
  165.  * _CX and bumps _SI and _DI.  If the values compared are equal and _CX <> 0
  166.  * then the cmpsb repeats.  Otherwise the flags are set to the result of the
  167.  * comparison.  The consequence of this is that the only way to determine
  168.  * whether the entire string was equal is to check the flags.  If the two
  169.  * strings are identical up to the last character, _CX will be zero
  170.  * whether or not the last characters match.
  171.  *
  172.  * The Microsoft Macro Assembler 5.0 Reference Booklet gets it wrong, even
  173.  * though Intel documents it very precisely and accurately.  Boo!  Hiss!
  174.  *
  175.  * If _CX is zero before the cmpsb, the flags are unchanged.  This affects
  176.  * the interpretation of zero length strings.  Are they equal or different?
  177.  * If you wish them to be equal, you can "or cx,cx".  If you wish them to
  178.  * be different you can "or sp,sp".  In a subroutine, sp is guaranteed to
  179.  * be nonzero.
  180.  */
  181.                 asm     repe cmpsb      /* 7% of runtime is spent here! */
  182. /* remember the sign flag to see if it was larger or smaller */
  183.                 asm lahf
  184.                 cmp = _AX;
  185. /* if it matched, we want _CX to be zero */
  186.                 asm je matched;
  187.                 _CX++;
  188. matched:
  189.                 i = F - _CX;
  190.                 asm pop di;
  191.                 asm pop si;
  192.                 if (i > THRESHOLD) {
  193.                         if (i > match_length) {
  194.                                 match_position = ((r - p) & (N - 1)) - 1;
  195.                                 if ((match_length = i) >= F)
  196.                                         break;
  197.                         }
  198.                         if (i == match_length) {
  199.                                 if (((r - p) & (N - 1)) - 1 < match_position) {
  200.                                         match_position = _AX;
  201.                                 }
  202.                         }
  203.                 }
  204.         }
  205. #else
  206.         for ( ; ; ) {
  207.                 if (cmp >= 0) {
  208.                         if (rson[p] != NIL)
  209.                                 p = rson[p];
  210.                         else {
  211.                                 rson[p] = r;
  212.                                 dad[r] = p;
  213.                                 return;
  214.                         }
  215.                 } else {
  216.                         if (lson[p] != NIL)
  217.                                 p = lson[p];
  218.                         else {
  219.                                 lson[p] = r;
  220.                                 dad[r] = p;
  221.                                 return;
  222.                         }
  223.                 }
  224.                 for (i = 1; i < F; i++)
  225.                         if ((cmp = key[i] - text_buf[p + i]) != 0)
  226.                                 break;
  227.                 if (i > THRESHOLD) {
  228.                         if (i > match_length) {
  229.                                 match_position = ((r - p) & (N - 1)) - 1;
  230.                                 if ((match_length = i) >= F)
  231.                                         break;
  232.                         }
  233.                         if (i == match_length) {
  234.                                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  235.                                         match_position = c;
  236.                                 }
  237.                         }
  238.                 }
  239.         }
  240. #endif
  241.         dad[r] = dad[p];
  242.         lson[r] = lson[p];
  243.         rson[r] = rson[p];
  244.         dad[lson[p]] = r;
  245.         dad[rson[p]] = r;
  246.         if (rson[dad[p]] == p)
  247.                 rson[dad[p]] = r;
  248.         else
  249.                 lson[dad[p]] = r;
  250.         dad[p] = NIL;  /* remove p */
  251. #undef p
  252. #undef r
  253. }
  254.  
  255. void DeleteNode(int p)  /* Deleting node from the tree */
  256. {
  257.         int  q;
  258.  
  259.         if (dad[p] == NIL)
  260.                 return;                 /* unregistered */
  261.         if (rson[p] == NIL)
  262.                 q = lson[p];
  263.         else
  264.         if (lson[p] == NIL)
  265.                 q = rson[p];
  266.         else {
  267.                 q = lson[p];
  268.                 if (rson[q] != NIL) {
  269.                         do {
  270.                                 q = rson[q];
  271.                         } while (rson[q] != NIL);
  272.                         rson[dad[q]] = lson[q];
  273.                         dad[lson[q]] = dad[q];
  274.                         lson[q] = lson[p];
  275.                         dad[lson[p]] = q;
  276.                 }
  277.                 rson[q] = rson[p];
  278.                 dad[rson[p]] = q;
  279.         }
  280.         dad[q] = dad[p];
  281.         if (rson[dad[p]] == p)
  282.                 rson[dad[p]] = q;
  283.         else
  284.                 lson[dad[p]] = q;
  285.         dad[p] = NIL;
  286. }
  287.  
  288. /* Huffman coding parameters */
  289.  
  290. #define N_CHAR          (256 - THRESHOLD + F)
  291.                                 /* character code (= 0..N_CHAR-1) */
  292. #define T               (N_CHAR * 2 - 1)        /* Size of table */
  293. #define R               (T - 1)                 /* root position */
  294. #define MAX_FREQ        0x8000
  295.                                         /* update when cumulative frequency */
  296.                                         /* reaches to this value */
  297.  
  298. typedef unsigned char uchar;
  299.  
  300. /*
  301.  * Tables for encoding/decoding upper 6 bits of
  302.  * sliding dictionary pointer
  303.  */
  304. /* encoder table */
  305. uchar p_len[64] = {
  306.         0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  307.         0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  308.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  309.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  310.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  311.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  312.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  313.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  314. };
  315.  
  316. uchar p_code[64] = {
  317.         0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  318.         0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  319.         0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  320.         0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  321.         0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  322.         0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  323.         0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  324.         0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  325. };
  326.  
  327. /* decoder table */
  328. uchar d_code[256] = {
  329.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  330.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  331.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  332.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  333.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  334.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  335.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  336.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  337.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  338.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  339.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  340.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  341.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  342.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  343.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  344.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  345.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  346.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  347.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  348.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  349.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  350.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  351.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  352.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  353.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  354.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  355.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  356.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  357.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  358.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  359.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  360.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  361. };
  362.  
  363. uchar d_len[256] = {
  364.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  365.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  366.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  367.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  368.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  369.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  370.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  371.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  372.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  373.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  374.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  375.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  376.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  377.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  378.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  379.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  380.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  381.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  382.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  383.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  384.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  385.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  386.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  387.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  388.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  389.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  390.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  391.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  392.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  393.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  394.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  395.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  396. };
  397.  
  398. unsigned freq[T + 1];   /* cumulative freq table */
  399.  
  400. /*
  401.  * pointing parent nodes.
  402.  * area [T..(T + N_CHAR - 1)] are pointers for leaves
  403.  */
  404. int prnt[T + N_CHAR];
  405.  
  406. /* pointing children nodes (son[], son[] + 1)*/
  407. int son[T];
  408.  
  409. unsigned getbuf = 0;
  410. uchar getlen = 0;
  411.  
  412. int GetBit(void)        /* get one bit */
  413. {
  414.         int i;
  415.  
  416.         while (getlen <= 8) {
  417.                 if ((i = getc(infile)) < 0) i = 0;
  418.                 getbuf |= i << (8 - getlen);
  419.                 getlen += 8;
  420.         }
  421.         i = getbuf;
  422.         getbuf <<= 1;
  423.         getlen--;
  424.         return (i < 0);
  425. }
  426.  
  427. int GetByte(void)       /* get a byte */
  428. {
  429.         unsigned i;
  430.  
  431.         while (getlen <= 8) {
  432.                 if ((i = getc(infile)) < 0) i = 0;
  433.                 getbuf |= i << (8 - getlen);
  434.                 getlen += 8;
  435.         }
  436. #ifdef USE_ASM
  437.         _AX = *(((unsigned char *)&getbuf)+1);
  438.         _BX = getbuf;
  439.         _BH = _BL;
  440.         _BL = 0;
  441.         asm mov getbuf,bx;
  442.         getlen -= 8;
  443.         return _AX;
  444. #else
  445.         i = getbuf;
  446.         getbuf <<= 8;
  447.         getlen -= 8;
  448.         return i >> 8;
  449. #endif
  450. }
  451.  
  452. unsigned putbuf = 0;
  453. uchar putlen = 0;
  454.  
  455. void Putcode(int l, unsigned c)         /* output c bits */
  456. {
  457.         putbuf |= c >> putlen;
  458.         if ((putlen += l) >= 8) {
  459.                 putc(putbuf >> 8, outfile);
  460.                 if ((putlen -= 8) >= 8) {
  461.                         putc(putbuf, outfile);
  462.                         codesize += 2;
  463.                         putlen -= 8;
  464.                         putbuf = c << (l - putlen);
  465.                 } else {
  466.                         putbuf <<= 8;
  467.                         codesize++;
  468.                 }
  469.         }
  470. }
  471.  
  472.  
  473. /* initialize freq tree */
  474.  
  475. void StartHuff()
  476. {
  477.         int i, j;
  478.  
  479.         for (i = 0; i < N_CHAR; i++) {
  480.                 freq[i] = 1;
  481.                 son[i] = i + T;
  482.                 prnt[i + T] = i;
  483.         }
  484.         i = 0; j = N_CHAR;
  485.         while (j <= R) {
  486.                 freq[j] = freq[i] + freq[i + 1];
  487.                 son[j] = i;
  488.                 prnt[i] = prnt[i + 1] = j;
  489.                 i += 2; j++;
  490.         }
  491.         freq[T] = 0xffff;
  492.         prnt[R] = 0;
  493. }
  494.  
  495.  
  496. /* reconstruct freq tree */
  497.  
  498. void reconst()
  499. {
  500.         int i, j, k;
  501.         unsigned f, l;
  502.  
  503.         /* halven cumulative freq for leaf nodes */
  504.         j = 0;
  505.         for (i = 0; i < T; i++) {
  506.                 if (son[i] >= T) {
  507.                         freq[j] = (freq[i] + 1) / 2;
  508.                         son[j] = son[i];
  509.                         j++;
  510.                 }
  511.         }
  512.         /* make a tree : first, connect children nodes */
  513.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  514.                 k = i + 1;
  515.                 f = freq[j] = freq[i] + freq[k];
  516.                 for (k = j - 1; f < freq[k]; k--);
  517.                 k++;
  518.                 l = (j - k) * 2;
  519.                 (void)memmove(&freq[k + 1], &freq[k], l);
  520.                 freq[k] = f;
  521.                 (void)memmove(&son[k + 1], &son[k], l);
  522.                 son[k] = i;
  523.         }
  524.         /* connect parent nodes */
  525.         for (i = 0; i < T; i++) {
  526.                 if ((k = son[i]) >= T) {
  527.                         prnt[k] = i;
  528.                 } else {
  529.                         prnt[k] = prnt[k + 1] = i;
  530.                 }
  531.         }
  532. }
  533.  
  534.  
  535. /* update freq tree */
  536.  
  537. void update(int c)
  538. {
  539.         register int k, l;
  540.         int i, j;
  541.  
  542.         if (freq[R] == MAX_FREQ) {
  543.                 reconst();
  544.         }
  545. #ifdef USE_ASM
  546. #define k _DX                           /* _DX is safe to use. */
  547.         _SI = prnt[c + T];
  548. #define c _SI
  549.         do {
  550.         more_k:
  551.                 k = ++freq[c];
  552.                 asm     cmp     dx,word ptr DGROUP:_freq+2[bx];
  553.                 asm     ja      start;
  554.                 asm     mov     si,word ptr DGROUP:_prnt[bx];
  555.                 asm     or      si,si;
  556.                 asm     jne     more_k;
  557.                 break;
  558.         start:
  559.                 _BX = (unsigned)&freq[c+1];
  560.         again:
  561.                 asm cmp dx,[bx]
  562.                 asm jbe done
  563.                 _BX += 4;
  564.                 asm cmp dx,[bx-2]
  565.                 asm ja again
  566.                 _BX -= 2;
  567.         done:
  568.                 _BX -= (unsigned) &freq;
  569.                 l = _BX >> 1;
  570. #else
  571.         c = prnt[c + T];
  572.         do {
  573.                 /* keep the outer loop together so stupid compilers
  574.                  * can optimize.
  575.                  */
  576.                 do {
  577.                         k = ++freq[c];
  578.                         /* swap nodes to keep the tree freq-ordered */
  579.                         if (k > freq[c + 1]) goto start;
  580.                 } while ((c = prnt[c]) != 0);
  581.                 break;
  582.         start:
  583.                 l = c + 1;
  584.                 /* this is the inner loop -- unroll it a few times */
  585.                 while (k > freq[++l] &&
  586.                        k > freq[++l] &&
  587.                        k > freq[++l]);
  588. #endif
  589.                 l--;
  590.                 freq[c] = freq[l];
  591.                 freq[l] = k;
  592.  
  593.                 i = son[c];
  594.                 prnt[i] = l;
  595.                 if (i < T) prnt[i + 1] = l;
  596.  
  597.                 j = son[l];
  598.                 son[l] = i;
  599.  
  600.                 prnt[j] = c;
  601.                 if (j < T) prnt[j + 1] = c;
  602.                 son[c] = j;
  603.  
  604.                 c = l;
  605.         } while ((c = prnt[c]) != 0);   /* do it until reaching the root */
  606. #undef k
  607. #undef c
  608. }
  609.  
  610. unsigned code, len;
  611.  
  612. void EncodeChar(unsigned c)
  613. {
  614.         unsigned i;
  615.         int j, k;
  616.  
  617.         i = 0;
  618.         j = 0;
  619.         k = prnt[c + T];
  620.  
  621.         /* search connections from leaf node to the root */
  622.         do {
  623.                 i >>= 1;
  624.  
  625.                 /*
  626.                 if node's address is odd, output 1
  627.                 else output 0
  628.                 */
  629.                 if (k & 1) i += 0x8000;
  630.  
  631.                 j++;
  632.         } while ((k = prnt[k]) != R);
  633.         Putcode(j, i);
  634.         code = i;
  635.         len = j;
  636.         update(c);
  637. }
  638.  
  639. void EncodePosition(unsigned c)
  640. {
  641.         unsigned i;
  642.  
  643.         /* output upper 6 bits with encoding */
  644.         i = c >> 6;
  645.         Putcode(p_len[i], (unsigned)p_code[i] << 8);
  646.  
  647.         /* output lower 6 bits directly */
  648.         Putcode(6, (c & 0x3f) << 10);
  649. }
  650.  
  651. void EncodeEnd()
  652. {
  653.         if (putlen) {
  654.                 putc(putbuf >> 8, outfile);
  655.                 codesize++;
  656.         }
  657. }
  658.  
  659. int DecodeChar()
  660. {
  661.         unsigned c;
  662.         c = son[R];
  663.  
  664.         /*
  665.          * start searching tree from the root to leaves.
  666.          * choose node #(son[]) if input bit == 0
  667.          * else choose #(son[]+1) (input bit == 1)
  668.          */
  669.         while (c < T) {
  670.                 if(getlen){
  671.                         getlen--;
  672. #ifdef USE_ASM
  673.                         getbuf<<=1;
  674.                         asm jnc zerobit;
  675.                         c++;
  676.                 zerobit:;
  677. #else
  678.                         if (getbuf < 0)
  679.                                 c++;
  680.                         getbuf<<=1;
  681. #endif
  682.                 } else
  683.                         c += GetBit();
  684.                 c = son[c];
  685.         }
  686.         c -= T;
  687.         update(c);
  688.         return c;
  689. }
  690.  
  691. int DecodePosition()
  692. {
  693.         unsigned i, j, c;
  694.  
  695.         /* decode upper 6 bits from given table */
  696.         i = GetByte();
  697.         c = (unsigned)d_code[i] << 6;
  698.         j = d_len[i];
  699.  
  700.         /* input lower 6 bits directly */
  701.         j -= 2;
  702.         while (j--) {
  703.                 i <<= 1;
  704.                 if(getlen){
  705.                         getlen--;
  706. #ifdef USE_ASM
  707.                         getbuf<<=1;
  708.                         asm jnc zerobit;
  709.                         i++;
  710.                 zerobit:;
  711. #else
  712.                         if (getbuf < 0)
  713.                                 i++;
  714.                         getbuf<<=1;
  715. #endif
  716.                 } else
  717.                         i += GetBit();
  718.         }
  719.         return c | i & 0x3f;
  720. }
  721.  
  722. /* Compression */
  723.  
  724. void Encode(void)  /* Encoding/Compressing */
  725. {
  726.         int  i, c, len, r, s, last_match_length;
  727.  
  728.         fseek(infile, 0L, 2);
  729.         textsize = ftell(infile);
  730.         if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  731.                 Error("Unable to write");       /* write size of original text */
  732.         if (textsize == 0)
  733.                 return;
  734.         rewind(infile);
  735.         textsize = 0;                   /* rewind and rescan */
  736.         StartHuff();
  737.         InitTree();
  738.         s = 0;
  739.         r = N - F;
  740.         for (i = s; i < r; i++)
  741.                 text_buf[i] = ' ';
  742.         for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  743.                 text_buf[r + len] = c;
  744.         textsize = len;
  745.         for (i = 1; i <= F; i++)
  746.                 InsertNode(r - i);
  747.         InsertNode(r);
  748.         do {
  749.                 if (match_length > len)
  750.                         match_length = len;
  751.                 if (match_length <= THRESHOLD) {
  752.                         match_length = 1;
  753.                         EncodeChar(text_buf[r]);
  754.                 } else {
  755.                         EncodeChar(255 - THRESHOLD + match_length);
  756.                         EncodePosition(match_position);
  757.                 }
  758.                 last_match_length = match_length;
  759.                 for (i = 0; i < last_match_length &&
  760.                                 (c = getc(infile)) != EOF; i++) {
  761.                         DeleteNode(s);
  762.                         text_buf[s] = c;
  763.                         if (s < F - 1)
  764.                                 text_buf[s + N] = c;
  765.                         s = (s + 1) & (N - 1);
  766.                         r = (r + 1) & (N - 1);
  767.                         InsertNode(r);
  768.                 }
  769.                 if ((textsize += i) > printcount) {
  770.                         printf("%12ld\r", textsize);
  771.                         printcount += 1024;
  772.                 }
  773.                 while (i++ < last_match_length) {
  774.                         DeleteNode(s);
  775.                         s = (s + 1) & (N - 1);
  776.                         r = (r + 1) & (N - 1);
  777.                         if (--len) InsertNode(r);
  778.                 }
  779.         } while (len > 0);
  780.         EncodeEnd();
  781.         printf("input: %ld bytes\n", textsize);
  782.         printf("output: %ld bytes\n", codesize);
  783.         printf("output/input: %.3f\n", (double)codesize / textsize);
  784. }
  785.  
  786. void Decode(void)  /* Decoding/Uncompressing */
  787. {
  788.         int  i, j, k, r, c;
  789.         unsigned long int  count;
  790.  
  791.         if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  792.                 Error("Unable to read");  /* read size of original text */
  793.         if (textsize == 0)
  794.                 return;
  795.         StartHuff();
  796.         for (i = 0; i < N - F; i++)
  797.                 text_buf[i] = ' ';
  798.         r = N - F;
  799.         for (count = 0; count < textsize; ) {
  800.                 c = DecodeChar();
  801.                 if (c < 256) {
  802.                         putc(c, outfile);
  803.                         text_buf[r++] = c;
  804.                         r &= (N - 1);
  805.                         count++;
  806.                 } else {
  807.                         i = (r - DecodePosition() - 1) & (N - 1);
  808.                         j = c - 255 + THRESHOLD;
  809.                         if (r + j < N
  810.                          && i + j < N
  811.                          && (i + j <= r || i >= r)
  812. #ifdef __TURBOC__
  813.                          && outfile->level < -j){
  814.                                 memcpy(outfile->curp,
  815.                                     memmove(&text_buf[r],&text_buf[i], j),
  816.                                     j);
  817.                                 outfile->curp += j;
  818.                                 outfile->level += j;
  819. #else
  820.                          ){
  821.                                 fwrite(memcpy(&text_buf[r],&text_buf[i], j),
  822.                                     1, j, outfile);
  823. #endif
  824.                                 r += j;
  825.                                 count += j;
  826.                         } else
  827.  
  828.                         for (k = i, j += i; k < j; k++) {
  829.                                 c = text_buf[k & (N - 1)];
  830.                                 putc(c, outfile);
  831.                                 text_buf[r++] = c;
  832.                                 r &= (N - 1);
  833.                                 count++;
  834.                         }
  835.                 }
  836.                 if (count > printcount) {
  837.                         printf("%12ld\r", count);
  838.                         printcount += 4096;
  839.                 }
  840.         }
  841.         printf("%12ld\n", count);
  842. }
  843.  
  844. int main(int argc, char *argv[])
  845. {
  846.         char  *s;
  847.  
  848.         if (argc != 4) {
  849.                 printf("Usage:lzhuf e(compression)|d(uncompression)"
  850.                         " infile outfile\n");
  851.                 return EXIT_FAILED;
  852.         }
  853.         if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  854.          || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  855.          || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  856.                 printf("Trouble with arg %s\n", s);
  857.                 return EXIT_FAILED;
  858.         }
  859.         setvbuf(outfile, NULL, _IOFBF, 1<<12);
  860.         setvbuf(infile, NULL, _IOFBF, 1<<12);
  861.         if (toupper(*argv[1]) == 'E')
  862.                 Encode();
  863.         else
  864.                 Decode();
  865.         fclose(infile);
  866.         fclose(outfile);
  867.         return EXIT_OK;
  868. }
  869.