utils/Install/packzip/unreduce.c

   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 */