- Main Page
- Namespaces
- Classes
- Files

# zdeflate.cpp

    00001 // zdeflate.cpp - written and placed in the public domain by Wei Dai
    00002
    00003 // Many of the algorithms and tables used here came from the deflate implementation
    00004 // by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely
    00005 // rewrote it in order to fix a bug that I could not figure out. This code
    00006 // is less clever, but hopefully more understandable and maintainable.
    00007
    00008 #include "pch.h"
    00009 #include "zdeflate.h"
    00010 #include <functional>
    00011
    00012 NAMESPACE_BEGIN(CryptoPP)
    00013
    00014 using namespace std;
    00015
    00016 LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *attachment)
    00017         : Filter(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0)
    00018 {
    00019 }
    00020
    00021 void LowFirstBitWriter::StartCounting()
    00022 {
    00023         assert(!m_counting);
    00024         m_counting = true;
    00025         m_bitCount = 0;
    00026 }
    00027
    00028 unsigned long LowFirstBitWriter::FinishCounting()
    00029 {
    00030         assert(m_counting);
    00031         m_counting = false;
    00032         return m_bitCount;
    00033 }
    00034
    00035 void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length)
    00036 {
    00037         if (m_counting)
    00038                 m_bitCount += length;
    00039         else
    00040         {
    00041                 m_buffer |= value << m_bitsBuffered;
    00042                 m_bitsBuffered += length;
    00043                 assert(m_bitsBuffered <= sizeof(unsigned long)*8);
    00044                 while (m_bitsBuffered >= 8)
    00045                 {
    00046                         m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;
    00047                         if (m_bytesBuffered == m_outputBuffer.size())
    00048                         {
    00049                                 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
    00050                                 m_bytesBuffered = 0;
    00051                         }
    00052                         m_buffer >>= 8;
    00053                         m_bitsBuffered -= 8;
    00054                 }
    00055         }
    00056 }
    00057
    00058 void LowFirstBitWriter::FlushBitBuffer()
    00059 {
    00060         if (m_counting)
    00061                 m_bitCount += 8*(m_bitsBuffered > 0);
    00062         else
    00063         {
    00064                 if (m_bytesBuffered > 0)
    00065                 {
    00066                         AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
    00067                         m_bytesBuffered = 0;
    00068                 }
    00069                 if (m_bitsBuffered > 0)
    00070                 {
    00071                         AttachedTransformation()->Put((byte)m_buffer);
    00072                         m_buffer = 0;
    00073                         m_bitsBuffered = 0;
    00074                 }
    00075         }
    00076 }
    00077
    00078 void LowFirstBitWriter::ClearBitBuffer()
    00079 {
    00080         m_buffer = 0;
    00081         m_bytesBuffered = 0;
    00082         m_bitsBuffered = 0;
    00083 }
    00084
    00085 HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)
    00086 {
    00087         Initialize(codeBits, nCodes);
    00088 }
    00089
    00090 struct HuffmanNode
    00091 {
    00092         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         // needed for MSVC .NET 2005
    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         {       // special case for no codes
    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;         // assume this object won't be used
    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 &parameters, 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 &parameters)
    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         // m_prev will be initialized automaticly in InsertString
    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                 /*      good lazy nice chain */
    00304                 /* 0 */ {0,    0,  0,    0},  /* store only */
    00305                 /* 1 */ {4,    3,  8,    4},  /* maximum speed, no lazy matches */
    00306                 /* 2 */ {4,    3, 16,    8},
    00307                 /* 3 */ {4,    3, 32,   32},
    00308                 /* 4 */ {4,    4, 16,   16},  /* lazy matches */
    00309                 /* 5 */ {8,   16, 32,   32},
    00310                 /* 6 */ {8,   16, 128, 128},
    00311                 /* 7 */ {8,   32, 128, 256},
    00312                 /* 8 */ {32, 128, 258, 1024},
    00313                 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
    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                 // call ProcessUncompressedData() after WritePrestreamHeader()
    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                         // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
    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[] = {    // Order of the bit length code lengths
    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);      // end of block
    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