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