Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume23/zip/part01

Text File | 1991-10-21 | 55KB | 1,599 lines

Newsgroups: comp.sources.misc
From: [e-mail] (David Kirschbaum)
Subject:  v23i088:  zip - Portable zip v1.0, Part01/09
Message-ID: <csm-v23i088=[e-mail]>
X-Md4-Signature: 61134dcb2a8c2cb49e9e129416f582d3
Date: Mon, 21 Oct 1991 04:20:22 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (David Kirschbaum)
Posting-number: Volume 23, Issue 88
Archive-name: zip/part01
Environment: UNIX, Minix, MSDOS, OS/2, VMS

Here's the product of the Info-ZIP Workgroup:  a portable, generic
compatible zip file compressor.  This is a companion to the unzip utility
also distributed by this group.

I extracted the original zip10ex.zip distribution files, changed them all
to Unix end_of_line, lower-cased a bunch of the file names (just to give
the Unix systems something familiar), and used cshar (comp.sources.unix
volume15) to create the Partnn shar files.  Other than those minor changes
(for transmission only), all honor and glory to the original authors.
(Be sure to contact *them* (or [e-mail]) if there
are any bugs or problems.)

Oh, yes, this is the *export* version (no encryption).  The domestic
version (with encryption) is not available for general distribution
(because of various Federal regulations).  No, you don't want to know.

Following is the README file from the original zip10ex.zip distribution.

David Kirschbaum
Info-ZIP Coordinator
[e-mail]
===
Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
Permission is granted to any individual or institution to use, copy, or
redistribute this software so long as all of the original files are included
unmodified, that it is not sold for profit, and that this copyright notice
is retained.

LIKE ANYTHING ELSE THAT'S FREE, ZIP AND ITS ASSOCIATED UTILITIES ARE
PROVIDED AS IS AND COME WITH NO WARRANTY OF ANY KIND, EITHER EXPRESSED OR
IMPLIED. IN NO EVENT WILL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY DAMAGES
RESULTING FROM THE USE OF THIS SOFTWARE.

Please read the file zip.doc for information on how to compile, install, and
use zip, zipcloak (if this is not an export version), zipsplit, zipnote, and
ship.  The file "contents" is a complete list of the files you should have in
this distribution.  Also, if you are using MSDOS, you should read the note on
file formats at the end of the contents file.
----------
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to [e-mail] if you want that tool.
# Contents:  README im_ctree.c makevms.com
# Wrapped by kent@sparky on Sun Oct 20 22:58:51 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 9)."'
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
  echo shar: Extracting \"'README'\" \(929 characters\)
  sed "s/^X//" >'README' <<'END_OF_FILE'
XCopyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
XPermission is granted to any individual or institution to use, copy, or
Xredistribute this software so long as all of the original files are included
Xunmodified, that it is not sold for profit, and that this copyright notice
Xis retained.
X
XLIKE ANYTHING ELSE THAT'S FREE, ZIP AND ITS ASSOCIATED UTILITIES ARE
XPROVIDED AS IS AND COME WITH NO WARRANTY OF ANY KIND, EITHER EXPRESSED OR
XIMPLIED. IN NO EVENT WILL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY DAMAGES
XRESULTING FROM THE USE OF THIS SOFTWARE.
X
XPlease read the file zip.doc for information on how to compile, install, and
Xuse zip, zipcloak (if this is not an export version), zipsplit, zipnote, and
Xship.  The file "contents" is a complete list of the files you should have in
Xthis distribution.  Also, if you are using MSDOS, you should read the note on
Xfile formats at the end of the contents file.
END_OF_FILE
  if test 929 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
  fi
  # end of 'README'
fi
if test -f 'im_ctree.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'im_ctree.c'\"
else
  echo shar: Extracting \"'im_ctree.c'\" \(45523 characters\)
  sed "s/^X//" >'im_ctree.c' <<'END_OF_FILE'
