aminet/util/arc/unzip/unshrink.c

   1 /*
   2   Copyright (c) 1990-2008 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.22                     19 Mar 2008
  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"
  71
  72
  73 #ifndef LZW_CLEAN
  74
  75 static void  partial_clear  OF((__GPRO__ int lastcodeused));
  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 (resp. unzpriv.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     uch *stacktop = stack + (HSIZE - 1);
 104     register uch *newstr;
 105     uch finalval;
 106     int codesize=9, len, error;
 107     shrint code, oldcode, 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         return PK_OK;
 168
 169     finalval = (uch)oldcode;
 170     OUTDBG(finalval)
 171     *G.outptr++ = finalval;
 172     ++G.outcnt;
 173
 174     while (TRUE) {
 175         READBITS(codesize, code)
 176         if (G.zipeof)
 177             break;
 178         if (code == BOGUSCODE) {   /* possible to have consecutive escapes? */
 179             READBITS(codesize, code)
 180             if (G.zipeof)
 181                 break;
 182             if (code == 1) {
 183                 ++codesize;
 184                 Trace((stderr, " (codesize now %d bits)\n", codesize));
 185                 if (codesize > MAX_BITS) return PK_ERR;
 186             } else if (code == 2) {
 187                 Trace((stderr, " (partial clear code)\n"));
 188                 /* clear leafs (nodes with no children) */
 189                 partial_clear(__G__ lastfreecode);
 190                 Trace((stderr, " (done with partial clear)\n"));
 191                 lastfreecode = BOGUSCODE; /* reset start of free-node search */
 192             }
 193             continue;
 194         }
 195
 196     /*-----------------------------------------------------------------------
 197         Translate code:  traverse tree from leaf back to root.
 198       -----------------------------------------------------------------------*/
 199
 200         newstr = stacktop;
 201         curcode = code;
 202
 203         if (parent[code] == FREE_CODE) {
 204             /* or (FLAG_BITS[code] & FREE_CODE)? */
 205             Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
 206               oldcode));
 207             *newstr-- = finalval;
 208             code = oldcode;
 209         }
 210
 211         while (code != BOGUSCODE) {
 212             if (newstr < stack) {
 213                 /* Bogus compression stream caused buffer underflow! */
 214                 Trace((stderr, "unshrink stack overflow!\n"));
 215                 return PK_ERR;
 216             }
 217             if (parent[code] == FREE_CODE) {
 218                 /* or (FLAG_BITS[code] & FREE_CODE)? */
 219                 Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n",
 220                   code, oldcode));
 221                 *newstr-- = finalval;
 222                 code = oldcode;
 223             } else {
 224                 *newstr-- = Value[code];
 225                 code = (shrint)(parent[code] & CODE_MASK);
 226             }
 227         }
 228
 229         len = (int)(stacktop - newstr++);
 230         finalval = *newstr;
 231
 232     /*-----------------------------------------------------------------------
 233         Write expanded string in reverse order to output buffer.
 234       -----------------------------------------------------------------------*/
 235
 236         Trace((stderr,
 237           "code %4d; oldcode %4d; char %3d (%c); len %d; string [", curcode,
 238           oldcode, (int)(*newstr), (*newstr<32 || *newstr>=127)? ' ':*newstr,
 239           len));
 240
 241         {
 242             register uch *p;
 243
 244             for (p = newstr;  p < newstr+len;  ++p) {
 245                 *G.outptr++ = *p;
 246                 OUTDBG(*p)
 247                 if (++G.outcnt == outbufsiz) {
 248                     Trace((stderr, "doing flush(), outcnt = %lu\n", G.outcnt));
 249                     if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0) {
 250                         Trace((stderr, "unshrink:  flush() error (%d)\n",
 251                           error));
 252                         return error;
 253                     }
 254                     G.outptr = realbuf;
 255                     G.outcnt = 0L;
 256                     Trace((stderr, "done with flush()\n"));
 257                 }
 258             }
 259         }
 260
 261     /*-----------------------------------------------------------------------
 262         Add new leaf (first character of newstr) to tree as child of oldcode.
 263       -----------------------------------------------------------------------*/
 264
 265         /* search for freecode */
 266         code = (shrint)(lastfreecode + 1);
 267         /* add if-test before loop for speed? */
 268         while ((code < HSIZE) && (parent[code] != FREE_CODE))
 269             ++code;
 270         lastfreecode = code;
 271         Trace((stderr, "]; newcode %d\n", code));
 272         if (code >= HSIZE)
 273             /* invalid compressed data caused max-code overflow! */
 274             return PK_ERR;
 275
 276         Value[code] = finalval;
 277         parent[code] = oldcode;
 278         oldcode = curcode;
 279
 280     }
 281
 282 /*---------------------------------------------------------------------------
 283     Flush any remaining data and return to sender...
 284   ---------------------------------------------------------------------------*/
 285
 286     if (G.outcnt > 0L) {
 287         Trace((stderr, "doing final flush(), outcnt = %lu\n", G.outcnt));
 288         if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0) {
 289             Trace((stderr, "unshrink:  flush() error (%d)\n", error));
 290             return error;
 291         }
 292         Trace((stderr, "done with flush()\n"));
 293     }
 294
 295     return PK_OK;
 296
 297 } /* end function unshrink() */
 298
 299
 300
 301
 302
 303 /****************************/
 304 /* Function partial_clear() */      /* no longer recursive... */
 305 /****************************/
 306
 307 static void partial_clear(__G__ lastcodeused)
 308     __GDEF
 309     int lastcodeused;
 310 {
 311     register shrint code;
 312
 313     /* clear all nodes which have no children (i.e., leaf nodes only) */
 314
 315     /* first loop:  mark each parent as such */
 316     for (code = BOGUSCODE+1;  code <= lastcodeused;  ++code) {
 317         register shrint cparent = (shrint)(parent[code] & CODE_MASK);
 318
 319         if (cparent > BOGUSCODE)
 320             FLAG_BITS[cparent] |= HAS_CHILD;   /* set parent's child-bit */
 321     }
 322
 323     /* second loop:  clear all nodes *not* marked as parents; reset flag bits */
 324     for (code = BOGUSCODE+1;  code <= lastcodeused;  ++code) {
 325         if (FLAG_BITS[code] & HAS_CHILD)    /* just clear child-bit */
 326             FLAG_BITS[code] &= ~HAS_CHILD;
 327         else {                              /* leaf:  lose it */
 328             Trace((stderr, "%d\n", code));
 329             parent[code] = FREE_CODE;
 330         }
 331     }
 332
 333     return;
 334 }
 335
 336 #endif /* !LZW_CLEAN */