perl/p7zip
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
upstream
p7zip/CPP/7zip/Compress/DeflateEncoder.cpp
Mario Fetka 855c3e81dd Imported Upstream version 16.02+dfsg
2017-10-11 12:35:36 +02:00

1004 lines
29 KiB
C++
Raw Permalink Blame History

// 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 {
static const unsigned kNumDivPassesMax = 10; // [0, 16); ratio/speed/ram tradeoff; use big value for better compression ratio.
static const UInt32 kNumTables = (1 << kNumDivPassesMax);
static const UInt32 kFixedHuffmanCodeBlockSizeMax = (1 << 8); // [0, (1 << 32)); ratio/speed tradeoff; use big value for better compression ratio.
static const UInt32 kDivideCodeBlockSizeMin = (1 << 7); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio.
static const 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 unsigned kMaxCodeBitLength = 11;
static const unsigned kMaxLevelBitLength = 7;
static const Byte kNoLiteralStatPrice = 11;
static const Byte kNoLenStatPrice = 11;
static const Byte kNoPosStatPrice = 6;
static Byte g_LenSlots[kNumLenSymbolsMax];
static Byte g_FastPos[1 << 9];
class CFastPosInit
{
public:
CFastPosInit()
{
unsigned i;
for (i = 0; i < kNumLenSlots; i++)
{
unsigned c = kLenStart32[i];
unsigned j = 1 << kLenDirectBits32[i];
for (unsigned k = 0; k < j; k++, c++)
g_LenSlots[c] = (Byte)i;
}
const unsigned kFastSlots = 18;
unsigned 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;
}
void CEncProps::Normalize()
{
int level = Level;
if (level < 0) level = 5;
Level = level;
if (algo < 0) algo = (level < 5 ? 0 : 1);
if (fb < 0) fb = (level < 7 ? 32 : (level < 9 ? 64 : 128));
if (btMode < 0) btMode = (algo == 0 ? 0 : 1);
if (mc == 0) mc = (16 + (fb >> 1));
if (numPasses == (UInt32)(Int32)-1) numPasses = (level < 7 ? 1 : (level < 9 ? 3 : 10));
}
void CCoder::SetProps(const CEncProps *props2)
{
CEncProps props = *props2;
props.Normalize();
m_MatchFinderCycles = props.mc;
{
unsigned fb = props.fb;
if (fb < kMatchMinLen)
fb = kMatchMinLen;
if (fb > m_MatchMaxLen)
fb = m_MatchMaxLen;
m_NumFastBytes = fb;
}
_fastMode = (props.algo == 0);
_btMode = (props.btMode != 0);
m_NumDivPasses = props.numPasses;
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;
}
}
CCoder::CCoder(bool deflate64Mode):
m_Deflate64Mode(deflate64Mode),
m_OnePosMatchesMemory(0),
m_DistanceMemory(0),
m_Created(false),
m_Values(0),
m_Tables(0)
{
m_MatchMaxLen = deflate64Mode ? kMatchMaxLen64 : kMatchMaxLen32;
m_NumLenCombinations = deflate64Mode ? kNumLenSymbols64 : kNumLenSymbols32;
m_LenStart = deflate64Mode ? kLenStart64 : kLenStart32;
m_LenDirectBits = deflate64Mode ? kLenDirectBits64 : kLenDirectBits32;
{
CEncProps props;
SetProps(&props);
}
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 = (Byte)(_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 *coderProps, UInt32 numProps)
{
CEncProps props;
for (UInt32 i = 0; i < numProps; i++)
{
const PROPVARIANT &prop = coderProps[i];
PROPID propID = propIDs[i];
if (propID >= NCoderPropID::kReduceSize)
continue;
if (prop.vt != VT_UI4)
return E_INVALIDARG;
UInt32 v = (UInt32)prop.ulVal;
switch (propID)
{
case NCoderPropID::kNumPasses: props.numPasses = v; break;
case NCoderPropID::kNumFastBytes: props.fb = v; break;
case NCoderPropID::kMatchFinderCycles: props.mc = v; break;
case NCoderPropID::kAlgorithm: props.algo = v; break;
case NCoderPropID::kLevel: props.Level = v; break;
case NCoderPropID::kNumThreads: break;
default: return E_INVALIDARG;
}
}
SetProps(&props);
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 lenEnd;
{
const UInt32 numDistancePairs = m_MatchDistances[0];
if (numDistancePairs == 0)
return 1;
const UInt16 *matchDistances = m_MatchDistances + 1;
lenEnd = matchDistances[numDistancePairs - 2];
if (lenEnd > m_NumFastBytes)
{
backRes = matchDistances[numDistancePairs - 1];
MovePos(lenEnd - 1);
return lenEnd;
}
m_Optimum[1].Price = m_LiteralPrices[*(Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) - 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 <= lenEnd; 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;
for (;;)
{
++cur;
if (cur == lenEnd || cur == kNumOptsBase || m_Pos >= kMatchArrayLimit)
return Backward(backRes, cur);
GetMatches();
const UInt16 *matchDistances = m_MatchDistances + 1;
const 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;
{
const UInt32 curAnd1Price = curPrice + m_LiteralPrices[*(Inline_MatchFinder_GetPointerToCurrentPos(&_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;
UInt32 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, unsigned numLevels, UInt32 *freqs)
{
unsigned prevLen = 0xFF;
unsigned nextLen = levels[0];
unsigned count = 0;
unsigned maxCount = 7;
unsigned minCount = 4;
if (nextLen == 0)
{
maxCount = 138;
minCount = 3;
}
for (unsigned n = 0; n < numLevels; n++)
{
unsigned 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, unsigned 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, unsigned numLevels, const Byte *lens, const UInt32 *codes)
{
unsigned prevLen = 0xFF;
unsigned nextLen = levels[0];
unsigned count = 0;
unsigned maxCount = 7;
unsigned minCount = 4;
if (nextLen == 0)
{
maxCount = 138;
minCount = 3;
}
for (unsigned n = 0; n < numLevels; n++)
{
unsigned curLen = nextLen;
nextLen = (n < numLevels - 1) ? levels[n + 1] : 0xFF;
count++;
if (count < maxCount && curLen == nextLen)
continue;
if (count < minCount)
for (unsigned 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_GetPointerToCurrentPos(&_lzInWindow) - 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, unsigned bitPosition)
{
UInt32 price = 0;
do
{
UInt32 nextBitPosition = (bitPosition + kFinalBlockFieldSize + kBlockTypeFieldSize) & 7;
unsigned 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(unsigned 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(unsigned 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(unsigned tableIndex, unsigned 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(unsigned 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);
unsigned i;
const unsigned 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();
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); }
}}}
Reference in New Issue View Git Blame Copy Permalink