//---------------------------------------------------------------------------

#pragma hdrstop

#include "SFXInflate.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#define min(x,y) ((x)<(y)?(x):(y))

//--------------------------------------------------------------------------
int GetNextByte(void)
{
  if(static_cast<unsigned>(InPTR) >= ZipCount)
  {
    ZipCount = FRead(InBuf, min(VInt_BytesToGo, WSIZE));

    if((VRec_ZipHeader.Flag & 1) == 1)
    {
      for(unsigned i = 0; i < ZipCount; ++i)
      {
        InBuf[i] = InBuf[i] ^ static_cast<char>(decrypt_byte());
        UpdateKeys(static_cast<char>(InBuf[i]));
      }
    }
    InPTR = 0;
  }
  int Result;
  if(!ZipCount)
  {
    VInt_BytesToGo = 0;
    InPTR = 0;
    Result = -1;
  }
  else return InBuf[InPTR++];
  return Result;
}
//--------------------------------------------------------------------------
int Get_Compressed(void)
{  // Unshrink & UnReduce & Explode & Inflate
  int Result;
  if(VInt_BytesToGo <= 0) return -1;
  else
  {

    Result = GetNextByte();
    --VInt_BytesToGo;
  }
  return Result;
}
//--------------------------------------------------------------------------*)
void NEEDBITS(unsigned n, unsigned long& b, unsigned& k)
{
  while(k<n)
  {
    unsigned char c = static_cast<char>(Get_Compressed());
    b |= c << k;
    k += 8;
  }
}
//--------------------------------------------------------------------------
void DUMPBITS(unsigned n, unsigned long& b, unsigned& k)
{
  b >>= n;
  k -= n;
}
//--------------------------------------------------------------------------
// "decompress" an inflated type 0 (stored) block.
void inflate_stored(void)
{
   // make local copies OF globals
  unsigned long b = bb; // initialize bit buffer
  unsigned k = bk;
  unsigned w = wp; // initialize window position

  // go TO BYTE boundary
  unsigned n = k & 7;
  DUMPBITS(n, b, k);
  // get the length AND its complement
  NEEDBITS(16, b, k);
  n = (static_cast<unsigned>(b) & 0xFFFF);
  DUMPBITS(16, b, k);
  NEEDBITS(16, b, k);
  if(n != static_cast<unsigned>((~b) & 0xFFFF)) wp = 0;
  DUMPBITS(16, b, k);
  // read AND output the compressed data
  while (n--)
  {
    NEEDBITS(8, b, k);
    Slide[w++] = static_cast<unsigned char>(b);
    if(w == WSIZE)
    {
      ULONG BytesWritten;
      WriteFile(VH_OutFile, Slide, w, &BytesWritten, NULL);
      Crc32_Buf(Slide, w, VDW_CRC32Val);
      w = 0;
    }
    DUMPBITS(8, b, k);
  }
  // restore the globals from the locals
  wp = w; // restore global window pointer
  bb = b; // restore global bit buffer
  bk = k;
}

//--------------------------------------------------------------------------
/* Free the malloc'ed tables built by huft_build(), which makes a linked
  list OF the tables it made, with the links in a dummy first entry OF
  each table. */
