context: // BZip2InputStream.cs
  //
  // Copyright (C) 2001 Mike Krueger
  //
  // This program is free software; you can redistribute it and/or
  // modify it under the terms of the GNU General Public License
  // as published by the Free Software Foundation; either version 2
  // of the License, or (at your option) any later version.
  //
  // This program is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  // GNU General Public License for more details.
  //
  // You should have received a copy of the GNU General Public License
  // along with this program; if not, write to the Free Software
  // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  //
  // Linking this library statically or dynamically with other modules is
  // making a combined work based on this library.  Thus, the terms and
  // conditions of the GNU General Public License cover the whole
  // combination.
  // 
  // As a special exception, the copyright holders of this library give you
  // permission to link this library with independent modules to produce an
  // executable, regardless of the license terms of these independent
  // modules, and to copy and distribute the resulting executable under
  // terms of your choice, provided that you also meet, for each linked
  // independent module, the terms and conditions of the license of that
  // module.  An independent module is a module which is not derived from
  // or based on this library.  If you modify this library, you may extend
  // this exception to your version of the library, but you are not
  // obligated to do so.  If you do not wish to do so, delete this
  // exception statement from your version.
  
  using System;
  using System.IO;
  using ICSharpCode.SharpZipLib.Checksums;
  
  namespace ICSharpCode.SharpZipLib.BZip2
  {
      /// <summary>
      ///     An input stream that decompresses files in the BZip2 format
      /// </summary>
      public class BZip2InputStream : Stream
      {
          #region Constructors
  
          /// <summary>
          ///     Construct instance for reading from stream
          /// </summary>
          /// <param name="stream">Data source</param>
          public BZip2InputStream(Stream stream)
          {
              // init arrays
              for (var i = 0; i < BZip2Constants.GroupCount; ++i)
              {
                  limit[i] = new int[BZip2Constants.MaximumAlphaSize];
                  baseArray[i] = new int[BZip2Constants.MaximumAlphaSize];
                  perm[i] = new int[BZip2Constants.MaximumAlphaSize];
              }
  
              BsSetStream(stream);
              Initialize();
              InitBlock();
              SetupBlock();
          }
  
          #endregion
  
          /// <summary>
          ///     Get/set flag indicating ownership of underlying stream.
          ///     When the flag is true <see cref="Close"></see> will close the underlying stream also.
          /// </summary>
          public bool IsStreamOwner { get; set; } = true;
  
          private void MakeMaps()
          {
              nInUse = 0;
              for (var i = 0; i < 256; ++i)
              {
                  if (inUse[i])
                  {
                      seqToUnseq[nInUse] = (byte) i;
                      unseqToSeq[i] = (byte) nInUse;
                      nInUse++;
                  }
              }
          }
  
          private void Initialize()
          {
              var magic1 = BsGetUChar();
              var magic2 = BsGetUChar();
  
              var magic3 = BsGetUChar();
              var magic4 = BsGetUChar();
  
              if (magic1 != 'B' || magic2 != 'Z' || magic3 != 'h' || magic4 < '1' || magic4 > '9')
              {
                  streamEnd = true;
                  return;
              }
  
              SetDecompressStructureSizes(magic4 - '0');
              computedCombinedCRC = 0;
          }
  
          private void InitBlock()
          {
              var magic1 = BsGetUChar();
              var magic2 = BsGetUChar();
              var magic3 = BsGetUChar();
              var magic4 = BsGetUChar();
              var magic5 = BsGetUChar();
              var magic6 = BsGetUChar();
  
              if (magic1 == 0x17 && magic2 == 0x72 && magic3 == 0x45 && magic4 == 0x38 && magic5 == 0x50 &&
                  magic6 == 0x90)
              {
                  Complete();
                  return;
              }
  
              if (magic1 != 0x31 || magic2 != 0x41 || magic3 != 0x59 || magic4 != 0x26 || magic5 != 0x53 ||
                  magic6 != 0x59)
              {
                  BadBlockHeader();
                  streamEnd = true;
                  return;
              }
  
              storedBlockCRC = BsGetInt32();
  
              blockRandomised = BsR(1) == 1;
  
              GetAndMoveToFrontDecode();
  
              mCrc.Reset();
              currentState = START_BLOCK_STATE;
          }
  
          private void EndBlock()
          {
              computedBlockCRC = (int) mCrc.Value;
  
              // -- A bad CRC is considered a fatal error. --
              if (storedBlockCRC != computedBlockCRC)
              {
                  CrcError();
              }
  
              // 1528150659
              computedCombinedCRC = ((computedCombinedCRC << 1) & 0xFFFFFFFF) | (computedCombinedCRC >> 31);
              computedCombinedCRC = computedCombinedCRC ^ (uint) computedBlockCRC;
          }
  
          private void Complete()
          {
              storedCombinedCRC = BsGetInt32();
              if (storedCombinedCRC != (int) computedCombinedCRC)
              {
                  CrcError();
              }
  
              streamEnd = true;
          }
  
          private void BsSetStream(Stream stream)
          {
              baseStream = stream;
              bsLive = 0;
              bsBuff = 0;
          }
  
          private void FillBuffer()
          {
              var thech = 0;
  
              try
              {
                  thech = baseStream.ReadByte();
              }
              catch (Exception)
              {
                  CompressedStreamEOF();
              }
  
              if (thech == -1)
              {
                  CompressedStreamEOF();
              }
  
              bsBuff = (bsBuff << 8) | (thech & 0xFF);
              bsLive += 8;
          }
  
          private int BsR(int n)
          {
              while (bsLive < n)
              {
                  FillBuffer();
              }
  
              var v = (bsBuff >> (bsLive - n)) & ((1 << n) - 1);
              bsLive -= n;
              return v;
          }
  
          private char BsGetUChar()
          {
              return (char) BsR(8);
          }
  
          private int BsGetIntVS(int numBits)
          {
              return BsR(numBits);
          }
  
          private int BsGetInt32()
          {
              var result = BsR(8);
              result = (result << 8) | BsR(8);
              result = (result << 8) | BsR(8);
              result = (result << 8) | BsR(8);
              return result;
          }
  
          private void RecvDecodingTables()
          {
              var len = new char[BZip2Constants.GroupCount][];
              for (var i = 0; i < BZip2Constants.GroupCount; ++i)
              {
                  len[i] = new char[BZip2Constants.MaximumAlphaSize];
              }
  
              var inUse16 = new bool[16];
  
              //--- Receive the mapping table ---
              for (var i = 0; i < 16; i++)
              {
                  inUse16[i] = BsR(1) == 1;
              }
  
              for (var i = 0; i < 16; i++)
              {
                  if (inUse16[i])
                  {
                      for (var j = 0; j < 16; j++)
                      {
                          inUse[i * 16 + j] = BsR(1) == 1;
                      }
                  }
                  else
                  {
                      for (var j = 0; j < 16; j++)
                      {
                          inUse[i * 16 + j] = false;
                      }
                  }
              }
  
              MakeMaps();
              var alphaSize = nInUse + 2;
  
              //--- Now the selectors ---
              var nGroups = BsR(3);
              var nSelectors = BsR(15);
  
              for (var i = 0; i < nSelectors; i++)
              {
                  var j = 0;
                  while (BsR(1) == 1)
                  {
                      j++;
                  }
                  selectorMtf[i] = (byte) j;
              }
  
              //--- Undo the MTF values for the selectors. ---
              var pos = new byte[BZip2Constants.GroupCount];
              for (var v = 0; v < nGroups; v++)
              {
                  pos[v] = (byte) v;
              }
  
              for (var i = 0; i < nSelectors; i++)
              {
                  int v = selectorMtf[i];
                  var tmp = pos[v];
                  while (v > 0)
                  {
                      pos[v] = pos[v - 1];
                      v--;
                  }
                  pos[0] = tmp;
                  selector[i] = tmp;
              }
  
              //--- Now the coding tables ---
              for (var t = 0; t < nGroups; t++)
              {
                  var curr = BsR(5);
                  for (var i = 0; i < alphaSize; i++)
                  {
                      while (BsR(1) == 1)
                      {
                          if (BsR(1) == 0)
                          {
                              curr++;
                          }
                          else
                          {
                              curr--;
                          }
                      }
                      len[t][i] = (char) curr;
                  }
              }
  
              //--- Create the Huffman decoding tables ---
              for (var t = 0; t < nGroups; t++)
              {
                  var minLen = 32;
                  var maxLen = 0;
                  for (var i = 0; i < alphaSize; i++)
                  {
                      maxLen = Math.Max(maxLen, len[t][i]);
                      minLen = Math.Min(minLen, len[t][i]);
                  }
                  HbCreateDecodeTables(limit[t], baseArray[t], perm[t], len[t], minLen, maxLen, alphaSize);
                  minLens[t] = minLen;
              }
          }
  
          private void GetAndMoveToFrontDecode()
          {
              var yy = new byte[256];
              int nextSym;
  
              var limitLast = BZip2Constants.BaseBlockSize * blockSize100k;
              origPtr = BsGetIntVS(24);
  
              RecvDecodingTables();
              var EOB = nInUse + 1;
              var groupNo = -1;
              var groupPos = 0;
  
              /*--
              Setting up the unzftab entries here is not strictly
              necessary, but it does save having to do it later
              in a separate pass, and so saves a block's worth of
              cache misses.
              --*/
              for (var i = 0; i <= 255; i++)
              {
                  unzftab[i] = 0;
              }
  
              for (var i = 0; i <= 255; i++)
              {
                  yy[i] = (byte) i;
              }
  
              last = -1;
  
              if (groupPos == 0)
              {
                  groupNo++;
                  groupPos = BZip2Constants.GroupSize;
              }
  
              groupPos--;
              int zt = selector[groupNo];
              var zn = minLens[zt];
              var zvec = BsR(zn);
              int zj;
  
              while (zvec > limit[zt][zn])
              {
                  if (zn > 20)
                  {
                      // the longest code
                      throw new BZip2Exception("Bzip data error");
                  }
                  zn++;
                  while (bsLive < 1)
                  {
                      FillBuffer();
                  }
                  zj = (bsBuff >> (bsLive - 1)) & 1;
                  bsLive--;
                  zvec = (zvec << 1) | zj;
              }
              if (zvec - baseArray[zt][zn] < 0 || zvec - baseArray[zt][zn] >= BZip2Constants.MaximumAlphaSize)
              {
                  throw new BZip2Exception("Bzip data error");
              }
              nextSym = perm[zt][zvec - baseArray[zt][zn]];
  
              while (true)
              {
                  if (nextSym == EOB)
                  {
                      break;
                  }
  
                  if (nextSym == BZip2Constants.RunA || nextSym == BZip2Constants.RunB)
                  {
                      var s = -1;
                      var n = 1;
                      do
                      {
                          if (nextSym == BZip2Constants.RunA)
                          {
                              s += (0 + 1) * n;
                          }
                          else if (nextSym == BZip2Constants.RunB)
                          {
                              s += (1 + 1) * n;
                          }
  
                          n <<= 1;
  
                          if (groupPos == 0)
                          {
                              groupNo++;
                              groupPos = BZip2Constants.GroupSize;
                          }
  
                          groupPos--;
  
                          zt = selector[groupNo];
                          zn = minLens[zt];
                          zvec = BsR(zn);
  
                          while (zvec > limit[zt][zn])
                          {
                              zn++;
                              while (bsLive < 1)
                              {
                                  FillBuffer();
                              }
                              zj = (bsBuff >> (bsLive - 1)) & 1;
                              bsLive--;
                              zvec = (zvec << 1) | zj;
                          }
                          nextSym = perm[zt][zvec - baseArray[zt][zn]];
                      } while (nextSym == BZip2Constants.RunA || nextSym == BZip2Constants.RunB);
  
                      s++;
                      var ch = seqToUnseq[yy[0]];
                      unzftab[ch] += s;
  
                      while (s > 0)
                      {
                          last++;
                          ll8[last] = ch;
                          s--;
                      }
  
                      if (last >= limitLast)
                      {
                          BlockOverrun();
                      }
                  }
                  else
                  {
                      last++;
                      if (last >= limitLast)
                      {
                          BlockOverrun();
                      }
  
                      var tmp = yy[nextSym - 1];
                      unzftab[seqToUnseq[tmp]]++;
                      ll8[last] = seqToUnseq[tmp];
  
                      for (var j = nextSym - 1; j > 0; --j)
                      {
                          yy[j] = yy[j - 1];
                      }
                      yy[0] = tmp;
  
                      if (groupPos == 0)
                      {
                          groupNo++;
                          groupPos = BZip2Constants.GroupSize;
                      }
  
                      groupPos--;
                      zt = selector[groupNo];
                      zn = minLens[zt];
                      zvec = BsR(zn);
                      while (zvec > limit[zt][zn])
                      {
                          zn++;
                          while (bsLive < 1)
                          {
                              FillBuffer();
                          }
                          zj = (bsBuff >> (bsLive - 1)) & 1;
                          bsLive--;
                          zvec = (zvec << 1) | zj;
                      }
                      nextSym = perm[zt][zvec - baseArray[zt][zn]];
                  }
              }
          }
  
          private void SetupBlock()
          {
              var cftab = new int[257];
  
              cftab[0] = 0;
              Array.Copy(unzftab, 0, cftab, 1, 256);
  
              for (var i = 1; i <= 256; i++)
              {
                  cftab[i] += cftab[i - 1];
              }
  
              for (var i = 0; i <= last; i++)
              {
                  var ch = ll8[i];
                  tt[cftab[ch]] = i;
                  cftab[ch]++;
              }
  
              cftab = null;
  
              tPos = tt[origPtr];
  
              count = 0;
              i2 = 0;
              ch2 = 256; /*-- not a char and not EOF --*/
  
              if (blockRandomised)
              {
                  rNToGo = 0;
                  rTPos = 0;
                  SetupRandPartA();
              }
              else
              {
                  SetupNoRandPartA();
              }
          }
  
          private void SetupRandPartA()
          {
              if (i2 <= last)
              {
                  chPrev = ch2;
                  ch2 = ll8[tPos];
                  tPos = tt[tPos];
                  if (rNToGo == 0)
                  {
                      rNToGo = BZip2Constants.RandomNumbers[rTPos];
                      rTPos++;
                      if (rTPos == 512)
                      {
                          rTPos = 0;
                      }
                  }
                  rNToGo--;
                  ch2 ^= rNToGo == 1 ? 1 : 0;
                  i2++;
  
                  currentChar = ch2;
                  currentState = RAND_PART_B_STATE;
                  mCrc.Update(ch2);
              }
              else
              {
                  EndBlock();
                  InitBlock();
                  SetupBlock();
              }
          }
  
          private void SetupNoRandPartA()
          {
              if (i2 <= last)
              {
                  chPrev = ch2;
                  ch2 = ll8[tPos];
                  tPos = tt[tPos];
                  i2++;
  
                  currentChar = ch2;
                  currentState = NO_RAND_PART_B_STATE;
                  mCrc.Update(ch2);
              }
              else
              {
                  EndBlock();
                  InitBlock();
                  SetupBlock();
              }
          }
  
          private void SetupRandPartB()
          {
              if (ch2 != chPrev)
              {
                  currentState = RAND_PART_A_STATE;
                  count = 1;
                  SetupRandPartA();
              }
              else
              {
                  count++;
                  if (count >= 4)
                  {
                      z = ll8[tPos];
                      tPos = tt[tPos];
                      if (rNToGo == 0)
                      {
                          rNToGo = BZip2Constants.RandomNumbers[rTPos];
                          rTPos++;
                          if (rTPos == 512)
                          {
                              rTPos = 0;
                          }
                      }
                      rNToGo--;
                      z ^= (byte) (rNToGo == 1 ? 1 : 0);
                      j2 = 0;
                      currentState = RAND_PART_C_STATE;
                      SetupRandPartC();
                  }
                  else
                  {
                      currentState = RAND_PART_A_STATE;
                      SetupRandPartA();
                  }
              }
          }
  
          private void SetupRandPartC()
          {
              if (j2 < z)
              {
                  currentChar = ch2;
                  mCrc.Update(ch2);
                  j2++;
              }
              else
              {
                  currentState = RAND_PART_A_STATE;
                  i2++;
                  count = 0;
                  SetupRandPartA();
              }
          }
  
          private void SetupNoRandPartB()
          {
              if (ch2 != chPrev)
              {
                  currentState = NO_RAND_PART_A_STATE;
                  count = 1;
                  SetupNoRandPartA();
              }
              else
              {
                  count++;
                  if (count >= 4)
                  {
                      z = ll8[tPos];
  
gt:                     tPos = tt[tPos];