Crypto++  5.6.5
Free C++ class library of cryptographic schemes
zdeflate.cpp
1 // zdeflate.cpp - 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 
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 
100 {
101  // Coverity finding on uninitalized 'symbol' member
102  HuffmanNode()
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 
119 void 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 
193 void 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 
225 inline 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 
231 Deflator::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 
247 void 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 
283 void 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 automaticly 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 
310 void 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 
340 unsigned 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 
379 inline 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 
385 unsigned 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 
436 inline 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 
444 void 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 
515 size_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, NULL, 0, messageEnd, blocking);
542  return 0;
543 }
544 
545 bool 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 
559 void 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 
569 void 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 
613 inline 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 
655 void 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)(std::find_if(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), std::bind2nd(std::not_equal_to<unsigned int>(), 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)(std::find_if(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), std::bind2nd(std::not_equal_to<unsigned int>(), 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 
752 void 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 
815 NAMESPACE_END
iterator end()
Provides an iterator pointing beyond the last element in the memory block.
Definition: secblock.h:507
An invalid argument was detected.
Definition: cryptlib.h:184
Minimum deflation level, slowest speed (9)
Definition: zdeflate.h:88
Stack-based SecBlock that grows into the heap.
Definition: secblock.h:776
Utility functions for the Crypto++ library.
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:350
Default window size (15)
Definition: zdeflate.h:95
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:524
Encoding table writer.
Definition: zdeflate.h:18
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:647
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
Definition: zdeflate.cpp:545
Interface for buffered transformations.
Definition: cryptlib.h:1352
DEFLATE compression and decompression (RFC 1951)
byte BitReverse(byte value)
Reverses bits in a 8-bit value.
Definition: misc.h:1733
Default deflation level, compromise between speed (6)
Definition: zdeflate.h:86
byte order is little-endian
Definition: cryptlib.h:126
size_t PutModifiable(byte *inString, size_t length, bool blocking=true)
Input multiple bytes that may be modified by callee.
Definition: cryptlib.h:1426
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:382
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1376
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:500
Minimum window size, smallest table (9)
Definition: zdeflate.h:93
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Definition: filters.cpp:36
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:847
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:512
#define COUNTOF(arr)
Counts elements in an array.
Definition: misc.h:168
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:477
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:62
HuffmanEncoder()
Construct a HuffmanEncoder.
Definition: zdeflate.h:50
void SetDeflateLevel(int deflateLevel)
Sets the deflation level.
Definition: zdeflate.cpp:310
Maximum window size, largest table (15)
Definition: zdeflate.h:97
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:499
Exception thrown by objects that have not implemented nonblocking input processing.
Definition: cryptlib.h:1470
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
LowFirstBitWriter(BufferedTransformation *attachment)
Construct a LowFirstBitWriter.
Definition: zdeflate.cpp:24
void Initialize(const unsigned int *codeBits, unsigned int nCodes)
Initialize or reinitialize this object.
Definition: zdeflate.cpp:193
Implementation of BufferedTransformation's attachment interface.
Definition: filters.h:36
std::string IntToString(T value, unsigned int base=10)
Converts a value to a string.
Definition: misc.h:539
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:714
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: zdeflate.cpp:515
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:905
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:487
Crypto++ library namespace.
Huffman Encoder.
Definition: zdeflate.h:43
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: zdeflate.cpp:259
Minimum deflation level, fastest speed (0)
Definition: zdeflate.h:84
Interface for retrieving values given their names.
Definition: cryptlib.h:279