X/*
X
X Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
X Permission is granted to any individual or institution to use, copy, or
X redistribute this software so long as all of the original files are included
X unmodified, that it is not sold for profit, and that this copyright notice
X is retained.
X
X*/
X
X/*
X *  im_ctree.c by Richard B. Wales.
X *
X *  Includes modifications by Jean-Loup Gailly.
X *
X *  PURPOSE
X *
X *      Encode various sets of source values using variable-length
X *      binary code trees.
X *
X *  DISCUSSION
X *
X *      The PKZIP "implosion" process uses several variable-depth binary
X *      code trees, similar to Huffman trees.  The more common source
X *      values are represented by shorter bit sequences.
X *
X *      Each code tree is stored in the ZIP file in a compressed form
X *      that is essentially a run-length-encoded list of the lengths of
X *      all the code strings (in ascending order by source values).
X *      The actual code strings are reconstructed from the lengths in
X *      the UNZIP process, as described in the "application note"
X *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
X *
X *      Because of the way a code tree is stored in the ZIP file, the
X *      codes must conform to the following restrictions:
X *
X *      (1) No code string may ever exceed 16 bits in length.
X *
X *      (2) If all code strings are extended to 16 bits by padding on
X *          the right (low-order end) with zeros, and then treated as
X *          unsigned 16-bit integers, then:
X *
X *          (a) The arithmetically higher 16-bit values must correspond
X *              to the shorter code strings.
X *
X *          (b) If two source values map into code strings of the same
X *              length, the higher code string must correspond to the
X *              lower source value (where source values are treated as
X *              unsigned).
X *
X *      Further, shortcuts taken by PKUNZIP 1.10 in the way it decodes
X *      the compressed data via the trees impose the following extra
X *      limitations:
X *
X *      (3) No code string in the "distance" tree can be longer than 8
X *          bits.
X *
X *      (4) The maximum length of any code string is limited by the
X *          number of initial zero bits, as follows:
X *
X *          (a) 0-3 leading zeros:  maximum length is 8.
X *
X *          (b) 4-5 leading zeros:  maximum length is 12.
X *
X *          (c) 6-7 leading zeros:  maximum length is 14.
X *
X *      (5) In the "literal" tree, the code string corresponding to the
X *          source value 255 must be at least 10 bits in length, regard-
X *          less of the frequency of the value 255 in the file.
X *
X *      PKWARE calls the code trees "Shannon-Fano trees".  (Shannon-Fano
X *      coding was a predecessor to the better-known Huffman coding
X *      technique; see the references below.)  Although it appears that
X *      the Shannon-Fano (top-down partitioning) algorithm is in fact
X *      used by PKZIP in the process of creating the code trees, the
X *      resulting trees are not in fact "pure" Shannon-Fano, because of
X *      the extra processing required in order to meet the restrictions
X *      described above.
X *
X *  REFERENCES
X *
X *      Lynch, Thomas J.
X *          Data Compression:  Techniques and Applications, pp. 53-55.
X *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
X *
X *      Storer, James A.
X *          Data Compression:  Methods and Theory, pp. 49-50.
X *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
X *
X *  INTERFACE
X *
X *      ImpErr ct_init (void)
X *          Initialize the code tree routines.  This routine must be
X *          called before any other code tree routines may be called.
X *
X *      ImpErr ct_tally (MATCH *ma)
X *          Tally a "string match" data set.  The tally results will be
X *          used to determine how large the imploded result will be.
X *
X *      ImpErr ct_mktrees (FDATA *fd)
X *          Construct all code trees, and then determine how big the
X *          imploded file will be under both "literal tree" and "no
X *          literal tree" conditions.  Choose the best option.
X *
X *      ImpErr ct_wrtrees (FILE *outfp)
X *          Output the code trees to the ZIP file.
X *
X *      ImpErr ct_wrdata (FILE *outfp)
X *          Output the file data to the ZIP file.
X *
X *      ImpErr ct_windup (void)
X *          Deallocate all code trees.
X */
X
X
X#ifdef DEBUG
X#   define VALIDATE
X#endif /* DEBUG */
X
X#include "implode.h"
X
X
X/***********************************************************************
X *
X * Local data used by the "code tree" routines.
X */
X
X
X/* Data structure describing a single value and its code string. */
Xtypedef
Xstruct  ct_data
X    {   UL_INT  ct_freq;                /* frequency count */
X        US_INT  ct_code;                /* bit string */
X        U_CHAR  ct_len;                 /* length of bit string */
X        U_CHAR  ct_val;                 /* source value */
X    }
X    TRDATA;
X
X
X/*
X * Data structure for re-sorting source values by bit string length;
X * used during tree generation.
X */
Xtypedef
Xstruct  ct_resort
X    {   U_CHAR  ct_rlen;                /* length of bit string */
X        U_CHAR  ct_rval;                /* source value */
X#ifdef VMS
X        US_INT  dummy;                  /* because of bug in qsort() */
X#endif /* VMS */
X    }
X    RESORT;
X
X
X/* Header for a code tree. */
Xtypedef
Xstruct  ct_desc
X    {   TRDATA *ct_array;               /* array of TRDATA */
X        int     ct_size;                /* # of entries in tree */
X    }
X    TRDESC;
X
X
X/*
X * Currently active code trees.
X * We allow for five trees (one literal tree, two length trees, and
X * two distance trees) so that we can evaluate the total compression
X * with or without the use of the literal tree.  Remember that the
X * minimum matching distance depends on whether or not a literal tree
X * is used; hence, the "length" and "distance" trees will differ.
X */
X#define MAXTREES        5               /* max # of trees at once */
Xlocal   TRDESC  ct_table[MAXTREES];
X
X
X/* Macro to validate a code tree handle. */
X#define VALID_HANDLE(x) \
X        ((x) >= 0 && (x) < MAXTREES && ct_table[x].ct_array != NULL)
X
X
X/*
X * Assorted frequency counts.
X * The "Minimum Match Length" (MML) is 2 if a "literal character" code
X * tree is not used, or 3 if a "literal character" tree is used.  Thus,
X * we need to keep two sets of "length" and "distance" frequency counts.
X * Also, 2-character matches need to be counted separately; depending
X * on whether a "literal character" tree is used or not, these will be
X * processed either as literal characters or as distance/length pairs.
X */
X
X/* Total number of source values from Pass One. */
Xlocal   long    ct_litc_num;            /* total # literal chars */
Xlocal   long    ct_lit2_num;            /* total # of 2-char matches */
Xlocal   long    ct_strg_num;            /* total # of string matches */
X
X/* Source value frequencies for the five trees. */
Xlocal   long    ct_litc_freq[256];      /* literal character freqs */
Xlocal   long    ct_len2_freq[64];       /* length freqs (MML=2) */
Xlocal   long    ct_len3_freq[64];       /* length freqs (MML=3) */
Xlocal   long    ct_dst2_freq[64];       /* distance freqs (MML=2) */
Xlocal   long    ct_dst3_freq[64];       /* distance freqs (MML=3) */
X
X/* Number of bits saved by using each of the trees. */
Xlocal   long    ct_litc_saved;          /* literal tree */
Xlocal   long    ct_len2_saved;          /* length tree (MML=2) */
Xlocal   long    ct_len3_saved;          /* length tree (MML=3) */
Xlocal   long    ct_dst2_saved;          /* distance tree (MML=2) */
Xlocal   long    ct_dst3_saved;          /* distance tree (MML=3) */
X
X/* Handles for the code trees to be used. */
Xlocal   int     ct_litc_tree;           /* temp literal tree */
Xlocal   int     ct_len2_tree;           /* temp length tree (MML=2) */
Xlocal   int     ct_len3_tree;           /* temp length tree (MML=3) */
Xlocal   int     ct_dst2_tree;           /* temp distance tree (MML=2) */
Xlocal   int     ct_dst3_tree;           /* temp distance tree (MML=3) */
Xlocal   int     lit_tree;               /* literal tree (-1 if none) */
Xlocal   int     len_tree;               /* length tree */
Xlocal   int     dst_tree;               /* distance tree */
X
X
X/***********************************************************************
X *
X * Local (static) routines in this file.
X */
X
Xlocal ImpErr ct_alloc
X        OF ((int size, int *handle));
X
Xlocal ImpErr ct_free
X        OF ((int handle));
X
Xlocal ImpErr ct_loadf
X        OF ((int handle, long *freq));
X
Xlocal ImpErr ct_ziprep
X        OF ((int handle, U_CHAR **result));
X
Xlocal ImpErr ct_gencodes
X        OF ((int handle, int minbits, int maxbits, long *saved));
X
Xlocal ImpErr ct_split
X        OF ((TRDATA *part, int size, long freq,
X             int prefix, int preflen, int minbits, int maxbits));
X
Xlocal int ct_fsort
X        OF ((TRDATA *tr1, TRDATA *tr2));
X
Xlocal int ct_rsort
X        OF ((RESORT *cr1, RESORT *cr2));
X
X
X/***********************************************************************
X *
X * Allocate a code tree.
X */
X
Xlocal
XImpErr
Xct_alloc (size, handle)
X    int size;
X    int *handle;
X{   register TRDATA *ct;
X    int n;
X
X#ifdef VALIDATE
X    /* Validate the arguments. */
X    if (size < 2 || size > 256) goto badarg;
X    if (handle == NULL)         goto badarg;
X#endif /* VALIDATE */
X
X    /* Allocate an available code tree handle. */
X    for (n = 0;
X         n < MAXTREES && ct_table[n].ct_array != NULL;
X         n++) ;
X    if (n >= MAXTREES) return IM_NOCTBLS;
X    *handle = n;
X    ct_table[n].ct_size  = size;
X
X    /* Allocate space for the code tree. */
X    ct = (TRDATA *) malloc ((unsigned) (size * sizeof (TRDATA)));
X    if (ct == NULL) return IM_NOMEM;
X    ct_table[n].ct_array = ct;
X
X    /* Initialize the code tree. */
X    for (n = 0; n < size; n++, ct++)
X    {   ct->ct_freq = 0;
X        ct->ct_code = 0;
X        ct->ct_val  = (U_CHAR)n;
X        ct->ct_len  = 0;
X    }
X
X    /* That's all. */
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_alloc: bad argument(s)");
X    return IM_BADARG;
X#endif /* VALIDATE */
X}
X
X
X/***********************************************************************
X *
X * Free a code tree.
X */
X
Xlocal
XImpErr
Xct_free (handle)
X    int handle;
X{
X#ifdef VALIDATE
X    /* Validate the argument. */
X    if (!VALID_HANDLE (handle)) goto badarg;
X#endif /* VALIDATE */
X
X    /* Free the code tree. */
X    free ((char *) ct_table[handle].ct_array);
X    ct_table[handle].ct_array = NULL;
X    ct_table[handle].ct_size  = 0;
X
X    /* That's all. */
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_free: bad argument(s)");
X    return IM_BADARG;
X#endif /* VALIDATE */
X}
X
X
X/***********************************************************************
X *
X * Update a code tree with frequency data.
X *
X * In order to allow for the later addition of "adaptive" coding,
X * the new frequencies are added to the existing data.
X */
X
Xlocal
XImpErr
Xct_loadf (handle, freq)
X    int   handle;
X    long *freq;
X{   register long *f;
X    register TRDATA *ct;
X    int n;
X
X#ifdef VALIDATE
X    /* Validate the arguments. */
X    if (!VALID_HANDLE (handle)) goto badarg;
X#endif /* VALIDATE */
X
X    /* Add in the frequencies. */
X    for (f = freq,
X             ct = ct_table[handle].ct_array,
X             n = ct_table[handle].ct_size;
X         n > 0;
X         f++, ct++, n--)
X        ct->ct_freq += *f;
X
X    /* That's all. */
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_loadf: bad argument(s)");
X    return IM_BADARG;
X#endif /* VALIDATE */
X}
X
X
X/***********************************************************************
X *
X * Generate the ZIP-file representation for a code tree.
X *
X * The returned "result" value points to static data which will be
X * overwritten on the next call to "ct_ziprep".
X *
X * The length of the result string is implicit in the first byte of
X * the value, as specified in the PKZIP applications note.
X */
X
X#ifdef IMPDEBUG
Xchar *treename;
X#endif /* IMPDEBUG */
X
Xlocal
XImpErr
Xct_ziprep (handle, result)
X    int      handle;
X    U_CHAR **result;
X{   static U_CHAR buffer[257];          /* result info */
X    register U_CHAR *c;
X    register TRDATA *ct;
X    int s, n, l;
X
X#ifdef VALIDATE
X    /* Validate the arguments. */
X    if (!VALID_HANDLE (handle)) goto badarg;
X    if (result == NULL)         goto badarg;
X#endif /* VALIDATE */
X
X#ifdef  IMPDEBUG
X    if (treename != NULL && treename[0] != 0)
X    {   /* Print the code tree info. */
X        fprintf (stderr, "\n%s tree:\n  value      len   string\n",
X                 treename);
X        for (ct = ct_table[handle].ct_array,
X                  s = ct_table[handle].ct_size,
X                  n = 0;
X             s > 0;
X             ct++, n++, s--)
X            fprintf (stderr, "  %3d (%02x)    %2d    %04x (rev %04x)\n",
X                     n, n, ct->ct_len,
X                     bi_reverse(ct->ct_code << (16 - ct->ct_len),
X                                ct->ct_len) << (16 - ct->ct_len),
X                     ct->ct_code);
X    }
X#endif  /* IMPDEBUG */
X
X    /* Generate the returned value. */
X    for (c = buffer+1,
X             ct = ct_table[handle].ct_array,
X             s = ct_table[handle].ct_size,
X             n = 0,
X             l = ct->ct_len;
X         s > 0;
X         ct++, s--)
X    {   if (l < 1 || l > 16)
X        {   fprintf (stderr, "\nError in ct_ziprep: bad code length");
X            return IM_LOGICERR;
X        }
X        if (n >= 16 || (int)ct->ct_len != l)
X        {   *c++ = (U_CHAR)((((n-1) << 4) & 0xf0) | ((l-1) & 0x0f));
X            n = 1; l = ct->ct_len;
X        }
X        else n++;
X    }
X    if (n > 0)
X        *c++ = (U_CHAR)((((n-1) << 4) & 0xf0) | ((l-1) & 0x0f));
X    buffer[0] = (U_CHAR)((c - buffer) - 2);
X
X    /* That's all. */
X    *result = buffer;
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_ziprep: bad argument(s)");
X    return IM_BADARG;
X#endif /* VALIDATE */
X}
X
X
X/***********************************************************************
X *
X * Look up the code string for a given value.
X */
X
X#define ct_lookup(handle, value, string, length) \
X{   register TRDATA *ct; \
X    ct = ct_table[handle].ct_array + (value); \
X    string = ct->ct_code; \
X    length = ct->ct_len; \
X}
X
X
X/***********************************************************************
X *
X * Generate the codes for a code tree.  If old codes already exist for
X * the tree, they are discarded, and a new set of codes is generated
X * from scratch.
X * IN assertion: ma_buf is already allocated and can be overwritten.
X */
X
Xlocal
XImpErr
Xct_gencodes (handle, minbits, maxbits, saved)
X    int   handle;                       /* which tree */
X    int   minbits;                      /* min code string bit length */
X    int   maxbits;                      /* max code string bit length */
X    long *saved;                        /* how many bits saved */
X{   register TRDATA *ct;
X    TRDATA *ct2;
X    register int n;
X    UL_INT f;
X    register RESORT *cr;
X    int code, srclen;
X    long totalfreq, totalbits;
X    ImpErr retcode;
X    RESORT rbuf[256];
X    int size; /* alias for ct_table[handle].ct_size */
X    int z;    /* index of zero frequency element */
X    int nz;   /* index of non zero frequency element */
X
X#ifdef VALIDATE
X    /* Validate the arguments. */
X    if (!VALID_HANDLE (handle)) goto badarg;
X    if (minbits < 1)            goto badarg;
X    if (maxbits > 16)           goto badarg;
X    if (maxbits < minbits)      goto badarg;
X    if (saved == NULL)          goto badarg;
X#endif /* VALIDATE */
X    size = ct_table[handle].ct_size;
X
X    /*
X     * Start by sorting the data by frequency.  The source values with
X     * higher frequency need to get the shorter Shannon-Fano codes.
X     * First exclude the elements with zero frequency, to speed up the sort.
X     * This optimization is very important for small files, otherwise the sort
X     * takes most of the implode time.
X     *    Also determine the total of all frequencies.  This will be needed in
X     * order to partition the source values in the Shannon-Fano bit
X     * string computation. Finally clear the "code" (bit string) and "len"
X     * (bit string length) fields in the code tree array.
X     */
X    totalfreq = 0;
X    ct = ct_table[handle].ct_array;
X    /* Copy ct into a tempo */
X    ct2 = (TRDATA*) ma_buf;
X    memcpy((char*)ct2, (char*)ct, size * sizeof(TRDATA));
X    for (nz = 0, z = n = size-1; n >= 0; n--) {
X        int m;
X        if (ct2[n].ct_freq != 0L) {
X            m = nz++;
X            totalfreq += (ct[m].ct_freq = ct2[n].ct_freq);
X        } else {
X            m = z--;
X            ct[m].ct_freq = 0L;
X        }
X        ct[m].ct_code = 0;
X        ct[m].ct_len = 0;
X        ct[m].ct_val = (U_CHAR)n; /* ct2[n].ct_val */
X    }
X    qsort ((char *) (ct_table[handle].ct_array), nz,
X           sizeof (TRDATA), (int (*)())ct_fsort);
X
X    /*
X     * Generate the bit strings via a Shannon-Fano (top-down) algorithm.
X     */
X    retcode =
X        ct_split (ct_table[handle].ct_array,    /* partition start */
X                  size,                         /* partition size */
X                  totalfreq,                    /* total frequency */
X                  0,                            /* code string prefix */
X                  0,                            /* # bits in prefix */
X                  minbits,                      /* minimum tree depth */
X                  maxbits);                     /* maximum tree depth */
X    if (retcode != IM_OK) return retcode;
X
X    /*
X     * The source value 255 needs to be assigned a bit string with a
X     * length of at least 10, in order to accommodate shortcuts in
X     * PKUNZIP's decoding algorithm.  If no bit string in the tree is
X     * of length 10, we assign 255 to the longest string and hope for
X     * the best.
X     */
X    n = size;
X    if (n == 256)
X    {   for (ct = ct_table[handle].ct_array;
X             n > 0 && ct->ct_val != 255;
X             n--, ct++) ;
X        if (n == 0)
X        {   fprintf (stderr, "\nError in ct_gencodes: no value 255");
X            return IM_LOGICERR;
X        }
X        if (ct->ct_len < 10)
X        {   ct2 = ct;
X            while (n > 0 && ct->ct_len < 10) n--, ct++;
X            if (n == 0) ct--;   /* no len>=10 in tree; use longest */
X            n = ct->ct_val;
X                ct->ct_val = ct2->ct_val;
X                ct2->ct_val = (U_CHAR)n;
X            f = ct->ct_freq;
X                ct->ct_freq = ct2->ct_freq;
X                ct2->ct_freq = f;
X    }   }
X
X    /*
X     * The source values need to be re-sorted so that all source values
X     * with code strings of the same length will be in ascending order.
X     * This is because of the compression scheme used to represent the
X     * tree in the ZIP file.
X     */
X    for (n = size,
X             ct = ct_table[handle].ct_array,
X             cr = rbuf;
X         n > 0;
X         n--, ct++, cr++)
X    {   cr->ct_rlen = ct->ct_len;
X        cr->ct_rval = ct->ct_val;
X    }
X    n = size;
X    qsort ((char *) rbuf, n, sizeof (RESORT), (int (*)())ct_rsort);
X    for (ct = ct_table[handle].ct_array,
X             cr = rbuf;
X         n > 0;
X         n--, ct++, cr++)
X        ct->ct_val = cr->ct_rval;
X
X#ifdef DUMP_TREE
X    printf ("Finished tree:\n");
X    for (n = size,
X             ct = ct_table[handle].ct_array;
X         n > 0;
X         n--, ct++)
X        printf ("  %3d (0x%02x)  l %2d  c 0x%04x f %ld\n",
X                ct->ct_val, ct->ct_val, ct->ct_len, ct->ct_code, ct->ct_freq);
X    putchar ('\n');
X#endif /* DUMP_TREE */
X
X    /*
X     * Finally, sort the tree back in ascending order by source value
X     * -- which is the order expected by other portions of the program.
X     */
X    ct = ct_table[handle].ct_array;
X    /* Copy ct into a tempo */
X    ct2 = (TRDATA*)ma_buf;
X    memcpy((char*)ct2, (char*)ct, size * sizeof(TRDATA));
X    for (n = size-1; n >= 0; n--) {
X        U_CHAR v = ct2[n].ct_val;
X        ct[v].ct_freq = ct2[n].ct_freq;
X        ct[v].ct_code = ct2[n].ct_code;
X        ct[v].ct_len = ct2[n].ct_len;
X        ct[v].ct_val = v;
X    }
X
X    /*
X     * Determine how many bits will be saved if all the source data is
X     * encoded using this new set of code strings, as opposed to being
X     * represented directly in unencoded form.
X     */
X    /* # of bits needed for unencoded source values */
X    n = ct_table[handle].ct_size;
X    for (code = 1, srclen = 0; code < n; code <<= 1, srclen++) ;
X    /* # of bits used if all source values encoded via this tree */
X    for (ct = ct_table[handle].ct_array,
X             totalbits = 0;
X         n > 0;
X         n--, ct++)
X        totalbits += ct->ct_freq * ct->ct_len;
X    /* # bits saved by using the tree */
X    *saved = (totalfreq * srclen) - totalbits;
X
X    /* That's all. */
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_gencodes: bad argument(s)");
X    return IM_BADARG;
X#endif /* VALIDATE */
X}
X
X
X/***********************************************************************
X *
X * Split a portion of a code tree into two pieces of approximately equal
X * total frequency.  This routine calls itself recursively in order to
X * generate the bit strings for the entire code tree.
X */
X
Xlocal
XImpErr
Xct_split (part, size, freq, prefix, preflen, minbits, maxbits)
X    TRDATA *part;               /* start of partition */
X    int     size;               /* # elements in partition */
X    long    freq;               /* sum of frequencies in partition */
X    int     prefix;             /* initial code bits for partition */
X    int     preflen;            /* # bits in prefix */
X    int     minbits;            /* minimum permissible bit length */
X    int     maxbits;            /* maximum permissible bit length */
X{   register TRDATA *ct;
X    int topmaxbits, botmaxbits, localminbits;
X    U_INT topmaxvals, botmaxvals;
X    int topsize, botsize;
X    long topfreq, botfreq, halffreq, onefreq;
X    int n, m, leadzeros;
X    int maxshort, minlong;
X    ImpErr retcode;
X    static maxarray[17] =
X        { 8,8,8,8,12,12,14,14,16,16,16,16,16,16,16,16,16 };
X
X#ifdef VALIDATE
X    if (part == NULL)           goto badarg;
X    if (size < 1)               goto badarg;
X    if (freq < 0)               goto badarg;
X    if (preflen < 0)            goto badarg;
X    if (preflen > maxbits)      goto badarg;
X    if (minbits < preflen)      goto badarg;
X    if (maxbits > 16)           goto badarg;
X    if (maxbits < minbits)      goto badarg;
X    /*
X    putc ('\n', stderr);
X    for (n = preflen; n > 0; n--) fprintf (stderr, "   ");
X    fprintf (stderr, "ct_split (sz=%d, pr=%04x[%d], min=%d, max=%d)",
X             size, prefix, preflen, minbits, maxbits);
X    */
X#endif /* VALIDATE */
X
X    /*
X     * If there's only one element in this partition, we simply take
X     * the "prefix" value as the code string for the single element.
X     * We reverse the bits of the prefix for more efficient output.
X     */
X    if (size == 1)
X    {   part->ct_code = bi_reverse(prefix, preflen);
X        part->ct_len  = (U_CHAR)preflen;
X        return IM_OK;
X    }
X
X    /*
X     * This partition will be divided into two parts.  The "top" part
X     * will have a "1" bit appended to its "prefix" bit string; the
X     * "bottom" part will have a "0" bit appended to its "prefix".
X     *
X     * We need to determine the maximum number of source values which
X     * may be assigned to the two partitions.  The first issue to con-
X     * sider is that PKUNZIP 1.10's tree-decoding shortcuts require a
X     * certain number of leading "0" bits in each code string, depending
X     * on its length.  Code strings of 9-12 bits must have at least 4
X     * leading zeros; strings of 13 or 14 bits, at least 6 leading
X     * zeros; and strings of 15 or 16 bits, at least 8 leading zeros.
X     *
X     * If the "prefix" is zero, the above limitation is used to restrict
X     * the maximum size of the top half of the partition.  The bottom
X     * half does not need to be restricted in this way, since it can be
X     * extended as far as needed along the path where the "prefix" grows
X     * in length but remains all zero.
X     */
X    botmaxbits = maxbits;
X    if (prefix != 0) topmaxbits = maxbits;
X    else
X    {   for (n = 0, leadzeros = 0x8000;
X             n < preflen && (prefix & leadzeros) == 0;
X             n++, leadzeros >>= 1) ;
X        topmaxbits = maxarray[n];
X        if (topmaxbits > maxbits) topmaxbits = maxbits;
X    }
X    if (topmaxbits < minbits)
X    {   fprintf (stderr, "\nError in ct_split: ");
X        fprintf (stderr, "topmaxbits(%d) < minbits(%d)",
X                 topmaxbits, minbits);
X        goto oops;
X    }
X    if (botmaxbits < minbits)
X    {   fprintf (stderr, "\nError in ct_split: ");
X        fprintf (stderr, "botmaxbits(%d) < minbits(%d)",
X                 botmaxbits, minbits);
X        goto oops;
X    }
X    topmaxvals = 1 << (topmaxbits - preflen - 1);
X    n = size >> 1; if (topmaxvals > n) topmaxvals = n;
X    botmaxvals = 1 << (botmaxbits - preflen - 1);
X    n = size - 1;  if (botmaxvals > n) botmaxvals = n;
X    if (topmaxvals + botmaxvals < size)
X    {   fprintf (stderr, "\nError in ct_split: ");
X        fprintf (stderr, "topmaxvals(%d) + botmaxvals(%d) ",
X                 topmaxvals, botmaxvals);
X        fprintf (stderr, "< size(%d)", size);
X        goto oops;
X    }
X
X    /*
X     * We now split the current partition into two halves of as close
X     * to equal frequency as possible.  If the total of all frequencies
X     * in the partition is zero, split into two halves of equal size.
X     */
X    if (freq == 0)
X    {   topsize = size >> 1;
X        ct = part + topsize;
X        topfreq = 0;
X    }
X    else
X    {   halffreq = freq >> 1;           /* half the total frequency */
X        m = size >> 1;                  /* half the total elements, */
X                                        /*    rounded down          */
X        for (topsize = 0, topfreq = 0, ct = part;
X             topsize < m && topfreq <= halffreq
X                 && (onefreq = ct->ct_freq) > 0;
X             topsize++, ct++)
X            topfreq += onefreq;
X        if (topsize >= 2)
X        {   /*
X             * If moving one element from the top to the bottom parti-
X             * tion would make the two more closely equal in frequency,
X             * do it.
X             */
X            onefreq = (ct-1)->ct_freq;
X            if ((topfreq - halffreq) > (halffreq - (topfreq - onefreq)))
X                ct--, topsize--, topfreq -= onefreq;
X    }   }
X    botsize = size - topsize;
X    botfreq = freq - topfreq;
X    /* "ct" points to first element in bottom half */
X
X    /*
X     * The above first-cut attempt to split the partition may not work
X     * for one of two reasons.  First, one or the other half may contain
X     * too many values (more than "topmaxvals" or "botmaxvals").
X     */
X    while (topsize > topmaxvals)
X    {   onefreq = (--ct)->ct_freq;
X        topsize--; topfreq -= onefreq;
X        botsize++; botfreq += onefreq;
X    }
X    while (botsize > botmaxvals)
X    {   onefreq = (ct++)->ct_freq;
X        topsize++; topfreq += onefreq;
X        botsize--; botfreq -= onefreq;
X    }
X
X    /*
X     * Second, the number of bits required to represent the values in
X     * each half may violate PKZIP's requirement (implicit in the way
X     * trees are compressed in an imploded file) that no code string in
X     * the top half may be longer than any code string in the bottom
X     * half.
X     */
X    localminbits = preflen + 1;
X    if (localminbits < minbits) localminbits = minbits;
X    for (;;)
X    {   for (maxshort = preflen + 1, n = 1;
X             n < botsize;
X             maxshort++, n <<= 1) ;
X        if (n > botsize) maxshort--;
X        if (maxshort < localminbits) maxshort = localminbits;
X        if (maxshort > topmaxbits) maxshort = topmaxbits;
X        for (minlong = preflen + 1, n = 1;
X             n < topsize;
X             minlong++, n <<= 1) ;
X        if (minlong <= maxshort) break;
X        onefreq = (--ct)->ct_freq;
X        topsize--; topfreq -= onefreq;
X        botsize++; botfreq += onefreq;
X    }
X
X    /*
X     * Third, the number of elements in the top half must be enough to
X     * result in each string having at least "minbits" bits in all.
X     */
X    n = 1 << (minbits - preflen - 1);
X    while (topsize < n)
X    {   onefreq = (ct++)->ct_freq;
X        topsize++; topfreq += onefreq;
X        botsize--; botfreq -= onefreq;
X    }
X
X    /*
X     * Now that the sizes of the two halves of the partition have been
X     * finalized, process the top and bottom halves via recursion.
X     */
X    retcode = ct_split (part, topsize, topfreq,
X                        prefix | (1 << (15-preflen)),
X                        preflen + 1, localminbits, maxshort);
X    if (retcode != IM_OK) return retcode;
X    ct = part + topsize;
X    retcode = ct_split (ct, botsize, botfreq,
X                        prefix, preflen + 1, (int)ct[-1].ct_len, maxbits);
X    if (retcode != IM_OK) return retcode;
X
X    /* That's all. */
X    return IM_OK;
X
X#ifdef VALIDATE
Xbadarg:
X    fprintf (stderr, "\nError in ct_split: bad argument(s)");
X    putchar ('\n'); fflush (stdout); fflush (stderr);
X    /* abort (); */
X    return IM_BADARG;
X#endif /* VALIDATE */
X
Xoops:
X#ifdef VALIDATE
X    putchar ('\n'); fflush (stdout); fflush (stderr);
X    /* abort (); */
X#endif /* VALIDATE */
X    return IM_LOGICERR;
X}
X
X
X/***********************************************************************
X *
X * Sorting function -- descending order by source value frequency.
X *
X * This sorting function is used at the start of the code tree con-
X * struction process, before the bit string values are assigned.
X * To ensure consistent behaviour on all machines, we use the source
X * values as secondary sort key, but this is not mandatory.
X */
X
Xlocal
Xint
Xct_fsort (tr1, tr2)
X    TRDATA *tr1, *tr2;
X{   long d;
X    int v;
X
X    d = (long) tr1->ct_freq - (long) tr2->ct_freq;
X    if (d < 0) return 1;
X    if (d > 0) return -1;
X    v = (int) tr1->ct_val - (int) tr2->ct_val;
X    if (v < 0) return 1;
X    if (v > 0) return -1;
X    return 0;
X}
X
X
X/***********************************************************************
X *
X * Sorting function -- ascending order by bit string length; if lengths
X * are the same, ascending order by source value.
X *
X * This sorting function is used after the bit string values have been
X * assigned.
X */
X
Xlocal
Xint
Xct_rsort (cr1, cr2)
X    RESORT *cr1, *cr2;
X{   int d;
X
X    d = (int) cr1->ct_rlen - (int) cr2->ct_rlen;
X    if (d > 0) return 1;
X    if (d < 0) return -1;
X    d = (int) cr1->ct_rval - (int) cr2->ct_rval;
X    if (d > 0) return 1;
X    if (d < 0) return -1;
X    return 0;
X}
X
X
X/***********************************************************************
X *
X * Allocate the code trees.
X */
X
XImpErr
Xct_init ()
X{   ImpErr retcode;
X    int i;
X
X#ifdef DEBUG
X    if (256*sizeof(TRDATA) > MA_BUFSIZE*sizeof(MATCH)) return IM_LOGICERR;
X#endif /* DEBUG */
X
X    retcode = ct_windup ();
X        if (retcode != IM_OK) return retcode;
X
X    ct_litc_num = 0;
X    ct_lit2_num = 0;
X    ct_strg_num = 0;
X
X    for (i = 255; i >= 0;  i--)
X        ct_litc_freq[i] = 0;
X    for (i = 63; i >= 0; i--)
X        ct_len2_freq[i] = 0, ct_len3_freq[i] = 0,
X        ct_dst2_freq[i] = 0, ct_dst3_freq[i] = 0;
X
X    retcode = ct_alloc (256, &ct_litc_tree);
X    if (retcode != IM_OK) return retcode;
X    retcode = ct_alloc  (64, &ct_len2_tree);
X    if (retcode != IM_OK) return retcode;
X    retcode = ct_alloc  (64, &ct_len3_tree);
X    if (retcode != IM_OK) return retcode;
X    retcode = ct_alloc  (64, &ct_dst2_tree);
X    if (retcode != IM_OK) return retcode;
X    retcode = ct_alloc  (64, &ct_dst3_tree);
X    if (retcode != IM_OK) return retcode;
X
X    return IM_OK;
X}
X
X
X/***********************************************************************
X *
X * Tally a "string match" data set.  The tally results will be used to
X * determine how large the imploded result will be.
X */
X
XImpErr
Xct_tally (ma)
X         MATCH *ma;             /* match data to write out */
X{   register int ch;
X    int dist = ma->ma_dist;
X
X    /* Tally up the latest data. */
X    if (dist == 0) {                 /* literal character */
X            ct_litc_num++;
X            ch = ma->l.ma_litc[0];
X                ct_litc_freq[ch]++;
X
X    } else if (dist < 0) {           /* 2-character match */
X            ct_lit2_num++;
X            ch = ma->l.ma_litc[0];
X                ct_litc_freq[ch]++;
X            ch = ma->l.ma_litc[1];
X                ct_litc_freq[ch]++;
X            ch = ((-dist-1) >> fd.fd_nbits) & 0x3f;
X                ct_dst2_freq[ch]++;
X            ct_len2_freq[0]++;
X
X     } else {                        /* 3-char or longer match */
X            ct_strg_num++;
X            ch = ((dist-1) >> fd.fd_nbits) & 0x3f;
X                ct_dst3_freq[ch]++;
X         /* We defer the update of ct_dst2_freq and ct_len2_freq until
X          * ct_mktrees:
X          *     ct_dst2_freq[ch]++;
X          * ch = ma->l.ma_length - 2;
X          *     if (ch > 63) ch = 63;
X          *     ct_len2_freq[ch]++;
X          */
X            ch = ma->l.ma_length - 3;
X                if (ch > 63) ch = 63;
X                ct_len3_freq[ch]++;
X    }
X
X    /* That's all. */
X    return IM_OK;
X}
X
X
X/***********************************************************************
X *
X * Construct all code trees, and then determine how big the imploded
X * file will be under both "literal tree" and "no literal tree" con-
X * ditions.  Choose the best option.
X */
X
XImpErr
Xct_mktrees ()
X{   U_CHAR *c;
X    ImpErr retcode;
X    register long sum;
X    long len2, len3;
X    int n;
X
X    /* ct_tally did not update ct_dst2_freq and ct_len2_freq for matches of
X     * length > 2, so correct this now.
X     */
X    for (n = 62; n >= 0; n--) {
X        ct_dst2_freq[n] += ct_dst3_freq[n];
X        ct_len2_freq[n+1] += ct_len3_freq[n];
X    }
X    ct_dst2_freq[63] += ct_dst3_freq[63];
X    ct_len2_freq[63] += ct_len3_freq[63];
X
X    /*
X     * Construct the code trees and see how much space each will save.
X     *
X     * It is conceivable that a tree could result in a negative savings
X     * if its compressed form is sufficiently long.
X     *
X     * We need to construct the ZIP-file compressed representation of
X     * each tree in order to figure out how much space it will take.
X     * However, we don't save these tree representations now; rather,
X     * we'll wait until later and reconstruct the representations for
X     * whichever two (or three) trees we really need for the output.
X     */
X#ifdef IMPDEBUG
X    treename = (char *)NULL;
X#endif /* IMPDEBUG */
X
X    /* literal code tree */
X    retcode = ct_loadf    (ct_litc_tree,  ct_litc_freq);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_gencodes (ct_litc_tree, 1, 16, &ct_litc_saved);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_ziprep   (ct_litc_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    ct_litc_saved -= (int) (c[0]+2) * 8;
X
X    /* length code tree (2) */
X    retcode = ct_loadf    (ct_len2_tree,  ct_len2_freq);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_gencodes (ct_len2_tree, 1, 16, &ct_len2_saved);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_ziprep   (ct_len2_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    ct_len2_saved -= (int) (c[0]+2) * 8;
X
X    /* length code tree (3) */
X    retcode = ct_loadf    (ct_len3_tree,  ct_len3_freq);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_gencodes (ct_len3_tree, 1, 16, &ct_len3_saved);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_ziprep   (ct_len3_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    ct_len3_saved -= (int) (c[0]+2) * 8;
X
X    /* distance code tree (2) */
X    retcode = ct_loadf    (ct_dst2_tree,  ct_dst2_freq);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_gencodes (ct_dst2_tree, 1,  8, &ct_dst2_saved);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_ziprep   (ct_dst2_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    ct_dst2_saved -= (int) (c[0]+2) * 8;
X
X    /* distance code tree (3) */
X    retcode = ct_loadf    (ct_dst3_tree,  ct_dst3_freq);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_gencodes (ct_dst3_tree, 1,  8, &ct_dst3_saved);
X        if (retcode != IM_OK) return retcode;
X    retcode = ct_ziprep   (ct_dst3_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    ct_dst3_saved -= (int) (c[0]+2) * 8;
X
X    /*
X     * Determine how big the compressed file will be
X     * with, and without, a literal character tree.
X     */
X
X    /* compressed length (no literal tree) */
X    sum  = ct_litc_num + ct_lit2_num + ct_strg_num;    /* initial bit */
X    sum += ct_litc_num * 8;                          /* literal bytes */
X    sum += (ct_lit2_num+ct_strg_num) * 6 - ct_len2_saved;  /* lengths */
X    sum += 8 * ct_len2_freq[63];                  /* oversize lengths */
X    sum += (ct_lit2_num+ct_strg_num) * (fd.fd_nbits+6)
X            - ct_dst2_saved;                             /* distances */
X    len2 = (sum+7) / 8;                           /* convert to bytes */
X
X    /* compressed length (with literal tree) */
X    sum  = ct_litc_num + 2*ct_lit2_num + ct_strg_num;  /* initial bit */
X    sum += (ct_litc_num+2*ct_lit2_num)*8 - ct_litc_saved;/* lit bytes */
X    sum += ct_strg_num * 6 - ct_len3_saved;                /* lengths */
X    sum += 8 * ct_len3_freq[63];                  /* oversize lengths */
X    sum += ct_strg_num * (fd.fd_nbits+6) - ct_dst3_saved;   /* dist's */
X    len3 = (sum+7) / 8;                           /* convert to bytes */
X
X    /*
X     * PKUNZIP 1.10 requires that the source value 255 in a "literal"
X     * tree must be represented by a bit string of length >= 10.  The
X     * literal tree was already adjusted to ensure that the value 255
X     * was given a bit string of length 10 or greater if possible.  If
X     * this did not succeed -- which would only happen if the longest
X     * bit string in the literal tree were of length 8 or 9 -- then the
X     * literal tree cannot be used.  In such a case, not much would be
X     * gained by using it anyway, so there's little reason to be upset.
X     */
X    if (ct_table[ct_litc_tree].ct_array[255].ct_len < 10)
X        len3 = len2;
X
X    /*
X     * Choose the method of compression which will use the least space
X     * for this particular file.  The possibilities are:  use a literal
X     * character tree; or, don't use a literal character tree.
X     */
X    if (len2 <= len3)
X    {   fd.fd_method = NO_LITERAL_TREE;
X        fd.fd_clen   = len2;
X        lit_tree     = -1;
X        len_tree     = ct_len2_tree;
X        dst_tree     = ct_dst2_tree;
X        retcode = ct_free (ct_litc_tree);
X            if (retcode != IM_OK) return retcode;
X        retcode = ct_free (ct_dst3_tree);
X            if (retcode != IM_OK) return retcode;
X        retcode = ct_free (ct_len3_tree);
X            if (retcode != IM_OK) return retcode;
X    }
X    else
X    {   fd.fd_method = LITERAL_TREE;
X        fd.fd_clen   = len3;
X        lit_tree     = ct_litc_tree;
X        len_tree     = ct_len3_tree;
X        dst_tree     = ct_dst3_tree;
X        retcode = ct_free (ct_dst2_tree);
X            if (retcode != IM_OK) return retcode;
X        retcode = ct_free (ct_len2_tree);
X            if (retcode != IM_OK) return retcode;
X    }
X
X    /* That's all. */
X    return IM_OK;
X}
X
X
X/***********************************************************************
X *
X * Output the code trees.
X */
X
XImpErr
Xct_wrtrees (outfp)
X    FILE *outfp;                        /* output file */
X{   ImpErr retcode;
X    U_CHAR *c;
X
X    /* Output the literal tree, if any. */
X#ifdef IMPDEBUG
X    treename = "Literal";
X#endif /* IMPDEBUG */
X    if (lit_tree >= 0)
X    {   retcode = ct_ziprep (lit_tree, &c);
X            if (retcode != IM_OK) return retcode;
X        if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
X            return IM_IOERR;
X    }
X
X    /* Output the length tree. */
X#ifdef IMPDEBUG
X    treename = "Length";
X#endif /* IMPDEBUG */
X    retcode = ct_ziprep (len_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
X        return IM_IOERR;
X
X    /* Output the distance tree. */
X#ifdef IMPDEBUG
X    treename = "Distance";
X#endif /* IMPDEBUG */
X    retcode = ct_ziprep (dst_tree, &c);
X        if (retcode != IM_OK) return retcode;
X    if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
X        return IM_IOERR;
X
X    return IM_OK;
X}
X
X/* Macros for outputting bit string. */
X
X#define OUTBITS(value,length) \
X        {   retcode = bi_rlout ((int) (value), (int) (length)); \
X                if (retcode != IM_OK) return retcode; \
X        }
X#define OUTCODE(value,tree) \
X        {   ct_lookup (tree, value, bitstring, bitlength); \
X            retcode = bi_rlout (bitstring, bitlength); \
X                if (retcode != IM_OK) return retcode; \
X        }
X
X/***********************************************************************
X *
X * Output the body of the file in imploded form.
X */
XImpErr
Xct_wrdata (outfp)
X         FILE *outfp;                   /* output (ZIP) file */
X{   MATCH *ma;
X    ImpErr retcode;
X    register int minmatch;
X    int bitstring, bitlength;
X    int bitmask = (1 << (fd.fd_nbits+1))-1;
X    /* Used to select the bottom 6 or 7 bits of a distance, which are
X     * output literally, plus 1 bit marking a distance
X     */
X    int matches;
X#ifdef  IMPDEBUG
X    long srcpos;
X#endif  /* IMPDEBUG */
X
X    /* Determine the minimum match length. */
X    minmatch = (lit_tree >= 0) ? 3 : 2;
X
X    /* Prepare the I/O. */
X    if (tflush (fd.fd_temp) != 0) return IM_IOERR;
X    trewind (fd.fd_temp);
X    retcode = bi_init (outfp);
X        if (retcode != IM_OK) return retcode;
X
X#ifdef  IMPDEBUG
X        srcpos = 0;
X        fprintf (stderr, "\nImploded output:\n");
X#endif  /* IMPDEBUG */
X
X    /* Read and process data from the temporary file. */
X    while ((matches =
X       tread ((char *) ma_buf, sizeof(MATCH), MA_BUFSIZE, fd.fd_temp)) > 0)
X       for (ma = ma_buf; matches > 0; ma++, matches--)
X    {
X        int dist = ma->ma_dist;
X        int len = 0;
X
X#ifdef  IMPDEBUG
X        fprintf (stderr, "%8ld: ", srcpos);
X#endif  /* IMPDEBUG */
X
X        if (dist < 0) {
X            dist = -dist, len = 2;
X        } else if (dist > 0) {
X            len = ma->l.ma_length;
X        }
X
X        /* Output distance and length if enough characters match. */
X        if (len >= minmatch)
X        {   /* "matched string" header bit (0) */
X#ifdef  IMPDEBUG
X            fprintf (stderr, "str (dst=%d,len=%d)  ",
X                     dist, len);
X            srcpos += len;
X#endif  /* IMPDEBUG */
X
X            /* ouput one zero bit then the distance */
X            dist--;
X            OUTBITS ((dist << 1) & bitmask, fd.fd_nbits + 1);
X            OUTCODE (dist >> fd.fd_nbits, dst_tree);
X
X            /* length -- depends on how it compares to maximum */
X            len -= minmatch;
X            if (len >= 63)
X            {   /* big length -- output code for 63, then surplus */
X                OUTCODE (63, len_tree);
X                OUTBITS ((len - 63), 8);
X            }
X            else
X            {   /* small length -- output code */
X                OUTCODE (len, len_tree);
X        }   }
X        else if (lit_tree >= 0)
X        {   /* first or single literal -- header bit (1) plus char */
X#ifdef  IMPDEBUG
X            fprintf (stderr, "lit (val=%02x)  ",
X                     ma->l.ma_litc[0] & 0xff);
X            srcpos++;
X#endif  /* IMPDEBUG */
X            OUTBITS (1, 1);
X            OUTCODE (ma->l.ma_litc[0], lit_tree);
X            if (len == 2)
X            {   /* second literal -- header bit (1) plus char */
X#ifdef  IMPDEBUG
X                fprintf (stderr, "\n%8ld: lit (val=%02x)  ",
X                         srcpos, ma->l.ma_litc[1] & 0xff);
X                srcpos++;
X#endif  /* IMPDEBUG */
X                OUTBITS (1, 1);
X                OUTCODE (ma->l.ma_litc[1], lit_tree);
X        }   }
X        else
X        {   /* single literal -- header bit (1) plus char */
X#ifdef  IMPDEBUG
X            fprintf (stderr, "lit (val=%02x)  ",
X                     ma->l.ma_litc[0] & 0xff);
X            srcpos++;
X#endif  /* IMPDEBUG */
X            OUTBITS ((ma->l.ma_litc[0] << 1) + 1, 9);
X        }
X#ifdef  IMPDEBUG
X        putc ('\n', stderr);
X#endif  /* IMPDEBUG */
X    }
X
X    /* Make sure we hit EOF on input without an error. */
X    if (terror (fd.fd_temp)
X#ifndef MINIX
X#ifndef __TURBOC__      /* TurboC 2.0 does not set the EOF flag (?) */
X        || !teof (fd.fd_temp)
X#endif /* !__TURBOC__ */
X#endif /* !MINIX */
X       )
X      return IM_IOERR;
X    retcode = bi_windup ();
X        if (retcode != IM_OK) return retcode;
X
X    /* That's all. */
X    return IM_OK;
X}
X
X#undef  OUTBITS
X#undef  OUTCODE
X
X
X/***********************************************************************
X *
X * Deallocate all code trees.
X */
X
XImpErr
Xct_windup ()
X{   int n;
X    static windup_already_called = 0;
X    ImpErr retcode;
X
X    if (windup_already_called)
X    {   /* Discard any old code trees. */
X        for (n = 0; n < MAXTREES; n++)
X        {   if (ct_table[n].ct_array != NULL)
X            {   retcode = ct_free (n);
X                if (retcode != IM_OK) return retcode;
X    }   }   }
X    else
X    {   /* Initialize the list of active code trees. */
X        for (n = 0; n < MAXTREES; n++)
X        {   ct_table[n].ct_array = NULL;
X            ct_table[n].ct_size  = 0;
X        }
X        windup_already_called = 1;
X    }
X
X    /* That's all. */
X    return IM_OK;
X}
X
X
X/**********************************************************************/
END_OF_FILE
  if test 45523 -ne `wc -c <'im_ctree.c'`; then
    echo shar: \"'im_ctree.c'\" unpacked with wrong size!
  fi
  # end of 'im_ctree.c'
fi
if test -f 'makevms.com' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'makevms.com'\"
else
  echo shar: Extracting \"'makevms.com'\" \(2470 characters\)
  sed "s/^X//" >'makevms.com' <<'END_OF_FILE'
X$ !
X$ !     "Makefile" for VMS versions of Zip, ZipNote,
X$ !      ZipSplit, Ship and UnShip (stolen from Unzip)
X$ !
X$ set verify    ! like "echo on", eh?
X$ !
X$ !------------------------------- Zip section --------------------------------
X$ !
X$ cc /def=EXPORT zip,zipfile,zipup,fileio,util,tempf,shrink,globals,implode,im_lmat,im_ctree,im_bits
X$ link zip,zipfile,zipup,fileio,util,tempf,shrink,globals,implode,im_lmat,im_ctree,im_bits,sys$input:/opt
Xsys$share:vaxcrtl.exe/shareable
X$ !
X$ ! If you have problems with implode, compile with /define=noimplode
X$ ! and remove all the im* files from the above lines.
X$ !
X$ !-------------------------- Zip utilities section ---------------------------
X$ !
X$ ren zipfile.c zipfile_.c;*
X$ ren zipup.c zipup_.c;*
X$ ren fileio.c fileio_.c;*
X$ ren util.c util_.c;*
X$ cc /def=EXPORT zipnote, zipsplit
X$ cc /def=EXPORT /def=UTIL zipfile_, zipup_, fileio_, util_
X$ ren zipfile_.c zipfile.c;*
X$ ren zipup_.c zipup.c;*
X$ ren fileio_.c fileio.c;*
X$ ren util_.c util.c;*
X$ link zipnote, zipfile_, zipup_, fileio_, globals, sys$input:/opt
Xsys$share:vaxcrtl.exe/shareable
X$ link zipsplit, zipfile_, zipup_, fileio_, globals, sys$input:/opt
Xsys$share:vaxcrtl.exe/shareable
X$ !
X$ !--------------------------- Ship/UnShip section ----------------------------
X$ !
X$ cc ship
X$ link ship,sys$input:/opt
Xsys$share:vaxcrtl.exe/shareable
X$ !
X$ ! Create a hard link.  (To remove both files, delete the copy FIRST, then
X$ ! the original.  Otherwise, if original deleted first [copy says "no such
X$ ! file"], must use "set file/remove unship.exe;#" to get rid of the copy.
X$ ! Unlike in Unix, deleting the original ALWAYS destroys the data--but not
X$ ! the directory entry of the copy.)  Using a hard link saves disk space, by
X$ ! the way.  Note, however, that copying a hard link copies the data, not
X$ ! just the link.  Therefore, set up the link in the directory in which the
X$ ! executable is to reside, or else rename (move) the executables into the
X$ ! directory.
X$ !
X$ set file/enter=unship.exe ship.exe
X$ !
X$ !----------------------------- Symbols section ------------------------------
X$ !
X$ ! Set up symbols for the various executables.  Edit the example below,
X$ ! changing "pc" to "disk:[directory]" as appropriate, and uncomment
X$ ! (remove the exclamation marks).
X$ !
X$ ! zip        == "$pc:zip.exe"
X$ ! zipnote    == "$pc:zipnote.exe"
X$ ! zipsplit    == "$pc:zipsplit.exe"
X$ ! ship        == "$pc:ship.exe"
X$ ! unship    == "$pc:unship.exe"
X$ !
X$ set noverify
END_OF_FILE
  if test 2470 -ne `wc -c <'makevms.com'`; then
    echo shar: \"'makevms.com'\" unpacked with wrong size!
  fi
  # end of 'makevms.com'
fi
echo shar: End of archive 1 \(of 9\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 9 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...
--
Kent Landfield                   INTERNET: [e-mail]
Sterling Software, IMD           UUCP:     uunet!sparky!kent
Phone:    [phone]         FAX:      [phone]
Please send comp.sources.misc-related mail to [e-mail].