From 2bb4ca7209a6b7ed86fd9c90a35c1b29df372c38 Mon Sep 17 00:00:00 2001 From: weidai Date: Thu, 8 Apr 2004 01:28:31 +0000 Subject: add detection of uncompressibilty git-svn-id: svn://svn.code.sf.net/p/cryptopp/code/trunk/c5@156 57ff6487-cd31-0410-9ec3-f628ee90f5f0 --- zdeflate.cpp | 122 ++++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 83 insertions(+), 39 deletions(-) (limited to 'zdeflate.cpp') diff --git a/zdeflate.cpp b/zdeflate.cpp index 98dcad3..b0e9f4b 100644 --- a/zdeflate.cpp +++ b/zdeflate.cpp @@ -210,11 +210,11 @@ inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) con writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len); } -Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize) +Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible) : LowFirstBitWriter(attachment) { InitializeStaticEncoders(); - IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)); + IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible)); } Deflator::Deflator(const NameValuePairs ¶meters, BufferedTransformation *attachment) @@ -239,7 +239,6 @@ void Deflator::InitializeStaticEncoders() void Deflator::IsolatedInitialize(const NameValuePairs ¶meters) { int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE); - if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE)) throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size"); @@ -252,9 +251,11 @@ void Deflator::IsolatedInitialize(const NameValuePairs ¶meters) m_head.New(HSIZE); m_prev.New(DSIZE); m_matchBuffer.New(DSIZE/2); + Reset(true); SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL)); - Reset(true); + bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true); + m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0; } void Deflator::Reset(bool forceReset) @@ -270,12 +271,13 @@ void Deflator::Reset(bool forceReset) m_stringStart = 0; m_lookahead = 0; m_minLookahead = MAX_MATCH; - m_previousMatch = 0; - m_previousLength = 0; m_matchBufferEnd = 0; m_blockStart = 0; m_blockLength = 0; + m_detectCount = 1; + m_detectSkip = 0; + // m_prev will be initialized automaticly in InsertString fill(m_head.begin(), m_head.end(), 0); @@ -288,7 +290,12 @@ void Deflator::SetDeflateLevel(int deflateLevel) if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL)) throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level"); - unsigned int configurationTable[10][4] = { + if (deflateLevel == m_deflateLevel) + return; + + EndBlock(false); + + static const unsigned int configurationTable[10][4] = { /* good lazy nice chain */ /* 0 */ {0, 0, 0, 0}, /* store only */ /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */ @@ -310,9 +317,9 @@ void Deflator::SetDeflateLevel(int deflateLevel) unsigned int Deflator::FillWindow(const byte *str, unsigned int length) { - unsigned int accepted = STDMIN(length, 2*DSIZE-(m_stringStart+m_lookahead)); + unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL); - if (m_stringStart >= 2*DSIZE - MAX_MATCH) + if (m_stringStart >= maxBlockSize - MAX_MATCH) { if (m_blockStart < DSIZE) EndBlock(false); @@ -322,7 +329,7 @@ unsigned int Deflator::FillWindow(const byte *str, unsigned int length) m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE; assert(m_stringStart >= DSIZE); m_stringStart -= DSIZE; - assert(m_previousMatch >= DSIZE || m_previousLength < MIN_MATCH); + assert(!m_matchAvailable || m_previousMatch >= DSIZE); m_previousMatch -= DSIZE; assert(m_blockStart >= DSIZE); m_blockStart -= DSIZE; @@ -334,11 +341,11 @@ unsigned int Deflator::FillWindow(const byte *str, unsigned int length) for (i=0; i 0); + assert(maxBlockSize > m_stringStart+m_lookahead); + unsigned int accepted = STDMIN(length, maxBlockSize-(m_stringStart+m_lookahead)); + assert(accepted > 0); memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted); m_lookahead += accepted; return accepted; @@ -406,11 +413,10 @@ void Deflator::ProcessBuffer() if (m_deflateLevel == 0) { - while (m_lookahead > 0) - { - LiteralByte(m_byteBuffer[m_stringStart++]); - m_lookahead--; - } + m_stringStart += m_lookahead; + m_lookahead = 0; + m_blockLength = m_stringStart - m_blockStart; + m_matchAvailable = false; return; } @@ -428,7 +434,7 @@ void Deflator::ProcessBuffer() else { matchLength = LongestMatch(matchPosition); - usePreviousMatch = (m_previousLength > 0 && matchLength == 0); + usePreviousMatch = (matchLength == 0); } if (usePreviousMatch) { @@ -436,7 +442,6 @@ void Deflator::ProcessBuffer() m_stringStart += m_previousLength-1; m_lookahead -= m_previousLength-1; m_matchAvailable = false; - m_previousLength = 0; } else { @@ -449,13 +454,19 @@ void Deflator::ProcessBuffer() } else { + m_previousLength = 0; m_previousLength = LongestMatch(m_previousMatch); - m_matchAvailable = true; + if (m_previousLength) + m_matchAvailable = true; + else + LiteralByte(m_byteBuffer[m_stringStart]); m_stringStart++; m_lookahead--; } + + assert(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable); } - assert(m_stringStart - (m_blockStart+m_blockLength) <= 1); + if (m_minLookahead == 0 && m_matchAvailable) { LiteralByte(m_byteBuffer[m_stringStart-1]); @@ -509,15 +520,19 @@ bool Deflator::IsolatedFlush(bool hardFlush, bool blocking) void Deflator::LiteralByte(byte b) { + if (m_matchBufferEnd == m_matchBuffer.size()) + EndBlock(false); + m_matchBuffer[m_matchBufferEnd++].literalCode = b; m_literalCounts[b]++; - - if (m_blockStart+(++m_blockLength) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size()) - EndBlock(false); + m_blockLength++; } void Deflator::MatchFound(unsigned int distance, unsigned int length) { + if (m_matchBufferEnd == m_matchBuffer.size()) + EndBlock(false); + static const unsigned int lengthCodes[] = { 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272, @@ -540,6 +555,7 @@ void Deflator::MatchFound(unsigned int distance, unsigned int length) {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++]; + assert(length >= 3); unsigned int lengthCode = lengthCodes[length-3]; m.literalCode = lengthCode; m.literalExtra = length - lengthBases[lengthCode-257]; @@ -549,9 +565,7 @@ void Deflator::MatchFound(unsigned int distance, unsigned int length) m_literalCounts[lengthCode]++; m_distanceCounts[distanceCode]++; - - if (m_blockStart+(m_blockLength+=length) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size()) - EndBlock(false); + m_blockLength += length; } inline unsigned int CodeLengthEncode(const unsigned int *begin, @@ -604,6 +618,7 @@ void Deflator::EncodeBlock(bool eof, unsigned int blockType) if (blockType == STORED) { assert(m_blockStart + m_blockLength <= m_byteBuffer.size()); + assert(m_blockLength <= 0xffff); FlushBitBuffer(); AttachedTransformation()->PutWord16(m_blockLength, LITTLE_ENDIAN_ORDER); AttachedTransformation()->PutWord16(~m_blockLength, LITTLE_ENDIAN_ORDER); @@ -701,29 +716,58 @@ void Deflator::EncodeBlock(bool eof, unsigned int blockType) void Deflator::EndBlock(bool eof) { - if (m_matchBufferEnd == 0 && !eof) + if (m_blockLength == 0 && !eof) return; if (m_deflateLevel == 0) + { EncodeBlock(eof, STORED); - else if (m_blockLength < 128) - EncodeBlock(eof, STATIC); + + if (m_compressibleDeflateLevel > 0 && ++m_detectCount == m_detectSkip) + { + m_deflateLevel = m_compressibleDeflateLevel; + m_detectCount = 1; + } + } else { - unsigned int storedLen = 8*(m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered; + unsigned long storedLen = 8*((unsigned long)m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered; + StartCounting(); EncodeBlock(eof, STATIC); - unsigned int staticLen = FinishCounting(); - StartCounting(); - EncodeBlock(eof, DYNAMIC); - unsigned int dynamicLen = FinishCounting(); + unsigned long staticLen = FinishCounting(); + + unsigned long dynamicLen; + if (m_blockLength < 128 && m_deflateLevel < 8) + dynamicLen = ULONG_MAX; + else + { + StartCounting(); + EncodeBlock(eof, DYNAMIC); + dynamicLen = FinishCounting(); + } if (storedLen <= staticLen && storedLen <= dynamicLen) + { EncodeBlock(eof, STORED); - else if (staticLen <= dynamicLen) - EncodeBlock(eof, STATIC); + + if (m_compressibleDeflateLevel > 0) + { + if (m_detectSkip) + m_deflateLevel = 0; + m_detectSkip = m_detectSkip ? STDMIN(2*m_detectSkip, 128U) : 1; + } + } else - EncodeBlock(eof, DYNAMIC); + { + if (staticLen <= dynamicLen) + EncodeBlock(eof, STATIC); + else + EncodeBlock(eof, DYNAMIC); + + if (m_compressibleDeflateLevel > 0) + m_detectSkip = 0; + } } m_matchBufferEnd = 0; -- cgit v1.2.1