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,
bool detectUncompressible)
00214 :
LowFirstBitWriter(attachment)
00215 {
00216 InitializeStaticEncoders();
00217 IsolatedInitialize(MakeParameters(
"DeflateLevel", deflateLevel)(
"Log2WindowSize", log2WindowSize)(
"DetectUncompressible", detectUncompressible));
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
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
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
00300 {0, 0, 0, 0},
00301 {4, 3, 8, 4},
00302 {4, 3, 16, 8},
00303 {4, 3, 32, 32},
00304 {4, 4, 16, 16},
00305 {8, 16, 32, 32},
00306 {8, 16, 128, 128},
00307 {8, 32, 128, 256},
00308 {32, 128, 258, 1024},
00309 {32, 258, 258, 4096}};
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
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
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[] = {
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);
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