home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / archiver / rblharc / lzhuf.c < prev    next >
C/C++ Source or Header  |  1993-07-08  |  53KB  |  2,184 lines
  1. /*----------------------------------------------------------------------*/
  2. /*              lzhuf.c : Encoding/Decoding module for LHarc            */
  3. /*                                                                      */
  4. /*      LZSS Algorithm                  Haruhiko.Okumura                */
  5. /*      Adaptic Huffman Encoding        1989.05.27  Haruyasu.Yoshizaki  */
  6. /*                                                                      */
  7. /*                                                                      */
  8. /*      Modified for UNIX LHarc V0.01   1989.05.28  Y.Tagawa            */
  9. /*      Modified for UNIX LHarc V0.02   1989.05.29  Y.Tagawa            */
  10. /*      Modified for UNIX LHarc V0.03   1989.07.02  Y.Tagawa            */
  11. /*----------------------------------------------------------------------*/
  12.  
  13. #include <stdio.h>
  14. #ifdef atarist
  15. #include <stdlib.h>
  16. #include <stddef.h>
  17. #include <string.h>
  18. #include <unixlib.h>
  19. #include <memory.h>
  20. #endif
  21.  
  22. #ifndef SELFMAIN
  23. #include "lhio.h"
  24. #else
  25. #define EXIT_SUCCESS    0
  26. #define EXIT_FAILURE    1
  27. #endif
  28.  
  29. #include "proto.h"
  30. static InitTree P((void ));
  31. static InsertNode P((int r ));
  32. static link P((int n , int p , int q ));
  33. static linknode P((int p , int q , int r ));
  34. static DeleteNode P((int p ));
  35. static int GetBit P((void ));
  36. static int GetByte P((void ));
  37. static int GetNBits P((unsigned int n ));
  38. static Putcode P((int l , unsigned int c ));
  39. static StartHuff P((void ));
  40. static reconst P((void ));
  41. static update P((unsigned int c ));
  42. static EncodeChar P((unsigned c ));
  43. static EncodePosition P((unsigned c ));
  44. static EncodeEnd P((void ));
  45. static int DecodeChar P((void ));
  46. static int DecodePosition P((void ));
  47. static Encode P((void ));
  48. static Decode P((void ));
  49. static InitBuf P((void ));
  50. static DecodeOld P((void ));
  51. static start_indicator P((char *name , long size , char *msg ));
  52. static finish_indicator2 P((char *name , char *msg , int pcnt ));
  53. static finish_indicator P((char *name , char *msg ));
  54.  
  55. #undef P
  56.  
  57. static FILE     *infile, *outfile;
  58. static long     textsize, codesize;
  59.  
  60.  
  61. #define INDICATOR_THRESHOLD     4096L
  62. #define MAX_INDICATOR_COUNT     64
  63. static long             indicator_count;
  64. static long             indicator_threshold;
  65.  
  66. #ifdef SELFMAIN
  67. int                     quiet = 0;
  68. #else
  69. extern int              quiet;
  70. #endif
  71.  
  72.  
  73. #ifdef SELFMAIN
  74. #define SETUP_PUTC_CRC(fp)      /* nothing */
  75. #define SETUP_GETC_CRC(fp)      /* nothing */
  76. #define PUTC_CRC(c)             putc((c),(outfile))
  77. #define GETC_CRC()              getc(infile)
  78. #define END_PUTC_CRC()
  79. #define END_GETC_CRC()
  80. #else
  81. #define SETUP_PUTC_CRC(fp)      crc_outfile = fp
  82. #define SETUP_GETC_CRC(fp)      crc_infile = fp
  83. #define PUTC_CRC(c)             putc_crc(c)
  84. #define GETC_CRC()              getc_crc()
  85. #define END_PUTC_CRC()
  86. #define END_GETC_CRC()
  87. #endif
  88.  
  89.  
  90.  
  91.  
  92. #ifdef SELFMAIN
  93. void Error (message)
  94.         char *message;
  95. {
  96.         printf("\n%s\n", message);
  97.         exit(EXIT_FAILURE);
  98. }
  99. #endif
  100.  
  101. /*----------------------------------------------------------------------*/
  102. /*                                                                      */
  103. /*              LZSS ENCODING                                           */
  104. /*                                                                      */
  105. /*----------------------------------------------------------------------*/
  106.  
  107. #define N               4096    /* buffer size */
  108. #define F               60      /* pre-sence buffer size */
  109. #define THRESHOLD       2
  110.  
  111. #ifdef __ASM__INSDEL__
  112. static unsigned char    text_buf[N+F];
  113. static unsigned int     match_position = 0, match_length = 0;
  114. static unsigned short   same[N+1];
  115. static unsigned short    rson[N+1];
  116. static unsigned short    lson[N+1];
  117. static unsigned short    dad[N+1];
  118. static unsigned short    roots[4096];
  119. static unsigned short *adrs[] = { &dad[0], &lson[0], &rson[0], &roots[0],
  120.                   (unsigned short *)&text_buf[-1] };
  121. static unsigned short *adrs2[] = { &dad[0], &lson[0], &rson[0], &same[0],
  122.                 (unsigned short *)&text_buf[-1] };
  123. #else
  124. #define NIL             N       /* term of tree */
  125. static unsigned char    text_buf[N + F - 1];
  126. static unsigned int     match_position, match_length;
  127. #endif
  128. #ifndef __ASM__INSDEL__
  129. static int              lson[N + 1], rson[N + 1 + N], dad[N + 1];
  130. static unsigned char    same[N + 1];
  131. #endif
  132.  
  133. #ifndef __ASM__INSDEL__
  134. /* Initialize Tree */
  135. static InitTree () 
  136. {
  137.         register int *p, *e;
  138.  
  139.         for (p = rson + N + 1, e = rson + N + N; p <= e; )
  140.                 *p++ = NIL;
  141.         for (p = dad, e = dad + N; p < e; )
  142.                 *p++ = NIL;
  143. }
  144.  
  145.  
  146. /* Insert to node */
  147. static InsertNode (r)
  148.         register int r;
  149. {
  150.         register int            p;
  151.         int                     cmp;
  152.         register unsigned char  *key;
  153.         register unsigned int   c;
  154.         register unsigned int   i, j;
  155.  
  156.         cmp = 1;
  157.         key = &text_buf[r];
  158.         i = key[1] ^ key[2];
  159.         i ^= i >> 4;
  160.         p = N + 1 + key[0] + ((i & 0x0f) << 8);
  161.         rson[r] = lson[r] = NIL;
  162.         match_length = 0;
  163.         i = j = 1;
  164.         for ( ; ; ) {
  165.                 if (cmp >= 0) {
  166.                         if (rson[p] != NIL) {
  167.                                 p = rson[p];
  168.                                 j = same[p];
  169.                         } else {
  170.                                 rson[p] = r;
  171.                                 dad[r] = p;
  172.                                 same[r] = i;
  173.                                 return;
  174.                         }
  175.                 } else {
  176.                         if (lson[p] != NIL) {
  177.                                 p = lson[p];
  178.                                 j = same[p];
  179.                         } else {
  180.                                 lson[p] = r;
  181.                                 dad[r] = p;
  182.                                 same[r] = i;
  183.                                 return;
  184.                         }
  185.                 }
  186.  
  187.                 if (i > j) {
  188.                         i = j;
  189.                         cmp = key[i] - text_buf[p + i];
  190.                 } else
  191.                 if (i == j) {
  192.                         for (; i < F; i++)
  193.                                 if ((cmp = key[i] - text_buf[p + i]) != 0)
  194.                                         break;
  195.                 }
  196.  
  197.                 if (i > THRESHOLD) {
  198.                         if (i > match_length) {
  199.                                 match_position = ((r - p) & (N - 1)) - 1;
  200.                                 if ((match_length = i) >= F)
  201.                                         break;
  202.                         } else
  203.                         if (i == match_length) {
  204.                                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  205.                                         match_position = c;
  206.                                 }
  207.                         }
  208.                 }
  209.         }
  210.         same[r] = same[p];
  211.         dad[r] = dad[p];
  212.         lson[r] = lson[p];
  213.         rson[r] = rson[p];
  214.         dad[lson[p]] = r;
  215.         dad[rson[p]] = r;
  216.         if (rson[dad[p]] == p)
  217.                 rson[dad[p]] = r;
  218.         else
  219.                 lson[dad[p]] = r;
  220.         dad[p] = NIL;  /* remove p */
  221. }
  222. #endif /* __ASM__INSDEL__ */
  223.  
  224. #ifndef __ASM__INSDEL__
  225. #ifdef __GNUC__
  226. inline
  227. #endif
  228. static link (n, p, q)
  229.         int n, p, q;
  230. {
  231.         register unsigned char *s1, *s2, *s3;
  232.         if (p >= NIL) {
  233.                 same[q] = 1;
  234.                 return;
  235.         }
  236.         s1 = text_buf + p + n;
  237.         s2 = text_buf + q + n;
  238.         s3 = text_buf + p + F;
  239.         while (s1 < s3) {
  240.                 if (*s1++ != *s2++) {
  241.                         same[q] = s1 - 1 - text_buf - p;
  242.                         return;
  243.                 }
  244.         }
  245.         same[q] = F;
  246. }
  247.  
  248.  
  249. #ifdef __GNUC__
  250. inline
  251. #endif
  252. static linknode (p, q, r)
  253.         int p, q, r;
  254. {
  255.         int cmp;
  256.  
  257.         if ((cmp = same[q] - same[r]) == 0) {
  258.                 link(same[q], p, r);
  259.         } else if (cmp < 0) {
  260.                 same[r] = same[q];
  261.         }
  262. }
  263. #endif /* __ASM__INSDEL__ */
  264.  
  265. #ifndef __ASM__INSDEL__
  266. static DeleteNode (p)
  267.         register int p;
  268. {
  269.         register int  q;
  270.  
  271.         if (dad[p] == NIL)
  272.                 return;                 /* has no linked */
  273.         if (rson[p] == NIL) {
  274.                 if ((q = lson[p]) != NIL)
  275.                         linknode(dad[p], p, q);
  276.         } else
  277.         if (lson[p] == NIL) {
  278.                 q = rson[p];
  279.                 linknode(dad[p], p, q);
  280.         } else {
  281.                 q = lson[p];
  282.                 if (rson[q] != NIL) {
  283.                         do {
  284.                                 q = rson[q];
  285.                         } while (rson[q] != NIL);
  286.                         if (lson[q] != NIL)
  287.                                 linknode(dad[q], q, lson[q]);
  288.                         link(1, q, lson[p]);
  289.                         rson[dad[q]] = lson[q];
  290.                         dad[lson[q]] = dad[q];
  291.                         lson[q] = lson[p];
  292.                         dad[lson[p]] = q;
  293.                 }
  294.                 link(1, dad[p], q);
  295.                 link(1, q, rson[p]);
  296.                 rson[q] = rson[p];
  297.                 dad[rson[p]] = q;
  298.         }
  299.         dad[q] = dad[p];
  300.         if (rson[dad[p]] == p)
  301.                 rson[dad[p]] = q;
  302.         else
  303.                 lson[dad[p]] = q;
  304.         dad[p] = NIL;
  305. }
  306. #endif /* __ASM__INSDEL__ */
  307.  
  308. /*----------------------------------------------------------------------*/
  309. /*                                                                      */
  310. /*              HUFFMAN ENCODING                                        */
  311. /*                                                                      */
  312. /*----------------------------------------------------------------------*/
  313.  
  314. #define N_CHAR          (256 - THRESHOLD + F) /* {code : 0 .. N_CHAR-1} */
  315. #define T               (N_CHAR * 2 - 1)        /* size of table */
  316. #define R               (T - 1)                 /* root position */
  317. #define MAX_FREQ        0x8000  /* tree update timing from frequency */
  318.  
  319. typedef unsigned char uchar;
  320.  
  321.  
  322.  
  323. /* TABLE OF ENCODE/DECODE for upper 6bits position information */
  324.  
  325. /* for encode */
  326. static uchar p_len[64] = {
  327.         0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  328.         0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  329.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  330.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  331.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  332.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  333.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  334.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  335. };
  336.  
  337. static uchar p_code[64] = {
  338.         0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  339.         0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  340.         0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  341.         0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  342.         0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  343.         0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  344.         0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  345.         0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  346. };
  347.  
  348. /* for decode */
  349. static uchar d_code[256] = {
  350.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  351.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  352.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  353.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  354.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  355.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  356.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  357.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  358.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  359.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  360.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  361.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  362.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  363.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  364.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  365.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  366.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  367.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  368.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  369.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  370.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  371.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  372.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  373.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  374.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  375.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  376.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  377.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  378.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  379.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  380.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  381.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  382. };
  383.  
  384. static uchar d_len[256] = {
  385.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  386.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  387.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  388.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  389.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  390.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  391.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  392.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  393.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  394.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  395.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  396.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  397.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  398.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  399.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  400.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  401.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  402.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  403.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  404.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  405.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  406.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  407.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  408.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  409.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  410.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  411.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  412.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  413.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  414.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  415.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  416.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  417. };
  418.  
  419. static unsigned freq[T + 1];    /* frequency table */
  420.  
  421. static int prnt[T + N_CHAR];    /* points to parent node */
  422. /* notes :
  423.    prnt[T .. T + N_CHAR - 1] used by
  424.    indicates leaf position that corresponding to code */
  425.  
  426. static int son[T];              /* points to son node (son[i],son[i+]) */
  427.  
  428. static unsigned getbuf = 0;
  429. static uchar getlen = 0;
  430.  
  431.  
  432. /* get one bit */
  433. /* returning in Bit 0 */
  434. #ifdef __GNUC__
  435. inline
  436. #endif
  437. static int GetBit ()
  438. {
  439.         register unsigned int dx = getbuf;
  440.         register unsigned int c;
  441.  
  442.         if (getlen <= 8)
  443.                 {
  444.                         c = getc (infile);
  445.                         if ((int)c < 0) c = 0;
  446.                         dx |= c << (8 - getlen);
  447.                         getlen += 8;
  448.                 }
  449.         getbuf = dx << 1;
  450.         getlen--;
  451.         return (dx & 0x8000) ? 1 : 0;
  452. }
  453.  
  454. /* get one byte */
  455. /* returning in Bit7...0 */
  456. #ifdef __GNUC__
  457. inline
  458. #endif
  459. static int GetByte ()
  460. {
  461.         register unsigned int dx = getbuf;
  462.         register unsigned c;
  463.  
  464.         if (getlen <= 8) {
  465.                 c = getc (infile);
  466.                 if ((int)c < 0) c = 0;
  467.                 dx |= c << (8 - getlen);
  468.                 getlen += 8;
  469.         }
  470.         getbuf = dx << 8;
  471.         getlen -= 8;
  472.         return (dx >> 8) & 0xff;
  473. }
  474.  
  475. /* get N bit */
  476. /* returning in Bit(N-1)...Bit 0 */
  477. static int GetNBits (n)
  478.         register unsigned int n;
  479. {
  480.         register unsigned int dx = getbuf;
  481.         register unsigned int c;
  482.         static int mask[17] = {
  483.                 0x0000,
  484.                 0x0001, 0x0003, 0x0007, 0x000f,
  485.                 0x001f, 0x003f, 0x007f, 0x00ff,
  486.                 0x01ff, 0x03ff, 0x07ff, 0x0fff,
  487.                 0x1fff, 0x3fff, 0x0fff, 0xffff };
  488.         static int shift[17] = {
  489.                 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
  490.         
  491.         if (getlen <= 8)
  492.                 {
  493.                         c = getc (infile);
  494.                         if ((int)c < 0) c = 0;
  495.                         dx |= c << (8 - getlen);
  496.                         getlen += 8;
  497.                 }
  498.         getbuf = dx << n;
  499.         getlen -= n;
  500.         return (dx >> shift[n]) & mask[n];
  501. }
  502.  
  503. static unsigned putbuf = 0;
  504. static uchar putlen = 0;
  505.  
  506. /* output C bits */
  507. #ifdef __GNUC__
  508. inline
  509. #endif
  510. static Putcode (l, c)
  511.         register int l;
  512.         register unsigned int c;
  513. {
  514.         register len = putlen;
  515.         register unsigned int b = putbuf;
  516.         b |= c >> len;
  517.         if ((len += l) >= 8) {
  518.                 putc (b >> 8, outfile);
  519.                 if ((len -= 8) >= 8) {
  520.                         putc (b, outfile);
  521.                         codesize += 2;
  522.                         len -= 8;
  523.                         b = c << (l - len);
  524.                 } else {
  525.                         b <<= 8;
  526.                         codesize++;
  527.                 }
  528.         }
  529.         putbuf = b;
  530.         putlen = len;
  531. }
  532.  
  533.  
  534. /* Initialize tree */
  535.  
  536. static StartHuff ()
  537. {
  538.         register int i, j;
  539.  
  540.         for (i = 0; i < N_CHAR; i++) {
  541.                 freq[i] = 1;
  542.                 son[i] = i + T;
  543.                 prnt[i + T] = i;
  544.         }
  545.         i = 0; j = N_CHAR;
  546.         while (j <= R) {
  547.                 freq[j] = freq[i] + freq[i + 1];
  548.                 son[j] = i;
  549.                 prnt[i] = prnt[i + 1] = j;
  550.                 i += 2; j++;
  551.         }
  552.         freq[T] = 0xffff;
  553.         prnt[R] = 0;
  554.         putlen = getlen = 0;
  555.         putbuf = getbuf = 0;
  556. }
  557.  
  558.  
  559. /* reconstruct tree */
  560. static reconst ()
  561. {
  562.         register int i, j, k;
  563.         register unsigned f;
  564.  
  565.         /* correct leaf node into of first half,
  566.            and set these freqency to (freq+1)/2       */
  567.         j = 0;
  568.         for (i = 0; i < T; i++) {
  569.                 if (son[i] >= T) {
  570.                         freq[j] = (freq[i] + 1) / 2;
  571.                         son[j] = son[i];
  572.                         j++;
  573.                 }
  574.         }
  575.         /* build tree.  Link sons first */
  576.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  577.                 k = i + 1;
  578.                 f = freq[j] = freq[i] + freq[k];
  579.                 for (k = j - 1; f < freq[k]; k--);
  580.                 k++;
  581.                 {       register unsigned *p, *e;
  582.                         for (p = &freq[j], e = &freq[k]; p > e; p--)
  583.                                 p[0] = p[-1];
  584.                         freq[k] = f;
  585.                 }
  586.                 {       register int *p, *e;
  587.                         for (p = &son[j], e = &son[k]; p > e; p--)
  588.                                 p[0] = p[-1];
  589.                         son[k] = i;
  590.                 }
  591.         }
  592.         /* link parents */
  593.         for (i = 0; i < T; i++) {
  594.                 if ((k = son[i]) >= T) {
  595.                         prnt[k] = i;
  596.                 } else {
  597.                         prnt[k] = prnt[k + 1] = i;
  598.                 }
  599.         }
  600. }
  601.  
  602.  
  603. /* update given code's frequency, and update tree */
  604.  
  605. #ifdef __GNUC__
  606. inline
  607. #endif
  608. static update (c)
  609.         unsigned int    c;
  610. {
  611.         register unsigned *p;
  612.         register int i, j, k, l;
  613.  
  614.         if (freq[R] == MAX_FREQ) {
  615.                 reconst();
  616.         }
  617.         c = prnt[c + T];
  618.         do {
  619.                 k = ++freq[c];
  620.  
  621.                 /* swap nodes when become wrong frequency order. */
  622.                 if (k > freq[l = c + 1]) {
  623.                         for (p = freq+l+1; k > *p++; ) ;
  624.                         l = p - freq - 2;
  625.                         freq[c] = p[-2];
  626.                         p[-2] = k;
  627.  
  628.                         i = son[c];
  629.                         prnt[i] = l;
  630.                         if (i < T) prnt[i + 1] = l;
  631.  
  632.                         j = son[l];
  633.                         son[l] = i;
  634.  
  635.                         prnt[j] = c;
  636.                         if (j < T) prnt[j + 1] = c;
  637.                         son[c] = j;
  638.  
  639.                         c = l;
  640.                 }
  641.         } while ((c = prnt[c]) != 0);   /* loop until reach to root */
  642. }
  643.  
  644. /* static unsigned code, len; */
  645.  
  646. static EncodeChar (c)
  647.         unsigned c;
  648. {
  649.         register int *p;
  650.         register unsigned long i;
  651.         register int j, k;
  652.  
  653.         i = 0;
  654.         j = 0;
  655.         p = prnt;
  656.         k = p[c + T];
  657.  
  658.         /* trace links from leaf node to root */
  659.         do {
  660.                 i >>= 1;
  661.  
  662.                 /* if node index is odd, trace larger of sons */
  663.                 if (k & 1) i += 0x80000000;
  664.  
  665.                 j++;
  666.         } while ((k = p[k]) != R) ;
  667.         if (j > 16) {
  668.                 Putcode(16, (unsigned int)(i >> 16));
  669.                 Putcode(j - 16, (unsigned int)i);
  670.         } else {
  671.                 Putcode(j, (unsigned int)(i >> 16));
  672.         }
  673. /*      code = i; */
  674. /*      len = j; */
  675.         update(c);
  676. }
  677.  
  678. static EncodePosition (c)
  679.         unsigned c;
  680. {
  681.         unsigned i;
  682.  
  683.         /* output upper 6bit from table */
  684.         i = c >> 6;
  685.         Putcode((int)(p_len[i]), (unsigned int)(p_code[i]) << 8);
  686.  
  687.         /* output lower 6 bit */
  688.         Putcode(6, (unsigned int)(c & 0x3f) << 10);
  689. }
  690.  
  691. static EncodeEnd ()
  692. {
  693.         if (putlen) {
  694.                 putc(putbuf >> 8, outfile);
  695.                 codesize++;
  696.         }
  697. }
  698.  
  699. #ifdef __GNUC__
  700. inline
  701. #endif
  702. static int DecodeChar ()
  703. {
  704.         register unsigned c;
  705.  
  706.         c = son[R];
  707.  
  708.         /* trace from root to leaf,
  709.            got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
  710.         while (c < T) {
  711.                 c += GetBit();
  712.                 c = son[c];
  713.         }
  714.         c -= T;
  715.         update(c);
  716.         return c;
  717. }
  718.  
  719. #ifdef __GNUC__
  720. inline
  721. #endif
  722. static int DecodePosition ()
  723. {
  724.         unsigned i, j, c;
  725.  
  726.         /* decode upper 6bit from table */
  727.         i = GetByte();
  728.         c = (unsigned)d_code[i] << 6;
  729.         j = d_len[i];
  730.  
  731.         /* get lower 6bit */
  732.         j -= 2;
  733.         return c | (((i << j) | GetNBits (j)) & 0x3f);
  734. }
  735.  
  736.  
  737. static Encode ()
  738. {
  739.         register int  i, c, len, r, s, last_match_length;
  740.  
  741.         if (textsize == 0)
  742.                 return;
  743.  
  744.         textsize = 0;
  745.         StartHuff();
  746.         InitTree();
  747.         s = 0;
  748.         r = N - F;
  749.         for (i = s; i < r; i++)
  750.                 text_buf[i] = ' ';
  751.         for (len = 0; len < F && (c = GETC_CRC()) != EOF; len++)
  752.                 text_buf[r + len] = c;
  753.         textsize = len;
  754. #ifndef __ASM__INSDEL__
  755.         for (i = 1; i <= F; i++)
  756.                 InsertNode(r - i);
  757. #else
  758.         for (i = 1; i <= F; i++)
  759.         InsertNoMatch(r - i);
  760. #endif
  761.         InsertNode(r);
  762. #if 0
  763. printf("%d %d\n", match_position, match_length);
  764. #endif
  765.         do {
  766.                 if (match_length > len)
  767.                         match_length = len;
  768.                 if (match_length <= THRESHOLD) {
  769.                         match_length = 1;
  770.                         EncodeChar(text_buf[r]);
  771.                 } else {
  772.                         EncodeChar(255 - THRESHOLD + match_length);
  773.                         EncodePosition(match_position);
  774.                 }
  775.                 last_match_length = match_length;
  776. #ifndef __ASM__INSDEL__
  777.                 for (i = 0; i < last_match_length &&
  778.                                 (c = GETC_CRC()) != EOF; i++) {
  779.                         DeleteNode(s);
  780.                         text_buf[s] = c;
  781.                         if (s < F - 1)
  782.                                 text_buf[s + N] = c;
  783.                         s = (s + 1) & (N - 1);
  784.                         r = (r + 1) & (N - 1);
  785.                         InsertNode(r);
  786.                 }
  787. #else
  788.         c = GETC_CRC();
  789.         i = 0;
  790.         if (i < last_match_length && c != EOF)
  791.         {
  792.           loopNM:
  793.                         DeleteNode(s);
  794.                         text_buf[s] = c;
  795.                         if (s < F - 1)
  796.                                 text_buf[s + N] = c;
  797.                         s = (s + 1) & (N - 1);
  798.                         r = (r + 1) & (N - 1);
  799.             if (++i < last_match_length && (c =
  800.                 GETC_CRC()) != EOF)
  801.             {
  802.                 InsertNoMatch (r);
  803.                 goto loopNM;
  804.             }
  805.             else
  806.                 InsertNode (r);
  807.             }
  808.  
  809. #endif
  810.  
  811. #if 0
  812. printf("%d %d\n", match_position, match_length);
  813. #endif
  814.  
  815.                 textsize += i;
  816.                 if ((textsize > indicator_count) && !quiet) {
  817.                         putchar ('o');
  818.                         fflush (stdout);
  819.                         indicator_count += indicator_threshold;
  820.                 }
  821.                 while (i++ < last_match_length) {
  822.                         DeleteNode(s);
  823.                         s = (s + 1) & (N - 1);
  824.                         r = (r + 1) & (N - 1);
  825.                         if (--len) InsertNode(r);
  826.                 }
  827.         } while (len > 0);
  828.         EncodeEnd();
  829.         END_GETC_CRC ();
  830. }
  831.  
  832. static Decode ()
  833. {
  834.         register int    i, j, k, r, c;
  835.         register long   count;
  836.  
  837. #ifdef SELFMAIN
  838.         if (textsize == 0)
  839.                 return;
  840. #endif
  841.         StartHuff();
  842.         for (i = 0; i < N - F; i++)
  843.                 text_buf[i] = ' ';
  844.         r = N - F;
  845.         for (count = 0; count < textsize; ) {
  846.                 c = DecodeChar();
  847.                 if (c < 256) {
  848.                         PUTC_CRC (c);
  849.                         text_buf[r++] = c;
  850.                         r &= (N - 1);
  851.                         count++;
  852.                 } else {
  853.                         i = (r - DecodePosition() - 1) & (N - 1);
  854.                         j = c - 255 + THRESHOLD;
  855.                         for (k = 0; k < j; k++) {
  856.                                 c = text_buf[(i + k) & (N - 1)];
  857.                                 PUTC_CRC (c);
  858.                                 text_buf[r++] = c;
  859.                                 r &= (N - 1);
  860.                                 count++;
  861.                         }
  862.                 }
  863.  
  864.                 if (!quiet && (count > indicator_count)) {
  865.                         putchar ('o');
  866.                         fflush (stdout);
  867.                         indicator_count += indicator_threshold;
  868.                 }
  869.         }
  870.         END_PUTC_CRC ();
  871. }
  872.  
  873.  
  874. /*----------------------------------------------------------------------*/
  875. /*                                                                      */
  876. /*              LARC                                                    */
  877. /*                                                                      */
  878. /*----------------------------------------------------------------------*/
  879.  
  880. #define F_OLD   18      /* look ahead buffer size for LArc */
  881.  
  882. /* intialize buffer for LArc type 5 */
  883. static InitBuf ()
  884. {
  885.         register unsigned char *p = text_buf;
  886.         register int i, j;
  887.         for (i = 0; i < 256; i ++)
  888.                 for (j = 0; j < 13; j ++)
  889.                         *p ++ = i;
  890.         for (i = 0; i < 256; i ++)
  891.                 *p ++ = i;
  892.         for (i = 0; i < 256; i ++)
  893.                 *p ++ = 255 - i;
  894.         for (i = 0; i < 128; i ++)
  895.                 *p ++ = 0;
  896.         for (i = 0; i < 128; i ++)
  897.                 *p ++ = 0x20;
  898. }
  899.  
  900. /* Decode LArc type 5 */
  901. static DecodeOld ()
  902. {
  903.         register int si, di;
  904.         register long count;
  905.         int     dl, dh, al, cx;
  906.         if (textsize == 0)
  907.                 return;
  908.         
  909.         InitBuf ();
  910.         di = N - F_OLD;
  911.         dl = 0x80;
  912.         
  913.         for (count = 0; count < textsize; ) {
  914.                 dl = ((dl << 1) | (dl >> 7)) & 0xff;
  915.                 if (dl & 0x01)
  916.                         dh = getc (infile);
  917.                 al = getc (infile);
  918.                 if ((dh & dl) != 0) {
  919.                         PUTC_CRC (al);
  920.                         text_buf[di] = al;
  921.                         di = (di + 1) & (N - 1);
  922.                         count ++;
  923.                 } else {
  924.                         cx = getc (infile);
  925.                         si = (al & 0x00ff) | ((cx << 4) & 0x0f00);
  926.                         cx = (cx & 0x000f) + 3;
  927.                         count += cx;
  928.                         do {
  929.                                 text_buf[di] = al = text_buf[si];
  930.                                 PUTC_CRC (al);
  931.                                 si = (si + 1) & (N - 1);
  932.                                 di = (di + 1) & (N - 1);
  933.                         } while (--cx != 0) ;
  934.                 }
  935.  
  936.                 if (!quiet && (count > indicator_count)) {
  937.                         putchar ('o');
  938.                         fflush (stdout);
  939.                         indicator_count += indicator_threshold;
  940.                 }
  941.         }
  942.         END_PUTC_CRC ();
  943. }
  944.  
  945.  
  946.  
  947. /*----------------------------------------------------------------------*/
  948. /*                                                                      */
  949. /*              Global Entries for Archiver Driver                      */
  950. /*                                                                      */
  951. /*----------------------------------------------------------------------*/
  952.  
  953.  
  954. static start_indicator (name, size, msg)
  955.         char *name;
  956.         long size;
  957.         char *msg;
  958. {
  959.         long    i;
  960.         int     m;
  961.  
  962.         if (quiet)
  963.                 return;
  964.  
  965.         m = MAX_INDICATOR_COUNT - strlen (name);
  966.         if (m < 0)
  967.                 m = 3;          /* (^_^) */
  968.  
  969. #ifndef atarist
  970.         printf ("\r%s\t- %s :  ", name, msg);
  971. #else
  972.         printf ("\r%s\n", name);
  973. #endif
  974.  
  975.         indicator_threshold =
  976.                 ((size  + (m * INDICATOR_THRESHOLD - 1)) /
  977.                  (m * INDICATOR_THRESHOLD) *
  978.                  INDICATOR_THRESHOLD);
  979.     i = (indicator_threshold ?
  980.          ((size + (indicator_threshold - 1)) / indicator_threshold) : 0);
  981. #ifndef atarist
  982.         while (i--)
  983.                 putchar ('.');
  984.         indicator_count = 0;
  985.         printf ("\r%s\t- %s :  ", name, msg);
  986.         fflush (stdout);
  987. #else
  988.         printf ("%s :  ", msg);
  989.         while (i--)
  990.                 putchar ('.');
  991.         indicator_count = 0;
  992.         printf ("\r%s :  ", msg);
  993.         fflush (stdout);
  994. #endif
  995. }
  996.  
  997. static finish_indicator2 (name, msg, pcnt)
  998.         char *name;
  999.         char *msg;
  1000.         int pcnt;
  1001. {
  1002.         if (quiet)
  1003.                 return;
  1004.  
  1005.         if (pcnt > 100) pcnt = 100;     /* (^_^) */
  1006. #ifndef atarist
  1007.         printf ("\r%s\t- %s(%d%%)\n", name, msg, pcnt);
  1008. #else
  1009.         printf ("\r%s(%d%%)\n", msg, pcnt);
  1010. #endif
  1011.         fflush (stdout);
  1012. }
  1013.  
  1014. static finish_indicator (name, msg)
  1015.         char *name;
  1016.         char *msg;
  1017. {
  1018.         if (quiet)
  1019.                 return;
  1020.  
  1021. #ifndef atarist
  1022.         printf ("\r%s\t- %s\n", name, msg);
  1023. #else
  1024.         printf ("\r%s\n", msg);
  1025. #endif
  1026.         fflush (stdout);
  1027. }
  1028.  
  1029.  
  1030. #ifndef SELFMAIN
  1031. int encode_lzhuf (infp, outfp, size, original_size_var, packed_size_var, name)
  1032.         FILE *infp;
  1033.         FILE *outfp;
  1034.         long size;
  1035.         long *original_size_var;
  1036.         long *packed_size_var;
  1037.         char *name;
  1038. {
  1039.         infile = infp;
  1040.         outfile = outfp;
  1041.         SETUP_GETC_CRC(infp);
  1042.         textsize = size;
  1043.         codesize = 0;
  1044.         init_crc ();
  1045.         start_indicator (name, size, "Freezing");
  1046.         Encode ();
  1047.         finish_indicator2 (name, "Frozen",
  1048.                            (int)((codesize * 100L) / crc_size));
  1049.         *packed_size_var = codesize;
  1050.         *original_size_var = crc_size;
  1051.         return crc_value;
  1052. }
  1053.  
  1054. int decode_lzhuf (infp, outfp, original_size, name)
  1055.         FILE *infp;
  1056.         FILE *outfp;
  1057.         long original_size;
  1058.         char *name;
  1059. {
  1060.         infile = infp;
  1061.         outfile = outfp;
  1062.         SETUP_PUTC_CRC(outfp);
  1063.         textsize = original_size;
  1064.         init_crc ();
  1065. #ifndef TSTFLG
  1066.         start_indicator (name, original_size, "Melting ");
  1067.         Decode ();
  1068.         finish_indicator (name, "Melted  ");
  1069. #else
  1070.         start_indicator (name, original_size, (tstflg ? "Testing " : "Melting "));
  1071.         Decode ();
  1072.         finish_indicator (name, (tstflg ? "Tested  " : "Melted  "));
  1073. #endif
  1074.         return crc_value;
  1075. }
  1076.  
  1077.  
  1078. int decode_larc (infp, outfp, original_size, name)
  1079.         FILE *infp, *outfp;
  1080.         long original_size;
  1081.         char *name;
  1082. {
  1083.         infile = infp;
  1084.         outfile = outfp;
  1085.         SETUP_PUTC_CRC(outfp);
  1086.         textsize = original_size;
  1087.         init_crc ();
  1088.         start_indicator (name, original_size, "Melting ");
  1089.         DecodeOld ();
  1090.         finish_indicator (name, "Melted  ");
  1091.         return crc_value;
  1092. }
  1093. #endif
  1094.  
  1095. #ifdef SELFMAIN
  1096. int main (argc, argv)
  1097.         int argc;
  1098.         char *argv[];
  1099. {
  1100.         char  *s;
  1101.         int i;
  1102.  
  1103.         indicator_count = 0;
  1104.         indicator_threshold = 1024;
  1105.         textsize = codesize = 0;
  1106.         if (argc != 4) {
  1107.                 printf ("\
  1108. usage: lzhuf e in_file out_file (packing)\n\
  1109.        lzhuf d in_file out_file (unpacking)\n");
  1110.                 return EXIT_FAILURE;
  1111.         }
  1112.         if ((s = argv[1], ((*s != 'e') && (*s != 'd')) || s[1] != '\0') ||
  1113.   #ifdef ultrix
  1114.          (s = argv[2], (infile  = fopen(s, "r")) == NULL) ||
  1115.          (s = argv[3], (outfile = fopen(s, "w")) == NULL)) {
  1116.   #else
  1117.             (s = argv[2], (infile  = fopen(s, "rb")) == NULL) ||
  1118.             (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  1119.   #endif
  1120.                 printf("??? %s\n", s);
  1121.                 return EXIT_FAILURE;
  1122.         }
  1123.         if (argv[1][0] == 'e') {
  1124.                 /* Get original text size and output it */
  1125.                 fseek(infile, 0L, 2);
  1126.                 textsize = ftell(infile);
  1127.                 rewind (infile);
  1128.                 if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  1129.                         Error("cannot write");
  1130.  
  1131.                 start_indicator (argv[2], textsize, "Freezing");
  1132.                 Encode();
  1133.                 finith_indicator2 (argv[2], "Frozen",
  1134.                                    (int)((codesize * 100L) / textsize));
  1135.  
  1136.                 printf("input : %ld bytes\n", textsize);
  1137.                 printf("output: %ld bytes\n", codesize);
  1138.         } else {
  1139.                 /* Read original text size */
  1140.                 if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  1141.                         Error("cannot read");
  1142.  
  1143.                 start_indicator (argv[2], textsize, "Melting ");
  1144.                 Decode();
  1145.                 finish_indicator (argv[2], "Melted  ");
  1146.         }
  1147.         fclose(infile);
  1148.         fclose(outfile);
  1149.         return EXIT_SUCCESS;
  1150. }
  1151. #endif
  1152.  
  1153.  
  1154. /* These lines are used in GNU-Emacs */
  1155. /* Local Variables: */
  1156. /* comment-column:40 */
  1157. /* tab-width:8 */
  1158. /* c-indent-level:8 */
  1159. /* c-continued-statement-offset:8 */
  1160. /* c-argdecl-indent:8 */
  1161. /* End: */
  1162.  
  1163. #ifdef __ASM__INSDEL__
  1164. #ifdef atarist
  1165. __asm__("
  1166. N    =    4096
  1167. F    =    60
  1168.  
  1169.     .text; .even
  1170.     | InitTree(void)
  1171. _InitTree:
  1172.     movel    _adrs+12,a1    | Roots
  1173.     moveq    #0,d0
  1174.     movew    #(N+1)*3+4095,d1
  1175. clrt:    movew    d0,a1@+
  1176.     dbf    d1,clrt
  1177.     rts
  1178.  
  1179. |----------
  1180. |- Delete -
  1181. |----------
  1182.  
  1183. D.doR:    movew    d1,d3        | Get to end of Lt tree
  1184.     movew    a4@(0,d3:w),d1
  1185.     bnes    D.doR
  1186.     movew    d1,a0@(_rson-_dad)    | Clear L & R
  1187.     movew    d1,a0@(_lson-_dad)
  1188.  
  1189.     movew    d4,a4@(0,d3:w)
  1190.     movew    d3,a2@(0,d4:w)
  1191.     movew    d4,d1        | Calc new _same value
  1192.     lsrw    #1,d1
  1193.     lea    a6@(1,d1:w),a0
  1194.     movew    d3,d1
  1195.     lsrw    #1,d1
  1196.     lea    a6@(1,d1:w),a1
  1197.     moveq    #0,d1
  1198. Lcmp3:    addqw    #1,d1
  1199.     cmpmb    a0@+,a1@+
  1200.     beqs    Lcmp3
  1201.  
  1202. put4d1:    movew    d1,a5@(0,d4:w)
  1203.     subaw    d1,a1
  1204.     movew    a3@(0,d3:w),d1    | _Lson of new
  1205.     movew    d0,a3@(0,d3:w)    | Move rest of old _lson tree to new,
  1206.     movew    d3,a2@(0,d0:w)    |and chg old _lson's _dad pointer
  1207.     movew    d0,d4
  1208.     lsrw    #1,d4
  1209.     lea    a6@(1,d4:w),a0
  1210.     moveq    #0,d4
  1211. Lcmp2:    addqw    #1,d4
  1212.     cmpmb    a0@+,a1@+
  1213.     beqs    Lcmp2
  1214.  
  1215. put0d4:    movew    d4,a5@(0,d0:w)
  1216.     movew    a2@(0,d3:w),d0    | Prev _dad of new
  1217.     movew    d0,a2@(0,d1:w)
  1218.     movew    d1,a4@(0,d0:w)    | Connect with prev _lson of new
  1219.     beqs    skplink
  1220.     movew    a5@(0,d3:w),d4
  1221.      cmpw    a5@(0,d1:w),d4
  1222.      bhis    skplink
  1223.     bnes    put1d4
  1224.     lsrw    #1,d0
  1225.     addw    d4,d0
  1226.     lea    a6@(0,d0:w),a0
  1227.     movew    d1,d0
  1228.     lsrw    #1,d0
  1229.     addw    d4,d0
  1230.     lea    a6@(0,d0:w),a1
  1231.     subqw    #1,d4
  1232. Lcmp1:    addqw    #1,d4
  1233.     cmpmb    a0@+,a1@+
  1234.     beqs    Lcmp1
  1235. put1d4:    movew    d4,a5@(0,d1:w)
  1236. skplink:    movew    d3,d4
  1237.     bras    Lcpy_dad
  1238.  
  1239. ret1:    moveml    sp@+,d2-d5/a2-a6
  1240.     rts
  1241.     
  1242.     .text; .even
  1243.     | DeleteNode(int p)
  1244. _DeleteNode:
  1245.     moveml d2-d5/a2-a6,sp@-
  1246.     moveml    _adrs2,a2-a6
  1247.     movew    a7@(40),d5
  1248.     addw    d5,d5
  1249.     lea    a2@(2,d5:w),a0
  1250.     movew    a0@,d2
  1251.     beqs    ret1        | Node empty (almost never)
  1252.     addqw    #2,d5
  1253.     movew    a0@(_rson-_dad),d4
  1254.     beqs    D.noR
  1255.     movew    a0@(_lson-_dad),d0
  1256.     beqs    cpy_dad0
  1257. |                | Has both sons: d4=_rson, d0=_lson
  1258.     movew    a4@(0,d0:w),d1
  1259.     bne    D.doR
  1260.  
  1261. copyL:    movew    d4,a4@(0,d0:w)
  1262.     movew    d0,a2@(0,d4:w)
  1263.     movew    d1,a0@(_rson-_dad)    | Clear L & R
  1264.     movew    d1,a0@(_lson-_dad)
  1265.     movew    d4,d3
  1266.     lsrw    #1,d3
  1267.     lea    a6@(1,d3:w),a0
  1268.     movew    d0,d3
  1269.     lsrw    #1,d3
  1270.     lea    a6@(1,d3:w),a1
  1271.     subqw    #1,d1
  1272. Lcmp4:    addqw    #1,d1
  1273.     cmpmb    a0@+,a1@+
  1274.     beqs    Lcmp4
  1275.     movew    d1,a5@(0,d4:w)
  1276.     movew    d0,d4
  1277.  
  1278. Lcpy_dad:    movew    d2,d0
  1279.     lsrw    #1,d0
  1280.     lea    a6@(1,d0:w),a0
  1281.     movew    d4,d0
  1282.     lsrw    #1,d0
  1283.     lea    a6@(1,d0:w),a1
  1284.     moveq    #0,d1
  1285.     bras    D.cmp
  1286.  
  1287. D.noR:    movew    a0@(_lson-_dad),d4
  1288.     beqs    cpy_dad
  1289.     moveq    #0,d0
  1290.     movew    d0,a0@(_lson-_dad)
  1291. cpy_dad0:    movew    d0,a0@(_rson-_dad)
  1292.      movew    a5@(0,d5:w),d1
  1293.     cmpw    a5@(0,d4:w),d1
  1294.      bhis    cpy_dad
  1295.     bnes    putd1
  1296.     movew    d2,d0
  1297.     lsrw    #1,d0
  1298.     addw    d1,d0
  1299.     lea    a6@(0,d0:w),a0
  1300.     movew    d4,d0
  1301.     lsrw    #1,d0
  1302.     addw    d1,d0
  1303.     lea    a6@(0,d0:w),a1
  1304.     subqw    #1,d1
  1305. D.cmp:    addqw    #1,d1
  1306.     cmpmb    a0@+,a1@+
  1307.     beqs    D.cmp
  1308. putd1:    movew    d1,a5@(0,d4:w)
  1309.  
  1310. cpy_dad:     movew    d2,a2@(0,d4:w)
  1311.     bmis    rootd4
  1312.     cmpw    a4@(0,d2:w),d5
  1313.     beqs    D.rt
  1314.     movew    d4,a3@(0,d2:w)
  1315.     moveml    sp@+,d2-d5/a2-a6
  1316.     rts
  1317. D.rt:    movew    d4,a4@(0,d2:w)
  1318.     moveml    sp@+,d2-d5/a2-a6
  1319.     rts
  1320.  
  1321. rootd4:    lsrw    #1,d5        | Occurs 50% of deletes
  1322.     lea    a6@(0,d5:w),a0
  1323.     moveq    #0,d0
  1324.     moveq    #0,d1
  1325.     moveb    a0@+,d0
  1326.     moveb    a0@+,d1
  1327.     moveb    a0@,d2
  1328.     eorb    d2,d1
  1329.     movew    d1,d2
  1330.     lslb    #4,d1
  1331.     eorw    d2,d1
  1332.     lslw    #4,d1
  1333.     clrb    d1
  1334.     addw    d1,d0
  1335.     addw    d0,d0        |104 = .5 sec per 100K
  1336.     movel    _adrs+12,a5
  1337.     movew    d4,a5@(0,d0:w)    | Update starting ptr
  1338.     moveml    sp@+,d2-d5/a2-a6
  1339.     rts
  1340.  
  1341. |----------
  1342. |- Insert -
  1343. |----------
  1344.  
  1345. I.mt:    movew    d6,a5@(0,d1:w)    | Set starting pt of tree
  1346.     moveq    #-1,d1
  1347.     movew    d1,a2@(0,d6:w)    | -1 marks root
  1348.     movew    d7,_match_length    | d7=0, No match
  1349.     moveml    sp@+,d2-d7/a2-a6
  1350.     rts
  1351.  
  1352. Isam:    addqw    #1,d0
  1353.     cmpw    d7,d0
  1354.     blts    ILcmp
  1355.     bra    I.full
  1356.  
  1357.     .text; .even
  1358.     | InsertNode(int r)
  1359. _InsertNode:
  1360.     moveml d2-d7/a2-a6,sp@-
  1361.     moveml    _adrs,a2-a6
  1362.     movew    sp@(48),d6
  1363.     addqw    #1,d6
  1364.     lea    a6@(0,d6:w),a0
  1365.     addw    d6,d6
  1366.     moveq    #0,d0
  1367.     moveq    #0,d1
  1368.     moveb    a0@+,d0
  1369.     moveb    a0@+,d1
  1370.     moveb    a0@,d2
  1371.     eorb    d2,d1
  1372.     movew    d1,d2
  1373.     lslb    #4,d1
  1374.     eorw    d2,d1
  1375.     lslw    #4,d1
  1376.     clrb    d1
  1377.     addw    d0,d1
  1378.     addw    d1,d1
  1379.     movew    a5@(0,d1:w),d7    | Get starting pt of tree
  1380.     beqs    I.mt        | 1st time character has been seen
  1381.     movel    _adrs2+12,a5
  1382.     moveq    #0,d2        | Clear L & R match lengths
  1383.     moveq    #0,d5
  1384.     moveq    #1,d0
  1385.     movew    d7,d1
  1386.  
  1387. Isame:    lsrw    #1,d7
  1388.     addw    d0,d7
  1389.     lea    a6@(0,d7:w),a1
  1390.     subql    #1,a0
  1391.     moveq    #F,d7
  1392. ILcmp:    cmpmb    a1@+,a0@+
  1393.     beqs    Isam
  1394.     blss    I.low
  1395. I.Ragain:
  1396.     cmpw    d0,d2
  1397.     bnes    Rset
  1398.     cmpw    d1,d3
  1399.     bccs    d1d3
  1400.     cmpw    d6,d1
  1401.     bcss    Ruzd1
  1402.     cmpw    d6,d3
  1403.     bccs    Ruzd1
  1404.     bras    Ruzd3
  1405.  
  1406. I.ckR:    movew    d7,d1
  1407.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1408.     bcss    I.Ragain
  1409.     beqs    Isame
  1410. I.part:    subaw    d0,a0        | 6%
  1411.     movew    a5@(0,d7:w),d0
  1412.     addaw    d0,a0        | Point to just after SAME data
  1413.     bras    Isame
  1414.  
  1415. d1d3:    cmpw    d6,d1
  1416.     bccs    Ruzd3
  1417.     cmpw    d6,d3
  1418.     bcss    Ruzd3
  1419. Rset:    movew    d0,d2        | Last match length R
  1420. Ruzd1:    movew    d1,d3        |        pos R
  1421. Ruzd3:    movew    a4@(0,d1:w),d7    | Link to rt son
  1422.     bnes    I.ckR
  1423.     movew    d1,a2@(0,d6:w)    | Node was mt, insert d6
  1424.     movew    d6,a4@(0,d1:w)
  1425.     movew    d0,a5@(0,d6:w)
  1426.     cmpw    d0,d5
  1427.     bcss    I.uzd3
  1428.     beqs    I.ck34
  1429. I.uzd4:    subw    d4,d6
  1430.     lsrw    #1,d6
  1431.     andw    #N-1,d6
  1432.     subqw    #1,d6
  1433.     movew    d6,_match_position    | Last Lt turn was longer
  1434.     movew    d5,_match_length
  1435.     moveml    sp@+,d2-d7/a2-a6
  1436.     rts
  1437.  
  1438. I.ckL:    movew    d7,d1
  1439.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1440.     beqs    Isame
  1441.     bccs    I.part
  1442. |                | Fall through to do Left again
  1443. I.low:    cmpw    d0,d5
  1444.     bnes    Lset
  1445.     cmpw    d1,d4
  1446.     bccs    d1d4
  1447.     cmpw    d6,d1
  1448.     bcss    Luzd1
  1449.     cmpw    d6,d4
  1450.     bcss    Luzd4
  1451. Lset:    movew    d0,d5        | Len L
  1452. Luzd1:    movew    d1,d4        | Pos L
  1453. Luzd4:    movew    a3@(0,d1:w),d7    | Link to lt son
  1454.     bnes    I.ckL
  1455.     movew    d1,a2@(0,d6:w)
  1456.     movew    d6,a3@(0,d1:w)
  1457.     movew    d0,a5@(0,d6:w)
  1458.     cmpw    d0,d2
  1459.     bcss    I.uzd4
  1460.     beqs    I.ck34
  1461. I.uzd3:    subw    d3,d6
  1462.     lsrw    #1,d6
  1463.     andw    #N-1,d6
  1464.     subqw    #1,d6
  1465.     movew    d6,_match_position    | Last Rt turn was longer
  1466.     movew    d2,_match_length
  1467.     moveml    sp@+,d2-d7/a2-a6
  1468.     rts
  1469.  
  1470. d1d4:    cmpw    d6,d1
  1471.     bccs    Luzd4
  1472.     cmpw    d6,d4
  1473.     bccs    Luzd1
  1474.     bras    Luzd4
  1475.  
  1476. I.ck34:    movew    d6,d2
  1477.     subw    d4,d6
  1478.     lsrw    #1,d6
  1479.     andw    #N-1,d6
  1480.     subw    d3,d2
  1481.     lsrw    #1,d2
  1482.     andw    #N-1,d2
  1483.     cmpw    d2,d6
  1484.     bcss    I.uzd6        | 56,58 from I.ck34
  1485.     subqw    #1,d2
  1486.     movew    d2,_match_position    | Last Lt turn was longer
  1487.     movew    d0,_match_length
  1488.     moveml    sp@+,d2-d7/a2-a6
  1489.     rts
  1490.  
  1491. I.uzd6:    subqw    #1,d6
  1492.     movew    d6,_match_position
  1493.     movew    d0,_match_length
  1494.     moveml    sp@+,d2-d7/a2-a6
  1495.     rts
  1496.  
  1497. I.full:    lea    a2@(0,d1:w),a1
  1498.     lea    a2@(0,d6:w),a0
  1499.     movew    a1@(_lson-_dad),d3    | Replace old node with new one
  1500.     movew    d3,a0@(_lson-_dad)
  1501.     movew    d6,a2@(0,d3:w)        |and point old sons to new
  1502.     movew    a1@(_rson-_dad),d3
  1503.     movew    d3,a0@(_rson-_dad)
  1504.     movew    d6,a2@(0,d3:w)
  1505.     movew    a5@(0,d1:w),a5@(0,d6:w)    | Move SAME
  1506.     movew    a1@,d3
  1507.     clrw    a1@            | Delete old
  1508.     clrw    a1@(_lson-_dad)
  1509.     clrw    a1@(_rson-_dad)
  1510.     movew    d3,a0@
  1511.     bmis    I.root
  1512.     cmpw    a4@(0,d3:w),d1
  1513.     beqs    I.rt
  1514.     movel    a3,a4
  1515. I.rt:    movew    d6,a4@(0,d3:w)
  1516.     subw    d1,d6
  1517.     lsrw    #1,d6
  1518.     andw    #N-1,d6
  1519.     subqw    #1,d6
  1520.     movew    d6,_match_position
  1521.     movew    #F,_match_length
  1522.     moveml    sp@+,d2-d7/a2-a6
  1523.     rts
  1524. I.root:    movew    d6,d3        | Occurs almost never
  1525.     lsrw    #1,d3
  1526.     lea    a6@(0,d3:w),a0
  1527.     moveq    #0,d3
  1528.     moveq    #0,d0
  1529.     moveb    a0@+,d3
  1530.     moveb    a0@+,d0
  1531.     moveb    a0@,d2
  1532.     eorb    d2,d0
  1533.     movew    d0,d2
  1534.     lslb    #4,d0
  1535.     eorw    d2,d0
  1536.     lslw    #4,d0
  1537.     clrb    d0
  1538.     addw    d0,d3
  1539.     addw    d3,d3
  1540.     movel    _adrs+12,a4    | ROOTS
  1541.     bras    I.rt
  1542.  
  1543. |-------------------------
  1544. |Insert with No Match data
  1545. |-------------------------
  1546.  
  1547. NM.mt:    movew    d6,a5@(0,d1:w)    | Set starting pt of tree
  1548.     moveq    #-1,d1
  1549.     movew    d1,a2@(0,d6:w)    | -1 marks root
  1550.     moveml    sp@+,d6-d7/a2-a6
  1551.     rts
  1552.  
  1553.      .text; .even
  1554. _InsertNoMatch:
  1555.     moveml d6-d7/a2-a6,sp@-
  1556.     moveml    _adrs,a2-a6
  1557.     movew    a7@(32),d6
  1558.     addqw    #1,d6
  1559.     lea    a6@(0,d6:w),a0
  1560.     addw    d6,d6
  1561.     moveq    #0,d0
  1562.     moveq    #0,d1
  1563.     moveb    a0@+,d0
  1564.     moveb    a0@+,d1
  1565.     moveb    a0@,d7
  1566.     eorb    d7,d1
  1567.     movew    d1,d7
  1568.     lslb    #4,d1
  1569.     eorw    d7,d1
  1570.     lslw    #4,d1
  1571.     clrb    d1
  1572.     addw    d0,d1
  1573.     addw    d1,d1
  1574.     movew    a5@(0,d1:w),d7    | Get starting pt of tree
  1575.     beqs    NM.mt        | 1st time character has been seen
  1576.     movel    _adrs2+12,a5
  1577.     moveq    #1,d0
  1578.     movew    d7,d1
  1579.  
  1580. NMsame:    lsrw    #1,d7
  1581.     addw    d0,d7
  1582.     lea    a6@(0,d7:w),a1
  1583.     subql    #1,a0
  1584.     moveq    #F,d7
  1585. NMLcmp:    cmpmb    a1@+,a0@+
  1586.     bnes    NM.dif
  1587.     addqw    #1,d0
  1588.     cmpw    d7,d0
  1589.     blts    NMLcmp
  1590.     bra    NM.full
  1591.  
  1592. NM.dif:
  1593.     blss    NM.low
  1594. NM.Ragain:
  1595.     movew    a4@(0,d1:w),d7    | Link to rt son
  1596.     bnes    NM.ckR
  1597.     movew    d1,a2@(0,d6:w)    | Node was mt, insert d6
  1598.     movew    d6,a4@(0,d1:w)
  1599.     movew    d0,a5@(0,d6:w)
  1600.     moveml    sp@+,d6-d7/a2-a6
  1601.     rts
  1602.  
  1603. NM.ckR:    movew    d7,d1
  1604.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1605.     bcss    NM.Ragain
  1606.     beqs    NMsame
  1607. NM.part:    subaw    d0,a0    | 6%
  1608.     movew    a5@(0,d7:w),d0
  1609.     addaw    d0,a0        | Point to just after SAME data
  1610.     bras    NMsame
  1611.  
  1612. NM.ckL:    movew    d7,d1
  1613.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1614.     beqs    NMsame
  1615.     bccs    NM.part
  1616. |                | Fall through to do Left again
  1617. NM.low:    movew    a3@(0,d1:w),d7    | Link to lt son
  1618.     bnes    NM.ckL
  1619.     movew    d1,a2@(0,d6:w)
  1620.     movew    d6,a3@(0,d1:w)
  1621.     movew    d0,a5@(0,d6:w)
  1622.     moveml    sp@+,d6-d7/a2-a6
  1623.     rts
  1624.  
  1625. NM.full:
  1626.     lea    a2@(0,d1:w),a1
  1627.     lea    a2@(0,d6:w),a0
  1628.     movew    a1@(_lson-_dad),d7    | Replace old node with new one
  1629.     movew    d7,a0@(_lson-_dad)
  1630.     movew    d6,a2@(0,d7:w)        |and point old sons to new
  1631.     movew    a1@(_rson-_dad),d7
  1632.     movew    d7,a0@(_rson-_dad)
  1633.     movew    d6,a2@(0,d7:w)
  1634.     movew    a5@(0,d1:w),a5@(0,d6:w)    | Move SAME
  1635.     movew    a1@,d7
  1636.     clrw    a1@            | Delete old
  1637.     clrw    a1@(_lson-_dad)
  1638.     clrw    a1@(_rson-_dad)
  1639.     movew    d7,a0@
  1640.     bmis    NM.root
  1641.     cmpw    a4@(0,d7:w),d1
  1642.     beqs    NM.rt
  1643.     movel    a3,a4
  1644. NM.rt:    movew    d6,a4@(0,d7:w)
  1645.     moveml    sp@+,d6-d7/a2-a6
  1646.     rts
  1647. NM.root:
  1648.     movew    d6,d7        | Occurs almost never
  1649.     lsrw    #1,d7
  1650.     lea    a6@(0,d7:w),a0
  1651.     moveq    #0,d7
  1652.     moveq    #0,d0
  1653.     moveb    a0@+,d7
  1654.     moveb    a0@+,d0
  1655.     moveb    a0@,d1
  1656.     eorb    d1,d0
  1657.     movew    d0,d1
  1658.     lslb    #4,d0
  1659.     eorw    d1,d0
  1660.     lslw    #4,d0
  1661.     clrb    d0
  1662.     addw    d0,d7
  1663.     addw    d7,d7
  1664.     movel    _adrs+12,a4    | ROOTS
  1665.     bras    NM.rt
  1666.  
  1667. ");
  1668. #else
  1669. __asm__("
  1670. N    =    4096
  1671. F    =    60
  1672.  
  1673.     .text; .even
  1674.     | InitTree(void)
  1675. _InitTree:
  1676.     movel    _adrs+12,a1    | Roots
  1677.     moveq    #0,d0
  1678.     movew    #(N+1)*3+4095,d1
  1679. clrt:    movew    d0,a1@+
  1680.     dbf    d1,clrt
  1681.     rts
  1682.  
  1683. |----------
  1684. |- Delete -
  1685. |----------
  1686.  
  1687. D.doR:    movew    d1,d3        | Get to end of Lt tree
  1688.     movew    a4@(0,d3:w),d1
  1689.     bnes    D.doR
  1690.     movew    d1,a0@(_rson-_dad)    | Clear L & R
  1691.     movew    d1,a0@(_lson-_dad)
  1692.  
  1693.     movew    d4,a4@(0,d3:w)
  1694.     movew    d3,a2@(0,d4:w)
  1695.     movew    d4,d1        | Calc new _same value
  1696.     lsrw    #1,d1
  1697.     lea    a6@(1,d1:w),a0
  1698.     movew    d3,d1
  1699.     lsrw    #1,d1
  1700.     lea    a6@(1,d1:w),a1
  1701.     moveq    #0,d1
  1702. Lcmp3:    addqw    #1,d1
  1703.     cmpmb    a0@+,a1@+
  1704.     beqs    Lcmp3
  1705.  
  1706. put4d1:    movew    d1,a5@(0,d4:w)
  1707.     subaw    d1,a1
  1708.     movew    a3@(0,d3:w),d1    | _Lson of new
  1709.     movew    d0,a3@(0,d3:w)    | Move rest of old _lson tree to new,
  1710.     movew    d3,a2@(0,d0:w)    |and chg old _lson's _dad pointer
  1711.     movew    d0,d4
  1712.     lsrw    #1,d4
  1713.     lea    a6@(1,d4:w),a0
  1714.     moveq    #0,d4
  1715. Lcmp2:    addqw    #1,d4
  1716.     cmpmb    a0@+,a1@+
  1717.     beqs    Lcmp2
  1718.  
  1719. put0d4:    movew    d4,a5@(0,d0:w)
  1720.     movew    a2@(0,d3:w),d0    | Prev _dad of new
  1721.     movew    d0,a2@(0,d1:w)
  1722.     movew    d1,a4@(0,d0:w)    | Connect with prev _lson of new
  1723.     beqs    skplink
  1724.     movew    a5@(0,d3:w),d4
  1725.      cmpw    a5@(0,d1:w),d4
  1726.      bhis    skplink
  1727.     bnes    put1d4
  1728.     lsrw    #1,d0
  1729.     addw    d4,d0
  1730.     lea    a6@(0,d0:w),a0
  1731.     movew    d1,d0
  1732.     lsrw    #1,d0
  1733.     addw    d4,d0
  1734.     lea    a6@(0,d0:w),a1
  1735.     subqw    #1,d4
  1736. Lcmp1:    addqw    #1,d4
  1737.     cmpmb    a0@+,a1@+
  1738.     beqs    Lcmp1
  1739. put1d4:    movew    d4,a5@(0,d1:w)
  1740. skplink:    movew    d3,d4
  1741.     bras    Lcpy_dad
  1742.  
  1743. ret1:    moveml    sp@+,d2-d5/a2-a6
  1744.     rts
  1745.     
  1746.     .text; .even
  1747.     | DeleteNode(int p)
  1748. _DeleteNode:
  1749.     moveml d2-d5/a2-a6,sp@-
  1750.     moveml    _adrs2,a2-a6
  1751.     movel    a7@(40),d5
  1752.     addw    d5,d5
  1753.     lea    a2@(2,d5:w),a0
  1754.     movew    a0@,d2
  1755.     beqs    ret1        | Node empty (almost never)
  1756.     addqw    #2,d5
  1757.     movew    a0@(_rson-_dad),d4
  1758.     beqs    D.noR
  1759.     movew    a0@(_lson-_dad),d0
  1760.     beqs    cpy_dad0
  1761. |                | Has both sons: d4=_rson, d0=_lson
  1762.     movew    a4@(0,d0:w),d1
  1763.     bne    D.doR
  1764.  
  1765. copyL:    movew    d4,a4@(0,d0:w)
  1766.     movew    d0,a2@(0,d4:w)
  1767.     movew    d1,a0@(_rson-_dad)    | Clear L & R
  1768.     movew    d1,a0@(_lson-_dad)
  1769.     movew    d4,d3
  1770.     lsrw    #1,d3
  1771.     lea    a6@(1,d3:w),a0
  1772.     movew    d0,d3
  1773.     lsrw    #1,d3
  1774.     lea    a6@(1,d3:w),a1
  1775.     subqw    #1,d1
  1776. Lcmp4:    addqw    #1,d1
  1777.     cmpmb    a0@+,a1@+
  1778.     beqs    Lcmp4
  1779.     movew    d1,a5@(0,d4:w)
  1780.     movew    d0,d4
  1781.  
  1782. Lcpy_dad:    movew    d2,d0
  1783.     lsrw    #1,d0
  1784.     lea    a6@(1,d0:w),a0
  1785.     movew    d4,d0
  1786.     lsrw    #1,d0
  1787.     lea    a6@(1,d0:w),a1
  1788.     moveq    #0,d1
  1789.     bras    D.cmp
  1790.  
  1791. D.noR:    movew    a0@(_lson-_dad),d4
  1792.     beqs    cpy_dad
  1793.     moveq    #0,d0
  1794.     movew    d0,a0@(_lson-_dad)
  1795. cpy_dad0:    movew    d0,a0@(_rson-_dad)
  1796.      movew    a5@(0,d5:w),d1
  1797.     cmpw    a5@(0,d4:w),d1
  1798.      bhis    cpy_dad
  1799.     bnes    putd1
  1800.     movew    d2,d0
  1801.     lsrw    #1,d0
  1802.     addw    d1,d0
  1803.     lea    a6@(0,d0:w),a0
  1804.     movew    d4,d0
  1805.     lsrw    #1,d0
  1806.     addw    d1,d0
  1807.     lea    a6@(0,d0:w),a1
  1808.     subqw    #1,d1
  1809. D.cmp:    addqw    #1,d1
  1810.     cmpmb    a0@+,a1@+
  1811.     beqs    D.cmp
  1812. putd1:    movew    d1,a5@(0,d4:w)
  1813.  
  1814. cpy_dad:     movew    d2,a2@(0,d4:w)
  1815.     bmis    rootd4
  1816.     cmpw    a4@(0,d2:w),d5
  1817.     beqs    D.rt
  1818.     movew    d4,a3@(0,d2:w)
  1819.     moveml    sp@+,d2-d5/a2-a6
  1820.     rts
  1821. D.rt:    movew    d4,a4@(0,d2:w)
  1822.     moveml    sp@+,d2-d5/a2-a6
  1823.     rts
  1824.  
  1825. rootd4:    lsrw    #1,d5        | Occurs 50% of deletes
  1826.     lea    a6@(0,d5:w),a0
  1827.     moveq    #0,d0
  1828.     moveq    #0,d1
  1829.     moveb    a0@+,d0
  1830.     moveb    a0@+,d1
  1831.     moveb    a0@,d2
  1832.     eorb    d2,d1
  1833.     movew    d1,d2
  1834.     lslb    #4,d1
  1835.     eorw    d2,d1
  1836.     lslw    #4,d1
  1837.     clrb    d1
  1838.     addw    d1,d0
  1839.     addw    d0,d0        |104 = .5 sec per 100K
  1840.     movel    _adrs+12,a5
  1841.     movew    d4,a5@(0,d0:w)    | Update starting ptr
  1842.     moveml    sp@+,d2-d5/a2-a6
  1843.     rts
  1844.  
  1845. |----------
  1846. |- Insert -
  1847. |----------
  1848.  
  1849. I.mt:    movew    d6,a5@(0,d1:w)    | Set starting pt of tree
  1850.     moveq    #-1,d1
  1851.     movew    d1,a2@(0,d6:w)    | -1 marks root
  1852.      extl    d7
  1853.     movel    d7,_match_length    | d7=0, No match
  1854.     moveml    sp@+,d2-d7/a2-a6
  1855.     rts
  1856.  
  1857. Isam:    addqw    #1,d0
  1858.     cmpw    d7,d0
  1859.     blts    ILcmp
  1860.     bra    I.full
  1861.  
  1862.     .text; .even
  1863.     | InsertNode(int r)
  1864. _InsertNode:
  1865.     moveml d2-d7/a2-a6,sp@-
  1866.     moveml    _adrs,a2-a6
  1867.     movel    sp@(48),d6
  1868.     addqw    #1,d6
  1869.     lea    a6@(0,d6:w),a0
  1870.     addw    d6,d6
  1871.     moveq    #0,d0
  1872.     moveq    #0,d1
  1873.     moveb    a0@+,d0
  1874.     moveb    a0@+,d1
  1875.     moveb    a0@,d2
  1876.     eorb    d2,d1
  1877.     movew    d1,d2
  1878.     lslb    #4,d1
  1879.     eorw    d2,d1
  1880.     lslw    #4,d1
  1881.     clrb    d1
  1882.     addw    d0,d1
  1883.     addw    d1,d1
  1884.     movew    a5@(0,d1:w),d7    | Get starting pt of tree
  1885.     beqs    I.mt        | 1st time character has been seen
  1886.     movel    _adrs2+12,a5
  1887.     moveq    #0,d2        | Clear L & R match lengths
  1888.     moveq    #0,d5
  1889.     moveq    #1,d0
  1890.     movew    d7,d1
  1891.  
  1892. Isame:    lsrw    #1,d7
  1893.     addw    d0,d7
  1894.     lea    a6@(0,d7:w),a1
  1895.     subql    #1,a0
  1896.     moveq    #F,d7
  1897. ILcmp:    cmpmb    a1@+,a0@+
  1898.     beqs    Isam
  1899.     blss    I.low
  1900. I.Ragain:
  1901.     cmpw    d0,d2
  1902.     bnes    Rset
  1903.     cmpw    d1,d3
  1904.     bccs    d1d3
  1905.     cmpw    d6,d1
  1906.     bcss    Ruzd1
  1907.     cmpw    d6,d3
  1908.     bccs    Ruzd1
  1909.     bras    Ruzd3
  1910.  
  1911. I.ckR:    movew    d7,d1
  1912.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1913.     bcss    I.Ragain
  1914.     beqs    Isame
  1915. I.part:    subaw    d0,a0        | 6%
  1916.     movew    a5@(0,d7:w),d0
  1917.     addaw    d0,a0        | Point to just after SAME data
  1918.     bras    Isame
  1919.  
  1920. d1d3:    cmpw    d6,d1
  1921.     bccs    Ruzd3
  1922.     cmpw    d6,d3
  1923.     bcss    Ruzd3
  1924. Rset:    movew    d0,d2        | Last match length R
  1925. Ruzd1:    movew    d1,d3        |        pos R
  1926. Ruzd3:    movew    a4@(0,d1:w),d7    | Link to rt son
  1927.     bnes    I.ckR
  1928.     movew    d1,a2@(0,d6:w)    | Node was mt, insert d6
  1929.     movew    d6,a4@(0,d1:w)
  1930.     movew    d0,a5@(0,d6:w)
  1931.     cmpw    d0,d5
  1932.     bcss    I.uzd3
  1933.     beqs    I.ck34
  1934. I.uzd4:    subw    d4,d6
  1935.     lsrw    #1,d6
  1936.     andw    #N-1,d6
  1937.     subqw    #1,d6
  1938.      extl    d6
  1939.     movel    d6,_match_position    | Last Lt turn was longer
  1940.      extl    d5
  1941.     movel    d5,_match_length
  1942.     moveml    sp@+,d2-d7/a2-a6
  1943.     rts
  1944.  
  1945. I.ckL:    movew    d7,d1
  1946.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  1947.     beqs    Isame
  1948.     bccs    I.part
  1949. |                | Fall through to do Left again
  1950. I.low:    cmpw    d0,d5
  1951.     bnes    Lset
  1952.     cmpw    d1,d4
  1953.     bccs    d1d4
  1954.     cmpw    d6,d1
  1955.     bcss    Luzd1
  1956.     cmpw    d6,d4
  1957.     bcss    Luzd4
  1958. Lset:    movew    d0,d5        | Len L
  1959. Luzd1:    movew    d1,d4        | Pos L
  1960. Luzd4:    movew    a3@(0,d1:w),d7    | Link to lt son
  1961.     bnes    I.ckL
  1962.     movew    d1,a2@(0,d6:w)
  1963.     movew    d6,a3@(0,d1:w)
  1964.     movew    d0,a5@(0,d6:w)
  1965.     cmpw    d0,d2
  1966.     bcss    I.uzd4
  1967.     beqs    I.ck34
  1968. I.uzd3:    subw    d3,d6
  1969.     lsrw    #1,d6
  1970.     andw    #N-1,d6
  1971.     subqw    #1,d6
  1972.      extl    d6
  1973.     movel    d6,_match_position    | Last Rt turn was longer
  1974.      extl    d2
  1975.     movel    d2,_match_length
  1976.     moveml    sp@+,d2-d7/a2-a6
  1977.     rts
  1978.  
  1979. d1d4:    cmpw    d6,d1
  1980.     bccs    Luzd4
  1981.     cmpw    d6,d4
  1982.     bccs    Luzd1
  1983.     bras    Luzd4
  1984.  
  1985. I.ck34:    movew    d6,d2
  1986.     subw    d4,d6
  1987.     lsrw    #1,d6
  1988.     andw    #N-1,d6
  1989.     subw    d3,d2
  1990.     lsrw    #1,d2
  1991.     andw    #N-1,d2
  1992.     cmpw    d2,d6
  1993.     bcss    I.uzd6        | 56,58 from I.ck34
  1994.     subqw    #1,d2
  1995.      extl    d2
  1996.     movel    d2,_match_position    | Last Lt turn was longer
  1997.      extl    d0
  1998.     movel    d0,_match_length
  1999.     moveml    sp@+,d2-d7/a2-a6
  2000.     rts
  2001.  
  2002. I.uzd6:    subqw    #1,d6
  2003.      extl    d6
  2004.     movel    d6,_match_position
  2005.      extl    d0
  2006.     movel    d0,_match_length
  2007.     moveml    sp@+,d2-d7/a2-a6
  2008.     rts
  2009.  
  2010. I.full:    lea    a2@(0,d1:w),a1
  2011.     lea    a2@(0,d6:w),a0
  2012.     movew    a1@(_lson-_dad),d3    | Replace old node with new one
  2013.     movew    d3,a0@(_lson-_dad)
  2014.     movew    d6,a2@(0,d3:w)        |and point old sons to new
  2015.     movew    a1@(_rson-_dad),d3
  2016.     movew    d3,a0@(_rson-_dad)
  2017.     movew    d6,a2@(0,d3:w)
  2018.     movew    a5@(0,d1:w),a5@(0,d6:w)    | Move SAME
  2019.     movew    a1@,d3
  2020.     clrw    a1@            | Delete old
  2021.     clrw    a1@(_lson-_dad)
  2022.     clrw    a1@(_rson-_dad)
  2023.     movew    d3,a0@
  2024.     bmis    I.root
  2025.     cmpw    a4@(0,d3:w),d1
  2026.     beqs    I.rt
  2027.     movel    a3,a4
  2028. I.rt:    movew    d6,a4@(0,d3:w)
  2029.     subw    d1,d6
  2030.     lsrw    #1,d6
  2031.     andw    #N-1,d6
  2032.     subqw    #1,d6
  2033.      extl    d6
  2034.     movel    d6,_match_position
  2035.     movel    #F,_match_length
  2036.     moveml    sp@+,d2-d7/a2-a6
  2037.     rts
  2038. I.root:    movew    d6,d3        | Occurs almost never
  2039.     lsrw    #1,d3
  2040.     lea    a6@(0,d3:w),a0
  2041.     moveq    #0,d3
  2042.     moveq    #0,d0
  2043.     moveb    a0@+,d3
  2044.     moveb    a0@+,d0
  2045.     moveb    a0@,d2
  2046.     eorb    d2,d0
  2047.     movew    d0,d2
  2048.     lslb    #4,d0
  2049.     eorw    d2,d0
  2050.     lslw    #4,d0
  2051.     clrb    d0
  2052.     addw    d0,d3
  2053.     addw    d3,d3
  2054.     movel    _adrs+12,a4    | ROOTS
  2055.     bras    I.rt
  2056.  
  2057. |-------------------------
  2058. |Insert with No Match data
  2059. |-------------------------
  2060.  
  2061. NM.mt:    movew    d6,a5@(0,d1:w)    | Set starting pt of tree
  2062.     moveq    #-1,d1
  2063.     movew    d1,a2@(0,d6:w)    | -1 marks root
  2064.     moveml    sp@+,d6-d7/a2-a6
  2065.     rts
  2066.  
  2067.      .text; .even
  2068. _InsertNoMatch:
  2069.     moveml d6-d7/a2-a6,sp@-
  2070.     moveml    _adrs,a2-a6
  2071.     movel    a7@(32),d6
  2072.     addqw    #1,d6
  2073.     lea    a6@(0,d6:w),a0
  2074.     addw    d6,d6
  2075.     moveq    #0,d0
  2076.     moveq    #0,d1
  2077.     moveb    a0@+,d0
  2078.     moveb    a0@+,d1
  2079.     moveb    a0@,d7
  2080.     eorb    d7,d1
  2081.     movew    d1,d7
  2082.     lslb    #4,d1
  2083.     eorw    d7,d1
  2084.     lslw    #4,d1
  2085.     clrb    d1
  2086.     addw    d0,d1
  2087.     addw    d1,d1
  2088.     movew    a5@(0,d1:w),d7    | Get starting pt of tree
  2089.     beqs    NM.mt        | 1st time character has been seen
  2090.     movel    _adrs2+12,a5
  2091.     moveq    #1,d0
  2092.     movew    d7,d1
  2093.  
  2094. NMsame:    lsrw    #1,d7
  2095.     addw    d0,d7
  2096.     lea    a6@(0,d7:w),a1
  2097.     subql    #1,a0
  2098.     moveq    #F,d7
  2099. NMLcmp:    cmpmb    a1@+,a0@+
  2100.     bnes    NM.dif
  2101.     addqw    #1,d0
  2102.     cmpw    d7,d0
  2103.     blts    NMLcmp
  2104.     bra    NM.full
  2105.  
  2106. NM.dif:
  2107.     blss    NM.low
  2108. NM.Ragain:
  2109.     movew    a4@(0,d1:w),d7    | Link to rt son
  2110.     bnes    NM.ckR
  2111.     movew    d1,a2@(0,d6:w)    | Node was mt, insert d6
  2112.     movew    d6,a4@(0,d1:w)
  2113.     movew    d0,a5@(0,d6:w)
  2114.     moveml    sp@+,d6-d7/a2-a6
  2115.     rts
  2116.  
  2117. NM.ckR:    movew    d7,d1
  2118.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  2119.     bcss    NM.Ragain
  2120.     beqs    NMsame
  2121. NM.part:    subaw    d0,a0    | 6%
  2122.     movew    a5@(0,d7:w),d0
  2123.     addaw    d0,a0        | Point to just after SAME data
  2124.     bras    NMsame
  2125.  
  2126. NM.ckL:    movew    d7,d1
  2127.     cmpw    a5@(0,d7:w),d0    | Ck # of bytes that are the SAME as _dad
  2128.     beqs    NMsame
  2129.     bccs    NM.part
  2130. |                | Fall through to do Left again
  2131. NM.low:    movew    a3@(0,d1:w),d7    | Link to lt son
  2132.     bnes    NM.ckL
  2133.     movew    d1,a2@(0,d6:w)
  2134.     movew    d6,a3@(0,d1:w)
  2135.     movew    d0,a5@(0,d6:w)
  2136.     moveml    sp@+,d6-d7/a2-a6
  2137.     rts
  2138.  
  2139. NM.full:
  2140.     lea    a2@(0,d1:w),a1
  2141.     lea    a2@(0,d6:w),a0
  2142.     movew    a1@(_lson-_dad),d7    | Replace old node with new one
  2143.     movew    d7,a0@(_lson-_dad)
  2144.     movew    d6,a2@(0,d7:w)        |and point old sons to new
  2145.     movew    a1@(_rson-_dad),d7
  2146.     movew    d7,a0@(_rson-_dad)
  2147.     movew    d6,a2@(0,d7:w)
  2148.     movew    a5@(0,d1:w),a5@(0,d6:w)    | Move SAME
  2149.     movew    a1@,d7
  2150.     clrw    a1@            | Delete old
  2151.     clrw    a1@(_lson-_dad)
  2152.     clrw    a1@(_rson-_dad)
  2153.     movew    d7,a0@
  2154.     bmis    NM.root
  2155.     cmpw    a4@(0,d7:w),d1
  2156.     beqs    NM.rt
  2157.     movel    a3,a4
  2158. NM.rt:    movew    d6,a4@(0,d7:w)
  2159.     moveml    sp@+,d6-d7/a2-a6
  2160.     rts
  2161. NM.root:
  2162.     movew    d6,d7        | Occurs almost never
  2163.     lsrw    #1,d7
  2164.     lea    a6@(0,d7:w),a0
  2165.     moveq    #0,d7
  2166.     moveq    #0,d0
  2167.     moveb    a0@+,d7
  2168.     moveb    a0@+,d0
  2169.     moveb    a0@,d1
  2170.     eorb    d1,d0
  2171.     movew    d0,d1
  2172.     lslb    #4,d0
  2173.     eorw    d1,d0
  2174.     lslw    #4,d0
  2175.     clrb    d0
  2176.     addw    d0,d7
  2177.     addw    d7,d7
  2178.     movel    _adrs+12,a4    | ROOTS
  2179.     bras    NM.rt
  2180.  
  2181. ");
  2182. #endif
  2183. #endif
  2184.