Crypto++
|
00001 // zdeflate.cpp - written and placed in the public domain by Wei Dai 00002 00003 // Many of the algorithms and tables used here came from the deflate implementation 00004 // by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely 00005 // rewrote it in order to fix a bug that I could not figure out. This code 00006 // is less clever, but hopefully more understandable and maintainable. 00007 00008 #include "pch.h" 00009 #include "zdeflate.h" 00010 #include <functional> 00011 00012 #if _MSC_VER >= 1600 00013 // for make_unchecked_array_iterator 00014 #include <iterator> 00015 #endif 00016 00017 NAMESPACE_BEGIN(CryptoPP) 00018 00019 using namespace std; 00020 00021 LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *attachment) 00022 : Filter(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0) 00023 { 00024 } 00025 00026 void LowFirstBitWriter::StartCounting() 00027 { 00028 assert(!m_counting); 00029 m_counting = true; 00030 m_bitCount = 0; 00031 } 00032 00033 unsigned long LowFirstBitWriter::FinishCounting() 00034 { 00035 assert(m_counting); 00036 m_counting = false; 00037 return m_bitCount; 00038 } 00039 00040 void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length) 00041 { 00042 if (m_counting) 00043 m_bitCount += length; 00044 else 00045 { 00046 m_buffer |= value << m_bitsBuffered; 00047 m_bitsBuffered += length; 00048 assert(m_bitsBuffered <= sizeof(unsigned long)*8); 00049 while (m_bitsBuffered >= 8) 00050 { 00051 m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer; 00052 if (m_bytesBuffered == m_outputBuffer.size()) 00053 { 00054 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered); 00055 m_bytesBuffered = 0; 00056 } 00057 m_buffer >>= 8; 00058 m_bitsBuffered -= 8; 00059 } 00060 } 00061 } 00062 00063 void LowFirstBitWriter::FlushBitBuffer() 00064 { 00065 if (m_counting) 00066 m_bitCount += 8*(m_bitsBuffered > 0); 00067 else 00068 { 00069 if (m_bytesBuffered > 0) 00070 { 00071 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered); 00072 m_bytesBuffered = 0; 00073 } 00074 if (m_bitsBuffered > 0) 00075 { 00076 AttachedTransformation()->Put((byte)m_buffer); 00077 m_buffer = 0; 00078 m_bitsBuffered = 0; 00079 } 00080 } 00081 } 00082 00083 void LowFirstBitWriter::ClearBitBuffer() 00084 { 00085 m_buffer = 0; 00086 m_bytesBuffered = 0; 00087 m_bitsBuffered = 0; 00088 } 00089 00090 HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes) 00091 { 00092 Initialize(codeBits, nCodes); 00093 } 00094 00095 struct HuffmanNode 00096 { 00097 size_t symbol; 00098 union {size_t parent; unsigned depth, freq;}; 00099 }; 00100 00101 struct FreqLessThan 00102 { 00103 inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;} 00104 inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;} 00105 // needed for MSVC .NET 2005 00106 inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;} 00107 }; 00108 00109 void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes) 00110 { 00111 assert(nCodes > 0); 00112 assert(nCodes <= ((size_t)1 << maxCodeBits)); 00113 00114 size_t i; 00115 SecBlockWithHint<HuffmanNode, 2*286> tree(nCodes); 00116 for (i=0; i<nCodes; i++) 00117 { 00118 tree[i].symbol = i; 00119 tree[i].freq = codeCounts[i]; 00120 } 00121 sort(tree.begin(), tree.end(), FreqLessThan()); 00122 size_t treeBegin = upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin(); 00123 if (treeBegin == nCodes) 00124 { // special case for no codes 00125 fill(codeBits, codeBits+nCodes, 0); 00126 return; 00127 } 00128 tree.resize(nCodes + nCodes - treeBegin - 1); 00129 00130 size_t leastLeaf = treeBegin, leastInterior = nCodes; 00131 for (i=nCodes; i<tree.size(); i++) 00132 { 00133 size_t least; 00134 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++; 00135 tree[i].freq = tree[least].freq; 00136 tree[least].parent = i; 00137 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++; 00138 tree[i].freq += tree[least].freq; 00139 tree[least].parent = i; 00140 } 00141 00142 tree[tree.size()-1].depth = 0; 00143 if (tree.size() >= 2) 00144 for (i=tree.size()-2; i>=nCodes; i--) 00145 tree[i].depth = tree[tree[i].parent].depth + 1; 00146 unsigned int sum = 0; 00147 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1); 00148 fill(blCount.begin(), blCount.end(), 0); 00149 for (i=treeBegin; i<nCodes; i++) 00150 { 00151 size_t depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1); 00152 blCount[depth]++; 00153 sum += 1 << (maxCodeBits - depth); 00154 } 00155 00156 unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0; 00157 00158 while (overflow--) 00159 { 00160 unsigned int bits = maxCodeBits-1; 00161 while (blCount[bits] == 0) 00162 bits--; 00163 blCount[bits]--; 00164 blCount[bits+1] += 2; 00165 assert(blCount[maxCodeBits] > 0); 00166 blCount[maxCodeBits]--; 00167 } 00168 00169 for (i=0; i<treeBegin; i++) 00170 codeBits[tree[i].symbol] = 0; 00171 unsigned int bits = maxCodeBits; 00172 for (i=treeBegin; i<nCodes; i++) 00173 { 00174 while (blCount[bits] == 0) 00175 bits--; 00176 codeBits[tree[i].symbol] = bits; 00177 blCount[bits]--; 00178 } 00179 assert(blCount[bits] == 0); 00180 } 00181 00182 void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes) 00183 { 00184 assert(nCodes > 0); 00185 unsigned int maxCodeBits = *max_element(codeBits, codeBits+nCodes); 00186 if (maxCodeBits == 0) 00187 return; // assume this object won't be used 00188 00189 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1); 00190 fill(blCount.begin(), blCount.end(), 0); 00191 unsigned int i; 00192 for (i=0; i<nCodes; i++) 00193 blCount[codeBits[i]]++; 00194 00195 code_t code = 0; 00196 SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1); 00197 nextCode[1] = 0; 00198 for (i=2; i<=maxCodeBits; i++) 00199 { 00200 code = (code + blCount[i-1]) << 1; 00201 nextCode[i] = code; 00202 } 00203 assert(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]); 00204 00205 m_valueToCode.resize(nCodes); 00206 for (i=0; i<nCodes; i++) 00207 { 00208 unsigned int len = m_valueToCode[i].len = codeBits[i]; 00209 if (len != 0) 00210 m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len); 00211 } 00212 } 00213 00214 inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const 00215 { 00216 assert(m_valueToCode[value].len > 0); 00217 writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len); 00218 } 00219 00220 Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible) 00221 : LowFirstBitWriter(attachment) 00222 , m_deflateLevel(-1) 00223 { 00224 InitializeStaticEncoders(); 00225 IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible)); 00226 } 00227 00228 Deflator::Deflator(const NameValuePairs ¶meters, BufferedTransformation *attachment) 00229 : LowFirstBitWriter(attachment) 00230 , m_deflateLevel(-1) 00231 { 00232 InitializeStaticEncoders(); 00233 IsolatedInitialize(parameters); 00234 } 00235 00236 void Deflator::InitializeStaticEncoders() 00237 { 00238 unsigned int codeLengths[288]; 00239 fill(codeLengths + 0, codeLengths + 144, 8); 00240 fill(codeLengths + 144, codeLengths + 256, 9); 00241 fill(codeLengths + 256, codeLengths + 280, 7); 00242 fill(codeLengths + 280, codeLengths + 288, 8); 00243 m_staticLiteralEncoder.Initialize(codeLengths, 288); 00244 fill(codeLengths + 0, codeLengths + 32, 5); 00245 m_staticDistanceEncoder.Initialize(codeLengths, 32); 00246 } 00247 00248 void Deflator::IsolatedInitialize(const NameValuePairs ¶meters) 00249 { 00250 int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE); 00251 if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE)) 00252 throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size"); 00253 00254 m_log2WindowSize = log2WindowSize; 00255 DSIZE = 1 << m_log2WindowSize; 00256 DMASK = DSIZE - 1; 00257 HSIZE = 1 << m_log2WindowSize; 00258 HMASK = HSIZE - 1; 00259 m_byteBuffer.New(2*DSIZE); 00260 m_head.New(HSIZE); 00261 m_prev.New(DSIZE); 00262 m_matchBuffer.New(DSIZE/2); 00263 Reset(true); 00264 00265 SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL)); 00266 bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true); 00267 m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0; 00268 } 00269 00270 void Deflator::Reset(bool forceReset) 00271 { 00272 if (forceReset) 00273 ClearBitBuffer(); 00274 else 00275 assert(m_bitsBuffered == 0); 00276 00277 m_headerWritten = false; 00278 m_matchAvailable = false; 00279 m_dictionaryEnd = 0; 00280 m_stringStart = 0; 00281 m_lookahead = 0; 00282 m_minLookahead = MAX_MATCH; 00283 m_matchBufferEnd = 0; 00284 m_blockStart = 0; 00285 m_blockLength = 0; 00286 00287 m_detectCount = 1; 00288 m_detectSkip = 0; 00289 00290 // m_prev will be initialized automaticly in InsertString 00291 fill(m_head.begin(), m_head.end(), 0); 00292 00293 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 00294 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 00295 } 00296 00297 void Deflator::SetDeflateLevel(int deflateLevel) 00298 { 00299 if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL)) 00300 throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level"); 00301 00302 if (deflateLevel == m_deflateLevel) 00303 return; 00304 00305 EndBlock(false); 00306 00307 static const unsigned int configurationTable[10][4] = { 00308 /* good lazy nice chain */ 00309 /* 0 */ {0, 0, 0, 0}, /* store only */ 00310 /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */ 00311 /* 2 */ {4, 3, 16, 8}, 00312 /* 3 */ {4, 3, 32, 32}, 00313 /* 4 */ {4, 4, 16, 16}, /* lazy matches */ 00314 /* 5 */ {8, 16, 32, 32}, 00315 /* 6 */ {8, 16, 128, 128}, 00316 /* 7 */ {8, 32, 128, 256}, 00317 /* 8 */ {32, 128, 258, 1024}, 00318 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */ 00319 00320 GOOD_MATCH = configurationTable[deflateLevel][0]; 00321 MAX_LAZYLENGTH = configurationTable[deflateLevel][1]; 00322 MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3]; 00323 00324 m_deflateLevel = deflateLevel; 00325 } 00326 00327 unsigned int Deflator::FillWindow(const byte *str, size_t length) 00328 { 00329 unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL); 00330 00331 if (m_stringStart >= maxBlockSize - MAX_MATCH) 00332 { 00333 if (m_blockStart < DSIZE) 00334 EndBlock(false); 00335 00336 memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE); 00337 00338 m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE; 00339 assert(m_stringStart >= DSIZE); 00340 m_stringStart -= DSIZE; 00341 assert(!m_matchAvailable || m_previousMatch >= DSIZE); 00342 m_previousMatch -= DSIZE; 00343 assert(m_blockStart >= DSIZE); 00344 m_blockStart -= DSIZE; 00345 00346 unsigned int i; 00347 00348 for (i=0; i<HSIZE; i++) 00349 m_head[i] = SaturatingSubtract(m_head[i], DSIZE); 00350 00351 for (i=0; i<DSIZE; i++) 00352 m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE); 00353 } 00354 00355 assert(maxBlockSize > m_stringStart+m_lookahead); 00356 unsigned int accepted = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length); 00357 assert(accepted > 0); 00358 memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted); 00359 m_lookahead += accepted; 00360 return accepted; 00361 } 00362 00363 inline unsigned int Deflator::ComputeHash(const byte *str) const 00364 { 00365 assert(str+3 <= m_byteBuffer + m_stringStart + m_lookahead); 00366 return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK; 00367 } 00368 00369 unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const 00370 { 00371 assert(m_previousLength < MAX_MATCH); 00372 00373 bestMatch = 0; 00374 unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1); 00375 if (m_lookahead <= bestLength) 00376 return 0; 00377 00378 const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead); 00379 unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0; 00380 unsigned int current = m_head[ComputeHash(scan)]; 00381 00382 unsigned int chainLength = MAX_CHAIN_LENGTH; 00383 if (m_previousLength >= GOOD_MATCH) 00384 chainLength >>= 2; 00385 00386 while (current > limit && --chainLength > 0) 00387 { 00388 const byte *match = m_byteBuffer + current; 00389 assert(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead); 00390 if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1]) 00391 { 00392 assert(scan[2] == match[2]); 00393 unsigned int len = (unsigned int)( 00394 #if defined(_STDEXT_BEGIN) && !(defined(_MSC_VER) && (_MSC_VER < 1400 || _MSC_VER >= 1600)) && !defined(_STLPORT_VERSION) 00395 stdext::unchecked_mismatch 00396 #else 00397 std::mismatch 00398 #endif 00399 #if _MSC_VER >= 1600 00400 (stdext::make_unchecked_array_iterator(scan)+3, stdext::make_unchecked_array_iterator(scanEnd), stdext::make_unchecked_array_iterator(match)+3).first - stdext::make_unchecked_array_iterator(scan)); 00401 #else 00402 (scan+3, scanEnd, match+3).first - scan); 00403 #endif 00404 assert(len != bestLength); 00405 if (len > bestLength) 00406 { 00407 bestLength = len; 00408 bestMatch = current; 00409 if (len == (scanEnd - scan)) 00410 break; 00411 } 00412 } 00413 current = m_prev[current & DMASK]; 00414 } 00415 return (bestMatch > 0) ? bestLength : 0; 00416 } 00417 00418 inline void Deflator::InsertString(unsigned int start) 00419 { 00420 unsigned int hash = ComputeHash(m_byteBuffer + start); 00421 m_prev[start & DMASK] = m_head[hash]; 00422 m_head[hash] = start; 00423 } 00424 00425 void Deflator::ProcessBuffer() 00426 { 00427 if (!m_headerWritten) 00428 { 00429 WritePrestreamHeader(); 00430 m_headerWritten = true; 00431 } 00432 00433 if (m_deflateLevel == 0) 00434 { 00435 m_stringStart += m_lookahead; 00436 m_lookahead = 0; 00437 m_blockLength = m_stringStart - m_blockStart; 00438 m_matchAvailable = false; 00439 return; 00440 } 00441 00442 while (m_lookahead > m_minLookahead) 00443 { 00444 while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead) 00445 InsertString(m_dictionaryEnd++); 00446 00447 if (m_matchAvailable) 00448 { 00449 unsigned int matchPosition, matchLength; 00450 bool usePreviousMatch; 00451 if (m_previousLength >= MAX_LAZYLENGTH) 00452 usePreviousMatch = true; 00453 else 00454 { 00455 matchLength = LongestMatch(matchPosition); 00456 usePreviousMatch = (matchLength == 0); 00457 } 00458 if (usePreviousMatch) 00459 { 00460 MatchFound(m_stringStart-1-m_previousMatch, m_previousLength); 00461 m_stringStart += m_previousLength-1; 00462 m_lookahead -= m_previousLength-1; 00463 m_matchAvailable = false; 00464 } 00465 else 00466 { 00467 m_previousLength = matchLength; 00468 m_previousMatch = matchPosition; 00469 LiteralByte(m_byteBuffer[m_stringStart-1]); 00470 m_stringStart++; 00471 m_lookahead--; 00472 } 00473 } 00474 else 00475 { 00476 m_previousLength = 0; 00477 m_previousLength = LongestMatch(m_previousMatch); 00478 if (m_previousLength) 00479 m_matchAvailable = true; 00480 else 00481 LiteralByte(m_byteBuffer[m_stringStart]); 00482 m_stringStart++; 00483 m_lookahead--; 00484 } 00485 00486 assert(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable); 00487 } 00488 00489 if (m_minLookahead == 0 && m_matchAvailable) 00490 { 00491 LiteralByte(m_byteBuffer[m_stringStart-1]); 00492 m_matchAvailable = false; 00493 } 00494 } 00495 00496 size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking) 00497 { 00498 if (!blocking) 00499 throw BlockingInputOnly("Deflator"); 00500 00501 size_t accepted = 0; 00502 while (accepted < length) 00503 { 00504 unsigned int newAccepted = FillWindow(str+accepted, length-accepted); 00505 ProcessBuffer(); 00506 // call ProcessUncompressedData() after WritePrestreamHeader() 00507 ProcessUncompressedData(str+accepted, newAccepted); 00508 accepted += newAccepted; 00509 } 00510 assert(accepted == length); 00511 00512 if (messageEnd) 00513 { 00514 m_minLookahead = 0; 00515 ProcessBuffer(); 00516 EndBlock(true); 00517 FlushBitBuffer(); 00518 WritePoststreamTail(); 00519 Reset(); 00520 } 00521 00522 Output(0, NULL, 0, messageEnd, blocking); 00523 return 0; 00524 } 00525 00526 bool Deflator::IsolatedFlush(bool hardFlush, bool blocking) 00527 { 00528 if (!blocking) 00529 throw BlockingInputOnly("Deflator"); 00530 00531 m_minLookahead = 0; 00532 ProcessBuffer(); 00533 m_minLookahead = MAX_MATCH; 00534 EndBlock(false); 00535 if (hardFlush) 00536 EncodeBlock(false, STORED); 00537 return false; 00538 } 00539 00540 void Deflator::LiteralByte(byte b) 00541 { 00542 if (m_matchBufferEnd == m_matchBuffer.size()) 00543 EndBlock(false); 00544 00545 m_matchBuffer[m_matchBufferEnd++].literalCode = b; 00546 m_literalCounts[b]++; 00547 m_blockLength++; 00548 } 00549 00550 void Deflator::MatchFound(unsigned int distance, unsigned int length) 00551 { 00552 if (m_matchBufferEnd == m_matchBuffer.size()) 00553 EndBlock(false); 00554 00555 static const unsigned int lengthCodes[] = { 00556 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 00557 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272, 00558 273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274, 00559 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276, 00560 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 00561 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 00562 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 00563 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 00564 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 00565 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 00566 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 00567 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 00568 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 00569 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 00570 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 00571 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285}; 00572 static const unsigned int lengthBases[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258}; 00573 static const unsigned int distanceBases[30] = 00574 {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}; 00575 00576 EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++]; 00577 assert(length >= 3); 00578 unsigned int lengthCode = lengthCodes[length-3]; 00579 m.literalCode = lengthCode; 00580 m.literalExtra = length - lengthBases[lengthCode-257]; 00581 unsigned int distanceCode = (unsigned int)(upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1); 00582 m.distanceCode = distanceCode; 00583 m.distanceExtra = distance - distanceBases[distanceCode]; 00584 00585 m_literalCounts[lengthCode]++; 00586 m_distanceCounts[distanceCode]++; 00587 m_blockLength += length; 00588 } 00589 00590 inline unsigned int CodeLengthEncode(const unsigned int *begin, 00591 const unsigned int *end, 00592 const unsigned int *& p, 00593 unsigned int &extraBits, 00594 unsigned int &extraBitsLength) 00595 { 00596 unsigned int v = *p; 00597 if ((end-p) >= 3) 00598 { 00599 const unsigned int *oldp = p; 00600 if (v==0 && p[1]==0 && p[2]==0) 00601 { 00602 for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {} 00603 unsigned int repeat = (unsigned int)(p - oldp); 00604 if (repeat <= 10) 00605 { 00606 extraBits = repeat-3; 00607 extraBitsLength = 3; 00608 return 17; 00609 } 00610 else 00611 { 00612 extraBits = repeat-11; 00613 extraBitsLength = 7; 00614 return 18; 00615 } 00616 } 00617 else if (p!=begin && v==p[-1] && v==p[1] && v==p[2]) 00618 { 00619 for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {} 00620 unsigned int repeat = (unsigned int)(p - oldp); 00621 extraBits = repeat-3; 00622 extraBitsLength = 2; 00623 return 16; 00624 } 00625 } 00626 p++; 00627 extraBits = 0; 00628 extraBitsLength = 0; 00629 return v; 00630 } 00631 00632 void Deflator::EncodeBlock(bool eof, unsigned int blockType) 00633 { 00634 PutBits(eof, 1); 00635 PutBits(blockType, 2); 00636 00637 if (blockType == STORED) 00638 { 00639 assert(m_blockStart + m_blockLength <= m_byteBuffer.size()); 00640 assert(m_blockLength <= 0xffff); 00641 FlushBitBuffer(); 00642 AttachedTransformation()->PutWord16(m_blockLength, LITTLE_ENDIAN_ORDER); 00643 AttachedTransformation()->PutWord16(~m_blockLength, LITTLE_ENDIAN_ORDER); 00644 AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength); 00645 } 00646 else 00647 { 00648 if (blockType == DYNAMIC) 00649 { 00650 #if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER <= 1300) 00651 // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one 00652 typedef reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt; 00653 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC) 00654 typedef reverse_iterator<unsigned int *, random_access_iterator_tag, unsigned int> RevIt; 00655 #else 00656 typedef reverse_iterator<unsigned int *> RevIt; 00657 #endif 00658 00659 FixedSizeSecBlock<unsigned int, 286> literalCodeLengths; 00660 FixedSizeSecBlock<unsigned int, 30> distanceCodeLengths; 00661 00662 m_literalCounts[256] = 1; 00663 HuffmanEncoder::GenerateCodeLengths(literalCodeLengths, 15, m_literalCounts, 286); 00664 m_dynamicLiteralEncoder.Initialize(literalCodeLengths, 286); 00665 unsigned int hlit = (unsigned int)(find_if(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (literalCodeLengths.begin()+257)); 00666 00667 HuffmanEncoder::GenerateCodeLengths(distanceCodeLengths, 15, m_distanceCounts, 30); 00668 m_dynamicDistanceEncoder.Initialize(distanceCodeLengths, 30); 00669 unsigned int hdist = (unsigned int)(find_if(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (distanceCodeLengths.begin()+1)); 00670 00671 SecBlockWithHint<unsigned int, 286+30> combinedLengths(hlit+257+hdist+1); 00672 memcpy(combinedLengths, literalCodeLengths, (hlit+257)*sizeof(unsigned int)); 00673 memcpy(combinedLengths+hlit+257, distanceCodeLengths, (hdist+1)*sizeof(unsigned int)); 00674 00675 FixedSizeSecBlock<unsigned int, 19> codeLengthCodeCounts, codeLengthCodeLengths; 00676 fill(codeLengthCodeCounts.begin(), codeLengthCodeCounts.end(), 0); 00677 const unsigned int *p = combinedLengths.begin(), *begin = combinedLengths.begin(), *end = combinedLengths.end(); 00678 while (p != end) 00679 { 00680 unsigned int code, extraBits, extraBitsLength; 00681 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 00682 codeLengthCodeCounts[code]++; 00683 } 00684 HuffmanEncoder::GenerateCodeLengths(codeLengthCodeLengths, 7, codeLengthCodeCounts, 19); 00685 HuffmanEncoder codeLengthEncoder(codeLengthCodeLengths, 19); 00686 static const unsigned int border[] = { // Order of the bit length code lengths 00687 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 00688 unsigned int hclen = 19; 00689 while (hclen > 4 && codeLengthCodeLengths[border[hclen-1]] == 0) 00690 hclen--; 00691 hclen -= 4; 00692 00693 PutBits(hlit, 5); 00694 PutBits(hdist, 5); 00695 PutBits(hclen, 4); 00696 00697 for (unsigned int i=0; i<hclen+4; i++) 00698 PutBits(codeLengthCodeLengths[border[i]], 3); 00699 00700 p = combinedLengths.begin(); 00701 while (p != end) 00702 { 00703 unsigned int code, extraBits, extraBitsLength; 00704 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 00705 codeLengthEncoder.Encode(*this, code); 00706 PutBits(extraBits, extraBitsLength); 00707 } 00708 } 00709 00710 static const unsigned int lengthExtraBits[] = { 00711 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 00712 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; 00713 static const unsigned int distanceExtraBits[] = { 00714 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 00715 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 00716 12, 12, 13, 13}; 00717 00718 const HuffmanEncoder &literalEncoder = (blockType == STATIC) ? m_staticLiteralEncoder : m_dynamicLiteralEncoder; 00719 const HuffmanEncoder &distanceEncoder = (blockType == STATIC) ? m_staticDistanceEncoder : m_dynamicDistanceEncoder; 00720 00721 for (unsigned int i=0; i<m_matchBufferEnd; i++) 00722 { 00723 unsigned int literalCode = m_matchBuffer[i].literalCode; 00724 literalEncoder.Encode(*this, literalCode); 00725 if (literalCode >= 257) 00726 { 00727 assert(literalCode <= 285); 00728 PutBits(m_matchBuffer[i].literalExtra, lengthExtraBits[literalCode-257]); 00729 unsigned int distanceCode = m_matchBuffer[i].distanceCode; 00730 distanceEncoder.Encode(*this, distanceCode); 00731 PutBits(m_matchBuffer[i].distanceExtra, distanceExtraBits[distanceCode]); 00732 } 00733 } 00734 literalEncoder.Encode(*this, 256); // end of block 00735 } 00736 } 00737 00738 void Deflator::EndBlock(bool eof) 00739 { 00740 if (m_blockLength == 0 && !eof) 00741 return; 00742 00743 if (m_deflateLevel == 0) 00744 { 00745 EncodeBlock(eof, STORED); 00746 00747 if (m_compressibleDeflateLevel > 0 && ++m_detectCount == m_detectSkip) 00748 { 00749 m_deflateLevel = m_compressibleDeflateLevel; 00750 m_detectCount = 1; 00751 } 00752 } 00753 else 00754 { 00755 unsigned long storedLen = 8*((unsigned long)m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered; 00756 00757 StartCounting(); 00758 EncodeBlock(eof, STATIC); 00759 unsigned long staticLen = FinishCounting(); 00760 00761 unsigned long dynamicLen; 00762 if (m_blockLength < 128 && m_deflateLevel < 8) 00763 dynamicLen = ULONG_MAX; 00764 else 00765 { 00766 StartCounting(); 00767 EncodeBlock(eof, DYNAMIC); 00768 dynamicLen = FinishCounting(); 00769 } 00770 00771 if (storedLen <= staticLen && storedLen <= dynamicLen) 00772 { 00773 EncodeBlock(eof, STORED); 00774 00775 if (m_compressibleDeflateLevel > 0) 00776 { 00777 if (m_detectSkip) 00778 m_deflateLevel = 0; 00779 m_detectSkip = m_detectSkip ? STDMIN(2*m_detectSkip, 128U) : 1; 00780 } 00781 } 00782 else 00783 { 00784 if (staticLen <= dynamicLen) 00785 EncodeBlock(eof, STATIC); 00786 else 00787 EncodeBlock(eof, DYNAMIC); 00788 00789 if (m_compressibleDeflateLevel > 0) 00790 m_detectSkip = 0; 00791 } 00792 } 00793 00794 m_matchBufferEnd = 0; 00795 m_blockStart += m_blockLength; 00796 m_blockLength = 0; 00797 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 00798 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 00799 } 00800 00801 NAMESPACE_END