context: /*  
      This file is part of SevenZipSharpMobile.
  
      SevenZipSharpMobile 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 3 of the License, or
      (at your option) any later version.
  
      SevenZipSharpMobile 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 SevenZipSharpMobile.  If not, see <http://www.gnu.org/licenses/>.
  */
  
  using System;
  using System.Globalization;
  using System.IO;
  using SevenZip.Sdk.Compression.LZ;
  using SevenZip.Sdk.Compression.RangeCoder;
  
  namespace SevenZip.Sdk.Compression.Lzma
  {
      /// <summary>
      /// The LZMA encoder class
      /// </summary>
      public class Encoder : ICoder, ISetCoderProperties, IWriteCoderProperties
      {
          private const int kDefaultDictionaryLogSize = 22;
          private const UInt32 kIfinityPrice = 0xFFFFFFF;
          private const UInt32 kNumFastBytesDefault = 0x20;
  
          private const UInt32 kNumLenSpecSymbols = Base.kNumLowLenSymbols + Base.kNumMidLenSymbols;
  
          private const UInt32 kNumOpts = 1 << 12;
          private const int kPropSize = 5;
          private static readonly Byte[] g_FastPos = new Byte[1 << 11];
  
          private static readonly string[] kMatchFinderIDs =
              {
                  "BT2",
                  "BT4",
              };
  
          private readonly UInt32[] _alignPrices = new UInt32[Base.kAlignTableSize];
          private readonly UInt32[] _distancesPrices = new UInt32[Base.kNumFullDistances << Base.kNumLenToPosStatesBits];
  
          private readonly BitEncoder[] _isMatch = new BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
          private readonly BitEncoder[] _isRep = new BitEncoder[Base.kNumStates];
          private readonly BitEncoder[] _isRep0Long = new BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
          private readonly BitEncoder[] _isRepG0 = new BitEncoder[Base.kNumStates];
          private readonly BitEncoder[] _isRepG1 = new BitEncoder[Base.kNumStates];
          private readonly BitEncoder[] _isRepG2 = new BitEncoder[Base.kNumStates];
  
          private readonly LenPriceTableEncoder _lenEncoder = new LenPriceTableEncoder();
  
          private readonly LiteralEncoder _literalEncoder = new LiteralEncoder();
  
          private readonly UInt32[] _matchDistances = new UInt32[Base.kMatchMaxLen*2 + 2];
          private readonly Optimal[] _optimum = new Optimal[kNumOpts];
          private readonly BitEncoder[] _posEncoders = new BitEncoder[Base.kNumFullDistances - Base.kEndPosModelIndex];
          private readonly BitTreeEncoder[] _posSlotEncoder = new BitTreeEncoder[Base.kNumLenToPosStates];
  
          private readonly UInt32[] _posSlotPrices = new UInt32[1 << (Base.kNumPosSlotBits + Base.kNumLenToPosStatesBits)];
          private readonly RangeCoder.Encoder _rangeEncoder = new RangeCoder.Encoder();
          private readonly UInt32[] _repDistances = new UInt32[Base.kNumRepDistances];
          private readonly LenPriceTableEncoder _repMatchLenEncoder = new LenPriceTableEncoder();
          private readonly Byte[] properties = new Byte[kPropSize];
          private readonly UInt32[] repLens = new UInt32[Base.kNumRepDistances];
          private readonly UInt32[] reps = new UInt32[Base.kNumRepDistances];
          private readonly UInt32[] tempPrices = new UInt32[Base.kNumFullDistances];
          private UInt32 _additionalOffset;
          private UInt32 _alignPriceCount;
  
          private UInt32 _dictionarySize = (1 << kDefaultDictionaryLogSize);
          private UInt32 _dictionarySizePrev = 0xFFFFFFFF;
          private UInt32 _distTableSize = (kDefaultDictionaryLogSize*2);
          private bool _finished;
          private Stream _inStream;
          private UInt32 _longestMatchLength;
          private bool _longestMatchWasFound;
          private IMatchFinder _matchFinder;
  
          private EMatchFinderType _matchFinderType = EMatchFinderType.BT4;
          private UInt32 _matchPriceCount;
  
          private bool _needReleaseMFStream;
          private UInt32 _numDistancePairs;
          private UInt32 _numFastBytes = kNumFastBytesDefault;
          private UInt32 _numFastBytesPrev = 0xFFFFFFFF;
          private int _numLiteralContextBits = 3;
          private int _numLiteralPosStateBits;
          private UInt32 _optimumCurrentIndex;
          private UInt32 _optimumEndIndex;
          private BitTreeEncoder _posAlignEncoder = new BitTreeEncoder(Base.kNumAlignBits);
          private int _posStateBits = 2;
          private UInt32 _posStateMask = (4 - 1);
          private Byte _previousByte;
          private Base.State _state;
          private uint _trainSize;
          private bool _writeEndMark;
          private Int64 nowPos64;
  
          static Encoder()
          {
              const Byte kFastSlots = 22;
              int c = 2;
              g_FastPos[0] = 0;
              g_FastPos[1] = 1;
              for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)
              {
                  UInt32 k = ((UInt32) 1 << ((slotFast >> 1) - 1));
                  for (UInt32 j = 0; j < k; j++, c++)
                      g_FastPos[c] = slotFast;
              }
          }
  
          /// <summary>
          /// Initializes a new instance of the Encoder class
          /// </summary>
          public Encoder()
          {
              for (int i = 0; i < kNumOpts; i++)
                  _optimum[i] = new Optimal();
              for (int i = 0; i < Base.kNumLenToPosStates; i++)
                  _posSlotEncoder[i] = new BitTreeEncoder(Base.kNumPosSlotBits);
          }
  
          #region ICoder Members
  
          /// <summary>
          /// Codes the specified stream
          /// </summary>
          /// <param name="inStream">The input stream</param>
          /// <param name="inSize">The input size</param>
          /// <param name="outSize">The output size</param>
          /// <param name="outStream">The output stream</param>
          /// <param name="progress">The progress callback</param>
          public void Code(Stream inStream, Stream outStream,
                           Int64 inSize, Int64 outSize, ICodeProgress progress)
          {
              _needReleaseMFStream = false;
              try
              {
                  SetStreams(inStream, outStream /*, inSize, outSize*/);
                  while (true)
                  {
                      Int64 processedInSize;
                      Int64 processedOutSize;
                      bool finished;
                      CodeOneBlock(out processedInSize, out processedOutSize, out finished);
                      if (finished)
                          return;
                      if (progress != null)
                      {
                          progress.SetProgress(processedInSize, processedOutSize);
                      }
                  }
              }
              finally
              {
                  ReleaseStreams();
              }
          }
  
          #endregion
  
          #region ISetCoderProperties Members
  
          /// <summary>
          /// Sets the coder properties
          /// </summary>
          /// <param name="propIDs">The property identificators</param>
          /// <param name="properties">The array of properties</param>
          public void SetCoderProperties(CoderPropId[] propIDs, object[] properties)
          {
              for (UInt32 i = 0; i < properties.Length; i++)
              {
                  object prop = properties[i];
                  switch (propIDs[i])
                  {
                      case CoderPropId.NumFastBytes:
                      {
                          if (!(prop is Int32))
                              throw new InvalidParamException();
                          var numFastBytes = (Int32) prop;
                          if (numFastBytes < 5 || numFastBytes > Base.kMatchMaxLen)
                              throw new InvalidParamException();
                          _numFastBytes = (UInt32) numFastBytes;
                          break;
                      }
                      case CoderPropId.Algorithm:
                      {
                          /*
  						if (!(prop is Int32))
  							throw new InvalidParamException();
  						Int32 maximize = (Int32)prop;
  						_fastMode = (maximize == 0);
  						_maxMode = (maximize >= 2);
  						*/
                          break;
                      }
                      case CoderPropId.MatchFinder:
                      {
                          if (!(prop is String))
                              throw new InvalidParamException();
                          EMatchFinderType matchFinderIndexPrev = _matchFinderType;
                          int m = FindMatchFinder(((string) prop).ToUpper(CultureInfo.CurrentCulture));
                          if (m < 0)
                              throw new InvalidParamException();
                          _matchFinderType = (EMatchFinderType) m;
                          if (_matchFinder != null && matchFinderIndexPrev != _matchFinderType)
                          {
                              _dictionarySizePrev = 0xFFFFFFFF;
                              _matchFinder = null;
                          }
                          break;
                      }
                      case CoderPropId.DictionarySize:
                      {
                          const int kDicLogSizeMaxCompress = 30;
                          if (!(prop is Int32))
                              throw new InvalidParamException();
                          ;
                          var dictionarySize = (Int32) prop;
                          if (dictionarySize < (UInt32) (1 << Base.kDicLogSizeMin) ||
                              dictionarySize > (UInt32) (1 << kDicLogSizeMaxCompress))
                              throw new InvalidParamException();
                          _dictionarySize = (UInt32) dictionarySize;
                          int dicLogSize;
                          for (dicLogSize = 0; dicLogSize < (UInt32) kDicLogSizeMaxCompress; dicLogSize++)
                              if (dictionarySize <= ((UInt32) (1) << dicLogSize))
                                  break;
                          _distTableSize = (UInt32) dicLogSize*2;
                          break;
                      }
                      case CoderPropId.PosStateBits:
                      {
                          if (!(prop is Int32))
                              throw new InvalidParamException();
                          var v = (Int32) prop;
                          if (v < 0 || v > (UInt32) Base.kNumPosStatesBitsEncodingMax)
                              throw new InvalidParamException();
                          _posStateBits = v;
                          _posStateMask = (((UInt32) 1) << _posStateBits) - 1;
                          break;
                      }
                      case CoderPropId.LitPosBits:
                      {
                          if (!(prop is Int32))
                              throw new InvalidParamException();
                          var v = (Int32) prop;
                          if (v < 0 || v > Base.kNumLitPosStatesBitsEncodingMax)
                              throw new InvalidParamException();
                          _numLiteralPosStateBits = v;
                          break;
                      }
                      case CoderPropId.LitContextBits:
                      {
                          if (!(prop is Int32))
                              throw new InvalidParamException();
                          var v = (Int32) prop;
                          if (v < 0 || v > Base.kNumLitContextBitsMax)
                              throw new InvalidParamException();
                          ;
                          _numLiteralContextBits = v;
                          break;
                      }
                      case CoderPropId.EndMarker:
                      {
                          if (!(prop is Boolean))
                              throw new InvalidParamException();
                          SetWriteEndMarkerMode((Boolean) prop);
                          break;
                      }
                      default:
                          throw new InvalidParamException();
                  }
              }
          }
  
          #endregion
  
          #region IWriteCoderProperties Members
  
          /// <summary>
          /// Writes the coder properties
          /// </summary>
          /// <param name="outStream">The output stream to write the properties to.</param>
          public void WriteCoderProperties(Stream outStream)
          {
              properties[0] = (Byte) ((_posStateBits*5 + _numLiteralPosStateBits)*9 + _numLiteralContextBits);
              for (int i = 0; i < 4; i++)
                  properties[1 + i] = (Byte) (_dictionarySize >> (8*i));
              outStream.Write(properties, 0, kPropSize);
          }
  
          #endregion
  
          private static UInt32 GetPosSlot(UInt32 pos)
          {
              if (pos < (1 << 11))
                  return g_FastPos[pos];
              if (pos < (1 << 21))
                  return (UInt32) (g_FastPos[pos >> 10] + 20);
              return (UInt32) (g_FastPos[pos >> 20] + 40);
          }
  
          private static UInt32 GetPosSlot2(UInt32 pos)
          {
              if (pos < (1 << 17))
                  return (UInt32) (g_FastPos[pos >> 6] + 12);
              if (pos < (1 << 27))
                  return (UInt32) (g_FastPos[pos >> 16] + 32);
              return (UInt32) (g_FastPos[pos >> 26] + 52);
          }
  
          private void BaseInit()
          {
              _state.Init();
              _previousByte = 0;
              for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
                  _repDistances[i] = 0;
          }
  
          private void Create()
          {
              if (_matchFinder == null)
              {
                  var bt = new BinTree();
                  int numHashBytes = 4;
                  if (_matchFinderType == EMatchFinderType.BT2)
                      numHashBytes = 2;
                  bt.SetType(numHashBytes);
                  _matchFinder = bt;
              }
              _literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
  
              if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
                  return;
              _matchFinder.Create(_dictionarySize, kNumOpts, _numFastBytes, Base.kMatchMaxLen + 1);
              _dictionarySizePrev = _dictionarySize;
              _numFastBytesPrev = _numFastBytes;
          }
  
          private void SetWriteEndMarkerMode(bool writeEndMarker)
          {
              _writeEndMark = writeEndMarker;
          }
  
          private void Init()
          {
              BaseInit();
              _rangeEncoder.Init();
  
              uint i;
              for (i = 0; i < Base.kNumStates; i++)
              {
                  for (uint j = 0; j <= _posStateMask; j++)
                  {
                      uint complexState = (i << Base.kNumPosStatesBitsMax) + j;
                      _isMatch[complexState].Init();
                      _isRep0Long[complexState].Init();
                  }
                  _isRep[i].Init();
                  _isRepG0[i].Init();
                  _isRepG1[i].Init();
                  _isRepG2[i].Init();
              }
              _literalEncoder.Init();
              for (i = 0; i < Base.kNumLenToPosStates; i++)
                  _posSlotEncoder[i].Init();
              for (i = 0; i < Base.kNumFullDistances - Base.kEndPosModelIndex; i++)
                  _posEncoders[i].Init();
  
              _lenEncoder.Init((UInt32) 1 << _posStateBits);
              _repMatchLenEncoder.Init((UInt32) 1 << _posStateBits);
  
              _posAlignEncoder.Init();
  
              _longestMatchWasFound = false;
              _optimumEndIndex = 0;
              _optimumCurrentIndex = 0;
              _additionalOffset = 0;
          }
  
          private void ReadMatchDistances(out UInt32 lenRes, out UInt32 numDistancePairs)
          {
              lenRes = 0;
              numDistancePairs = _matchFinder.GetMatches(_matchDistances);
              if (numDistancePairs > 0)
              {
                  lenRes = _matchDistances[numDistancePairs - 2];
                  if (lenRes == _numFastBytes)
                      lenRes += _matchFinder.GetMatchLen((int) lenRes - 1, _matchDistances[numDistancePairs - 1],
                                                         Base.kMatchMaxLen - lenRes);
              }
              _additionalOffset++;
          }
  
  
          private void MovePos(UInt32 num)
          {
              if (num > 0)
              {
                  _matchFinder.Skip(num);
                  _additionalOffset += num;
              }
          }
  
          private UInt32 GetRepLen1Price(Base.State state, UInt32 posState)
          {
              return _isRepG0[state.Index].GetPrice0() +
                     _isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0();
          }
  
          private UInt32 GetPureRepPrice(UInt32 repIndex, Base.State state, UInt32 posState)
          {
              UInt32 price;
              if (repIndex == 0)
              {
                  price = _isRepG0[state.Index].GetPrice0();
                  price += _isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
              }
              else
              {
                  price = _isRepG0[state.Index].GetPrice1();
                  if (repIndex == 1)
                      price += _isRepG1[state.Index].GetPrice0();
                  else
                  {
                      price += _isRepG1[state.Index].GetPrice1();
                      price += _isRepG2[state.Index].GetPrice(repIndex - 2);
                  }
              }
              return price;
          }
  
          private UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, Base.State state, UInt32 posState)
          {
              UInt32 price = _repMatchLenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
              return price + GetPureRepPrice(repIndex, state, posState);
          }
  
          private UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState)
          {
              UInt32 price;
              UInt32 lenToPosState = Base.GetLenToPosState(len);
              if (pos < Base.kNumFullDistances)
                  price = _distancesPrices[(lenToPosState*Base.kNumFullDistances) + pos];
              else
                  price = _posSlotPrices[(lenToPosState << Base.kNumPosSlotBits) + GetPosSlot2(pos)] +
                          _alignPrices[pos & Base.kAlignMask];
              return price + _lenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
          }
  
          private UInt32 Backward(out UInt32 backRes, UInt32 cur)
          {
              _optimumEndIndex = cur;
              UInt32 posMem = _optimum[cur].PosPrev;
              UInt32 backMem = _optimum[cur].BackPrev;
              do
              {
                  if (_optimum[cur].Prev1IsChar)
                  {
                      _optimum[posMem].MakeAsChar();
                      _optimum[posMem].PosPrev = posMem - 1;
                      if (_optimum[cur].Prev2)
                      {
                          _optimum[posMem - 1].Prev1IsChar = false;
                          _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
                          _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
                      }
                  }
                  UInt32 posPrev = posMem;
                  UInt32 backCur = backMem;
  
                  backMem = _optimum[posPrev].BackPrev;
                  posMem = _optimum[posPrev].PosPrev;
  
                  _optimum[posPrev].BackPrev = backCur;
                  _optimum[posPrev].PosPrev = cur;
                  cur = posPrev;
              } while (cur > 0);
              backRes = _optimum[0].BackPrev;
              _optimumCurrentIndex = _optimum[0].PosPrev;
              return _optimumCurrentIndex;
          }
  
  
          private UInt32 GetOptimum(UInt32 position, out UInt32 backRes)
          {
              if (_optimumEndIndex != _optimumCurrentIndex)
              {
                  UInt32 lenRes = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
                  backRes = _optimum[_optimumCurrentIndex].BackPrev;
                  _optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
                  return lenRes;
              }
              _optimumCurrentIndex = _optimumEndIndex = 0;
  
              UInt32 lenMain, numDistancePairs;
              if (!_longestMatchWasFound)
              {
                  ReadMatchDistances(out lenMain, out numDistancePairs);
              }
              else
              {
                  lenMain = _longestMatchLength;
                  numDistancePairs = _numDistancePairs;
                  _longestMatchWasFound = false;
              }
  
              UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes() + 1;
              if (numAvailableBytes < 2)
              {
                  backRes = 0xFFFFFFFF;
                  return 1;
              }
              if (numAvailableBytes > Base.kMatchMaxLen)
                  numAvailableBytes = Base.kMatchMaxLen;
  
              UInt32 repMaxIndex = 0;
  
              for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
              {
                  reps[i] = _repDistances[i];
                  repLens[i] = _matchFinder.GetMatchLen(0 - 1, reps[i], Base.kMatchMaxLen);
                  if (repLens[i] > repLens[repMaxIndex])
                      repMaxIndex = i;
              }
              if (repLens[repMaxIndex] >= _numFastBytes)
              {
                  backRes = repMaxIndex;
                  UInt32 lenRes = repLens[repMaxIndex];
                  MovePos(lenRes - 1);
                  return lenRes;
              }
  
              if (lenMain >= _numFastBytes)
              {
                  backRes = _matchDistances[numDistancePairs - 1] + Base.kNumRepDistances;
                  MovePos(lenMain - 1);
                  return lenMain;
              }
  
              Byte currentByte = _matchFinder.GetIndexByte(0 - 1);
              Byte matchByte = _matchFinder.GetIndexByte((Int32) (0 - _repDistances[0] - 1 - 1));
  
              if (lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)
              {
                  backRes = 0xFFFFFFFF;
                  return 1;
              }
  
              _optimum[0].State = _state;
  
              UInt32 posState = (position & _posStateMask);
  
              _optimum[1].Price = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0() +
                                  _literalEncoder.GetSubCoder(position, _previousByte).GetPrice(!_state.IsCharState(),
                                                                                                matchByte, currentByte);
              _optimum[1].MakeAsChar();
  
              UInt32 matchPrice = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
              UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();
  
              if (matchByte == currentByte)
              {
                  UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
                  if (shortRepPrice < _optimum[1].Price)
                  {
                      _optimum[1].Price = shortRepPrice;
                      _optimum[1].MakeAsShortRep();
                  }
              }
  
              UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);
  
              if (lenEnd < 2)
              {
                  backRes = _optimum[1].BackPrev;
                  return 1;
              }
  
              _optimum[1].PosPrev = 0;
  
              _optimum[0].Backs0 = reps[0];
              _optimum[0].Backs1 = reps[1];
              _optimum[0].Backs2 = reps[2];
              _optimum[0].Backs3 = reps[3];
  
              UInt32 len = lenEnd;
              do
                  _optimum[len--].Price = kIfinityPrice; while (len >= 2);
  
              for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
              {
                  UInt32 repLen = repLens[i];
                  if (repLen < 2)
                      continue;
                  UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);
                  do
                  {
                      UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);
                      Optimal optimum = _optimum[repLen];
                      if (curAndLenPrice < optimum.Price)
                      {
                          optimum.Price = curAndLenPrice;
                          optimum.PosPrev = 0;
                          optimum.BackPrev = i;
                          optimum.Prev1IsChar = false;
                      }
                  } while (--repLen >= 2);
              }
  
              UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();
  
              len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
              if (len <= lenMain)
              {
                  UInt32 offs = 0;
                  while (len > _matchDistances[offs])
                      offs += 2;
                  for (;; len++)
                  {
                      UInt32 distance = _matchDistances[offs + 1];
                      UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);
                      Optimal optimum = _optimum[len];
                      if (curAndLenPrice < optimum.Price)
                      {
                          optimum.Price = curAndLenPrice;
                          optimum.PosPrev = 0;
                          optimum.BackPrev = distance + Base.kNumRepDistances;
                          optimum.Prev1IsChar = false;
                      }
                      if (len == _matchDistances[offs])
                      {
                          offs += 2;
                          if (offs == numDistancePairs)
                              break;
                      }
                  }
              }
  
              UInt32 cur = 0;
  
              while (true)
              {
                  cur++;
                  if (cur == lenEnd)
                      return Backward(out backRes, cur);
                  UInt32 newLen;
                  ReadMatchDistances(out newLen, out numDistancePairs);
                  if (newLen >= _numFastBytes)
                  {
                      _numDistancePairs = numDistancePairs;
                      _longestMatchLength = newLen;
                      _longestMatchWasFound = true;
                      return Backward(out backRes, cur);
                  }
                  position++;
  
gt:                 UInt32 posPrev = _optimum[cur].PosPrev;