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