src/bin/unzip/unshrink.c

   1 /*
   2   Copyright (c) 1990-2001 Info-ZIP.  All rights reserved.
   3
   4   See the accompanying file LICENSE, version 2000-Apr-09 or later
   5   (the contents of which are also included in unzip.h) for terms of use.
   6   If, for some reason, all these files are missing, the Info-ZIP license
   7   also may be found at:  ftp://ftp.info-zip.org/pub/infozip/license.html
   8 */
   9 /*---------------------------------------------------------------------------
  10
  11   unshrink.c                     version 1.21                     23 Nov 95
  12
  13
  14        NOTE:  This code may or may not infringe on the so-called "Welch
  15        patent" owned by Unisys.  (From reading the patent, it appears
  16        that a pure LZW decompressor is *not* covered, but this claim has
  17        not been tested in court, and Unisys is reported to believe other-
  18        wise.)  It is therefore the responsibility of the user to acquire
  19        whatever license(s) may be required for legal use of this code.
  20
  21        THE INFO-ZIP GROUP DISCLAIMS ALL LIABILITY FOR USE OF THIS CODE
  22        IN VIOLATION OF APPLICABLE PATENT LAW.
  23
  24
  25   Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
  26   up to 13 bits; in addition, there is provision for partial clearing of
  27   leaf nodes.  PKWARE uses the special code 256 (decimal) to indicate a
  28   change in code size or a partial clear of the code tree:  256,1 for the
  29   former and 256,2 for the latter.  [Note that partial clearing can "orphan"
  30   nodes:  the parent-to-be can be cleared before its new child is added,
  31   but the child is added anyway (as an orphan, as though the parent still
  32   existed).  When the tree fills up to the point where the parent node is
  33   reused, the orphan is effectively "adopted."  Versions prior to 1.05 were
  34   affected more due to greater use of pointers (to children and siblings
  35   as well as parents).]
  36
  37   This replacement version of unshrink.c was written from scratch.  It is
  38   based only on the algorithms described in Mark Nelson's _The Data Compres-
  39   sion Book_ and in Terry Welch's original paper in the June 1984 issue of
  40   IEEE _Computer_; no existing source code, including any in Nelson's book,
  41   was used.
  42
  43   Memory requirements have been reduced in this version and are now no more
  44   than the original Sam Smith code.  This is still larger than any of the
  45   other algorithms:  at a minimum, 8K+8K+16K (stack+values+parents) assuming
  46   16-bit short ints, and this does not even include the output buffer (the
  47   other algorithms leave the uncompressed data in the work area, typically
  48   called slide[]).  For machines with a 64KB data space this is a problem,
  49   particularly when text conversion is required and line endings have more
  50   than one character.  UnZip's solution is to use two roughly equal halves
  51   of outbuf for the ASCII conversion in such a case; the "unshrink" argument
  52   to flush() signals that this is the case.
  53
  54   For large-memory machines, a second outbuf is allocated for translations,
  55   but only if unshrinking and only if translations are required.
  56
  57               | binary mode  |        text mode
  58     ---------------------------------------------------
  59     big mem   |  big outbuf  | big outbuf + big outbuf2  <- malloc'd here
  60     small mem | small outbuf | half + half small outbuf
  61
  62   Copyright 1994, 1995 Greg Roelofs.  See the accompanying file "COPYING"
  63   in UnZip 5.20 (or later) source or binary distributions.
  64
  65   ---------------------------------------------------------------------------*/
  66
  67
  68 #define __UNSHRINK_C    /* identifies this source module */
  69 #define UNZIP_INTERNAL
  70 #include "unzip.h"      /* defines LZW_CLEAN by default */
  71
  72
  73 #ifndef LZW_CLEAN
  74
  75 static void  partial_clear  OF((__GPRO));
  76
  77 #ifdef DEBUG
  78 #  define OUTDBG(c) \
  79    if ((c)<32 || (c)>=127) fprintf(stderr,"\\x%02x",(c)); else putc((c),stderr);
  80 #else
  81 #  define OUTDBG(c)
  82 #endif
  83
  84 /* HSIZE is defined as 2^13 (8192) in unzip.h */
  85 #define BOGUSCODE  256
  86 #define FLAG_BITS  parent        /* upper bits of parent[] used as flag bits */
  87 #define CODE_MASK  (HSIZE - 1)   /* 0x1fff (lower bits are parent's index) */
  88 #define FREE_CODE  HSIZE         /* 0x2000 (code is unused or was cleared) */
  89 #define HAS_CHILD  (HSIZE << 1)  /* 0x4000 (code has a child--do not clear) */
  90
  91 #define parent G.area.shrink.Parent
  92 #define Value  G.area.shrink.value /* "value" conflicts with Pyramid ioctl.h */
  93 #define stack  G.area.shrink.Stack
  94
  95
  96 /***********************/
  97 /* Function unshrink() */
  98 /***********************/
  99
 100 int unshrink(__G)
 101      __GDEF
 102 {
 103     int offset = (HSIZE - 1);
 104     uch *stacktop = stack + offset;
 105     register uch *newstr;
 106     int codesize=9, len, KwKwK, error;
 107     shrint code, oldcode, freecode, curcode;
 108     shrint lastfreecode;
 109     unsigned int outbufsiz;
 110 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
 111     /* Normally realbuf and outbuf will be the same.  However, if the data
 112      * are redirected to a large memory buffer, realbuf will point to the
 113      * new location while outbuf will remain pointing to the malloc'd
 114      * memory buffer. */
 115     uch *realbuf = G.outbuf;
 116 #else
 117 #   define realbuf G.outbuf
 118 #endif
 119
 120
 121 /*---------------------------------------------------------------------------
 122     Initialize various variables.
 123   ---------------------------------------------------------------------------*/
 124
 125     lastfreecode = BOGUSCODE;
 126
 127 #ifndef VMS     /* VMS uses its own buffer scheme for textmode flush(). */
 128 #ifndef SMALL_MEM
 129     /* non-memory-limited machines:  allocate second (large) buffer for
 130      * textmode conversion in flush(), but only if needed */
 131     if (G.pInfo->textmode && !G.outbuf2 &&
 132         (G.outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
 133         return PK_MEM3;
 134 #endif
 135 #endif /* !VMS */
 136
 137     for (code = 0;  code < BOGUSCODE;  ++code) {
 138         Value[code] = (uch)code;
 139         parent[code] = BOGUSCODE;
 140     }
 141     for (code = BOGUSCODE+1;  code < HSIZE;  ++code)
 142         parent[code] = FREE_CODE;
 143
 144 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
 145     if (G.redirect_slide) { /* use normal outbuf unless we're a DLL routine */
 146         realbuf = G.redirect_buffer;
 147         outbufsiz = (unsigned)G.redirect_size;
 148     } else
 149 #endif
 150 #ifdef DLL
 151     if (G.pInfo->textmode && !G.redirect_data)
 152 #else
 153     if (G.pInfo->textmode)
 154 #endif
 155         outbufsiz = RAWBUFSIZ;
 156     else
 157         outbufsiz = OUTBUFSIZ;
 158     G.outptr = realbuf;
 159     G.outcnt = 0L;
 160
 161 /*---------------------------------------------------------------------------
 162     Get and output first code, then loop over remaining ones.
 163   ---------------------------------------------------------------------------*/
 164
 165     READBITS(codesize, oldcode)
 166     if (!G.zipeof) {
 167         *G.outptr++ = (uch)oldcode;
 168         OUTDBG((uch)oldcode)
 169         ++G.outcnt;
 170     }
 171
 172     do {
 173         READBITS(codesize, code)
 174         if (G.zipeof)
 175             break;
 176         if (code == BOGUSCODE) {   /* possible to have consecutive escapes? */
 177             READBITS(codesize, code)
 178             if (code == 1) {
 179                 ++codesize;
 180                 Trace((stderr, " (codesize now %d bits)\n", codesize));
 181             } else if (code == 2) {
 182                 Trace((stderr, " (partial clear code)\n"));
 183                 partial_clear(__G);   /* clear leafs (nodes with no children) */
 184                 Trace((stderr, " (done with partial clear)\n"));
 185                 lastfreecode = BOGUSCODE;  /* reset start of free-node search */
 186             }
 187             continue;
 188         }
 189
 190     /*-----------------------------------------------------------------------
 191         Translate code:  traverse tree from leaf back to root.
 192       -----------------------------------------------------------------------*/
 193
 194         newstr = stacktop;
 195         curcode = code;
 196
 197         if (parent[curcode] == FREE_CODE) {
 198             /* or (FLAG_BITS[curcode] & FREE_CODE)? */
 199             KwKwK = TRUE;
 200             Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
 201               oldcode));
 202             --newstr;   /* last character will be same as first character */
 203             curcode = oldcode;
 204         } else
 205             KwKwK = FALSE;
 206
 207         do {
 208             *newstr-- = Value[curcode];
 209             curcode = (shrint)(parent[curcode] & CODE_MASK);
 210         } while (curcode != BOGUSCODE);
 211
 212         len = (int)(stacktop - newstr++);
 213         if (KwKwK)
 214             *stacktop = *newstr;
 215
 216     /*-----------------------------------------------------------------------
 217         Write expanded string in reverse order to output buffer.
 218       -----------------------------------------------------------------------*/
 219
 220         Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
 221           oldcode, (int)(*newstr), (*newstr<32 || *newstr>=127)? ' ':*newstr));
 222
 223         {
 224             register uch *p;
 225
 226             for (p = newstr;  p < newstr+len;  ++p) {
 227                 *G.outptr++ = *p;
 228                 OUTDBG(*p)
 229                 if (++G.outcnt == outbufsiz) {
 230                     Trace((stderr, "doing flush(), outcnt = %lu\n", G.outcnt));
 231                     if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0) {
 232                         Trace((stderr, "unshrink:  flush() error (%d)\n",
 233                           error));
 234                         return error;
 235                     }
 236                     G.outptr = realbuf;
 237                     G.outcnt = 0L;
 238                     Trace((stderr, "done with flush()\n"));
 239                 }
 240             }
 241         }
 242
 243     /*-----------------------------------------------------------------------
 244         Add new leaf (first character of newstr) to tree as child of oldcode.
 245       -----------------------------------------------------------------------*/
 246
 247         /* search for freecode */
 248         freecode = (shrint)(lastfreecode + 1);
 249         /* add if-test before loop for speed? */
 250         while (parent[freecode] != FREE_CODE)
 251             ++freecode;
 252         lastfreecode = freecode;
 253         Trace((stderr, "]; newcode %d\n", freecode));
 254
 255         Value[freecode] = *newstr;
 256         parent[freecode] = oldcode;
 257         oldcode = code;
 258
 259     } while (!G.zipeof);
 260
 261 /*---------------------------------------------------------------------------
 262     Flush any remaining data and return to sender...
 263   ---------------------------------------------------------------------------*/
 264
 265     if (G.outcnt > 0L) {
 266         Trace((stderr, "doing final flush(), outcnt = %lu\n", G.outcnt));
 267         if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0) {
 268             Trace((stderr, "unshrink:  flush() error (%d)\n", error));
 269             return error;
 270         }
 271         Trace((stderr, "done with flush()\n"));
 272     }
 273
 274     return PK_OK;
 275
 276 } /* end function unshrink() */
 277
 278
 279
 280
 281
 282 /****************************/
 283 /* Function partial_clear() */      /* no longer recursive... */
 284 /****************************/
 285
 286 static void partial_clear(__G)
 287      __GDEF
 288 {
 289     register shrint code;
 290
 291     /* clear all nodes which have no children (i.e., leaf nodes only) */
 292
 293     /* first loop:  mark each parent as such */
 294     for (code = BOGUSCODE+1;  code < HSIZE;  ++code) {
 295         register shrint cparent = (shrint)(parent[code] & CODE_MASK);
 296
 297         if (cparent > BOGUSCODE && cparent != FREE_CODE)
 298             FLAG_BITS[cparent] |= HAS_CHILD;   /* set parent's child-bit */
 299     }
 300
 301     /* second loop:  clear all nodes *not* marked as parents; reset flag bits */
 302     for (code = BOGUSCODE+1;  code < HSIZE;  ++code) {
 303         if (FLAG_BITS[code] & HAS_CHILD)    /* just clear child-bit */
 304             FLAG_BITS[code] &= ~HAS_CHILD;
 305         else {                              /* leaf:  lose it */
 306             Trace((stderr, "%d\n", code));
 307             parent[code] = FREE_CODE;
 308         }
 309     }
 310
 311     return;
 312 }
 313
 314 #endif /* !LZW_CLEAN */