Crypto++ 8.2
Free C&
zdeflate.cpp
1// zdeflate.cpp - originally written and placed in the public domain by Wei Dai
2
3// Many of the algorithms and tables used here came from the deflate implementation
4// by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely
5// rewrote it in order to fix a bug that I could not figure out. This code
6// is less clever, but hopefully more understandable and maintainable.
7
8#include "pch.h"
9#include "zdeflate.h"
10#include "stdcpp.h"
11#include "misc.h"
12
13NAMESPACE_BEGIN(CryptoPP)
14
15#if (defined(_MSC_VER) && (_MSC_VER < 1400)) && !defined(__MWERKS__)
16 // VC60 and VC7 workaround: built-in std::reverse_iterator has two template parameters, Dinkumware only has one
17 typedef std::reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt;
18#elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
19 typedef std::reverse_iterator<unsigned int *, std::random_access_iterator_tag, unsigned int> RevIt;
20#else
21 typedef std::reverse_iterator<unsigned int *> RevIt;
22#endif
23
25 : Filter(attachment), m_counting(false), m_bitCount(0), m_buffer(0)
26 , m_bitsBuffered(0), m_bytesBuffered(0)
27{
28}
29
30void LowFirstBitWriter::StartCounting()
31{
32 CRYPTOPP_ASSERT(!m_counting);
33 m_counting = true;
34 m_bitCount = 0;
35}
36
37unsigned long LowFirstBitWriter::FinishCounting()
38{
39 CRYPTOPP_ASSERT(m_counting);
40 m_counting = false;
41 return m_bitCount;
42}
43
44void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length)
45{
46 if (m_counting)
47 m_bitCount += length;
48 else
49 {
50 m_buffer |= value << m_bitsBuffered;
51 m_bitsBuffered += length;
52 CRYPTOPP_ASSERT(m_bitsBuffered <= sizeof(unsigned long)*8);
53 while (m_bitsBuffered >= 8)
54 {
55 m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;
56 if (m_bytesBuffered == m_outputBuffer.size())
57 {
58 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
59 m_bytesBuffered = 0;
60 }
61 m_buffer >>= 8;
62 m_bitsBuffered -= 8;
63 }
64 }
65}
66
67void LowFirstBitWriter::FlushBitBuffer()
68{
69 if (m_counting)
70 m_bitCount += 8*(m_bitsBuffered > 0);
71 else
72 {
73 if (m_bytesBuffered > 0)
74 {
75 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
76 m_bytesBuffered = 0;
77 }
78 if (m_bitsBuffered > 0)
79 {
80 AttachedTransformation()->Put((byte)m_buffer);
81 m_buffer = 0;
82 m_bitsBuffered = 0;
83 }
84 }
85}
86
87void LowFirstBitWriter::ClearBitBuffer()
88{
89 m_buffer = 0;
90 m_bytesBuffered = 0;
91 m_bitsBuffered = 0;
92}
93
94HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)
95{
96 Initialize(codeBits, nCodes);
97}
98
100{
101 // Coverity finding on uninitialized 'symbol' member
103 : symbol(0), parent(0) {}
104 HuffmanNode(const HuffmanNode& rhs)
105 : symbol(rhs.symbol), parent(rhs.parent) {}
106
107 size_t symbol;
108 union {size_t parent; unsigned depth, freq;};
109};
110
112{
113 inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;}
114 inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;}
115 // needed for MSVC .NET 2005
116 inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;}
117};
118
119void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes)
120{
121 CRYPTOPP_ASSERT(nCodes > 0);
122 CRYPTOPP_ASSERT(nCodes <= ((size_t)1 << maxCodeBits));
123
124 size_t i;
126 for (i=0; i<nCodes; i++)
127 {
128 tree[i].symbol = i;
129 tree[i].freq = codeCounts[i];
130 }
131 std::sort(tree.begin(), tree.end(), FreqLessThan());
132 size_t treeBegin = std::upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin();
133 if (treeBegin == nCodes)
134 { // special case for no codes
135 std::fill(codeBits, codeBits+nCodes, 0);
136 return;
137 }
138 tree.resize(nCodes + nCodes - treeBegin - 1);
139
140 size_t leastLeaf = treeBegin, leastInterior = nCodes;
141 for (i=nCodes; i<tree.size(); i++)
142 {
143 size_t least;
144 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
145 tree[i].freq = tree[least].freq;
146 tree[least].parent = i;
147 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
148 tree[i].freq += tree[least].freq;
149 tree[least].parent = i;
150 }
151
152 tree[tree.size()-1].depth = 0;
153 if (tree.size() >= 2)
154 for (i=tree.size()-2; i>=nCodes; i--)
155 tree[i].depth = tree[tree[i].parent].depth + 1;
156 unsigned int sum = 0;
157 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
158 std::fill(blCount.begin(), blCount.end(), 0);
159 for (i=treeBegin; i<nCodes; i++)
160 {
161 const size_t n = tree[i].parent;
162 const size_t depth = STDMIN(maxCodeBits, tree[n].depth + 1);
163 blCount[depth]++;
164 sum += 1 << (maxCodeBits - depth);
165 }
166
167 unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0;
168
169 while (overflow--)
170 {
171 unsigned int bits = maxCodeBits-1;
172 while (blCount[bits] == 0)
173 bits--;
174 blCount[bits]--;
175 blCount[bits+1] += 2;
176 CRYPTOPP_ASSERT(blCount[maxCodeBits] > 0);
177 blCount[maxCodeBits]--;
178 }
179
180 for (i=0; i<treeBegin; i++)
181 codeBits[tree[i].symbol] = 0;
182 unsigned int bits = maxCodeBits;
183 for (i=treeBegin; i<nCodes; i++)
184 {
185 while (blCount[bits] == 0)
186 bits--;
187 codeBits[tree[i].symbol] = bits;
188 blCount[bits]--;
189 }
190 CRYPTOPP_ASSERT(blCount[bits] == 0);
191}
192
193void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)
194{
195 CRYPTOPP_ASSERT(nCodes > 0);
196 unsigned int maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
197 if (maxCodeBits == 0)
198 return; // assume this object won't be used
199
200 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
201 std::fill(blCount.begin(), blCount.end(), 0);
202 unsigned int i;
203 for (i=0; i<nCodes; i++)
204 blCount[codeBits[i]]++;
205
206 code_t code = 0;
207 SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1);
208 nextCode[1] = 0;
209 for (i=2; i<=maxCodeBits; i++)
210 {
211 code = (code + blCount[i-1]) << 1;
212 nextCode[i] = code;
213 }
214 CRYPTOPP_ASSERT(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]);
215
216 m_valueToCode.resize(nCodes);
217 for (i=0; i<nCodes; i++)
218 {
219 unsigned int len = m_valueToCode[i].len = codeBits[i];
220 if (len != 0)
221 m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len);
222 }
223}
224
225inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const
226{
227 CRYPTOPP_ASSERT(m_valueToCode[value].len > 0);
228 writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len);
229}
230
231Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible)
232 : LowFirstBitWriter(attachment)
233 , m_deflateLevel(-1)
234{
235 InitializeStaticEncoders();
236 IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible));
237}
238
240 : LowFirstBitWriter(attachment)
241 , m_deflateLevel(-1)
242{
243 InitializeStaticEncoders();
244 IsolatedInitialize(parameters);
245}
246
247void Deflator::InitializeStaticEncoders()
248{
249 unsigned int codeLengths[288];
250 std::fill(codeLengths + 0, codeLengths + 144, 8);
251 std::fill(codeLengths + 144, codeLengths + 256, 9);
252 std::fill(codeLengths + 256, codeLengths + 280, 7);
253 std::fill(codeLengths + 280, codeLengths + 288, 8);
254 m_staticLiteralEncoder.Initialize(codeLengths, 288);
255 std::fill(codeLengths + 0, codeLengths + 32, 5);
256 m_staticDistanceEncoder.Initialize(codeLengths, 32);
257}
258
260{
261 int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE);
262 if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE))
263 throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size");
264
265 m_log2WindowSize = log2WindowSize;
266 DSIZE = 1 << m_log2WindowSize;
267 DMASK = DSIZE - 1;
268 HSIZE = 1 << m_log2WindowSize;
269 HMASK = HSIZE - 1;
270 m_byteBuffer.New(2*DSIZE);
271 m_head.New(HSIZE);
272 m_prev.New(DSIZE);
273 m_matchBuffer.New(DSIZE/2);
274 Reset(true);
275
276 const int deflateLevel = parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL);
277 CRYPTOPP_ASSERT(deflateLevel >= MIN_DEFLATE_LEVEL /*0*/ && deflateLevel <= MAX_DEFLATE_LEVEL /*9*/);
278 SetDeflateLevel(deflateLevel);
279 bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true);
280 m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0;
281}
282
283void Deflator::Reset(bool forceReset)
284{
285 if (forceReset)
286 ClearBitBuffer();
287 else
288 CRYPTOPP_ASSERT(m_bitsBuffered == 0);
289
290 m_headerWritten = false;
291 m_matchAvailable = false;
292 m_dictionaryEnd = 0;
293 m_stringStart = 0;
294 m_lookahead = 0;
295 m_minLookahead = MAX_MATCH;
296 m_matchBufferEnd = 0;
297 m_blockStart = 0;
298 m_blockLength = 0;
299
300 m_detectCount = 1;
301 m_detectSkip = 0;
302
303 // m_prev will be initialized automatically in InsertString
304 std::fill(m_head.begin(), m_head.end(), byte(0));
305
306 std::fill(m_literalCounts.begin(), m_literalCounts.end(), byte(0));
307 std::fill(m_distanceCounts.begin(), m_distanceCounts.end(), byte(0));
308}
309
310void Deflator::SetDeflateLevel(int deflateLevel)
311{
312 if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL))
313 throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level");
314
315 if (deflateLevel == m_deflateLevel)
316 return;
317
318 EndBlock(false);
319
320 static const unsigned int configurationTable[10][4] = {
321 /* good lazy nice chain */
322 /* 0 */ {0, 0, 0, 0}, /* store only */
323 /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */
324 /* 2 */ {4, 3, 16, 8},
325 /* 3 */ {4, 3, 32, 32},
326 /* 4 */ {4, 4, 16, 16}, /* lazy matches */
327 /* 5 */ {8, 16, 32, 32},
328 /* 6 */ {8, 16, 128, 128},
329 /* 7 */ {8, 32, 128, 256},
330 /* 8 */ {32, 128, 258, 1024},
331 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
332
333 GOOD_MATCH = configurationTable[deflateLevel][0];
334 MAX_LAZYLENGTH = configurationTable[deflateLevel][1];
335 MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3];
336
337 m_deflateLevel = deflateLevel;
338}
339
340unsigned int Deflator::FillWindow(const byte *str, size_t length)
341{
342 unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL);
343
344 if (m_stringStart >= maxBlockSize - MAX_MATCH)
345 {
346 if (m_blockStart < DSIZE)
347 EndBlock(false);
348
349 memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE);
350
351 m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE;
352 CRYPTOPP_ASSERT(m_stringStart >= DSIZE);
353 m_stringStart -= DSIZE;
354 CRYPTOPP_ASSERT(!m_matchAvailable || m_previousMatch >= DSIZE);
355 m_previousMatch -= DSIZE;
356 CRYPTOPP_ASSERT(m_blockStart >= DSIZE);
357 m_blockStart -= DSIZE;
358
359 // These are set to the same value in IsolatedInitialize(). If they
360 // are the same, then we can clear a Coverity false alarm.
361 CRYPTOPP_ASSERT(DSIZE == HSIZE);
362
363 unsigned int i;
364 for (i=0; i<HSIZE; i++)
365 m_head[i] = SaturatingSubtract(m_head[i], HSIZE); // was DSIZE???
366
367 for (i=0; i<DSIZE; i++)
368 m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE);
369 }
370
371 CRYPTOPP_ASSERT(maxBlockSize > m_stringStart+m_lookahead);
372 unsigned int accepted = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length);
373 CRYPTOPP_ASSERT(accepted > 0);
374 memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted);
375 m_lookahead += accepted;
376 return accepted;
377}
378
379inline unsigned int Deflator::ComputeHash(const byte *str) const
380{
381 CRYPTOPP_ASSERT(str+3 <= m_byteBuffer + m_stringStart + m_lookahead);
382 return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK;
383}
384
385unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const
386{
387 CRYPTOPP_ASSERT(m_previousLength < MAX_MATCH);
388
389 bestMatch = 0;
390 unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1);
391 if (m_lookahead <= bestLength)
392 return 0;
393
394 const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead);
395 unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0;
396 unsigned int current = m_head[ComputeHash(scan)];
397
398 unsigned int chainLength = MAX_CHAIN_LENGTH;
399 if (m_previousLength >= GOOD_MATCH)
400 chainLength >>= 2;
401
402 while (current > limit && --chainLength > 0)
403 {
404 const byte *match = m_byteBuffer + current;
405 CRYPTOPP_ASSERT(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead);
406 if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1])
407 {
408 CRYPTOPP_ASSERT(scan[2] == match[2]);
409 unsigned int len = (unsigned int)(
410#if defined(_STDEXT_BEGIN) && !(defined(_MSC_VER) && (_MSC_VER < 1400 || _MSC_VER >= 1600)) && !defined(_STLPORT_VERSION)
411 stdext::unchecked_mismatch
412#else
413 std::mismatch
414#endif
415#if _MSC_VER >= 1600
416 (stdext::make_unchecked_array_iterator(scan)+3, stdext::make_unchecked_array_iterator(scanEnd), stdext::make_unchecked_array_iterator(match)+3).first - stdext::make_unchecked_array_iterator(scan));
417#else
418 (scan+3, scanEnd, match+3).first - scan);
419#endif
420 CRYPTOPP_ASSERT(len != bestLength);
421 if (len > bestLength)
422 {
423 bestLength = len;
424 bestMatch = current;
425
426 CRYPTOPP_ASSERT(scanEnd >= scan);
427 if (len == (unsigned int)(scanEnd - scan))
428 break;
429 }
430 }
431 current = m_prev[current & DMASK];
432 }
433 return (bestMatch > 0) ? bestLength : 0;
434}
435
436inline void Deflator::InsertString(unsigned int start)
437{
438 CRYPTOPP_ASSERT(start <= 0xffff);
439 unsigned int hash = ComputeHash(m_byteBuffer + start);
440 m_prev[start & DMASK] = m_head[hash];
441 m_head[hash] = word16(start);
442}
443
444void Deflator::ProcessBuffer()
445{
446 if (!m_headerWritten)
447 {
448 WritePrestreamHeader();
449 m_headerWritten = true;
450 }
451
452 if (m_deflateLevel == 0)
453 {
454 m_stringStart += m_lookahead;
455 m_lookahead = 0;
456 m_blockLength = m_stringStart - m_blockStart;
457 m_matchAvailable = false;
458 return;
459 }
460
461 while (m_lookahead > m_minLookahead)
462 {
463 while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead)
464 InsertString(m_dictionaryEnd++);
465
466 if (m_matchAvailable)
467 {
468 unsigned int matchPosition = 0, matchLength = 0;
469 bool usePreviousMatch;
470 if (m_previousLength >= MAX_LAZYLENGTH)
471 usePreviousMatch = true;
472 else
473 {
474 matchLength = LongestMatch(matchPosition);
475 usePreviousMatch = (matchLength == 0);
476 }
477 if (usePreviousMatch)
478 {
479 MatchFound(m_stringStart-1-m_previousMatch, m_previousLength);
480 m_stringStart += m_previousLength-1;
481 m_lookahead -= m_previousLength-1;
482 m_matchAvailable = false;
483 }
484 else
485 {
486 m_previousLength = matchLength;
487 m_previousMatch = matchPosition;
488 LiteralByte(m_byteBuffer[m_stringStart-1]);
489 m_stringStart++;
490 m_lookahead--;
491 }
492 }
493 else
494 {
495 m_previousLength = 0;
496 m_previousLength = LongestMatch(m_previousMatch);
497 if (m_previousLength)
498 m_matchAvailable = true;
499 else
500 LiteralByte(m_byteBuffer[m_stringStart]);
501 m_stringStart++;
502 m_lookahead--;
503 }
504
505 CRYPTOPP_ASSERT(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable);
506 }
507
508 if (m_minLookahead == 0 && m_matchAvailable)
509 {
510 LiteralByte(m_byteBuffer[m_stringStart-1]);
511 m_matchAvailable = false;
512 }
513}
514
515size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking)
516{
517 if (!blocking)
518 throw BlockingInputOnly("Deflator");
519
520 size_t accepted = 0;
521 while (accepted < length)
522 {
523 unsigned int newAccepted = FillWindow(str+accepted, length-accepted);
524 ProcessBuffer();
525 // call ProcessUncompressedData() after WritePrestreamHeader()
526 ProcessUncompressedData(str+accepted, newAccepted);
527 accepted += newAccepted;
528 }
529 CRYPTOPP_ASSERT(accepted == length);
530
531 if (messageEnd)
532 {
533 m_minLookahead = 0;
534 ProcessBuffer();
535 EndBlock(true);
536 FlushBitBuffer();
537 WritePoststreamTail();
538 Reset();
539 }
540
541 Output(0, NULLPTR, 0, messageEnd, blocking);
542 return 0;
543}
544
545bool Deflator::IsolatedFlush(bool hardFlush, bool blocking)
546{
547 if (!blocking)
548 throw BlockingInputOnly("Deflator");
549
550 m_minLookahead = 0;
551 ProcessBuffer();
552 m_minLookahead = MAX_MATCH;
553 EndBlock(false);
554 if (hardFlush)
555 EncodeBlock(false, STORED);
556 return false;
557}
558
559void Deflator::LiteralByte(byte b)
560{
561 if (m_matchBufferEnd == m_matchBuffer.size())
562 EndBlock(false);
563
564 m_matchBuffer[m_matchBufferEnd++].literalCode = b;
565 m_literalCounts[b]++;
566 m_blockLength++;
567}
568
569void Deflator::MatchFound(unsigned int distance, unsigned int length)
570{
571 if (m_matchBufferEnd == m_matchBuffer.size())
572 EndBlock(false);
573
574 static const unsigned int lengthCodes[] = {
575 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268,
576 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272,
577 273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274,
578 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276,
579 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277,
580 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278,
581 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279,
582 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280,
583 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
584 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
585 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
586 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
587 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
588 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
589 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284,
590 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285};
591 static const unsigned int lengthBases[] =
592 {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,
593 227,258};
594 static const unsigned int distanceBases[30] =
595 {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,
596 4097,6145,8193,12289,16385,24577};
597
598 CRYPTOPP_ASSERT(m_matchBufferEnd < m_matchBuffer.size());
599 EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++];
600 CRYPTOPP_ASSERT((length >= 3) && (length-3 < COUNTOF(lengthCodes)));
601 unsigned int lengthCode = lengthCodes[length-3];
602 m.literalCode = lengthCode;
603 m.literalExtra = length - lengthBases[lengthCode-257];
604 unsigned int distanceCode = (unsigned int)(std::upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1);
605 m.distanceCode = distanceCode;
606 m.distanceExtra = distance - distanceBases[distanceCode];
607
608 m_literalCounts[lengthCode]++;
609 m_distanceCounts[distanceCode]++;
610 m_blockLength += length;
611}
612
613inline unsigned int CodeLengthEncode(const unsigned int *begin,
614 const unsigned int *end,
615 const unsigned int *& p,
616 unsigned int &extraBits,
617 unsigned int &extraBitsLength)
618{
619 unsigned int v = *p;
620 if ((end-p) >= 3)
621 {
622 const unsigned int *oldp = p;
623 if (v==0 && p[1]==0 && p[2]==0)
624 {
625 for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {}
626 unsigned int repeat = (unsigned int)(p - oldp);
627 if (repeat <= 10)
628 {
629 extraBits = repeat-3;
630 extraBitsLength = 3;
631 return 17;
632 }
633 else
634 {
635 extraBits = repeat-11;
636 extraBitsLength = 7;
637 return 18;
638 }
639 }
640 else if (p!=begin && v==p[-1] && v==p[1] && v==p[2])
641 {
642 for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {}
643 unsigned int repeat = (unsigned int)(p - oldp);
644 extraBits = repeat-3;
645 extraBitsLength = 2;
646 return 16;
647 }
648 }
649 p++;
650 extraBits = 0;
651 extraBitsLength = 0;
652 return v;
653}
654
655void Deflator::EncodeBlock(bool eof, unsigned int blockType)
656{
657 PutBits(eof, 1);
658 PutBits(blockType, 2);
659
660 if (blockType == STORED)
661 {
662 CRYPTOPP_ASSERT(m_blockStart + m_blockLength <= m_byteBuffer.size());
663 CRYPTOPP_ASSERT(m_blockLength <= 0xffff);
664 FlushBitBuffer();
665 AttachedTransformation()->PutWord16(word16(m_blockLength), LITTLE_ENDIAN_ORDER);
666 AttachedTransformation()->PutWord16(word16(~m_blockLength), LITTLE_ENDIAN_ORDER);
667 AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength);
668 }
669 else
670 {
671 if (blockType == DYNAMIC)
672 {
673 FixedSizeSecBlock<unsigned int, 286> literalCodeLengths;
674 FixedSizeSecBlock<unsigned int, 30> distanceCodeLengths;
675
676 m_literalCounts[256] = 1;
677 HuffmanEncoder::GenerateCodeLengths(literalCodeLengths, 15, m_literalCounts, 286);
678 m_dynamicLiteralEncoder.Initialize(literalCodeLengths, 286);
679 unsigned int hlit = (unsigned int)(FindIfNot(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), 0).base() - (literalCodeLengths.begin()+257));
680
681 HuffmanEncoder::GenerateCodeLengths(distanceCodeLengths, 15, m_distanceCounts, 30);
682 m_dynamicDistanceEncoder.Initialize(distanceCodeLengths, 30);
683 unsigned int hdist = (unsigned int)(FindIfNot(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), 0).base() - (distanceCodeLengths.begin()+1));
684
685 SecBlockWithHint<unsigned int, 286+30> combinedLengths(hlit+257+hdist+1);
686 memcpy(combinedLengths, literalCodeLengths, (hlit+257)*sizeof(unsigned int));
687 memcpy(combinedLengths+hlit+257, distanceCodeLengths, (hdist+1)*sizeof(unsigned int));
688
689 FixedSizeSecBlock<unsigned int, 19> codeLengthCodeCounts, codeLengthCodeLengths;
690 std::fill(codeLengthCodeCounts.begin(), codeLengthCodeCounts.end(), 0);
691 const unsigned int *p = combinedLengths.begin(), *begin = combinedLengths.begin(), *end = combinedLengths.end();
692 while (p != end)
693 {
694 unsigned int code=0, extraBits=0, extraBitsLength=0;
695 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength);
696 codeLengthCodeCounts[code]++;
697 }
698 HuffmanEncoder::GenerateCodeLengths(codeLengthCodeLengths, 7, codeLengthCodeCounts, 19);
699 HuffmanEncoder codeLengthEncoder(codeLengthCodeLengths, 19);
700 static const unsigned int border[] = { // Order of the bit length code lengths
701 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
702 unsigned int hclen = 19;
703 while (hclen > 4 && codeLengthCodeLengths[border[hclen-1]] == 0)
704 hclen--;
705 hclen -= 4;
706
707 PutBits(hlit, 5);
708 PutBits(hdist, 5);
709 PutBits(hclen, 4);
710
711 for (unsigned int i=0; i<hclen+4; i++)
712 PutBits(codeLengthCodeLengths[border[i]], 3);
713
714 p = combinedLengths.begin();
715 while (p != end)
716 {
717 unsigned int code=0, extraBits=0, extraBitsLength=0;
718 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength);
719 codeLengthEncoder.Encode(*this, code);
720 PutBits(extraBits, extraBitsLength);
721 }
722 }
723
724 static const unsigned int lengthExtraBits[] = {
725 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
726 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
727 static const unsigned int distanceExtraBits[] = {
728 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
729 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
730 12, 12, 13, 13};
731
732 const HuffmanEncoder &literalEncoder = (blockType == STATIC) ? m_staticLiteralEncoder : m_dynamicLiteralEncoder;
733 const HuffmanEncoder &distanceEncoder = (blockType == STATIC) ? m_staticDistanceEncoder : m_dynamicDistanceEncoder;
734
735 for (unsigned int i=0; i<m_matchBufferEnd; i++)
736 {
737 unsigned int literalCode = m_matchBuffer[i].literalCode;
738 literalEncoder.Encode(*this, literalCode);
739 if (literalCode >= 257)
740 {
741 CRYPTOPP_ASSERT(literalCode <= 285);
742 PutBits(m_matchBuffer[i].literalExtra, lengthExtraBits[literalCode-257]);
743 unsigned int distanceCode = m_matchBuffer[i].distanceCode;
744 distanceEncoder.Encode(*this, distanceCode);
745 PutBits(m_matchBuffer[i].distanceExtra, distanceExtraBits[distanceCode]);
746 }
747 }
748 literalEncoder.Encode(*this, 256); // end of block
749 }
750}
751
752void Deflator::EndBlock(bool eof)
753{
754 if (m_blockLength == 0 && !eof)
755 return;
756
757 if (m_deflateLevel == 0)
758 {
759 EncodeBlock(eof, STORED);
760
761 if (m_compressibleDeflateLevel > 0 && ++m_detectCount == m_detectSkip)
762 {
763 m_deflateLevel = m_compressibleDeflateLevel;
764 m_detectCount = 1;
765 }
766 }
767 else
768 {
769 unsigned long storedLen = 8*((unsigned long)m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered;
770
771 StartCounting();
772 EncodeBlock(eof, STATIC);
773 unsigned long staticLen = FinishCounting();
774
775 unsigned long dynamicLen;
776 if (m_blockLength < 128 && m_deflateLevel < 8)
777 dynamicLen = ULONG_MAX;
778 else
779 {
780 StartCounting();
781 EncodeBlock(eof, DYNAMIC);
782 dynamicLen = FinishCounting();
783 }
784
785 if (storedLen <= staticLen && storedLen <= dynamicLen)
786 {
787 EncodeBlock(eof, STORED);
788
789 if (m_compressibleDeflateLevel > 0)
790 {
791 if (m_detectSkip)
792 m_deflateLevel = 0;
793 m_detectSkip = m_detectSkip ? STDMIN(2*m_detectSkip, 128U) : 1;
794 }
795 }
796 else
797 {
798 if (staticLen <= dynamicLen)
799 EncodeBlock(eof, STATIC);
800 else
801 EncodeBlock(eof, DYNAMIC);
802
803 if (m_compressibleDeflateLevel > 0)
804 m_detectSkip = 0;
805 }
806 }
807
808 m_matchBufferEnd = 0;
809 m_blockStart += m_blockLength;
810 m_blockLength = 0;
811 std::fill(m_literalCounts.begin(), m_literalCounts.end(), 0);
812 std::fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0);
813}
814
815NAMESPACE_END
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:502
Interface for buffered transformations.
Definition: cryptlib.h:1599
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:745
size_t PutModifiable(byte *inString, size_t length, bool blocking=true)
Input multiple bytes that may be modified by callee.
Definition: cryptlib.h:1674
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1620
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
Definition: zdeflate.cpp:545
void SetDeflateLevel(int deflateLevel)
Sets the deflation level.
Definition: zdeflate.cpp:310
@ MIN_DEFLATE_LEVEL
Minimum deflation level, fastest speed (0)
Definition: zdeflate.h:81
@ DEFAULT_DEFLATE_LEVEL
Default deflation level, compromise between speed (6)
Definition: zdeflate.h:83
@ MAX_DEFLATE_LEVEL
Minimum deflation level, slowest speed (9)
Definition: zdeflate.h:85
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: zdeflate.cpp:515
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: zdeflate.cpp:259
@ DEFAULT_LOG2_WINDOW_SIZE
Default window size (15)
Definition: zdeflate.h:92
@ MAX_LOG2_WINDOW_SIZE
Maximum window size, largest table (15)
Definition: zdeflate.h:94
@ MIN_LOG2_WINDOW_SIZE
Minimum window size, smallest table (9)
Definition: zdeflate.h:90
Deflator(BufferedTransformation *attachment=NULL, int deflateLevel=DEFAULT_DEFLATE_LEVEL, int log2WindowSize=DEFAULT_LOG2_WINDOW_SIZE, bool detectUncompressible=true)
Construct a Deflator compressor.
Definition: zdeflate.cpp:231
Implementation of BufferedTransformation's attachment interface.
Definition: filters.h:36
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Definition: filters.cpp:36
Fixed size stack-based SecBlock.
Definition: secblock.h:1078
Huffman Encoder.
Definition: zdeflate.h:42
void Initialize(const unsigned int *codeBits, unsigned int nCodes)
Initialize or reinitialize this object.
Definition: zdeflate.cpp:193
HuffmanEncoder()
Construct a HuffmanEncoder.
Definition: zdeflate.h:48
An invalid argument was detected.
Definition: cryptlib.h:203
Encoding table writer.
Definition: zdeflate.h:18
LowFirstBitWriter(BufferedTransformation *attachment)
Construct a LowFirstBitWriter.
Definition: zdeflate.cpp:24
Interface for retrieving values given their names.
Definition: cryptlib.h:294
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:363
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:395
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:772
iterator end()
Provides an iterator pointing beyond the last element in the memory block.
Definition: secblock.h:780
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:965
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
Stack-based SecBlock that grows into the heap.
Definition: secblock.h:1099
@ LITTLE_ENDIAN_ORDER
byte order is little-endian
Definition: cryptlib.h:145
Utility functions for the Crypto++ library.
byte BitReverse(byte value)
Reverses bits in a 8-bit value.
Definition: misc.h:2039
#define COUNTOF(arr)
Counts elements in an array.
Definition: misc.h:153
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:1004
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:578
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:1085
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:567
std::string IntToString(T value, unsigned int base=10)
Converts a value to a string.
Definition: misc.h:636
InputIt FindIfNot(InputIt first, InputIt last, const T &value)
Finds first element not in a range.
Definition: misc.h:2670
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:606
Crypto++ library namespace.
Precompiled header file.
Common C++ header files.
Exception thrown by objects that have not implemented nonblocking input processing.
Definition: cryptlib.h:1723
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
DEFLATE compression and decompression (RFC 1951)