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 9extern "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 22namespace NCompress { 23namespace NLZMA { 24 25typedef NRangeCoder::CBitEncoder<kNumMoveBits> CMyBitEncoder; 26 27class CBaseState 28{ 29protected: 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 42struct 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 70static const int kNumLogBits = 13; // don't change it ! 71extern Byte g_FastPos[]; 72#endif 73inline 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 90inline 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 111const UInt32 kIfinityPrice = 0xFFFFFFF; 112 113const UInt32 kNumOpts = 1 << 12; 114 115 116class CLiteralEncoder2 117{ 118 CMyBitEncoder _encoders[0x300]; 119public: 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 130class CLiteralEncoder 131{ 132 CLiteralEncoder2 *_coders; 133 int _numPrevBits; 134 int _numPosBits; 135 UInt32 _posMask; 136public: 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 167namespace NLength { 168 169class 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; 176public: 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 182const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols; 183 184class CPriceTableEncoder: public CEncoder 185{ 186 UInt32 _prices[kNumPosStatesEncodingMax][kNumSymbolsTotal]; 187 UInt32 _tableSize; 188 UInt32 _counters[kNumPosStatesEncodingMax]; 189public: 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 213typedef struct _CSeqInStream 214{ 215 ISeqInStream SeqInStream; 216 CMyComPtr<ISequentialInStream> RealStream; 217} CSeqInStream; 218 219 220class 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 418public: 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 466