Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | 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) 00214 : LowFirstBitWriter(attachment) 00215 { 00216 InitializeStaticEncoders(); 00217 IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)); 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 00243 if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE)) 00244 throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size"); 00245 00246 m_log2WindowSize = log2WindowSize; 00247 DSIZE = 1 << m_log2WindowSize; 00248 DMASK = DSIZE - 1; 00249 HSIZE = 1 << m_log2WindowSize; 00250 HMASK = HSIZE - 1; 00251 m_byteBuffer.New(2*DSIZE); 00252 m_head.New(HSIZE); 00253 m_prev.New(DSIZE); 00254 m_matchBuffer.New(DSIZE/2); 00255 00256 SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL)); 00257 Reset(true); 00258 } 00259 00260 void Deflator::Reset(bool forceReset) 00261 { 00262 if (forceReset) 00263 ClearBitBuffer(); 00264 else 00265 assert(m_bitsBuffered == 0); 00266 00267 m_headerWritten = false; 00268 m_matchAvailable = false; 00269 m_dictionaryEnd = 0; 00270 m_stringStart = 0; 00271 m_lookahead = 0; 00272 m_minLookahead = MAX_MATCH; 00273 m_previousMatch = 0; 00274 m_previousLength = 0; 00275 m_matchBufferEnd = 0; 00276 m_blockStart = 0; 00277 m_blockLength = 0; 00278 00279 // m_prev will be initialized automaticly in InsertString 00280 fill(m_head.begin(), m_head.end(), 0); 00281 00282 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 00283 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 00284 } 00285 00286 void Deflator::SetDeflateLevel(int deflateLevel) 00287 { 00288 if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL)) 00289 throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level"); 00290 00291 unsigned int configurationTable[10][4] = { 00292 /* good lazy nice chain */ 00293 /* 0 */ {0, 0, 0, 0}, /* store only */ 00294 /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */ 00295 /* 2 */ {4, 3, 16, 8}, 00296 /* 3 */ {4, 3, 32, 32}, 00297 /* 4 */ {4, 4, 16, 16}, /* lazy matches */ 00298 /* 5 */ {8, 16, 32, 32}, 00299 /* 6 */ {8, 16, 128, 128}, 00300 /* 7 */ {8, 32, 128, 256}, 00301 /* 8 */ {32, 128, 258, 1024}, 00302 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */ 00303 00304 GOOD_MATCH = configurationTable[deflateLevel][0]; 00305 MAX_LAZYLENGTH = configurationTable[deflateLevel][1]; 00306 MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3]; 00307 00308 m_deflateLevel = deflateLevel; 00309 } 00310 00311 unsigned int Deflator::FillWindow(const byte *str, unsigned int length) 00312 { 00313 unsigned int accepted = STDMIN(length, 2*DSIZE-(m_stringStart+m_lookahead)); 00314 00315 if (m_stringStart >= 2*DSIZE - MAX_MATCH) 00316 { 00317 if (m_blockStart < DSIZE) 00318 EndBlock(false); 00319 00320 memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE); 00321 00322 m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE; 00323 assert(m_stringStart >= DSIZE); 00324 m_stringStart -= DSIZE; 00325 assert(m_previousMatch >= DSIZE || m_previousLength < MIN_MATCH); 00326 m_previousMatch -= DSIZE; 00327 assert(m_blockStart >= DSIZE); 00328 m_blockStart -= DSIZE; 00329 00330 unsigned int i; 00331 00332 for (i=0; i<HSIZE; i++) 00333 m_head[i] = SaturatingSubtract(m_head[i], DSIZE); 00334 00335 for (i=0; i<DSIZE; i++) 00336 m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE); 00337 00338 accepted = STDMIN(accepted + DSIZE, length); 00339 } 00340 assert(accepted > 0); 00341 00342 memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted); 00343 m_lookahead += accepted; 00344 return accepted; 00345 } 00346 00347 inline unsigned int Deflator::ComputeHash(const byte *str) const 00348 { 00349 assert(str+3 <= m_byteBuffer + m_stringStart + m_lookahead); 00350 return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK; 00351 } 00352 00353 unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const 00354 { 00355 assert(m_previousLength < MAX_MATCH); 00356 00357 bestMatch = 0; 00358 unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1); 00359 if (m_lookahead <= bestLength) 00360 return 0; 00361 00362 const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead); 00363 unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0; 00364 unsigned int current = m_head[ComputeHash(scan)]; 00365 00366 unsigned int chainLength = MAX_CHAIN_LENGTH; 00367 if (m_previousLength >= GOOD_MATCH) 00368 chainLength >>= 2; 00369 00370 while (current > limit && --chainLength > 0) 00371 { 00372 const byte *match = m_byteBuffer + current; 00373 assert(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead); 00374 if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1]) 00375 { 00376 assert(scan[2] == match[2]); 00377 unsigned int len = std::mismatch(scan+3, scanEnd, match+3).first - scan; 00378 assert(len != bestLength); 00379 if (len > bestLength) 00380 { 00381 bestLength = len; 00382 bestMatch = current; 00383 if (len == (scanEnd - scan)) 00384 break; 00385 } 00386 } 00387 current = m_prev[current & DMASK]; 00388 } 00389 return (bestMatch > 0) ? bestLength : 0; 00390 } 00391 00392 inline void Deflator::InsertString(unsigned int start) 00393 { 00394 unsigned int hash = ComputeHash(m_byteBuffer + start); 00395 m_prev[start & DMASK] = m_head[hash]; 00396 m_head[hash] = start; 00397 } 00398 00399 void Deflator::ProcessBuffer() 00400 { 00401 if (!m_headerWritten) 00402 { 00403 WritePrestreamHeader(); 00404 m_headerWritten = true; 00405 } 00406 00407 if (m_deflateLevel == 0) 00408 { 00409 while (m_lookahead > 0) 00410 { 00411 LiteralByte(m_byteBuffer[m_stringStart++]); 00412 m_lookahead--; 00413 } 00414 return; 00415 } 00416 00417 while (m_lookahead > m_minLookahead) 00418 { 00419 while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead) 00420 InsertString(m_dictionaryEnd++); 00421 00422 if (m_matchAvailable) 00423 { 00424 unsigned int matchPosition, matchLength; 00425 bool usePreviousMatch; 00426 if (m_previousLength >= MAX_LAZYLENGTH) 00427 usePreviousMatch = true; 00428 else 00429 { 00430 matchLength = LongestMatch(matchPosition); 00431 usePreviousMatch = (m_previousLength > 0 && matchLength == 0); 00432 } 00433 if (usePreviousMatch) 00434 { 00435 MatchFound(m_stringStart-1-m_previousMatch, m_previousLength); 00436 m_stringStart += m_previousLength-1; 00437 m_lookahead -= m_previousLength-1; 00438 m_matchAvailable = false; 00439 m_previousLength = 0; 00440 } 00441 else 00442 { 00443 m_previousLength = matchLength; 00444 m_previousMatch = matchPosition; 00445 LiteralByte(m_byteBuffer[m_stringStart-1]); 00446 m_stringStart++; 00447 m_lookahead--; 00448 } 00449 } 00450 else 00451 { 00452 m_previousLength = LongestMatch(m_previousMatch); 00453 m_matchAvailable = true; 00454 m_stringStart++; 00455 m_lookahead--; 00456 } 00457 } 00458 assert(m_stringStart - (m_blockStart+m_blockLength) <= 1); 00459 if (m_minLookahead == 0 && m_matchAvailable) 00460 { 00461 LiteralByte(m_byteBuffer[m_stringStart-1]); 00462 m_matchAvailable = false; 00463 } 00464 } 00465 00466 unsigned int Deflator::Put2(const byte *str, unsigned int length, int messageEnd, bool blocking) 00467 { 00468 if (!blocking) 00469 throw BlockingInputOnly("Deflator"); 00470 00471 unsigned int accepted = 0; 00472 while (accepted < length) 00473 { 00474 unsigned int newAccepted = FillWindow(str+accepted, length-accepted); 00475 ProcessBuffer(); 00476 // call ProcessUncompressedData() after WritePrestreamHeader() 00477 ProcessUncompressedData(str+accepted, newAccepted); 00478 accepted += newAccepted; 00479 } 00480 assert(accepted == length); 00481 00482 if (messageEnd) 00483 { 00484 m_minLookahead = 0; 00485 ProcessBuffer(); 00486 EndBlock(true); 00487 FlushBitBuffer(); 00488 WritePoststreamTail(); 00489 Reset(); 00490 } 00491 00492 Output(0, NULL, 0, messageEnd, blocking); 00493 return 0; 00494 } 00495 00496 bool Deflator::IsolatedFlush(bool hardFlush, bool blocking) 00497 { 00498 if (!blocking) 00499 throw BlockingInputOnly("Deflator"); 00500 00501 m_minLookahead = 0; 00502 ProcessBuffer(); 00503 m_minLookahead = MAX_MATCH; 00504 EndBlock(false); 00505 if (hardFlush) 00506 EncodeBlock(false, STORED); 00507 return false; 00508 } 00509 00510 void Deflator::LiteralByte(byte b) 00511 { 00512 m_matchBuffer[m_matchBufferEnd++].literalCode = b; 00513 m_literalCounts[b]++; 00514 00515 if (m_blockStart+(++m_blockLength) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size()) 00516 EndBlock(false); 00517 } 00518 00519 void Deflator::MatchFound(unsigned int distance, unsigned int length) 00520 { 00521 static const unsigned int lengthCodes[] = { 00522 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 00523 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272, 00524 273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274, 00525 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276, 00526 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 00527 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 00528 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 00529 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 00530 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 00531 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 00532 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 00533 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 00534 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 00535 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 00536 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 00537 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285}; 00538 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}; 00539 static const unsigned int distanceBases[30] = 00540 {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}; 00541 00542 EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++]; 00543 unsigned int lengthCode = lengthCodes[length-3]; 00544 m.literalCode = lengthCode; 00545 m.literalExtra = length - lengthBases[lengthCode-257]; 00546 unsigned int distanceCode = upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1; 00547 m.distanceCode = distanceCode; 00548 m.distanceExtra = distance - distanceBases[distanceCode]; 00549 00550 m_literalCounts[lengthCode]++; 00551 m_distanceCounts[distanceCode]++; 00552 00553 if (m_blockStart+(m_blockLength+=length) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size()) 00554 EndBlock(false); 00555 } 00556 00557 inline unsigned int CodeLengthEncode(const unsigned int *begin, 00558 const unsigned int *end, 00559 const unsigned int *& p, 00560 unsigned int &extraBits, 00561 unsigned int &extraBitsLength) 00562 { 00563 unsigned int v = *p; 00564 if ((end-p) >= 3) 00565 { 00566 const unsigned int *oldp = p; 00567 if (v==0 && p[1]==0 && p[2]==0) 00568 { 00569 for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {} 00570 unsigned int repeat = p - oldp; 00571 if (repeat <= 10) 00572 { 00573 extraBits = repeat-3; 00574 extraBitsLength = 3; 00575 return 17; 00576 } 00577 else 00578 { 00579 extraBits = repeat-11; 00580 extraBitsLength = 7; 00581 return 18; 00582 } 00583 } 00584 else if (p!=begin && v==p[-1] && v==p[1] && v==p[2]) 00585 { 00586 for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {} 00587 unsigned int repeat = p - oldp; 00588 extraBits = repeat-3; 00589 extraBitsLength = 2; 00590 return 16; 00591 } 00592 } 00593 p++; 00594 extraBits = 0; 00595 extraBitsLength = 0; 00596 return v; 00597 } 00598 00599 void Deflator::EncodeBlock(bool eof, unsigned int blockType) 00600 { 00601 PutBits(eof, 1); 00602 PutBits(blockType, 2); 00603 00604 if (blockType == STORED) 00605 { 00606 assert(m_blockStart + m_blockLength <= m_byteBuffer.size()); 00607 FlushBitBuffer(); 00608 AttachedTransformation()->PutWord16(m_blockLength, LITTLE_ENDIAN_ORDER); 00609 AttachedTransformation()->PutWord16(~m_blockLength, LITTLE_ENDIAN_ORDER); 00610 AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength); 00611 } 00612 else 00613 { 00614 if (blockType == DYNAMIC) 00615 { 00616 #if defined(_MSC_VER) && !defined(__MWERKS__) 00617 // VC60 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one 00618 typedef reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt; 00619 #else 00620 typedef reverse_iterator<unsigned int *> RevIt; 00621 #endif 00622 00623 FixedSizeSecBlock<unsigned int, 286> literalCodeLengths; 00624 FixedSizeSecBlock<unsigned int, 30> distanceCodeLengths; 00625 00626 m_literalCounts[256] = 1; 00627 HuffmanEncoder::GenerateCodeLengths(literalCodeLengths, 15, m_literalCounts, 286); 00628 m_dynamicLiteralEncoder.Initialize(literalCodeLengths, 286); 00629 unsigned int hlit = find_if(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (literalCodeLengths.begin()+257); 00630 00631 HuffmanEncoder::GenerateCodeLengths(distanceCodeLengths, 15, m_distanceCounts, 30); 00632 m_dynamicDistanceEncoder.Initialize(distanceCodeLengths, 30); 00633 unsigned int hdist = find_if(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (distanceCodeLengths.begin()+1); 00634 00635 SecBlockWithHint<unsigned int, 286+30> combinedLengths(hlit+257+hdist+1); 00636 memcpy(combinedLengths, literalCodeLengths, (hlit+257)*sizeof(unsigned int)); 00637 memcpy(combinedLengths+hlit+257, distanceCodeLengths, (hdist+1)*sizeof(unsigned int)); 00638 00639 FixedSizeSecBlock<unsigned int, 19> codeLengthCodeCounts, codeLengthCodeLengths; 00640 fill(codeLengthCodeCounts.begin(), codeLengthCodeCounts.end(), 0); 00641 const unsigned int *p = combinedLengths.begin(), *begin = combinedLengths.begin(), *end = combinedLengths.end(); 00642 while (p != end) 00643 { 00644 unsigned int code, extraBits, extraBitsLength; 00645 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 00646 codeLengthCodeCounts[code]++; 00647 } 00648 HuffmanEncoder::GenerateCodeLengths(codeLengthCodeLengths, 7, codeLengthCodeCounts, 19); 00649 HuffmanEncoder codeLengthEncoder(codeLengthCodeLengths, 19); 00650 static const unsigned int border[] = { // Order of the bit length code lengths 00651 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 00652 unsigned int hclen = 19; 00653 while (hclen > 4 && codeLengthCodeLengths[border[hclen-1]] == 0) 00654 hclen--; 00655 hclen -= 4; 00656 00657 PutBits(hlit, 5); 00658 PutBits(hdist, 5); 00659 PutBits(hclen, 4); 00660 00661 for (unsigned int i=0; i<hclen+4; i++) 00662 PutBits(codeLengthCodeLengths[border[i]], 3); 00663 00664 p = combinedLengths.begin(); 00665 while (p != end) 00666 { 00667 unsigned int code, extraBits, extraBitsLength; 00668 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 00669 codeLengthEncoder.Encode(*this, code); 00670 PutBits(extraBits, extraBitsLength); 00671 } 00672 } 00673 00674 static const unsigned int lengthExtraBits[] = { 00675 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 00676 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; 00677 static const unsigned int distanceExtraBits[] = { 00678 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 00679 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 00680 12, 12, 13, 13}; 00681 00682 const HuffmanEncoder &literalEncoder = (blockType == STATIC) ? m_staticLiteralEncoder : m_dynamicLiteralEncoder; 00683 const HuffmanEncoder &distanceEncoder = (blockType == STATIC) ? m_staticDistanceEncoder : m_dynamicDistanceEncoder; 00684 00685 for (unsigned int i=0; i<m_matchBufferEnd; i++) 00686 { 00687 unsigned int literalCode = m_matchBuffer[i].literalCode; 00688 literalEncoder.Encode(*this, literalCode); 00689 if (literalCode >= 257) 00690 { 00691 assert(literalCode <= 285); 00692 PutBits(m_matchBuffer[i].literalExtra, lengthExtraBits[literalCode-257]); 00693 unsigned int distanceCode = m_matchBuffer[i].distanceCode; 00694 distanceEncoder.Encode(*this, distanceCode); 00695 PutBits(m_matchBuffer[i].distanceExtra, distanceExtraBits[distanceCode]); 00696 } 00697 } 00698 literalEncoder.Encode(*this, 256); // end of block 00699 } 00700 } 00701 00702 void Deflator::EndBlock(bool eof) 00703 { 00704 if (m_matchBufferEnd == 0 && !eof) 00705 return; 00706 00707 if (m_deflateLevel == 0) 00708 EncodeBlock(eof, STORED); 00709 else if (m_blockLength < 128) 00710 EncodeBlock(eof, STATIC); 00711 else 00712 { 00713 unsigned int storedLen = 8*(m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered; 00714 StartCounting(); 00715 EncodeBlock(eof, STATIC); 00716 unsigned int staticLen = FinishCounting(); 00717 StartCounting(); 00718 EncodeBlock(eof, DYNAMIC); 00719 unsigned int dynamicLen = FinishCounting(); 00720 00721 if (storedLen <= staticLen && storedLen <= dynamicLen) 00722 EncodeBlock(eof, STORED); 00723 else if (staticLen <= dynamicLen) 00724 EncodeBlock(eof, STATIC); 00725 else 00726 EncodeBlock(eof, DYNAMIC); 00727 } 00728 00729 m_matchBufferEnd = 0; 00730 m_blockStart += m_blockLength; 00731 m_blockLength = 0; 00732 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 00733 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 00734 } 00735 00736 NAMESPACE_END

Generated on Fri Aug 13 09:56:55 2004 for Crypto++ by doxygen 1.3.7