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