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 / UNREDUCE.C < prev    next >
Text File  |  1992-12-05  |  6KB  |  218 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 byte f_array[64];       /* for followers[256][64] */
  23.  
  24. #ifndef NOPROTO
  25. static void LoadFollowers __((void));
  26. void flush OF((unsigned));      /* routine from inflate.c */
  27. #endif
  28.  
  29.  
  30. /*******************************/
  31. /*  UnReduce Global Variables  */
  32. /*******************************/
  33.  
  34. #if (defined(MACOS) || defined(MTS))
  35.    f_array *followers;     /* shared work space */
  36. #else
  37.    f_array *followers = (f_array *) (slide + 0x4000);
  38. #endif
  39.  
  40. byte Slen[256];
  41. int factor;
  42.  
  43. int L_table[] =
  44. {0, 0x7f, 0x3f, 0x1f, 0x0f};
  45.  
  46. int D_shift[] =
  47. {0, 0x07, 0x06, 0x05, 0x04};
  48. int D_mask[] =
  49. {0, 0x01, 0x03, 0x07, 0x0f};
  50.  
  51. int B_table[] =
  52. {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
  53.  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
  54.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  55.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 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, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  58.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  59.  7, 7, 7, 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, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  65.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  66.  8, 8, 8, 8};
  67.  
  68.  
  69.  
  70.  
  71.  
  72. /*************************/
  73. /*  Function unReduce()  */
  74. /*************************/
  75.  
  76. void unReduce()   /* expand probabilistically reduced data */
  77. {
  78.     register int lchar = 0;
  79.     int nchar;
  80.     int ExState = 0;
  81.     int V = 0;
  82.     int Len = 0;
  83.     longint s = ucsize;  /* number of bytes left to decompress */
  84.     unsigned w = 0;      /* position in output window slide[] */
  85.     unsigned u = 1;      /* true if slide[] unflushed */
  86.  
  87.  
  88. #if (defined(MACOS) || defined(MTS))
  89.     followers = (f_array *) (slide + 0x4000);
  90. #endif
  91.  
  92.     factor = lrec.compression_method - 1;
  93.     LoadFollowers();
  94.  
  95.     while (s > 0 /* && (!zipeof) */) {
  96.         if (Slen[lchar] == 0)
  97.             READBIT(8, nchar)   /* ; */
  98.         else {
  99.             READBIT(1, nchar);
  100.             if (nchar != 0)
  101.                 READBIT(8, nchar)       /* ; */
  102.             else {
  103.                 int follower;
  104.                 int bitsneeded = B_table[Slen[lchar]];
  105.                 READBIT(bitsneeded, follower);
  106.                 nchar = followers[lchar][follower];
  107.             }
  108.         }
  109.         /* expand the resulting byte */
  110.         switch (ExState) {
  111.  
  112.         case 0:
  113.             if (nchar != DLE) {
  114.                 s--;
  115.                 slide[w++] = (byte) nchar;
  116.                 if (w == 0x4000) {
  117.                     flush(w);
  118.                     w = u = 0;
  119.                 }
  120.             }
  121.             else
  122.                 ExState = 1;
  123.             break;
  124.  
  125.         case 1:
  126.             if (nchar != 0) {
  127.                 V = nchar;
  128.                 Len = V & L_table[factor];
  129.                 if (Len == L_table[factor])
  130.                     ExState = 2;
  131.                 else
  132.                     ExState = 3;
  133.             } else {
  134.                 s--;
  135.                 slide[w++] = DLE;
  136.                 if (w == 0x4000)
  137.                 {
  138.                   flush(w);
  139.                   w = u = 0;
  140.                 }
  141.                 ExState = 0;
  142.             }
  143.             break;
  144.  
  145.         case 2:{
  146.                 Len += nchar;
  147.                 ExState = 3;
  148.             }
  149.             break;
  150.  
  151.         case 3:{
  152.                 register unsigned e;
  153.                 register unsigned n = Len + 3;
  154.                 register unsigned d = w - ((((V >> D_shift[factor]) &
  155.                                D_mask[factor]) << 8) + nchar + 1);
  156.  
  157.                 s -= n;
  158.                 do {
  159.                   n -= (e = (e = 0x4000 - ((d &= 0x3fff) > w ? d : w)) > n ?
  160.                         n : e);
  161.                   if (u && w <= d)
  162.                   {
  163.                     memset(slide + w, 0, e);
  164.                     w += e;
  165.                     d += e;
  166.                   }
  167.                   else
  168.                     if (w - d < e)      /* (assume unsigned comparison) */
  169.                       do {              /* slow to avoid memcpy() overlap */
  170.                         slide[w++] = slide[d++];
  171.                       } while (--e);
  172.                     else
  173.                     {
  174.                       memcpy(slide + w, slide + d, e);
  175.                       w += e;
  176.                       d += e;
  177.                     }
  178.                   if (w == 0x4000)
  179.                   {
  180.                     flush(w);
  181.                     w = u = 0;
  182.                   }
  183.                 } while (n);
  184.  
  185.                 ExState = 0;
  186.             }
  187.             break;
  188.         }
  189.  
  190.         /* store character for next iteration */
  191.         lchar = nchar;
  192.     }
  193.  
  194.     /* flush out slide */
  195.     flush(w);
  196. }
  197.  
  198.  
  199.  
  200.  
  201.  
  202. /******************************/
  203. /*  Function LoadFollowers()  */
  204. /******************************/
  205.  
  206. static void LoadFollowers()
  207. {
  208.     register int x;
  209.     register int i;
  210.  
  211.     for (x = 255; x >= 0; x--) {
  212.         READBIT(6, Slen[x]);
  213.         for (i = 0; (byte) i < Slen[x]; i++) {
  214.             READBIT(8, followers[x][i]);
  215.         }
  216.     }
  217. }
  218.