home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / b / vmslz1.arc < prev    next >
Text File  |  2020-01-01  |  43KB  |  1,537 lines
  1. -h- readme.txt    Wed Jul 24 11:49:28 1985    USER$A:[MINOW.LZ]README.TXT;1
  2. This is a rewrite of the Unix compress utility.  It is *not*
  3. switch-compatible with Unix compress, however it is (almost)
  4. file-compatible (when compiled on Unix, or when "export" mode
  5. is selected on VMS Version 4).
  6.  
  7. The advantages of this version are as follows:
  8.  
  9. 1. Compress and decompress are separate programs, simplifying the
  10.    problems of the small system implementor.  Both run on an
  11.    unmapped PDP-11 (with a maximum of 12 bits).
  12.  
  13.    The command interface is just
  14.  
  15.     lzcomp input compressed_output
  16.     lzdcmp compressed_input output
  17.  
  18.    Input files are not deleted.
  19.  
  20. 2. The compression algorithm and I/O design is intended to simplify
  21.    embedding the programs (as subroutines) in some other task.
  22.    (for example, in a database package.)
  23.  
  24. 3. On non-Unix systems, the I/O design should be significantly
  25.    faster.  It should be slightly faster on Unix.
  26.  
  27. The only disadvantage is that, as noted, it is not command (option)
  28. compatible with Unix compress.  Also, some periferal functionality
  29. (such as the deletion of input files and the output file naming
  30. conventions) have not been implemented.
  31.  
  32. On Unix (i.e., in "export" mode), the compressed data file is
  33. identical to the Unix file, *except* that lzcomp writes two
  34. CLEAR codes in a row to signal end-of-file (and lzdcmp treats
  35. two CLEAR codes in a row as signalling end-of-file).
  36.  
  37. lzcomp and lzdcmp have been added to the Decus C distribution.
  38.  
  39. Martin Minow
  40. decvax!minow,
  41. minow%rex.dec@decwrl.arpa
  42.  
  43. -h- lzcmp1.c    Wed Jul 24 11:49:28 1985    USER$A:[MINOW.LZ]LZCMP1.C;21
  44. /*
  45.  *        lzcomp [-options] infile outfile
  46.  */
  47. #ifdef    DOCUMENTATION
  48.  
  49. title    lzcomp    File Compression
  50. index        File compression
  51.  
  52. synopsis
  53.     .s.nf
  54.     lzcomp [-options] [infile [outfile]]
  55.     .s.f
  56. description
  57.  
  58.     lzcomp implements the Lempel-Ziv file compression algorithm.
  59.     (Files compressed by lzcomp are uncompressed by lzdcmp.)
  60.     It operates by finding common substrings and replaces them
  61.     with a variable-size code.  This is deterministic, and
  62.     can be done with a single pass over the file.  Thus,
  63.     the decompression procedure needs no input table, but
  64.     can track the way the table was built.
  65.  
  66.     Options may be given in either case.
  67.     .lm +8
  68.     .p -8
  69.     -B    Input file is "binary", not "human readable text".
  70.     This is necessary on Dec operating systems, such as VMS and
  71.     RSX-11M, that treat these files differently.  (Note that binary
  72.     support is rudamentary and probably insufficient as yet.)
  73.     (On VMS version 4, this is ignored unless the -x option is
  74.     specified or the input file is record-oriented.)
  75.     .p -8
  76.     -M bits    Write using the specified number of bits in the
  77.     code -- necessary for big machines making files for little
  78.     machines.  For example, if compressing a file on VMS
  79.     which is to be read on a PDP-11, you should select -M 12.
  80.     .p -8
  81.     -V [n]    Verbose if specified.  If a value is specified,
  82.     it will enable debugging code (if compiled in).
  83.     .p -8
  84.     -X [n]    "Export" -- write a file format that can be read by
  85.     other operating systems.  Only the bytes in the file are copied;
  86.     file attributes are not preserved.  If specified, the value
  87.     determines the level of compatiblity.  If not specified,
  88.     or specified with an explicit value of zero, and lzcomp is
  89.     running on Vax/VMS version 4 under VaxC and the input file
  90.     is a disk or magtape file (block-oriented), a VMS-private output
  91.     format is used which is incompatible with the Unix compress
  92.     utility, but which preserves VMS file attributes.  -X may
  93.     take on the following values:
  94.     .lm +4.s
  95.     .i -4;#0##Choose VMS private format.  See restrictions below.
  96.     .i -4;#1##Compatible with Unix compress version 3.0:
  97.     this is the default if -x is given without a value.
  98.     .i -4;#2##As above, but supress "block compression"
  99.     .i -4;#3##Supress block compression and do not output
  100.     a compress header block.  This is for compatiblity
  101.     with a quite early version of Unix compress (and requires
  102.     conditional-compilation to use).
  103.     .lm -4.s
  104.     Note that the -B (binary) option is ignored unless
  105.     the input file is "record-oriented", such as a terminal
  106.     or mailbox.
  107.     .lm -8.s
  108.     The other two arguments are the input and output
  109.     filenames respectively.  Redirection is supported,
  110.     however, the output must be a disk/tape file.
  111.  
  112.     The file format is almost identical to the current
  113.     Unix implementation of compress (V4.0).  Files written
  114.     by Unix compress should be readable by lzdcmp.  Files
  115.     written by lzcomp in export (-x) format will be
  116.     readable by Unix compress (except that lzcomp outputs
  117.     two "clear" codes to mark EOF.  A patch to Unix
  118.     compress is available.)
  119.  
  120. VMS Restrictions
  121.  
  122.     VMS Private mode stores the true name and attributes
  123.     of the input file into the compressed file and lzdcmp
  124.     restores the attributes (and filename if requested).
  125.     The following restrictions apply -- they may be lifted
  126.     in the future as they are primarily due to the author's
  127.     lack of understanding of the intricacies of of VMS I/O:
  128.  
  129.         All files must be stored on disk.
  130.         The lzcomp output file must be specified directly.
  131.  
  132.     Also, for all usage on VMS, the compressed file must
  133.     be written to, and read from disk.
  134.  
  135. LZW compression algorithm
  136.  
  137.     This section is abstracted from Terry Welch's article
  138.     referenced below.  The algorithm builds a string
  139.     translation table that maps substrings in the input
  140.     into fixed-length codes.  The compress algorithm may
  141.     be described as follows:
  142.  
  143.       1. Initialize table to contain single-character
  144.          strings.
  145.       2. Read the first character.  Set <w> (the prefix
  146.          string) to that character.
  147.       3. (step): Read next input character, K.
  148.        4. If at end of file, output code(<w>); exit.
  149.       5. If <w>K is in the string table:
  150.         Set <w> to <w>K; goto step 3.
  151.       6. Else <w>K is not in the string table.
  152.         Output code(<w>);
  153.         Put <w>K into the string table;
  154.         Set <w> to K; Goto step 3.
  155.  
  156.     "At each execution of the basic step an acceptable input
  157.     string <w> has been parsed off.  The next character K is
  158.     read and the extended string <w>K is tested to see if it
  159.     exists in the string table.  If it is there, then the
  160.     extended string becomes the parsed string <w> and the
  161.     step is repeated.  If <w>K is not in the string table,
  162.     then it is entered, the code for the successfully
  163.     parsed string <w> is put out as comprssed data, the
  164.     character K becomes the beginning of the next string,
  165.     and the step is repeated."
  166.  
  167.     The decompression algorithm translates each received
  168.     code into a prefix string and extension [suffix] character.
  169.     The extension character is stored (in a push-down stack),
  170.     and the prefix translated again, until the prefix is a
  171.     single character, which completes decompression of this
  172.     code.  The entire code is then output by popping the
  173.     stack.
  174.  
  175.     "An update to the string table is made for each code received
  176.     (except the first one).  When a code has been translated,
  177.     its final character is used as the extension character,
  178.     combined with the prior string, to add a new string to
  179.     the string table.  This new string is assigned a unique
  180.     code value, which is the same code that the compressor
  181.     assigned to that string.  In this way, the decompressor
  182.     incrementally reconstructs the same string table that
  183.     the decompressor used.... Unfortunately ... [the algorithm]
  184.     does not work for an abnormal case.
  185.  
  186.     The abnormal case occurs whenever an input character string
  187.     contains the sequence K<w>K<w>K, where K<w> already
  188.     appears in the compressor string table."
  189.  
  190.     The decompression algorithm, augmented to handle
  191.     the abnormal case, is as follows:
  192.  
  193.       1. Read first input code;
  194.          Store in CODE and OLDcode;
  195.          With CODE = code(K), output(K);  FINchar = K;
  196.       2. Read next code to CODE; INcode = CODE;
  197.          If at end of file, exit;
  198.       3. If CODE not in string table (special case) then
  199.         Output(FINchar);
  200.         CODE = OLDcode;
  201.         INcode = code(OLDcode, FINchar);
  202.     
  203.       4. If CODE == code(<w>K) then
  204.         Push K onto the stack;
  205.         CODE == code(<w>);
  206.         Goto 4.
  207.  
  208.       5. If CODE == code(K) then
  209.         Output K;
  210.         FINchar = K;
  211.  
  212.       6. While stack not empty
  213.         Output top of stack;
  214.         Pop stack;
  215.  
  216.       7. Put OLDcode,K into the string table.
  217.          OLDcode = INcode;
  218.          Goto 2.
  219.  
  220.     The algorithm as implemented here introduces two additional
  221.     complications.
  222.  
  223.     The actual codes are transmitted using a variable-length
  224.     encoding.  The lowest-level routines increase the number
  225.     of bits in the code when the largest possible code is
  226.     transmitted.
  227.  
  228.     Periodically, the algorithm checks that compression is
  229.     still increasing.  If the ratio of input bytes to output
  230.     bytes decreases, the entire process is reset.  This can
  231.     happen if the characteristics of the input file change.
  232.  
  233. VMS Private File Structure
  234.  
  235.     In VMS Private mode, the compressed data file contains
  236.     a variable-length (but compressed) file header with the
  237.     file "attributes" needed by the operating system to
  238.      construct the file.  This allows the decompression
  239.     program to recreate the file in its original format,
  240.     which is essential if ISAM databases are compressed.
  241.  
  242.     The overall file format is as follows:
  243.     .lm +8
  244.     .p -8
  245.     LZ_SOH    "start of header" signal (this value cannot appear
  246.     in user data).
  247.  
  248.     A variable-length data record (maximum 256 bytes)
  249.     containing the header name, followed by whitespace, followed
  250.     by header-specific information.  In this case, the name
  251.     record will contain the string "vms$attributes" followed
  252.     by the number of bytes in the attribute data block.
  253.     (I assume that the name record will consist of a facility
  254.     name, such as "vms", followed by a dollar sign, followed
  255.     by a facility-unique word.)
  256.     .p -8
  257.     LZ_EOR    Signals "end of record".
  258.  
  259.     This is followed by a VMS file attributes record (generated
  260.     by a VMS system library    routine).
  261.     .p -8
  262.     LZ_ETX    Signals "end of segment".
  263.     .p -8
  264.     ST_STX    Signals "start of text" (i.e., start of data file).
  265.  
  266.     This is followed by the user data file.
  267.     .p -8
  268.     LZ_ETX    Signals "end of segment"
  269.     .p -8
  270.     LZ_ETX    Two in a row signals "end of file".
  271.     .s.lm -8
  272.     Note that this format can easily be extended to include
  273.     trailer records (with file counts and checksums) and/or
  274.     multiple data files in one compressed file.
  275.  
  276.     Note also that the LZ_CLEAR code may appear in headers
  277.     or data files to cause the decompression program to
  278.     "readapt" to the characteristics of the input data.
  279.     LZ_STX and LZ_SOH reset the compression algorithm.
  280.     LZ_EOR does not.
  281.  
  282. Authors
  283.  
  284.     The algorithm is from "A Technique for High Performance
  285.     Data Compression."  Terry A. Welch. IEEE Computer Vol 17,
  286.     No. 6 (June 1984), pp 8-19.
  287.  
  288.     This revision is by Martin Minow.
  289.  
  290.     Unix Compress authors are as follows:
  291.     .s.nf
  292.     Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  293.     Jim McKie        (decvax!mcvax!jim)
  294.     Steve Davies        (decvax!vax135!petsd!peora!srd)
  295.     Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  296.     James A. Woods        (decvax!ihnp4!ames!jaw)
  297.     Joe Orost        (decvax!vax135!petsd!joe)
  298.     .s.f
  299.  
  300. #endif
  301.  
  302. /*
  303.  * Compatible with compress.c, v3.0 84/11/27
  304.  */
  305.  
  306. /*)BUILD
  307.  *        $(PROGRAM) = lzcomp
  308.  *        $(INCLUDE) = lz.h
  309.  *        $(FILES) = { lzcmp1.c lzcmp2.c lzcmp3.c lzio.c lzvio.c }
  310.  */
  311.  
  312. #include    "lz.h"
  313.  
  314.  
  315. #ifdef unix
  316. #include <sys/types.h>
  317. #include <sys/stat.h>
  318. #endif
  319.  
  320. /*
  321.  * These global parameters are written to the compressed file.
  322.  * The decompressor needs them.  The initialized values are defaults
  323.  * and are modified by command line arguments.
  324.  */
  325. short        maxbits = BITS;        /* settable max # bits/code    */
  326. code_int maxmaxcode = 1 << BITS;     /* Totally largest code    */
  327. code_int    hsize = HSIZE;        /* Actual hash table size    */
  328.  
  329. /*
  330.  * Flags (command line arguments) to control compression.
  331.  */
  332. #if VMS_V4
  333. flag        export = 0;        /* Assume vms "private" mode    */
  334. #else
  335. flag        export = 1;        /* Assume Unix compatible mode    */
  336. #endif
  337. flag        block_compress = TRUE;    /* Assume block compression    */
  338. flag        binary = FALSE;        /* Reading text file if FALSE    */
  339. flag        noheader = FALSE;    /* No magic header if TRUE    */
  340. flag        verbose = VERBOSE_DEFAULT; /* Non-zero for status/debug    */
  341. flag        background = FALSE;    /* TRUE (Unix) if detached    */
  342. readonly flag    is_compress = TRUE;    /* for lzio.c (needed?)        */
  343. long        fsize;            /* Input file size in bytes    */
  344. char        *infilename = NULL;    /* For error printouts        */
  345. char        *outfilename = NULL;    /* For openoutput and errors    */
  346. int        firstcode;        /* First code after internals    */
  347. count_int    tot_incount = 0;    /* Total number of input bytes    */
  348. count_int    tot_outcount = 0;    /* Total number of output codes    */
  349. extern count_int in_count;
  350. extern count_int out_count;
  351. static long    start_time;        /* Time we started (in msec)    */
  352. extern long    cputime();        /* Returns process time in msec    */
  353. STREAM        instream;
  354. STREAM        outstream;
  355. char_type    inbuffer[MAXIO];
  356. char_type    outbuffer[MAXIO];
  357. static STREAM    mem_stream;
  358. jmp_buf        failure;
  359. #if VMS_V4
  360. #include types
  361. #include stat
  362. #include descrip
  363. #ifndef FDLSTUFF
  364. #define FDLSTUFF char
  365. #endif
  366. FDLSTUFF    *fdl_input;
  367. FDLSTUFF    *fdl_output;
  368. static struct dsc$descriptor fdl_descriptor;
  369. #endif
  370.  
  371. main(argc, argv)
  372. int        argc;
  373. char        *argv[];
  374. /*
  375.  * Compress mainline
  376.  */
  377. {
  378. #ifndef    decus
  379.     /*
  380.      * background is TRUE if running detached from the command terminal.
  381.      */
  382.     background = (signal(SIGINT, SIG_IGN) == SIG_IGN) ? TRUE : FALSE;
  383.     if (!background)
  384.         background = !isatty(fileno(stderr));
  385.     if (!background) {
  386.         if (verbose > 0)
  387.         signal(SIGINT, abort);
  388.         else {
  389.         signal(SIGINT, interrupt);
  390.         signal(SIGSEGV, address_error);
  391.         }
  392.     }
  393. #endif
  394.     if (setjmp(failure) == 0) {
  395.         setup(argc, argv);        /* Command line parameters    */
  396.         openinput();        /* Open input, set instream    */
  397.         getfilesize();        /* Get input file size        */
  398.         gethashsize();        /* Get actual hash table size    */
  399.         initialize();        /* Set maxbits and the like    */
  400.         openoutput();        /* Open output file        */
  401.         if (verbose > 0)
  402.         start_time = cputime();
  403.         put_magic_header();
  404.         init_compress(TRUE);
  405.         compress(&instream);
  406. #if VMS_V4
  407.         if (export == 0) {
  408.         outputcode((code_int) LZ_ETX);
  409.         outputcode((code_int) LZ_ETX);
  410.         fdl_close(fdl_input);
  411.         }
  412.         else
  413. #endif
  414.         if (block_compress) {
  415.         outputcode((code_int) LZ_CLEAR);
  416.         outputcode((code_int) LZ_CLEAR);
  417.         }
  418.         outputcode((code_int) -1);        /* Flush output buffers    */
  419. #if VMS_V4
  420.         if (export == 0)
  421.         fdl_close(fdl_output);
  422.         else {
  423.         fclose(stdout);
  424.         }
  425. #else
  426.         fclose(stdout);
  427. #endif
  428.         if (verbose > 0) {
  429.         start_time = cputime() - start_time;
  430.         tot_incount += in_count;
  431.         tot_outcount += out_count;
  432.         fprintf(stderr, "%ld chars in, %ld bytes out, ",
  433.             tot_incount, tot_outcount);
  434.         if (tot_outcount > 0) {
  435.             divout("compression ratio: ",
  436.             (long) tot_incount, (long) tot_outcount, "");
  437.             divout(" (",
  438.             ((long) tot_incount - (long) tot_outcount) * 100,
  439.             (long) tot_incount, "%)\n");
  440.         }
  441.         fprintf(stderr,
  442.             "%ld.%02ld seconds (process time) for compression.\n",
  443.             start_time / 1000L, (start_time % 1000L) / 10L);
  444.         if (start_time > 0) {
  445.             divout("  ", (long) tot_incount * 10L,
  446.             (start_time + 50L) / 100L,
  447.             " input bytes per second.\n");
  448.         }
  449.         }
  450.         exit(IO_SUCCESS);
  451.     }
  452.     else {
  453.         fprintf(stderr, "Error when compressing \"%s\" to \"%s\"\n",
  454.         (infilename  == NULL) ? 
  455.             "<input file unknown>" : infilename,
  456.         (outfilename == NULL) ?
  457.             "<output file unknown>" : outfilename);
  458.         if (errno != 0)
  459.         perror("lzcomp fatal error");
  460.         exit(IO_ERROR);
  461.     }
  462. }
  463.  
  464. divout(leader, numer, denom, trailer)
  465. char        *leader;
  466. long        numer;
  467. long        denom;
  468. char        *trailer;
  469. /*
  470.  * Print numer/denom without floating point on small machines.
  471.  */
  472. {
  473.     fprintf(stderr, "%s%ld.%02ld%s",
  474.         leader, numer / denom, ((numer % denom) * 100L) / denom, trailer);
  475. }
  476.  
  477. static
  478. initialize()
  479. /*
  480.  * Mung some global values.
  481.  */
  482. {
  483.     if (maxbits < INIT_BITS)    /* maxbits is set by the -M     */
  484.         maxbits = INIT_BITS;    /* option.  Make sure it's    */
  485.     if (maxbits > BITS)        /* within a reasonable range    */
  486.         maxbits = BITS;
  487.     maxmaxcode = 1 << maxbits;    /* Truly biggest code        */
  488.     if (export == 0)
  489.         firstcode = LZ_FIRST;    /* VMS private            */
  490.     else if (block_compress)
  491.         firstcode = LZ_CLEAR + 1;    /* Default            */
  492.     else
  493.         firstcode = 256;        /* Backwards compatible        */
  494. }
  495.  
  496. put_magic_header()
  497. /*
  498.  * Write the magic header bits.
  499.  */
  500. {
  501. #ifndef COMPATIBLE
  502.     if (export && !noheader) {
  503.         PUT(HEAD1_MAGIC, &outstream);
  504.         PUT(HEAD2_MAGIC, &outstream);
  505.         PUT(maxbits | ((block_compress) ? BLOCK_MASK : 0),
  506.         &outstream);
  507.     }
  508. #if VMS_V4
  509.     else if (export == 0) {
  510.         char        text[256];
  511.         /*
  512.          * VMS private mode (with attribute block)
  513.          */
  514.         PUT(HEAD1_MAGIC, &outstream);
  515.         PUT(VMS_HEAD2_MAGIC, &outstream);
  516.         PUT((char) (maxbits | BLOCK_MASK), &outstream);
  517.         PUT(firstcode - 0x100, &outstream);
  518.         init_compress();
  519.         outputcode(LZ_SOH);
  520. #if DEBUG
  521.         if (strlen(ATT_NAME) != ATT_SIZE) {
  522.         fprintf("\"%s\", expected %d, got %d\n",
  523.             ATT_NAME, ATT_SIZE, strlen(ATT_NAME));
  524.         }
  525. #endif
  526.         sprintf(text, "%s%d;", ATT_NAME, fdl_descriptor.dsc$w_length);
  527.         mem_compress(text, strlen(text));
  528.         outputcode(LZ_EOR);
  529.         mem_compress(fdl_descriptor.dsc$a_pointer,
  530.              fdl_descriptor.dsc$w_length);
  531.         fdl_free(&fdl_descriptor);
  532.         outputcode(LZ_ETX);
  533.         outputcode(LZ_STX);
  534.     }
  535. #endif
  536. #endif
  537. }
  538.  
  539. mem_compress(datum, length)
  540. char_type    *datum;
  541. int        length;
  542. /*
  543.  * Compress from memory
  544.  */
  545. {
  546.     mem_stream.bp = mem_stream.bstart = datum;
  547.     mem_stream.bsize = length;
  548.     mem_stream.bend = datum + length;
  549.     mem_stream.func = lz_eof;
  550.     compress(&mem_stream);
  551. }
  552.  
  553. /*
  554.  * This routine is used to tune the hash table size according to
  555.  * the file size.  If the filesize is unknown, fsize should be
  556.  * set to zero.
  557.  */
  558.  
  559. typedef struct TUNETAB {
  560.     long    fsize;
  561.     code_int    hsize;
  562. } TUNETAB;
  563.  
  564. static readonly TUNETAB tunetab[] = {
  565. #if HSIZE > 5003
  566.     {    1 << 12,     5003    },
  567. #endif
  568. #if HSIZE > 9001
  569.     {    1 << 13,     9001    },
  570. #endif
  571. #if HSIZE > 18013
  572.     {    1 << 14,    18013    },
  573. #endif
  574. #if HSIZE > 35023
  575.     {    1 << 15,    35023    },
  576.     {      47000,    50021    },
  577. #endif
  578.     {          0,        0    },
  579. };
  580.  
  581. static
  582. gethashsize()
  583. /*
  584.  * Tune the hash table parameters for small files.
  585.  * We don't have a good way to find the file size on vms V3.
  586.  * fsize is set to zero if we can't find it.
  587.  */
  588. {
  589.     register TUNETAB    *tunep;
  590.  
  591.     hsize = HSIZE;
  592.     if (fsize > 0) {
  593.         for (tunep = tunetab; tunep->fsize != 0; tunep++) {
  594.         if (fsize < tunep->fsize) {
  595.             hsize = tunep->hsize;
  596.             break;
  597.         }
  598.         }
  599.     }
  600. }
  601.  
  602. static
  603. getfilesize()
  604. /*
  605.  * Set fsize to the input filesize (in bytes) if possible.
  606.  * Magic for all operating systems.
  607.  */
  608. {
  609. #ifdef    rsx
  610.     extern char    f_efbk;    /* F.EFBK -- highest block in file    */
  611. #define    fdb(p,offset)    (stdin->io_fdb[((int) &p + offset)] & 0xFF)
  612. #define efbk(offset)    fdb(f_efbk, offset)
  613.     extern char    f_rtyp;    /* F.RTYP -- Record type        */
  614.     extern char    f_ratt;    /* F.RATT -- Record attributes        */
  615.     /*
  616.      * Note: Block number is stored high-order word first.
  617.      */
  618.     fsize = efbk(2)
  619.         + (efbk(3) << 8)
  620.         + (efbk(0) << 16)
  621.         + (efbk(1) << 24);
  622.     fsize *= 512;
  623. #endif
  624. #ifdef    rt11
  625.     fsize = stdin->io_size;        /* Set by Decus C        */
  626.     fsize *= 512;
  627. #endif
  628. #ifdef    vms
  629. #if VMS_V4
  630.     struct stat    statbuf;
  631.  
  632.     fsize = 0;
  633.     if (export != 0) {
  634.         if (fstat(fileno(stdin), &statbuf) == 0)
  635.         fsize = (long) statbuf.st_size;
  636.     }
  637.     else {
  638.         fsize = (long) fdl_fsize(fdl_input);
  639.     }
  640. #else
  641.     fsize = 0;                /* Can't find filesize    */
  642. #endif
  643. #endif
  644. #ifdef    unix
  645.     struct stat    statbuf;
  646.  
  647.     fsize = 0;
  648.     if (fstat(fileno(stdin), &statbuf) == 0)
  649.         fsize = (long) statbuf.st_size;
  650. #endif
  651. }
  652.  
  653. static readonly char *helptext[] = {
  654.     "The following options are valid:",
  655.     "-B\tBinary file (important on VMS/RSX, ignored on Unix)",
  656.     "-M val\tExplicitly set the maximum number of code bits",
  657.     "-V val\tPrint status information (or debugging) to stderr",
  658.     "-X val\tSet export (compatiblity) mode:",
  659. #if VMS_V4
  660.     "  -X 0\tExplicitly choose VMS Private mode",
  661. #endif
  662.     "  -X 1\t(default if -X specified, output format is compatible",
  663.           "\twith Unix compress V3.0",
  664.     "  -X 2\tCompatible with Unix compress 3.0, block compression",
  665.           "\tsupressed.",
  666. #ifdef COMPATIBLE
  667.     "  -X 3No header (file is readable by old compress)",
  668. #endif
  669.     NULL,
  670. };
  671.  
  672. static
  673. setup(argc, argv)
  674. int        argc;
  675. char        *argv[];
  676. /*
  677.  * Get parameters and open files.  Exit fatally on errors.
  678.  */
  679. {
  680.     register char    *ap;
  681.     register int    c;
  682.     char        **hp;
  683.     auto int    i;
  684.     int        j;
  685.  
  686. #ifdef    vms
  687.     argc = getredirection(argc, argv);
  688. #endif
  689.     for (i = j = 1; i < argc; i++) {
  690.         ap = argv[i];
  691.         if (*ap++ != '-' || *ap == EOS)    /* Filename?        */
  692.         argv[j++] = argv[i];        /* Just copy it        */
  693.         else {
  694.         while ((c = *ap++) != EOS) {
  695.             if (islower(c))
  696.             c = toupper(c);
  697.             switch (c) {
  698.             case 'B':
  699.             binary = TRUE;
  700.             break;
  701.  
  702.             case 'M':
  703.             maxbits = getvalue(ap, &i, argv);
  704.             if (maxbits < MIN_BITS) {
  705.                 fprintf(stderr, "Illegal -M value\n");
  706.                 goto usage;
  707.             }
  708.             break;
  709.  
  710.             case 'V':
  711.             verbose = getvalue(ap, &i, argv);
  712.             break;
  713.  
  714.             case 'X':
  715.             export = getvalue(ap, &i, argv);
  716.             if (export < 0 || export > 3) {
  717.                 fprintf(stderr, "Illegal -X value: %d\n", export);
  718.                 goto usage;
  719.             }
  720.             block_compress = "\1\1\0\0"[export];
  721.             noheader       = "\0\0\0\1"[export];
  722.             export         = "\0\1\1\1"[export];
  723.             break;
  724.  
  725.             default:
  726.             fprintf(stderr, "Unknown option '%c' in \"%s\"\n",
  727.                 *ap, argv[i]);
  728. usage:            for (hp = helptext; *hp != NULL; hp++)
  729.                 fprintf(stderr, "%s\n", *hp);
  730.             FAIL("usage");
  731.             }                /* Switch on options    */
  732.         }                /* Everything for -xxx    */
  733.         }                    /* If -option        */
  734.     }                    /* For all argc's    */
  735.     /*  infilename = NULL; */        /* Set "stdin"  signal    */
  736.     /* outfilename = NULL; */        /* Set "stdout" signal    */
  737.     switch (j) {                /* Any file arguments?    */
  738.     case 3:                    /* both files given    */
  739.         if (!streq(argv[2], "-"))        /* But - means stdout    */
  740.         outfilename = argv[2];
  741.     case 2:                    /* Input file given    */
  742.         if (!streq(argv[1], "-")) {
  743.         infilename = argv[1];
  744.         }
  745.         break;
  746.  
  747.     case 0:                    /* None!        */
  748.     case 1:                    /* No file arguments    */
  749.         break;
  750.  
  751.     default:
  752.         fprintf(stderr, "Too many file arguments\n");
  753.         FAIL("too many files");
  754.     }
  755. }
  756.  
  757. static int
  758. getvalue(ap, ip, argv)
  759. register char        *ap;
  760. int            *ip;
  761. char            *argv[];
  762. /*
  763.  * Compile a "value".  We are currently scanning *ap, part of argv[*ip].
  764.  * The following are possible:
  765.  *    -x123        return (123) and set *ap to EOS so the caller
  766.  *    ap^        cycles to the next argument.
  767.  *
  768.  *    -x 123        *ap == EOS and argv[*ip + 1][0] is a digit.
  769.  *            return (123) and increment *i to skip over the
  770.  *            next argument.
  771.  *
  772.  *    -xy or -x y    return(1), don't touch *ap or *ip.
  773.  *
  774.  * Note that the default for "flag option without value" is 1.  This
  775.  * can only cause a problem for the -M option where the value is
  776.  * mandatory.  However, the result of 1 is illegal as it is less
  777.  * than INIT_BITS.
  778.  */
  779. {
  780.     register int    result;
  781.     register int    i;
  782.  
  783.     i = *ip + 1;
  784.     if (isdigit(*ap)) {
  785.         result = atoi(ap);
  786.         *ap = EOS;
  787.     }
  788.     else if (*ap == EOS
  789.           && argv[i] != NULL
  790.           && isdigit(argv[i][0])) {
  791.         result = atoi(argv[i]);
  792.         *ip = i;
  793.     }
  794.     else {
  795.         result = 1;
  796.     }
  797.     return (result);
  798. }
  799.  
  800. openinput()
  801. {
  802. #ifdef decus
  803.     if (infilename == NULL) {
  804.         infilename = malloc(256 + 1);
  805.         fgetname(stdin, infilename);
  806.         infilename = realloc(infilename, strlen(infilename) + 1);
  807.     }
  808.     else {
  809.         if (freopen(infilename, (binary) ? "rn" : "r", stdin) == NULL) {
  810.         perror(infilename);
  811.         FAIL("can't reopen input");
  812.         }
  813.     }
  814. #else
  815. #ifdef vms
  816. #if VMS_V4
  817.     if (export == 0) {
  818.         char        *fname;
  819.         char        filename[256];
  820.  
  821.         if ((fname = infilename) == NULL) {
  822.         fgetname(stdin, filename);
  823.         fname = filename;
  824.         }
  825.         if ((fdl_input = fdl_open(fname, &fdl_descriptor)) == NULL) {
  826.         if ((fdl_status & 01) == 0) {
  827.             fdl_message(NULL, fname);
  828.             FAIL("can't fdl_open");
  829.         }
  830.         fprintf(stderr,
  831.             "Cannot open \"%s\" in vms private format,", fname);
  832.         fprintf(stderr, " trying export format.\n");
  833.         export = TRUE;
  834.         goto try_export;
  835.         }
  836.         fclose(stdin);
  837.         stdin = NULL;
  838.         infilename = malloc(256 + 1);
  839.         infilename = realloc(fname, strlen(fname) + 1);
  840.         if (verbose > 1) {
  841.         fprintf(stderr, "FDL information for \"%s\"\n", filename);
  842.         fdl_dump(&fdl_descriptor, stderr);
  843.         }
  844.         goto opened;
  845.     }
  846. try_export:
  847. #endif
  848.     if (infilename == NULL) {
  849.         infilename = malloc(256 + 1);
  850.         fgetname(stdin, infilename);
  851.         infilename = realloc(infilename, strlen(infilename) + 1);
  852.     }
  853.     else {
  854. #if VMS_V4
  855.         if ((stdin = freopen(infilename, "r", stdin)) == NULL) {
  856. #else
  857.         if (freopen(infilename, "r", stdin) == NULL) {
  858. #endif
  859.         perror(infilename);
  860.         exit(IO_ERROR);
  861.         }
  862.     }
  863. #else
  864.     if (infilename == NULL)
  865.         infilename = "stdin";
  866.     else {
  867.         if (freopen(infilename, "r", stdin) == NULL) {
  868.         perror(infilename);
  869.         exit(IO_ERROR);
  870.         }            
  871.     }
  872. #endif
  873. #endif
  874. opened:    instream.bp = instream.bend = NULL;
  875.     instream.bstart = inbuffer;
  876.     instream.bsize = sizeof inbuffer;
  877.     instream.func = lz_fill;
  878. }
  879.  
  880. openoutput()
  881. /*
  882.  * Open the output file (after the input file has been opened).
  883.  * if outfilename == NULL, it's already open on stdout.
  884.  */
  885. {
  886.     if (outfilename == NULL) {
  887. #if VMS_V4
  888. #if 0                    /* The following doesn't work    */
  889.         outfilename = malloc(256 + 1);
  890.         fgetname(stdout, outfilename);
  891.         outfilename = realloc(outfilename, strlen(outfilename) + 1);
  892.         if (export == 0) {
  893.         fclose(stdout);
  894.         stdout = NULL;        /* Can't do terminal test below    */
  895.         if ((fdl_output = fdl_create(NULL, outfilename)) == NULL) {
  896.             if ((fdl_status & 01) == 0)
  897.             fdl_message(NULL, outfilename);
  898.             fprintf(stderr, "Can't create \"%s\"\n", outfilename);
  899.             FAIL("can't fdl_create");
  900.         }
  901.         }
  902. #else
  903.         fprintf(stderr,
  904.         "Restriction: The output file must be specified.\n");
  905.         FAIL("can't redirect on VMS V4");
  906. #endif
  907. #else
  908. #ifdef    vms
  909.         outfilename = malloc(256 + 1);
  910.         fgetname(stdout, outfilename);
  911.         outfilename = realloc(outfilename, strlen(outfilename) + 1);
  912. #else
  913. #ifdef decus
  914.         outfilename = malloc(256 + 1);
  915.         fgetname(stdout, outfilename);
  916.         outfilename = realloc(outfilename, strlen(outfilename) + 1);
  917. #else
  918.         outfilename = "<stdout>";
  919. #endif
  920. #endif
  921. #endif
  922.     }
  923.     else {
  924. #if VMS_V4
  925.         if (export == 0) {
  926.         fclose(stdout);
  927.         stdout = NULL;        /* Can't do terminal test below    */
  928.         if ((fdl_output = fdl_create(NULL, outfilename)) == NULL) {
  929.             if ((fdl_status & 01) == 0)
  930.             fdl_message(NULL, outfilename);
  931.             fprintf(stderr,
  932.             "Can't create \"%s\" (VMS private)\n", outfilename);
  933.             FAIL("can't fdl_create");
  934.         }
  935.         }
  936.         else {
  937.         if (freopen(outfilename, "w", stdout) == NULL) {
  938.             perror(outfilename);
  939.             FAIL("can't create");
  940.         }
  941.         }
  942. #else
  943. #ifdef decus
  944.         if (freopen(outfilename, "wn", stdout) == NULL) {
  945.         perror(outfilename);
  946.         FAIL("can't create");
  947.         }
  948. #else
  949.         if (freopen(outfilename, "w", stdout) == NULL) {
  950.         perror(outfilename);
  951.         FAIL("can't create");
  952.         }
  953. #endif
  954. #endif
  955.     }
  956.     if (stdout != NULL && isatty(fileno(stdout))) {
  957.         fprintf(stderr, "%s: is a terminal.  We object.\n",
  958.         outfilename);
  959.         FAIL("can't create");
  960.     }
  961.     outstream.bp = outstream.bstart = outbuffer;
  962.     outstream.bend = outbuffer + sizeof outbuffer;
  963.     outstream.bsize = sizeof outbuffer;
  964.     outstream.func = lz_flush;
  965. }
  966.  
  967. -h- lzcmp2.c    Wed Jul 24 11:49:28 1985    USER$A:[MINOW.LZ]LZCMP2.C;8
  968. /*
  969.  *        l z c m p 2 . c
  970.  *
  971.  * Actually do compression.  Terminology (and algorithm):
  972.  *
  973.  * Assume the input string is "abcd", we have just processed "ab" and
  974.  * read 'c'.  At this point, a "prefix code" will be assigned to "ab".
  975.  * Search in the prefix:character memory (either the "fast memory" or
  976.  * the hash-code table) for the code followed by this character.  If
  977.  * found, assign the code found to the "prefix code" and read the
  978.  * next character.  If not found, output the current prefix code,
  979.  * generate a new prefix code and store "old_prefix:char" in the
  980.  * table with "new_prefix" as its definition.
  981.  *
  982.  * Naming conventions:
  983.  *   code    a variable containing a prefix code
  984.  *   c or char    a variable containing a character
  985.  *
  986.  * There are three tables that are searched (dependent on compile-time
  987.  * and execution time considerations):
  988.  *   fast    Direct table-lookup -- requires a huge amount of physical
  989.  *        (non-paged) memory, but is very fast.
  990.  *   hash    Hash-coded table-lookup.
  991.  *   cache    A "look-ahead" cache for the hash table that optimizes
  992.  *        searching for the most frequent character.  This considerably
  993.  *        speeds up processing for raster-images (for example) at
  994.  *        a modest amount of memory.
  995.  * Structures are used to hold the actual tables to simplify organization
  996.  * of the program.
  997.  *
  998.  * Subroutines:
  999.  *    compress()    performs data compression on an input datastream.
  1000.  *    init_compress()    called by the output routine to clear tables.
  1001.  */
  1002.  
  1003. #include    "lz.h"
  1004.  
  1005. /*
  1006.  * General variables
  1007.  * Cleared by init_compress on a "hard initialization"
  1008.  * outputcode() in lzcmp3.c refers to next_code.
  1009.  */
  1010.  
  1011. long int    in_count;        /* Length of input        */
  1012. long int    out_count;        /* Bytes written to output file    */
  1013. static flag    first_clear = TRUE;    /* Don't zero first time    */
  1014. code_int    next_code;        /* Next output code        */
  1015. static count_int checkpoint = CHECK_GAP; /* When to test ratio again    */
  1016. static long    ratio = 0;        /* Ratio for last segment    */
  1017.  
  1018. /*
  1019.  * These global parameters are set by mainline code.  Unchanged here.
  1020.  */
  1021. extern short    maxbits;        /* Settable max # bits/code    */
  1022. extern short    block_compress;        /* For old-style compatibility    */
  1023. extern code_int    maxmaxcode;        /* Actual maximum output code    */
  1024. extern long    tot_incount;        /* Total input count        */
  1025. extern long    tot_outcount;        /* Total output count        */
  1026. extern code_int    hsize;            /* Actual hash table size    */
  1027.  
  1028. #ifdef XENIX_16
  1029. static count_int htab0[8192];
  1030. static count_int htab1[8192];
  1031. static count_int htab2[8192];
  1032. static count_int htab3[8192];
  1033. static count_int htab4[8192];
  1034. static count_int htab5[8192];
  1035. static count_int htab6[8192];
  1036. static count_int htab7[8192];
  1037. static count_int htab8[HSIZE - 65536];
  1038. static count_int *hashtab[9] = {
  1039.     htab0, htab1, htab2, htab3, htab4, htab5, htab6, htab7, htab8
  1040. };
  1041.  
  1042. static U_short code0[16384];
  1043. static U_short code1[16384];
  1044. static U_short code2[16384];
  1045. static U_short code3[16384];
  1046. static U_short code4[HSIZE - 65536];
  1047. static U_short *codetab[5] = {
  1048.     code0, code1, code3, code3, code4
  1049. }
  1050.  
  1051. #define HASH(i)        (hashtab[((unsigned) (i)) >> 13][(i) & 0x1FFF])
  1052. #define CODE(i)        (codetab[((unsigned) (i)) >> 14][(i) & 0x3FFF])
  1053.  
  1054. #else
  1055. count_int    hashtab[HSIZE];
  1056. U_short        codetab[HSIZE];
  1057.  
  1058. #define HASH(i)        hashtab[i]
  1059. #define CODE(i)        codetab[i]
  1060. #endif
  1061.  
  1062. /*
  1063.  * compress a datastream
  1064.  *
  1065.  * Algorithm:  on large machines, for maxbits <= FBITS, use fast direct table
  1066.  * lookup on the prefix code / next character combination.  For smaller code
  1067.  * size, use open addressing modular division double hashing (no chaining), ala
  1068.  * Knuth vol. 3, sec. 6.4 Algorithm D, along with G. Knott's relatively-prime
  1069.  * secondary probe.  Do block compression with an adaptive reset, whereby the
  1070.  * code table is cleared when the compression ratio decreases, but after the
  1071.  * table fills.  The variable-length output codes are re-sized at this point,
  1072.  * and a special LZ_CLEAR code is generated for the decompressor.  For the
  1073.  * megamemory version, the sparse array is cleared indirectly through a
  1074.  * "shadow" output code history.  Late additions: for the hashing code,
  1075.  * construct the table according to file size for noticeable speed improvement
  1076.  * on small files.  Also detect and cache codes associated with the most
  1077.  * common character to bypass hash calculation on these codes (a characteristic
  1078.  * of highly-compressable raster images).  Please direct questions about this
  1079.  * implementation to ames!jaw.
  1080.  */
  1081.  
  1082. compress(in)
  1083. STREAM        *in;        /* Input stream structure        */
  1084. /*
  1085.  * Compress driver.  Global fsize is the size of the entire datastream
  1086.  * (from LZ_STX or LZ_SOH to the terminating LZ_ETX).  You must
  1087.  * force a reinitialization -- by calling outputcode() with a new header --
  1088.  * if size is changed.  If the "newer" output format is chosen (with
  1089.  * data streams delimited by LZ_SOH/LZ_STX, init_compress will be
  1090.  * called automatically.  Otherwise, you must call init_compress(TRUE)
  1091.  * before calling compress() for the first time.
  1092.  */
  1093. {
  1094.     register long        hash_code;    /* What we look for    */
  1095.     register code_int    i;        /* Index into vectors    */
  1096.     register int        c;        /* Current input char    */
  1097.     register code_int    code;        /* Substring code    */
  1098.     register int        displacement;    /* For secondary hash    */
  1099.     register code_int    hsize_reg;    /* Size of hash table    */
  1100.     register int        hshift;        /* For xor hasher    */
  1101.  
  1102.     if ((code = GET(in)) == EOF)
  1103.         return;
  1104.     in_count++;
  1105.     hsize_reg = hsize;
  1106.     /*
  1107.      * Set hash code range bound
  1108.      */
  1109.     hshift = 0;
  1110.     for (hash_code = (long) hsize; hash_code < 65536L; hash_code <<= 1)
  1111.         hshift++;
  1112.     hshift = 8 - hshift;
  1113.     while ((c = GET(in)) != (unsigned) EOF) {
  1114.         in_count++;
  1115.         hash_code = (long) (((long) c << maxbits) + code);
  1116.         i = (c << hshift) ^ code;        /* XOR hashing        */
  1117.         if (HASH(i) == hash_code) {        /* Found at first slot?    */
  1118.         code = CODE(i);
  1119.         continue;
  1120.         }
  1121.         else if ((long) HASH(i) < 0)    /* empty slot        */
  1122.         goto nomatch;
  1123.         displacement = hsize_reg - i;    /* secondary hash    */
  1124.         if (i == 0)
  1125.         displacement = 1;
  1126. probe:
  1127.         if ((i -= displacement) < 0)    /* Wrap around?        */
  1128.         i += hsize_reg;
  1129.         if (HASH(i) == hash_code) {        /* Found in hash table?    */
  1130.         code = CODE(i);            /* Set new prefix code    */
  1131.         continue;            /* Read next input char    */
  1132.         }
  1133.         else if ((long) HASH(i) > 0)    /* If slot is occupied    */
  1134.         goto probe;            /* Look somewhere else    */
  1135. nomatch:
  1136.         /*
  1137.          * Output the current prefix and designate a new prefix.
  1138.          * If the input character was the "hog", save it in the
  1139.          * look-ahead cache table.  Then, save in the hash table.
  1140.          */
  1141.         outputcode((code_int) code);    /* No match, put prefix    */
  1142. #if SIGNED_COMPARE_SLOW
  1143.         if ((unsigned) next_code < (unsigned) maxmaxcode) {
  1144. #else
  1145.         if (next_code < maxmaxcode) {
  1146. #endif
  1147.         CODE(i) = next_code++;        /* code -> hashtable    */
  1148.         HASH(i) = hash_code;
  1149.         }
  1150.         else if (block_compress
  1151.           && (count_int) in_count >= checkpoint) {
  1152.         clear();
  1153.         }
  1154.         code = c;                /* Start new substring    */
  1155.     }
  1156.     /*
  1157.      * At EOF, put out the final code.
  1158.      */
  1159.     outputcode((code_int) code);
  1160. }
  1161.  
  1162. clear()
  1163. /*
  1164.  * Check the compression ratio to see whether it is going up
  1165.  * or staying the same.  If it is going down, the internal
  1166.  * statistics of the file have changed, so clear out our
  1167.  * tables and start over.  Inform the decompressor of the
  1168.  * change by sending out a LZ_CLEAR code.
  1169.  */
  1170. {
  1171.     register long int    rat;
  1172.  
  1173.     checkpoint = in_count + CHECK_GAP;
  1174. #if DEBUG
  1175.     if (verbose > 2) {
  1176.         divout("at clear() test",  in_count, out_count, "");
  1177.         fprintf(stderr, ", ratio at entry: %ld.%02ld, gap %d\n",
  1178.         rat / 256L, ((rat & 255L) * 100L) / 256L, CHECK_GAP);
  1179.     }
  1180. #endif
  1181.     if (in_count > 0x007FFFFL) {        /* Shift will overflow    */
  1182.         rat = out_count >> 8;
  1183.         if (rat == 0)
  1184.         rat = 0x7FFFFFFFL;
  1185.         else {
  1186.         rat = in_count / rat;
  1187.         }
  1188.     }
  1189.     else {
  1190.         rat = (in_count << 8) / out_count;
  1191.     }
  1192.     if (rat > ratio)
  1193.         ratio = rat;
  1194.     else {
  1195. #if DEBUG
  1196.         if (verbose > 0) {
  1197.         fprintf(stderr, "Resetting compression, in %ld, out %ld\n",
  1198.             in_count, out_count);
  1199.         fprintf(stderr, "Old ratio: %ld == (%ld.%02ld)",
  1200.             ratio, ratio / 256L, ((ratio & 255L) * 100L) / 256L);
  1201.         fprintf(stderr, ", test ratio: %ld = (%ld.%02ld), gap %d\n",
  1202.             rat, rat / 256L, ((rat & 255L) * 100L) / 256L, CHECK_GAP);
  1203.         }
  1204. #endif
  1205.         outputcode((code_int) LZ_CLEAR);    /* Calls init_compress    */
  1206.     }
  1207. }
  1208.  
  1209. init_compress(full_init)
  1210. flag        full_init;    /* TRUE for full initialization        */
  1211. /*
  1212.  * Clear the tables.  Called by outputcode() on LZ_SOH, LZ_STX
  1213.  * (full_init TRUE) or on LZ_CLEAR (full_init FALSE).
  1214.  * init_compress() is not called on LZ_EOR.
  1215.  */
  1216. {
  1217. #ifdef XENIX_16
  1218.     register count_int    *hp;
  1219.     register int        n;
  1220.     register int        j;
  1221.     register code_int    k;
  1222.  
  1223.     k = hsize;
  1224.     for (j = 0; k > 0; k -= 8192) {
  1225.         i = (k < 8192) ? k : 8192;
  1226.         hp = hashtab[j++];
  1227.         n = i >> 4;
  1228.         switch (i & 15) {
  1229.         case 15:    *hp++ = -1;
  1230.         case 14:    *hp++ = -1;
  1231.         case 13:    *hp++ = -1;
  1232.         case 12:    *hp++ = -1;
  1233.         case 11:    *hp++ = -1;
  1234.         case 10:    *hp++ = -1;
  1235.         case  9:    *hp++ = -1;
  1236.         case  8:    *hp++ = -1;
  1237.         case  7:    *hp++ = -1;
  1238.         case  6:    *hp++ = -1;
  1239.         case  5:    *hp++ = -1;
  1240.         case  4:    *hp++ = -1;
  1241.         case  3:    *hp++ = -1;
  1242.         case  2:    *hp++ = -1;
  1243.         case  1:    *hp++ = -1;
  1244.         }
  1245.         while (--n >= 0) {
  1246.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1247.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1248.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1249.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1250.        }
  1251.     }
  1252. #else
  1253.     register count_int    *hp;
  1254.     register code_int    n;
  1255.  
  1256.     hp = &hashtab[0];
  1257.     n = hsize >> 4;            /* divide by 16            */
  1258.     switch (hsize & 15) {
  1259.     case 15:    *hp++ = -1;
  1260.     case 14:    *hp++ = -1;
  1261.     case 13:    *hp++ = -1;
  1262.     case 12:    *hp++ = -1;
  1263.     case 11:    *hp++ = -1;
  1264.     case 10:    *hp++ = -1;
  1265.     case  9:    *hp++ = -1;
  1266.     case  8:    *hp++ = -1;
  1267.     case  7:    *hp++ = -1;
  1268.     case  6:    *hp++ = -1;
  1269.     case  5:    *hp++ = -1;
  1270.     case  4:    *hp++ = -1;
  1271.     case  3:    *hp++ = -1;
  1272.     case  2:    *hp++ = -1;
  1273.     case  1:    *hp++ = -1;
  1274.     }
  1275.     while (--n >= 0) {
  1276.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1277.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1278.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1279.         *hp++ = -1; *hp++ = -1; *hp++ = -1; *hp++ = -1;
  1280.     }
  1281. #endif
  1282.     if (full_init) {
  1283.         tot_incount += in_count;
  1284.         tot_outcount += out_count;
  1285.         in_count = 0;
  1286.         out_count = 0;
  1287.         ratio = 0;
  1288.     }
  1289.     first_clear = FALSE;
  1290.     next_code = firstcode;
  1291. }
  1292. -h- lzcmp3.c    Wed Jul 24 11:49:28 1985    USER$A:[MINOW.LZ]LZCMP3.C;10
  1293. /*
  1294.  *             l z c m p 3 . c
  1295.  * Output a given code.
  1296.  */
  1297. #include "lz.h"
  1298.  
  1299. extern STREAM    outstream;
  1300. extern code_int    next_code;
  1301. extern code_int    maxmaxcode;        /* Actual maximum output code    */
  1302. extern short    maxbits;
  1303. extern count_int out_count;
  1304.  
  1305. static char_type buf[BITS];
  1306. static int    offset;
  1307. static short    n_bits = INIT_BITS;    /* # of bits in compressed file    */
  1308. static short    n_bits8 = INIT_BITS << 3;
  1309. static code_int    maxcode = MAXCODE(INIT_BITS);
  1310.  
  1311. #if !vax_asm
  1312. static readonly char_type lmask[9] = {
  1313.     0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80, 0x00
  1314. };
  1315. static readonly char_type rmask[9] = {
  1316.     0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF
  1317. };
  1318. #endif
  1319.  
  1320. #if DEBUG
  1321. extern int    col;
  1322. static int    todump;
  1323. #endif
  1324.  
  1325. outputcode(code)
  1326. code_int  code;
  1327. /*
  1328.  * Output the given code.
  1329.  * Inputs:
  1330.  *     code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  1331.  *        that n_bits <= (long)wordsize - 1.
  1332.  * Note: if not in "export" mode, the following values are special:
  1333.  *    LZ_CLEAR    (also in export mode if block_compress TRUE)
  1334.  *            (soft) clear out compress tables and reset the
  1335.  *            number of bits per code to the minimum.
  1336.  *    LZ_SOH, LZ_STX    (hard) clear out compress tables and reset as above.
  1337.  *    LZ_ETX, LZ_EOR    force out the current output segment, analogous
  1338.  *            to fflush.
  1339.  *            
  1340.  * Outputs:
  1341.  *     Outputs code to the file.  If the codespace has filled
  1342.  *    (next_code >= (1 << n_bits), increase n_bits.
  1343.  *    If LZ_CLEAR, LZ_SOH, or LZ_STX is seen, reset n_bits
  1344.  *    to the initial value and call init_compress to reset
  1345.  *    the lookup and cache tables.
  1346.  *
  1347.  * Assumptions:
  1348.  *    Output chars are 8 bits long.  This is deeply hardwired
  1349.  *    into the algorithm.  It is independent, however, of the
  1350.  *    size of the input data.
  1351.  *
  1352.  * Algorithm:
  1353.  *     Maintain a BITS character long buffer (so that 8 codes will
  1354.  *    fit in it exactly).  Use the VAX insv instruction to insert each
  1355.  *    code in turn.  When the buffer fills up empty it and start over.
  1356.  */
  1357. {
  1358.     /*
  1359.      * On the VAX (Unix), it is important to have the register declarations
  1360.      * in exactly the order given, or the asm will break.
  1361.      */
  1362.     register int    r_off, bits;
  1363.     register char_type    *bp;
  1364. #if !vax_asm
  1365.     register code_int    r_code;
  1366. #endif
  1367.  
  1368.     r_off = offset;
  1369.     bits = n_bits;
  1370.     bp = buf;
  1371.     if (code >= 0) {
  1372.         /*
  1373.          * Not at EOF, add the code
  1374.          */
  1375. #if DEBUG
  1376.         if (verbose > 3) {
  1377.         fprintf(stderr, "%c%5d %5d",
  1378.             ((col += 12) >= 72) ? (col = 0, '\n') : ' ',
  1379.             code, next_code);
  1380.         if (code >= LZ_CLEAR && code < firstcode) {
  1381.             fprintf(stderr, " = %s", lz_names[code - LZ_CLEAR]);
  1382.             col = 74;
  1383.         }
  1384.         }
  1385. #endif
  1386. #if vax_asm
  1387.         /*
  1388.          * VAX DEPENDENT!! Implementation on other machines may be
  1389.          * difficult.
  1390.          *
  1391.          * Translation: Insert BITS bits from the argument starting at
  1392.          * offset bits from the beginning of buf.
  1393.          */
  1394.         0;                    /* C compiler bug ??    */
  1395.         asm("insv    4(ap),r11,r10,(r9)");
  1396. #else
  1397.         /*
  1398.          * WARNING: byte/bit numbering on the vax is simulated
  1399.          * by the following code
  1400.          */
  1401.         bp += (r_off >> 3);            /* -> first output slot    */
  1402.         r_off &= 7;
  1403.         /*
  1404.          * Since code is always >= 8 bits, only need to mask the first
  1405.          * hunk on the left.
  1406.          */
  1407.         r_code = code;
  1408.         *bp = (*bp & rmask[r_off]) | (r_code << r_off) & lmask[r_off];
  1409.         bp++;
  1410.         bits -= (8 - r_off);
  1411.         r_code >>= 8 - r_off;
  1412.         /*
  1413.          * Get any 8 bit parts in the middle ( <= 1 for up to 16 bits).
  1414.          */
  1415.         if (bits >= 8) {
  1416.         *bp++ = r_code;
  1417.         r_code >>= 8;
  1418.         bits -= 8;
  1419.         }
  1420.         if (bits != 0)                /* Last bits. */
  1421.         *bp = r_code;
  1422. #endif
  1423.         offset += n_bits;
  1424.         if (offset == n_bits8) {
  1425.         out_count += n_bits;
  1426.         lz_putbuf(buf, n_bits, &outstream);
  1427. #if DEBUG
  1428.         if (todump > 0) {
  1429.             dumphex(buf, n_bits, stderr);
  1430.             todump -= n_bits;
  1431.         }
  1432. #endif
  1433.         offset = 0;
  1434.         }
  1435.         /*
  1436.          * If the next entry is going to be too big for the code size,
  1437.          * then increase it, if possible.  Note:
  1438.          *     !export            firstcode == LZ_FIRST
  1439.          *       export && block_compress    firstcode == LZ_CLEAR + 1
  1440.          *       export && !block_compress    firstcode == LZ_CLEAR
  1441.          */
  1442.         if (next_code > maxcode) {
  1443.         if (offset > 0) {
  1444.             lz_putbuf(buf, n_bits, &outstream);
  1445.             out_count += n_bits;
  1446.             offset = 0;
  1447. #if DEBUG
  1448.             if (todump > 0) {
  1449.             dumphex(buf, n_bits, stderr);
  1450.             todump -= n_bits;
  1451.             }
  1452. #endif
  1453.         }
  1454.         n_bits++;            /* Need more bits    */
  1455.         n_bits8 += (1 << 3);
  1456.         if (n_bits == maxbits)
  1457.             maxcode = maxmaxcode;
  1458.         else
  1459.             maxcode = MAXCODE(n_bits);
  1460. #if DEBUG
  1461.         if (verbose > 2) {
  1462.             fprintf(stderr,
  1463.             "%snext_code %d, change to %d bits max %d",
  1464.             (col > 0) ? "\n" : "", next_code,
  1465.             n_bits, maxcode);
  1466.             col = 74;
  1467.         }
  1468. #endif
  1469.         }
  1470.         if (code >= LZ_CLEAR && code < firstcode) {
  1471.         switch (code) {
  1472.         case LZ_SOH:
  1473.         case LZ_STX:
  1474.         case LZ_CLEAR:
  1475.             if (offset > 0) {
  1476.             lz_putbuf(buf, n_bits, &outstream);
  1477.             out_count += n_bits;
  1478.             offset = 0;
  1479. #if DEBUG
  1480.             if (todump > 0) {
  1481.                 dumphex(buf, n_bits, stderr);
  1482.                 todump -= n_bits;
  1483.             }
  1484. #endif
  1485.             }
  1486.             n_bits = INIT_BITS;        /* Reset codes        */
  1487.             n_bits8 = INIT_BITS << 3;
  1488.             maxcode = MAXCODE(INIT_BITS);
  1489.             init_compress(code != LZ_CLEAR);
  1490. #if DEBUG
  1491.             if (verbose > 2) {
  1492.             fprintf(stderr,
  1493.             "\n(%s) Change to %d bits, maxcode %d, next_code = %d",
  1494.                 lz_names[code - LZ_CLEAR],
  1495.                 n_bits, maxcode, next_code);
  1496.             col = 74;
  1497.             todump = 32;
  1498.             }
  1499. #endif
  1500.             break;
  1501.  
  1502.         case LZ_EOR:
  1503.         case LZ_ETX:            /* Just written out    */
  1504.             break;
  1505.  
  1506.         default:
  1507.             abort();            /* Can't happen        */
  1508.         }
  1509.         }
  1510.     }
  1511.     else {
  1512.         /*
  1513.          * At EOF, write the rest of the buffer.
  1514.          */
  1515.         if ((r_off = offset) > 0) {
  1516.         r_off += 7;
  1517.         r_off >>= 3;
  1518.         lz_putbuf(buf, r_off, &outstream);
  1519.         out_count += r_off;
  1520. #if DEBUG
  1521.         if (todump > 0) {
  1522.             dumphex(buf, r_off, stderr);
  1523.             todump -= r_off;
  1524.         }
  1525. #endif
  1526.         }
  1527.         offset = 0;
  1528.         lz_flush(&outstream);        /* Flush output buffer    */
  1529. #if DEBUG
  1530.         if (verbose > 3 || todump > 0) {
  1531.         fprintf(stderr, "\n*EOF*\n");
  1532.         col = 0;
  1533.         }
  1534. #endif
  1535.     }
  1536. }
  1537.