home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / sources / misc / 3818 < prev    next >
Encoding:
Text File  |  1992-08-18  |  28.8 KB  |  1,126 lines
  1. Newsgroups: comp.sources.misc
  2. Path: sparky!kent
  3. From: leo@ipmce.su (Leonid A. Broukhis)
  4. Subject:  v31i089:  freeze - Freeze/melt compression program 2.3, Patch05
  5. Message-ID: <1992Aug18.215658.29273@sparky.imd.sterling.com>
  6. Followup-To: comp.sources.d
  7. X-Md4-Signature: d64313176f1e0ff48b0941206b3eb8e6
  8. Sender: kent@sparky.imd.sterling.com (Kent Landfield)
  9. Organization: Sterling Software
  10. Date: Tue, 18 Aug 1992 21:56:58 GMT
  11. Approved: kent@sparky.imd.sterling.com
  12. Lines: 1112
  13.  
  14. Submitted-by: leo@ipmce.su (Leonid A. Broukhis)
  15. Posting-number: Volume 31, Issue 89
  16. Archive-name: freeze/patch05
  17. Environment: ISC, Xenix, SunOS, MS-DOS
  18. Patch-To: freeze: Volume 25, Issue 12-13
  19.  
  20. Main enhancements:
  21.  - compression speed (without reducing compression rate)
  22.    was significantly increased;
  23.  - other small contributed patches.
  24.  
  25. *** distribution/README    Thu Jul 16 15:20:51 1992
  26. --- README    Mon Aug 17 17:02:12 1992
  27. ***************
  28. *** 12,29 ****
  29.       o M_XENIX & !M_I386     Makes arrays < 65536 bytes each
  30.       o BSD                   Allow long filenames ( > 14 characters) &
  31.                   Call setlinebuf(stderr)
  32. !     o INT_SIG               signal is int (*)() unstead of void
  33.       o MSDOS                 Turns off some UNIX-dependencies
  34. !                 and MSDOS' ones - vice versa
  35. !                 !!! It's important !!!
  36. !                 If your MSDOS' C compiler does support
  37. !                 inline functions, define DO_INLINE.
  38. !                 This will cause the main loop to be
  39. !                 replaced with a call of memcmp, which
  40. !                 will be represented as 'repz cmpsb'.
  41.       o FAST                  Forces the Get_Next_Match routine
  42.                   to be inline. This gives additional
  43. !                 percents of speedup.
  44.       o __TURBOC__            For compiling under TURBO C
  45.       o __i386__              When compiling under GNU C causes
  46.                   some fixed register allocations,
  47. --- 12,31 ----
  48.       o M_XENIX & !M_I386     Makes arrays < 65536 bytes each
  49.       o BSD                   Allow long filenames ( > 14 characters) &
  50.                   Call setlinebuf(stderr)
  51. !     o SIGTYPE               The type that is returned by signal
  52. !                 handlers.  Defaults to void.
  53.       o MSDOS                 Turns off some UNIX-dependencies
  54. !                 and MSDOS' ones - vice versa.
  55. !     o FASTHASH              Uses another hash function which gives
  56. !                 some speedup, thus reducing the compression
  57. !                 rate (!)
  58.       o FAST                  Forces the Get_Next_Match routine
  59.                   to be inline. This gives additional
  60. !                 percents of speedup on some machines
  61. !                 using some compilers (depends on
  62. !                 the number of registers, register
  63. !                 allocation strategy and subroutine call
  64. !                 overhead).
  65.       o __TURBOC__            For compiling under TURBO C
  66.       o __i386__              When compiling under GNU C causes
  67.                   some fixed register allocations,
  68. ***************
  69. *** 38,46 ****
  70.                   4.3).
  71.   
  72.   Please! If your computer supports the string operations, try to write
  73. ! "asm" instructions (GNU style) which realize the right-to-left memory
  74. ! comparison (s1, s2, length) in minimum number of clock cycles.
  75. ! If a noticeable (5% or more) speedup is gained, please send me a message.
  76.   
  77.   Other preprocessor symbols (DEBUG, GATHER_STAT) are for internal use
  78.   only.
  79. --- 40,49 ----
  80.                   4.3).
  81.   
  82.   Please! If your computer supports the string operations, try to write
  83. ! "asm" instructions (GNU style) which realize the memory comparison
  84. ! "(s1, s2, maxlength) --> matched length" in the minimum number of clock
  85. ! cycles.  If a noticeable (5% or more) speedup is gained, please send
  86. ! me a message.
  87.   
  88.   Other preprocessor symbols (DEBUG, GATHER_STAT) are for internal use
  89.   only.
  90. ***************
  91. *** 126,131 ****
  92. --- 129,136 ----
  93.   gif =   0 0 0 0 2 60 0 0        # This is NOT! optimal data
  94.                   # for GIF files
  95.   doc=0 0 1 2 7 16 36 0           # The sample was gcc.lp
  96. + greedy2=0 1 1 2 5 8 11 34       #
  97. + 
  98.   # End of file
  99.   ---------- cut here -----------
  100.   
  101. ***************
  102. *** 144,150 ****
  103.   ------------------- BUGS ----------------------------
  104.   
  105.   Please send descriptions of found bugs, incompatibilities, etc.  to
  106. ! leo@s514.ipmce.su.  MS-DOS version will not be supported in future
  107.   versions !!  (If they will be :-) )
  108.   
  109.   ------------ SPEED & COMPRESSION RATE ---------------
  110. --- 149,155 ----
  111.   ------------------- BUGS ----------------------------
  112.   
  113.   Please send descriptions of found bugs, incompatibilities, etc.  to
  114. ! leo@ipmce.su.  MS-DOS version might not be supported in future
  115.   versions !!  (If they will be :-) )
  116.   
  117.   ------------ SPEED & COMPRESSION RATE ---------------
  118. *** distribution/encode.c    Thu Jul 16 15:20:58 1992
  119. --- encode.c    Thu Jul 30 13:19:42 1992
  120. ***************
  121. *** 6,13 ****
  122.   /* for future versions ?... */
  123.   
  124.   #define LENGTH_OFFSET   256
  125. ! #define EncodeLiteral(l)        EncodeChar(l)
  126. ! #define EncodeLength(l)         EncodeChar(l + LENGTH_OFFSET)
  127.   
  128.   /*
  129.    * Freezes stdin to stdout
  130. --- 6,13 ----
  131.   /* for future versions ?... */
  132.   
  133.   #define LENGTH_OFFSET   256
  134. ! #define EncodeLiteral(l)        EncodeChar((int)l)
  135. ! #define EncodeLength(l)         EncodeChar((int)l + LENGTH_OFFSET)
  136.   
  137.   /*
  138.    * Freezes stdin to stdout
  139. ***************
  140. *** 15,23 ****
  141.   
  142.   void freeze ()
  143.   {
  144. !     register us_t i, len, r, s;
  145. !     register short c;
  146. !     int greedy_threshold = CHAIN_THRESHOLD / (3 * greedy + 3);
  147.       putchar(MAGIC1);
  148.       putchar(MAGIC2_2);
  149.   
  150. --- 15,21 ----
  151.   
  152.   void freeze ()
  153.   {
  154. !     register int i, len, r, s, c;
  155.       putchar(MAGIC1);
  156.       putchar(MAGIC2_2);
  157.   
  158. ***************
  159. *** 65,78 ****
  160.                   fprintf(stderr, "'%s'\n",
  161.                       pr_char(text_buf[r]));
  162.   #endif /* DEBUG */
  163. !         } else if (match_length >= greedy_threshold) {
  164.   /* GREEDY parsing (compression rate 1.5% worse, but 40% faster) */
  165.   
  166. !             EncodeLength((us_t) (match_length - THRESHOLD));
  167. !             EncodePosition((us_t)match_position);
  168.   
  169.           } else {
  170. !             register us_t orig_length, orig_position, oldchar;
  171.   
  172.   /* This fragment (delayed coding, non-greedy) is due to ideas of
  173.       Jan Mark Wams' <jms@cs.vu.nl> COMIC:
  174. --- 63,77 ----
  175.                   fprintf(stderr, "'%s'\n",
  176.                       pr_char(text_buf[r]));
  177.   #endif /* DEBUG */
  178. !         } else if (greedy) {
  179.   /* GREEDY parsing (compression rate 1.5% worse, but 40% faster) */
  180.   
  181. !             EncodeLength(match_length - THRESHOLD);
  182. !             EncodePosition(match_position);
  183.   
  184.           } else {
  185. !             register int orig_length, orig_position;
  186. !             register us_t oldchar;
  187.   
  188.   /* This fragment (delayed coding, non-greedy) is due to ideas of
  189.       Jan Mark Wams' <jms@cs.vu.nl> COMIC:
  190. ***************
  191. *** 88,96 ****
  192.               if (match_length > len) match_length = len;
  193.   
  194.               if (orig_length >= match_length) {
  195. !                 EncodeLength((us_t)
  196. !                     (orig_length - THRESHOLD));
  197. !                 EncodePosition((us_t)orig_position);
  198.   #ifdef DEBUG
  199.                   match_position = orig_position;
  200.   #endif  /* DEBUG */
  201. --- 87,94 ----
  202.               if (match_length > len) match_length = len;
  203.   
  204.               if (orig_length >= match_length) {
  205. !                 EncodeLength(orig_length - THRESHOLD);
  206. !                 EncodePosition(orig_position);
  207.   #ifdef DEBUG
  208.                   match_position = orig_position;
  209.   #endif  /* DEBUG */
  210. ***************
  211. *** 106,113 ****
  212.                   EncodeLength(match_length - THRESHOLD);
  213.                   EncodePosition(match_position);
  214.               }
  215. ! #ifdef DEBUG
  216.               refers_out ++;
  217.               if (verbose) {
  218.                   register short pos =
  219.                       (r - 1 - match_position) & (N2 - 1),
  220. --- 104,114 ----
  221.                   EncodeLength(match_length - THRESHOLD);
  222.                   EncodePosition(match_position);
  223.               }
  224. ! 
  225. ! #if defined(GATHER_STAT) || defined (DEBUG)
  226.               refers_out ++;
  227. + #endif
  228. + #ifdef DEBUG
  229.               if (verbose) {
  230.                   register short pos =
  231.                       (r - 1 - match_position) & (N2 - 1),
  232. ***************
  233. *** 159,167 ****
  234.        */
  235.       if(quiet != 1) {
  236.   #ifdef GATHER_STAT
  237. !     fprintf(stderr, "Average number of steps: ");
  238. !     fprintf(stderr, "%d.%02d\n", (int) (node_steps / node_matches),
  239. !             (int)((node_steps * 100 / node_matches) % 100));
  240.   #endif
  241.   #ifdef DEBUG
  242.       fprintf( stderr,
  243. --- 160,171 ----
  244.        */
  245.       if(quiet != 1) {
  246.   #ifdef GATHER_STAT
  247. !     fprintf(stderr, "Average number of compares per matching: %d.%02d\n",
  248. !         (int) (node_compares / node_matches),
  249. !         (int)((node_compares * 100 / node_matches) % 100));
  250. !     fprintf(stderr, "Average number of prolongations per compare: %d.%02d\n",
  251. !         (int) (node_prolongations / node_compares),
  252. !         (int)((node_prolongations * 100 / node_compares) % 100));
  253.   #endif
  254.   #ifdef DEBUG
  255.       fprintf( stderr,
  256. *** distribution/freeze.1    Wed Feb 26 14:40:06 1992
  257. --- freeze.1    Mon Aug 17 17:02:13 1992
  258. ***************
  259. *** 62,70 ****
  260.   If the
  261.   .B \-g
  262.   flag is given, a slightly less powerful (compression
  263. ! rate is 1.5% less), but 40% faster heuristic is used. The more times this
  264. ! flag is present, the faster program works and the less compression
  265. ! rate is. This flag is quite useful when freezing bitmaps.
  266.   .PP
  267.   If the
  268.   .B \-f
  269. --- 62,70 ----
  270.   If the
  271.   .B \-g
  272.   flag is given, a slightly less powerful (compression
  273. ! rate is 1.5% less), but 40% faster heuristic is used. This flag may be
  274. ! used twice (this mode is quite useful when freezing bitmaps) for
  275. ! additional speedup.
  276.   .PP
  277.   If the
  278.   .B \-f
  279. *** distribution/freeze.c    Thu Jul 16 15:20:59 1992
  280. --- freeze.c    Thu Jul 30 13:27:11 1992
  281. ***************
  282. *** 95,102 ****
  283.   short debug = 0;
  284.   short verbose = 0;
  285.   char * pr_char();
  286. ! long symbols_out = 0, refers_out = 0;
  287.   #endif /* DEBUG */
  288.   
  289.   /* Do not sleep when freeze works :-) */
  290.   long indc_count, indc_threshold;
  291. --- 95,106 ----
  292.   short debug = 0;
  293.   short verbose = 0;
  294.   char * pr_char();
  295. ! long symbols_out = 0;
  296.   #endif /* DEBUG */
  297. + 
  298. + #if defined(GATHER_STAT) || defined(DEBUG)
  299. + long refers_out = 0;
  300. + #endif
  301.   
  302.   /* Do not sleep when freeze works :-) */
  303.   long indc_count, indc_threshold;
  304. *** distribution/freeze.h    Thu Jul 16 15:20:59 1992
  305. --- freeze.h    Wed Jul 29 21:54:52 1992
  306. ***************
  307. *** 4,13 ****
  308. --- 4,21 ----
  309.   #include <sys/stdtypes.h>
  310.   #else   /* SUN4 */
  311.   # ifndef getc
  312. + #  ifdef m88k            /* Green Hill C library bug. */
  313. + #   define getc(p)         (--(p)->_cnt < 0 ? __filbuf(p) : (int) *(p)->_ptr++)
  314. + #  else
  315.   #   define getc(p)         (--(p)->_cnt < 0 ? _filbuf(p) : (int) *(p)->_ptr++)
  316. + #  endif
  317.   # endif
  318.   # ifndef putc
  319. + #  ifdef m88k            /* Green Hill C library bug. */
  320. + #   define putc(x, p)      (--(p)->_cnt < 0 ? __flsbuf((unsigned char) (x), (p)) : (int) (*(p)->_ptr++ = (unsigned char) (x)))
  321. + #  else
  322.   #   define putc(x, p)      (--(p)->_cnt < 0 ? _flsbuf((unsigned char) (x), (p)) : (int) (*(p)->_ptr++ = (unsigned char) (x)))
  323. + #  endif
  324.   # endif
  325.   #endif  /* SUN4 */
  326.   
  327. ***************
  328. *** 87,95 ****
  329.   # else /* TOS */
  330.   #  include <ext.h>
  331.   # endif  /* MSDOS */
  332. - #if !defined(SIGTYPE)
  333. - #define SIGTYPE void
  334. - #endif
  335.   #endif /* __TURBOC__ */
  336.   
  337.   typedef unsigned short us_t;
  338. --- 95,100 ----
  339. ***************
  340. *** 136,146 ****
  341.   extern short debug;
  342.   extern short verbose;
  343.   extern char * pr_char();
  344. ! extern long symbols_out, refers_out;
  345.   #endif /* DEBUG */
  346.   
  347. ! #ifdef GATHER_STAT
  348. ! extern long node_steps, node_matches;
  349.   #endif
  350.   
  351.   extern short DecodeChar(), DecodePosition(), GetNBits();
  352. --- 141,151 ----
  353.   extern short debug;
  354.   extern short verbose;
  355.   extern char * pr_char();
  356. ! extern long symbols_out;
  357.   #endif /* DEBUG */
  358.   
  359. ! #if defined(GATHER_STAT) || defined(DEBUG)
  360. ! extern long refers_out;
  361.   #endif
  362.   
  363.   extern short DecodeChar(), DecodePosition(), GetNBits();
  364. ***************
  365. *** 177,179 ****
  366. --- 182,188 ----
  367.   #endif
  368.   
  369.   extern char *strchr(), *strrchr();
  370. + 
  371. + #ifndef SIGTYPE
  372. + #define SIGTYPE void
  373. + #endif
  374. *** distribution/huf.c    Wed Feb 26 14:39:48 1992
  375. --- huf.c    Thu Jul 30 17:55:36 1992
  376. ***************
  377. *** 76,83 ****
  378.   
  379.   void reconst ()
  380.   {
  381. !     register us_t i, j, k;
  382. !     register us_t f;
  383.   
  384.   #ifdef DEBUG
  385.       if (quiet < 0)
  386. --- 76,83 ----
  387.   
  388.   void reconst ()
  389.   {
  390. !     register int i, j, k;
  391. !     register int f;
  392.   
  393.   #ifdef DEBUG
  394.       if (quiet < 0)
  395. ***************
  396. *** 130,139 ****
  397.   /* Updates given code's frequency, and updates tree */
  398.   
  399.   void update (c)
  400. !     us_t c;
  401.   {
  402.       register us_t *p;
  403. !     register us_t i, j, k, l;
  404.   
  405.       if (freq[r] == MAX_FREQ) {
  406.           reconst();
  407. --- 130,139 ----
  408.   /* Updates given code's frequency, and updates tree */
  409.   
  410.   void update (c)
  411. !     register int c;
  412.   {
  413.       register us_t *p;
  414. !     register int i, j, k, l;
  415.   
  416.       if (freq[r] == MAX_FREQ) {
  417.           reconst();
  418. ***************
  419. *** 168,177 ****
  420.   /* Encodes the literal or the length information */
  421.   
  422.   void EncodeChar (c)
  423. !     us_t c;
  424.   {
  425.       ul_t i;
  426. !     register us_t j, k;
  427.   
  428.       i = 0;
  429.       j = 0;
  430. --- 168,177 ----
  431.   /* Encodes the literal or the length information */
  432.   
  433.   void EncodeChar (c)
  434. !     int c;
  435.   {
  436.       ul_t i;
  437. !     register int j, k;
  438.   
  439.       i = 0;
  440.       j = 0;
  441. ***************
  442. *** 202,208 ****
  443.   /* Encodes the position information */
  444.   
  445.   void EncodePosition (c)
  446. !     register us_t c;
  447.   {
  448.       register us_t i;
  449.   
  450. --- 202,208 ----
  451.   /* Encodes the position information */
  452.   
  453.   void EncodePosition (c)
  454. !     register int c;
  455.   {
  456.       register us_t i;
  457.   
  458. ***************
  459. *** 221,227 ****
  460.   
  461.   short DecodeChar ()
  462.   {
  463. !     register us_t c;
  464.       c = son[r];
  465.   
  466.       /* trace from root to leaf,
  467. --- 221,227 ----
  468.   
  469.   short DecodeChar ()
  470.   {
  471. !     register int c;
  472.       c = son[r];
  473.   
  474.       /* trace from root to leaf,
  475. *** distribution/lz.c    Thu Jul 16 15:20:59 1992
  476. --- lz.c    Thu Aug  6 18:16:58 1992
  477. ***************
  478. *** 8,16 ****
  479.   /*----------------------------------------------------------------------*/
  480.   
  481.   uc_t    text_buf[N2 + F2 - 1];          /* cyclic buffer with an overlay */
  482. ! us_t    match_position, match_length;   /* current characteristics of a
  483.                           matched pattern */
  484. ! us_t    chain_length;                   /* max_chain_length ==
  485.                           CHAIN_THRESHOLD / greedy */
  486.   
  487.   
  488. --- 8,16 ----
  489.   /*----------------------------------------------------------------------*/
  490.   
  491.   uc_t    text_buf[N2 + F2 - 1];          /* cyclic buffer with an overlay */
  492. ! int     match_position, match_length;   /* current characteristics of a
  493.                           matched pattern */
  494. ! int     chain_length;                   /* max_chain_length ==
  495.                           CHAIN_THRESHOLD / greedy */
  496.   
  497.   
  498. ***************
  499. *** 45,51 ****
  500.   #endif  /* __XENIX__ */
  501.   
  502.   #ifdef GATHER_STAT
  503. ! long node_steps, node_matches;
  504.   #endif  /* GATHER_STAT */
  505.   
  506.   /* Initialize the data structures and allocate memory, if needed.
  507. --- 45,51 ----
  508.   #endif  /* __XENIX__ */
  509.   
  510.   #ifdef GATHER_STAT
  511. ! long node_matches, node_compares, node_prolongations;
  512.   #endif  /* GATHER_STAT */
  513.   
  514.   /* Initialize the data structures and allocate memory, if needed.
  515. ***************
  516. *** 57,63 ****
  517.   {
  518.       hash_t i;
  519.   #ifdef GATHER_STAT
  520. !     node_steps = node_matches = 0;
  521.   #endif  /* GATHER_STAT */
  522.   
  523.   #ifdef __TURBOC__
  524. --- 57,63 ----
  525.   {
  526.       hash_t i;
  527.   #ifdef GATHER_STAT
  528. !     node_matches = node_compares = node_prolongations = 0;
  529.   #endif  /* GATHER_STAT */
  530.   
  531.   #ifdef __TURBOC__
  532. ***************
  533. *** 74,80 ****
  534.           nextof(i) = NIL;
  535.       for (i = 0; i < sizeof(prev)/sizeof(*prev); i++ )
  536.           prev[i] = NIL;
  537. !     chain_length = greedy ? CHAIN_THRESHOLD / greedy : 0;
  538.   }
  539.   
  540.   /* Get the longest (longer than `match_length' when entering in subroutine)
  541. --- 74,89 ----
  542.           nextof(i) = NIL;
  543.       for (i = 0; i < sizeof(prev)/sizeof(*prev); i++ )
  544.           prev[i] = NIL;
  545. !     switch (greedy) {
  546. !     case 0:
  547. !         chain_length = CHAIN_THRESHOLD;
  548. !         break;
  549. !     case 1:
  550. !         chain_length = 3;
  551. !         break;
  552. !     default:
  553. !         chain_length = 1;
  554. !     }
  555.   }
  556.   
  557.   /* Get the longest (longer than `match_length' when entering in subroutine)
  558. ***************
  559. *** 81,138 ****
  560.       nearest match of the string beginning in text_buf[r]
  561.       to the cyclic buffer. Result (length & position) is returned
  562.       in correspondent global variables (`match_length' &
  563. !     `match_position'). Unchanged `match_length' denotes failure.
  564.   */
  565.   
  566.   #ifndef FAST
  567.   void get_next_match (r)
  568. !     us_t r;
  569.   {
  570. !     register us_t p = r;
  571.       register int m;
  572.       register uc_t  *key FIX_SI, *pattern FIX_DI;
  573.       int     chain_count = chain_length;
  574.   #ifdef GATHER_STAT
  575.       node_matches++;
  576.   #endif
  577. !     key = text_buf + r;
  578. !     do {
  579.           do {
  580. !             /* From ZIP 1.0 by J.-L. Gailly et al. */
  581.   
  582. !             if ((p = nextof(p)) == NIL ||
  583. !                 (greedy && !chain_count--))
  584. !                 return;
  585.   
  586. !             pattern = text_buf + p;
  587.   
  588.   #ifdef GATHER_STAT
  589. !         node_steps++;
  590.   #endif
  591.   
  592. !             MATCHING;
  593.   
  594. !         } while NOT_YET;
  595.   
  596. !         for (m = match_length;
  597. !             ++m < F2 && key[m] == pattern[m]; );
  598.   
  599. -         match_length = m;
  600. -         match_position = ((r - p) & (N2 - 1)) - 1;
  601. -     } while (m < F2);
  602. - 
  603.   /* There are two equal F-char sequences, the oldest one must be
  604.       deleted from the list.
  605.   */
  606.   
  607. - 
  608.   #ifdef DEBUG
  609.       if (verbose)
  610.           fprintf(stderr, "Replacing node: %d -> %d\n", p, r);
  611.   #endif
  612. !     nextof(prev[p]) = nextof(p);
  613. !     prev[nextof(p)] = prev[p];
  614. !     prev[p] = NIL;  /* remove p, it is further than r */
  615. !     return;
  616.   }
  617.   #endif
  618. --- 90,172 ----
  619.       nearest match of the string beginning in text_buf[r]
  620.       to the cyclic buffer. Result (length & position) is returned
  621.       in correspondent global variables (`match_length' &
  622. !     `match_position'). Unchanged `match_length' denotes failure and
  623. !     `match_position' contains garbage !!
  624. !     In order to achieve faster operation, `match_length' is shifted
  625. !     down to F2.
  626.   */
  627.   
  628.   #ifndef FAST
  629.   void get_next_match (r)
  630. !     int r;
  631.   {
  632. !     register int p = r;
  633.       register int m;
  634. +     register uc_t lastbyte;
  635.       register uc_t  *key FIX_SI, *pattern FIX_DI;
  636.       int     chain_count = chain_length;
  637. + 
  638.   #ifdef GATHER_STAT
  639.       node_matches++;
  640.   #endif
  641. ! 
  642. !     key = text_buf + r + F2;
  643. !     match_length -= F2;
  644. ! 
  645. !     for(;chain_count--;) {
  646. ! 
  647. !         lastbyte = key[match_length];
  648. ! 
  649.           do {
  650. !             pattern = text_buf + match_length + F2;
  651.   
  652. !             do {
  653. !                 if ((p = nextof(p)) == NIL) {
  654. !                     match_length += F2;
  655. !                     match_position = ((r - match_position) & (N2 - 1)) - 1;
  656. !                     return;
  657. !                 }
  658. !             } while (pattern[p] != lastbyte);
  659.   
  660. !             pattern = text_buf + p + F2;
  661.   
  662.   #ifdef GATHER_STAT
  663. !         node_compares++;
  664.   #endif
  665.   
  666. !             for (m = -F2; key[m] == pattern[m] && ++m < 0;);
  667.   
  668. !         } while (m < match_length);
  669.   
  670. !         if (m == 0) {
  671.   
  672.   /* There are two equal F-char sequences, the oldest one must be
  673.       deleted from the list.
  674.   */
  675.   
  676.   #ifdef DEBUG
  677.       if (verbose)
  678.           fprintf(stderr, "Replacing node: %d -> %d\n", p, r);
  679.   #endif
  680. !             nextof(prev[p]) = nextof(p);
  681. !             prev[nextof(p)] = prev[p];
  682. !             prev[p] = NIL;  /* remove p, it is further than r */
  683. !             match_length = F2;
  684. !             match_position = ((r - p) & (N2 - 1)) - 1;
  685. !             return;
  686. !         }
  687. ! 
  688. !         match_length = m;       /* remember new results */
  689. !         match_position = p;
  690. ! 
  691. ! #ifdef GATHER_STAT
  692. !         node_prolongations++;
  693. ! #endif
  694. !     }
  695. ! 
  696. !     /* chain length exceeded */
  697. ! 
  698. !     match_length += F2;
  699. !     match_position = ((r - match_position) & (N2 - 1)) - 1;
  700.   }
  701.   #endif
  702. *** distribution/lz.h    Thu Jul 16 15:20:59 1992
  703. --- lz.h    Mon Aug 17 17:02:11 1992
  704. ***************
  705. *** 39,45 ****
  706.   #define array_size      (N2 + 1 + (1L << BITS))
  707.   
  708.   extern hash_t prev[];
  709. ! extern us_t      match_position, match_length, chain_length;
  710.   
  711.   #ifndef __XENIX__
  712.   #define nextof(i)       next[i]
  713. --- 39,45 ----
  714.   #define array_size      (N2 + 1 + (1L << BITS))
  715.   
  716.   extern hash_t prev[];
  717. ! extern int       match_position, match_length, chain_length;
  718.   
  719.   #ifndef __XENIX__
  720.   #define nextof(i)       next[i]
  721. ***************
  722. *** 75,81 ****
  723. --- 75,95 ----
  724.          nextof(prev[n]) = NIL;\
  725.          prev[n] = NIL;\
  726.   }
  727. + /* Hash function */
  728.   
  729. + #define hash(p)\
  730. +     ((hash_t)(p)[0] + ((hash_t)(p)[1] << LEN0) +\
  731. +     ((hash_t)(p)[2] << LEN1))
  732. + 
  733. + #ifdef FASTHASH
  734. + #define hashof(p)\
  735. +     (((p)[0] != (p)[1] ? hash(p) : hash(p) + hash((p) + 3)) &\
  736. +     ((1L << BITS) - 1))
  737. + #else
  738. + #define hashof(p)\
  739. +     (hash(p) & ((1L << BITS) - 1))
  740. + #endif
  741. + 
  742.   /* Inserting of a node `r' into hashed linked list: `r' becomes
  743.       the head of list.
  744.   */
  745. ***************
  746. *** 85,92 ****
  747.       register hash_t p; register us_t first_son;\
  748.       register uc_t  *key;\
  749.       key = &text_buf[r];\
  750. !     p = N2 + 1 + (((hash_t)key[0] + ((hash_t)key[1] << LEN0) +\
  751. !             ((hash_t)key[2] << LEN1)) & ((1L << BITS) - 1));\
  752.       first_son = nextof(p);\
  753.       nextof(r) = first_son;\
  754.       nextof(p) = r;\
  755. --- 99,105 ----
  756.       register hash_t p; register us_t first_son;\
  757.       register uc_t  *key;\
  758.       key = &text_buf[r];\
  759. !     p = N2 + 1 + hashof(key);\
  760.       first_son = nextof(p);\
  761.       nextof(r) = first_son;\
  762.       nextof(p) = r;\
  763. ***************
  764. *** 133,161 ****
  765.   #define FIX_DI
  766.   #endif
  767.   
  768. ! #ifndef DO_INLINE
  769.   
  770. ! /* This statement is due to ideas of Boyer and Moore: */
  771. ! /* Is somewhere an optimizing compiler which can vectorize this? ;-) */
  772.   
  773. ! #define MATCHING for (m = match_length; m >= 0 && key[m] == pattern[m]; m--)
  774. ! #define NOT_YET (m >= 0)
  775. ! 
  776. ! #else
  777. ! 
  778. ! /* Hope that memcmp will be intrinsic (Microsoft C).
  779.   */
  780. - #define MATCHING
  781. - #define NOT_YET (key[match_length] != pattern[match_length] || memcmp(key, pattern, match_length))
  782.   
  783. - #endif
  784. - 
  785. - #define CHAIN_THRESHOLD (F2 * 3)
  786. - 
  787. - #ifdef  FAST
  788. - /* Simple inline replacement for get_next_match; they match
  789. - literally except return --> goto quote(leave)l. No obfuscations !! */
  790. - 
  791.   #if defined(__STDC__) || defined (__TURBOC__)
  792.   #define LEAVE(num) leave##num
  793.   #else
  794. --- 146,159 ----
  795.   #define FIX_DI
  796.   #endif
  797.   
  798. ! #define CHAIN_THRESHOLD F2
  799.   
  800. ! #ifdef  FAST
  801.   
  802. ! /* Simple inline replacement for get_next_match; they match almost
  803. ! literally except return --> goto quote(leave)l. No obfuscations !!
  804.   */
  805.   
  806.   #if defined(__STDC__) || defined (__TURBOC__)
  807.   #define LEAVE(num) leave##num
  808.   #else
  809. ***************
  810. *** 163,178 ****
  811.   #define LEAVE(num) quote(leave)num
  812.   #endif
  813.   
  814. ! #define Get_Next_Match(r,l) {register us_t p=r;register int m;\
  815. ! register uc_t *key FIX_SI, *pattern FIX_DI;int chain_count=chain_length;\
  816. ! key=text_buf+r;do{ do{ if((p=nextof(p))==NIL||(greedy &&\
  817. ! !chain_count--))goto LEAVE(l);pattern=text_buf+p;MATCHING;}while NOT_YET;\
  818. ! for(m=match_length;++m<F2&&key[m]==pattern[m];);\
  819. ! match_length=m;match_position=((r-p)&(N2-1))-1;}while(m<F2);\
  820. ! nextof(prev[p])=nextof(p);prev[nextof(p)]=prev[p];prev[p]=NIL;LEAVE(l):;}
  821.   
  822.   #else
  823.   
  824.   #define Get_Next_Match(r,l)     get_next_match(r)
  825.   
  826.   #endif
  827. --- 161,187 ----
  828.   #define LEAVE(num) quote(leave)num
  829.   #endif
  830.   
  831. ! #define m_l match_length
  832. ! #define t_b text_buf
  833. ! #define m_p match_position
  834.   
  835. + #define Get_Next_Match(r,l) {register p=r;register m;register uc_t lb;\
  836. + register uc_t *key FIX_SI, *pat FIX_DI;int cc=chain_length;\
  837. + key=t_b+r+F2;m_l-=F2;for(;cc--;){lb=key[m_l];do{pat=t_b+m_l+F2;do{\
  838. + if((p=nextof(p))==NIL){m_p=((r-m_p)&(N2-1))-1;m_l+=F2;goto LEAVE(l);}\
  839. + }while(pat[p]!=lb);pat=t_b+p+F2;for(m= -F2;key[m]==pat[m]&&++m<0;);\
  840. + }while(m<m_l);if(m==0){nextof(prev[p])=nextof(p);prev[nextof(p)]=prev[p];\
  841. + prev[p]=NIL;m_l=F2;m_p=((r-p)&(N2-1))-1;goto LEAVE(l);}m_l=m;m_p=p;}\
  842. + m_p=((r-m_p)&(N2-1))-1;m_l+=F2;LEAVE(l):;}
  843. + 
  844.   #else
  845.   
  846.   #define Get_Next_Match(r,l)     get_next_match(r)
  847. + extern void get_next_match();
  848.   
  849.   #endif
  850. + 
  851. + #ifdef GATHER_STAT
  852. + extern long node_matches, node_compares, node_prolongations;
  853. + #endif
  854. + 
  855. *** distribution/makefile    Thu Jul 16 15:21:00 1992
  856. --- makefile    Thu Jul 30 13:27:39 1992
  857. ***************
  858. *** 4,14 ****
  859.       @echo ''
  860.       @echo 'Please indicate the system to make Freeze for.'
  861.       @echo 'Possible choices are: bsd, sysv, x286, sun4, hpux,'
  862. !     @echo 'generic.'
  863.       @echo ''
  864.   
  865. ! DEST          = /usr/local/bin
  866. ! MANDEST       = /usr/local/man/man1
  867.   SEC           = 1
  868.   
  869.   HDRS          = bitio.h\
  870. --- 4,19 ----
  871.       @echo ''
  872.       @echo 'Please indicate the system to make Freeze for.'
  873.       @echo 'Possible choices are: bsd, sysv, x286, sun4, hpux,'
  874. !     @echo 'm88k, sysv-longnames, generic.'
  875.       @echo ''
  876. +     @echo 'sysv-longnames is a target for SysV machines which allow'
  877. +     @echo 'filenames to be more than 14 characters long.'
  878. +     @echo ''
  879.   
  880. ! # Added the prefix macro, so that it was easier to change installation place.
  881. ! prefix        = /usr/local
  882. ! DEST          = $(prefix)/bin
  883. ! MANDEST       = $(prefix)/man/man1
  884.   SEC           = 1
  885.   
  886.   HDRS          = bitio.h\
  887. ***************
  888. *** 24,30 ****
  889.   OPTIONS       = -DCOMPAT
  890.   
  891.   LINTFLAGS     = -DBITS=15 -DSIGTYPE=void -DCOMPAT -DDEBUG\
  892. !         -DGATHER_STAT -x -DFAST
  893.   
  894.   MAKEFILE      = makefile
  895.   
  896. --- 29,35 ----
  897.   OPTIONS       = -DCOMPAT
  898.   
  899.   LINTFLAGS     = -DBITS=15 -DSIGTYPE=void -DCOMPAT -DDEBUG\
  900. !         -DGATHER_STAT -DUTIMES -x
  901.   
  902.   MAKEFILE      = makefile
  903.   
  904. ***************
  905. *** 74,80 ****
  906.           $(CC) $(CFLAGS) $(LDFLAGS) -o statist statist.o lz.o $(LIBS)
  907.   
  908.   clobber:        clean
  909. !         rm -f $(PROGRAM) statist *.man
  910.   
  911.   clean:;         rm -f *.o *.b .,* core *.out
  912.   
  913. --- 79,85 ----
  914.           $(CC) $(CFLAGS) $(LDFLAGS) -o statist statist.o lz.o $(LIBS)
  915.   
  916.   clobber:        clean
  917. !         rm -f $(PROGRAM) statist *.man \#* *~
  918.   
  919.   clean:;         rm -f *.o *.b .,* core *.out
  920.   
  921. ***************
  922. *** 91,96 ****
  923. --- 96,102 ----
  924.           -strip $@
  925.           -mcs -d $@
  926.           -ln -f $@ $(DEST)/melt
  927. +         -ln -f $@ $(DEST)/unfreeze
  928.           -ln -f $@ $(DEST)/fcat
  929.   
  930.   $(DEST)/statist: statist
  931. ***************
  932. *** 103,110 ****
  933. --- 109,122 ----
  934.           cp freeze.1 $@
  935.           chmod +r $@
  936.           -ln -f $@ $(MANDEST)/melt.$(SEC)
  937. +         -ln -f $@ $(MANDEST)/unfreeze.$(SEC)
  938.           -ln -f $@ $(MANDEST)/fcat.$(SEC)
  939. + # This is much better for places which keep preformated manpages.
  940. + #        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/melt.$(SEC)
  941. + #        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/unfreeze.$(SEC)
  942. + #        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/fcat.$(SEC)
  943.   
  944. + 
  945.   $(MANDEST)/statist.$(SEC): statist.1
  946.           cp statist.1 $@
  947.           chmod +r $@
  948. ***************
  949. *** 111,125 ****
  950.   
  951.   bsd:
  952.           make prog CFLAGS="-O -DBSD -DUTIMES -DBITS=16\
  953. !         -DFAST -DSIGTYPE=void" CC=$(CC)
  954.   
  955. ! hpux:
  956.           make prog CFLAGS="-O -DLONGNAMES -DBITS=16\
  957. !         -DFAST -DSIGTYPE=void" CC=$(CC)
  958.   
  959.   sysv:
  960.           make prog CFLAGS="-O -DBITS=16 -DFAST -DSIGTYPE=void"\
  961. !         LIBS="-lc_s" CC=$(CC)
  962.   
  963.   x286:
  964.           make prog CC=cc CFLAGS="-Ox -Ml2 -DBITS=16 -DFAST\
  965. --- 123,141 ----
  966.   
  967.   bsd:
  968.           make prog CFLAGS="-O -DBSD -DUTIMES -DBITS=16\
  969. !         -DFAST -DSIGTYPE=void" CC="$(CC)"
  970.   
  971. ! sysv-longnames:
  972.           make prog CFLAGS="-O -DLONGNAMES -DBITS=16\
  973. !         -DFAST -DSIGTYPE=void" CC="$(CC)"
  974.   
  975. + hpux:        sysv-longnames
  976. + 
  977. + m88k:        sysv-longnames
  978. + 
  979.   sysv:
  980.           make prog CFLAGS="-O -DBITS=16 -DFAST -DSIGTYPE=void"\
  981. !         LIBS="-lc_s" CC="$(CC)"
  982.   
  983.   x286:
  984.           make prog CC=cc CFLAGS="-Ox -Ml2 -DBITS=16 -DFAST\
  985. ***************
  986. *** 129,140 ****
  987.           make install MANDEST=/usr/man/man.C SEC=C
  988.   
  989.   generic:
  990. !         make prog CFLAGS="-O -DBITS=16 -DFAST -DSIGTYPE=int" CC=$(CC)
  991.   
  992.   sun4:
  993. !         make prog CC=cc CFLAGS="-O4 -DBSD -DSUN4 -DSIGTYPE=void\
  994. !         -DUTIMES -DBITS=16 -DFAST"
  995. ! 
  996.   
  997.   ###
  998.   bitio.o: freeze.h compat.h bitio.h
  999. --- 145,155 ----
  1000.           make install MANDEST=/usr/man/man.C SEC=C
  1001.   
  1002.   generic:
  1003. !         make prog CFLAGS="-O -DBITS=16 -DFAST -DSIGTYPE=int" CC="$(CC)"
  1004.   
  1005.   sun4:
  1006. !         make prog CC="cc" CFLAGS="-O4 -DBSD -DSUN4 -DSIGTYPE=void\
  1007. !         -DUTIMES -DBITS=16"
  1008.   
  1009.   ###
  1010.   bitio.o: freeze.h compat.h bitio.h
  1011. *** distribution/patchlevel.h    Thu Jul 16 15:21:00 1992
  1012. --- patchlevel.h    Mon Aug 17 16:48:47 1992
  1013. ***************
  1014. *** 1,2 ****
  1015. ! #define PATCHLEVEL 4
  1016. ! #define PATCHDATE "6/3/92"
  1017. --- 1,2 ----
  1018. ! #define PATCHLEVEL 5
  1019. ! #define PATCHDATE "17/8/92"
  1020. *** distribution/statist.c    Thu Jul 16 15:20:52 1992
  1021. --- statist.c    Thu Jul 30 13:43:21 1992
  1022. ***************
  1023. *** 113,118 ****
  1024. --- 113,120 ----
  1025.   
  1026.       for (c = 1; c <= 6; c++) bits[c] = 0;
  1027.   
  1028. +     printf("Non-monotonities are in: ");
  1029. + 
  1030.       for(c = 0; c < N_POS; c++) {
  1031.           j = 0;
  1032.           k = c;
  1033. ***************
  1034. *** 119,134 ****
  1035.           do j++; while ((k = prnt[k]) != r);
  1036.           if (j <= 6)
  1037.               bits[j]++;
  1038. !         if (j < pr)
  1039.               f += pr - j;
  1040. !         else
  1041.               pr = j;
  1042.       }
  1043.   
  1044.       k = bits[1] + bits[2] + bits[3] + bits[4] +
  1045.       bits[5] + bits[6];
  1046.   
  1047. !     k = 62 - k;     /* free variable length codes for 7 & 8 bits */
  1048.   
  1049.       j = 128 * bits[1] + 64 * bits[2] + 32 * bits[3] +
  1050.       16 * bits[4] + 8 * bits[5] + 4 * bits[6];
  1051. --- 121,142 ----
  1052.           do j++; while ((k = prnt[k]) != r);
  1053.           if (j <= 6)
  1054.               bits[j]++;
  1055. !         if (j < pr) {
  1056.               f += pr - j;
  1057. !             printf("%d, ", c);
  1058. ! 
  1059. !         } else
  1060.               pr = j;
  1061.       }
  1062. +     if(f == 0)
  1063. +         printf("\b\b\b\babsent.\n");
  1064. +     else
  1065. +         printf("\b\b.\n");
  1066.   
  1067.       k = bits[1] + bits[2] + bits[3] + bits[4] +
  1068.       bits[5] + bits[6];
  1069.   
  1070. !     k = N_POS - k;  /* free variable length codes for 7 & 8 bits */
  1071.   
  1072.       j = 128 * bits[1] + 64 * bits[2] + 32 * bits[3] +
  1073.       16 * bits[4] + 8 * bits[5] + 4 * bits[6];
  1074. ***************
  1075. *** 216,222 ****
  1076.               match_length = 1;
  1077.           } else if (greedy) {
  1078.               lens[match_length] ++;
  1079. !             update((us_t)match_position >> 7);
  1080.               refers ++;
  1081.           } else {
  1082.               register us_t orig_length, orig_position;
  1083. --- 224,233 ----
  1084.               match_length = 1;
  1085.           } else if (greedy) {
  1086.               lens[match_length] ++;
  1087. !         if (match_position < 0 || match_position >= 8192 - 256)
  1088. !             printf("%d\n", match_position);
  1089. ! 
  1090. !             update(match_position >> 7);
  1091.               refers ++;
  1092.           } else {
  1093.               register us_t orig_length, orig_position;
  1094. ***************
  1095. *** 226,237 ****
  1096.               Next_Char(N2, F2);
  1097.               Get_Next_Match(r,2);
  1098.               if (match_length > len) match_length = len;
  1099. !             if (orig_length > match_length) {
  1100.                   lens[orig_length] ++;
  1101. !                 update((us_t)orig_position >> 7);
  1102.                   match_length = orig_length - 1;
  1103.               } else  {
  1104.                   lens[match_length] ++;
  1105.                   update(match_position >> 7);
  1106.               }
  1107.               refers ++;
  1108. --- 237,251 ----
  1109.               Next_Char(N2, F2);
  1110.               Get_Next_Match(r,2);
  1111.               if (match_length > len) match_length = len;
  1112. !             if (orig_length >= match_length) {
  1113.                   lens[orig_length] ++;
  1114. !                 update(orig_position >> 7);
  1115.                   match_length = orig_length - 1;
  1116.               } else  {
  1117.                   lens[match_length] ++;
  1118. +             if (match_position < 0 || match_position >= 8192 - 256)
  1119. +                 printf("%d\n", match_position);
  1120. + 
  1121.                   update(match_position >> 7);
  1122.               }
  1123.               refers ++;
  1124.  
  1125. exit 0 # Just in case...
  1126.