int huft_free(Thuft* t)
{
  Thuft *p, *q;
  /* Go through linked list, freeing from the malloced (t[-1]) address. */
  p = t;
  while(p != NULL)
  {
    q = (--p)->Next;
    free(p);
    p = q;
  }
  return 0;
}
//--------------------------------------------------------------------------
int huft_build(unsigned *b, unsigned n, unsigned s, const unsigned short * d,
               const unsigned short * e, struct Thuft **t, int *m)
{

  unsigned a;                   // counter for codes of length k
  unsigned c[BMAX + 1];         // bit length count table
  unsigned el;                  // length of EOB code (value 256)
  unsigned f;                   // i repeats in table every f entries
  int g;                        // maximum code length
  int h;                        // table level
  unsigned i;                   // counter, current code
  unsigned j;                   // counter
  int k;                        // number of bits in current code
  int lx[BMAX + 1];             // memory for l[-1..BMAX-1]
  int *l = lx + 1;              // stack of bits per table
  unsigned *p;                  // pointer into c[], b[], or v[]
  Thuft *q;                     // points to current table
  Thuft r;                      // table entry for structure assignment
  Thuft *u[BMAX];               // table stack
  unsigned v[N_MAX];            // values in order of bit length
  int w;                        // bits before this table == (l * h)
  unsigned x[BMAX + 1];         // bit offsets, then code stack
  unsigned *xp;                 // pointer into x
  int y;                        // number of dummy codes added
  unsigned z;                   // number of entries in current table

  // Generate counts for each bit length
  el = n > 256 ? b[256] : BMAX; // set length of EOB code, if any
  ZeroMemory(c, sizeof (c));
  p = b;
  i = n;
  do
  {
    c[*p]++;
    p++;                        // assume all entries <= BMAX
  } while(--i);
  if(c[0] == n)
  {              // null input--all zero length codes
    *t = NULL;
    *m = 0;
    return 0;
  }
   // Find minimum and maximum length, bound *m by those
  for(j = 1; j <= BMAX; j++) if(c[j]) break;

  k = j;                        // minimum code length
  if(static_cast<unsigned>(*m) < j) *m = j;
  for(i = BMAX; i; i--) if(c[i]) break;

  g = i;                        // maximum code length
  if(static_cast<unsigned>(*m) > i) *m = i;
    // Adjust last length count to fill out codes, if needed
  for(y = 1 << j; j < i; j++, y <<= 1)
    if ((y -= c[j]) < 0)  return 2;     // bad input: more codes than bits

  if((y -= c[i]) < 0) return 2;
  c[i] += y;
  // Generate starting offsets into the value table for each length
  x[1] = j = 0;
  p = c + 1;
  xp = x + 2;

  while(--i)
  {                 // note that i == g from above
    *xp++ = (j += *p++);
  }
    /* Make a table of values in order of bit lengths */
  p = b;
  i = 0;

  do
  {
    if((j = *p++) != 0) v[x[j]++] = i;
  } while (++i < n);
    // Generate the Huffman codes and for each, make the table entries
  x[0] = i = 0;                 // first Huffman code is zero
  p = v;                        // grab values in bit order
  h = -1;                       // no tables yet--level -1
  w = l[-1] = 0;                // no bits decoded yet
  u[0] = NULL;                  // just to keep compilers happy
  q =  NULL;                    // ditto
  z = 0;                        // ditto
   // go through the bit lengths (k already is bits in shortest code)
  for(; k <= g; k++)
  {
    a = c[k];
    while(a--)
    { // here i is the Huffman code of length k bits for value *p
      // make tables up to required level
      while (k > w + l[h])
      {
        w += l[h++];            // add bits already decoded
          // compute minimum size table less than or equal to *m bits
        z = (z = g - w) > static_cast<unsigned>(*m) ? *m : z;       // upper limit
        if((f = 1 << (j = k - w)) > a + 1)
        {   // try a k-w bit table
                                               // too few codes for k-w bit table
          f -= a + 1;           // deduct codes from patterns left
          xp = c + k;
          while (++j < z)
          {     // try smaller tables up to z bits
            if ((f <<= 1) <= *++xp) break;            // enough codes to use up j bits
            f -= *xp;           // else deduct codes from patterns
          }
        }
        if(static_cast<unsigned>(w) + j > el && static_cast<unsigned>(w) < el)
              j = el - w;           // make EOB code end at table
        z = 1 << j;             // table entries for j-bit table
        l[h] = j;               // set table size in stack
          // allocate and link in new table
        if((q = static_cast<Thuft*>(malloc((z + 1) * sizeof(Thuft)))) == NULL)
        {
          if(h) huft_free (u[0]);
          return 3;             // not enough memory
        }
        hufts += z + 1;     // track memory usage
        *t = q + 1;             // link to list for huft_free()
        *(t = &(q->Next)) = NULL;
        u[h] = ++q;             // table starts after link

        // connect to last table, if there is one
        if(h)
        {
          x[h] = i;             // save pattern for backing up
          r.b = static_cast<unsigned char>(l[h - 1]); // bits to dump before this table
          r.e = static_cast<unsigned char>(16 + j); // bits in this table
          r.Next = q;            // pointer to this table
          j = (i & ((1 << w) - 1)) >> (w - l[h - 1]);
          u[h - 1][j] = r;      // connect to last table
        }
      }
           // set up table entry in r
      r.b = static_cast<unsigned char>(k - w);
      if(p >= v + n) r.e = 99;               // out of values--invalid code
      else if(*p < s)
      {
        r.e = static_cast<unsigned char>(*p < 256 ? 16 : 15);       // 256 is end-of-block code
        r.n = static_cast<unsigned short>(* p++);    // simple code is just the value
      }
      else
      {
        if(!e) return 1;             // RCV v1.6015 added
        r.e = static_cast<unsigned char>(e[*p - s]);  // non-simple--look up in lists
        r.n = d[*p++ - s];
      }
       // fill code-like entries with r
      f = 1 << (k - w);
      for (j = i >> w; j < z; j += f) q[j] = r;

      // backwards increment the k-bit code i
      for(j = 1 << (k - 1); i & j; j >>= 1) i ^= j;
      i ^= j;

      // backup over finished tables
      while((i & ((1 << w) - 1)) != x[h])
        w -= l[--h];            // don't need to update q
    }
  }
  // return actual size of base table
  *m = l[0];

  // Return true (1) if we were given an incomplete table
  return y != 0 && g != 1;
}

