vcs.maemo.org Git - physicsfs/blob - lzma/CPP/7zip/Compress/LZMA/LZMAEncoder.h

   1 // LZMA/Encoder.h
   2
   3 #ifndef __LZMA_ENCODER_H
   4 #define __LZMA_ENCODER_H
   5
   6 #include "../../../Common/MyCom.h"
   7 #include "../../ICoder.h"
   8
   9 extern "C"
  10 {
  11   #include "../../../../C/Alloc.h"
  12   #include "../../../../C/Compress/Lz/MatchFinder.h"
  13   #ifdef COMPRESS_MF_MT
  14   #include "../../../../C/Compress/Lz/MatchFinderMt.h"
  15   #endif
  16 }
  17
  18 #include "../RangeCoder/RangeCoderBitTree.h"
  19
  20 #include "LZMA.h"
  21
  22 namespace NCompress {
  23 namespace NLZMA {
  24
  25 typedef NRangeCoder::CBitEncoder<kNumMoveBits> CMyBitEncoder;
  26
  27 class CBaseState
  28 {
  29 protected:
  30   CState _state;
  31   Byte _previousByte;
  32   UInt32 _repDistances[kNumRepDistances];
  33   void Init()
  34   {
  35     _state.Init();
  36     _previousByte = 0;
  37     for(UInt32 i = 0 ; i < kNumRepDistances; i++)
  38       _repDistances[i] = 0;
  39   }
  40 };
  41
  42 struct COptimal
  43 {
  44   CState State;
  45
  46   bool Prev1IsChar;
  47   bool Prev2;
  48
  49   UInt32 PosPrev2;
  50   UInt32 BackPrev2;
  51
  52   UInt32 Price;
  53   UInt32 PosPrev;         // posNext;
  54   UInt32 BackPrev;
  55   UInt32 Backs[kNumRepDistances];
  56   void MakeAsChar() { BackPrev = UInt32(-1); Prev1IsChar = false; }
  57   void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; }
  58   bool IsShortRep() { return (BackPrev == 0); }
  59 };
  60
  61
  62 // #define LZMA_LOG_BRANCH
  63
  64 #if _MSC_VER >= 1400
  65 // Must give gain in core 2. but slower ~2% on k8.
  66 // #define LZMA_LOG_BSR
  67 #endif
  68
  69 #ifndef LZMA_LOG_BSR
  70 static const int kNumLogBits = 13; // don't change it !
  71 extern Byte g_FastPos[];
  72 #endif
  73 inline UInt32 GetPosSlot(UInt32 pos)
  74 {
  75   #ifdef LZMA_LOG_BSR
  76   if (pos < 2)
  77     return pos;
  78   unsigned long index;
  79   _BitScanReverse(&index, pos);
  80   return (index + index) + ((pos >> (index - 1)) & 1);
  81   #else
  82   if (pos < (1 << kNumLogBits))
  83     return g_FastPos[pos];
  84   if (pos < (1 << (kNumLogBits * 2 - 1)))
  85     return g_FastPos[pos >> (kNumLogBits - 1)] + (kNumLogBits - 1) * 2;
  86   return g_FastPos[pos >> (kNumLogBits - 1) * 2] + (kNumLogBits - 1) * 4;
  87   #endif
  88 }
  89
  90 inline UInt32 GetPosSlot2(UInt32 pos)
  91 {
  92   #ifdef LZMA_LOG_BSR
  93   unsigned long index;
  94   _BitScanReverse(&index, pos);
  95   return (index + index) + ((pos >> (index - 1)) & 1);
  96   #else
  97   #ifdef LZMA_LOG_BRANCH
  98   if (pos < (1 << (kNumLogBits + 6)))
  99     return g_FastPos[pos >> 6] + 12;
 100   if (pos < (1 << (kNumLogBits * 2 + 5)))
 101     return g_FastPos[pos >> (kNumLogBits + 5)] + (kNumLogBits + 5) * 2;
 102   return g_FastPos[pos >> (kNumLogBits * 2 + 4)] + (kNumLogBits * 2 + 4) * 2;
 103   #else
 104   // it's faster with VC6-32bit.
 105   UInt32 s = 6 + ((kNumLogBits - 1) & (UInt32)((Int32)(((1 << (kNumLogBits + 6)) - 1) -  pos) >> 31));
 106   return g_FastPos[pos >> s] + (s * 2);
 107   #endif
 108   #endif
 109 }
 110
 111 const UInt32 kIfinityPrice = 0xFFFFFFF;
 112
 113 const UInt32 kNumOpts = 1 << 12;
 114
 115
 116 class CLiteralEncoder2
 117 {
 118   CMyBitEncoder _encoders[0x300];
 119 public:
 120   void Init()
 121   {
 122     for (int i = 0; i < 0x300; i++)
 123       _encoders[i].Init();
 124   }
 125   void Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol);
 126   void EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, Byte matchByte, Byte symbol);
 127   UInt32 GetPrice(bool matchMode, Byte matchByte, Byte symbol) const;
 128 };
 129
 130 class CLiteralEncoder
 131 {
 132   CLiteralEncoder2 *_coders;
 133   int _numPrevBits;
 134   int _numPosBits;
 135   UInt32 _posMask;
 136 public:
 137   CLiteralEncoder(): _coders(0) {}
 138   ~CLiteralEncoder()  { Free(); }
 139   void Free()
 140   {
 141     MyFree(_coders);
 142     _coders = 0;
 143   }
 144   bool Create(int numPosBits, int numPrevBits)
 145   {
 146     if (_coders == 0 || (numPosBits + numPrevBits) != (_numPrevBits + _numPosBits))
 147     {
 148       Free();
 149       UInt32 numStates = 1 << (numPosBits + numPrevBits);
 150       _coders = (CLiteralEncoder2 *)MyAlloc(numStates * sizeof(CLiteralEncoder2));
 151     }
 152     _numPosBits = numPosBits;
 153     _posMask = (1 << numPosBits) - 1;
 154     _numPrevBits = numPrevBits;
 155     return (_coders != 0);
 156   }
 157   void Init()
 158   {
 159     UInt32 numStates = 1 << (_numPrevBits + _numPosBits);
 160     for (UInt32 i = 0; i < numStates; i++)
 161       _coders[i].Init();
 162   }
 163   CLiteralEncoder2 *GetSubCoder(UInt32 pos, Byte prevByte)
 164     { return &_coders[((pos & _posMask) << _numPrevBits) + (prevByte >> (8 - _numPrevBits))]; }
 165 };
 166
 167 namespace NLength {
 168
 169 class CEncoder
 170 {
 171   CMyBitEncoder _choice;
 172   CMyBitEncoder _choice2;
 173   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumLowBits> _lowCoder[kNumPosStatesEncodingMax];
 174   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumMidBits> _midCoder[kNumPosStatesEncodingMax];
 175   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumHighBits> _highCoder;
 176 public:
 177   void Init(UInt32 numPosStates);
 178   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState);
 179   void SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const;
 180 };
 181
 182 const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols;
 183
 184 class CPriceTableEncoder: public CEncoder
 185 {
 186   UInt32 _prices[kNumPosStatesEncodingMax][kNumSymbolsTotal];
 187   UInt32 _tableSize;
 188   UInt32 _counters[kNumPosStatesEncodingMax];
 189 public:
 190   void SetTableSize(UInt32 tableSize) { _tableSize = tableSize;  }
 191   UInt32 GetPrice(UInt32 symbol, UInt32 posState) const { return _prices[posState][symbol]; }
 192   void UpdateTable(UInt32 posState)
 193   {
 194     SetPrices(posState, _tableSize, _prices[posState]);
 195     _counters[posState] = _tableSize;
 196   }
 197   void UpdateTables(UInt32 numPosStates)
 198   {
 199     for (UInt32 posState = 0; posState < numPosStates; posState++)
 200       UpdateTable(posState);
 201   }
 202   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState, bool updatePrice)
 203   {
 204     CEncoder::Encode(rangeEncoder, symbol, posState);
 205     if (updatePrice)
 206       if (--_counters[posState] == 0)
 207         UpdateTable(posState);
 208   }
 209 };
 210
 211 }
 212
 213 typedef struct _CSeqInStream
 214 {
 215   ISeqInStream SeqInStream;
 216   CMyComPtr<ISequentialInStream> RealStream;
 217 } CSeqInStream;
 218
 219
 220 class CEncoder :
 221   public ICompressCoder,
 222   public ICompressSetOutStream,
 223   public ICompressSetCoderProperties,
 224   public ICompressWriteCoderProperties,
 225   public CBaseState,
 226   public CMyUnknownImp
 227 {
 228   NRangeCoder::CEncoder _rangeEncoder;
 229
 230   IMatchFinder _matchFinder;
 231   void *_matchFinderObj;
 232
 233   #ifdef COMPRESS_MF_MT
 234   Bool _multiThread;
 235   Bool _mtMode;
 236   CMatchFinderMt _matchFinderMt;
 237   #endif
 238
 239   CMatchFinder _matchFinderBase;
 240   #ifdef COMPRESS_MF_MT
 241   Byte _pad1[kMtCacheLineDummy];
 242   #endif
 243
 244   COptimal _optimum[kNumOpts];
 245
 246   CMyBitEncoder _isMatch[kNumStates][NLength::kNumPosStatesEncodingMax];
 247   CMyBitEncoder _isRep[kNumStates];
 248   CMyBitEncoder _isRepG0[kNumStates];
 249   CMyBitEncoder _isRepG1[kNumStates];
 250   CMyBitEncoder _isRepG2[kNumStates];
 251   CMyBitEncoder _isRep0Long[kNumStates][NLength::kNumPosStatesEncodingMax];
 252
 253   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> _posSlotEncoder[kNumLenToPosStates];
 254
 255   CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex];
 256   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumAlignBits> _posAlignEncoder;
 257
 258   NLength::CPriceTableEncoder _lenEncoder;
 259   NLength::CPriceTableEncoder _repMatchLenEncoder;
 260
 261   CLiteralEncoder _literalEncoder;
 262
 263   UInt32 _matchDistances[kMatchMaxLen * 2 + 2 + 1];
 264
 265   bool _fastMode;
 266   // bool _maxMode;
 267   UInt32 _numFastBytes;
 268   UInt32 _longestMatchLength;
 269   UInt32 _numDistancePairs;
 270
 271   UInt32 _additionalOffset;
 272
 273   UInt32 _optimumEndIndex;
 274   UInt32 _optimumCurrentIndex;
 275
 276   bool _longestMatchWasFound;
 277
 278   UInt32 _posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
 279
 280   UInt32 _distancesPrices[kNumLenToPosStates][kNumFullDistances];
 281
 282   UInt32 _alignPrices[kAlignTableSize];
 283   UInt32 _alignPriceCount;
 284
 285   UInt32 _distTableSize;
 286
 287   UInt32 _posStateBits;
 288   UInt32 _posStateMask;
 289   UInt32 _numLiteralPosStateBits;
 290   UInt32 _numLiteralContextBits;
 291
 292   UInt32 _dictionarySize;
 293
 294   UInt32 _matchPriceCount;
 295   UInt64 nowPos64;
 296   bool _finished;
 297   ISequentialInStream *_inStream;
 298
 299   CSeqInStream _seqInStream;
 300
 301   UInt32 _matchFinderCycles;
 302   // int _numSkip
 303
 304   bool _writeEndMark;
 305
 306   bool _needReleaseMFStream;
 307
 308   void ReleaseMatchFinder()
 309   {
 310     _matchFinder.Init = 0;
 311     _seqInStream.RealStream.Release();
 312   }
 313
 314   void ReleaseMFStream()
 315   {
 316     if (_matchFinderObj && _needReleaseMFStream)
 317     {
 318       #ifdef COMPRESS_MF_MT
 319       if (_mtMode)
 320         MatchFinderMt_ReleaseStream(&_matchFinderMt);
 321       #endif
 322       _needReleaseMFStream = false;
 323     }
 324     _seqInStream.RealStream.Release();
 325   }
 326
 327   UInt32 ReadMatchDistances(UInt32 &numDistancePairs);
 328
 329   void MovePos(UInt32 num);
 330   UInt32 GetRepLen1Price(CState state, UInt32 posState) const
 331   {
 332     return _isRepG0[state.Index].GetPrice0() +
 333         _isRep0Long[state.Index][posState].GetPrice0();
 334   }
 335
 336   UInt32 GetPureRepPrice(UInt32 repIndex, CState state, UInt32 posState) const
 337   {
 338     UInt32 price;
 339     if(repIndex == 0)
 340     {
 341       price = _isRepG0[state.Index].GetPrice0();
 342       price += _isRep0Long[state.Index][posState].GetPrice1();
 343     }
 344     else
 345     {
 346       price = _isRepG0[state.Index].GetPrice1();
 347       if (repIndex == 1)
 348         price += _isRepG1[state.Index].GetPrice0();
 349       else
 350       {
 351         price += _isRepG1[state.Index].GetPrice1();
 352         price += _isRepG2[state.Index].GetPrice(repIndex - 2);
 353       }
 354     }
 355     return price;
 356   }
 357   UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, CState state, UInt32 posState) const
 358   {
 359     return _repMatchLenEncoder.GetPrice(len - kMatchMinLen, posState) +
 360         GetPureRepPrice(repIndex, state, posState);
 361   }
 362   /*
 363   UInt32 GetPosLen2Price(UInt32 pos, UInt32 posState) const
 364   {
 365     if (pos >= kNumFullDistances)
 366       return kIfinityPrice;
 367     return _distancesPrices[0][pos] + _lenEncoder.GetPrice(0, posState);
 368   }
 369   UInt32 GetPosLen3Price(UInt32 pos, UInt32 len, UInt32 posState) const
 370   {
 371     UInt32 price;
 372     UInt32 lenToPosState = GetLenToPosState(len);
 373     if (pos < kNumFullDistances)
 374       price = _distancesPrices[lenToPosState][pos];
 375     else
 376       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] +
 377           _alignPrices[pos & kAlignMask];
 378     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);
 379   }
 380   */
 381   UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState) const
 382   {
 383     UInt32 price;
 384     UInt32 lenToPosState = GetLenToPosState(len);
 385     if (pos < kNumFullDistances)
 386       price = _distancesPrices[lenToPosState][pos];
 387     else
 388       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] +
 389           _alignPrices[pos & kAlignMask];
 390     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);
 391   }
 392
 393   UInt32 Backward(UInt32 &backRes, UInt32 cur);
 394   UInt32 GetOptimum(UInt32 position, UInt32 &backRes);
 395   UInt32 GetOptimumFast(UInt32 &backRes);
 396
 397   void FillDistancesPrices();
 398   void FillAlignPrices();
 399
 400   void ReleaseStreams()
 401   {
 402     ReleaseMFStream();
 403     ReleaseOutStream();
 404   }
 405
 406   HRESULT Flush(UInt32 nowPos);
 407   class CCoderReleaser
 408   {
 409     CEncoder *_coder;
 410   public:
 411     CCoderReleaser(CEncoder *coder): _coder(coder) {}
 412     ~CCoderReleaser() { _coder->ReleaseStreams(); }
 413   };
 414   friend class CCoderReleaser;
 415
 416   void WriteEndMarker(UInt32 posState);
 417
 418 public:
 419   CEncoder();
 420   void SetWriteEndMarkerMode(bool writeEndMarker)
 421     { _writeEndMark= writeEndMarker; }
 422
 423   HRESULT Create();
 424
 425   MY_UNKNOWN_IMP3(
 426       ICompressSetOutStream,
 427       ICompressSetCoderProperties,
 428       ICompressWriteCoderProperties
 429       )
 430
 431   HRESULT Init();
 432
 433   // ICompressCoder interface
 434   HRESULT SetStreams(ISequentialInStream *inStream,
 435       ISequentialOutStream *outStream,
 436       const UInt64 *inSize, const UInt64 *outSize);
 437   HRESULT CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished);
 438
 439   HRESULT CodeReal(ISequentialInStream *inStream,
 440       ISequentialOutStream *outStream,
 441       const UInt64 *inSize, const UInt64 *outSize,
 442       ICompressProgressInfo *progress);
 443
 444   // ICompressCoder interface
 445   STDMETHOD(Code)(ISequentialInStream *inStream,
 446       ISequentialOutStream *outStream,
 447       const UInt64 *inSize, const UInt64 *outSize,
 448       ICompressProgressInfo *progress);
 449
 450   // ICompressSetCoderProperties2
 451   STDMETHOD(SetCoderProperties)(const PROPID *propIDs,
 452       const PROPVARIANT *properties, UInt32 numProperties);
 453
 454   // ICompressWriteCoderProperties
 455   STDMETHOD(WriteCoderProperties)(ISequentialOutStream *outStream);
 456
 457   STDMETHOD(SetOutStream)(ISequentialOutStream *outStream);
 458   STDMETHOD(ReleaseOutStream)();
 459
 460   virtual ~CEncoder();
 461 };
 462
 463 }}
 464
 465 #endif