monotone

monotone Mtn Source Tree

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

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status