00001
00002
00003
00004
00005
00006
00007
00008 #include "pch.h"
00009 #include "zinflate.h"
00010
00011 NAMESPACE_BEGIN(CryptoPP)
00012
00013 struct CodeLessThan
00014 {
00015 inline bool operator()(const CryptoPP::HuffmanDecoder::code_t lhs, const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
00016 {return lhs < rhs.code;}
00017 };
00018
00019 inline bool LowFirstBitReader::FillBuffer(unsigned int length)
00020 {
00021 while (m_bitsBuffered < length)
00022 {
00023 byte b;
00024 if (!m_store.Get(b))
00025 return false;
00026 m_buffer |= (unsigned long)b << m_bitsBuffered;
00027 m_bitsBuffered += 8;
00028 }
00029 assert(m_bitsBuffered <= sizeof(unsigned long)*8);
00030 return true;
00031 }
00032
00033 inline unsigned long LowFirstBitReader::PeekBits(unsigned int length)
00034 {
00035 bool result = FillBuffer(length);
00036 assert(result);
00037 return m_buffer & (((unsigned long)1 << length) - 1);
00038 }
00039
00040 inline void LowFirstBitReader::SkipBits(unsigned int length)
00041 {
00042 assert(m_bitsBuffered >= length);
00043 m_buffer >>= length;
00044 m_bitsBuffered -= length;
00045 }
00046
00047 inline unsigned long LowFirstBitReader::GetBits(unsigned int length)
00048 {
00049 unsigned long result = PeekBits(length);
00050 SkipBits(length);
00051 return result;
00052 }
00053
00054 inline HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code, unsigned int codeBits)
00055 {
00056 return code << (MAX_CODE_BITS - codeBits);
00057 }
00058
00059 void HuffmanDecoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)
00060 {
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076 if (nCodes == 0)
00077 throw Err("null code");
00078
00079 m_maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
00080
00081 if (m_maxCodeBits > MAX_CODE_BITS)
00082 throw Err("code length exceeds maximum");
00083
00084 if (m_maxCodeBits == 0)
00085 throw Err("null code");
00086
00087
00088 SecBlockWithHint<unsigned int, 15+1> blCount(m_maxCodeBits+1);
00089 std::fill(blCount.begin(), blCount.end(), 0);
00090 unsigned int i;
00091 for (i=0; i<nCodes; i++)
00092 blCount[codeBits[i]]++;
00093
00094
00095 code_t code = 0;
00096 SecBlockWithHint<code_t, 15+1> nextCode(m_maxCodeBits+1);
00097 nextCode[1] = 0;
00098 for (i=2; i<=m_maxCodeBits; i++)
00099 {
00100
00101 if (code > code + blCount[i-1])
00102 throw Err("codes oversubscribed");
00103 code += blCount[i-1];
00104 if (code > (code << 1))
00105 throw Err("codes oversubscribed");
00106 code <<= 1;
00107 nextCode[i] = code;
00108 }
00109
00110 if (code > (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
00111 throw Err("codes oversubscribed");
00112 else if (m_maxCodeBits != 1 && code < (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
00113 throw Err("codes incomplete");
00114
00115
00116 m_codeToValue.resize(nCodes - blCount[0]);
00117 unsigned int j=0;
00118 for (i=0; i<nCodes; i++)
00119 {
00120 unsigned int len = codeBits[i];
00121 if (len != 0)
00122 {
00123 code = NormalizeCode(nextCode[len]++, len);
00124 m_codeToValue[j].code = code;
00125 m_codeToValue[j].len = len;
00126 m_codeToValue[j].value = i;
00127 j++;
00128 }
00129 }
00130 std::sort(m_codeToValue.begin(), m_codeToValue.end());
00131
00132
00133 m_cacheBits = STDMIN(9U, m_maxCodeBits);
00134 m_cacheMask = (1 << m_cacheBits) - 1;
00135 m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);
00136 assert(m_normalizedCacheMask == BitReverse(m_cacheMask));
00137
00138 if (m_cache.size() != 1 << m_cacheBits)
00139 m_cache.resize(1 << m_cacheBits);
00140
00141 for (i=0; i<m_cache.size(); i++)
00142 m_cache[i].type = 0;
00143 }
00144
00145 void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const
00146 {
00147 normalizedCode &= m_normalizedCacheMask;
00148 const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode, CodeLessThan())-1);
00149 if (codeInfo.len <= m_cacheBits)
00150 {
00151 entry.type = 1;
00152 entry.value = codeInfo.value;
00153 entry.len = codeInfo.len;
00154 }
00155 else
00156 {
00157 entry.begin = &codeInfo;
00158 const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask, CodeLessThan())-1);
00159 if (codeInfo.len == last->len)
00160 {
00161 entry.type = 2;
00162 entry.len = codeInfo.len;
00163 }
00164 else
00165 {
00166 entry.type = 3;
00167 entry.end = last+1;
00168 }
00169 }
00170 }
00171
00172 inline unsigned int HuffmanDecoder::Decode(code_t code, value_t &value) const
00173 {
00174 assert(m_codeToValue.size() > 0);
00175 LookupEntry &entry = m_cache[code & m_cacheMask];
00176
00177 code_t normalizedCode;
00178 if (entry.type != 1)
00179 normalizedCode = BitReverse(code);
00180
00181 if (entry.type == 0)
00182 FillCacheEntry(entry, normalizedCode);
00183
00184 if (entry.type == 1)
00185 {
00186 value = entry.value;
00187 return entry.len;
00188 }
00189 else
00190 {
00191 const CodeInfo &codeInfo = (entry.type == 2)
00192 ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
00193 : *(std::upper_bound(entry.begin, entry.end, normalizedCode, CodeLessThan())-1);
00194 value = codeInfo.value;
00195 return codeInfo.len;
00196 }
00197 }
00198
00199 bool HuffmanDecoder::Decode(LowFirstBitReader &reader, value_t &value) const
00200 {
00201 reader.FillBuffer(m_maxCodeBits);
00202 unsigned int codeBits = Decode(reader.PeekBuffer(), value);
00203 if (codeBits > reader.BitsBuffered())
00204 return false;
00205 reader.SkipBits(codeBits);
00206 return true;
00207 }
00208
00209
00210
00211 Inflator::Inflator(BufferedTransformation *attachment, bool repeat, int propagation)
00212 : AutoSignaling<Filter>(propagation)
00213 , m_state(PRE_STREAM), m_repeat(repeat), m_reader(m_inQueue)
00214 {
00215 Detach(attachment);
00216 }
00217
00218 void Inflator::IsolatedInitialize(const NameValuePairs ¶meters)
00219 {
00220 m_state = PRE_STREAM;
00221 parameters.GetValue("Repeat", m_repeat);
00222 m_inQueue.Clear();
00223 m_reader.SkipBits(m_reader.BitsBuffered());
00224 }
00225
00226 void Inflator::OutputByte(byte b)
00227 {
00228 m_window[m_current++] = b;
00229 if (m_current == m_window.size())
00230 {
00231 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
00232 m_lastFlush = 0;
00233 m_current = 0;
00234 m_wrappedAround = true;
00235 }
00236 }
00237
00238 void Inflator::OutputString(const byte *string, unsigned int length)
00239 {
00240 while (length)
00241 {
00242 unsigned int len = STDMIN(length, (unsigned int)(m_window.size() - m_current));
00243 memcpy(m_window + m_current, string, len);
00244 m_current += len;
00245 if (m_current == m_window.size())
00246 {
00247 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
00248 m_lastFlush = 0;
00249 m_current = 0;
00250 m_wrappedAround = true;
00251 }
00252 string += len;
00253 length -= len;
00254 }
00255 }
00256
00257 void Inflator::OutputPast(unsigned int length, unsigned int distance)
00258 {
00259 unsigned int start;
00260 if (distance <= m_current)
00261 start = m_current - distance;
00262 else if (m_wrappedAround && distance <= m_window.size())
00263 start = m_current + m_window.size() - distance;
00264 else
00265 throw BadBlockErr();
00266
00267 if (start + length > m_window.size())
00268 {
00269 for (; start < m_window.size(); start++, length--)
00270 OutputByte(m_window[start]);
00271 start = 0;
00272 }
00273
00274 if (start + length > m_current || m_current + length >= m_window.size())
00275 {
00276 while (length--)
00277 OutputByte(m_window[start++]);
00278 }
00279 else
00280 {
00281 memcpy(m_window + m_current, m_window + start, length);
00282 m_current += length;
00283 }
00284 }
00285
00286 unsigned int Inflator::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking)
00287 {
00288 if (!blocking)
00289 throw BlockingInputOnly("Inflator");
00290
00291 LazyPutter lp(m_inQueue, inString, length);
00292 ProcessInput(messageEnd != 0);
00293
00294 if (messageEnd)
00295 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
00296 throw UnexpectedEndErr();
00297
00298 Output(0, NULL, 0, messageEnd, blocking);
00299 return 0;
00300 }
00301
00302 bool Inflator::IsolatedFlush(bool hardFlush, bool blocking)
00303 {
00304 if (!blocking)
00305 throw BlockingInputOnly("Inflator");
00306
00307 if (hardFlush)
00308 ProcessInput(true);
00309 FlushOutput();
00310
00311 return false;
00312 }
00313
00314 void Inflator::ProcessInput(bool flush)
00315 {
00316 while (true)
00317 {
00318 switch (m_state)
00319 {
00320 case PRE_STREAM:
00321 if (!flush && m_inQueue.CurrentSize() < MaxPrestreamHeaderSize())
00322 return;
00323 ProcessPrestreamHeader();
00324 m_state = WAIT_HEADER;
00325 m_wrappedAround = false;
00326 m_current = 0;
00327 m_lastFlush = 0;
00328 m_window.New(1 << GetLog2WindowSize());
00329 break;
00330 case WAIT_HEADER:
00331 {
00332
00333 const unsigned int MAX_HEADER_SIZE = BitsToBytes(3+5+5+4+19*7+286*15+19*15);
00334 if (m_inQueue.CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
00335 return;
00336 DecodeHeader();
00337 break;
00338 }
00339 case DECODING_BODY:
00340 if (!DecodeBody())
00341 return;
00342 break;
00343 case POST_STREAM:
00344 if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
00345 return;
00346 ProcessPoststreamTail();
00347 m_state = m_repeat ? PRE_STREAM : AFTER_END;
00348 Output(0, NULL, 0, GetAutoSignalPropagation(), true);
00349 if (m_inQueue.IsEmpty())
00350 return;
00351 break;
00352 case AFTER_END:
00353 m_inQueue.TransferTo(*AttachedTransformation());
00354 return;
00355 }
00356 }
00357 }
00358
00359 void Inflator::DecodeHeader()
00360 {
00361 if (!m_reader.FillBuffer(3))
00362 throw UnexpectedEndErr();
00363 m_eof = m_reader.GetBits(1) != 0;
00364 m_blockType = (byte)m_reader.GetBits(2);
00365 switch (m_blockType)
00366 {
00367 case 0:
00368 {
00369 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
00370 if (!m_reader.FillBuffer(32))
00371 throw UnexpectedEndErr();
00372 m_storedLen = (word16)m_reader.GetBits(16);
00373 word16 nlen = (word16)m_reader.GetBits(16);
00374 if (nlen != (word16)~m_storedLen)
00375 throw BadBlockErr();
00376 break;
00377 }
00378 case 1:
00379 m_nextDecode = LITERAL;
00380 break;
00381 case 2:
00382 {
00383 if (!m_reader.FillBuffer(5+5+4))
00384 throw UnexpectedEndErr();
00385 unsigned int hlit = m_reader.GetBits(5);
00386 unsigned int hdist = m_reader.GetBits(5);
00387 unsigned int hclen = m_reader.GetBits(4);
00388
00389 FixedSizeSecBlock<unsigned int, 286+32> codeLengths;
00390 unsigned int i;
00391 static const unsigned int border[] = {
00392 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00393 std::fill(codeLengths.begin(), codeLengths+19, 0);
00394 for (i=0; i<hclen+4; i++)
00395 codeLengths[border[i]] = m_reader.GetBits(3);
00396
00397 try
00398 {
00399 HuffmanDecoder codeLengthDecoder(codeLengths, 19);
00400 for (i = 0; i < hlit+257+hdist+1; )
00401 {
00402 unsigned int k, count, repeater;
00403 bool result = codeLengthDecoder.Decode(m_reader, k);
00404 if (!result)
00405 throw UnexpectedEndErr();
00406 if (k <= 15)
00407 {
00408 count = 1;
00409 repeater = k;
00410 }
00411 else switch (k)
00412 {
00413 case 16:
00414 if (!m_reader.FillBuffer(2))
00415 throw UnexpectedEndErr();
00416 count = 3 + m_reader.GetBits(2);
00417 if (i == 0)
00418 throw BadBlockErr();
00419 repeater = codeLengths[i-1];
00420 break;
00421 case 17:
00422 if (!m_reader.FillBuffer(3))
00423 throw UnexpectedEndErr();
00424 count = 3 + m_reader.GetBits(3);
00425 repeater = 0;
00426 break;
00427 case 18:
00428 if (!m_reader.FillBuffer(7))
00429 throw UnexpectedEndErr();
00430 count = 11 + m_reader.GetBits(7);
00431 repeater = 0;
00432 break;
00433 }
00434 if (i + count > hlit+257+hdist+1)
00435 throw BadBlockErr();
00436 std::fill(codeLengths + i, codeLengths + i + count, repeater);
00437 i += count;
00438 }
00439 m_dynamicLiteralDecoder.Initialize(codeLengths, hlit+257);
00440 if (hdist == 0 && codeLengths[hlit+257] == 0)
00441 {
00442 if (hlit != 0)
00443 throw BadBlockErr();
00444 }
00445 else
00446 m_dynamicDistanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
00447 m_nextDecode = LITERAL;
00448 }
00449 catch (HuffmanDecoder::Err &)
00450 {
00451 throw BadBlockErr();
00452 }
00453 break;
00454 }
00455 default:
00456 throw BadBlockErr();
00457 }
00458 m_state = DECODING_BODY;
00459 }
00460
00461 bool Inflator::DecodeBody()
00462 {
00463 bool blockEnd = false;
00464 switch (m_blockType)
00465 {
00466 case 0:
00467 assert(m_reader.BitsBuffered() == 0);
00468 while (!m_inQueue.IsEmpty() && !blockEnd)
00469 {
00470 unsigned int size;
00471 const byte *block = m_inQueue.Spy(size);
00472 size = STDMIN(size, (unsigned int)m_storedLen);
00473 OutputString(block, size);
00474 m_inQueue.Skip(size);
00475 m_storedLen -= size;
00476 if (m_storedLen == 0)
00477 blockEnd = true;
00478 }
00479 break;
00480 case 1:
00481 case 2:
00482 static const unsigned int lengthStarts[] = {
00483 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00484 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
00485 static const unsigned int lengthExtraBits[] = {
00486 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00487 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
00488 static const unsigned int distanceStarts[] = {
00489 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00490 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00491 8193, 12289, 16385, 24577};
00492 static const unsigned int distanceExtraBits[] = {
00493 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00494 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00495 12, 12, 13, 13};
00496
00497 const HuffmanDecoder& literalDecoder = GetLiteralDecoder();
00498 const HuffmanDecoder& distanceDecoder = GetDistanceDecoder();
00499
00500 switch (m_nextDecode)
00501 {
00502 case LITERAL:
00503 while (true)
00504 {
00505 if (!literalDecoder.Decode(m_reader, m_literal))
00506 {
00507 m_nextDecode = LITERAL;
00508 break;
00509 }
00510 if (m_literal < 256)
00511 OutputByte((byte)m_literal);
00512 else if (m_literal == 256)
00513 {
00514 blockEnd = true;
00515 break;
00516 }
00517 else
00518 {
00519 if (m_literal > 285)
00520 throw BadBlockErr();
00521 unsigned int bits;
00522 case LENGTH_BITS:
00523 bits = lengthExtraBits[m_literal-257];
00524 if (!m_reader.FillBuffer(bits))
00525 {
00526 m_nextDecode = LENGTH_BITS;
00527 break;
00528 }
00529 m_literal = m_reader.GetBits(bits) + lengthStarts[m_literal-257];
00530 case DISTANCE:
00531 if (!distanceDecoder.Decode(m_reader, m_distance))
00532 {
00533 m_nextDecode = DISTANCE;
00534 break;
00535 }
00536 case DISTANCE_BITS:
00537 bits = distanceExtraBits[m_distance];
00538 if (!m_reader.FillBuffer(bits))
00539 {
00540 m_nextDecode = DISTANCE_BITS;
00541 break;
00542 }
00543 m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
00544 OutputPast(m_literal, m_distance);
00545 }
00546 }
00547 }
00548 }
00549 if (blockEnd)
00550 {
00551 if (m_eof)
00552 {
00553 FlushOutput();
00554 m_reader.SkipBits(m_reader.BitsBuffered()%8);
00555 if (m_reader.BitsBuffered())
00556 {
00557
00558 SecBlockWithHint<byte, 4> buffer(m_reader.BitsBuffered() / 8);
00559 for (unsigned int i=0; i<buffer.size(); i++)
00560 buffer[i] = (byte)m_reader.GetBits(8);
00561 m_inQueue.Unget(buffer, buffer.size());
00562 }
00563 m_state = POST_STREAM;
00564 }
00565 else
00566 m_state = WAIT_HEADER;
00567 }
00568 return blockEnd;
00569 }
00570
00571 void Inflator::FlushOutput()
00572 {
00573 if (m_state != PRE_STREAM)
00574 {
00575 assert(m_current >= m_lastFlush);
00576 ProcessDecompressedData(m_window + m_lastFlush, m_current - m_lastFlush);
00577 m_lastFlush = m_current;
00578 }
00579 }
00580
00581 struct NewFixedLiteralDecoder
00582 {
00583 HuffmanDecoder * operator()() const
00584 {
00585 unsigned int codeLengths[288];
00586 std::fill(codeLengths + 0, codeLengths + 144, 8);
00587 std::fill(codeLengths + 144, codeLengths + 256, 9);
00588 std::fill(codeLengths + 256, codeLengths + 280, 7);
00589 std::fill(codeLengths + 280, codeLengths + 288, 8);
00590 std::auto_ptr<HuffmanDecoder> pDecoder(new HuffmanDecoder);
00591 pDecoder->Initialize(codeLengths, 288);
00592 return pDecoder.release();
00593 }
00594 };
00595
00596 struct NewFixedDistanceDecoder
00597 {
00598 HuffmanDecoder * operator()() const
00599 {
00600 unsigned int codeLengths[32];
00601 std::fill(codeLengths + 0, codeLengths + 32, 5);
00602 std::auto_ptr<HuffmanDecoder> pDecoder(new HuffmanDecoder);
00603 pDecoder->Initialize(codeLengths, 32);
00604 return pDecoder.release();
00605 }
00606 };
00607
00608 const HuffmanDecoder& Inflator::GetLiteralDecoder() const
00609 {
00610 return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedLiteralDecoder>().Ref() : m_dynamicLiteralDecoder;
00611 }
00612
00613 const HuffmanDecoder& Inflator::GetDistanceDecoder() const
00614 {
00615 return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedDistanceDecoder>().Ref() : m_dynamicDistanceDecoder;
00616 }
00617
00618 NAMESPACE_END