11 NAMESPACE_BEGIN(CryptoPP)
15 inline bool operator()(CryptoPP::HuffmanDecoder::code_t lhs,
const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
16 {
return lhs < rhs.code;}
18 inline bool operator()(
const CryptoPP::HuffmanDecoder::CodeInfo &lhs,
const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
19 {
return lhs.code < rhs.code;}
22 inline bool LowFirstBitReader::FillBuffer(
unsigned int length)
24 while (m_bitsBuffered < length)
29 m_buffer |= (
unsigned long)b << m_bitsBuffered;
32 assert(m_bitsBuffered <=
sizeof(
unsigned long)*8);
36 inline unsigned long LowFirstBitReader::PeekBits(
unsigned int length)
38 bool result = FillBuffer(length);
40 return m_buffer & (((
unsigned long)1 << length) - 1);
43 inline void LowFirstBitReader::SkipBits(
unsigned int length)
45 assert(m_bitsBuffered >= length);
47 m_bitsBuffered -= length;
50 inline unsigned long LowFirstBitReader::GetBits(
unsigned int length)
52 unsigned long result = PeekBits(length);
57 inline HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code,
unsigned int codeBits)
59 return code << (MAX_CODE_BITS - codeBits);
62 void HuffmanDecoder::Initialize(
const unsigned int *codeBits,
unsigned int nCodes)
80 throw Err(
"null code");
82 m_maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
84 if (m_maxCodeBits > MAX_CODE_BITS)
85 throw Err(
"code length exceeds maximum");
87 if (m_maxCodeBits == 0)
88 throw Err(
"null code");
92 std::fill(blCount.begin(), blCount.end(), 0);
94 for (i=0; i<nCodes; i++)
95 blCount[codeBits[i]]++;
101 for (i=2; i<=m_maxCodeBits; i++)
104 if (code > code + blCount[i-1])
105 throw Err(
"codes oversubscribed");
106 code += blCount[i-1];
107 if (code > (code << 1))
108 throw Err(
"codes oversubscribed");
113 if (code > (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
114 throw Err(
"codes oversubscribed");
115 else if (m_maxCodeBits != 1 && code < (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
116 throw Err(
"codes incomplete");
119 m_codeToValue.resize(nCodes - blCount[0]);
121 for (i=0; i<nCodes; i++)
123 unsigned int len = codeBits[i];
126 code = NormalizeCode(nextCode[len]++, len);
127 m_codeToValue[j].code = code;
128 m_codeToValue[j].len = len;
129 m_codeToValue[j].value = i;
133 std::sort(m_codeToValue.begin(), m_codeToValue.end());
136 m_cacheBits = STDMIN(9U, m_maxCodeBits);
137 m_cacheMask = (1 << m_cacheBits) - 1;
138 m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);
139 assert(m_normalizedCacheMask == BitReverse(m_cacheMask));
141 if (m_cache.size() != size_t(1) << m_cacheBits)
142 m_cache.resize(1 << m_cacheBits);
144 for (i=0; i<m_cache.size(); i++)
148 void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode)
const
150 normalizedCode &= m_normalizedCacheMask;
151 const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode,
CodeLessThan())-1);
152 if (codeInfo.len <= m_cacheBits)
155 entry.value = codeInfo.value;
156 entry.len = codeInfo.len;
160 entry.begin = &codeInfo;
161 const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask,
CodeLessThan())-1);
162 if (codeInfo.len == last->len)
165 entry.len = codeInfo.len;
175 inline unsigned int HuffmanDecoder::Decode(code_t code, value_t &value)
const
177 assert(m_codeToValue.size() > 0);
178 LookupEntry &entry = m_cache[code & m_cacheMask];
180 code_t normalizedCode;
182 normalizedCode = BitReverse(code);
185 FillCacheEntry(entry, normalizedCode);
194 const CodeInfo &codeInfo = (entry.type == 2)
195 ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
196 : *(std::upper_bound(entry.begin, entry.end, normalizedCode,
CodeLessThan())-1);
197 value = codeInfo.value;
204 reader.FillBuffer(m_maxCodeBits);
205 unsigned int codeBits = Decode(reader.PeekBuffer(), value);
206 if (codeBits > reader.BitsBuffered())
208 reader.SkipBits(codeBits);
216 , m_state(PRE_STREAM), m_repeat(repeat), m_reader(m_inQueue)
221 void Inflator::IsolatedInitialize(
const NameValuePairs ¶meters)
223 m_state = PRE_STREAM;
224 parameters.
GetValue(
"Repeat", m_repeat);
226 m_reader.SkipBits(m_reader.BitsBuffered());
229 void Inflator::OutputByte(byte b)
231 m_window[m_current++] = b;
232 if (m_current == m_window.size())
234 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
237 m_wrappedAround =
true;
241 void Inflator::OutputString(
const byte *
string,
size_t length)
245 size_t len = UnsignedMin(length, m_window.size() - m_current);
246 memcpy(m_window + m_current,
string, len);
248 if (m_current == m_window.size())
250 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
253 m_wrappedAround =
true;
260 void Inflator::OutputPast(
unsigned int length,
unsigned int distance)
263 if (distance <= m_current)
264 start = m_current - distance;
265 else if (m_wrappedAround && distance <= m_window.size())
266 start = m_current + m_window.size() - distance;
270 if (start + length > m_window.size())
272 for (; start < m_window.size(); start++, length--)
273 OutputByte(m_window[start]);
277 if (start + length > m_current || m_current + length >= m_window.size())
280 OutputByte(m_window[start++]);
284 memcpy(m_window + m_current, m_window + start, length);
289 size_t Inflator::Put2(
const byte *inString,
size_t length,
int messageEnd,
bool blocking)
295 ProcessInput(messageEnd != 0);
298 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
301 Output(0, NULL, 0, messageEnd, blocking);
305 bool Inflator::IsolatedFlush(
bool hardFlush,
bool blocking)
308 throw BlockingInputOnly(
"Inflator");
317 void Inflator::ProcessInput(
bool flush)
324 if (!flush && m_inQueue.CurrentSize() < MaxPrestreamHeaderSize())
326 ProcessPrestreamHeader();
327 m_state = WAIT_HEADER;
328 m_wrappedAround =
false;
331 m_window.
New(1 << GetLog2WindowSize());
336 const size_t MAX_HEADER_SIZE = BitsToBytes(3+5+5+4+19*7+286*15+19*15);
337 if (m_inQueue.CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
347 if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
349 ProcessPoststreamTail();
350 m_state = m_repeat ? PRE_STREAM : AFTER_END;
351 Output(0, NULL, 0, GetAutoSignalPropagation(),
true);
352 if (m_inQueue.IsEmpty())
362 void Inflator::DecodeHeader()
364 if (!m_reader.FillBuffer(3))
365 throw UnexpectedEndErr();
366 m_eof = m_reader.GetBits(1) != 0;
367 m_blockType = (byte)m_reader.GetBits(2);
372 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
373 if (!m_reader.FillBuffer(32))
374 throw UnexpectedEndErr();
375 m_storedLen = (word16)m_reader.GetBits(16);
376 word16 nlen = (word16)m_reader.GetBits(16);
377 if (nlen != (word16)~m_storedLen)
382 m_nextDecode = LITERAL;
386 if (!m_reader.FillBuffer(5+5+4))
387 throw UnexpectedEndErr();
388 unsigned int hlit = m_reader.GetBits(5);
389 unsigned int hdist = m_reader.GetBits(5);
390 unsigned int hclen = m_reader.GetBits(4);
394 static const unsigned int border[] = {
395 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
396 std::fill(codeLengths.begin(), codeLengths+19, 0);
397 for (i=0; i<hclen+4; i++)
398 codeLengths[border[i]] = m_reader.GetBits(3);
403 for (i = 0; i < hlit+257+hdist+1; )
405 unsigned int k, count, repeater;
406 bool result = codeLengthDecoder.Decode(m_reader, k);
408 throw UnexpectedEndErr();
417 if (!m_reader.FillBuffer(2))
418 throw UnexpectedEndErr();
419 count = 3 + m_reader.GetBits(2);
422 repeater = codeLengths[i-1];
425 if (!m_reader.FillBuffer(3))
426 throw UnexpectedEndErr();
427 count = 3 + m_reader.GetBits(3);
431 if (!m_reader.FillBuffer(7))
432 throw UnexpectedEndErr();
433 count = 11 + m_reader.GetBits(7);
437 if (i + count > hlit+257+hdist+1)
439 std::fill(codeLengths + i, codeLengths + i + count, repeater);
442 m_dynamicLiteralDecoder.Initialize(codeLengths, hlit+257);
443 if (hdist == 0 && codeLengths[hlit+257] == 0)
449 m_dynamicDistanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
450 m_nextDecode = LITERAL;
461 m_state = DECODING_BODY;
464 bool Inflator::DecodeBody()
466 bool blockEnd =
false;
470 assert(m_reader.BitsBuffered() == 0);
471 while (!m_inQueue.IsEmpty() && !blockEnd)
474 const byte *block = m_inQueue.Spy(size);
475 size = UnsignedMin(m_storedLen, size);
476 OutputString(block, size);
477 m_inQueue.
Skip(size);
478 m_storedLen -= (word16)size;
479 if (m_storedLen == 0)
485 static const unsigned int lengthStarts[] = {
486 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
487 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
488 static const unsigned int lengthExtraBits[] = {
489 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
490 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
491 static const unsigned int distanceStarts[] = {
492 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
493 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
494 8193, 12289, 16385, 24577};
495 static const unsigned int distanceExtraBits[] = {
496 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
497 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
503 switch (m_nextDecode)
508 if (!literalDecoder.Decode(m_reader, m_literal))
510 m_nextDecode = LITERAL;
514 OutputByte((byte)m_literal);
515 else if (m_literal == 256)
526 bits = lengthExtraBits[m_literal-257];
527 if (!m_reader.FillBuffer(bits))
529 m_nextDecode = LENGTH_BITS;
532 m_literal = m_reader.GetBits(bits) + lengthStarts[m_literal-257];
534 if (!distanceDecoder.Decode(m_reader, m_distance))
536 m_nextDecode = DISTANCE;
540 bits = distanceExtraBits[m_distance];
541 if (!m_reader.FillBuffer(bits))
543 m_nextDecode = DISTANCE_BITS;
546 m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
547 OutputPast(m_literal, m_distance);
557 m_reader.SkipBits(m_reader.BitsBuffered()%8);
558 if (m_reader.BitsBuffered())
562 for (
unsigned int i=0; i<buffer.size(); i++)
563 buffer[i] = (byte)m_reader.GetBits(8);
564 m_inQueue.Unget(buffer, buffer.size());
566 m_state = POST_STREAM;
569 m_state = WAIT_HEADER;
574 void Inflator::FlushOutput()
576 if (m_state != PRE_STREAM)
578 assert(m_current >= m_lastFlush);
579 ProcessDecompressedData(m_window + m_lastFlush, m_current - m_lastFlush);
580 m_lastFlush = m_current;
588 unsigned int codeLengths[288];
589 std::fill(codeLengths + 0, codeLengths + 144, 8);
590 std::fill(codeLengths + 144, codeLengths + 256, 9);
591 std::fill(codeLengths + 256, codeLengths + 280, 7);
592 std::fill(codeLengths + 280, codeLengths + 288, 8);
594 pDecoder->Initialize(codeLengths, 288);
595 return pDecoder.release();
603 unsigned int codeLengths[32];
604 std::fill(codeLengths + 0, codeLengths + 32, 5);
606 pDecoder->Initialize(codeLengths, 32);
607 return pDecoder.release();