home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume1 / compress < prev    next >
Internet Message Format  |  1986-11-30  |  61KB
  1. Date: 2 Jan 1985 2321-EST (Wednesday)
  2. From: decvax!vax135!petsd!joe (Joe Orost)
  3. Subject: Compress release 3.0
  4.  
  5. Here is a state-of-the-art file compression program - "compress" release 3.0.
  6.  
  7. #!/bin/sh
  8. cat >README <<'------ EOF ------'
  9. Enclosed is compress version 3.0 with the following changes:
  10.  
  11. 1.    "Block" compression is performed.  After the BITS run out, the
  12.     compression ratio is checked every so often.  If it is decreasing,
  13.     the table is cleared and a new set of substrings are generated.
  14.  
  15.     This makes the output of compress 3.0 not compatable with that of
  16.     compress 2.0.  However, compress 3.0 still accepts the output of
  17.     compress 2.0.  To generate output that is compatable with compress
  18.     2.0, use the undocumented "-C" flag.
  19.  
  20. 2.    A quiet "-q" flag has been added for use by the news system.
  21.  
  22. 3.    The character chaining has been deleted and the program now uses
  23.     hashing.  This improves the speed of the program, especially
  24.     during decompression.  Other speed improvements have been made,
  25.     such as using putc() instead of fwrite().
  26.  
  27. 4.    A large table is used on large machines when a relatively small
  28.     number of bits is specified.  This saves much time when compressing
  29.     for a 16-bit machine on a 32-bit virtual machine.  Note that the
  30.     speed improvement only occurs when the input file is > 30000
  31.     characters, and the -b BITS is less than or equal to the cutoff
  32.     described below.
  33.  
  34. Most of these changes were made by James A. Woods (ames!jaw).  Thank you
  35. James!
  36.  
  37. Version 3.0 has been beta tested on many machines.
  38.  
  39. To compile compress:
  40.  
  41.     cc -O -DUSERMEM=usermem -o compress compress.c
  42.  
  43. Where "usermem" is the amount of physical user memory available (in bytes).  
  44. If any physical memory is to be reserved for other processes, put in 
  45. "-DSACREDMEM sacredmem", where "sacredmem" is the amount to be reserved.
  46.  
  47. The difference "usermem-sacredmem" determines the maximum BITS that can be
  48. specified, and the cutoff bits where the large+fast table is used.
  49.  
  50. memory: at least        BITS        cutoff
  51. ------  -- -----                ----            ------
  52.    4,718,592              16          13
  53.    2,621,440              16          12
  54.    1,572,864             16          11
  55.    1,048,576             16          10
  56.      631,808             16               --
  57.      329,728             15               --
  58.      178,176             14          --
  59.       99,328             13          --
  60.            0             12          --
  61.  
  62. The default memory size is 750,000 which gives a maximum BITS=16 and no
  63. large+fast table.
  64.  
  65. The maximum bits can be overrulled by specifying "-DBITS=bits" at
  66. compilation time.
  67.  
  68. If your machine doesn't support unsigned characters, define "NO_UCHAR" 
  69. when compiling.
  70.  
  71. If your machine has "int" as 16-bits, define "SHORT_INT" when compiling.
  72.  
  73. After compilation, move "compress" to a standard executable location, such 
  74. as /usr/local.  Then:
  75.     cd /usr/local
  76.     ln compress uncompress
  77.     ln compress zcat
  78.  
  79. On machines that have a fixed stack size (such as Perkin-Elmer), set the
  80. stack to at least 12kb.  ("setstack compress 12" on Perkin-Elmer).
  81.  
  82. Next, install the manual (compress.l).
  83.     cp compress.l /usr/man/manl
  84.     cd /usr/man/manl
  85.     ln compress.l uncompress.l
  86.     ln compress.l zcat.l
  87.  
  88.         - or -
  89.  
  90.     cp compress.l /usr/man/man1/compress.1
  91.     cd /usr/man/man1
  92.     ln compress.1 uncompress.1
  93.     ln compress.1 zcat.1
  94.  
  95. The zmore shell script and manual page are for use on systems that have a
  96. "more(1)" program.  Install the shell script and the manual page in a "bin"
  97. and "man" directory, respectively.  If your system doesn't have the
  98. "more(1)" program, just skip "zmore".
  99.  
  100.                     regards,
  101.                     petsd!joe
  102.  
  103. Here is the README file from the previous version of compress (2.0):
  104.  
  105. >Enclosed is compress.c version 2.0 with the following bugs fixed:
  106. >
  107. >1.    The packed files produced by compress are different on different
  108. >    machines and dependent on the vax sysgen option.
  109. >        The bug was in the different byte/bit ordering on the
  110. >        various machines.  This has been fixed.
  111. >
  112. >        This version is NOT compatible with the original vax posting
  113. >        unless the '-DCOMPATIBLE' option is specified to the C
  114. >        compiler.  The original posting has a bug which I fixed, 
  115. >        causing incompatible files.  I recommend you NOT to use this
  116. >        option unless you already have a lot of packed files from
  117. >        the original posting by thomas.
  118. >2.    The exit status is not well defined (on some machines) causing the
  119. >    scripts to fail.
  120. >        The exit status is now 0,1 or 2 and is documented in
  121. >        compress.l.
  122. >3.    The function getopt() is not available in all C libraries.
  123. >        The function getopt() is no longer referenced by the
  124. >        program.
  125. >4.    Error status is not being checked on the fwrite() and fflush() calls.
  126. >        Fixed.
  127. >
  128. >The following enhancements have been made:
  129. >
  130. >1.    Added facilities of "compact" into the compress program.  "Pack",
  131. >    "Unpack", and "Pcat" are no longer required (no longer supplied).
  132. >2.    Installed work around for C compiler bug with "-O".
  133. >3.    Added a magic number header (\037\235).  Put the bits specified
  134. >    in the file.
  135. >4.    Added "-f" flag to force overwrite of output file.
  136. >5.    Added "-c" flag and "zcat" program.  'ln compress zcat' after you
  137. >    compile.
  138. >6.    The 'uncompress' script has been deleted; simply 
  139. >    'ln compress uncompress' after you compile and it will work.
  140. >7.    Removed extra bit masking for machines that support unsigned
  141. >    characters.  If your machine doesn't support unsigned characters,
  142. >    define "NO_UCHAR" when compiling.
  143. >
  144. >Compile "compress.c" with "-O -o compress" flags.  Move "compress" to a
  145. >standard executable location, such as /usr/local.  Then:
  146. >    cd /usr/local
  147. >    ln compress uncompress
  148. >    ln compress zcat
  149. >
  150. >On machines that have a fixed stack size (such as Perkin-Elmer), set the
  151. >stack to at least 12kb.  ("setstack compress 12" on Perkin-Elmer).
  152. >
  153. >Next, install the manual (compress.l).
  154. >    cp compress.l /usr/man/manl        - or -
  155. >    cp compress.l /usr/man/man1/compress.1
  156. >
  157. >Here is the README that I sent with my first posting:
  158. >
  159. >>Enclosed is a modified version of compress.c, along with scripts to make it
  160. >>run identically to pack(1), unpack(1), an pcat(1).  Here is what I
  161. >>(petsd!joe) and a colleague (petsd!peora!srd) did:
  162. >>
  163. >>1. Removed VAX dependencies.
  164. >>2. Changed the struct to separate arrays; saves mucho memory.
  165. >>3. Did comparisons in unsigned, where possible.  (Faster on Perkin-Elmer.)
  166. >>4. Sorted the character next chain and changed the search to stop
  167. >>prematurely.  This saves a lot on the execution time when compressing.
  168. >>
  169. >>This version is totally compatible with the original version.  Even though
  170. >>lint(1) -p has no complaints about compress.c, it won't run on a 16-bit
  171. >>machine, due to the size of the arrays.
  172. >>
  173. >>Here is the README file from the original author:
  174. >> 
  175. >>>Well, with all this discussion about file compression (for news batching
  176. >>>in particular) going around, I decided to implement the text compression
  177. >>>algorithm described in the June Computer magazine.  The author claimed
  178. >>>blinding speed and good compression ratios.  It's certainly faster than
  179. >>>compact (but, then, what wouldn't be), but it's also the same speed as
  180. >>>pack, and gets better compression than both of them.  On 350K bytes of
  181. >>>unix-wizards, compact took about 8 minutes of CPU, pack took about 80
  182. >>>seconds, and compress (herein) also took 80 seconds.  But, compact and
  183. >>>pack got about 30% compression, whereas compress got over 50%.  So, I
  184. >>>decided I had something, and that others might be interested, too.
  185. >>>
  186. >>>As is probably true of compact and pack (although I haven't checked),
  187. >>>the byte order within a word is probably relevant here, but as long as
  188. >>>you stay on a single machine type, you should be ok.  (Can anybody
  189. >>>elucidate on this?)  There are a couple of asm's in the code (extv and
  190. >>>insv instructions), so anyone porting it to another machine will have to
  191. >>>deal with this anyway (and could probably make it compatible with Vax
  192. >>>byte order at the same time).  Anyway, I've linted the code (both with
  193. >>>and without -p), so it should run elsewhere.  Note the longs in the
  194. >>>code, you can take these out if you reduce BITS to <= 15.
  195. >>>
  196. >>>Have fun, and as always, if you make good enhancements, or bug fixes,
  197. >>>I'd like to see them.
  198. >>>
  199. >>>=Spencer (thomas@utah-20, {harpo,hplabs,arizona}!utah-cs!thomas)
  200. >>
  201. >>                    regards,
  202. >>                    joe
  203. >>
  204. >>--
  205. >>Full-Name:  Joseph M. Orost
  206. >>UUCP:       ..!{decvax,ucbvax,ihnp4}!vax135!petsd!joe
  207. >>US Mail:    MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724
  208. >>Phone:      (201) 870-5844
  209. ------ EOF ------
  210. ls -l README
  211. cat >compress.l <<'------ EOF ------'
  212. .PU
  213. .TH COMPRESS 1 local
  214. .SH NAME
  215. compress, uncompress, zcat  \-  compress and uncompress files
  216. .SH SYNOPSIS
  217. .ll +8
  218. .B compress
  219. [
  220. .B \-d
  221. ] [
  222. .B \-f
  223. ] [
  224. .B \-F
  225. ] [
  226. .B \-q
  227. ] [
  228. .B \-c
  229. ] [
  230. .B \-b
  231. .I bits
  232. ] [
  233. .I "filename \&..."
  234. ]
  235. .ll -8
  236. .br
  237. .B uncompress
  238. [
  239. .B \-f
  240. ] [
  241. .B \-q
  242. ] [
  243. .B \-c
  244. ] [
  245. .I "filename \&..."
  246. ]
  247. .br
  248. .B zcat
  249. [
  250. .I "filename \&..."
  251. ]
  252. .SH DESCRIPTION
  253. Compresses the specified files or standard input.
  254. Each file is replaced by a file with the extension
  255. .B "\&.Z,"
  256. but only if the file got smaller.
  257. If no files are specified,
  258. the compression is applied to the standard input
  259. and is written to standard output
  260. regardless of the results.
  261. Compressed files can be restored
  262. to their original form by specifying the
  263. .B \-d
  264. option, or by running
  265. .I uncompress
  266. (linked to
  267. .IR compress ),
  268. on the 
  269. .B "\&.Z"
  270. files or the standard input.
  271. .PP
  272. If the output file exists, it will not be overwritten unless the
  273. .B \-f
  274. flag is given.  If
  275. .B \-f
  276. is not specified and
  277. .I compress
  278. is run in the foreground,
  279. the user is prompted
  280. as to whether the file should be overwritten.
  281. .PP
  282. If the
  283. .B \-F
  284. flag is given, all files specified are replaced with
  285. .B "\&.Z"
  286. files \- even if the file didn't get smaller.
  287. .PP
  288. When file names are given, the ownership (if run by root), modes, accessed
  289. and modified times are maintained between the file and its 
  290. .B "\&.Z"
  291. version.  In this respect,
  292. .I compress
  293. can be used for archival purposes, yet can still be used with
  294. .IR make "(1)"
  295. after uncompression.
  296. .PP
  297. The
  298. .B \-c
  299. option causes the results of the compress/uncompress operation to be written
  300. to stdout; no files are changed.  The
  301. .I zcat
  302. program is the same as specifying
  303. .B \-c
  304. to
  305. .I uncompress
  306. (all files are unpacked and written to stdout).
  307. .PP
  308. .I Compress
  309. uses the modified Lempel-Ziv algorithm described in
  310. "A Technique for High Performance Data Compression",
  311. Terry A. Welch,
  312. .I "IEEE Computer"
  313. Vol 17, No 6 (June 1984), pp 8-19.
  314. Common substrings in the file are first replaced by 9-bit codes 257 and up.
  315. When code 512 is reached, the algorithm switches to 10-bit codes and
  316. continues to use more bits until the
  317. .I bits
  318. limit as specified by the
  319. .B \-b
  320. flag is reached (default 16).
  321. .I Bits
  322. must be between 9 and 16.  The default can be changed in the source to allow
  323. .I compress
  324. to be run on a smaller machine.
  325. .PP
  326. After the
  327. .I bits
  328. limit is reached,
  329. .I compress
  330. periodically checks the compression ratio.  If it is increasing,
  331. .I compress
  332. continues to use the codes that were previously found in the file.  However,
  333. if the compression ratio decreases,
  334. .I compress
  335. discards the table of substrings and rebuilds it from scratch.  This allows
  336. the algorithm to adapt to the next "block" of the file.
  337. .PP
  338. A two byte magic number is prepended to the file
  339. to ensure that neither uncompression of random text nor recompression of 
  340. compressed text are attempted.  In addition, the
  341. .I bits
  342. specified during
  343. .I compress
  344. is written to the file so that the
  345. .B \-b
  346. flag can be omitted for
  347. .IR uncompress \.
  348. .PP
  349. .ne 8
  350. The amount of compression obtained depends on the size of the
  351. input file, the amount of
  352. .I bits
  353. per code, and the distribution of character substrings.
  354. Typically, text files, such as C programs,
  355. are reduced by 50\-60%.
  356. Compression is generally much better than that achieved by
  357. Huffman coding (as used in
  358. .IR pack ),
  359. or adaptive Huffman coding
  360. .RI ( compact ),
  361. and takes less time to compute.
  362. .PP
  363. .PP
  364. After each file is compressed, a message is printed giving the percentage of
  365. the input file that has been saved by compression.  This message is
  366. suppressed when the
  367. .B \-q
  368. (quiet) flag is given.
  369. .PP
  370. The exit status is normally 0;
  371. if the last file gets bigger after compression, the exit status is 2;
  372. if an error occurs, the exit status is 1.
  373. .SH "SEE ALSO"
  374. compact(1), pack(1)
  375. .SH "DIAGNOSTICS"
  376. Usage: compress [-dfFqc] [-b maxbits] [file ...]
  377. .in +8
  378. Invalid options were specified on the command line.
  379. .in -8
  380. Missing maxbits
  381. .in +8
  382. Maxbits must follow
  383. .BR \-b \.
  384. .in -8
  385. Unknown flag: 
  386. .I "\'x\';"
  387. .in +8
  388. Invalid flags were specified on the command line.
  389. .in -8
  390. .IR file :
  391. not in compressed format
  392. .in +8
  393. The specified file has not been compressed.
  394. .in -8
  395. .IR file :
  396. compressed with 
  397. .I xx
  398. bits, can only handle 
  399. .I yy
  400. bits
  401. .in +8
  402. The specified file was compressed by a compress program that could handle
  403. more 
  404. .I bits
  405. than the current compress program.  Recompress the file with a smaller
  406. .IR bits \.
  407. .in -8
  408. .IR file :
  409. already has .Z suffix -- no change
  410. .in +8
  411. Cannot compress a file that has a ".Z" suffix.
  412. .IR mv "(1)"
  413. the file to a different name and try again.
  414. .in -8
  415. .IR file :
  416. filename too long to tack on .Z
  417. .in +8
  418. The specified file cannot be compressed because its filename is longer than
  419. 12 characters.
  420. .IR mv "(1)"
  421. the file to a different name and try again.  This message does not occur on
  422. 4.2BSD systems.
  423. .in -8
  424. .I file
  425. already exists; do you wish to overwrite (y or n)?
  426. .in +8
  427. Respond "y" if you want the output file to be replaced; "n" if you want it
  428. to be left alone.
  429. .in -8
  430. .IR file :
  431. .in +8
  432. This message fragment is written during the processing of a file.
  433. .in -8
  434. Compression: 
  435. .I "xx.xx%"
  436. .in +8
  437. This message fragment gives the percentage of the input file that has been
  438. saved by compression.
  439. .in -8
  440. -- not a regular file: unchanged
  441. .in +8
  442. This message fragment is written when the input file is not a regular file.
  443. The input file is left unchanged.
  444. .in -8
  445. -- has 
  446. .I xx 
  447. other links: unchanged
  448. .in +8
  449. This message fragment is written when the input file has links.  The input
  450. file is left unchanged.  See
  451. .IR ln "(1)"
  452. for more information.
  453. .in -8
  454. -- file unchanged
  455. .in +8
  456. This message fragment is written when no savings are achieved by
  457. compression.  The input file is left unchanged.
  458. .in -8
  459. -- replaced with 
  460. .I file
  461. .in +8
  462. This message fragment is written when a file has been sucessfully
  463. compressed/uncompressed.
  464. .in -8
  465. ------ EOF ------
  466. ls -l compress.l
  467. cat >compress.c <<'------ EOF ------'
  468. /* Set USERMEM to the maximum amount of physical user memory available
  469.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  470.  * for compression.  If USERMEM is big enough, use fast compression algorithm.
  471.  *
  472.  * SACREDMEM is the amount of physical memory saved for others; compress
  473.  * will hog the rest.
  474.  */
  475. #ifndef SACREDMEM
  476. #define SACREDMEM    0
  477. #endif
  478.  
  479. #ifdef pdp11
  480. # define BITS     12    /* max bits/code for 16-bit machine */
  481. # define NO_UCHAR    /* also if "unsigned char" functions as signed char */
  482. # define SHORT_INT    /* ints are short */
  483. # undef USERMEM 
  484. #else !pdp11
  485. # ifndef USERMEM
  486. #  define USERMEM 750000    /* default user memory */
  487. # endif
  488. #endif !pdp11
  489. /* 
  490.  * Define FBITS for machines with several MB of physical memory, to use
  491.  * table lookup for (b <= FBITS).  If FBITS is made too large, performance
  492.  * will decrease due to increased swapping/paging.  Since the program minus
  493.  * the fast lookup table is about a half Meg, we can allocate the rest of
  494.  * available physical memory to the fast lookup table.
  495.  * 
  496.  * If FBITS is set to 12, a 2 MB array is allocated, but only 1 MB is
  497.  * addressed for parity-free input (i.e. text).
  498.  *
  499.  * FBITS=10 yields 1/2 meg lookup table + 4K code memory
  500.  * FBITS=11 yields 1 meg lookup table + 8K code memory
  501.  * FBITS=12 yields 2 meg lookup table + 16K code memory
  502.  * FBITS=13 yields 4 meg lookup table + 32K code memory
  503.  *
  504.  */
  505.  
  506. #ifdef USERMEM
  507. # if USERMEM >= (2621440+SACREDMEM)
  508. #  if USERMEM >= (4718592+SACREDMEM)
  509. #   define FBITS        13
  510. #   define PBITS    16
  511. #  else 2.5M <= USERMEM < 4.5M
  512. #   define FBITS        12
  513. #   define PBITS    16
  514. #  endif USERMEM <=> 4.5M
  515. # else USERMEM < 2.5M
  516. #  if USERMEM >= (1572864+SACREDMEM)
  517. #   define FBITS        11
  518. #   define PBITS    16
  519. #  else USERMEM < 1.5M
  520. #   if USERMEM >= (1048576+SACREDMEM)
  521. #    define FBITS        10
  522. #    define PBITS    16
  523. #   else USERMEM < 1M
  524. #    if USERMEM >= (631808+SACREDMEM)
  525. #     define PBITS    16
  526. #    else
  527. #     if USERMEM >= (329728+SACREDMEM)
  528. #      define PBITS    15
  529. #     else
  530. #      if USERMEM >= (178176+SACREDMEM)
  531. #       define PBITS    14
  532. #      else
  533. #       if USERMEM >= (99328+SACREDMEM)
  534. #        define PBITS    13
  535. #       else
  536. #        define PBITS    12
  537. #       endif
  538. #      endif
  539. #     endif
  540. #    endif
  541. #    undef USERMEM
  542. #   endif USERMEM <=> 1M
  543. #  endif USERMEM <=> 1.5M
  544. # endif USERMEM <=> 2.5M
  545. #endif USERMEM
  546.  
  547. #ifdef PBITS        /* Preferred BITS for this memory size */
  548. # ifndef BITS
  549. #  define BITS PBITS
  550. # endif BITS
  551. #endif PBITS
  552.  
  553. #if BITS == 16
  554. # define HSIZE    69001        /* 95% occupancy */
  555. #endif
  556. #if BITS == 15
  557. # define HSIZE    35023        /* 94% occupancy */
  558. #endif
  559. #if BITS == 14
  560. # define HSIZE    18013        /* 91% occupancy */
  561. #endif
  562. #if BITS == 13
  563. # define HSIZE    9001        /* 91% occupancy */
  564. #endif
  565. #if BITS == 12
  566. # define HSIZE    5003        /* 80% occupancy */
  567. #endif
  568. #if BITS == 11
  569. # define HSIZE    2591        /* 79% occupancy */
  570. #endif
  571. #if BITS == 10
  572. # define HSIZE    1291        /* 79% occupancy */
  573. #endif
  574. #if BITS == 9
  575. # define HSIZE    691        /* 74% occupancy */
  576. #endif
  577. /* BITS < 9 will cause an error */
  578.  
  579. /*
  580.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  581.  */
  582. #if BITS > 15
  583. typedef long int    code_int;
  584. #else
  585. typedef int        code_int;
  586. #endif
  587.  
  588. #ifdef interdata
  589. typedef unsigned long int count_int;
  590. typedef unsigned short int count_short;
  591. #else
  592. typedef long int      count_int;
  593. #endif
  594.  
  595. #ifdef NO_UCHAR
  596.  typedef char    char_type;
  597. #else UCHAR
  598.  typedef    unsigned char    char_type;
  599. #endif UCHAR
  600. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  601.  
  602. /* Defines for third byte of header */
  603. #define BIT_MASK    0x1f
  604. #define BLOCK_MASK    0x80
  605. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  606.    a fourth header byte (for expansion).
  607. */
  608. #define INIT_BITS 9            /* initial number of bits/code */
  609.  
  610. /*
  611.  * compress.c - File compression ala IEEE Computer June 1984.
  612.  *
  613.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  614.  *        Jim McKie        (decvax!mcvax!jim)
  615.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  616.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  617.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  618.  *        Joe Orost        (decvax!vax135!petsd!joe)
  619.  *
  620.  * $Header: compress.c,v 3.0 84/11/27 11:50:00 joe Exp $
  621.  * $Log:    compress.c,v $
  622.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  623.  * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  624.  * loops in clear routines.  Added "-C" flag for 2.0 compatability.  Used
  625.  * unsigned compares on Perkin-Elmer.  Fixed foreground check.
  626.  *
  627.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  628.  * Cache common hash codes based on input statistics; this improves
  629.  * performance for low-density raster images.  Pass on #ifdef bundle
  630.  * from Turkowski.
  631.  *
  632.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  633.  * Vary size of hash tables to reduce time for small files.
  634.  * Tune PDP-11 hash function.
  635.  *
  636.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  637.  * Junk chaining; replace with the simpler (and, on the VAX, faster)
  638.  * double hashing, discussed within.  Make block compression standard.
  639.  *
  640.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  641.  * Introduce adaptive reset for block compression, to boost the rate
  642.  * another several percent.  (See mailing list notes.)
  643.  *
  644.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  645.  * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  646.  * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  647.  *
  648.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  649.  * Fold in news changes, small machine typedef from thomas,
  650.  * #ifdef interdata from joe.
  651.  *
  652.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  653.  * Configured fast table lookup for 32-bit machines.
  654.  * This cuts user time in half for b <= FBITS, and is useful for news batching
  655.  * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  656.  * added signal catcher [plus beef in writeerr()] to delete effluvia.
  657.  *
  658.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  659.  * Add check for foreground before prompting user.  Insert maxbits into
  660.  * compressed file.  Force file being uncompressed to end with ".Z".
  661.  * Added "-c" flag and "zcat".  Prepared for release.
  662.  *
  663.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  664.  * Will only compress regular files (no directories), added a magic number
  665.  * header (plus an undocumented -n flag to handle old files without headers),
  666.  * added -f flag to force overwriting of possibly existing destination file,
  667.  * otherwise the user is prompted for a response.  Will tack on a .Z to a
  668.  * filename if it doesn't have one when decompressing.  Will only replace
  669.  * file if it was compressed.
  670.  *
  671.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  672.  * Removed scanargs(), getopt(), added .Z extension and unlimited number of
  673.  * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  674.  * (-D -d -v -b 12), or combination thereof.  Modes and other status is
  675.  * copied with copystat().  -O bug for 4.2 seems to have disappeared with
  676.  * 1.8.
  677.  *
  678.  * Revision 1.8  84/08/09  23:15:00  joe
  679.  * Made it compatible with vax version, installed jim's fixes/enhancements
  680.  *
  681.  * Revision 1.6  84/08/01  22:08:00  joe
  682.  * Sped up algorithm significantly by sorting the compress chain.
  683.  *
  684.  * Revision 1.5  84/07/13  13:11:00  srd
  685.  * Added C version of vax asm routines.  Changed structure to arrays to
  686.  * save much memory.  Do unsigned compares where possible (faster on
  687.  * Perkin-Elmer)
  688.  *
  689.  * Revision 1.4  84/07/05  03:11:11  thomas
  690.  * Clean up the code a little and lint it.  (Lint complains about all
  691.  * the regs used in the asm, but I'm not going to "fix" this.)
  692.  *
  693.  * Revision 1.3  84/07/05  02:06:54  thomas
  694.  * Minor fixes.
  695.  *
  696.  * Revision 1.2  84/07/05  00:27:27  thomas
  697.  * Add variable bit length output.
  698.  *
  699.  */
  700. #ifndef lint
  701. static char rcs_ident[] = "$Header: compress.c,v 3.0 84/11/27 11:50:00 joe Exp $";
  702. #endif !lint
  703.  
  704. #include <stdio.h>
  705. #include <ctype.h>
  706. #include <signal.h>
  707. #include <sys/types.h>
  708. #include <sys/stat.h>
  709.  
  710. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  711.  
  712. int n_bits;                /* number of bits/code */
  713. int maxbits = BITS;            /* user settable max # bits/code */
  714. code_int maxcode;            /* maximum code, given n_bits */
  715. code_int maxmaxcode = 1 << BITS;    /* should NEVER generate this code */
  716. #ifdef COMPATIBLE        /* But wrong! */
  717. # define MAXCODE(n_bits)    (1 << (n_bits) - 1)
  718. #else COMPATIBLE
  719. # define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  720. #endif COMPATIBLE
  721.  
  722. /*
  723.  * One code could conceivably represent (1<<BITS) characters, but
  724.  * to get a code of length N requires an input string of at least
  725.  * N*(N-1)/2 characters.  With 5000 chars in the stack, an input
  726.  * file would have to contain a 25Mb string of a single character.
  727.  * This seems unlikely.
  728.  */
  729. #ifdef SHORT_INT
  730. # define MAXSTACK    5000        /* size of output stack */
  731. #else !SHORT_INT
  732. # define MAXSTACK    8000        /* size of output stack */
  733. #endif !SHORT_INT
  734.  
  735. count_int htab [HSIZE];
  736. unsigned short codetab [HSIZE];
  737. code_int hsize = HSIZE;            /* for dynamic table sizing */
  738. count_int fsize;
  739.  
  740. #define tab_prefix    codetab        /* prefix code for this entry */
  741. char_type      tab_suffix[1<<BITS];    /* last char in this entry */
  742.  
  743. #ifdef USERMEM
  744. short ftable [(1 << FBITS) * 256];
  745. count_int fcodemem [1 << FBITS];
  746. #endif USERMEM
  747.  
  748. code_int free_ent = 0;            /* first unused entry */
  749. int exit_stat = 0;
  750.  
  751. code_int getcode();
  752.  
  753. Usage() {
  754. #ifdef DEBUG
  755. fprintf(stderr,"Usage: compress [-dDvqfFc] [-b maxbits] [file ...]\n");
  756. }
  757. int debug = 0;
  758. #else DEBUG
  759. fprintf(stderr,"Usage: compress [-dfFqc] [-b maxbits] [file ...]\n");
  760. }
  761. #endif DEBUG
  762. int nomagic = 0;    /* Use a 2 byte magic number header, unless old file */
  763. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  764. int quiet = 0;        /* don't tell me about compression */
  765.  
  766. /*
  767.  * block compression parameters -- after all codes are used up,
  768.  * and compression rate changes, start over.
  769.  */
  770. int block_compress = BLOCK_MASK;
  771. int clear_flg = 0;
  772. double ratio = 0.0;    /* compression ratio for last block */
  773. #define CHECK_GAP 10000    /* ratio check interval */
  774. count_int checkpoint = CHECK_GAP;
  775. /*
  776.  * the next two codes should not be changed lightly, as they must not
  777.  * lie within the contiguous general code space.
  778.  */ 
  779. #define FIRST    257    /* first free entry */
  780. #define    CLEAR    256    /* table clear output code */
  781.  
  782. int force = 0;
  783. char ofname [100];
  784. #ifdef DEBUG
  785. int verbose = 0;
  786. #endif DEBUG
  787. int (*bgnd_flag)();
  788.  
  789. /*****************************************************************
  790.  * TAG( main )
  791.  *
  792.  * Algorithm from "A Technique for High Performance Data Compression",
  793.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  794.  *
  795.  * Usage: compress [-dfFqc] [-b bits] [file ...]
  796.  * Inputs:
  797.  *    -d:        If given, decompression is done instead.
  798.  *
  799.  *      -c:         Write output on stdout, don't remove original.
  800.  *
  801.  *      -b:         Parameter limits the max number of bits/code.
  802.  *
  803.  *    -f:        Forces output file to be generated, even if one already
  804.  *            exists; if -f is not used, the user will be prompted if
  805.  *            the stdin is a tty, otherwise, the output file will not
  806.  *            be overwritten.
  807.  *
  808.  *    -F:        Forces output file to be generated, even if no space is
  809.  *            saved by compressing.
  810.  *
  811.  *    -q:        No output, unless error
  812.  *
  813.  *     file ...:   Files to be compressed.  If none specified, stdin
  814.  *            is used.
  815.  * Outputs:
  816.  *    file.Z:        Compressed form of file with same mode, owner, and utimes
  817.  *     or stdout   (if stdin used as input)
  818.  *
  819.  * Assumptions:
  820.  *    When filenames are given, replaces with the compressed version
  821.  *    (.Z suffix) only if the file decreased in size.
  822.  * Algorithm:
  823.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  824.  * substrings and replaces them with a variable size code.  This is
  825.  * deterministic, and can be done on the fly.  Thus, the decompression
  826.  * procedure needs no input table, but tracks the way the table was
  827.  * built.
  828.  */
  829.  
  830. main( argc, argv )
  831. register int argc; char **argv;
  832. {
  833.     int do_decomp = 0;
  834.     int overwrite = 0;    /* Do not overwrite unless given -f flag */
  835.     char tempname[100];
  836.     char **filelist, **fileptr;
  837.     char *cp, *rindex();
  838.     struct stat statbuf;
  839.     extern onintr();
  840.  
  841.  
  842.     if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN )
  843.     signal ( SIGINT, onintr );
  844.  
  845. #ifdef COMPATIBLE
  846.     nomagic = 1;    /* Original didn't have a magic number */
  847. #endif COMPATIBLE
  848.  
  849.     filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
  850.     *filelist = NULL;
  851.  
  852.     if((cp = rindex(argv[0], '/')) != 0) {
  853.     cp++;
  854.     } else {
  855.     cp = argv[0];
  856.     }
  857.     if(strcmp(cp, "uncompress") == 0) {
  858.     do_decomp = 1;
  859.     } else if(strcmp(cp, "zcat") == 0) {
  860.     do_decomp = 1;
  861.     zcat_flg = 1;
  862.     }
  863.  
  864. #ifdef BSD4_2
  865.     /* 4.2BSD dependent - take it out if not */
  866.     setlinebuf( stderr );
  867. #endif BSD4_2
  868.  
  869.     /* Argument Processing
  870.      * All flags are optional.
  871.      * -D => debug
  872.      * -d => do_decomp
  873.      * -v => verbose
  874.      * -f => force overwrite of output file
  875.      * -n => no header: useful to uncompress old files
  876.      * -b maxbits => maxbits.  If -b is specified, then maxbits MUST be
  877.      *        given also.
  878.      * -c => cat all output to stdout
  879.      * -C => generate output compatable with compress 2.0.
  880.      * if a string is left, must be an input filename.
  881.      */
  882.     for (argc--, argv++; argc > 0; argc--, argv++) {
  883.     if (**argv == '-') {    /* A flag argument */
  884.         while (*++(*argv)) {    /* Process all flags in this arg */
  885.         switch (**argv) {
  886. #ifdef DEBUG
  887.             case 'D':
  888.             debug = 1;
  889.             break;
  890.             case 'v':
  891.             verbose = 1;
  892.             break;
  893. #endif DEBUG
  894.             case 'd':
  895.             do_decomp = 1;
  896.             break;
  897.             case 'f':
  898.             overwrite = 1;
  899.             break;
  900.             case 'n':
  901.             nomagic = 1;
  902.             break;
  903.             case 'C':
  904.             block_compress = 0;
  905.             break;
  906.             case 'b':
  907.             if (!ARGVAL()) {
  908.                 fprintf(stderr, "Missing maxbits\n");
  909.                 Usage();
  910.                 exit(1);
  911.             }
  912.             maxbits = atoi(*argv);
  913.             goto nextarg;
  914.             case 'c':
  915.             zcat_flg = 1;
  916.             break;
  917.             case 'q':
  918.             quiet = 1;
  919.             break;
  920.             case 'F':
  921.             force = 1;
  922.             break;
  923.             default:
  924.             fprintf(stderr, "Unknown flag: '%c'; ", **argv);
  925.             Usage();
  926.             exit(1);
  927.         }
  928.         }
  929.     }
  930.     else {        /* Input file name */
  931.         *fileptr++ = *argv;    /* Build input file list */
  932.         *fileptr = NULL;
  933.         /* goto nextarg; */
  934.     }
  935.     nextarg: continue;
  936.     }
  937.  
  938.     if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  939.     if (maxbits > BITS) maxbits = BITS;
  940.     maxmaxcode = 1 << maxbits;
  941.  
  942.     if (*filelist != NULL) {
  943.     for (fileptr = filelist; *fileptr; fileptr++) {
  944.         exit_stat = 0;
  945.         if (do_decomp != 0) {            /* DECOMPRESSION */
  946.         /* Check for .Z suffix */
  947.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") != 0) {
  948.             /* No .Z: tack one on */
  949.             strcpy(tempname, *fileptr);
  950.             strcat(tempname, ".Z");
  951.             *fileptr = tempname;
  952.         }
  953.         /* Open input file */
  954.         if ((freopen(*fileptr, "r", stdin)) == NULL) {
  955.             perror(*fileptr); continue;
  956.         }
  957.         /* Check the magic number */
  958.         if (nomagic == 0) {
  959.             if ((getchar() != (magic_header[0] & 0xFF))
  960.              || (getchar() != (magic_header[1] & 0xFF))) {
  961.             fprintf(stderr, "%s: not in compressed format\n",
  962.                 *fileptr);
  963.             continue;
  964.             }
  965.             maxbits = getchar();    /* set -b from file */
  966.             block_compress = maxbits & BLOCK_MASK;
  967.             maxbits &= BIT_MASK;
  968.             maxmaxcode = 1 << maxbits;
  969.             if(maxbits > BITS) {
  970.             fprintf(stderr,
  971.             "%s: compressed with %d bits, can only handle %d bits\n",
  972.             *fileptr, maxbits, BITS);
  973.             continue;
  974.             }
  975.         }
  976.         /* Generate output filename */
  977.         strcpy(ofname, *fileptr);
  978.         ofname[strlen(*fileptr) - 2] = '\0';  /* Strip off .Z */
  979.         } else {                    /* COMPRESSION */
  980.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") == 0) {
  981.             fprintf(stderr, "%s: already has .Z suffix -- no change\n",
  982.                 *fileptr);
  983.             continue;
  984.         }
  985.         /* Open input file */
  986.         if ((freopen(*fileptr, "r", stdin)) == NULL) {
  987.             perror(*fileptr); continue;
  988.         }
  989.         stat ( *fileptr, &statbuf );
  990.         fsize = (long) statbuf.st_size;
  991.         /*
  992.          * tune hash table size for small files -- ad hoc
  993.          */
  994. #if HSIZE > 5003
  995.         if ( fsize < (1 << 12) )
  996.             hsize = 5003;
  997. #if HSIZE > 9001
  998.         else if ( fsize < (1 << 13) )
  999.             hsize = 9001;
  1000. #if HSIZE > 18013
  1001.         else if ( fsize < (1 << 14) )
  1002.             hsize = 18013;
  1003. #if HSIZE > 35023
  1004.         else if ( fsize < (1 << 15) )
  1005.             hsize = 35023;
  1006.         else if ( fsize < 47000 )
  1007.             hsize = 50021;
  1008. #endif HSIZE > 35023
  1009. #endif HSIZE > 18013
  1010. #endif HSIZE > 9001
  1011.         else
  1012. #endif HSIZE > 5003
  1013.             hsize = HSIZE;
  1014.         /* Generate output filename */
  1015.         strcpy(ofname, *fileptr);
  1016. #ifndef BSD4_2        /* Short filenames */
  1017.         if ((cp=rindex(ofname,'/')) != NULL)    cp++;
  1018.         else                    cp = ofname;
  1019.         if (strlen(cp) > 12) {
  1020.             fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
  1021.             continue;
  1022.         }
  1023. #endif  BSD4_2        /* Long filenames allowed */
  1024.         strcat(ofname, ".Z");
  1025.         }
  1026.         /* Check for overwrite of existing file */
  1027.         if (overwrite == 0 && zcat_flg == 0) {
  1028.         if (stat(ofname, &statbuf) == 0) {
  1029.             char response[2];
  1030.             response[0] = 'n';
  1031.             fprintf(stderr, "%s already exists;", ofname);
  1032.             if (foreground()) {
  1033.             fprintf(stderr, " do you wish to overwrite (y or n)? ",
  1034.             ofname);
  1035.             fflush(stderr);
  1036.             read(2, response, 2);
  1037.             while (response[1] != '\n') {
  1038.                 if (read(2, response+1, 1) < 0) {    /* Ack! */
  1039.                 perror("stderr"); break;
  1040.                 }
  1041.             }
  1042.             }
  1043.             if (response[0] != 'y') {
  1044.             fprintf(stderr, "\tnot overwritten\n");
  1045.             continue;
  1046.             }
  1047.         }
  1048.         }
  1049.         if(zcat_flg == 0) {        /* Open output file */
  1050.         if (freopen(ofname, "w", stdout) == NULL) {
  1051.             perror(ofname);
  1052.             continue;
  1053.         }
  1054.         if(!quiet)
  1055.             fprintf(stderr, "%s: ", *fileptr);
  1056.         }
  1057.  
  1058.         /* Actually do the compression/decompression */
  1059.         if (do_decomp == 0)    compress();
  1060. #ifndef DEBUG
  1061.         else            decompress();
  1062. #else   DEBUG
  1063.         else if (debug == 0)    decompress();
  1064.         else            printcodes();
  1065.         if (verbose)        dump_tab();
  1066. #endif DEBUG
  1067.         if(zcat_flg == 0) {
  1068.         copystat(*fileptr, ofname);    /* Copy stats */
  1069.         if(exit_stat || (!quiet))
  1070.             putc('\n', stderr);
  1071.         }
  1072.     }
  1073.     } else {        /* Standard input */
  1074.     if (do_decomp == 0) {
  1075.         compress();
  1076.         if(!quiet)
  1077.             putc('\n', stderr);
  1078.     } else {
  1079.         /* Check the magic number */
  1080.         if (nomagic == 0) {
  1081.         if ((getchar()!=(magic_header[0] & 0xFF))
  1082.          || (getchar()!=(magic_header[1] & 0xFF))) {
  1083.             fprintf(stderr, "stdin: not in compressed format\n");
  1084.             exit(1);
  1085.         }
  1086.         maxbits = getchar();    /* set -b from file */
  1087.         block_compress = maxbits & BLOCK_MASK;
  1088.         maxbits &= BIT_MASK;
  1089.         maxmaxcode = 1 << maxbits;
  1090.         fsize = 100000;        /* assume stdin large for USERMEM */
  1091.         if(maxbits > BITS) {
  1092.             fprintf(stderr,
  1093.             "stdin: compressed with %d bits, can only handle %d bits\n",
  1094.             maxbits, BITS);
  1095.             exit(1);
  1096.         }
  1097.         }
  1098. #ifndef DEBUG
  1099.         decompress();
  1100. #else   DEBUG
  1101.         if (debug == 0)    decompress();
  1102.         else        printcodes();
  1103.         if (verbose)    dump_tab();
  1104. #endif DEBUG
  1105.     }
  1106.     }
  1107.     exit(exit_stat);
  1108. }
  1109.  
  1110. static int offset;
  1111. long int in_count = 1;            /* length of input */
  1112. long int bytes_out;            /* length of compressed output */
  1113. long int out_count = 0;            /* # of codes output (for debugging) */
  1114.  
  1115. #define HOG_CHECK ((count_int) 2000)    /* Number of chars to read b4 check */
  1116. #define MAX_CACHE ((count_int) 1<<BITS) /* Next line is this constant too */
  1117. unsigned short hashcache [1<<BITS];    /* common hash short circuit cache */
  1118. count_int cfreq [256];            /* character counts */
  1119. #ifndef vax
  1120.  char chog;                /* most common character from input */
  1121. # define CHOG    ' '            /* Assume space is most frequent */
  1122. #else 
  1123.  int chog;                /* char arith slow on VAX */
  1124. # define CHOG    (int) ' '        /* Assume space is most frequent */
  1125. #endif
  1126. int cstat_flg = 0;            /* on after determining char hog */
  1127.  
  1128. /*
  1129.  * compress stdin to stdout
  1130.  *
  1131.  * Algorithm:  on large machines, for maxbits <= FBITS, use fast direct table
  1132.  * lookup on the prefix code / next character combination.  For smaller code
  1133.  * size, use open addressing modular division double hashing (no chaining), ala
  1134.  * Knuth vol. 3, sec. 6.4 Algorithm D, along with G. Knott's relatively-prime
  1135.  * secondary probe.  Do block compression with an adaptive reset, whereby the
  1136.  * code table is cleared when the compression ratio decreases, but after the
  1137.  * table fills.  The variable-length output codes are re-sized at this point,
  1138.  * and a special CLEAR code is generated for the decompressor.  For the
  1139.  * megamemory version, the sparse array is cleared indirectly through a
  1140.  * "shadow" output code history.  Late additions: for the hashing code,
  1141.  * construct the table according to file size for noticeable speed improvement
  1142.  * on small files.  Also detect and cache codes associated with the most
  1143.  * common character to bypass hash calculation on these codes (a characteristic
  1144.  * of highly-compressable raster images).  Please direct questions about this
  1145.  * implementation to ames!jaw.
  1146.  */
  1147.  
  1148.  
  1149. compress() {
  1150.     register long fcode;
  1151.     register code_int i = 0;
  1152.     register int c;
  1153.     register code_int ent;
  1154.     register int disp;
  1155.     register code_int hsize_reg;
  1156.  
  1157. #ifndef COMPATIBLE
  1158.     if (nomagic == 0) {
  1159.     putchar(magic_header[0]); putchar(magic_header[1]);
  1160.     putchar((char)(maxbits | block_compress));
  1161.     }
  1162. #endif COMPATIBLE
  1163.  
  1164.     offset = 0;
  1165.     bytes_out = 0;
  1166.     out_count = 0;
  1167.     clear_flg = 0;
  1168.     ratio = 0.0;
  1169.     in_count = 1;
  1170.     checkpoint = CHECK_GAP;
  1171.     maxcode = MAXCODE(n_bits = INIT_BITS);
  1172.     free_ent = ((block_compress) ? FIRST : 256 );
  1173.     ent = getchar ();
  1174.  
  1175. #ifdef USERMEM
  1176. if ( maxbits <= FBITS && (fsize >= 30000) ) {    /* use hashing on small files */
  1177.  
  1178.     while ( (c = getchar()) != (unsigned) EOF ) {
  1179.     in_count++;
  1180.     fcode = (long) (((long) c << maxbits) + ent);
  1181.     if ( ftable [fcode] != 0 )        /* test for code in "string" table */
  1182.         ent = ftable [fcode];
  1183.     else {
  1184.         output ( (code_int) ent );
  1185.         out_count++;
  1186.         ent = c;
  1187.         if ( free_ent >= maxmaxcode ) {    
  1188.             if ( (count_int)in_count < checkpoint || (!block_compress) ) 
  1189.             continue;
  1190.         else {
  1191.             clear ();
  1192.             i = 0;
  1193.         }
  1194.         } else {                /* put code in table */
  1195.         ftable [fcode] = (short) free_ent++;
  1196.         fcodemem [i++] = fcode;        /* memorize for block compression */
  1197.         }
  1198.     }
  1199.     }
  1200.     goto fin;
  1201. }
  1202. #endif USERMEM
  1203.  
  1204.     chog = CHOG;        /* assumed character for the hog */
  1205.     cstat_flg = 0;
  1206.     hsize_reg = hsize;
  1207.     cl_hash(hsize_reg);        /* clear hash tables */
  1208.  
  1209.     while ( (c = getchar()) != (unsigned) EOF ) {
  1210.     in_count++;
  1211.     if ( cstat_flg == 0 ) {
  1212.         cfreq [c]++;     /* gather frequencies at start of input */
  1213.         if ( (count_int)in_count >  HOG_CHECK ) {
  1214.             cstat_flg = 1;
  1215.         chog = hogtally();    /* compute char hog */
  1216.         if(chog != CHOG)     /* fixup for wrong assumption */
  1217.             creset( (count_int) free_ent );
  1218.         }
  1219.     }
  1220.     if ( c == chog )
  1221.         if ( (i = hashcache [ent]) ) {    /* cache -> code */
  1222.             ent = i;
  1223.             continue;
  1224.         }
  1225.     fcode = (long) (((long) c << maxbits) + ent);
  1226. #ifdef SHORT_INT
  1227.     i = (((c + 12347) * ent) & 077777) % HSIZE;    /* avoid 'lrem' call */
  1228. #else !SHORT_INT
  1229.     i = fcode % hsize_reg;            /* division hashing */
  1230. #endif SHORT_INT
  1231.  
  1232.     if ( htab [i] == fcode ) {
  1233.         ent = codetab [i];
  1234.         continue;
  1235.     } else if ( (long)htab [i] < 0 )    /* empty slot */
  1236.         goto nomatch;
  1237.     disp = hsize_reg - i;        /* secondary hash (G. Knott) */
  1238.     if ( i == 0 )
  1239.         disp = 1;
  1240. probe:
  1241.     if ( (i -= disp) < 0 )
  1242.         i += hsize_reg;
  1243.  
  1244.     if ( htab [i] == fcode ) {
  1245.         ent = codetab [i];
  1246.         continue;
  1247.     }
  1248.     if ( (long)htab [i] > 0 ) 
  1249.         goto probe;
  1250. nomatch:
  1251.     output ( (code_int) ent );
  1252.     out_count++;
  1253. #ifdef interdata
  1254.     if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  1255. #else
  1256.     if ( free_ent < maxmaxcode ) {
  1257. #endif
  1258.         if ( c == chog )        /* code -> cache */
  1259.             hashcache [ent] = free_ent;
  1260.                           /* code -> hashtable */
  1261.         codetab [i] = free_ent++;
  1262.         htab [i] = fcode;
  1263.     }
  1264.     else if ( (count_int)in_count >= checkpoint && block_compress )
  1265.         clear ();
  1266.     ent = c;
  1267.     }
  1268. fin:
  1269.     /*
  1270.      * Put out the final code.
  1271.      */
  1272.     output( (code_int)ent );
  1273.     out_count++;
  1274.     output( (code_int)-1 );
  1275.  
  1276.     /*
  1277.      * Print out stats on stderr
  1278.      */
  1279.     if(zcat_flg == 0 && !quiet) {
  1280. #ifdef DEBUG
  1281.     fprintf( stderr,
  1282.     "%ld chars in, %ld codes (%ld bytes) out, compression factor %g\n",
  1283.         in_count, out_count, bytes_out,
  1284.         (double)in_count / (double)bytes_out );
  1285.     fprintf( stderr, "\tCompression as in compact: %5.2f%%\n",
  1286.         100.0 * ( in_count - bytes_out ) / (double) in_count );
  1287.     fprintf( stderr, "\tLargest code was %d (%d bits)\n", free_ent - 1, n_bits );
  1288. #else DEBUG
  1289.     fprintf( stderr, "Compression: %5.2f%%",
  1290.         100.0 * ( in_count - bytes_out ) / (double) in_count );
  1291. #endif DEBUG
  1292.     }
  1293.     if(bytes_out > in_count)    /* exit(2) if no savings */
  1294.     exit_stat = 2;
  1295.     return;
  1296. }
  1297.  
  1298. /*****************************************************************
  1299.  * TAG( output )
  1300.  *
  1301.  * Output the given code.
  1302.  * Inputs:
  1303.  *     code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  1304.  *        that n_bits =< (long)wordsize - 1.
  1305.  * Outputs:
  1306.  *     Outputs code to the file.
  1307.  * Assumptions:
  1308.  *    Chars are 8 bits long.
  1309.  * Algorithm:
  1310.  *     Maintain a BITS character long buffer (so that 8 codes will
  1311.  * fit in it exactly).  Use the VAX insv instruction to insert each
  1312.  * code in turn.  When the buffer fills up empty it and start over.
  1313.  */
  1314.  
  1315. static char buf[BITS];
  1316.  
  1317. #ifndef vax
  1318. char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  1319. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  1320. #endif !vax
  1321.  
  1322. output( code )
  1323. code_int  code;
  1324. {
  1325. #ifdef DEBUG
  1326.     static int col = 0;
  1327. #endif DEBUG
  1328.  
  1329.     /*
  1330.      * On the VAX, it is important to have the register declarations
  1331.      * in exactly the order given, or the asm will break.
  1332.      */
  1333.     register int r_off = offset, bits= n_bits;
  1334.     register char * bp = buf;
  1335.  
  1336.     if ( code >= 0 ) {
  1337. #ifdef DEBUG
  1338.     if ( verbose )
  1339.         fprintf( stderr, "%5d%c", code,
  1340.             (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
  1341. #endif DEBUG
  1342. #ifdef vax
  1343.     /* VAX DEPENDENT!! Implementation on other machines may be
  1344.      * difficult.
  1345.      *
  1346.      * Translation: Insert BITS bits from the argument starting at
  1347.      * offset bits from the beginning of buf.
  1348.      */
  1349.     0;    /* C compiler bug ?? */
  1350.     asm( "insv    4(ap),r11,r10,(r9)" );
  1351. #else not a vax
  1352. /* WARNING: byte/bit numbering on the vax is simulated by the following code
  1353. */
  1354.     /*
  1355.      * Get to the first byte.
  1356.      */
  1357.     bp += (r_off >> 3);
  1358.     r_off &= 7;
  1359.     /*
  1360.      * Since code is always >= 8 bits, only need to mask the first
  1361.      * hunk on the left.
  1362.      */
  1363.     *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  1364.     bp++;
  1365.     bits -= (8 - r_off);
  1366.     code >>= 8 - r_off;
  1367.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  1368.     if ( bits >= 8 ) {
  1369.         *bp++ = code;
  1370.         code >>= 8;
  1371.         bits -= 8;
  1372.     }
  1373.     /* Last bits. */
  1374.     if(bits)
  1375.         *bp = code;
  1376. #endif vax
  1377.     offset += n_bits;
  1378.     if ( offset == (n_bits << 3) ) {
  1379.         bp = buf;
  1380.         bits = n_bits;
  1381.         bytes_out += bits;
  1382.         do
  1383.         putchar(*bp++);
  1384.         while(--bits);
  1385.         if (ferror(stdout))
  1386.         writeerr();
  1387.         offset = 0;
  1388.     }
  1389.  
  1390.     /*
  1391.      * If the next entry is going to be too big for the code size,
  1392.      * then increase it, if possible.
  1393.      */
  1394.     if ( free_ent > maxcode || (clear_flg > 0)) {
  1395.         /*
  1396.          * Write the whole buffer, because the input side won't
  1397.          * discover the size increase until after it has read it.
  1398.          */
  1399.         if ( offset > 0 ) {
  1400.         if( fwrite( buf, 1, n_bits, stdout ) != n_bits)
  1401.             writeerr();
  1402.         bytes_out += n_bits;
  1403.         }
  1404.         offset = 0;
  1405.  
  1406.         if ( clear_flg ) {
  1407.                 maxcode = MAXCODE (n_bits = INIT_BITS);
  1408.             clear_flg = 0;
  1409.         } else {
  1410.             n_bits++;
  1411.             if ( n_bits == maxbits )
  1412.             maxcode = maxmaxcode;
  1413.             else
  1414.             maxcode = MAXCODE(n_bits);
  1415.         }
  1416. #ifdef DEBUG
  1417.         if ( debug ) {
  1418.         fprintf( stderr, "\nChange to %d bits\n", n_bits );
  1419.         col = 0;
  1420.         }
  1421. #endif DEBUG
  1422.     }
  1423.     } else {
  1424.     /*
  1425.      * At EOF, write the rest of the buffer.
  1426.      */
  1427.     if ( offset > 0 )
  1428.         fwrite( buf, 1, (offset + 7) / 8, stdout );
  1429.     bytes_out += (offset + 7) / 8;
  1430.     offset = 0;
  1431.     fflush( stdout );
  1432. #ifdef DEBUG
  1433.     if ( verbose )
  1434.         fprintf( stderr, "\n" );
  1435. #endif DEBUG
  1436.     if( ferror( stdout ) )
  1437.         writeerr();
  1438.     }
  1439. }
  1440.  
  1441. decompress() {
  1442.     register int stack_top = MAXSTACK;
  1443.     register code_int code, oldcode, incode;
  1444.     register int finchar;
  1445.     char stack[MAXSTACK];
  1446.  
  1447.     /*
  1448.      * As above, initialize the first 256 entries in the table.
  1449.      */
  1450.     maxcode = MAXCODE(n_bits = INIT_BITS);
  1451.     for ( code = 255; code >= 0; code-- ) {
  1452.     tab_prefix[code] = 0;
  1453.     tab_suffix[code] = (char_type)code;
  1454.     }
  1455.     free_ent = ((block_compress) ? FIRST : 256 );
  1456.  
  1457.     finchar = oldcode = getcode();
  1458.     putchar( (char)finchar );        /* first code must be 8 bits = char */
  1459.  
  1460.     while ( (code = getcode()) != -1 ) {
  1461.  
  1462.     if ( (code == CLEAR) && block_compress ) {
  1463.         for ( code = 255; code > 0; code -= 4 ) {
  1464.         tab_prefix [code-3] = 0;
  1465.         tab_prefix [code-2] = 0;
  1466.         tab_prefix [code-1] = 0;
  1467.         tab_prefix [code] = 0;
  1468.         }
  1469.         clear_flg = 1;
  1470.         free_ent = FIRST - 1;
  1471.         if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  1472.         break;
  1473.     }
  1474.     incode = code;
  1475.     /*
  1476.      * Special case for KwKwK string.
  1477.      */
  1478.     if ( code >= free_ent ) {
  1479.         stack[--stack_top] = finchar;
  1480.         code = oldcode;
  1481.     }
  1482.  
  1483.     /*
  1484.      * Generate output characters in reverse order
  1485.      */
  1486. #ifdef interdata
  1487.     while ( ((unsigned long)code) >= ((unsigned long)256) ) {
  1488. #else !interdata
  1489.     while ( code >= 256 ) {
  1490. #endif interdata
  1491.         stack[--stack_top] = tab_suffix[code];
  1492.         code = tab_prefix[code];
  1493.     }
  1494.     stack[--stack_top] = finchar = tab_suffix[code];
  1495.  
  1496.     /*
  1497.      * And put them out in forward order
  1498.      */
  1499.     for ( ; stack_top < MAXSTACK; stack_top++ )
  1500.         putchar(stack[stack_top]);
  1501.     if (ferror(stdout))
  1502.         writeerr ( );
  1503.     stack_top = MAXSTACK;
  1504.  
  1505.     /*
  1506.      * Generate the new entry.
  1507.      */
  1508.     if ( (code=free_ent) < maxmaxcode ) {
  1509.         tab_prefix[code] = (unsigned short)oldcode;
  1510.         tab_suffix[code] = finchar;
  1511.         free_ent = code+1;
  1512.     } 
  1513.     /*
  1514.      * Remember previous code.
  1515.      */
  1516.     oldcode = incode;
  1517.     }
  1518.     fflush( stdout );
  1519.     if(ferror(stdout))
  1520.     writeerr();
  1521. }
  1522.  
  1523.  
  1524. /*****************************************************************
  1525.  * TAG( getcode )
  1526.  *
  1527.  * Read one code from the standard input.  If EOF, return -1.
  1528.  * Inputs:
  1529.  *     stdin
  1530.  * Outputs:
  1531.  *     code or -1 is returned.
  1532.  */
  1533.  
  1534. code_int
  1535. getcode() {
  1536.     /*
  1537.      * On the VAX, it is important to have the register declarations
  1538.      * in exactly the order given, or the asm will break.
  1539.      */
  1540.     register code_int code;
  1541.     static int offset = 0, size = 0;
  1542.     static char_type buf[BITS];
  1543.     register int r_off, bits;
  1544.     register char_type *bp = buf;
  1545.  
  1546.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  1547.     /*
  1548.      * If the next entry will be too big for the current code
  1549.      * size, then we must increase the size.  This implies reading
  1550.      * a new buffer full, too.
  1551.      */
  1552.     if ( free_ent > maxcode ) {
  1553.         n_bits++;
  1554.         if ( n_bits == maxbits )
  1555.         maxcode = maxmaxcode;    /* won't get any bigger now */
  1556.         else
  1557.         maxcode = MAXCODE(n_bits);
  1558.     }
  1559.     if ( clear_flg > 0) {
  1560.             maxcode = MAXCODE (n_bits = INIT_BITS);
  1561.         clear_flg = 0;
  1562.     }
  1563.     size = fread( buf, 1, n_bits, stdin );
  1564.     if ( size <= 0 )
  1565.         return -1;            /* end of file */
  1566.     offset = 0;
  1567.     /* Round size down to integral number of codes */
  1568.     size = (size << 3) - (n_bits - 1);
  1569.     }
  1570.     r_off = offset;
  1571.     bits = n_bits;
  1572. #ifdef vax
  1573.     asm( "extzv   r10,r9,(r8),r11" );
  1574. #else not a vax
  1575.     /*
  1576.      * Get to the first byte.
  1577.      */
  1578.     bp += (r_off >> 3);
  1579.     r_off &= 7;
  1580.     /* Get first part (low order bits) */
  1581. #ifdef NO_UCHAR
  1582.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  1583. #else  NO_UCHAR
  1584.     code = (*bp++ >> r_off);
  1585. #endif NO_UCHAR
  1586.     bits -= (8 - r_off);
  1587.     r_off = 8 - r_off;        /* now, offset into code word */
  1588.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  1589.     if ( bits >= 8 ) {
  1590. #ifdef NO_UCHAR
  1591.         code |= (*bp++ & 0xff) << r_off;
  1592. #else  NO_UCHAR
  1593.         code |= *bp++ << r_off;
  1594. #endif NO_UCHAR
  1595.         r_off += 8;
  1596.         bits -= 8;
  1597.     }
  1598.     /* high order bits. */
  1599.     code |= (*bp & rmask[bits]) << r_off;
  1600. #endif vax
  1601.     offset += n_bits;
  1602.  
  1603.     return code;
  1604. }
  1605.  
  1606. char *
  1607. rindex(s, c)        /* For those who don't have it in libc.a */
  1608. register char *s, c;
  1609. {
  1610.     char *p;
  1611.     for (p = NULL; *s; s++)
  1612.         if (*s == c)
  1613.         p = s;
  1614.     return(p);
  1615. }
  1616.  
  1617. #ifdef DEBUG
  1618. printcodes()
  1619. {
  1620.     /*
  1621.      * Just print out codes from input file.  Mostly for debugging.
  1622.      */
  1623.     code_int code;
  1624.     int col = 0, bits;
  1625.  
  1626.     bits = n_bits = INIT_BITS;
  1627.     maxcode = MAXCODE(n_bits);
  1628.     free_ent = ((block_compress) ? FIRST : 256 );
  1629.     while ( ( code = getcode() ) >= 0 ) {
  1630.     if ( (code == CLEAR) && block_compress ) {
  1631.            free_ent = FIRST - 1;
  1632.            clear_flg = 1;
  1633.     }
  1634.     else if ( free_ent < maxmaxcode )
  1635.         free_ent++;
  1636.     if ( bits != n_bits ) {
  1637.         fprintf(stderr, "\nChange to %d bits\n", n_bits );
  1638.         bits = n_bits;
  1639.         col = 0;
  1640.     }
  1641.     fprintf(stderr, "%5d%c", code, (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
  1642.     }
  1643.     putc( '\n', stderr );
  1644.     exit( 0 );
  1645. }
  1646.  
  1647. dump_tab()    /* dump string table */
  1648. {
  1649.     register int i;
  1650.     register ent;
  1651.     char stack[4 * MAXSTACK];    /* \nnn makes it 4 times bigger */
  1652.     int stack_top = 4 * MAXSTACK;
  1653.  
  1654.     for ( i = 0; i < free_ent; i++ ) {
  1655.     ent = i;
  1656.     if ( isascii(tab_suffix[ent]) && isprint(tab_suffix[ent]) )
  1657.         fprintf( stderr, "%5d: %5d/'%c'  \"",
  1658.             ent, tab_prefix[ent], tab_suffix[ent] );
  1659.     else
  1660.         fprintf( stderr, "%5d: %5d/\\%03o \"",
  1661.             ent, tab_prefix[ent], tab_suffix[ent] );
  1662.     stack[--stack_top] = '\n';
  1663.     stack[--stack_top] = '"';
  1664.     for ( ; ent != NULL;
  1665.         ent = (ent >= FIRST ? tab_prefix[ent] : NULL) ) {
  1666.         if ( isascii(tab_suffix[ent]) && isprint(tab_suffix[ent]) )
  1667.         stack[--stack_top] = tab_suffix[ent];
  1668.         else {
  1669.         switch( tab_suffix[ent] ) {
  1670.         case '\n': stack[--stack_top] = 'n'; break;
  1671.         case '\t': stack[--stack_top] = 't'; break;
  1672.         case '\b': stack[--stack_top] = 'b'; break;
  1673.         case '\f': stack[--stack_top] = 'f'; break;
  1674.         case '\r': stack[--stack_top] = 'r'; break;
  1675.         default:
  1676.             stack[--stack_top] = '0' + tab_suffix[ent] % 8;
  1677.             stack[--stack_top] = '0' + (tab_suffix[ent] / 8) % 8;
  1678.             stack[--stack_top] = '0' + tab_suffix[ent] / 64;
  1679.             break;
  1680.         }
  1681.         stack[--stack_top] = '\\';
  1682.         }
  1683.     }
  1684.     fwrite( &stack[stack_top], 1, 4 * MAXSTACK - stack_top, stderr );
  1685.     stack_top = 4 * MAXSTACK;
  1686.     }
  1687. }
  1688. #endif DEBUG
  1689.  
  1690. /*****************************************************************
  1691.  * TAG( writeerr )
  1692.  *
  1693.  * Exits with a message.  We only check for write errors often enough
  1694.  * to avoid a lot of "file system full" messages, not on every write.
  1695.  * ferror() check after fflush will catch any others (I trust).
  1696.  *
  1697.  */
  1698.  
  1699. writeerr()
  1700. {
  1701.     perror ( ofname );
  1702.     unlink ( ofname );
  1703.     exit ( 1 );
  1704. }
  1705.  
  1706. copystat(ifname, ofname)
  1707. char *ifname, *ofname;
  1708. {
  1709.     struct stat statbuf;
  1710.     int mode;
  1711.     time_t timep[2];
  1712.  
  1713.     fclose(stdout);
  1714.     if (stat(ifname, &statbuf)) {        /* Get stat on input file */
  1715.     perror(ifname);
  1716.     return;
  1717.     }
  1718.     if ((statbuf.st_mode & S_IFMT/*0170000*/) != S_IFREG/*0100000*/) {
  1719.     if(quiet)
  1720.         fprintf(stderr, "%s: ", ifname);
  1721.     fprintf(stderr, " -- not a regular file: unchanged");
  1722.     exit_stat = 1;
  1723.     } else if (statbuf.st_nlink > 1) {
  1724.     if(quiet)
  1725.         fprintf(stderr, "%s: ", ifname);
  1726.     fprintf(stderr, " -- has %d other links: unchanged",
  1727.         statbuf.st_nlink - 1);
  1728.     exit_stat = 1;
  1729.     } else if (exit_stat == 2 && (!force)) { /* No compression: remove file.Z */
  1730.     fprintf(stderr, " -- file unchanged");
  1731.     } else {            /* ***** Successful Compression ***** */
  1732.     exit_stat = 0;
  1733.     mode = statbuf.st_mode & 07777;
  1734.     if (chmod(ofname, mode))        /* Copy modes */
  1735.         perror(ofname);
  1736.     chown(ofname, statbuf.st_uid, statbuf.st_gid);    /* Copy ownership */
  1737.     timep[0] = statbuf.st_atime;
  1738.     timep[1] = statbuf.st_mtime;
  1739.     utime(ofname, timep);    /* Update last accessed and modified times */
  1740.     if (unlink(ifname))    /* Remove input file */
  1741.         perror(ifname);
  1742.     if(!quiet)
  1743.         fprintf(stderr, " -- replaced with %s", ofname);
  1744.     return;        /* Successful return */
  1745.     }
  1746.  
  1747.     /* Unsuccessful return -- one of the tests failed */
  1748.     if (unlink(ofname))
  1749.     perror(ofname);
  1750. }
  1751. /*
  1752.  * This routine returns 1 if we are running in the foreground and stderr
  1753.  * is a tty.
  1754.  */
  1755. foreground()
  1756. {
  1757.     if(bgnd_flag) {    /* background? */
  1758.         return(0);
  1759.     } else {            /* foreground */
  1760.         if(isatty(2)) {        /* and stderr is a tty */
  1761.             return(1);
  1762.         } else {
  1763.             return(0);
  1764.         }
  1765.     }
  1766. }
  1767.  
  1768. onintr ( )
  1769. {
  1770.     unlink ( ofname );
  1771.     exit ( 1 );
  1772. }
  1773.  
  1774. clear ()        /* table clear for block compress */
  1775. {
  1776.     register code_int i;
  1777.     register count_int *p, *endp;
  1778.     register unsigned short *q;
  1779.  
  1780. #ifdef DEBUG
  1781.     if(debug)
  1782.             fprintf ( stderr, "count: %ld ratio: %f\n", in_count,
  1783.              (double) in_count / (double) bytes_out );
  1784. #endif DEBUG
  1785.  
  1786.     checkpoint = in_count + CHECK_GAP;
  1787.     if ( (double) in_count / (double) bytes_out > ratio )
  1788.     ratio = (double) in_count / (double) bytes_out;
  1789.     else {
  1790.     ratio = 0.0;
  1791. #ifdef USERMEM
  1792.     if ( maxbits <= FBITS )         /* sparse array clear */
  1793.         for ( i = (1 << maxbits) - 1; i >= 0; i-- )
  1794.         ftable [fcodemem [i]] = 0;    /* indirect thru "shadow" */
  1795.     else 
  1796. #endif USERMEM                    /* hash table clear */
  1797.     {
  1798.         endp = &htab [hsize];
  1799.         for ( p = &htab [0], q = &codetab [0]; p < endp; ) {
  1800.         *p++ = -1;
  1801.         *q++ = 0;
  1802.         }
  1803.         creset ( MAX_CACHE );
  1804.     }
  1805.     free_ent = FIRST;
  1806.     clear_flg = 1;
  1807.     output ( (code_int) CLEAR );
  1808. #ifdef DEBUG
  1809.     if(debug)
  1810.             fprintf ( stderr, "clear\n" );
  1811. #endif DEBUG
  1812.     }
  1813. }
  1814.  
  1815. creset ( n )    /* clear hash cache */
  1816.     register count_int n;    /* clear at least this many entries */
  1817. {
  1818.     register count_int i;
  1819.     register unsigned short *hash_p;
  1820.     register unsigned short zero = 0;
  1821.     static int nfiles = 0;
  1822.  
  1823.     if ( nfiles++ == 0 )    /* No clear needed if first time */
  1824.     return;
  1825.     n = (n+15) & (-16);
  1826.     hash_p = hashcache + n;
  1827.     for ( i = n; i > 0; i -=16 ) {
  1828.     *(hash_p-16) = zero;
  1829.     *(hash_p-15) = zero;
  1830.     *(hash_p-14) = zero;
  1831.     *(hash_p-13) = zero;
  1832.     *(hash_p-12) = zero;
  1833.     *(hash_p-11) = zero;
  1834.     *(hash_p-10) = zero;
  1835.     *(hash_p-9) = zero;
  1836.     *(hash_p-8) = zero;
  1837.     *(hash_p-7) = zero;
  1838.     *(hash_p-6) = zero;
  1839.     *(hash_p-5) = zero;
  1840.     *(hash_p-4) = zero;
  1841.     *(hash_p-3) = zero;
  1842.     *(hash_p-2) = zero;
  1843.     *(hash_p-1) = zero;
  1844.     hash_p -= 16;
  1845.     }
  1846. }
  1847.  
  1848. hogtally ()    /* compute character code hog */
  1849. {
  1850.     register int i, most;
  1851.  
  1852.     for ( i = most = 0; i < 256; i++ )
  1853.     if ( cfreq [i] >= cfreq [most] )
  1854.         most = i;
  1855.     return ( most );
  1856. }
  1857.  
  1858. cl_hash(hsize)
  1859.     register int hsize;
  1860. {
  1861.     register count_int *htab_p = htab+hsize;
  1862.     register int i;
  1863.     register long m1 = -1;
  1864.  
  1865.     /* clear hashcache */
  1866. #define    min(a,b)    ((a>b) ? b : a)
  1867.     creset( min((count_int)hsize, MAX_CACHE) );
  1868.  
  1869.     i = hsize - 16;
  1870.     do {
  1871.         *(htab_p-16) = m1;
  1872.         *(htab_p-15) = m1;
  1873.         *(htab_p-14) = m1;
  1874.         *(htab_p-13) = m1;
  1875.         *(htab_p-12) = m1;
  1876.         *(htab_p-11) = m1;
  1877.         *(htab_p-10) = m1;
  1878.         *(htab_p-9) = m1;
  1879.         *(htab_p-8) = m1;
  1880.         *(htab_p-7) = m1;
  1881.         *(htab_p-6) = m1;
  1882.         *(htab_p-5) = m1;
  1883.         *(htab_p-4) = m1;
  1884.         *(htab_p-3) = m1;
  1885.         *(htab_p-2) = m1;
  1886.         *(htab_p-1) = m1;
  1887.         htab_p -= 16;
  1888.     } while ((i -= 16) >= 0);
  1889.         for ( i += 16; i > 0; i-- )
  1890.         *--htab_p = m1;
  1891. }
  1892. ------ EOF ------
  1893. ls -l compress.c
  1894. cat >zmore.l <<'------ EOF ------'
  1895. .TH ZMORE 1
  1896. .SH NAME
  1897. zmore \- file perusal filter for crt viewing of compressed text
  1898. .SH SYNOPSIS
  1899. .B zmore
  1900. [ name ...  ]
  1901. .SH DESCRIPTION
  1902. .I  Zmore
  1903. is a filter which allows examination of compressed text files
  1904. one screenful at a time on a soft-copy terminal.
  1905. It normally pauses after each screenful, printing --More--
  1906. at the bottom of the screen.
  1907. If the user then types a carriage return, one more line is displayed.
  1908. If the user hits a space,
  1909. another screenful is displayed.  Other possibilites are enumerated later.
  1910. .PP
  1911. .I Zmore
  1912. looks in the file
  1913. .I /etc/termcap
  1914. to determine terminal characteristics,
  1915. and to determine the default window size.
  1916. On a terminal capable of displaying 24 lines,
  1917. the default window size is 22 lines.
  1918. .PP
  1919. Other sequences which may be typed when
  1920. .I zmore
  1921. pauses, and their effects, are as follows (\fIi\fP is an optional integer
  1922. argument, defaulting to 1) :
  1923. .PP
  1924. .IP \fIi\|\fP<space>
  1925. display
  1926. .I i
  1927. more lines, (or another screenful if no argument is given)
  1928. .PP
  1929. .IP ^D
  1930. display 11 more lines (a ``scroll'').
  1931. If
  1932. .I i
  1933. is given, then the scroll size is set to \fIi\|\fP.
  1934. .PP
  1935. .IP d
  1936. same as ^D (control-D)
  1937. .PP
  1938. .IP \fIi\|\fPz
  1939. same as typing a space except that \fIi\|\fP, if present, becomes the new
  1940. window size.  Note that the window size reverts back to the default at the
  1941. end of the current file.
  1942. .PP
  1943. .IP \fIi\|\fPs
  1944. skip \fIi\|\fP lines and print a screenful of lines
  1945. .PP
  1946. .IP \fIi\|\fPf
  1947. skip \fIi\fP screenfuls and print a screenful of lines
  1948. .PP
  1949. .IP "q or Q"
  1950. quit reading the current file; go on to the next (if any)
  1951. .PP
  1952. .IP e
  1953. When the prompt --More--(Next file: 
  1954. .IR file )
  1955. is printed, this command causes zmore to exit.
  1956. .PP 
  1957. .IP =
  1958. Display the current line number.
  1959. .PP
  1960. .IP \fIi\|\fP/expr
  1961. search for the \fIi\|\fP-th occurrence of the regular expression \fIexpr.\fP
  1962. If the pattern is not found,
  1963. .I zmore
  1964. goes on to the next file (if any).
  1965. Otherwise, a screenful is displayed, starting two lines before the place
  1966. where the expression was found.
  1967. The user's erase and kill characters may be used to edit the regular
  1968. expression.
  1969. Erasing back past the first column cancels the search command.
  1970. .PP
  1971. .IP \fIi\|\fPn
  1972. search for the \fIi\|\fP-th occurrence of the last regular expression entered.
  1973. .PP
  1974. .IP !command
  1975. invoke a shell with \fIcommand\|\fP. 
  1976. The character `!' in "command" are replaced with the
  1977. the previous shell command.  The sequence "\\!" is replaced by "!".
  1978. .PP
  1979. .IP ":q or :Q"
  1980. quit reading the current file; go on to the next (if any)
  1981. (same as q or Q).
  1982. .PP
  1983. .IP .
  1984. (dot) repeat the previous command.
  1985. .PP
  1986. The commands take effect immediately, i.e., it is not necessary to
  1987. type a carriage return.
  1988. Up to the time when the command character itself is given,
  1989. the user may hit the line kill character to cancel the numerical
  1990. argument being formed.
  1991. In addition, the user may hit the erase character to redisplay the
  1992. --More-- message.
  1993. .PP
  1994. At any time when output is being sent to the terminal, the user can
  1995. hit the quit key (normally control\-\\).
  1996. .I Zmore
  1997. will stop sending output, and will display the usual --More--
  1998. prompt.
  1999. The user may then enter one of the above commands in the normal manner.
  2000. Unfortunately, some output is lost when this is done, due to the
  2001. fact that any characters waiting in the terminal's output queue
  2002. are flushed when the quit signal occurs.
  2003. .PP
  2004. The terminal is set to
  2005. .I noecho
  2006. mode by this program so that the output can be continuous.
  2007. What you type will thus not show on your terminal, except for the / and !
  2008. commands.
  2009. .PP
  2010. If the standard output is not a teletype, then
  2011. .I zmore
  2012. acts just like
  2013. .I zcat,
  2014. except that a header is printed before each file.
  2015. .SH FILES
  2016. .DT
  2017. /etc/termcap        Terminal data base
  2018. .SH "SEE ALSO"
  2019. more(1), zcat(1), compress(1), uncompress(1)
  2020. ------ EOF ------
  2021. ls -l zmore.l
  2022. cat >zmore <<'------ EOF ------'
  2023. FIRST=1
  2024. for FILE
  2025. do
  2026.     if test $FIRST -eq 0; then
  2027.         echo "--More--(Next file: $FILE)\c"
  2028.         stty cbreak -echo
  2029.         ANS=`dd bs=1 count=1 2>/dev/null` 
  2030.         stty -cbreak echo
  2031.         echo " "
  2032.         if test "$ANS" = 'e'; then
  2033.             exit
  2034.         fi
  2035.     fi
  2036.     echo "------> $FILE <------"
  2037.     zcat $FILE | more
  2038.     if test -t; then
  2039.         FIRST=0
  2040.     fi
  2041. done
  2042. ------ EOF ------
  2043. chmod +x zmore
  2044. ls -l zmore
  2045.  
  2046.  
  2047. From decvax!decwrl!turtlevax!ken  Mon Jan  7 11:12:12 EST 1985
  2048. Article: 2384 of net.sources
  2049. Relay-Version: version B 2.10.2 9/3/84; site genrad.UUCP
  2050. Posting-Version: version B 2.10.2 9/18/84; site turtlevax.UUCP
  2051. Path: genrad!decvax!decwrl!turtlevax!ken
  2052. >From: ken@turtlevax.UUCP (Ken Turkowski)
  2053. Newsgroups: net.sources
  2054. Subject: Re: Compress release 3.0 : sample Makefile
  2055. Message-ID: <623@turtlevax.UUCP>
  2056. Date: 5 Jan 85 11:35:20 GMT
  2057. Date-Received: 6 Jan 85 03:04:38 GMT
  2058. References: <578@genrad.UUCP>
  2059. Organization: CADLINC, Inc. @ Menlo Park, CA
  2060. Lines: 116
  2061.  
  2062. In the compress 3.0 source recently posted to mod.sources, there is a
  2063. #define variable which can be set for optimum performance on a machine
  2064. with a large amount of memory.  A program (usermem) to calculate the
  2065. useable amount of physical user memory is enclosed, as well as a sample
  2066. 4.2bsd Vax Makefile for compress.
  2067.  
  2068. -----------------------------------------------------------------
  2069.  
  2070. # This is a shell archive.  Remove anything before this line, then
  2071. # unpack it by saving it in a file and typing "sh file".  (Files
  2072. # unpacked will be owned by you and have default permissions.)
  2073. #
  2074. # This archive contains:
  2075. # Makefile usermem
  2076.  
  2077. echo x - Makefile
  2078. cat > "Makefile" << '//E*O*F Makefile//'
  2079. # if you have bugs in your C compiler dont use -O
  2080. COMFLAGS=-DBSD4_2 -O -DSACREDMEM=256000
  2081. BIN=/usr/bin
  2082.  
  2083. compress : compress.c USERMEM
  2084.     cc $(COMFLAGS) -DUSERMEM=`cat USERMEM` -o compress compress.c
  2085.  
  2086. # USERMEM may have to be set by hand.  It should contain the amount of
  2087. # available user memory in bytes.  Set it to zero, for physical memory
  2088. # less than 1 Meg.
  2089. USERMEM:
  2090.     sh usermem > USERMEM
  2091.  
  2092. install: compress
  2093.     cp compress $BIN
  2094.     rm -f $BIN/uncompress $BIN/zcat
  2095.     ln $BIN/compress $BIN/uncompress
  2096.     ln $BIN/compress $BIN/zcat
  2097. //E*O*F Makefile//
  2098.  
  2099. echo x - usermem
  2100. cat > "usermem" << '//E*O*F usermem//'
  2101. : This shell script snoops around to find the maximum amount of available
  2102. : user memory.  These variables need to be set only if there is no
  2103. : /usr/adm/messages.  KMEM, UNIX, and CLICKSIZE can be set on the command
  2104. : line, if desired, e.g. UNIX=/unix
  2105. KMEM=/dev/kmem        # User needs read access to KMEM
  2106. UNIX=
  2107. # VAX            CLICKSIZE=512,    UNIX=/vmunix
  2108. # PDP-11        CLICKSIZE=64,    UNIX=/unix
  2109. # CADLINC 68000        CLICKSIZE=4096,    UNIX=/unix
  2110. # Perkin-Elmer 3205    CLICKSIZE=4096,    UNIX=/edition7
  2111. # Perkin-Elmer all others, CLICKSIZE=2048, UNIX=/edition7
  2112. CLICKSIZE=512
  2113. eval $*
  2114.  
  2115. SIZE=0
  2116. if test -r /usr/adm/messages    # probably the most transportable
  2117. then
  2118.     SIZE=`grep avail /usr/adm/messages | sed -n '$s/.*[     ]//p'`
  2119. fi
  2120.  
  2121. if test 0$SIZE -le 0        # no SIZE in /usr/adm/messages
  2122. then
  2123.     if test -r $KMEM        # Readable KMEM
  2124.     then
  2125.     if test -n "$UNIX"
  2126.     then
  2127.         : User must have specified it already.
  2128.     elif test -r /vmunix
  2129.     then
  2130.         UNIX=/vmunix
  2131.         CLICKSIZE=512    # Probably VAX
  2132.     elif test -r /edition7
  2133.     then
  2134.         UNIX=/edition7
  2135.         CLICKSIZE=2048    # Perkin-Elmer: change to 4096 on a 3205
  2136.     elif test -r /unix
  2137.     then
  2138.         UNIX=/unix        # Could be anything
  2139.     fi
  2140.     if test -n "$UNIX"
  2141.     then
  2142.         SIZE=`echo maxmem/D | adb $UNIX $KMEM | sed -n '$s/.*[     ]//p'`
  2143.         if test 0$SIZE -le 0
  2144.         then
  2145.         SIZE=`echo physmem/D | adb $UNIX $KMEM | sed -n '$s/.*[     ]//p'`
  2146.         fi
  2147.         SIZE=`expr 0$SIZE '*' $CLICKSIZE`
  2148.     fi
  2149.     fi
  2150. fi
  2151.  
  2152. if test 0$SIZE -le 0
  2153. then
  2154.     echo 0
  2155. else
  2156.     echo $SIZE
  2157. fi
  2158. //E*O*F usermem//
  2159.  
  2160. echo Possible errors detected by \'sum\' [hopefully none]:
  2161. temp=/tmp/shar$$
  2162. trap "rm -f $temp; exit" 0 1 2 3 15
  2163. cat > $temp <<\!!!
  2164. 14495     1 Makefile
  2165. 42168     2 usermem
  2166. !!!
  2167. sum  Makefile usermem | sed 's=[^ ]*/==' | diff -b $temp -
  2168. exit 0
  2169.  
  2170. --
  2171. Ken Turkowski @ CADLINC, Menlo Park, CA
  2172. UUCP: {amd,decwrl,nsc,spar}!turtlevax!ken
  2173. ARPA: turtlevax!ken@DECWRL.ARPA
  2174. -- 
  2175. Ken Turkowski @ CADLINC, Menlo Park, CA
  2176. UUCP: {amd,decwrl,nsc,spar}!turtlevax!ken
  2177. ARPA: turtlevax!ken@DECWRL.ARPA
  2178.  
  2179.  
  2180.