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)
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

Generated on Mon Apr 19 18:12:34 2004 for Crypto++ by doxygen 1.3.6-20040222