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