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