home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / UNZP50P1.ZIP / unshrink.c < prev    next >
C/C++ Source or Header  |  1993-01-23  |  5KB  |  187 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unshrink.c
  4.  
  5.   Shrinking is a Dynamic Lempel-Ziv-Welch compression algorithm with partial
  6.   clearing.
  7.  
  8.   ---------------------------------------------------------------------------*/
  9.  
  10.  
  11. #include "unzip.h"
  12.  
  13.  
  14. /*************************************/
  15. /*  UnShrink Defines, Globals, etc.  */
  16. /*************************************/
  17.  
  18. /*      MAX_BITS        13   (in unzip.h; defines size of global work area)  */
  19. #define INIT_BITS       9
  20. #define FIRST_ENT       257
  21. #define CLEAR           256
  22. #define GetCode(dest)   READBIT(codesize,dest)
  23.  
  24. static void partial_clear __((void));   /* local prototype */
  25.  
  26. int codesize, maxcode, maxcodemax, free_ent;
  27.  
  28.  
  29.  
  30.  
  31. /*************************/
  32. /*  Function unShrink()  */
  33. /*************************/
  34.  
  35. void unShrink()
  36. {
  37.     register int code;
  38.     register int stackp;
  39.     int finchar;
  40.     int oldcode;
  41.     int incode;
  42.  
  43.  
  44.     /* decompress the file */
  45.     codesize = INIT_BITS;
  46.     maxcode = (1 << codesize) - 1;
  47.     maxcodemax = HSIZE;         /* (1 << MAX_BITS) */
  48.     free_ent = FIRST_ENT;
  49.  
  50.     code = maxcodemax;
  51.     do {
  52.         prefix_of[code] = -1;
  53.     } while (--code > 255);
  54. /*
  55.     OvdL: -Ox with SCO's 3.2.0 cc gives
  56.     a. warning: overflow in constant multiplication
  57.     b. segmentation fault (core dumped) when using the executable
  58.     for (code = maxcodemax; code > 255; code--)
  59.         prefix_of[code] = -1;
  60.  */
  61.  
  62.     for (code = 255; code >= 0; code--) {
  63.         prefix_of[code] = 0;
  64.         suffix_of[code] = (byte) code;
  65.     }
  66.  
  67.     GetCode(oldcode);
  68.     if (zipeof)
  69.         return;
  70.     finchar = oldcode;
  71.  
  72.     OUTB(finchar);
  73.  
  74.     stackp = HSIZE;
  75.  
  76.     while (!zipeof) {
  77.         GetCode(code);
  78.         if (zipeof)
  79.             return;
  80.  
  81.         while (code == CLEAR) {
  82.             GetCode(code);
  83.             switch (code) {
  84.                 case 1:
  85.                     codesize++;
  86.                     if (codesize == MAX_BITS)
  87.                         maxcode = maxcodemax;
  88.                     else
  89.                         maxcode = (1 << codesize) - 1;
  90.                     break;
  91.  
  92.                 case 2:
  93.                     partial_clear();
  94.                     break;
  95.             }
  96.  
  97.             GetCode(code);
  98.             if (zipeof)
  99.                 return;
  100.         }
  101.  
  102.  
  103.         /* special case for KwKwK string */
  104.         incode = code;
  105.         if (prefix_of[code] == -1) {
  106.             stack[--stackp] = (byte) finchar;
  107.             code = oldcode;
  108.         }
  109.         /* generate output characters in reverse order */
  110.         while (code >= FIRST_ENT) {
  111.             if (prefix_of[code] == -1) {
  112.                 stack[--stackp] = (byte) finchar;
  113.                 code = oldcode;
  114.             } else {
  115.                 stack[--stackp] = suffix_of[code];
  116.                 code = prefix_of[code];
  117.             }
  118.         }
  119.  
  120.         finchar = suffix_of[code];
  121.         stack[--stackp] = (byte) finchar;
  122.  
  123.  
  124.         /* and put them out in forward order, block copy */
  125.         if ((HSIZE - stackp + outcnt) < OUTBUFSIZ) {
  126.             memcpy(outptr, &stack[stackp], HSIZE - stackp);
  127.             outptr += HSIZE - stackp;
  128.             outcnt += HSIZE - stackp;
  129.             stackp = HSIZE;
  130.         }
  131.         /* output byte by byte if we can't go by blocks */
  132.         else
  133.             while (stackp < HSIZE)
  134.                 OUTB(stack[stackp++]);
  135.  
  136.  
  137.         /* generate new entry */
  138.         code = free_ent;
  139.         if (code < maxcodemax) {
  140.             prefix_of[code] = oldcode;
  141.             suffix_of[code] = (byte) finchar;
  142.  
  143.             do
  144.                 code++;
  145.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  146.  
  147.             free_ent = code;
  148.         }
  149.         /* remember previous code */
  150.         oldcode = incode;
  151.     }
  152. }
  153.  
  154.  
  155.  
  156. /******************************/
  157. /*  Function partial_clear()  */
  158. /******************************/
  159.  
  160. static void partial_clear()
  161. {
  162.     register int pr;
  163.     register int cd;
  164.  
  165.     /* mark all nodes as potentially unused */
  166.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  167.         prefix_of[cd] |= 0x8000;
  168.  
  169.     /* unmark those that are used by other nodes */
  170.     for (cd = FIRST_ENT; cd < free_ent; cd++) {
  171.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  172.         if (pr >= FIRST_ENT)    /* flag node as referenced */
  173.             prefix_of[pr] &= 0x7fff;
  174.     }
  175.  
  176.     /* clear the ones that are still marked */
  177.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  178.         if ((prefix_of[cd] & 0x8000) != 0)
  179.             prefix_of[cd] = -1;
  180.  
  181.     /* find first cleared node as next free_ent */
  182.     cd = FIRST_ENT;
  183.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  184.         cd++;
  185.     free_ent = cd;
  186. }
  187.