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

zdeflate.cpp

00001 // zdeflate.cpp - written and placed in the public domain by Wei Dai
00002 
00003 // Many of the algorithms and tables used here came from the deflate implementation
00004 // by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely
00005 // rewrote it in order to fix a bug that I could not figure out. This code
00006 // is less clever, but hopefully more understandable and maintainable.
00007 
00008 #include "pch.h"
00009 #include "zdeflate.h"
00010 #include <functional>
00011 
00012 NAMESPACE_BEGIN(CryptoPP)
00013 
00014 using namespace std;
00015 
00016 LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *attachment)
00017         : Filter(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0)
00018 {
00019 }
00020 
00021 void LowFirstBitWriter::StartCounting()
00022 {
00023         assert(!m_counting);
00024         m_counting = true;
00025         m_bitCount = 0;
00026 }
00027 
00028 unsigned long LowFirstBitWriter::FinishCounting()
00029 {
00030         assert(m_counting);
00031         m_counting = false;
00032         return m_bitCount;
00033 }
00034 
00035 void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length)
00036 {
00037         if (m_counting)
00038                 m_bitCount += length;
00039         else
00040         {
00041                 m_buffer |= value << m_bitsBuffered;
00042                 m_bitsBuffered += length;
00043                 assert(m_bitsBuffered <= sizeof(unsigned long)*8);
00044                 while (m_bitsBuffered >= 8)
00045                 {
00046                         m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;
00047                         if (m_bytesBuffered == m_outputBuffer.size())
00048                         {
00049                                 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
00050                                 m_bytesBuffered = 0;
00051                         }
00052                         m_buffer >>= 8;
00053                         m_bitsBuffered -= 8;
00054                 }
00055         }
00056 }
00057 
00058 void LowFirstBitWriter::FlushBitBuffer()
00059 {
00060         if (m_counting)
00061                 m_bitCount += 8*(m_bitsBuffered > 0);
00062         else
00063         {
00064                 if (m_bytesBuffered > 0)
00065                 {
00066                         AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
00067                         m_bytesBuffered = 0;
00068                 }
00069                 if (m_bitsBuffered > 0)
00070                 {
00071                         AttachedTransformation()->Put((byte)m_buffer);
00072                         m_buffer = 0;
00073                         m_bitsBuffered = 0;
00074                 }
00075         }
00076 }
00077 
00078 void LowFirstBitWriter::ClearBitBuffer()
00079 {
00080         m_buffer = 0;
00081         m_bytesBuffered = 0;
00082         m_bitsBuffered = 0;
00083 }
00084 
00085 HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)
00086 {
00087         Initialize(codeBits, nCodes);
00088 }
00089 
00090 struct HuffmanNode
00091 {
00092         unsigned int symbol;
00093         union {unsigned int parent, depth, freq;};
00094 };
00095 
00096 struct FreqLessThan
00097 {
00098         inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;}
00099         inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;}
00100 };
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

Generated on Tue Oct 26 20:21:01 2004 for Crypto++ by  doxygen 1.3.9.1