18 inline bool operator()(CryptoPP::HuffmanDecoder::code_t lhs,
const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
19 {
return lhs < rhs.code;}
21 inline bool operator()(
const CryptoPP::HuffmanDecoder::CodeInfo &lhs,
const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
22 {
return lhs.code < rhs.code;}
25inline bool LowFirstBitReader::FillBuffer(
unsigned int length)
27 while (m_bitsBuffered < length)
32 m_buffer |= (
unsigned long)b << m_bitsBuffered;
39inline unsigned long LowFirstBitReader::PeekBits(
unsigned int length)
41 bool result = FillBuffer(length);
43 return m_buffer & (((
unsigned long)1 << length) - 1);
46inline void LowFirstBitReader::SkipBits(
unsigned int length)
50 m_bitsBuffered -= length;
53inline unsigned long LowFirstBitReader::GetBits(
unsigned int length)
55 unsigned long result = PeekBits(length);
60inline HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code,
unsigned int codeBits)
62 return code << (MAX_CODE_BITS - codeBits);
65void HuffmanDecoder::Initialize(
const unsigned int *codeBits,
unsigned int nCodes)
83 throw Err(
"null code");
85 m_maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
87 if (m_maxCodeBits > MAX_CODE_BITS)
88 throw Err(
"code length exceeds maximum");
90 if (m_maxCodeBits == 0)
91 throw Err(
"null code");
94 SecBlockWithHint<unsigned int, 15+1> blCount(m_maxCodeBits+1);
95 std::fill(blCount.begin(), blCount.end(), 0);
97 for (i=0; i<nCodes; i++)
98 blCount[codeBits[i]]++;
102 SecBlockWithHint<code_t, 15+1> nextCode(m_maxCodeBits+1);
104 for (i=2; i<=m_maxCodeBits; i++)
107 if (code > code + blCount[i-1])
108 throw Err(
"codes oversubscribed");
109 code += blCount[i-1];
110 if (code > (code << 1))
111 throw Err(
"codes oversubscribed");
117 const word64 shiftedMaxCode = ((
word64)1 << m_maxCodeBits);
118 if (code > shiftedMaxCode - blCount[m_maxCodeBits])
119 throw Err(
"codes oversubscribed");
120 else if (m_maxCodeBits != 1 && code < shiftedMaxCode - blCount[m_maxCodeBits])
121 throw Err(
"codes incomplete");
124 m_codeToValue.resize(nCodes - blCount[0]);
126 for (i=0; i<nCodes; i++)
128 unsigned int len = codeBits[i];
132 code = NormalizeCode(nextCode[len]++, len);
133 m_codeToValue[j].code = code;
134 m_codeToValue[j].len = len;
135 m_codeToValue[j].value = i;
139 std::sort(m_codeToValue.begin(), m_codeToValue.end());
142 m_cacheBits =
STDMIN(9U, m_maxCodeBits);
143 m_cacheMask = (1 << m_cacheBits) - 1;
144 m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);
149 if (m_cache.size() != shiftedCache)
150 m_cache.resize((
size_t)shiftedCache);
152 for (i=0; i<m_cache.size(); i++)
156void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode)
const
158 normalizedCode &= m_normalizedCacheMask;
159 const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode, CodeLessThan())-1);
160 if (codeInfo.len <= m_cacheBits)
163 entry.value = codeInfo.value;
164 entry.len = codeInfo.len;
168 entry.begin = &codeInfo;
169 const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask, CodeLessThan())-1);
170 if (codeInfo.len == last->len)
173 entry.len = codeInfo.len;
183inline unsigned int HuffmanDecoder::Decode(code_t code, value_t &value)
const
186 LookupEntry &entry = m_cache[code & m_cacheMask];
188 code_t normalizedCode = 0;
193 FillCacheEntry(entry, normalizedCode);
202 const CodeInfo &codeInfo = (entry.type == 2)
203 ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
204 : *(std::upper_bound(entry.begin, entry.end, normalizedCode, CodeLessThan())-1);
205 value = codeInfo.value;
212 bool result = reader.FillBuffer(m_maxCodeBits);
213 CRYPTOPP_UNUSED(result);
215 unsigned int codeBits = Decode(reader.PeekBuffer(), value);
216 if (codeBits > reader.BitsBuffered())
218 reader.SkipBits(codeBits);
226 , m_state(PRE_STREAM), m_repeat(repeat), m_eof(0), m_wrappedAround(0)
227 , m_blockType(0xff), m_storedLen(0xffff), m_nextDecode(), m_literal(0)
228 , m_distance(0), m_reader(m_inQueue), m_current(0), m_lastFlush(0)
235 m_state = PRE_STREAM;
236 parameters.
GetValue(
"Repeat", m_repeat);
238 m_reader.SkipBits(m_reader.BitsBuffered());
241void Inflator::OutputByte(
byte b)
243 m_window[m_current++] = b;
244 if (m_current == m_window.
size())
246 ProcessDecompressedData(m_window + m_lastFlush, m_window.
size() - m_lastFlush);
249 m_wrappedAround =
true;
253void Inflator::OutputString(
const byte *
string,
size_t length)
257 size_t len =
UnsignedMin(length, m_window.size() - m_current);
258 std::memcpy(m_window + m_current,
string, len);
260 if (m_current == m_window.size())
262 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
265 m_wrappedAround =
true;
272void Inflator::OutputPast(
unsigned int length,
unsigned int distance)
275 if (distance <= m_current)
276 start = m_current - distance;
277 else if (m_wrappedAround && distance <= m_window.size())
278 start = m_current + m_window.
size() - distance;
282 if (start + length > m_window.size())
284 for (; start < m_window.size(); start++, length--)
285 OutputByte(m_window[start]);
289 if (start + length > m_current || m_current + length >= m_window.size())
292 OutputByte(m_window[start++]);
296 std::memcpy(m_window + m_current, m_window + start, length);
301size_t Inflator::Put2(
const byte *inString,
size_t length,
int messageEnd,
bool blocking)
307 ProcessInput(messageEnd != 0);
310 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
313 Output(0, NULLPTR, 0, messageEnd, blocking);
329void Inflator::ProcessInput(
bool flush)
336 if (!flush && m_inQueue.
CurrentSize() < MaxPrestreamHeaderSize())
338 ProcessPrestreamHeader();
339 m_state = WAIT_HEADER;
340 m_wrappedAround =
false;
343 m_window.
New(((
size_t) 1) << GetLog2WindowSize());
348 const size_t MAX_HEADER_SIZE =
BitsToBytes(3+5+5+4+19*7+286*15+19*15);
349 if (m_inQueue.
CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
359 if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
361 ProcessPoststreamTail();
362 m_state = m_repeat ? PRE_STREAM : AFTER_END;
364 if (m_inQueue.IsEmpty())
374void Inflator::DecodeHeader()
376 if (!m_reader.FillBuffer(3))
378 m_eof = m_reader.GetBits(1) != 0;
379 m_blockType = (
byte)m_reader.GetBits(2);
385 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
386 if (!m_reader.FillBuffer(32))
388 m_storedLen = (
word16)m_reader.GetBits(16);
390 if (nlen != (
word16)~m_storedLen)
395 m_nextDecode = LITERAL;
399 if (!m_reader.FillBuffer(5+5+4))
401 unsigned int hlit = m_reader.GetBits(5);
402 unsigned int hdist = m_reader.GetBits(5);
403 unsigned int hclen = m_reader.GetBits(4);
406 FixedSizeSecBlock<unsigned int, 286+32> codeLengths;
407 static const unsigned int border[] = {
408 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
409 std::fill(codeLengths.
begin(), codeLengths+19, 0);
410 for (i=0; i<hclen+4; ++i)
413 codeLengths[border[i]] = m_reader.GetBits(3);
419 unsigned int k=0, count=0, repeater=0;
420 HuffmanDecoder codeLengthDecoder(codeLengths, 19);
421 for (i=0; i < hlit+257+hdist+1; )
423 k = 0, count = 0, repeater = 0;
424 result = codeLengthDecoder.Decode(m_reader, k);
435 if (!m_reader.FillBuffer(2))
437 count = 3 + m_reader.GetBits(2);
440 repeater = codeLengths[i-1];
443 if (!m_reader.FillBuffer(3))
445 count = 3 + m_reader.GetBits(3);
449 if (!m_reader.FillBuffer(7))
451 count = 11 + m_reader.GetBits(7);
455 if (i + count > hlit+257+hdist+1)
457 std::fill(codeLengths + i, codeLengths + i + count, repeater);
460 m_dynamicLiteralDecoder.Initialize(codeLengths, hlit+257);
461 if (hdist == 0 && codeLengths[hlit+257] == 0)
467 m_dynamicDistanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
468 m_nextDecode = LITERAL;
470 catch (HuffmanDecoder::Err &)
479 m_state = DECODING_BODY;
482bool Inflator::DecodeBody()
484 bool blockEnd =
false;
489 while (!m_inQueue.IsEmpty() && !blockEnd)
492 const byte *block = m_inQueue.Spy(size);
496 OutputString(block, size);
497 m_inQueue.Skip(size);
498 m_storedLen = m_storedLen - (
word16)size;
499 if (m_storedLen == 0)
505 static const unsigned int lengthStarts[] = {
506 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
507 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
508 static const unsigned int lengthExtraBits[] = {
509 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
510 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
511 static const unsigned int distanceStarts[] = {
512 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
513 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
514 8193, 12289, 16385, 24577};
515 static const unsigned int distanceExtraBits[] = {
516 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
517 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
520 const HuffmanDecoder& literalDecoder = GetLiteralDecoder();
521 const HuffmanDecoder& distanceDecoder = GetDistanceDecoder();
523 switch (m_nextDecode)
528 if (!literalDecoder.Decode(m_reader, m_literal))
530 m_nextDecode = LITERAL;
534 OutputByte((
byte)m_literal);
535 else if (m_literal == 256)
547 bits = lengthExtraBits[m_literal-257];
548 if (!m_reader.FillBuffer(bits))
550 m_nextDecode = LENGTH_BITS;
554 m_literal = m_reader.GetBits(bits) + lengthStarts[m_literal-257];
556 if (!distanceDecoder.Decode(m_reader, m_distance))
558 m_nextDecode = DISTANCE;
563 if (m_distance >=
COUNTOF(distanceExtraBits))
565 bits = distanceExtraBits[m_distance];
566 if (!m_reader.FillBuffer(bits))
568 m_nextDecode = DISTANCE_BITS;
572 if (m_distance >=
COUNTOF(distanceStarts))
574 m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
575 OutputPast(m_literal, m_distance);
588 m_reader.SkipBits(m_reader.BitsBuffered()%8);
589 if (m_reader.BitsBuffered())
592 SecBlockWithHint<byte, 4> buffer(m_reader.BitsBuffered() / 8);
593 for (
unsigned int i=0; i<buffer.size(); i++)
594 buffer[i] = (
byte)m_reader.GetBits(8);
595 m_inQueue.Unget(buffer, buffer.size());
597 m_state = POST_STREAM;
600 m_state = WAIT_HEADER;
605void Inflator::FlushOutput()
607 if (m_state != PRE_STREAM)
610 ProcessDecompressedData(m_window + m_lastFlush, m_current - m_lastFlush);
611 m_lastFlush = m_current;
615void Inflator::CreateFixedLiteralDecoder()
617 unsigned int codeLengths[288];
618 std::fill(codeLengths + 0, codeLengths + 144, 8);
619 std::fill(codeLengths + 144, codeLengths + 256, 9);
620 std::fill(codeLengths + 256, codeLengths + 280, 7);
621 std::fill(codeLengths + 280, codeLengths + 288, 8);
622 m_fixedLiteralDecoder.reset(
new HuffmanDecoder);
623 m_fixedLiteralDecoder->Initialize(codeLengths, 288);
626void Inflator::CreateFixedDistanceDecoder()
628 unsigned int codeLengths[32];
629 std::fill(codeLengths + 0, codeLengths + 32, 5);
630 m_fixedDistanceDecoder.reset(
new HuffmanDecoder);
631 m_fixedDistanceDecoder->Initialize(codeLengths, 32);
636 if (m_blockType == 1)
638 if (m_fixedLiteralDecoder.get() == NULLPTR)
639 CreateFixedLiteralDecoder();
640 return *m_fixedLiteralDecoder;
644 return m_dynamicLiteralDecoder;
650 if (m_blockType == 1)
652 if (m_fixedDistanceDecoder.get() == NULLPTR)
653 CreateFixedDistanceDecoder();
654 return *m_fixedDistanceDecoder;
658 return m_dynamicDistanceDecoder;
int GetAutoSignalPropagation() const
AutoSignaling(int propagation=-1)
lword CurrentSize() const
Determine data size.
Filter(BufferedTransformation *attachment=NULL)
Construct a Filter.
void Detach(BufferedTransformation *newAttachment=NULL)
Replace an attached transformation.
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Exception thrown when a bad block is encountered.
Exception thrown when an invalid distance is encountered.
Exception thrown when a truncated stream is encountered.
void IsolatedInitialize(const NameValuePairs ¶meters)
Initialize or reinitialize this object, without signal propagation.
Inflator(BufferedTransformation *attachment=NULL, bool repeat=false, int autoSignalPropagation=-1)
RFC 1951 Decompressor.
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
Helper class to finalize Puts on ByteQueue.
Interface for retrieving values given their names.
bool GetValue(const char *name, T &value) const
Get a named value.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
void New(size_type newSize)
Change size without preserving contents.
size_type size() const
Provides the count of elements in the SecBlock.
unsigned char byte
8-bit unsigned datatype
unsigned short word16
16-bit unsigned datatype
unsigned long long word64
64-bit unsigned datatype
byte BitReverse(byte value)
Reverses bits in a 8-bit value.
#define COUNTOF(arr)
Counts elements in an array.
#define SIZE_MAX
The maximum value of a machine word.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be negative and incorrectly promoted.
Crypto++ library namespace.
Classes and functions for secure memory allocations.
Classes for automatic resource management.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
DEFLATE compression and decompression (RFC 1951)