//--------------------------------------------------------------------------
int inflate_codes(Thuft *tl, Thuft *td, int bl, int bd)
/* inflate (decompress) the codes in a deflated (compressed) block.
 * Return an error code or zero if it all goes ok.
        *tl, *td :: Literal/length and distance decoder tables.
         bl, bd  :: Number of bits decoded by tl[] and td[].  */
{
  unsigned e;          // table entry flag/number of extra bits
  unsigned n, d;       // length and index for copy
  unsigned w;          // current window position
  Thuft *t;            // pointer to table entry
  unsigned ml, md;     // masks for bl and bd bits
  unsigned long b;              // bit buffer
  unsigned k;          // number of bits in bit buffer
   // make local copies of globals
  b = bb;                   // initialize bit buffer
  k = bk;
  w = wp;                   // initialize window position

  // inflate the coded data
  ml = mask_bits[bl];       // precompute masks for speed 
  md = mask_bits[bd];
  while(1)
  {                   // do until end of block
    NEEDBITS(static_cast<unsigned>(bl), b, k);
    if((e = (t = tl + (static_cast<unsigned>(b) & ml))->e) > 16)
     do
     {
      if(e == 99) return 1;
      DUMPBITS(t->b, b, k);
      e -= 16;
      NEEDBITS(e, b, k);
     }while ((e = (t = t->Next + (static_cast<unsigned>(b) & mask_bits[e]))->e) > 16);
    DUMPBITS (t->b, b, k);
    if(e == 16)
    {            // then it's a literal
      Slide[w++] = static_cast<unsigned char>(t->n);
      if (w == WSIZE)
      {
        ULONG BytesWritten;
        WriteFile(VH_OutFile, Slide, w, &BytesWritten, NULL);
        Crc32_Buf(Slide, w, VDW_CRC32Val);
        w = 0;
      }
    }
    else
    {                      // it's an EOB or a length
      if(e == 15) break;    // exit if end of block
      // get length of block to copy
      NEEDBITS(e, b, k);
      n = t->n + (static_cast<unsigned>(b) & mask_bits[e]);
      DUMPBITS(e,b,k);

      /* decode distance of block to copy */
      NEEDBITS(bd, b ,k);
      if((e = (t = td + (static_cast<unsigned>(b) & md))->e) > 16)
      do
      {
        if(e == 99) return 1;
        DUMPBITS(t->b, b, k);
        e -= 16;
        NEEDBITS(e, b, k);
      } while((e = (t = t->Next + (static_cast<unsigned>(b) & mask_bits[e]))->e) > 16);
      DUMPBITS(t->b, b ,k);
      NEEDBITS(e, b , k);
      d = w - t->n - (static_cast<unsigned>(b) & mask_bits[e]);
      DUMPBITS(e, b , k);
      // do the copy
      do
      {
        n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n : e);
        if (w - d >= e)
        {       // (this test assumes unsigned comparison)
          memcpy (Slide + w, Slide + d, e);
          w += e;
          d += e;
        }
        else                    // do it slowly to avoid memcpy() overlap
        do
        {
          Slide[w++] = Slide[d++];
        }while(--e);
        if(w == WSIZE)
        {
          ULONG BytesWritten;
          WriteFile(VH_OutFile, Slide, w, &BytesWritten, NULL);
          Crc32_Buf(Slide, w, VDW_CRC32Val);
          w = 0;
        }
      }while(n);
    }
  }
  // restore the globals from the locals
  wp = w;                   // restore global window pointer
  bb = b;                   // restore global bit buffer
  bk = k;
  return 0;
}
//--------------------------------------------------------------------------
void inflate_fixed(void)
{
 if(!Fixed_inited) Init_Fixed_Tables(); // init tabels first time called
 inflate_codes(fixed_tl, fixed_td, 7, 5);
}
//--------------------------------------------------------------------------
//added to release fixed tables when no longer needed
void Release_Fixed_Tables(void)
{
  huft_free(fixed_tl);
  huft_free(fixed_td);
  Fixed_inited = false;
}
//--------------------------------------------------------------------------
// improved inflate fixed thanks to James Turner and Markus Stephany
void Init_Fixed_Tables(void)
{
  int fixed_bl, fixed_bd;
  int i;                   // temporary variable
  unsigned l[288];         // length list for huft_build
    // literal table
  for(i = 0; i < 144; i++) l[i] = 8;
  for(; i < 256; i++) l[i] = 9;
  for(; i < 280; i++) l[i] = 7;
  for(; i < 288; i++) l[i] = 8;      // make a complete, but wrong code set
  fixed_bl = 7;
  huft_build(l, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl);
   // distance table
  for(i = 0; i < 30; i++) l[i] = 5;    // make an incomplete code set
  fixed_bd = 5;
  huft_build( l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd);
  Fixed_inited = true;
}
//--------------------------------------------------------------------------
void inflate_dynamic(void)
{ //decompress an inflated type 2 (dynamic Huffman codes) block.
  int i;                        // temporary variables
  unsigned j;
  unsigned l;                   // last length                                                          */
  unsigned m;                   // mask for bit lengths table
  unsigned n;                   // number of lengths to get
  Thuft *tl;                    // literal/length code table
  Thuft *td;                    // distance code table
  int bl;                       // lookup bits for tl
  int bd;                       // lookup bits for td
  unsigned nb;                  // number of bit length codes
  unsigned nl;                  // number of literal/length codes
  unsigned nd;                  // number of distance codes
  unsigned ll[288 + 32];        // literal/length and distance code lengths
  unsigned long b;                       // bit buffer
  unsigned k;                   // number of bits in bit buffer
   // make local bit buffer */
  b = bb;
  k = bk;

  // read in table lengths
  NEEDBITS(5, b, k);
  nl = 257 + (static_cast<unsigned>(b) & 0x1f);   // number of literal/length codes
  DUMPBITS(5, b, k);
  NEEDBITS(5, b, k);
  nd = 1 + (static_cast<unsigned>(b) & 0x1f);     // number of distance codes
  DUMPBITS(5, b, k);
  NEEDBITS(4, b, k);
  nb = 4 + (static_cast<unsigned>(b) & 0xf);      // number of bit length codes
  DUMPBITS(4, b, k);
  if (nl > 288 || nd > 32) return;  // bad lengths
   // read in bit-length-code lengths
  for(j = 0; j < nb; j++)
  {
    NEEDBITS(3, b, k);
    ll[border[j]] = static_cast<unsigned>(b) & 7;
    DUMPBITS(3, b, k);
  }
  for(; j < 19; j++)
        ll[border[j]] = 0;

  // build decoding table for trees--single level, 7 bit lookup
  bl = 7;
  if((i = huft_build( ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
  {
    if(i == 1) huft_free(tl);   // incomplete code set
    return;
  }
   // read in literal and distance code lengths
  n = nl + nd;
  m = mask_bits[bl];
  i = l = 0;

  while(static_cast<unsigned>(i) < n)
  {
    NEEDBITS(static_cast<unsigned>(bl), b, k);
    j = (td = tl + (static_cast<unsigned>(b) & m))->b;
    DUMPBITS(j, b, k);
    j = td->n;     // length of code in bits (0..15)
    if(j < 16) ll[i++] = l = j;          //save last length in l
    else if (j == 16)
    {         // repeat last length 3 to 6 times
      NEEDBITS(2, b, k);
      j = 3 + (static_cast<unsigned>(b) & 3);
      DUMPBITS(2, b, k);
      if (static_cast<unsigned>(i) + j > n) return;
      while(j--) ll[i++] = l;
    }
    else if(j == 17)
    {         // 3 to 10 zero length codes
      NEEDBITS(3, b, k);
      j = 3 + (static_cast<unsigned>(b) & 7);
      DUMPBITS(3, b, k);
      if(static_cast<unsigned>(i) + j > n) return;
      while(j--) ll[i++] = 0;
      l = 0;
    }
    else
    {                      // j == 18: 11 to 138 zero length codes
      NEEDBITS(7, b, k);
      j = 11 + (static_cast<unsigned>(b) & 0x7f);
      DUMPBITS(7, b, k);
      if(static_cast<unsigned>(i) + j > n) return;
      while(j--) ll[i++] = 0;
      l = 0;
    }
  }
   // free decoding table for trees
  huft_free(tl);

  // restore the global bit buffer
  bb = b;
  bk = k;

  // build the decoding tables for literal/length and distance codes
  bl = lbits;
  if((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
  {
    if(i == 1) huft_free(tl);
    return;                   // incomplete code set
  }
  bd = dbits;
  huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd);
  // decompress until an end-of-block code
  if (inflate_codes(tl, td, bl, bd)) return;
  // free the decoding tables, return
  huft_free (tl);
  huft_free (td);
}
//--------------------------------------------------------------------------
void inflate_block(int* e)
{//   e = last block flag
 // decompress an inflated block

   // make local bit buffer
  unsigned long b = bb; //bit buffer
  unsigned k = bk; // number of bits in bit buffer
  // read in last block bit
  NEEDBITS(1, b, k);
  *e = static_cast<int>(b) & 1;
  DUMPBITS(1, b, k);
    /* read in block type */
  NEEDBITS(2, b, k);
  unsigned t = static_cast<unsigned>(b) & 3;   /* block type */
  DUMPBITS(2, b, k);
    /* restore the global bit buffer */
  bb = b;
  bk = k;
  /* inflate that block type */
  switch(t)
  {
    case 0: inflate_stored(); break;
    case 1: inflate_fixed();  break;
    case 2: inflate_dynamic();break;
  }
}
//--------------------------------------------------------------------------
void Inflate(void)
{
  int e;
  InPTR = 0;
  ZipCount = 0;
   // initialize window, bit buffer
  wp = 0;
  bk = 0;
  bb = 0;
  // decompress UNTIL the last block
  unsigned h = 0; // maximum struct huft's malloc'ed
  InBuf = NULL;
  Slide = NULL;
  try
  {
    InBuf = new char[WSIZE + 1];
    Slide = new char[WSIZE + 1];
    try
    {
      do
      {
        hufts = 0;
        inflate_block(&e);
        if(hufts > h) h = hufts;
      } while (!e);
      if(wp)
      {
        ULONG BytesWritten;
        WriteFile(VH_OutFile, Slide, wp, &BytesWritten, NULL);
        Crc32_Buf(Slide, wp, VDW_CRC32Val);
        wp = 0;
      }
    }
    catch(...)
    {
//      MessageBox(0, "Error...", "Error", mb_OK)
    }
  }
  __finally
  {
    delete[] InBuf;
    delete[] Slide;
  }
}



