00001
00002
00003
00004
00005
00006
00007
00008 #include "pch.h"
00009 #include "zdeflate.h"
00010 #include <functional>
00011
00012 #if _MSC_VER >= 1600
00013
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
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 {
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;
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
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
00309 {0, 0, 0, 0},
00310 {4, 3, 8, 4},
00311 {4, 3, 16, 8},
00312 {4, 3, 32, 32},
00313 {4, 4, 16, 16},
00314 {8, 16, 32, 32},
00315 {8, 16, 128, 128},
00316 {8, 32, 128, 256},
00317 {32, 128, 258, 1024},
00318 {32, 258, 258, 4096}};
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
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
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[] = {
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);
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