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