00001
00002
00003
00004
00005
00006
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 {
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;
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 ¶meters, 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 ¶meters)
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
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
00293 {0, 0, 0, 0},
00294 {4, 3, 8, 4},
00295 {4, 3, 16, 8},
00296 {4, 3, 32, 32},
00297 {4, 4, 16, 16},
00298 {8, 16, 32, 32},
00299 {8, 16, 128, 128},
00300 {8, 32, 128, 256},
00301 {32, 128, 258, 1024},
00302 {32, 258, 258, 4096}};
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
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
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[] = {
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);
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