home *** CD-ROM | disk | FTP | other *** search
/ Toolkit for Civilization 2 / Walnut Creek CDROM - Toolkit for Civilization II.iso / utils / unix / unzip512 / unreduce.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-30  |  5.6 KB  |  216 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unreduce.c
  4.  
  5.   The Reducing algorithm is actually a combination of two distinct algorithms.
  6.   The first algorithm compresses repeated byte sequences, and the second al-
  7.   gorithm takes the compressed stream from the first algorithm and applies a
  8.   probabilistic compression method.
  9.  
  10.   ---------------------------------------------------------------------------*/
  11.  
  12.  
  13. #include "unzip.h"
  14.  
  15.  
  16. /**************************************/
  17. /*  UnReduce Defines, Typedefs, etc.  */
  18. /**************************************/
  19.  
  20. #define DLE    144
  21.  
  22. typedef uch f_array[64];        /* for followers[256][64] */
  23.  
  24. static void LoadFollowers __((void));
  25.  
  26.  
  27.  
  28. /*******************************/
  29. /*  UnReduce Global Variables  */
  30. /*******************************/
  31.  
  32. #if defined(MALLOC_WORK) || defined(MTS)
  33.    f_array *followers;     /* shared work space */
  34. #else
  35.    f_array *followers = (f_array *) (slide + 0x4000);
  36. #endif
  37.  
  38. uch Slen[256];
  39. int factor;
  40.  
  41. int L_table[] =
  42. {0, 0x7f, 0x3f, 0x1f, 0x0f};
  43.  
  44. int D_shift[] =
  45. {0, 0x07, 0x06, 0x05, 0x04};
  46. int D_mask[] =
  47. {0, 0x01, 0x03, 0x07, 0x0f};
  48.  
  49. int B_table[] =
  50. {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
  51.  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
  52.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  53.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
  54.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  55.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  56.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  57.  7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  58.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  59.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  60.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  61.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  62.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  63.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  64.  8, 8, 8, 8};
  65.  
  66.  
  67.  
  68.  
  69.  
  70. /*************************/
  71. /*  Function unreduce()  */
  72. /*************************/
  73.  
  74. void unreduce()   /* expand probabilistically reduced data */
  75. {
  76.     register int lchar = 0;
  77.     int nchar;
  78.     int ExState = 0;
  79.     int V = 0;
  80.     int Len = 0;
  81.     long s = ucsize;  /* number of bytes left to decompress */
  82.     unsigned w = 0;      /* position in output window slide[] */
  83.     unsigned u = 1;      /* true if slide[] unflushed */
  84.  
  85.  
  86. #if defined(MALLOC_WORK) || defined(MTS)
  87.     followers = (f_array *)(slide + 0x4000);
  88. #endif
  89.  
  90.     factor = lrec.compression_method - 1;
  91.     LoadFollowers();
  92.  
  93.     while (s > 0 /* && (!zipeof) */) {
  94.         if (Slen[lchar] == 0)
  95.             READBITS(8, nchar)   /* ; */
  96.         else {
  97.             READBITS(1, nchar)   /* ; */
  98.             if (nchar != 0)
  99.                 READBITS(8, nchar)       /* ; */
  100.             else {
  101.                 int follower;
  102.                 int bitsneeded = B_table[Slen[lchar]];
  103.  
  104.                 READBITS(bitsneeded, follower)   /* ; */
  105.                 nchar = followers[lchar][follower];
  106.             }
  107.         }
  108.         /* expand the resulting byte */
  109.         switch (ExState) {
  110.  
  111.         case 0:
  112.             if (nchar != DLE) {
  113.                 s--;
  114.                 slide[w++] = (uch)nchar;
  115.                 if (w == 0x4000) {
  116.                     flush(slide, w, 0);
  117.                     w = u = 0;
  118.                 }
  119.             }
  120.             else
  121.                 ExState = 1;
  122.             break;
  123.  
  124.         case 1:
  125.             if (nchar != 0) {
  126.                 V = nchar;
  127.                 Len = V & L_table[factor];
  128.                 if (Len == L_table[factor])
  129.                     ExState = 2;
  130.                 else
  131.                     ExState = 3;
  132.             } else {
  133.                 s--;
  134.                 slide[w++] = DLE;
  135.                 if (w == 0x4000)
  136.                 {
  137.                   flush(slide, w, 0);
  138.                   w = u = 0;
  139.                 }
  140.                 ExState = 0;
  141.             }
  142.             break;
  143.  
  144.         case 2:{
  145.                 Len += nchar;
  146.                 ExState = 3;
  147.             }
  148.             break;
  149.  
  150.         case 3:{
  151.                 register unsigned e;
  152.                 register unsigned n = Len + 3;
  153.                 register unsigned d = w - ((((V >> D_shift[factor]) &
  154.                                D_mask[factor]) << 8) + nchar + 1);
  155.  
  156.                 s -= n;
  157.                 do {
  158.                   n -= (e = (e = 0x4000 - ((d &= 0x3fff) > w ? d : w)) > n ?
  159.                         n : e);
  160.                   if (u && w <= d)
  161.                   {
  162.                     memzero(slide + w, e);
  163.                     w += e;
  164.                     d += e;
  165.                   }
  166.                   else
  167.                     if (w - d < e)      /* (assume unsigned comparison) */
  168.                       do {              /* slow to avoid memcpy() overlap */
  169.                         slide[w++] = slide[d++];
  170.                       } while (--e);
  171.                     else
  172.                     {
  173.                       memcpy(slide + w, slide + d, e);
  174.                       w += e;
  175.                       d += e;
  176.                     }
  177.                   if (w == 0x4000)
  178.                   {
  179.                     flush(slide, w, 0);
  180.                     w = u = 0;
  181.                   }
  182.                 } while (n);
  183.  
  184.                 ExState = 0;
  185.             }
  186.             break;
  187.         }
  188.  
  189.         /* store character for next iteration */
  190.         lchar = nchar;
  191.     }
  192.  
  193.     /* flush out slide */
  194.     flush(slide, w, 0);
  195. }
  196.  
  197.  
  198.  
  199.  
  200.  
  201. /******************************/
  202. /*  Function LoadFollowers()  */
  203. /******************************/
  204.  
  205. static void LoadFollowers()
  206. {
  207.     register int x;
  208.     register int i;
  209.  
  210.     for (x = 255; x >= 0; x--) {
  211.         READBITS(6, Slen[x])   /* ; */
  212.         for (i = 0; (uch)i < Slen[x]; i++)
  213.             READBITS(8, followers[x][i])   /* ; */
  214.     }
  215. }
  216.