home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / unzip51.zip / unshrink.c < prev    next >
C/C++ Source or Header  |  1993-10-19  |  7KB  |  239 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unshrink.c
  4.  
  5.   Shrinking is a dynamic Lempel-Ziv-Welch compression algorithm with partial
  6.   clearing.  Sadly, it uses more memory than any of the other algorithms (at
  7.   a minimum, 8K+8K+16K, assuming 16-bit short ints), and this does not even
  8.   include the output buffer (the other algorithms leave the uncompressed data
  9.   in the work area, typically called slide[]).  For machines with a 64KB data
  10.   space, this is a problem, particularly when text conversion is required and
  11.   line endings have more than one character.  UnZip's solution is to use two
  12.   roughly equal halves of outbuf for the ASCII conversion in such a case; the
  13.   "unshrink" argument to flush() signals that this is the case.
  14.  
  15.   For large-memory machines, a second outbuf is allocated for translations,
  16.   but only if unshrinking and only if translations are required.
  17.  
  18.               | binary mode  |        text mode
  19.     ---------------------------------------------------
  20.     big mem   |  big outbuf  | big outbuf + big outbuf2  <- malloc'd here
  21.     small mem | small outbuf | half + half small outbuf
  22.  
  23.  
  24.   ---------------------------------------------------------------------------*/
  25.  
  26.  
  27. #include "unzip.h"
  28.  
  29. /*      MAX_BITS   13   (in unzip.h; defines size of global work area)  */
  30. #define INIT_BITS  9
  31. #define FIRST_ENT  257
  32. #define CLEAR      256
  33.  
  34. #define OUTB(c) {\
  35.     *outptr++=(uch)(c);\
  36.     if (++outcnt==outbufsiz) {\
  37.         flush(outbuf,outcnt,TRUE);\
  38.         outcnt=0L;\
  39.         outptr=outbuf;\
  40.     }\
  41. }
  42.  
  43. static void partial_clear __((void));
  44.  
  45. int codesize, maxcode, maxcodemax, free_ent;
  46.  
  47.  
  48.  
  49.  
  50. /*************************/
  51. /*  Function unshrink()  */
  52. /*************************/
  53.  
  54. int unshrink()   /* return PK-type error code */
  55. {
  56.     register int code;
  57.     register int stackp;
  58.     int finchar;
  59.     int oldcode;
  60.     int incode;
  61.     unsigned int outbufsiz;
  62.  
  63.  
  64.     /* non-memory-limited machines:  allocate second (large) buffer for
  65.      * textmode conversion in flush(), but only if needed */
  66. #ifndef SMALL_MEM
  67.     if (pInfo->textmode && !outbuf2 &&
  68.         (outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == NULL)
  69.         return PK_MEM2;
  70. #endif
  71.  
  72.     outptr = outbuf;
  73.     outcnt = 0L;
  74.     if (pInfo->textmode)
  75.         outbufsiz = RAWBUFSIZ;
  76.     else
  77.         outbufsiz = OUTBUFSIZ;
  78.  
  79.     /* decompress the file */
  80.     codesize = INIT_BITS;
  81.     maxcode = (1 << codesize) - 1;
  82.     maxcodemax = HSIZE;         /* (1 << MAX_BITS) */
  83.     free_ent = FIRST_ENT;
  84.  
  85.     code = maxcodemax;
  86. /*
  87.     OvdL: -Ox with SCO's 3.2.0 cc gives
  88.     a. warning: overflow in constant multiplication
  89.     b. segmentation fault (core dumped) when using the executable
  90.     for (code = maxcodemax; code > 255; code--)
  91.         prefix_of[code] = -1;
  92.  */
  93.     do {
  94.         prefix_of[code] = -1;
  95.     } while (--code > 255);
  96.  
  97.     for (code = 255; code >= 0; code--) {
  98.         prefix_of[code] = 0;
  99.         suffix_of[code] = (uch)code;
  100.     }
  101.  
  102.     READBITS(codesize,oldcode)  /* ; */
  103.     if (zipeof)
  104.         return PK_COOL;
  105.     finchar = oldcode;
  106.  
  107.     OUTB(finchar)
  108.  
  109.     stackp = HSIZE;
  110.  
  111.     while (!zipeof) {
  112.         READBITS(codesize,code)  /* ; */
  113.         if (zipeof) {
  114.             if (outcnt > 0L)
  115.                 flush(outbuf, outcnt, TRUE);   /* flush last, partial buffer */
  116.             return PK_COOL;
  117.         }
  118.  
  119.         while (code == CLEAR) {
  120.             READBITS(codesize,code)  /* ; */
  121.             switch (code) {
  122.                 case 1:
  123.                     codesize++;
  124.                     if (codesize == MAX_BITS)
  125.                         maxcode = maxcodemax;
  126.                     else
  127.                         maxcode = (1 << codesize) - 1;
  128.                     break;
  129.  
  130.                 case 2:
  131.                     partial_clear();
  132.                     break;
  133.             }
  134.  
  135.             READBITS(codesize,code)  /* ; */
  136.             if (zipeof) {
  137.                 if (outcnt > 0L)
  138.                     flush(outbuf, outcnt, TRUE);   /* partial buffer */
  139.                 return PK_COOL;
  140.             }
  141.         }
  142.  
  143.  
  144.         /* special case for KwKwK string */
  145.         incode = code;
  146.         if (prefix_of[code] == -1) {
  147.             stack[--stackp] = (uch)finchar;
  148.             code = oldcode;
  149.         }
  150.         /* generate output characters in reverse order */
  151.         while (code >= FIRST_ENT) {
  152.             if (prefix_of[code] == -1) {
  153.                 stack[--stackp] = (uch)finchar;
  154.                 code = oldcode;
  155.             } else {
  156.                 stack[--stackp] = suffix_of[code];
  157.                 code = prefix_of[code];
  158.             }
  159.         }
  160.  
  161.         finchar = suffix_of[code];
  162.         stack[--stackp] = (uch)finchar;
  163.  
  164.  
  165.         /* and put them out in forward order, block copy */
  166.         if ((HSIZE - stackp + outcnt) < outbufsiz) {
  167.             /* GRR:  this is not necessarily particularly efficient:
  168.              *       typically output only 2-5 bytes per loop (more
  169.              *       than a dozen rather rare?) */
  170.             memcpy(outptr, &stack[stackp], HSIZE - stackp);
  171.             outptr += HSIZE - stackp;
  172.             outcnt += HSIZE - stackp;
  173.             stackp = HSIZE;
  174.         }
  175.         /* output byte by byte if we can't go by blocks */
  176.         else
  177.             while (stackp < HSIZE)
  178.                 OUTB(stack[stackp++])
  179.  
  180.  
  181.         /* generate new entry */
  182.         code = free_ent;
  183.         if (code < maxcodemax) {
  184.             prefix_of[code] = oldcode;
  185.             suffix_of[code] = (uch)finchar;
  186.  
  187.             do
  188.                 code++;
  189.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  190.  
  191.             free_ent = code;
  192.         }
  193.         /* remember previous code */
  194.         oldcode = incode;
  195.     }
  196.  
  197.     /* never reached? */
  198.     /* flush last, partial buffer */
  199.     if (outcnt > 0L)
  200.         flush(outbuf, outcnt, TRUE);
  201.  
  202.     return PK_OK;
  203.  
  204. } /* end function unshrink() */
  205.  
  206.  
  207.  
  208. /******************************/
  209. /*  Function partial_clear()  */
  210. /******************************/
  211.  
  212. static void partial_clear()
  213. {
  214.     register int pr;
  215.     register int cd;
  216.  
  217.     /* mark all nodes as potentially unused */
  218.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  219.         prefix_of[cd] |= 0x8000;
  220.  
  221.     /* unmark those that are used by other nodes */
  222.     for (cd = FIRST_ENT; cd < free_ent; cd++) {
  223.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  224.         if (pr >= FIRST_ENT)    /* flag node as referenced */
  225.             prefix_of[pr] &= 0x7fff;
  226.     }
  227.  
  228.     /* clear the ones that are still marked */
  229.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  230.         if ((prefix_of[cd] & 0x8000) != 0)
  231.             prefix_of[cd] = -1;
  232.  
  233.     /* find first cleared node as next free_ent */
  234.     cd = FIRST_ENT;
  235.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  236.         cd++;
  237.     free_ent = cd;
  238. }
  239.