home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / unzip512.zip / unshrink.c < prev    next >
C/C++ Source or Header  |  1994-08-15  |  18KB  |  546 lines
  1. #include "unzip.h"
  2.  
  3. #ifdef NEW_UNSHRINK
  4.  
  5. /*---------------------------------------------------------------------------
  6.  
  7.   unshrink.c                     version 0.94                     26 Apr 94
  8.  
  9.   Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
  10.   up to 13 bits; in addition, there is provision for partial clearing of
  11.   leaf nodes.  PKWARE uses the special code 256 (decimal) to indicate a
  12.   change in code size or a partial clear of the code tree:  256,1 for the
  13.   former and 256,2 for the latter.  See the notes in the code below about
  14.   orphaned nodes after partial clearing.
  15.  
  16.   This replacement version of unshrink.c was written from scratch.  It is
  17.   based only on the algorithms described in Mark Nelson's _The Data Compres-
  18.   sion Book_ and in Terry Welch's original paper in the June 1984 issue of
  19.   IEEE _Computer_; no existing source code, including any in Nelson's book,
  20.   was used.
  21.  
  22.   Memory requirements are fairly large.  While the NODE struct could be mod-
  23.   ified to fit in a single 64KB segment (as a "far" data structure), for now
  24.   it is assumed that a flat, 32-bit address space is available.  outbuf2 is
  25.   always malloc'd, and flush() is always called with unshrink == FALSE.
  26.  
  27.   Copyright (C) 1994 Greg Roelofs.  See the accompanying file "COPYING" in
  28.   the UnZip 5.11 (or later) source distribution.
  29.  
  30.   ---------------------------------------------------------------------------*/
  31.  
  32.  
  33. /* #include "unzip.h" */
  34.  
  35. #ifdef DEBUG
  36. #  define OUTDBG(c)  if ((c)=='\n') {PUTC('^',stderr); PUTC('J',stderr);}\
  37.                      else PUTC((c),stderr);
  38. #else
  39. #  define OUTDBG(c)
  40. #endif
  41.  
  42. typedef struct leaf {
  43.     struct leaf *parent;
  44.     struct leaf *next_sibling;
  45.     struct leaf *first_child;
  46.     uch value;
  47. } NODE;
  48.  
  49. static void  partial_clear  __((NODE *cursib));
  50.  
  51. static NODE *node, *bogusnode, *lastfreenode;
  52.  
  53.  
  54. int unshrink()
  55. {
  56. #ifdef MACOS
  57.     static uch *stacktop = NULL;
  58. #else
  59.     static uch *stacktop = stack + 8192 - 1;
  60. #endif
  61.     register uch *newstr;
  62.     int codesize=9, code, oldcode=0, len, KwKwK;
  63.     unsigned int outbufsiz;
  64.     NODE *freenode, *curnode, *lastnode=node, *oldnode;
  65.  
  66.  
  67. /*---------------------------------------------------------------------------
  68.     Initialize various variables.
  69.   ---------------------------------------------------------------------------*/
  70.  
  71. #ifdef MACOS
  72.     if (stacktop == NULL) stacktop = stack + 8192 - 1;
  73. #endif
  74.  
  75.     if ((node = (NODE *)malloc(8192*sizeof(NODE))) == (NODE *)NULL)
  76.         return PK_MEM3;
  77.     bogusnode = node + 256;
  78.     lastfreenode = node + 256;
  79.  
  80. #ifndef SMALL_MEM   /* always true, at least for now */
  81.     /* non-memory-limited machines:  allocate second (large) buffer for
  82.      * textmode conversion in flush(), but only if needed */
  83.     if (pInfo->textmode && !outbuf2 &&
  84.         (outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
  85.     {
  86.         free(node);
  87.         return PK_MEM3;
  88.     }
  89. #endif
  90.  
  91.     /* this stuff was an attempt to debug compiler errors(?) when had
  92.      * node[8192] in union work area...no clues what was wrong (SGI worked)
  93.     Trace((stderr, "\nsizeof(NODE) = %d\n", sizeof(NODE)));
  94.     Trace((stderr, "sizeof(node) = %d\n", sizeof(node)));
  95.     Trace((stderr, "sizeof(area) = %d\n", sizeof(area)));
  96.     Trace((stderr, "address of node[0] = %d\n", (int)&node[0]));
  97.     Trace((stderr, "address of node[6945] = %d\n", (int)&node[6945]));
  98.      */
  99.  
  100.     for (code = 0;  code < 256;  ++code) {
  101.         node[code].value = code;
  102.         node[code].parent = bogusnode;
  103.         node[code].next_sibling = &node[code+1];
  104.         node[code].first_child = (NODE *)NULL;
  105.     }
  106.     node[255].next_sibling = (NODE *)NULL;
  107.     for (code = 257;  code < 8192;  ++code)
  108.         node[code].parent = node[code].next_sibling = (NODE *)NULL;
  109.  
  110.     outptr = outbuf;
  111.     outcnt = 0L;
  112.     if (pInfo->textmode)
  113.         outbufsiz = RAWBUFSIZ;
  114.     else
  115.         outbufsiz = OUTBUFSIZ;
  116.  
  117. /*---------------------------------------------------------------------------
  118.     Get and output first code, then loop over remaining ones.
  119.   ---------------------------------------------------------------------------*/
  120.  
  121.     READBITS(codesize, oldcode)
  122.     if (!zipeof) {
  123.         *outptr++ = (uch)oldcode;
  124.         OUTDBG((uch)oldcode)
  125.         if (++outcnt == outbufsiz) {
  126.             flush(outbuf, outcnt, FALSE);
  127.             outptr = outbuf;
  128.             outcnt = 0L;
  129.         }
  130.     }
  131.  
  132.     do {
  133.         READBITS(codesize, code)
  134.         if (zipeof)
  135.             break;
  136.         if (code == 256) {   /* GRR:  possible to have consecutive escapes? */
  137.             READBITS(codesize, code)
  138.             if (code == 1) {
  139.                 ++codesize;
  140.                 Trace((stderr, " (codesize now %d bits)\n", codesize));
  141.             } else if (code == 2) {
  142.                 Trace((stderr, " (partial clear code)\n"));
  143. #ifdef DEBUG
  144.                 fprintf(stderr, "   should clear:\n");
  145.                 for (curnode = node+257;  curnode < node+8192;  ++curnode)
  146.                     if (!curnode->first_child)
  147.                         fprintf(stderr, "%d\n", curnode-node);
  148.                 fprintf(stderr, "   did clear:\n");
  149. #endif
  150.                 partial_clear(node);       /* recursive clear of leafs */
  151.                 lastfreenode = bogusnode;  /* reset start of free-node search */
  152.             }
  153.             continue;
  154.         }
  155.  
  156.     /*-----------------------------------------------------------------------
  157.         Translate code:  traverse tree from leaf back to root.
  158.       -----------------------------------------------------------------------*/
  159.  
  160.         curnode = &node[code];
  161.         newstr = stacktop;
  162.  
  163.         if (curnode->parent)
  164.             KwKwK = FALSE;
  165.         else {
  166.             KwKwK = TRUE;
  167.             Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
  168.               oldcode));
  169.             --newstr;   /* last character will be same as first character */
  170.             curnode = &node[oldcode];
  171.         }
  172.  
  173.         do {
  174.             *newstr-- = curnode->value;
  175.             curnode = curnode->parent;
  176.         } while (curnode != bogusnode);
  177.  
  178.         len = stacktop - newstr++;
  179.         if (KwKwK)
  180.             *stacktop = *newstr;
  181.  
  182.     /*-----------------------------------------------------------------------
  183.         Write expanded string in reverse order to output buffer.
  184.       -----------------------------------------------------------------------*/
  185.  
  186.         Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
  187.           oldcode, (int)(*newstr), *newstr));
  188.         {
  189.             register uch *p;
  190.  
  191.             for (p = newstr;  p < newstr+len;  ++p) {
  192.                 *outptr++ = *p;
  193.                 OUTDBG(*p)
  194.                 if (++outcnt == outbufsiz) {
  195.                     flush(outbuf, outcnt, FALSE);
  196.                     outptr = outbuf;
  197.                     outcnt = 0L;
  198.                 }
  199.             }
  200.         }
  201.  
  202.     /*-----------------------------------------------------------------------
  203.         Add new leaf (first character of newstr) to tree as child of oldcode.
  204.       -----------------------------------------------------------------------*/
  205.  
  206.         /* search for freenode */
  207.         freenode = lastfreenode + 1;
  208.         while (freenode->parent)       /* add if-test before loop for speed? */
  209.             ++freenode;
  210.         lastfreenode = freenode;
  211.         Trace((stderr, "]; newcode %d\n", freenode-node));
  212.  
  213.         oldnode = &node[oldcode];
  214.         if (!oldnode->first_child) {   /* no children yet:  add first one */
  215.             if (!oldnode->parent) {
  216.                 /*
  217.                  * oldnode is itself a free node:  the only way this can happen
  218.                  * is if a partial clear occurred immediately after oldcode was
  219.                  * received and therefore immediately before this step (adding
  220.                  * freenode).  This is subtle:  even though the parent no longer
  221.                  * exists, it is treated as if it does, and pointers are set as
  222.                  * usual.  Thus freenode is an orphan, *but only until the tree
  223.                  * fills up to the point where oldnode is reused*.  At that
  224.                  * point the reborn oldnode "adopts" the orphaned node.  Such
  225.                  * wacky guys at PKWARE...
  226.                  *
  227.                  * To mark this, we set oldnode->next_sibling to point at the
  228.                  * bogus node (256) and then check for this in the freenode sec-
  229.                  * tion just below.
  230.                  */
  231.                 Trace((stderr, "  [%d's parent (%d) was just cleared]\n",
  232.                   freenode-node, oldcode));
  233.                 oldnode->next_sibling = bogusnode;
  234.             }
  235.             oldnode->first_child = freenode;
  236.         } else {
  237.             curnode = oldnode->first_child;
  238.             while (curnode) {          /* find last child in sibling chain */
  239.                 lastnode = curnode;
  240.                 curnode = curnode->next_sibling;
  241.             }
  242.             lastnode->next_sibling = freenode;
  243.         }
  244.         freenode->value = *newstr;
  245.         freenode->parent = oldnode;
  246.         if (freenode->next_sibling != bogusnode)  /* no adoptions today... */
  247.             freenode->first_child = (NODE *)NULL;
  248.         freenode->next_sibling = (NODE *)NULL;
  249.  
  250.         oldcode = code;
  251.     } while (!zipeof);
  252.  
  253. /*---------------------------------------------------------------------------
  254.     Flush any remaining data, free malloc'd space and return to sender...
  255.   ---------------------------------------------------------------------------*/
  256.  
  257.     if (outcnt > 0L)
  258.         flush(outbuf, outcnt, FALSE);
  259.  
  260.     free(node);
  261.     return PK_OK;
  262.  
  263. } /* end function unshrink() */
  264.  
  265.  
  266.  
  267.  
  268.  
  269. static void partial_clear(cursib)   /* like, totally recursive, eh? */
  270.     NODE *cursib;
  271. {
  272.     NODE *lastsib=(NODE *)NULL;
  273.  
  274.     /* Loop over siblings, removing any without children; recurse on those
  275.      * which do have children.  This hits even the orphans because they're
  276.      * always adopted (parent node is reused) before tree becomes full and
  277.      * needs clearing.
  278.      */
  279.     do {
  280.         if (cursib->first_child) {
  281.             partial_clear(cursib->first_child);
  282.             lastsib = cursib;
  283.         } else if ((cursib - node) > 256) {  /* no children (leaf):  clear it */
  284.             Trace((stderr, "%d\n", cursib-node));
  285.             if (!lastsib)
  286.                 cursib->parent->first_child = cursib->next_sibling;
  287.             else
  288.                 lastsib->next_sibling = cursib->next_sibling;
  289.             cursib->parent = (NODE *)NULL;
  290.         }
  291.         cursib = cursib->next_sibling;
  292.     } while (cursib);
  293.     return;
  294. }
  295.  
  296.  
  297.  
  298. #else /* !NEW_UNSHRINK */
  299.  
  300.  
  301.  
  302. /*---------------------------------------------------------------------------
  303.  
  304.   unshrink.c
  305.  
  306.   Shrinking is a dynamic Lempel-Ziv-Welch compression algorithm with partial
  307.   clearing.  Sadly, it uses more memory than any of the other algorithms (at
  308.   a minimum, 8K+8K+16K, assuming 16-bit short ints), and this does not even
  309.   include the output buffer (the other algorithms leave the uncompressed data
  310.   in the work area, typically called slide[]).  For machines with a 64KB data
  311.   space, this is a problem, particularly when text conversion is required and
  312.   line endings have more than one character.  UnZip's solution is to use two
  313.   roughly equal halves of outbuf for the ASCII conversion in such a case; the
  314.   "unshrink" argument to flush() signals that this is the case.
  315.  
  316.   For large-memory machines, a second outbuf is allocated for translations,
  317.   but only if unshrinking and only if translations are required.
  318.  
  319.               | binary mode  |        text mode
  320.     ---------------------------------------------------
  321.     big mem   |  big outbuf  | big outbuf + big outbuf2  <- malloc'd here
  322.     small mem | small outbuf | half + half small outbuf
  323.  
  324.   This version contains code which is copyright (C) 1989 Samuel H. Smith.
  325.   See the accompanying file "COPYING" in the UnZip 5.11 (or later) source
  326.   distribution.
  327.  
  328.   ---------------------------------------------------------------------------*/
  329.  
  330.  
  331. /* #include "unzip.h" */
  332.  
  333. /*      MAX_BITS   13   (in unzip.h; defines size of global work area)  */
  334. #define INIT_BITS  9
  335. #define FIRST_ENT  257
  336. #define CLEAR      256
  337.  
  338. #define OUTB(c) {\
  339.     *outptr++=(uch)(c);\
  340.     if (++outcnt==outbufsiz) {\
  341.         flush(outbuf,outcnt,TRUE);\
  342.         outcnt=0L;\
  343.         outptr=outbuf;\
  344.     }\
  345. }
  346.  
  347. static void partial_clear __((void));
  348.  
  349. int codesize, maxcode, maxcodemax, free_ent;
  350.  
  351.  
  352.  
  353.  
  354. /*************************/
  355. /*  Function unshrink()  */
  356. /*************************/
  357.  
  358. int unshrink()   /* return PK-type error code */
  359. {
  360.     register int code;
  361.     register int stackp;
  362.     int finchar;
  363.     int oldcode;
  364.     int incode;
  365.     unsigned int outbufsiz;
  366.  
  367.  
  368.     /* non-memory-limited machines:  allocate second (large) buffer for
  369.      * textmode conversion in flush(), but only if needed */
  370. #ifndef SMALL_MEM
  371.     if (pInfo->textmode && !outbuf2 &&
  372.         (outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
  373.         return PK_MEM3;
  374. #endif
  375.  
  376.     outptr = outbuf;
  377.     outcnt = 0L;
  378.     if (pInfo->textmode)
  379.         outbufsiz = RAWBUFSIZ;
  380.     else
  381.         outbufsiz = OUTBUFSIZ;
  382.  
  383.     /* decompress the file */
  384.     codesize = INIT_BITS;
  385.     maxcode = (1 << codesize) - 1;
  386.     maxcodemax = HSIZE;         /* (1 << MAX_BITS) */
  387.     free_ent = FIRST_ENT;
  388.  
  389.     code = maxcodemax;
  390. /*
  391.     OvdL: -Ox with SCO's 3.2.0 cc gives
  392.     a. warning: overflow in constant multiplication
  393.     b. segmentation fault (core dumped) when using the executable
  394.     for (code = maxcodemax; code > 255; code--)
  395.         prefix_of[code] = -1;
  396.  */
  397.     do {
  398.         prefix_of[code] = -1;
  399.     } while (--code > 255);
  400.  
  401.     for (code = 255; code >= 0; code--) {
  402.         prefix_of[code] = 0;
  403.         suffix_of[code] = (uch)code;
  404.     }
  405.  
  406.     READBITS(codesize,oldcode)  /* ; */
  407.     if (zipeof)
  408.         return PK_COOL;
  409.     finchar = oldcode;
  410.  
  411.     OUTB(finchar)
  412.  
  413.     stackp = HSIZE;
  414.  
  415.     while (!zipeof) {
  416.         READBITS(codesize,code)  /* ; */
  417.         if (zipeof) {
  418.             if (outcnt > 0L)
  419.                 flush(outbuf, outcnt, TRUE);   /* flush last, partial buffer */
  420.             return PK_COOL;
  421.         }
  422.  
  423.         while (code == CLEAR) {
  424.             READBITS(codesize,code)  /* ; */
  425.             switch (code) {
  426.                 case 1:
  427.                     codesize++;
  428.                     if (codesize == MAX_BITS)
  429.                         maxcode = maxcodemax;
  430.                     else
  431.                         maxcode = (1 << codesize) - 1;
  432.                     break;
  433.  
  434.                 case 2:
  435.                     partial_clear();
  436.                     break;
  437.             }
  438.  
  439.             READBITS(codesize,code)  /* ; */
  440.             if (zipeof) {
  441.                 if (outcnt > 0L)
  442.                     flush(outbuf, outcnt, TRUE);   /* partial buffer */
  443.                 return PK_COOL;
  444.             }
  445.         }
  446.  
  447.  
  448.         /* special case for KwKwK string */
  449.         incode = code;
  450.         if (prefix_of[code] == -1) {
  451.             stack[--stackp] = (uch)finchar;
  452.             code = oldcode;
  453.         }
  454.         /* generate output characters in reverse order */
  455.         while (code >= FIRST_ENT) {
  456.             if (prefix_of[code] == -1) {
  457.                 stack[--stackp] = (uch)finchar;
  458.                 code = oldcode;
  459.             } else {
  460.                 stack[--stackp] = suffix_of[code];
  461.                 code = prefix_of[code];
  462.             }
  463.         }
  464.  
  465.         finchar = suffix_of[code];
  466.         stack[--stackp] = (uch)finchar;
  467.  
  468.  
  469.         /* and put them out in forward order, block copy */
  470.         if ((HSIZE - stackp + outcnt) < outbufsiz) {
  471.             /* GRR:  this is not necessarily particularly efficient:
  472.              *       typically output only 2-5 bytes per loop (more
  473.              *       than a dozen rather rare?) */
  474.             memcpy(outptr, &stack[stackp], HSIZE - stackp);
  475.             outptr += HSIZE - stackp;
  476.             outcnt += HSIZE - stackp;
  477.             stackp = HSIZE;
  478.         }
  479.         /* output byte by byte if we can't go by blocks */
  480.         else
  481.             while (stackp < HSIZE)
  482.                 OUTB(stack[stackp++])
  483.  
  484.  
  485.         /* generate new entry */
  486.         code = free_ent;
  487.         if (code < maxcodemax) {
  488.             prefix_of[code] = oldcode;
  489.             suffix_of[code] = (uch)finchar;
  490.  
  491.             do
  492.                 code++;
  493.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  494.  
  495.             free_ent = code;
  496.         }
  497.         /* remember previous code */
  498.         oldcode = incode;
  499.     }
  500.  
  501.     /* never reached? */
  502.     /* flush last, partial buffer */
  503.     if (outcnt > 0L)
  504.         flush(outbuf, outcnt, TRUE);
  505.  
  506.     return PK_OK;
  507.  
  508. } /* end function unshrink() */
  509.  
  510.  
  511.  
  512. /******************************/
  513. /*  Function partial_clear()  */
  514. /******************************/
  515.  
  516. static void partial_clear()
  517. {
  518.     register int pr;
  519.     register int cd;
  520.  
  521.     /* mark all nodes as potentially unused */
  522.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  523.         prefix_of[cd] |= 0x8000;
  524.  
  525.     /* unmark those that are used by other nodes */
  526.     for (cd = FIRST_ENT; cd < free_ent; cd++) {
  527.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  528.         if (pr >= FIRST_ENT)    /* flag node as referenced */
  529.             prefix_of[pr] &= 0x7fff;
  530.     }
  531.  
  532.     /* clear the ones that are still marked */
  533.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  534.         if ((prefix_of[cd] & 0x8000) != 0)
  535.             prefix_of[cd] = -1;
  536.  
  537.     /* find first cleared node as next free_ent */
  538.     cd = FIRST_ENT;
  539.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  540.         cd++;
  541.     free_ent = cd;
  542. }
  543.  
  544.  
  545. #endif /* ?NEW_UNSHRINK */
  546.