Crypto++  5.6.3
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 
16  : Filter(attachment), m_counting(false), m_bitCount(0), m_buffer(0)
17  , m_bitsBuffered(0), m_bytesBuffered(0)
18 {
19 }
20 
21 void LowFirstBitWriter::StartCounting()
22 {
23  assert(!m_counting);
24  m_counting = true;
25  m_bitCount = 0;
26 }
27 
28 unsigned long LowFirstBitWriter::FinishCounting()
29 {
30  assert(m_counting);
31  m_counting = false;
32  return m_bitCount;
33 }
34 
35 void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length)
36 {
37  if (m_counting)
38  m_bitCount += length;
39  else
40  {
41  m_buffer |= value << m_bitsBuffered;
42  m_bitsBuffered += length;
43  assert(m_bitsBuffered <= sizeof(unsigned long)*8);
44  while (m_bitsBuffered >= 8)
45  {
46  m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;
47  if (m_bytesBuffered == m_outputBuffer.size())
48  {
49  AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
50  m_bytesBuffered = 0;
51  }
52  m_buffer >>= 8;
53  m_bitsBuffered -= 8;
54  }
55  }
56 }
57 
58 void LowFirstBitWriter::FlushBitBuffer()
59 {
60  if (m_counting)
61  m_bitCount += 8*(m_bitsBuffered > 0);
62  else
63  {
64  if (m_bytesBuffered > 0)
65  {
66  AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);
67  m_bytesBuffered = 0;
68  }
69  if (m_bitsBuffered > 0)
70  {
71  AttachedTransformation()->Put((byte)m_buffer);
72  m_buffer = 0;
73  m_bitsBuffered = 0;
74  }
75  }
76 }
77 
78 void LowFirstBitWriter::ClearBitBuffer()
79 {
80  m_buffer = 0;
81  m_bytesBuffered = 0;
82  m_bitsBuffered = 0;
83 }
84 
85 HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)
86 {
87  Initialize(codeBits, nCodes);
88 }
89 
91 {
92  // Coverity finding on uninitalized 'symbol' member
93  HuffmanNode()
94  : symbol(0), parent(0) {}
95  HuffmanNode(const HuffmanNode& rhs)
96  : symbol(rhs.symbol), parent(rhs.parent) {}
97 
98  size_t symbol;
99  union {size_t parent; unsigned depth, freq;};
100 };
101 
103 {
104  inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;}
105  inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;}
106  // needed for MSVC .NET 2005
107  inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;}
108 };
109 
110 void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes)
111 {
112  assert(nCodes > 0);
113  assert(nCodes <= ((size_t)1 << maxCodeBits));
114 
115  size_t i;
117  for (i=0; i<nCodes; i++)
118  {
119  tree[i].symbol = i;
120  tree[i].freq = codeCounts[i];
121  }
122  std::sort(tree.begin(), tree.end(), FreqLessThan());
123  size_t treeBegin = std::upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin();
124  if (treeBegin == nCodes)
125  { // special case for no codes
126  std::fill(codeBits, codeBits+nCodes, 0);
127  return;
128  }
129  tree.resize(nCodes + nCodes - treeBegin - 1);
130 
131  size_t leastLeaf = treeBegin, leastInterior = nCodes;
132  for (i=nCodes; i<tree.size(); i++)
133  {
134  size_t least;
135  least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
136  tree[i].freq = tree[least].freq;
137  tree[least].parent = i;
138  least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
139  tree[i].freq += tree[least].freq;
140  tree[least].parent = i;
141  }
142 
143  tree[tree.size()-1].depth = 0;
144  if (tree.size() >= 2)
145  for (i=tree.size()-2; i>=nCodes; i--)
146  tree[i].depth = tree[tree[i].parent].depth + 1;
147  unsigned int sum = 0;
148  SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
149  std::fill(blCount.begin(), blCount.end(), 0);
150  for (i=treeBegin; i<nCodes; i++)
151  {
152  const size_t n = tree[i].parent;
153  const size_t depth = STDMIN(maxCodeBits, tree[n].depth + 1);
154  blCount[depth]++;
155  sum += 1 << (maxCodeBits - depth);
156  }
157 
158  unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0;
159 
160  while (overflow--)
161  {
162  unsigned int bits = maxCodeBits-1;
163  while (blCount[bits] == 0)
164  bits--;
165  blCount[bits]--;
166  blCount[bits+1] += 2;
167  assert(blCount[maxCodeBits] > 0);
168  blCount[maxCodeBits]--;
169  }
170 
171  for (i=0; i<treeBegin; i++)
172  codeBits[tree[i].symbol] = 0;
173  unsigned int bits = maxCodeBits;
174  for (i=treeBegin; i<nCodes; i++)
175  {
176  while (blCount[bits] == 0)
177  bits--;
178  codeBits[tree[i].symbol] = bits;
179  blCount[bits]--;
180  }
181  assert(blCount[bits] == 0);
182 }
183 
184 void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)
185 {
186  assert(nCodes > 0);
187  unsigned int maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
188  if (maxCodeBits == 0)
189  return; // assume this object won't be used
190 
191  SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
192  std::fill(blCount.begin(), blCount.end(), 0);
193  unsigned int i;
194  for (i=0; i<nCodes; i++)
195  blCount[codeBits[i]]++;
196 
197  code_t code = 0;
198  SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1);
199  nextCode[1] = 0;
200  for (i=2; i<=maxCodeBits; i++)
201  {
202  code = (code + blCount[i-1]) << 1;
203  nextCode[i] = code;
204  }
205  assert(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]);
206 
207  m_valueToCode.resize(nCodes);
208  for (i=0; i<nCodes; i++)
209  {
210  unsigned int len = m_valueToCode[i].len = codeBits[i];
211  if (len != 0)
212  m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len);
213  }
214 }
215 
216 inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const
217 {
218  assert(m_valueToCode[value].len > 0);
219  writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len);
220 }
221 
222 Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible)
223  : LowFirstBitWriter(attachment)
224  , m_deflateLevel(-1)
225 {
226  InitializeStaticEncoders();
227  IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible));
228 }
229 
231  : LowFirstBitWriter(attachment)
232  , m_deflateLevel(-1)
233 {
234  InitializeStaticEncoders();
235  IsolatedInitialize(parameters);
236 }
237 
238 void Deflator::InitializeStaticEncoders()
239 {
240  unsigned int codeLengths[288];
241  std::fill(codeLengths + 0, codeLengths + 144, 8);
242  std::fill(codeLengths + 144, codeLengths + 256, 9);
243  std::fill(codeLengths + 256, codeLengths + 280, 7);
244  std::fill(codeLengths + 280, codeLengths + 288, 8);
245  m_staticLiteralEncoder.Initialize(codeLengths, 288);
246  std::fill(codeLengths + 0, codeLengths + 32, 5);
247  m_staticDistanceEncoder.Initialize(codeLengths, 32);
248 }
249 
251 {
252  int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE);
253  if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE))
254  throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size");
255 
256  m_log2WindowSize = log2WindowSize;
257  DSIZE = 1 << m_log2WindowSize;
258  DMASK = DSIZE - 1;
259  HSIZE = 1 << m_log2WindowSize;
260  HMASK = HSIZE - 1;
261  m_byteBuffer.New(2*DSIZE);
262  m_head.New(HSIZE);
263  m_prev.New(DSIZE);
264  m_matchBuffer.New(DSIZE/2);
265  Reset(true);
266 
267  const int deflateLevel = parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL);
268  assert(deflateLevel >= MIN_DEFLATE_LEVEL /*0*/ && deflateLevel <= MAX_DEFLATE_LEVEL /*9*/);
269  SetDeflateLevel(deflateLevel);
270  bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true);
271  m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0;
272 }
273 
274 void Deflator::Reset(bool forceReset)
275 {
276  if (forceReset)
277  ClearBitBuffer();
278  else
279  assert(m_bitsBuffered == 0);
280 
281  m_headerWritten = false;
282  m_matchAvailable = false;
283  m_dictionaryEnd = 0;
284  m_stringStart = 0;
285  m_lookahead = 0;
286  m_minLookahead = MAX_MATCH;
287  m_matchBufferEnd = 0;
288  m_blockStart = 0;
289  m_blockLength = 0;
290 
291  m_detectCount = 1;
292  m_detectSkip = 0;
293 
294  // m_prev will be initialized automaticly in InsertString
295  std::fill(m_head.begin(), m_head.end(), byte(0));
296 
297  std::fill(m_literalCounts.begin(), m_literalCounts.end(), byte(0));
298  std::fill(m_distanceCounts.begin(), m_distanceCounts.end(), byte(0));
299 }
300 
301 void Deflator::SetDeflateLevel(int deflateLevel)
302 {
303  if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL))
304  throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level");
305 
306  if (deflateLevel == m_deflateLevel)
307  return;
308 
309  EndBlock(false);
310 
311  static const unsigned int configurationTable[10][4] = {
312  /* good lazy nice chain */
313  /* 0 */ {0, 0, 0, 0}, /* store only */
314  /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */
315  /* 2 */ {4, 3, 16, 8},
316  /* 3 */ {4, 3, 32, 32},
317  /* 4 */ {4, 4, 16, 16}, /* lazy matches */
318  /* 5 */ {8, 16, 32, 32},
319  /* 6 */ {8, 16, 128, 128},
320  /* 7 */ {8, 32, 128, 256},
321  /* 8 */ {32, 128, 258, 1024},
322  /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
323 
324  GOOD_MATCH = configurationTable[deflateLevel][0];
325  MAX_LAZYLENGTH = configurationTable[deflateLevel][1];
326  MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3];
327 
328  m_deflateLevel = deflateLevel;
329 }
330 
331 unsigned int Deflator::FillWindow(const byte *str, size_t length)
332 {
333  unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL);
334 
335  if (m_stringStart >= maxBlockSize - MAX_MATCH)
336  {
337  if (m_blockStart < DSIZE)
338  EndBlock(false);
339 
340  memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE);
341 
342  m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE;
343  assert(m_stringStart >= DSIZE);
344  m_stringStart -= DSIZE;
345  assert(!m_matchAvailable || m_previousMatch >= DSIZE);
346  m_previousMatch -= DSIZE;
347  assert(m_blockStart >= DSIZE);
348  m_blockStart -= DSIZE;
349 
350  // These are set to the same value in IsolatedInitialize(). If they
351  // are the same, then we can clear a Coverity false alarm.
352  assert(DSIZE == HSIZE);
353 
354  unsigned int i;
355  for (i=0; i<HSIZE; i++)
356  m_head[i] = SaturatingSubtract(m_head[i], HSIZE); // was DSIZE???
357 
358  for (i=0; i<DSIZE; i++)
359  m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE);
360  }
361 
362  assert(maxBlockSize > m_stringStart+m_lookahead);
363  unsigned int accepted = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length);
364  assert(accepted > 0);
365  memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted);
366  m_lookahead += accepted;
367  return accepted;
368 }
369 
370 inline unsigned int Deflator::ComputeHash(const byte *str) const
371 {
372  assert(str+3 <= m_byteBuffer + m_stringStart + m_lookahead);
373  return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK;
374 }
375 
376 unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const
377 {
378  assert(m_previousLength < MAX_MATCH);
379 
380  bestMatch = 0;
381  unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1);
382  if (m_lookahead <= bestLength)
383  return 0;
384 
385  const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead);
386  unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0;
387  unsigned int current = m_head[ComputeHash(scan)];
388 
389  unsigned int chainLength = MAX_CHAIN_LENGTH;
390  if (m_previousLength >= GOOD_MATCH)
391  chainLength >>= 2;
392 
393  while (current > limit && --chainLength > 0)
394  {
395  const byte *match = m_byteBuffer + current;
396  assert(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead);
397  if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1])
398  {
399  assert(scan[2] == match[2]);
400  unsigned int len = (unsigned int)(
401 #if defined(_STDEXT_BEGIN) && !(defined(_MSC_VER) && (_MSC_VER < 1400 || _MSC_VER >= 1600)) && !defined(_STLPORT_VERSION)
402  stdext::unchecked_mismatch
403 #else
404  std::mismatch
405 #endif
406 #if _MSC_VER >= 1600
407  (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));
408 #else
409  (scan+3, scanEnd, match+3).first - scan);
410 #endif
411  assert(len != bestLength);
412  if (len > bestLength)
413  {
414  bestLength = len;
415  bestMatch = current;
416 
417  assert(scanEnd >= scan);
418  if (len == (unsigned int)(scanEnd - scan))
419  break;
420  }
421  }
422  current = m_prev[current & DMASK];
423  }
424  return (bestMatch > 0) ? bestLength : 0;
425 }
426 
427 inline void Deflator::InsertString(unsigned int start)
428 {
429  assert(start <= 0xffff);
430  unsigned int hash = ComputeHash(m_byteBuffer + start);
431  m_prev[start & DMASK] = m_head[hash];
432  m_head[hash] = word16(start);
433 }
434 
435 void Deflator::ProcessBuffer()
436 {
437  if (!m_headerWritten)
438  {
439  WritePrestreamHeader();
440  m_headerWritten = true;
441  }
442 
443  if (m_deflateLevel == 0)
444  {
445  m_stringStart += m_lookahead;
446  m_lookahead = 0;
447  m_blockLength = m_stringStart - m_blockStart;
448  m_matchAvailable = false;
449  return;
450  }
451 
452  while (m_lookahead > m_minLookahead)
453  {
454  while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead)
455  InsertString(m_dictionaryEnd++);
456 
457  if (m_matchAvailable)
458  {
459  unsigned int matchPosition = 0, matchLength = 0;
460  bool usePreviousMatch;
461  if (m_previousLength >= MAX_LAZYLENGTH)
462  usePreviousMatch = true;
463  else
464  {
465  matchLength = LongestMatch(matchPosition);
466  usePreviousMatch = (matchLength == 0);
467  }
468  if (usePreviousMatch)
469  {
470  MatchFound(m_stringStart-1-m_previousMatch, m_previousLength);
471  m_stringStart += m_previousLength-1;
472  m_lookahead -= m_previousLength-1;
473  m_matchAvailable = false;
474  }
475  else
476  {
477  m_previousLength = matchLength;
478  m_previousMatch = matchPosition;
479  LiteralByte(m_byteBuffer[m_stringStart-1]);
480  m_stringStart++;
481  m_lookahead--;
482  }
483  }
484  else
485  {
486  m_previousLength = 0;
487  m_previousLength = LongestMatch(m_previousMatch);
488  if (m_previousLength)
489  m_matchAvailable = true;
490  else
491  LiteralByte(m_byteBuffer[m_stringStart]);
492  m_stringStart++;
493  m_lookahead--;
494  }
495 
496  assert(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable);
497  }
498 
499  if (m_minLookahead == 0 && m_matchAvailable)
500  {
501  LiteralByte(m_byteBuffer[m_stringStart-1]);
502  m_matchAvailable = false;
503  }
504 }
505 
506 size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking)
507 {
508  if (!blocking)
509  throw BlockingInputOnly("Deflator");
510 
511  size_t accepted = 0;
512  while (accepted < length)
513  {
514  unsigned int newAccepted = FillWindow(str+accepted, length-accepted);
515  ProcessBuffer();
516  // call ProcessUncompressedData() after WritePrestreamHeader()
517  ProcessUncompressedData(str+accepted, newAccepted);
518  accepted += newAccepted;
519  }
520  assert(accepted == length);
521 
522  if (messageEnd)
523  {
524  m_minLookahead = 0;
525  ProcessBuffer();
526  EndBlock(true);
527  FlushBitBuffer();
528  WritePoststreamTail();
529  Reset();
530  }
531 
532  Output(0, NULL, 0, messageEnd, blocking);
533  return 0;
534 }
535 
536 bool Deflator::IsolatedFlush(bool hardFlush, bool blocking)
537 {
538  if (!blocking)
539  throw BlockingInputOnly("Deflator");
540 
541  m_minLookahead = 0;
542  ProcessBuffer();
543  m_minLookahead = MAX_MATCH;
544  EndBlock(false);
545  if (hardFlush)
546  EncodeBlock(false, STORED);
547  return false;
548 }
549 
550 void Deflator::LiteralByte(byte b)
551 {
552  if (m_matchBufferEnd == m_matchBuffer.size())
553  EndBlock(false);
554 
555  m_matchBuffer[m_matchBufferEnd++].literalCode = b;
556  m_literalCounts[b]++;
557  m_blockLength++;
558 }
559 
560 void Deflator::MatchFound(unsigned int distance, unsigned int length)
561 {
562  if (m_matchBufferEnd == m_matchBuffer.size())
563  EndBlock(false);
564 
565  static const unsigned int lengthCodes[] = {
566  257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268,
567  269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272,
568  273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274,
569  275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276,
570  277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277,
571  278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278,
572  279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279,
573  280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280,
574  281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
575  281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
576  282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
577  282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
578  283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
579  283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
580  284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284,
581  284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285};
582  static const unsigned int lengthBases[] =
583  {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,
584  227,258};
585  static const unsigned int distanceBases[30] =
586  {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,
587  4097,6145,8193,12289,16385,24577};
588 
589  assert(m_matchBufferEnd < m_matchBuffer.size());
590  EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++];
591  assert((length >= 3) && (length-3 < COUNTOF(lengthCodes)));
592  unsigned int lengthCode = lengthCodes[length-3];
593  m.literalCode = lengthCode;
594  m.literalExtra = length - lengthBases[lengthCode-257];
595  unsigned int distanceCode = (unsigned int)(std::upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1);
596  m.distanceCode = distanceCode;
597  m.distanceExtra = distance - distanceBases[distanceCode];
598 
599  m_literalCounts[lengthCode]++;
600  m_distanceCounts[distanceCode]++;
601  m_blockLength += length;
602 }
603 
604 inline unsigned int CodeLengthEncode(const unsigned int *begin,
605  const unsigned int *end,
606  const unsigned int *& p,
607  unsigned int &extraBits,
608  unsigned int &extraBitsLength)
609 {
610  unsigned int v = *p;
611  if ((end-p) >= 3)
612  {
613  const unsigned int *oldp = p;
614  if (v==0 && p[1]==0 && p[2]==0)
615  {
616  for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {}
617  unsigned int repeat = (unsigned int)(p - oldp);
618  if (repeat <= 10)
619  {
620  extraBits = repeat-3;
621  extraBitsLength = 3;
622  return 17;
623  }
624  else
625  {
626  extraBits = repeat-11;
627  extraBitsLength = 7;
628  return 18;
629  }
630  }
631  else if (p!=begin && v==p[-1] && v==p[1] && v==p[2])
632  {
633  for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {}
634  unsigned int repeat = (unsigned int)(p - oldp);
635  extraBits = repeat-3;
636  extraBitsLength = 2;
637  return 16;
638  }
639  }
640  p++;
641  extraBits = 0;
642  extraBitsLength = 0;
643  return v;
644 }
645 
646 void Deflator::EncodeBlock(bool eof, unsigned int blockType)
647 {
648  PutBits(eof, 1);
649  PutBits(blockType, 2);
650 
651  if (blockType == STORED)
652  {
653  assert(m_blockStart + m_blockLength <= m_byteBuffer.size());
654  assert(m_blockLength <= 0xffff);
655  FlushBitBuffer();
656  AttachedTransformation()->PutWord16(word16(m_blockLength), LITTLE_ENDIAN_ORDER);
657  AttachedTransformation()->PutWord16(word16(~m_blockLength), LITTLE_ENDIAN_ORDER);
658  AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength);
659  }
660  else
661  {
662  if (blockType == DYNAMIC)
663  {
664 #if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER <= 1300)
665  // VC60 and VC7 workaround: built-in std::reverse_iterator has two template parameters, Dinkumware only has one
666  typedef std::reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt;
667 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
668  typedef std::reverse_iterator<unsigned int *, std::random_access_iterator_tag, unsigned int> RevIt;
669 #else
670  typedef std::reverse_iterator<unsigned int *> RevIt;
671 #endif
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  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:504
Minimum deflation level, fastest speed (0)
Definition: zdeflate.h:79
An invalid argument was detected.
Definition: cryptlib.h:182
Stack-based SecBlock that grows into the heap.
Definition: secblock.h:773
Utility functions for the Crypto++ library.
Minimum window size, smallest table (9)
Definition: zdeflate.h:88
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:348
Minimum deflation level, slowest speed (9)
Definition: zdeflate.h:83
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:521
Encoding table writer.
Definition: zdeflate.h:16
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:644
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
Definition: zdeflate.cpp:536
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:1738
Maximum window size, largest table (15)
Definition: zdeflate.h:92
byte order is little-endian
Definition: cryptlib.h:125
size_t PutModifiable(byte *inString, size_t length, bool blocking=true)
Input multiple bytes that may be modified by callee.
Definition: cryptlib.h:1428
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:380
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1378
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:554
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:942
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:486
#define COUNTOF(arr)
Counts elements in an array.
Definition: misc.h:159
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:450
Default deflation level, compromise between speed (6)
Definition: zdeflate.h:81
HuffmanEncoder()
Construct a HuffmanEncoder.
Definition: zdeflate.h:46
void SetDeflateLevel(int deflateLevel)
Sets the deflation level.
Definition: zdeflate.cpp:301
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:496
Exception thrown by objects that have not implemented nonblocking input processing.
Definition: cryptlib.h:1472
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:222
void Initialize(const unsigned int *codeBits, unsigned int nCodes)
Initialize or reinitialize this object.
Definition: zdeflate.cpp:184
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:513
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:717
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: zdeflate.cpp:506
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:846
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:460
Crypto++ library namespace.
Default window size (15)
Definition: zdeflate.h:90
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: zdeflate.cpp:250
Interface for retrieving values given their names.
Definition: cryptlib.h:277