summaryrefslogtreecommitdiff
path: root/Build/source/libs/unzip/unshrink.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/unzip/unshrink.c')
-rw-r--r--Build/source/libs/unzip/unshrink.c301
1 files changed, 301 insertions, 0 deletions
diff --git a/Build/source/libs/unzip/unshrink.c b/Build/source/libs/unzip/unshrink.c
new file mode 100644
index 00000000000..2b7e6f027f0
--- /dev/null
+++ b/Build/source/libs/unzip/unshrink.c
@@ -0,0 +1,301 @@
+/*---------------------------------------------------------------------------
+
+ unshrink.c version 1.21 23 Nov 95
+
+
+ NOTE: This code may or may not infringe on the so-called "Welch
+ patent" owned by Unisys. (From reading the patent, it appears
+ that a pure LZW decompressor is *not* covered, but this claim has
+ not been tested in court, and Unisys is reported to believe other-
+ wise.) It is therefore the responsibility of the user to acquire
+ whatever license(s) may be required for legal use of this code.
+
+ THE INFO-ZIP GROUP DISCLAIMS ALL LIABILITY FOR USE OF THIS CODE
+ IN VIOLATION OF APPLICABLE PATENT LAW.
+
+
+ Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
+ up to 13 bits; in addition, there is provision for partial clearing of
+ leaf nodes. PKWARE uses the special code 256 (decimal) to indicate a
+ change in code size or a partial clear of the code tree: 256,1 for the
+ former and 256,2 for the latter. [Note that partial clearing can "orphan"
+ nodes: the parent-to-be can be cleared before its new child is added,
+ but the child is added anyway (as an orphan, as though the parent still
+ existed). When the tree fills up to the point where the parent node is
+ reused, the orphan is effectively "adopted." Versions prior to 1.05 were
+ affected more due to greater use of pointers (to children and siblings
+ as well as parents).]
+
+ This replacement version of unshrink.c was written from scratch. It is
+ based only on the algorithms described in Mark Nelson's _The Data Compres-
+ sion Book_ and in Terry Welch's original paper in the June 1984 issue of
+ IEEE _Computer_; no existing source code, including any in Nelson's book,
+ was used.
+
+ Memory requirements have been reduced in this version and are now no more
+ than the original Sam Smith code. This is still larger than any of the
+ other algorithms: at a minimum, 8K+8K+16K (stack+values+parents) assuming
+ 16-bit short ints, and this does not even include the output buffer (the
+ other algorithms leave the uncompressed data in the work area, typically
+ called slide[]). For machines with a 64KB data space this is a problem,
+ particularly when text conversion is required and line endings have more
+ than one character. UnZip's solution is to use two roughly equal halves
+ of outbuf for the ASCII conversion in such a case; the "unshrink" argument
+ to flush() signals that this is the case.
+
+ For large-memory machines, a second outbuf is allocated for translations,
+ but only if unshrinking and only if translations are required.
+
+ | binary mode | text mode
+ ---------------------------------------------------
+ big mem | big outbuf | big outbuf + big outbuf2 <- malloc'd here
+ small mem | small outbuf | half + half small outbuf
+
+ Copyright 1994, 1995 Greg Roelofs. See the accompanying file "COPYING"
+ in UnZip 5.20 (or later) source or binary distributions.
+
+ ---------------------------------------------------------------------------*/
+
+
+#define UNZIP_INTERNAL
+#include "unzip.h" /* defines LZW_CLEAN by default */
+
+
+#ifndef LZW_CLEAN
+
+static void partial_clear OF((__GPRO));
+
+#ifdef DEBUG
+# define OUTDBG(c) \
+ if ((c)<32 || (c)>=127) fprintf(stderr,"\\x%02x",(c)); else putc((c),stderr);
+#else
+# define OUTDBG(c)
+#endif
+
+/* HSIZE is defined as 2^13 (8192) in unzip.h */
+#define BOGUSCODE 256
+#define FLAG_BITS parent /* upper bits of parent[] used as flag bits */
+#define CODE_MASK (HSIZE - 1) /* 0x1fff (lower bits are parent's index) */
+#define FREE_CODE HSIZE /* 0x2000 (code is unused or was cleared) */
+#define HAS_CHILD (HSIZE << 1) /* 0x4000 (code has a child--do not clear) */
+
+#define parent G.area.shrink.Parent
+#define Value G.area.shrink.value /* "value" conflicts with Pyramid ioctl.h */
+#define stack G.area.shrink.Stack
+
+
+/***********************/
+/* Function unshrink() */
+/***********************/
+
+int unshrink(__G)
+ __GDEF
+{
+ int offset = (HSIZE - 1);
+ uch *stacktop = stack + offset;
+ register uch *newstr;
+ int codesize=9, len, KwKwK, error;
+ shrint code, oldcode, freecode, curcode;
+ shrint lastfreecode;
+ unsigned int outbufsiz;
+#if (defined(DLL) && !defined(NO_SLIDE_REDIR))
+ /* Normally realbuf and outbuf will be the same. However, if the data
+ * are redirected to a large memory buffer, realbuf will point to the
+ * new location while outbuf will remain pointing to the malloc'd
+ * memory buffer. */
+ uch *realbuf = G.outbuf;
+#else
+# define realbuf G.outbuf
+#endif
+
+
+/*---------------------------------------------------------------------------
+ Initialize various variables.
+ ---------------------------------------------------------------------------*/
+
+ lastfreecode = BOGUSCODE;
+
+#ifndef VMS /* VMS uses its own buffer scheme for textmode flush(). */
+#ifndef SMALL_MEM
+ /* non-memory-limited machines: allocate second (large) buffer for
+ * textmode conversion in flush(), but only if needed */
+ if (G.pInfo->textmode && !G.outbuf2 &&
+ (G.outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
+ return PK_MEM3;
+#endif
+#endif /* !VMS */
+
+ for (code = 0; code < BOGUSCODE; ++code) {
+ Value[code] = (uch)code;
+ parent[code] = BOGUSCODE;
+ }
+ for (code = BOGUSCODE+1; code < HSIZE; ++code)
+ parent[code] = FREE_CODE;
+
+#if (defined(DLL) && !defined(NO_SLIDE_REDIR))
+ if (G.redirect_slide) { /* use normal outbuf unless we're a DLL routine */
+ realbuf = G.redirect_buffer;
+ outbufsiz = G.redirect_size;
+ } else
+#endif
+#ifdef DLL
+ if (G.pInfo->textmode && !G.redirect_data)
+#else
+ if (G.pInfo->textmode)
+#endif
+ outbufsiz = RAWBUFSIZ;
+ else
+ outbufsiz = OUTBUFSIZ;
+ G.outptr = realbuf;
+ G.outcnt = 0L;
+
+/*---------------------------------------------------------------------------
+ Get and output first code, then loop over remaining ones.
+ ---------------------------------------------------------------------------*/
+
+ READBITS(codesize, oldcode)
+ if (!G.zipeof) {
+ *G.outptr++ = (uch)oldcode;
+ OUTDBG((uch)oldcode)
+ ++G.outcnt;
+ }
+
+ do {
+ READBITS(codesize, code)
+ if (G.zipeof)
+ break;
+ if (code == BOGUSCODE) { /* possible to have consecutive escapes? */
+ READBITS(codesize, code)
+ if (code == 1) {
+ ++codesize;
+ Trace((stderr, " (codesize now %d bits)\n", codesize));
+ } else if (code == 2) {
+ Trace((stderr, " (partial clear code)\n"));
+ partial_clear(__G); /* clear leafs (nodes with no children) */
+ Trace((stderr, " (done with partial clear)\n"));
+ lastfreecode = BOGUSCODE; /* reset start of free-node search */
+ }
+ continue;
+ }
+
+ /*-----------------------------------------------------------------------
+ Translate code: traverse tree from leaf back to root.
+ -----------------------------------------------------------------------*/
+
+ newstr = stacktop;
+ curcode = code;
+
+ if (parent[curcode] == FREE_CODE) {
+ /* or (FLAG_BITS[curcode] & FREE_CODE)? */
+ KwKwK = TRUE;
+ Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
+ oldcode));
+ --newstr; /* last character will be same as first character */
+ curcode = oldcode;
+ } else
+ KwKwK = FALSE;
+
+ do {
+ *newstr-- = Value[curcode];
+ curcode = (shrint)(parent[curcode] & CODE_MASK);
+ } while (curcode != BOGUSCODE);
+
+ len = (int)(stacktop - newstr++);
+ if (KwKwK)
+ *stacktop = *newstr;
+
+ /*-----------------------------------------------------------------------
+ Write expanded string in reverse order to output buffer.
+ -----------------------------------------------------------------------*/
+
+ Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
+ oldcode, (int)(*newstr), (*newstr<32 || *newstr>=127)? ' ':*newstr));
+
+ {
+ register uch *p;
+
+ for (p = newstr; p < newstr+len; ++p) {
+ *G.outptr++ = *p;
+ OUTDBG(*p)
+ if (++G.outcnt == outbufsiz) {
+ Trace((stderr, "doing flush(), outcnt = %lu\n", G.outcnt));
+ if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0)
+ fprintf(stderr, "unshrink: flush() error (%d)\n",
+ error);
+ Trace((stderr, "done with flush()\n"));
+ G.outptr = realbuf;
+ G.outcnt = 0L;
+ }
+ }
+ }
+
+ /*-----------------------------------------------------------------------
+ Add new leaf (first character of newstr) to tree as child of oldcode.
+ -----------------------------------------------------------------------*/
+
+ /* search for freecode */
+ freecode = (shrint)(lastfreecode + 1);
+ /* add if-test before loop for speed? */
+ while (parent[freecode] != FREE_CODE)
+ ++freecode;
+ lastfreecode = freecode;
+ Trace((stderr, "]; newcode %d\n", freecode));
+
+ Value[freecode] = *newstr;
+ parent[freecode] = oldcode;
+ oldcode = code;
+
+ } while (!G.zipeof);
+
+/*---------------------------------------------------------------------------
+ Flush any remaining data and return to sender...
+ ---------------------------------------------------------------------------*/
+
+ if (G.outcnt > 0L) {
+ Trace((stderr, "doing final flush(), outcnt = %lu\n", G.outcnt));
+ if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0)
+ fprintf(stderr, "unshrink: flush() error (%d)\n", error);
+ Trace((stderr, "done with flush()\n"));
+ }
+
+ return PK_OK;
+
+} /* end function unshrink() */
+
+
+
+
+
+/****************************/
+/* Function partial_clear() */ /* no longer recursive... */
+/****************************/
+
+static void partial_clear(__G)
+ __GDEF
+{
+ register shrint code;
+
+ /* clear all nodes which have no children (i.e., leaf nodes only) */
+
+ /* first loop: mark each parent as such */
+ for (code = BOGUSCODE+1; code < HSIZE; ++code) {
+ register shrint cparent = (shrint)(parent[code] & CODE_MASK);
+
+ if (cparent > BOGUSCODE && cparent != FREE_CODE)
+ FLAG_BITS[cparent] |= HAS_CHILD; /* set parent's child-bit */
+ }
+
+ /* second loop: clear all nodes *not* marked as parents; reset flag bits */
+ for (code = BOGUSCODE+1; code < HSIZE; ++code) {
+ if (FLAG_BITS[code] & HAS_CHILD) /* just clear child-bit */
+ FLAG_BITS[code] &= ~HAS_CHILD;
+ else { /* leaf: lose it */
+ Trace((stderr, "%d\n", code));
+ parent[code] = FREE_CODE;
+ }
+ }
+
+ return;
+}
+
+#endif /* !LZW_CLEAN */