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