home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / ARCHIVERS / unzip50_src.lzh / UNZIP50 / UNSHRINK.C < prev    next >
Text File  |  1992-12-05  |  5KB  |  189 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. #ifndef NOPROTO
  25. static void partial_clear __((void));   /* local prototype */
  26. #endif
  27.  
  28. int codesize, maxcode, maxcodemax, free_ent;
  29.  
  30.  
  31.  
  32.  
  33. /*************************/
  34. /*  Function unShrink()  */
  35. /*************************/
  36.  
  37. void unShrink()
  38. {
  39.     register int code;
  40.     register int stackp;
  41.     int finchar;
  42.     int oldcode;
  43.     int incode;
  44.  
  45.  
  46.     /* decompress the file */
  47.     codesize = INIT_BITS;
  48.     maxcode = (1 << codesize) - 1;
  49.     maxcodemax = HSIZE;         /* (1 << MAX_BITS) */
  50.     free_ent = FIRST_ENT;
  51.  
  52.     code = maxcodemax;
  53.     do {
  54.         prefix_of[code] = -1;
  55.     } while (--code > 255);
  56. /*
  57.     OvdL: -Ox with SCO's 3.2.0 cc gives
  58.     a. warning: overflow in constant multiplication
  59.     b. segmentation fault (core dumped) when using the executable
  60.     for (code = maxcodemax; code > 255; code--)
  61.         prefix_of[code] = -1;
  62.  */
  63.  
  64.     for (code = 255; code >= 0; code--) {
  65.         prefix_of[code] = 0;
  66.         suffix_of[code] = (byte) code;
  67.     }
  68.  
  69.     GetCode(oldcode);
  70.     if (zipeof)
  71.         return;
  72.     finchar = oldcode;
  73.  
  74.     OUTB(finchar);
  75.  
  76.     stackp = HSIZE;
  77.  
  78.     while (!zipeof) {
  79.         GetCode(code);
  80.         if (zipeof)
  81.             return;
  82.  
  83.         while (code == CLEAR) {
  84.             GetCode(code);
  85.             switch (code) {
  86.                 case 1:
  87.                     codesize++;
  88.                     if (codesize == MAX_BITS)
  89.                         maxcode = maxcodemax;
  90.                     else
  91.                         maxcode = (1 << codesize) - 1;
  92.                     break;
  93.  
  94.                 case 2:
  95.                     partial_clear();
  96.                     break;
  97.             }
  98.  
  99.             GetCode(code);
  100.             if (zipeof)
  101.                 return;
  102.         }
  103.  
  104.  
  105.         /* special case for KwKwK string */
  106.         incode = code;
  107.         if (prefix_of[code] == -1) {
  108.             stack[--stackp] = (byte) finchar;
  109.             code = oldcode;
  110.         }
  111.         /* generate output characters in reverse order */
  112.         while (code >= FIRST_ENT) {
  113.             if (prefix_of[code] == -1) {
  114.                 stack[--stackp] = (byte) finchar;
  115.                 code = oldcode;
  116.             } else {
  117.                 stack[--stackp] = suffix_of[code];
  118.                 code = prefix_of[code];
  119.             }
  120.         }
  121.  
  122.         finchar = suffix_of[code];
  123.         stack[--stackp] = (byte) finchar;
  124.  
  125.  
  126.         /* and put them out in forward order, block copy */
  127.         if ((HSIZE - stackp + outcnt) < OUTBUFSIZ) {
  128.             memcpy(outptr, &stack[stackp], HSIZE - stackp);
  129.             outptr += HSIZE - stackp;
  130.             outcnt += HSIZE - stackp;
  131.             stackp = HSIZE;
  132.         }
  133.         /* output byte by byte if we can't go by blocks */
  134.         else
  135.             while (stackp < HSIZE)
  136.                 OUTB(stack[stackp++]);
  137.  
  138.  
  139.         /* generate new entry */
  140.         code = free_ent;
  141.         if (code < maxcodemax) {
  142.             prefix_of[code] = oldcode;
  143.             suffix_of[code] = (byte) finchar;
  144.  
  145.             do
  146.                 code++;
  147.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  148.  
  149.             free_ent = code;
  150.         }
  151.         /* remember previous code */
  152.         oldcode = incode;
  153.     }
  154. }
  155.  
  156.  
  157.  
  158. /******************************/
  159. /*  Function partial_clear()  */
  160. /******************************/
  161.  
  162. static void partial_clear()
  163. {
  164.     register int pr;
  165.     register int cd;
  166.  
  167.     /* mark all nodes as potentially unused */
  168.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  169.         prefix_of[cd] |= 0x8000;
  170.  
  171.     /* unmark those that are used by other nodes */
  172.     for (cd = FIRST_ENT; cd < free_ent; cd++) {
  173.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  174.         if (pr >= FIRST_ENT)    /* flag node as referenced */
  175.             prefix_of[pr] &= 0x7fff;
  176.     }
  177.  
  178.     /* clear the ones that are still marked */
  179.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  180.         if ((prefix_of[cd] & 0x8000) != 0)
  181.             prefix_of[cd] = -1;
  182.  
  183.     /* find first cleared node as next free_ent */
  184.     cd = FIRST_ENT;
  185.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  186.         cd++;
  187.     free_ent = cd;
  188. }
  189.