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