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