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>(attachment, propagation)
00213 , m_state(PRE_STREAM), m_repeat(repeat)
00214 , m_decodersInitializedWithFixedCodes(false), m_reader(m_inQueue)
00215 {
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 inline 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 }
00235 if (m_maxDistance < m_window.size())
00236 m_maxDistance++;
00237 }
00238
00239 void Inflator::OutputString(const byte *string, unsigned int length)
00240 {
00241 while (length--)
00242 OutputByte(*string++);
00243 }
00244
00245 void Inflator::OutputPast(unsigned int length, unsigned int distance)
00246 {
00247 if (distance > m_maxDistance)
00248 throw BadBlockErr();
00249 unsigned int start;
00250 if (m_current > distance)
00251 start = m_current - distance;
00252 else
00253 start = m_current + m_window.size() - distance;
00254
00255 if (start + length > m_window.size())
00256 {
00257 for (; start < m_window.size(); start++, length--)
00258 OutputByte(m_window[start]);
00259 start = 0;
00260 }
00261
00262 if (start + length > m_current || m_current + length >= m_window.size())
00263 {
00264 while (length--)
00265 OutputByte(m_window[start++]);
00266 }
00267 else
00268 {
00269 memcpy(m_window + m_current, m_window + start, length);
00270 m_current += length;
00271 m_maxDistance = STDMIN((unsigned int)m_window.size(), m_maxDistance + length);
00272 }
00273 }
00274
00275 unsigned int Inflator::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking)
00276 {
00277 if (!blocking)
00278 throw BlockingInputOnly("Inflator");
00279
00280 LazyPutter lp(m_inQueue, inString, length);
00281 ProcessInput(messageEnd != 0);
00282
00283 if (messageEnd)
00284 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
00285 throw UnexpectedEndErr();
00286
00287 Output(0, NULL, 0, messageEnd, blocking);
00288 return 0;
00289 }
00290
00291 bool Inflator::IsolatedFlush(bool hardFlush, bool blocking)
00292 {
00293 if (!blocking)
00294 throw BlockingInputOnly("Inflator");
00295
00296 if (hardFlush)
00297 ProcessInput(true);
00298 FlushOutput();
00299
00300 return false;
00301 }
00302
00303 void Inflator::ProcessInput(bool flush)
00304 {
00305 while (true)
00306 {
00307 if (m_inQueue.IsEmpty())
00308 return;
00309
00310 switch (m_state)
00311 {
00312 case PRE_STREAM:
00313 if (!flush && m_inQueue.CurrentSize() < MaxPrestreamHeaderSize())
00314 return;
00315 ProcessPrestreamHeader();
00316 m_state = WAIT_HEADER;
00317 m_maxDistance = 0;
00318 m_current = 0;
00319 m_lastFlush = 0;
00320 m_window.New(1 << GetLog2WindowSize());
00321 break;
00322 case WAIT_HEADER:
00323 {
00324
00325 const unsigned int MAX_HEADER_SIZE = BitsToBytes(3+5+5+4+19*7+286*15+19*15);
00326 if (m_inQueue.CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
00327 return;
00328 DecodeHeader();
00329 break;
00330 }
00331 case DECODING_BODY:
00332 if (!DecodeBody())
00333 return;
00334 break;
00335 case POST_STREAM:
00336 if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
00337 return;
00338 ProcessPoststreamTail();
00339 m_state = m_repeat ? PRE_STREAM : AFTER_END;
00340 Output(0, NULL, 0, GetAutoSignalPropagation(), true);
00341 break;
00342 case AFTER_END:
00343 m_inQueue.TransferTo(*AttachedTransformation());
00344 return;
00345 }
00346 }
00347 }
00348
00349 void Inflator::DecodeHeader()
00350 {
00351 if (!m_reader.FillBuffer(3))
00352 throw UnexpectedEndErr();
00353 m_eof = m_reader.GetBits(1) != 0;
00354 m_blockType = (byte)m_reader.GetBits(2);
00355 switch (m_blockType)
00356 {
00357 case 0:
00358 {
00359 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
00360 if (!m_reader.FillBuffer(32))
00361 throw UnexpectedEndErr();
00362 m_storedLen = (word16)m_reader.GetBits(16);
00363 word16 nlen = (word16)m_reader.GetBits(16);
00364 if (nlen != (word16)~m_storedLen)
00365 throw BadBlockErr();
00366 break;
00367 }
00368 case 1:
00369 if (!m_decodersInitializedWithFixedCodes)
00370 {
00371 unsigned int codeLengths[288];
00372 std::fill(codeLengths + 0, codeLengths + 144, 8);
00373 std::fill(codeLengths + 144, codeLengths + 256, 9);
00374 std::fill(codeLengths + 256, codeLengths + 280, 7);
00375 std::fill(codeLengths + 280, codeLengths + 288, 8);
00376 m_literalDecoder.Initialize(codeLengths, 288);
00377 std::fill(codeLengths + 0, codeLengths + 32, 5);
00378 m_distanceDecoder.Initialize(codeLengths, 32);
00379 m_decodersInitializedWithFixedCodes = true;
00380 }
00381 m_nextDecode = LITERAL;
00382 break;
00383 case 2:
00384 {
00385 m_decodersInitializedWithFixedCodes = false;
00386 if (!m_reader.FillBuffer(5+5+4))
00387 throw UnexpectedEndErr();
00388 unsigned int hlit = m_reader.GetBits(5);
00389 unsigned int hdist = m_reader.GetBits(5);
00390 unsigned int hclen = m_reader.GetBits(4);
00391
00392 FixedSizeSecBlock<unsigned int, 286+32> codeLengths;
00393 unsigned int i;
00394 static const unsigned int border[] = {
00395 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00396 std::fill(codeLengths.begin(), codeLengths+19, 0);
00397 for (i=0; i<hclen+4; i++)
00398 codeLengths[border[i]] = m_reader.GetBits(3);
00399
00400 try
00401 {
00402 HuffmanDecoder codeLengthDecoder(codeLengths, 19);
00403 for (i = 0; i < hlit+257+hdist+1; )
00404 {
00405 unsigned int k, count, repeater;
00406 bool result = codeLengthDecoder.Decode(m_reader, k);
00407 if (!result)
00408 throw UnexpectedEndErr();
00409 if (k <= 15)
00410 {
00411 count = 1;
00412 repeater = k;
00413 }
00414 else switch (k)
00415 {
00416 case 16:
00417 if (!m_reader.FillBuffer(2))
00418 throw UnexpectedEndErr();
00419 count = 3 + m_reader.GetBits(2);
00420 if (i == 0)
00421 throw BadBlockErr();
00422 repeater = codeLengths[i-1];
00423 break;
00424 case 17:
00425 if (!m_reader.FillBuffer(3))
00426 throw UnexpectedEndErr();
00427 count = 3 + m_reader.GetBits(3);
00428 repeater = 0;
00429 break;
00430 case 18:
00431 if (!m_reader.FillBuffer(7))
00432 throw UnexpectedEndErr();
00433 count = 11 + m_reader.GetBits(7);
00434 repeater = 0;
00435 break;
00436 }
00437 if (i + count > hlit+257+hdist+1)
00438 throw BadBlockErr();
00439 std::fill(codeLengths + i, codeLengths + i + count, repeater);
00440 i += count;
00441 }
00442 m_literalDecoder.Initialize(codeLengths, hlit+257);
00443 if (hdist == 0 && codeLengths[hlit+257] == 0)
00444 {
00445 if (hlit != 0)
00446 throw BadBlockErr();
00447 }
00448 else
00449 m_distanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
00450 m_nextDecode = LITERAL;
00451 }
00452 catch (HuffmanDecoder::Err &)
00453 {
00454 throw BadBlockErr();
00455 }
00456 break;
00457 }
00458 default:
00459 throw BadBlockErr();
00460 }
00461 m_state = DECODING_BODY;
00462 }
00463
00464 bool Inflator::DecodeBody()
00465 {
00466 bool blockEnd = false;
00467 switch (m_blockType)
00468 {
00469 case 0:
00470 assert(m_reader.BitsBuffered() == 0);
00471 while (!m_inQueue.IsEmpty() && !blockEnd)
00472 {
00473 unsigned int size;
00474 const byte *block = m_inQueue.Spy(size);
00475 size = STDMIN(size, (unsigned int)m_storedLen);
00476 OutputString(block, size);
00477 m_inQueue.Skip(size);
00478 m_storedLen -= size;
00479 if (m_storedLen == 0)
00480 blockEnd = true;
00481 }
00482 break;
00483 case 1:
00484 case 2:
00485 static const unsigned int lengthStarts[] = {
00486 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00487 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
00488 static const unsigned int lengthExtraBits[] = {
00489 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00490 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
00491 static const unsigned int distanceStarts[] = {
00492 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00493 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00494 8193, 12289, 16385, 24577};
00495 static const unsigned int distanceExtraBits[] = {
00496 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00497 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00498 12, 12, 13, 13};
00499
00500 switch (m_nextDecode)
00501 {
00502 while (true)
00503 {
00504 case LITERAL:
00505 if (!m_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 (!m_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 NAMESPACE_END