Crypto++  8.2
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 
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  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 
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;
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 
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 
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
iterator end()
Provides an iterator pointing beyond the last element in the memory block.
Definition: secblock.h:780
InputIt FindIfNot(InputIt first, InputIt last, const T &value)
Finds first element not in a range.
Definition: misc.h:2754
An invalid argument was detected.
Definition: cryptlib.h:202
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:424
Stack-based SecBlock that grows into the heap.
Definition: secblock.h:1098
Utility functions for the Crypto++ library.
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:392
Minimum window size, smallest table (9)
Definition: zdeflate.h:90
Encoding table writer.
Definition: zdeflate.h:17
Common C++ header files.
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:965
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
Definition: zdeflate.cpp:551
Interface for buffered transformations.
Definition: cryptlib.h:1627
DEFLATE compression and decompression (RFC 1951)
byte BitReverse(byte value)
Reverses bits in a 8-bit value.
Definition: misc.h:2105
byte order is little-endian
Definition: cryptlib.h:145
size_t PutModifiable(byte *inString, size_t length, bool blocking=true)
Input multiple bytes that may be modified by callee.
Definition: cryptlib.h:1711
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1649
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:504
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Definition: filters.cpp:36
Precompiled header file.
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:1046
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:647
Minimum deflation level, fastest speed (0)
Definition: zdeflate.h:81
#define COUNTOF(arr)
Counts elements in an array.
Definition: misc.h:189
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:608
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
HuffmanEncoder()
Construct a HuffmanEncoder.
Definition: zdeflate.h:48
void SetDeflateLevel(int deflateLevel)
Sets the deflation level.
Definition: zdeflate.cpp:316
Default window size (15)
Definition: zdeflate.h:92
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:772
Exception thrown by objects that have not implemented nonblocking input processing.
Definition: cryptlib.h:1759
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
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:199
Implementation of BufferedTransformation's attachment interface.
Definition: filters.h:35
Default deflation level, compromise between speed (6)
Definition: zdeflate.h:83
std::string IntToString(T value, unsigned int base=10)
Converts a value to a string.
Definition: misc.h:677
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:753
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: zdeflate.cpp:521
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:1127
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:619
Maximum window size, largest table (15)
Definition: zdeflate.h:94
Crypto++ library namespace.
Minimum deflation level, slowest speed (9)
Definition: zdeflate.h:85
Huffman Encoder.
Definition: zdeflate.h:41
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: zdeflate.cpp:265
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
Interface for retrieving values given their names.
Definition: cryptlib.h:321