diff options
Diffstat (limited to 'src/libs/7zip/win/CPP/7zip/Compress/DeflateEncoder.cpp')
| -rw-r--r-- | src/libs/7zip/win/CPP/7zip/Compress/DeflateEncoder.cpp | 986 |
1 files changed, 0 insertions, 986 deletions
diff --git a/src/libs/7zip/win/CPP/7zip/Compress/DeflateEncoder.cpp b/src/libs/7zip/win/CPP/7zip/Compress/DeflateEncoder.cpp deleted file mode 100644 index 35a81cae4..000000000 --- a/src/libs/7zip/win/CPP/7zip/Compress/DeflateEncoder.cpp +++ /dev/null @@ -1,986 +0,0 @@ -// DeflateEncoder.cpp - -#include "StdAfx.h" - -#include "../../../C/Alloc.h" -#include "../../../C/HuffEnc.h" - -#include "Common/ComTry.h" - -#include "DeflateEncoder.h" - -#undef NO_INLINE - -#ifdef _MSC_VER -#define NO_INLINE MY_NO_INLINE -#else -#define NO_INLINE -#endif - -namespace NCompress { -namespace NDeflate { -namespace NEncoder { - -const int kNumDivPassesMax = 10; // [0, 16); ratio/speed/ram tradeoff; use big value for better compression ratio. -const UInt32 kNumTables = (1 << kNumDivPassesMax); - -static UInt32 kFixedHuffmanCodeBlockSizeMax = (1 << 8); // [0, (1 << 32)); ratio/speed tradeoff; use big value for better compression ratio. -static UInt32 kDivideCodeBlockSizeMin = (1 << 7); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio. -static UInt32 kDivideBlockSizeMin = (1 << 6); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio. - -static const UInt32 kMaxUncompressedBlockSize = ((1 << 16) - 1) * 1; // [1, (1 << 32)) -static const UInt32 kMatchArraySize = kMaxUncompressedBlockSize * 10; // [kMatchMaxLen * 2, (1 << 32)) -static const UInt32 kMatchArrayLimit = kMatchArraySize - kMatchMaxLen * 4 * sizeof(UInt16); -static const UInt32 kBlockUncompressedSizeThreshold = kMaxUncompressedBlockSize - - kMatchMaxLen - kNumOpts; - -static const int kMaxCodeBitLength = 11; -static const int kMaxLevelBitLength = 7; - -static Byte kNoLiteralStatPrice = 11; -static Byte kNoLenStatPrice = 11; -static Byte kNoPosStatPrice = 6; - -static Byte g_LenSlots[kNumLenSymbolsMax]; -static Byte g_FastPos[1 << 9]; - -class CFastPosInit -{ -public: - CFastPosInit() - { - int i; - for(i = 0; i < kNumLenSlots; i++) - { - int c = kLenStart32[i]; - int j = 1 << kLenDirectBits32[i]; - for(int k = 0; k < j; k++, c++) - g_LenSlots[c] = (Byte)i; - } - - const int kFastSlots = 18; - int c = 0; - for (Byte slotFast = 0; slotFast < kFastSlots; slotFast++) - { - UInt32 k = (1 << kDistDirectBits[slotFast]); - for (UInt32 j = 0; j < k; j++, c++) - g_FastPos[c] = slotFast; - } - } -}; - -static CFastPosInit g_FastPosInit; - - -inline UInt32 GetPosSlot(UInt32 pos) -{ - if (pos < 0x200) - return g_FastPos[pos]; - return g_FastPos[pos >> 8] + 16; -} - -static void *SzAlloc(void *p, size_t size) { p = p; return MyAlloc(size); } -static void SzFree(void *p, void *address) { p = p; MyFree(address); } -static ISzAlloc g_Alloc = { SzAlloc, SzFree }; - -CCoder::CCoder(bool deflate64Mode): - m_Deflate64Mode(deflate64Mode), - m_NumPasses(1), - m_NumDivPasses(1), - m_NumFastBytes(32), - _fastMode(false), - _btMode(true), - m_OnePosMatchesMemory(0), - m_DistanceMemory(0), - m_Created(false), - m_Values(0), - m_Tables(0), - m_MatchFinderCycles(0) - // m_SetMfPasses(0) -{ - m_MatchMaxLen = deflate64Mode ? kMatchMaxLen64 : kMatchMaxLen32; - m_NumLenCombinations = deflate64Mode ? kNumLenSymbols64 : kNumLenSymbols32; - m_LenStart = deflate64Mode ? kLenStart64 : kLenStart32; - m_LenDirectBits = deflate64Mode ? kLenDirectBits64 : kLenDirectBits32; - MatchFinder_Construct(&_lzInWindow); -} - -HRESULT CCoder::Create() -{ - COM_TRY_BEGIN - if (m_Values == 0) - { - m_Values = (CCodeValue *)MyAlloc((kMaxUncompressedBlockSize) * sizeof(CCodeValue)); - if (m_Values == 0) - return E_OUTOFMEMORY; - } - if (m_Tables == 0) - { - m_Tables = (CTables *)MyAlloc((kNumTables) * sizeof(CTables)); - if (m_Tables == 0) - return E_OUTOFMEMORY; - } - - if (m_IsMultiPass) - { - if (m_OnePosMatchesMemory == 0) - { - m_OnePosMatchesMemory = (UInt16 *)::MidAlloc(kMatchArraySize * sizeof(UInt16)); - if (m_OnePosMatchesMemory == 0) - return E_OUTOFMEMORY; - } - } - else - { - if (m_DistanceMemory == 0) - { - m_DistanceMemory = (UInt16 *)MyAlloc((kMatchMaxLen + 2) * 2 * sizeof(UInt16)); - if (m_DistanceMemory == 0) - return E_OUTOFMEMORY; - m_MatchDistances = m_DistanceMemory; - } - } - - if (!m_Created) - { - _lzInWindow.btMode = _btMode ? 1 : 0; - _lzInWindow.numHashBytes = 3; - if (!MatchFinder_Create(&_lzInWindow, - m_Deflate64Mode ? kHistorySize64 : kHistorySize32, - kNumOpts + kMaxUncompressedBlockSize, - m_NumFastBytes, m_MatchMaxLen - m_NumFastBytes, &g_Alloc)) - return E_OUTOFMEMORY; - if (!m_OutStream.Create(1 << 20)) - return E_OUTOFMEMORY; - } - if (m_MatchFinderCycles != 0) - _lzInWindow.cutValue = m_MatchFinderCycles; - m_Created = true; - return S_OK; - COM_TRY_END -} - -HRESULT CCoder::BaseSetEncoderProperties2(const PROPID *propIDs, const PROPVARIANT *props, UInt32 numProps) -{ - for (UInt32 i = 0; i < numProps; i++) - { - const PROPVARIANT &prop = props[i]; - switch(propIDs[i]) - { - case NCoderPropID::kNumPasses: - if (prop.vt != VT_UI4) - return E_INVALIDARG; - m_NumDivPasses = prop.ulVal; - if (m_NumDivPasses == 0) - m_NumDivPasses = 1; - if (m_NumDivPasses == 1) - m_NumPasses = 1; - else if (m_NumDivPasses <= kNumDivPassesMax) - m_NumPasses = 2; - else - { - m_NumPasses = 2 + (m_NumDivPasses - kNumDivPassesMax); - m_NumDivPasses = kNumDivPassesMax; - } - break; - case NCoderPropID::kNumFastBytes: - if (prop.vt != VT_UI4) - return E_INVALIDARG; - m_NumFastBytes = prop.ulVal; - if(m_NumFastBytes < kMatchMinLen || m_NumFastBytes > m_MatchMaxLen) - return E_INVALIDARG; - break; - case NCoderPropID::kMatchFinderCycles: - { - if (prop.vt != VT_UI4) - return E_INVALIDARG; - m_MatchFinderCycles = prop.ulVal; - break; - } - case NCoderPropID::kAlgorithm: - { - if (prop.vt != VT_UI4) - return E_INVALIDARG; - UInt32 maximize = prop.ulVal; - _fastMode = (maximize == 0); - _btMode = !_fastMode; - break; - } - default: - return E_INVALIDARG; - } - } - return S_OK; -} - -void CCoder::Free() -{ - ::MidFree(m_OnePosMatchesMemory); m_OnePosMatchesMemory = 0; - ::MyFree(m_DistanceMemory); m_DistanceMemory = 0; - ::MyFree(m_Values); m_Values = 0; - ::MyFree(m_Tables); m_Tables = 0; -} - -CCoder::~CCoder() -{ - Free(); - MatchFinder_Free(&_lzInWindow, &g_Alloc); -} - -NO_INLINE void CCoder::GetMatches() -{ - if (m_IsMultiPass) - { - m_MatchDistances = m_OnePosMatchesMemory + m_Pos; - if (m_SecondPass) - { - m_Pos += *m_MatchDistances + 1; - return; - } - } - - UInt32 distanceTmp[kMatchMaxLen * 2 + 3]; - - UInt32 numPairs = (_btMode) ? - Bt3Zip_MatchFinder_GetMatches(&_lzInWindow, distanceTmp): - Hc3Zip_MatchFinder_GetMatches(&_lzInWindow, distanceTmp); - - *m_MatchDistances = (UInt16)numPairs; - - if (numPairs > 0) - { - UInt32 i; - for(i = 0; i < numPairs; i += 2) - { - m_MatchDistances[i + 1] = (UInt16)distanceTmp[i]; - m_MatchDistances[i + 2] = (UInt16)distanceTmp[i + 1]; - } - UInt32 len = distanceTmp[numPairs - 2]; - if (len == m_NumFastBytes && m_NumFastBytes != m_MatchMaxLen) - { - UInt32 numAvail = Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) + 1; - const Byte *pby = Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) - 1; - const Byte *pby2 = pby - (distanceTmp[numPairs - 1] + 1); - if (numAvail > m_MatchMaxLen) - numAvail = m_MatchMaxLen; - for (; len < numAvail && pby[len] == pby2[len]; len++); - m_MatchDistances[i - 1] = (UInt16)len; - } - } - if (m_IsMultiPass) - m_Pos += numPairs + 1; - if (!m_SecondPass) - m_AdditionalOffset++; -} - -void CCoder::MovePos(UInt32 num) -{ - if (!m_SecondPass && num > 0) - { - if (_btMode) - Bt3Zip_MatchFinder_Skip(&_lzInWindow, num); - else - Hc3Zip_MatchFinder_Skip(&_lzInWindow, num); - m_AdditionalOffset += num; - } -} - -static const UInt32 kIfinityPrice = 0xFFFFFFF; - -NO_INLINE UInt32 CCoder::Backward(UInt32 &backRes, UInt32 cur) -{ - m_OptimumEndIndex = cur; - UInt32 posMem = m_Optimum[cur].PosPrev; - UInt16 backMem = m_Optimum[cur].BackPrev; - do - { - UInt32 posPrev = posMem; - UInt16 backCur = backMem; - backMem = m_Optimum[posPrev].BackPrev; - posMem = m_Optimum[posPrev].PosPrev; - m_Optimum[posPrev].BackPrev = backCur; - m_Optimum[posPrev].PosPrev = (UInt16)cur; - cur = posPrev; - } - while(cur > 0); - backRes = m_Optimum[0].BackPrev; - m_OptimumCurrentIndex = m_Optimum[0].PosPrev; - return m_OptimumCurrentIndex; -} - -NO_INLINE UInt32 CCoder::GetOptimal(UInt32 &backRes) -{ - if(m_OptimumEndIndex != m_OptimumCurrentIndex) - { - UInt32 len = m_Optimum[m_OptimumCurrentIndex].PosPrev - m_OptimumCurrentIndex; - backRes = m_Optimum[m_OptimumCurrentIndex].BackPrev; - m_OptimumCurrentIndex = m_Optimum[m_OptimumCurrentIndex].PosPrev; - return len; - } - m_OptimumCurrentIndex = m_OptimumEndIndex = 0; - - GetMatches(); - - UInt32 numDistancePairs = m_MatchDistances[0]; - if(numDistancePairs == 0) - return 1; - - const UInt16 *matchDistances = m_MatchDistances + 1; - UInt32 lenMain = matchDistances[numDistancePairs - 2]; - - if(lenMain > m_NumFastBytes) - { - backRes = matchDistances[numDistancePairs - 1]; - MovePos(lenMain - 1); - return lenMain; - } - m_Optimum[1].Price = m_LiteralPrices[Inline_MatchFinder_GetIndexByte(&_lzInWindow, 0 - m_AdditionalOffset)]; - m_Optimum[1].PosPrev = 0; - - m_Optimum[2].Price = kIfinityPrice; - m_Optimum[2].PosPrev = 1; - - - UInt32 offs = 0; - for(UInt32 i = kMatchMinLen; i <= lenMain; i++) - { - UInt32 distance = matchDistances[offs + 1]; - m_Optimum[i].PosPrev = 0; - m_Optimum[i].BackPrev = (UInt16)distance; - m_Optimum[i].Price = m_LenPrices[i - kMatchMinLen] + m_PosPrices[GetPosSlot(distance)]; - if (i == matchDistances[offs]) - offs += 2; - } - - UInt32 cur = 0; - UInt32 lenEnd = lenMain; - for (;;) - { - ++cur; - if(cur == lenEnd || cur == kNumOptsBase || m_Pos >= kMatchArrayLimit) - return Backward(backRes, cur); - GetMatches(); - matchDistances = m_MatchDistances + 1; - - UInt32 numDistancePairs = m_MatchDistances[0]; - UInt32 newLen = 0; - if(numDistancePairs != 0) - { - newLen = matchDistances[numDistancePairs - 2]; - if(newLen > m_NumFastBytes) - { - UInt32 len = Backward(backRes, cur); - m_Optimum[cur].BackPrev = matchDistances[numDistancePairs - 1]; - m_OptimumEndIndex = cur + newLen; - m_Optimum[cur].PosPrev = (UInt16)m_OptimumEndIndex; - MovePos(newLen - 1); - return len; - } - } - UInt32 curPrice = m_Optimum[cur].Price; - UInt32 curAnd1Price = curPrice + m_LiteralPrices[Inline_MatchFinder_GetIndexByte(&_lzInWindow, cur - m_AdditionalOffset)]; - COptimal &optimum = m_Optimum[cur + 1]; - if (curAnd1Price < optimum.Price) - { - optimum.Price = curAnd1Price; - optimum.PosPrev = (UInt16)cur; - } - if(numDistancePairs == 0) - continue; - while(lenEnd < cur + newLen) - m_Optimum[++lenEnd].Price = kIfinityPrice; - offs = 0; - UInt32 distance = matchDistances[offs + 1]; - curPrice += m_PosPrices[GetPosSlot(distance)]; - for(UInt32 lenTest = kMatchMinLen; ; lenTest++) - { - UInt32 curAndLenPrice = curPrice + m_LenPrices[lenTest - kMatchMinLen]; - COptimal &optimum = m_Optimum[cur + lenTest]; - if (curAndLenPrice < optimum.Price) - { - optimum.Price = curAndLenPrice; - optimum.PosPrev = (UInt16)cur; - optimum.BackPrev = (UInt16)distance; - } - if (lenTest == matchDistances[offs]) - { - offs += 2; - if (offs == numDistancePairs) - break; - curPrice -= m_PosPrices[GetPosSlot(distance)]; - distance = matchDistances[offs + 1]; - curPrice += m_PosPrices[GetPosSlot(distance)]; - } - } - } -} - -UInt32 CCoder::GetOptimalFast(UInt32 &backRes) -{ - GetMatches(); - UInt32 numDistancePairs = m_MatchDistances[0]; - if (numDistancePairs == 0) - return 1; - UInt32 lenMain = m_MatchDistances[numDistancePairs - 1]; - backRes = m_MatchDistances[numDistancePairs]; - MovePos(lenMain - 1); - return lenMain; -} - -void CTables::InitStructures() -{ - UInt32 i; - for(i = 0; i < 256; i++) - litLenLevels[i] = 8; - litLenLevels[i++] = 13; - for(;i < kFixedMainTableSize; i++) - litLenLevels[i] = 5; - for(i = 0; i < kFixedDistTableSize; i++) - distLevels[i] = 5; -} - -NO_INLINE void CCoder::LevelTableDummy(const Byte *levels, int numLevels, UInt32 *freqs) -{ - int prevLen = 0xFF; - int nextLen = levels[0]; - int count = 0; - int maxCount = 7; - int minCount = 4; - if (nextLen == 0) - { - maxCount = 138; - minCount = 3; - } - for (int n = 0; n < numLevels; n++) - { - int curLen = nextLen; - nextLen = (n < numLevels - 1) ? levels[n + 1] : 0xFF; - count++; - if (count < maxCount && curLen == nextLen) - continue; - - if (count < minCount) - freqs[curLen] += (UInt32)count; - else if (curLen != 0) - { - if (curLen != prevLen) - { - freqs[curLen]++; - count--; - } - freqs[kTableLevelRepNumber]++; - } - else if (count <= 10) - freqs[kTableLevel0Number]++; - else - freqs[kTableLevel0Number2]++; - - count = 0; - prevLen = curLen; - - if (nextLen == 0) - { - maxCount = 138; - minCount = 3; - } - else if (curLen == nextLen) - { - maxCount = 6; - minCount = 3; - } - else - { - maxCount = 7; - minCount = 4; - } - } -} - -NO_INLINE void CCoder::WriteBits(UInt32 value, int numBits) -{ - m_OutStream.WriteBits(value, numBits); -} - -#define WRITE_HF2(codes, lens, i) m_OutStream.WriteBits(codes[i], lens[i]) -#define WRITE_HF(i) WriteBits(codes[i], lens[i]) - -NO_INLINE void CCoder::LevelTableCode(const Byte *levels, int numLevels, const Byte *lens, const UInt32 *codes) -{ - int prevLen = 0xFF; - int nextLen = levels[0]; - int count = 0; - int maxCount = 7; - int minCount = 4; - if (nextLen == 0) - { - maxCount = 138; - minCount = 3; - } - for (int n = 0; n < numLevels; n++) - { - int curLen = nextLen; - nextLen = (n < numLevels - 1) ? levels[n + 1] : 0xFF; - count++; - if (count < maxCount && curLen == nextLen) - continue; - - if (count < minCount) - for(int i = 0; i < count; i++) - WRITE_HF(curLen); - else if (curLen != 0) - { - if (curLen != prevLen) - { - WRITE_HF(curLen); - count--; - } - WRITE_HF(kTableLevelRepNumber); - WriteBits(count - 3, 2); - } - else if (count <= 10) - { - WRITE_HF(kTableLevel0Number); - WriteBits(count - 3, 3); - } - else - { - WRITE_HF(kTableLevel0Number2); - WriteBits(count - 11, 7); - } - - count = 0; - prevLen = curLen; - - if (nextLen == 0) - { - maxCount = 138; - minCount = 3; - } - else if (curLen == nextLen) - { - maxCount = 6; - minCount = 3; - } - else - { - maxCount = 7; - minCount = 4; - } - } -} - -NO_INLINE void CCoder::MakeTables(unsigned maxHuffLen) -{ - Huffman_Generate(mainFreqs, mainCodes, m_NewLevels.litLenLevels, kFixedMainTableSize, maxHuffLen); - Huffman_Generate(distFreqs, distCodes, m_NewLevels.distLevels, kDistTableSize64, maxHuffLen); -} - -NO_INLINE UInt32 Huffman_GetPrice(const UInt32 *freqs, const Byte *lens, UInt32 num) -{ - UInt32 price = 0; - UInt32 i; - for (i = 0; i < num; i++) - price += lens[i] * freqs[i]; - return price; -} - -NO_INLINE UInt32 Huffman_GetPrice_Spec(const UInt32 *freqs, const Byte *lens, UInt32 num, const Byte *extraBits, UInt32 extraBase) -{ - return Huffman_GetPrice(freqs, lens, num) + - Huffman_GetPrice(freqs + extraBase, extraBits, num - extraBase); -} - -NO_INLINE UInt32 CCoder::GetLzBlockPrice() const -{ - return - Huffman_GetPrice_Spec(mainFreqs, m_NewLevels.litLenLevels, kFixedMainTableSize, m_LenDirectBits, kSymbolMatch) + - Huffman_GetPrice_Spec(distFreqs, m_NewLevels.distLevels, kDistTableSize64, kDistDirectBits, 0); -} - -NO_INLINE void CCoder::TryBlock() -{ - memset(mainFreqs, 0, sizeof(mainFreqs)); - memset(distFreqs, 0, sizeof(distFreqs)); - - m_ValueIndex = 0; - UInt32 blockSize = BlockSizeRes; - BlockSizeRes = 0; - for (;;) - { - if (m_OptimumCurrentIndex == m_OptimumEndIndex) - { - if (m_Pos >= kMatchArrayLimit || BlockSizeRes >= blockSize || !m_SecondPass && - ((Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) == 0) || m_ValueIndex >= m_ValueBlockSize)) - break; - } - UInt32 pos; - UInt32 len; - if (_fastMode) - len = GetOptimalFast(pos); - else - len = GetOptimal(pos); - CCodeValue &codeValue = m_Values[m_ValueIndex++]; - if (len >= kMatchMinLen) - { - UInt32 newLen = len - kMatchMinLen; - codeValue.Len = (UInt16)newLen; - mainFreqs[kSymbolMatch + g_LenSlots[newLen]]++; - codeValue.Pos = (UInt16)pos; - distFreqs[GetPosSlot(pos)]++; - } - else - { - Byte b = Inline_MatchFinder_GetIndexByte(&_lzInWindow, 0 - m_AdditionalOffset); - mainFreqs[b]++; - codeValue.SetAsLiteral(); - codeValue.Pos = b; - } - m_AdditionalOffset -= len; - BlockSizeRes += len; - } - mainFreqs[kSymbolEndOfBlock]++; - m_AdditionalOffset += BlockSizeRes; - m_SecondPass = true; -} - -NO_INLINE void CCoder::SetPrices(const CLevels &levels) -{ - if (_fastMode) - return; - UInt32 i; - for(i = 0; i < 256; i++) - { - Byte price = levels.litLenLevels[i]; - m_LiteralPrices[i] = ((price != 0) ? price : kNoLiteralStatPrice); - } - - for(i = 0; i < m_NumLenCombinations; i++) - { - UInt32 slot = g_LenSlots[i]; - Byte price = levels.litLenLevels[kSymbolMatch + slot]; - m_LenPrices[i] = (Byte)(((price != 0) ? price : kNoLenStatPrice) + m_LenDirectBits[slot]); - } - - for(i = 0; i < kDistTableSize64; i++) - { - Byte price = levels.distLevels[i]; - m_PosPrices[i] = (Byte)(((price != 0) ? price: kNoPosStatPrice) + kDistDirectBits[i]); - } -} - -NO_INLINE void Huffman_ReverseBits(UInt32 *codes, const Byte *lens, UInt32 num) -{ - for (UInt32 i = 0; i < num; i++) - { - UInt32 x = codes[i]; - x = ((x & 0x5555) << 1) | ((x & 0xAAAA) >> 1); - x = ((x & 0x3333) << 2) | ((x & 0xCCCC) >> 2); - x = ((x & 0x0F0F) << 4) | ((x & 0xF0F0) >> 4); - codes[i] = (((x & 0x00FF) << 8) | ((x & 0xFF00) >> 8)) >> (16 - lens[i]); - } -} - -NO_INLINE void CCoder::WriteBlock() -{ - Huffman_ReverseBits(mainCodes, m_NewLevels.litLenLevels, kFixedMainTableSize); - Huffman_ReverseBits(distCodes, m_NewLevels.distLevels, kDistTableSize64); - - for (UInt32 i = 0; i < m_ValueIndex; i++) - { - const CCodeValue &codeValue = m_Values[i]; - if (codeValue.IsLiteral()) - WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, codeValue.Pos); - else - { - UInt32 len = codeValue.Len; - UInt32 lenSlot = g_LenSlots[len]; - WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, kSymbolMatch + lenSlot); - m_OutStream.WriteBits(len - m_LenStart[lenSlot], m_LenDirectBits[lenSlot]); - UInt32 dist = codeValue.Pos; - UInt32 posSlot = GetPosSlot(dist); - WRITE_HF2(distCodes, m_NewLevels.distLevels, posSlot); - m_OutStream.WriteBits(dist - kDistStart[posSlot], kDistDirectBits[posSlot]); - } - } - WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, kSymbolEndOfBlock); -} - -static UInt32 GetStorePrice(UInt32 blockSize, int bitPosition) -{ - UInt32 price = 0; - do - { - UInt32 nextBitPosition = (bitPosition + kFinalBlockFieldSize + kBlockTypeFieldSize) & 7; - int numBitsForAlign = nextBitPosition > 0 ? (8 - nextBitPosition): 0; - UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1; - price += kFinalBlockFieldSize + kBlockTypeFieldSize + numBitsForAlign + (2 + 2) * 8 + curBlockSize * 8; - bitPosition = 0; - blockSize -= curBlockSize; - } - while(blockSize != 0); - return price; -} - -void CCoder::WriteStoreBlock(UInt32 blockSize, UInt32 additionalOffset, bool finalBlock) -{ - do - { - UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1; - blockSize -= curBlockSize; - WriteBits((finalBlock && (blockSize == 0) ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize); - WriteBits(NBlockType::kStored, kBlockTypeFieldSize); - m_OutStream.FlushByte(); - WriteBits((UInt16)curBlockSize, kStoredBlockLengthFieldSize); - WriteBits((UInt16)~curBlockSize, kStoredBlockLengthFieldSize); - const Byte *data = Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow)- additionalOffset; - for(UInt32 i = 0; i < curBlockSize; i++) - m_OutStream.WriteByte(data[i]); - additionalOffset -= curBlockSize; - } - while(blockSize != 0); -} - -NO_INLINE UInt32 CCoder::TryDynBlock(int tableIndex, UInt32 numPasses) -{ - CTables &t = m_Tables[tableIndex]; - BlockSizeRes = t.BlockSizeRes; - UInt32 posTemp = t.m_Pos; - SetPrices(t); - - for (UInt32 p = 0; p < numPasses; p++) - { - m_Pos = posTemp; - TryBlock(); - unsigned numHuffBits = - (m_ValueIndex > 18000 ? 12 : - (m_ValueIndex > 7000 ? 11 : - (m_ValueIndex > 2000 ? 10 : 9))); - MakeTables(numHuffBits); - SetPrices(m_NewLevels); - } - - (CLevels &)t = m_NewLevels; - - m_NumLitLenLevels = kMainTableSize; - while(m_NumLitLenLevels > kNumLitLenCodesMin && m_NewLevels.litLenLevels[m_NumLitLenLevels - 1] == 0) - m_NumLitLenLevels--; - - m_NumDistLevels = kDistTableSize64; - while(m_NumDistLevels > kNumDistCodesMin && m_NewLevels.distLevels[m_NumDistLevels - 1] == 0) - m_NumDistLevels--; - - UInt32 levelFreqs[kLevelTableSize]; - memset(levelFreqs, 0, sizeof(levelFreqs)); - - LevelTableDummy(m_NewLevels.litLenLevels, m_NumLitLenLevels, levelFreqs); - LevelTableDummy(m_NewLevels.distLevels, m_NumDistLevels, levelFreqs); - - Huffman_Generate(levelFreqs, levelCodes, levelLens, kLevelTableSize, kMaxLevelBitLength); - - m_NumLevelCodes = kNumLevelCodesMin; - for (UInt32 i = 0; i < kLevelTableSize; i++) - { - Byte level = levelLens[kCodeLengthAlphabetOrder[i]]; - if (level > 0 && i >= m_NumLevelCodes) - m_NumLevelCodes = i + 1; - m_LevelLevels[i] = level; - } - - return GetLzBlockPrice() + - Huffman_GetPrice_Spec(levelFreqs, levelLens, kLevelTableSize, kLevelDirectBits, kTableDirectLevels) + - kNumLenCodesFieldSize + kNumDistCodesFieldSize + kNumLevelCodesFieldSize + - m_NumLevelCodes * kLevelFieldSize + kFinalBlockFieldSize + kBlockTypeFieldSize; -} - -NO_INLINE UInt32 CCoder::TryFixedBlock(int tableIndex) -{ - CTables &t = m_Tables[tableIndex]; - BlockSizeRes = t.BlockSizeRes; - m_Pos = t.m_Pos; - m_NewLevels.SetFixedLevels(); - SetPrices(m_NewLevels); - TryBlock(); - return kFinalBlockFieldSize + kBlockTypeFieldSize + GetLzBlockPrice(); -} - -NO_INLINE UInt32 CCoder::GetBlockPrice(int tableIndex, int numDivPasses) -{ - CTables &t = m_Tables[tableIndex]; - t.StaticMode = false; - UInt32 price = TryDynBlock(tableIndex, m_NumPasses); - t.BlockSizeRes = BlockSizeRes; - UInt32 numValues = m_ValueIndex; - UInt32 posTemp = m_Pos; - UInt32 additionalOffsetEnd = m_AdditionalOffset; - - if (m_CheckStatic && m_ValueIndex <= kFixedHuffmanCodeBlockSizeMax) - { - const UInt32 fixedPrice = TryFixedBlock(tableIndex); - t.StaticMode = (fixedPrice < price); - if (t.StaticMode) - price = fixedPrice; - } - - const UInt32 storePrice = GetStorePrice(BlockSizeRes, 0); // bitPosition - t.StoreMode = (storePrice <= price); - if (t.StoreMode) - price = storePrice; - - t.UseSubBlocks = false; - - if (numDivPasses > 1 && numValues >= kDivideCodeBlockSizeMin) - { - CTables &t0 = m_Tables[(tableIndex << 1)]; - (CLevels &)t0 = t; - t0.BlockSizeRes = t.BlockSizeRes >> 1; - t0.m_Pos = t.m_Pos; - UInt32 subPrice = GetBlockPrice((tableIndex << 1), numDivPasses - 1); - - UInt32 blockSize2 = t.BlockSizeRes - t0.BlockSizeRes; - if (t0.BlockSizeRes >= kDivideBlockSizeMin && blockSize2 >= kDivideBlockSizeMin) - { - CTables &t1 = m_Tables[(tableIndex << 1) + 1]; - (CLevels &)t1 = t; - t1.BlockSizeRes = blockSize2; - t1.m_Pos = m_Pos; - m_AdditionalOffset -= t0.BlockSizeRes; - subPrice += GetBlockPrice((tableIndex << 1) + 1, numDivPasses - 1); - t.UseSubBlocks = (subPrice < price); - if (t.UseSubBlocks) - price = subPrice; - } - } - m_AdditionalOffset = additionalOffsetEnd; - m_Pos = posTemp; - return price; -} - -void CCoder::CodeBlock(int tableIndex, bool finalBlock) -{ - CTables &t = m_Tables[tableIndex]; - if (t.UseSubBlocks) - { - CodeBlock((tableIndex << 1), false); - CodeBlock((tableIndex << 1) + 1, finalBlock); - } - else - { - if (t.StoreMode) - WriteStoreBlock(t.BlockSizeRes, m_AdditionalOffset, finalBlock); - else - { - WriteBits((finalBlock ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize); - if (t.StaticMode) - { - WriteBits(NBlockType::kFixedHuffman, kBlockTypeFieldSize); - TryFixedBlock(tableIndex); - int i; - const int kMaxStaticHuffLen = 9; - for (i = 0; i < kFixedMainTableSize; i++) - mainFreqs[i] = (UInt32)1 << (kMaxStaticHuffLen - m_NewLevels.litLenLevels[i]); - for (i = 0; i < kFixedDistTableSize; i++) - distFreqs[i] = (UInt32)1 << (kMaxStaticHuffLen - m_NewLevels.distLevels[i]); - MakeTables(kMaxStaticHuffLen); - } - else - { - if (m_NumDivPasses > 1 || m_CheckStatic) - TryDynBlock(tableIndex, 1); - WriteBits(NBlockType::kDynamicHuffman, kBlockTypeFieldSize); - WriteBits(m_NumLitLenLevels - kNumLitLenCodesMin, kNumLenCodesFieldSize); - WriteBits(m_NumDistLevels - kNumDistCodesMin, kNumDistCodesFieldSize); - WriteBits(m_NumLevelCodes - kNumLevelCodesMin, kNumLevelCodesFieldSize); - - for (UInt32 i = 0; i < m_NumLevelCodes; i++) - WriteBits(m_LevelLevels[i], kLevelFieldSize); - - Huffman_ReverseBits(levelCodes, levelLens, kLevelTableSize); - LevelTableCode(m_NewLevels.litLenLevels, m_NumLitLenLevels, levelLens, levelCodes); - LevelTableCode(m_NewLevels.distLevels, m_NumDistLevels, levelLens, levelCodes); - } - WriteBlock(); - } - m_AdditionalOffset -= t.BlockSizeRes; - } -} - -SRes Read(void *object, void *data, size_t *size) -{ - const UInt32 kStepSize = (UInt32)1 << 31; - UInt32 curSize = ((*size < kStepSize) ? (UInt32)*size : kStepSize); - HRESULT res = ((CSeqInStream *)object)->RealStream->Read(data, curSize, &curSize); - *size = curSize; - return (SRes)res; -} - -HRESULT CCoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 * /* inSize */ , const UInt64 * /* outSize */ , ICompressProgressInfo *progress) -{ - m_CheckStatic = (m_NumPasses != 1 || m_NumDivPasses != 1); - m_IsMultiPass = (m_CheckStatic || (m_NumPasses != 1 || m_NumDivPasses != 1)); - - RINOK(Create()); - - m_ValueBlockSize = (7 << 10) + (1 << 12) * m_NumDivPasses; - - UInt64 nowPos = 0; - - _seqInStream.RealStream = inStream; - _seqInStream.SeqInStream.Read = Read; - _lzInWindow.stream = &_seqInStream.SeqInStream; - - MatchFinder_Init(&_lzInWindow); - m_OutStream.SetStream(outStream); - m_OutStream.Init(); - - CCoderReleaser coderReleaser(this); - - m_OptimumEndIndex = m_OptimumCurrentIndex = 0; - - CTables &t = m_Tables[1]; - t.m_Pos = 0; - t.InitStructures(); - - m_AdditionalOffset = 0; - do - { - t.BlockSizeRes = kBlockUncompressedSizeThreshold; - m_SecondPass = false; - GetBlockPrice(1, m_NumDivPasses); - CodeBlock(1, Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) == 0); - nowPos += m_Tables[1].BlockSizeRes; - if (progress != NULL) - { - UInt64 packSize = m_OutStream.GetProcessedSize(); - RINOK(progress->SetRatioInfo(&nowPos, &packSize)); - } - } - while (Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) != 0); - if (_lzInWindow.result != SZ_OK) - return _lzInWindow.result; - return m_OutStream.Flush(); -} - -HRESULT CCoder::BaseCode(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) -{ - try { return CodeReal(inStream, outStream, inSize, outSize, progress); } - catch(const COutBufferException &e) { return e.ErrorCode; } - catch(...) { return E_FAIL; } -} - -STDMETHODIMP CCOMCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) - { return BaseCode(inStream, outStream, inSize, outSize, progress); } - -STDMETHODIMP CCOMCoder::SetCoderProperties(const PROPID *propIDs, const PROPVARIANT *props, UInt32 numProps) - { return BaseSetEncoderProperties2(propIDs, props, numProps); } - -STDMETHODIMP CCOMCoder64::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) - { return BaseCode(inStream, outStream, inSize, outSize, progress); } - -STDMETHODIMP CCOMCoder64::SetCoderProperties(const PROPID *propIDs, const PROPVARIANT *props, UInt32 numProps) - { return BaseSetEncoderProperties2(propIDs, props, numProps); } - -}}} |