Crypto++ 8.4 Free C++ class library of cryptographic schemes

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