Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

zdeflate.cpp

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

Generated on Wed Jul 21 19:15:36 2004 for Crypto++ by doxygen 1.3.7-20040704