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;}
25 inline bool LowFirstBitReader::FillBuffer(
unsigned int length)
27 while (m_bitsBuffered < length)
32 m_buffer |= (
unsigned long)b << m_bitsBuffered;
35 assert(m_bitsBuffered <=
sizeof(
unsigned long)*8);
39 inline unsigned long LowFirstBitReader::PeekBits(
unsigned int length)
41 bool result = FillBuffer(length);
42 CRYPTOPP_UNUSED(result); assert(result);
43 return m_buffer & (((
unsigned long)1 << length) - 1);
46 inline void LowFirstBitReader::SkipBits(
unsigned int length)
48 assert(m_bitsBuffered >= length);
50 m_bitsBuffered -= length;
53 inline unsigned long LowFirstBitReader::GetBits(
unsigned int length)
55 unsigned long result = PeekBits(length);
60 inline HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code,
unsigned int codeBits)
62 return code << (MAX_CODE_BITS - codeBits);
65 void 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");
95 std::fill(blCount.
begin(), blCount.
end(), 0);
97 for (i=0; i<nCodes; i++)
98 blCount[codeBits[i]]++;
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 unsigned long long shiftedMaxCode = (1ULL << 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];
131 code = NormalizeCode(nextCode[len]++, len);
132 m_codeToValue[j].code = code;
133 m_codeToValue[j].len = len;
134 m_codeToValue[j].value = i;
138 std::sort(m_codeToValue.begin(), m_codeToValue.end());
141 m_cacheBits =
STDMIN(9U, m_maxCodeBits);
142 m_cacheMask = (1 << m_cacheBits) - 1;
143 m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);
144 assert(m_normalizedCacheMask ==
BitReverse(m_cacheMask));
146 const unsigned long long shiftedCache = (1ULL << m_cacheBits);
148 if (m_cache.size() != shiftedCache)
149 m_cache.resize((
size_t)shiftedCache);
151 for (i=0; i<m_cache.size(); i++)
155 void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode)
const 157 normalizedCode &= m_normalizedCacheMask;
158 const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode,
CodeLessThan())-1);
159 if (codeInfo.len <= m_cacheBits)
162 entry.value = codeInfo.value;
163 entry.len = codeInfo.len;
167 entry.begin = &codeInfo;
168 const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask,
CodeLessThan())-1);
169 if (codeInfo.len == last->len)
172 entry.len = codeInfo.len;
182 inline unsigned int HuffmanDecoder::Decode(code_t code, value_t &value)
const 184 assert(m_codeToValue.size() > 0);
185 LookupEntry &entry = m_cache[code & m_cacheMask];
187 code_t normalizedCode = 0;
192 FillCacheEntry(entry, normalizedCode);
201 const CodeInfo &codeInfo = (entry.type == 2)
202 ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
203 : *(std::upper_bound(entry.begin, entry.end, normalizedCode,
CodeLessThan())-1);
204 value = codeInfo.value;
211 bool result = reader.FillBuffer(m_maxCodeBits);
212 if(!result)
return false;
214 unsigned int codeBits = Decode(reader.PeekBuffer(), value);
215 if (codeBits > reader.BitsBuffered())
217 reader.SkipBits(codeBits);
225 , m_state(PRE_STREAM), m_repeat(repeat), m_eof(0), m_wrappedAround(0)
226 , m_blockType(0xff), m_storedLen(0xffff), m_nextDecode(), m_literal(0)
227 , m_distance(0), m_reader(m_inQueue), m_current(0), m_lastFlush(0)
234 m_state = PRE_STREAM;
235 parameters.
GetValue(
"Repeat", m_repeat);
237 m_reader.SkipBits(m_reader.BitsBuffered());
240 void Inflator::OutputByte(byte b)
242 m_window[m_current++] = b;
243 if (m_current == m_window.
size())
245 ProcessDecompressedData(m_window + m_lastFlush, m_window.
size() - m_lastFlush);
248 m_wrappedAround =
true;
252 void Inflator::OutputString(
const byte *
string,
size_t length)
257 memcpy(m_window + m_current,
string, len);
259 if (m_current == m_window.
size())
261 ProcessDecompressedData(m_window + m_lastFlush, m_window.
size() - m_lastFlush);
264 m_wrappedAround =
true;
271 void Inflator::OutputPast(
unsigned int length,
unsigned int distance)
274 if (distance <= m_current)
275 start = m_current - distance;
276 else if (m_wrappedAround && distance <= m_window.
size())
277 start = m_current + m_window.
size() - distance;
281 if (start + length > m_window.
size())
283 for (; start < m_window.
size(); start++, length--)
284 OutputByte(m_window[start]);
288 if (start + length > m_current || m_current + length >= m_window.
size())
291 OutputByte(m_window[start++]);
295 memcpy(m_window + m_current, m_window + start, length);
300 size_t Inflator::Put2(
const byte *inString,
size_t length,
int messageEnd,
bool blocking)
306 ProcessInput(messageEnd != 0);
309 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
312 Output(0, NULL, 0, messageEnd, blocking);
328 void Inflator::ProcessInput(
bool flush)
335 if (!flush && m_inQueue.CurrentSize() < MaxPrestreamHeaderSize())
337 ProcessPrestreamHeader();
338 m_state = WAIT_HEADER;
339 m_wrappedAround =
false;
342 m_window.
New(1 << GetLog2WindowSize());
347 const size_t MAX_HEADER_SIZE =
BitsToBytes(3+5+5+4+19*7+286*15+19*15);
348 if (m_inQueue.CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
358 if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
360 ProcessPoststreamTail();
361 m_state = m_repeat ? PRE_STREAM : AFTER_END;
362 Output(0, NULL, 0, GetAutoSignalPropagation(),
true);
363 if (m_inQueue.IsEmpty())
373 void Inflator::DecodeHeader()
375 if (!m_reader.FillBuffer(3))
377 m_eof = m_reader.GetBits(1) != 0;
378 m_blockType = (byte)m_reader.GetBits(2);
383 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
384 if (!m_reader.FillBuffer(32))
386 m_storedLen = (word16)m_reader.GetBits(16);
387 word16 nlen = (word16)m_reader.GetBits(16);
388 if (nlen != (word16)~m_storedLen)
393 m_nextDecode = LITERAL;
397 if (!m_reader.FillBuffer(5+5+4))
399 unsigned int hlit = m_reader.GetBits(5);
400 unsigned int hdist = m_reader.GetBits(5);
401 unsigned int hclen = m_reader.GetBits(4);
405 static const unsigned int border[] = {
406 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
407 std::fill(codeLengths.
begin(), codeLengths+19, 0);
408 for (i=0; i<hclen+4; i++)
409 codeLengths[border[i]] = m_reader.GetBits(3);
414 for (i = 0; i < hlit+257+hdist+1; )
416 unsigned int k = 0, count = 0, repeater = 0;
417 bool result = codeLengthDecoder.Decode(m_reader, k);
428 if (!m_reader.FillBuffer(2))
430 count = 3 + m_reader.GetBits(2);
433 repeater = codeLengths[i-1];
436 if (!m_reader.FillBuffer(3))
438 count = 3 + m_reader.GetBits(3);
442 if (!m_reader.FillBuffer(7))
444 count = 11 + m_reader.GetBits(7);
448 if (i + count > hlit+257+hdist+1)
450 std::fill(codeLengths + i, codeLengths + i + count, repeater);
453 m_dynamicLiteralDecoder.Initialize(codeLengths, hlit+257);
454 if (hdist == 0 && codeLengths[hlit+257] == 0)
460 m_dynamicDistanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
461 m_nextDecode = LITERAL;
472 m_state = DECODING_BODY;
475 bool Inflator::DecodeBody()
477 bool blockEnd =
false;
481 assert(m_reader.BitsBuffered() == 0);
482 while (!m_inQueue.IsEmpty() && !blockEnd)
485 const byte *block = m_inQueue.Spy(size);
487 assert(size <= 0xffff);
489 OutputString(block, size);
490 m_inQueue.
Skip(size);
491 m_storedLen = m_storedLen - (word16)size;
492 if (m_storedLen == 0)
498 static const unsigned int lengthStarts[] = {
499 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
500 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
501 static const unsigned int lengthExtraBits[] = {
502 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
503 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
504 static const unsigned int distanceStarts[] = {
505 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
506 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
507 8193, 12289, 16385, 24577};
508 static const unsigned int distanceExtraBits[] = {
509 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
510 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
516 switch (m_nextDecode)
521 if (!literalDecoder.Decode(m_reader, m_literal))
523 m_nextDecode = LITERAL;
527 OutputByte((byte)m_literal);
528 else if (m_literal == 256)
539 bits = lengthExtraBits[m_literal-257];
540 if (!m_reader.FillBuffer(bits))
542 m_nextDecode = LENGTH_BITS;
545 m_literal = m_reader.GetBits(bits) + lengthStarts[m_literal-257];
547 if (!distanceDecoder.Decode(m_reader, m_distance))
549 m_nextDecode = DISTANCE;
553 bits = distanceExtraBits[m_distance];
554 if (!m_reader.FillBuffer(bits))
556 m_nextDecode = DISTANCE_BITS;
559 m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
560 OutputPast(m_literal, m_distance);
573 m_reader.SkipBits(m_reader.BitsBuffered()%8);
574 if (m_reader.BitsBuffered())
578 for (
unsigned int i=0; i<buffer.size(); i++)
579 buffer[i] = (byte)m_reader.GetBits(8);
580 m_inQueue.Unget(buffer, buffer.size());
582 m_state = POST_STREAM;
585 m_state = WAIT_HEADER;
590 void Inflator::FlushOutput()
592 if (m_state != PRE_STREAM)
594 assert(m_current >= m_lastFlush);
595 ProcessDecompressedData(m_window + m_lastFlush, m_current - m_lastFlush);
596 m_lastFlush = m_current;
604 unsigned int codeLengths[288];
605 std::fill(codeLengths + 0, codeLengths + 144, 8);
606 std::fill(codeLengths + 144, codeLengths + 256, 9);
607 std::fill(codeLengths + 256, codeLengths + 280, 7);
608 std::fill(codeLengths + 280, codeLengths + 288, 8);
610 pDecoder->Initialize(codeLengths, 288);
611 return pDecoder.release();
619 unsigned int codeLengths[32];
620 std::fill(codeLengths + 0, codeLengths + 32, 5);
622 pDecoder->Initialize(codeLengths, 32);
623 return pDecoder.release();
Inflator(BufferedTransformation *attachment=NULL, bool repeat=false, int autoSignalPropagation=-1)
RFC 1951 Decompressor.
iterator end()
Provides an iterator pointing beyond the last element in the memory block.
use this to make sure LazyPut is finalized in event of exception
Stack-based SecBlock that grows into the heap.
Restricts the instantiation of a class to one static object without locks.
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
size_type size() const
Provides the count of elements in the SecBlock.
Classes for automatic resource management.
bool IsolatedFlush(bool hardFlush, bool blocking)
Flushes data buffered by this object, without signal propagation.
void New(size_type newSize)
Change size without preserving contents.
byte BitReverse(byte value)
Reverses bits in a 8-bit value.
Pointer that overloads operator→
Classes and functions for secure memory allocations.
void IsolatedInitialize(const NameValuePairs ¶meters)
Initialize or reinitialize this object, without signal propagation.
bool GetValue(const char *name, T &value) const
Get a named value.
void Detach(BufferedTransformation *newAttachment=NULL)
Replace an attached transformation.
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Fixed size stack-based SecBlock.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Provides auto signaling support.
Implementation of BufferedTransformation's attachment interface.
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Crypto++ library namespace.
#define SIZE_MAX
The maximum value of a machine word.
Interface for retrieving values given their names.