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         size_t symbol;
00093         union {size_t parent; unsigned depth, freq;};
00094 };
00095 
00096 struct FreqLessThan
00097 {
00098         inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;}
00099         inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;}
00100         // needed for MSVC .NET 2005
00101         inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;}
00102 };
00103 
00104 void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes)
00105 {
00106         assert(nCodes > 0);
00107         assert(nCodes <= ((size_t)1 << maxCodeBits));
00108 
00109         size_t i;
00110         SecBlockWithHint<HuffmanNode, 2*286> tree(nCodes);
00111         for (i=0; i<nCodes; i++)
00112         {
00113                 tree[i].symbol = i;
00114                 tree[i].freq = codeCounts[i];
00115         }
00116         sort(tree.begin(), tree.end(), FreqLessThan());
00117         size_t treeBegin = upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin();
00118         if (treeBegin == nCodes)
00119         {       // special case for no codes
00120                 fill(codeBits, codeBits+nCodes, 0);
00121                 return;
00122         }
00123         tree.resize(nCodes + nCodes - treeBegin - 1);
00124 
00125         size_t leastLeaf = treeBegin, leastInterior = nCodes;
00126         for (i=nCodes; i<tree.size(); i++)
00127         {
00128                 size_t least;
00129                 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
00130                 tree[i].freq = tree[least].freq;
00131                 tree[least].parent = i;
00132                 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
00133                 tree[i].freq += tree[least].freq;
00134                 tree[least].parent = i;
00135         }
00136 
00137         tree[tree.size()-1].depth = 0;
00138         if (tree.size() >= 2)
00139                 for (i=tree.size()-2; i>=nCodes; i--)
00140                         tree[i].depth = tree[tree[i].parent].depth + 1;
00141         unsigned int sum = 0;
00142         SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
00143         fill(blCount.begin(), blCount.end(), 0);
00144         for (i=treeBegin; i<nCodes; i++)
00145         {
00146                 size_t depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1);
00147                 blCount[depth]++;
00148                 sum += 1 << (maxCodeBits - depth);
00149         }
00150 
00151         unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0;
00152 
00153         while (overflow--)
00154         {
00155                 unsigned int bits = maxCodeBits-1;
00156                 while (blCount[bits] == 0)
00157                         bits--;
00158                 blCount[bits]--;
00159                 blCount[bits+1] += 2;
00160                 assert(blCount[maxCodeBits] > 0);
00161                 blCount[maxCodeBits]--;
00162         }
00163 
00164         for (i=0; i<treeBegin; i++)
00165                 codeBits[tree[i].symbol] = 0;
00166         unsigned int bits = maxCodeBits;
00167         for (i=treeBegin; i<nCodes; i++)
00168         {
00169                 while (blCount[bits] == 0)
00170                         bits--;
00171                 codeBits[tree[i].symbol] = bits;
00172                 blCount[bits]--;
00173         }
00174         assert(blCount[bits] == 0);
00175 }
00176 
00177 void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)
00178 {
00179         assert(nCodes > 0);
00180         unsigned int maxCodeBits = *max_element(codeBits, codeBits+nCodes);
00181         if (maxCodeBits == 0)
00182                 return;         // assume this object won't be used
00183 
00184         SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
00185         fill(blCount.begin(), blCount.end(), 0);
00186         unsigned int i;
00187         for (i=0; i<nCodes; i++)
00188                 blCount[codeBits[i]]++;
00189 
00190         code_t code = 0;
00191         SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1);
00192         nextCode[1] = 0;
00193         for (i=2; i<=maxCodeBits; i++)
00194         {
00195                 code = (code + blCount[i-1]) << 1;
00196                 nextCode[i] = code;
00197         }
00198         assert(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]);
00199 
00200         m_valueToCode.resize(nCodes);
00201         for (i=0; i<nCodes; i++)
00202         {
00203                 unsigned int len = m_valueToCode[i].len = codeBits[i];
00204                 if (len != 0)
00205                         m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len);
00206         }
00207 }
00208 
00209 inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const
00210 {
00211         assert(m_valueToCode[value].len > 0);
00212         writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len);
00213 }
00214 
00215 Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible)
00216         : LowFirstBitWriter(attachment)
00217 {
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, size_t 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 = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length);
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 = (unsigned int)(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 size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking)
00480 {
00481         if (!blocking)
00482                 throw BlockingInputOnly("Deflator");
00483 
00484         size_t 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 = (unsigned int)(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 = (unsigned int)(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 = (unsigned int)(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 = (unsigned int)(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 = (unsigned int)(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

Generated on Tue Aug 16 08:38:44 2005 for Crypto++ by  doxygen 1.3.9.1