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