home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / unzip540.zip / unreduce.c < prev    next >
C/C++ Source or Header  |  1998-04-15  |  7KB  |  231 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.      * Copyright 1989 Samuel H. Smith;  All rights reserved
  11.      *
  12.      * Do not distribute modified versions without my permission.
  13.      * Do not remove or alter this notice or any other copyright notice.
  14.      * If you use this in your own program you must distribute source code.
  15.      * Do not use any of this in a commercial product.
  16.  
  17.   See the accompanying file "COPYING" in UnZip source and binary distributions
  18.   for further information.  This code is NOT used unless USE_SMITH_CODE is
  19.   explicitly defined (==> COPYRIGHT_CLEAN is not defined).
  20.  
  21.   ---------------------------------------------------------------------------*/
  22.  
  23.  
  24. #define UNZIP_INTERNAL
  25. #include "unzip.h"   /* defines COPYRIGHT_CLEAN by default */
  26.  
  27.  
  28. #ifndef COPYRIGHT_CLEAN
  29.  
  30. /**************************************/
  31. /*  UnReduce Defines, Typedefs, etc.  */
  32. /**************************************/
  33.  
  34. #define DLE    144
  35.  
  36. typedef uch f_array[64];        /* for followers[256][64] */
  37.  
  38.  
  39.  
  40. /******************************/
  41. /*  UnReduce Local Functions  */
  42. /******************************/
  43.  
  44. static void LoadFollowers OF((__GPRO__ f_array *followers, uch *Slen));
  45.  
  46.  
  47.  
  48. /*******************************/
  49. /*  UnReduce Global Constants  */
  50. /*******************************/
  51.  
  52. static ZCONST shrint L_table[] =
  53. {0, 0x7f, 0x3f, 0x1f, 0x0f};
  54.  
  55. static ZCONST shrint D_shift[] =
  56. {0, 0x07, 0x06, 0x05, 0x04};
  57. static ZCONST shrint D_mask[] =
  58. {0, 0x01, 0x03, 0x07, 0x0f};
  59.  
  60. static ZCONST shrint B_table[] =
  61. {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
  62.  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
  63.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  64.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
  65.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  66.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  67.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  68.  7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  69.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  70.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  71.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  72.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  73.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  74.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  75.  8, 8, 8, 8};
  76.  
  77.  
  78.  
  79.  
  80.  
  81. /*************************/
  82. /*  Function unreduce()  */
  83. /*************************/
  84.  
  85. void unreduce(__G)   /* expand probabilistically reduced data */
  86.      __GDEF
  87. {
  88.     register int lchar = 0;
  89.     shrint nchar;
  90.     shrint ExState = 0;
  91.     shrint V = 0;
  92.     shrint Len = 0;
  93.     long s = G.ucsize;  /* number of bytes left to decompress */
  94.     unsigned w = 0;      /* position in output window slide[] */
  95.     unsigned u = 1;      /* true if slide[] unflushed */
  96.     uch Slen[256];
  97.  
  98.     f_array *followers = (f_array *)(slide + 0x4000);
  99.     int factor = G.lrec.compression_method - 1;
  100.  
  101.     LoadFollowers(__G__ followers, Slen);
  102.  
  103.     while (s > 0 /* && (!zipeof) */) {
  104.         if (Slen[lchar] == 0)
  105.             READBITS(8, nchar)   /* ; */
  106.         else {
  107.             READBITS(1, nchar)   /* ; */
  108.             if (nchar != 0)
  109.                 READBITS(8, nchar)       /* ; */
  110.             else {
  111.                 shrint follower;
  112.                 int bitsneeded = B_table[Slen[lchar]];
  113.  
  114.                 READBITS(bitsneeded, follower)   /* ; */
  115.                 nchar = followers[lchar][follower];
  116.             }
  117.         }
  118.         /* expand the resulting byte */
  119.         switch (ExState) {
  120.  
  121.         case 0:
  122.             if (nchar != DLE) {
  123.                 s--;
  124.                 slide[w++] = (uch)nchar;
  125.                 if (w == 0x4000) {
  126.                     flush(__G__ slide, (ulg)w, 0);
  127.                     w = u = 0;
  128.                 }
  129.             }
  130.             else
  131.                 ExState = 1;
  132.             break;
  133.  
  134.         case 1:
  135.             if (nchar != 0) {
  136.                 V = nchar;
  137.                 Len = V & L_table[factor];
  138.                 if (Len == L_table[factor])
  139.                     ExState = 2;
  140.                 else
  141.                     ExState = 3;
  142.             } else {
  143.                 s--;
  144.                 slide[w++] = DLE;
  145.                 if (w == 0x4000)
  146.                 {
  147.                   flush(__G__ slide, (ulg)w, 0);
  148.                   w = u = 0;
  149.                 }
  150.                 ExState = 0;
  151.             }
  152.             break;
  153.  
  154.         case 2:{
  155.                 Len += nchar;
  156.                 ExState = 3;
  157.             }
  158.             break;
  159.  
  160.         case 3:{
  161.                 register unsigned e;
  162.                 register unsigned n = Len + 3;
  163.                 register unsigned d = w - ((((V >> D_shift[factor]) &
  164.                                D_mask[factor]) << 8) + nchar + 1);
  165.  
  166.                 s -= n;
  167.                 do {
  168.                   n -= (e = (e = 0x4000 - ((d &= 0x3fff) > w ? d : w)) > n ?
  169.                         n : e);
  170.                   if (u && w <= d)
  171.                   {
  172.                     memzero(slide + w, e);
  173.                     w += e;
  174.                     d += e;
  175.                   }
  176.                   else
  177.                     if (w - d < e)      /* (assume unsigned comparison) */
  178.                       do {              /* slow to avoid memcpy() overlap */
  179.                         slide[w++] = slide[d++];
  180.                       } while (--e);
  181.                     else
  182.                     {
  183.                       memcpy(slide + w, slide + d, e);
  184.                       w += e;
  185.                       d += e;
  186.                     }
  187.                   if (w == 0x4000)
  188.                   {
  189.                     flush(__G__ slide, (ulg)w, 0);
  190.                     w = u = 0;
  191.                   }
  192.                 } while (n);
  193.  
  194.                 ExState = 0;
  195.             }
  196.             break;
  197.         }
  198.  
  199.         /* store character for next iteration */
  200.         lchar = nchar;
  201.     }
  202.  
  203.     /* flush out slide */
  204.     flush(__G__ slide, (ulg)w, 0);
  205. }
  206.  
  207.  
  208.  
  209.  
  210.  
  211. /******************************/
  212. /*  Function LoadFollowers()  */
  213. /******************************/
  214.  
  215. static void LoadFollowers(__G__ followers, Slen)
  216.      __GDEF
  217.      f_array *followers;
  218.      uch *Slen;
  219. {
  220.     register int x;
  221.     register int i;
  222.  
  223.     for (x = 255; x >= 0; x--) {
  224.         READBITS(6, Slen[x])   /* ; */
  225.         for (i = 0; (uch)i < Slen[x]; i++)
  226.             READBITS(8, followers[x][i])   /* ; */
  227.     }
  228. }
  229.  
  230. #endif /* !COPYRIGHT_CLEAN */
  231.