Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

# 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         unsigned int symbol;
    00093         union {unsigned int parent, 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, unsigned int nCodes)
    00105 {
    00106         assert(nCodes > 0);
    00107         assert(nCodes <= (unsigned int)(1 << maxCodeBits));
    00108
    00109         unsigned int 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         unsigned int 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         unsigned int leastLeaf = treeBegin, leastInterior = nCodes;
    00126         for (i=nCodes; i<tree.size(); i++)
    00127         {
    00128                 unsigned int 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                 unsigned int 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 {
    00218         InitializeStaticEncoders();
    00219         IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible));
    00220 }
    00221
    00222 Deflator::Deflator(const NameValuePairs &parameters, 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 &parameters)
    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         // m_prev will be initialized automaticly in InsertString
    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                 /*      good lazy nice chain */
    00302                 /* 0 */ {0,    0,  0,    0},  /* store only */
    00303                 /* 1 */ {4,    3,  8,    4},  /* maximum speed, no lazy matches */
    00304                 /* 2 */ {4,    3, 16,    8},
    00305                 /* 3 */ {4,    3, 32,   32},
    00306                 /* 4 */ {4,    4, 16,   16},  /* lazy matches */
    00307                 /* 5 */ {8,   16, 32,   32},
    00308                 /* 6 */ {8,   16, 128, 128},
    00309                 /* 7 */ {8,   32, 128, 256},
    00310                 /* 8 */ {32, 128, 258, 1024},
    00311                 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
    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, unsigned int 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 = STDMIN(length, maxBlockSize-(m_stringStart+m_lookahead));
    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 = 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 unsigned int Deflator::Put2(const byte *str, unsigned int length, int messageEnd, bool blocking)
    00480 {
    00481         if (!blocking)
    00482                 throw BlockingInputOnly("Deflator");
    00483
    00484         unsigned int accepted = 0;
    00485         while (accepted < length)
    00486         {
    00487                 unsigned int newAccepted = FillWindow(str+accepted, length-accepted);
    00488                 ProcessBuffer();
    00489                 // call ProcessUncompressedData() after WritePrestreamHeader()
    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 = 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 = 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 = 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                         // VC60 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
    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 = 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 = 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[] = {    // Order of the bit length code lengths
    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);      // end of block
    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