You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
611 lines
14 KiB
611 lines
14 KiB
//
|
|
// infstatic.c
|
|
//
|
|
// Decompress a static (fixed) compressed block
|
|
//
|
|
// This code was cloned from infdyna.c with the following changes:
|
|
// 1. Use global pre-initialised static tables
|
|
// 2. All distance prefixes are 5 bits, so don't look this up in a table
|
|
// 3. g_StaticDistanceTreeTable is a BYTE[] not a USHORT[]
|
|
// 4. Table lookup size for literals is 9 bits, for distances it is 5 bits
|
|
// 5. Due to #3 there is no table overflow, so there are no left/right arrays
|
|
// 6. When dumping 5 distance bits, no need to check for bitcount overflow twice
|
|
//
|
|
#include <stdio.h>
|
|
#include <crtdbg.h>
|
|
#include "inflate.h"
|
|
#include "infmacro.h"
|
|
#include "maketbl.h"
|
|
|
|
|
|
//
|
|
// Decoding table sizes; do not change!
|
|
//
|
|
// 9 is the largest code length for literals
|
|
// 5 is the largest code length for distances
|
|
//
|
|
// Therefore we don't need an overflow left/right table
|
|
//
|
|
#define STATIC_BLOCK_LITERAL_TABLE_BITS 9
|
|
#define STATIC_BLOCK_LITERAL_TABLE_MASK ((1 << STATIC_BLOCK_LITERAL_TABLE_BITS)-1)
|
|
|
|
#define STATIC_BLOCK_DISTANCE_TABLE_BITS 5
|
|
#define STATIC_BLOCK_DISTANCE_TABLE_MASK ((1 << STATIC_BLOCK_DISTANCE_TABLE_BITS)-1)
|
|
|
|
|
|
#define OUTPUT_EOF() (output_curpos >= context->end_output_buffer)
|
|
|
|
//
|
|
// This is the slow version, which worries about the input running out or the output
|
|
// running out. The trick here is to not read any more bytes than we need to; theoretically
|
|
// the "end of block" code could be 1 bit, so we cannot always assume that it is ok to fill
|
|
// the bit buffer with 16 bits right before a table decode.
|
|
//
|
|
BOOL DecodeStaticBlock(t_decoder_context *context, BOOL *end_of_block_code_seen)
|
|
{
|
|
const byte * input_ptr;
|
|
const byte * end_input_buffer;
|
|
byte * output_curpos;
|
|
byte * window;
|
|
unsigned long bufpos;
|
|
unsigned long bitbuf;
|
|
int bitcount;
|
|
int length;
|
|
long dist_code;
|
|
unsigned long offset;
|
|
|
|
*end_of_block_code_seen = FALSE;
|
|
|
|
//
|
|
// Store these variables locally for speed
|
|
//
|
|
top:
|
|
output_curpos = context->output_curpos;
|
|
|
|
window = context->window;
|
|
bufpos = context->bufpos;
|
|
|
|
end_input_buffer = context->end_input_buffer;
|
|
|
|
LOAD_BITBUF_VARS();
|
|
|
|
_ASSERT(bitcount >= -16);
|
|
|
|
//
|
|
// Set the state to DECODE_TOP here
|
|
//
|
|
switch (context->state)
|
|
{
|
|
case STATE_DECODE_TOP:
|
|
break;
|
|
|
|
case STATE_HAVE_INITIAL_LENGTH:
|
|
context->state = STATE_DECODE_TOP;
|
|
length = context->length;
|
|
goto reenter_state_have_initial_length;
|
|
|
|
case STATE_HAVE_FULL_LENGTH:
|
|
context->state = STATE_DECODE_TOP;
|
|
length = context->length;
|
|
goto reenter_state_have_full_length;
|
|
|
|
case STATE_HAVE_DIST_CODE:
|
|
context->state = STATE_DECODE_TOP;
|
|
length = context->length;
|
|
dist_code = context->dist_code;
|
|
goto reenter_state_have_dist_code;
|
|
|
|
case STATE_INTERRUPTED_MATCH:
|
|
context->state = STATE_DECODE_TOP;
|
|
length = context->length;
|
|
offset = context->offset;
|
|
goto reenter_state_interrupted_match;
|
|
}
|
|
|
|
do
|
|
{
|
|
if (context->output_curpos + MAX_MATCH < context->end_output_buffer &&
|
|
context->input_curpos + 12 < context->end_input_buffer)
|
|
{
|
|
SAVE_BITBUF_VARS();
|
|
context->output_curpos = output_curpos;
|
|
context->bufpos = bufpos;
|
|
|
|
if (FastDecodeStaticBlock(context, end_of_block_code_seen) == FALSE)
|
|
return FALSE;
|
|
|
|
if (*end_of_block_code_seen)
|
|
return TRUE;
|
|
|
|
goto top;
|
|
}
|
|
|
|
//
|
|
// decode an element from the main tree
|
|
//
|
|
|
|
// we must have at least 1 bit available
|
|
_ASSERT(bitcount >= -16);
|
|
|
|
if (bitcount == -16)
|
|
{
|
|
if (input_ptr >= end_input_buffer)
|
|
break;
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
|
|
retry_decode_literal:
|
|
|
|
// assert that at least 1 bit is present
|
|
_ASSERT(bitcount > -16);
|
|
|
|
// decode an element from the literal tree
|
|
length = g_StaticLiteralTreeTable[bitbuf & STATIC_BLOCK_LITERAL_TABLE_MASK];
|
|
|
|
//
|
|
// If this code is longer than the # bits we had in the bit buffer (i.e.
|
|
// we read only part of the code - but enough to know that it's too long),
|
|
// read more bits and retry
|
|
//
|
|
if (g_StaticLiteralTreeLength[length] > (bitcount+16))
|
|
{
|
|
// if we run out of bits, break
|
|
if (input_ptr >= end_input_buffer)
|
|
break;
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
goto retry_decode_literal;
|
|
}
|
|
|
|
DUMPBITS(g_StaticLiteralTreeLength[length]);
|
|
_ASSERT(bitcount >= -16);
|
|
|
|
//
|
|
// Is it a character or a match?
|
|
//
|
|
if (length < 256)
|
|
{
|
|
// it's an unmatched symbol
|
|
window[bufpos] = *output_curpos++ = (byte) length;
|
|
bufpos = (bufpos + 1) & WINDOW_MASK;
|
|
}
|
|
else
|
|
{
|
|
// it's a match
|
|
int extra_bits;
|
|
|
|
length -= 257;
|
|
|
|
// if value was 256, that was the end-of-block code
|
|
if (length < 0)
|
|
{
|
|
*end_of_block_code_seen = TRUE;
|
|
break;
|
|
}
|
|
|
|
|
|
//
|
|
// Get match length
|
|
//
|
|
|
|
//
|
|
// These matches are by far the most common case.
|
|
//
|
|
if (length < 8)
|
|
{
|
|
// no extra bits
|
|
|
|
// match length = 3,4,5,6,7,8,9,10
|
|
length += 3;
|
|
}
|
|
else
|
|
{
|
|
int extra_bits;
|
|
|
|
reenter_state_have_initial_length:
|
|
|
|
extra_bits = g_ExtraLengthBits[length];
|
|
|
|
if (extra_bits > 0)
|
|
{
|
|
// make sure we have this many bits in the bit buffer
|
|
if (extra_bits > bitcount + 16)
|
|
{
|
|
// if we run out of bits, break
|
|
if (input_ptr >= end_input_buffer)
|
|
{
|
|
context->state = STATE_HAVE_INITIAL_LENGTH;
|
|
context->length = length;
|
|
break;
|
|
}
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
// extra_length_bits will be no more than 5, so we need to read at
|
|
// most one byte of input to satisfy this request
|
|
}
|
|
|
|
length = g_LengthBase[length] + (bitbuf & g_BitMask[extra_bits]);
|
|
|
|
DUMPBITS(extra_bits);
|
|
_ASSERT(bitcount >= -16);
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* we know length > 8 and extra_bits == 0, there the length must be 258
|
|
*/
|
|
length = 258; /* g_LengthBase[length]; */
|
|
}
|
|
}
|
|
|
|
//
|
|
// Get match distance
|
|
//
|
|
|
|
// decode distance code
|
|
reenter_state_have_full_length:
|
|
|
|
// we must have at least 1 bit available
|
|
if (bitcount == -16)
|
|
{
|
|
if (input_ptr >= end_input_buffer)
|
|
{
|
|
context->state = STATE_HAVE_FULL_LENGTH;
|
|
context->length = length;
|
|
break;
|
|
}
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
|
|
|
|
retry_decode_distance:
|
|
|
|
// assert that at least 1 bit is present
|
|
_ASSERT(bitcount > -16);
|
|
|
|
dist_code = g_StaticDistanceTreeTable[bitbuf & STATIC_BLOCK_DISTANCE_TABLE_MASK];
|
|
|
|
//
|
|
// If this code is longer than the # bits we had in the bit buffer (i.e.
|
|
// we read only part of the code - but enough to know that it's too long),
|
|
// read more bits and retry
|
|
//
|
|
// g_StaticTreeDistanceLength[dist_code] == 5
|
|
//
|
|
if (5 > (bitcount+16))
|
|
{
|
|
// if we run out of bits, break
|
|
if (input_ptr >= end_input_buffer)
|
|
{
|
|
context->state = STATE_HAVE_FULL_LENGTH;
|
|
context->length = length;
|
|
break;
|
|
}
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
_ASSERT(bitcount >= -16);
|
|
goto retry_decode_distance;
|
|
}
|
|
|
|
|
|
DUMPBITS(5);
|
|
|
|
// To avoid a table lookup we note that for dist_code >= 2,
|
|
// extra_bits = (dist_code-2) >> 1
|
|
//
|
|
// Old (intuitive) way of doing this:
|
|
// offset = distance_base_position[dist_code] +
|
|
// getBits(extra_distance_bits[dist_code]);
|
|
|
|
reenter_state_have_dist_code:
|
|
|
|
_ASSERT(bitcount >= -16);
|
|
|
|
extra_bits = (dist_code-2) >> 1;
|
|
|
|
if (extra_bits > 0)
|
|
{
|
|
// make sure we have this many bits in the bit buffer
|
|
if (extra_bits > bitcount + 16)
|
|
{
|
|
// if we run out of bits, break
|
|
if (input_ptr >= end_input_buffer)
|
|
{
|
|
context->state = STATE_HAVE_DIST_CODE;
|
|
context->length = length;
|
|
context->dist_code = dist_code;
|
|
break;
|
|
}
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
// extra_length_bits can be > 8, so check again
|
|
if (extra_bits > bitcount + 16)
|
|
{
|
|
// if we run out of bits, break
|
|
if (input_ptr >= end_input_buffer)
|
|
{
|
|
context->state = STATE_HAVE_DIST_CODE;
|
|
context->length = length;
|
|
context->dist_code = dist_code;
|
|
break;
|
|
}
|
|
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
}
|
|
|
|
offset = g_DistanceBasePosition[dist_code] + (bitbuf & g_BitMask[extra_bits]);
|
|
|
|
DUMPBITS(extra_bits);
|
|
_ASSERT(bitcount >= -16);
|
|
}
|
|
else
|
|
{
|
|
offset = dist_code + 1;
|
|
}
|
|
|
|
// copy remaining byte(s) of match
|
|
reenter_state_interrupted_match:
|
|
|
|
do
|
|
{
|
|
window[bufpos] = *output_curpos++ = window[(bufpos - offset) & WINDOW_MASK];
|
|
bufpos = (bufpos + 1) & WINDOW_MASK;
|
|
|
|
if (--length == 0)
|
|
break;
|
|
|
|
} while (output_curpos < context->end_output_buffer);
|
|
|
|
if (length > 0)
|
|
{
|
|
context->state = STATE_INTERRUPTED_MATCH;
|
|
context->length = length;
|
|
context->offset = offset;
|
|
break;
|
|
}
|
|
}
|
|
|
|
// it's "<=" because we end when we received the end-of-block code,
|
|
// not when we fill up the output, however, this will catch cases
|
|
// of corrupted data where there is no end-of-output code
|
|
} while (output_curpos < context->end_output_buffer);
|
|
|
|
_ASSERT(bitcount >= -16);
|
|
|
|
SAVE_BITBUF_VARS();
|
|
|
|
context->output_curpos = output_curpos;
|
|
context->bufpos = bufpos;
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
//
|
|
// This is the fast version, which assumes that, at the top of the loop:
|
|
//
|
|
// 1. There are at least 12 bytes of input available at the top of the loop (so that we don't
|
|
// have to check input EOF several times in the middle of the loop)
|
|
//
|
|
// and
|
|
//
|
|
// 2. There are at least MAX_MATCH bytes of output available (so that we don't have to check
|
|
// for output EOF while we're copying matches)
|
|
//
|
|
// The state must also be STATE_DECODE_TOP on entering and exiting this function
|
|
//
|
|
BOOL FastDecodeStaticBlock(t_decoder_context *context, BOOL *end_of_block_code_seen)
|
|
{
|
|
const byte * input_ptr;
|
|
const byte * end_input_buffer;
|
|
byte * output_curpos;
|
|
byte * window;
|
|
unsigned long bufpos;
|
|
unsigned long bitbuf;
|
|
int bitcount;
|
|
int length;
|
|
long dist_code;
|
|
unsigned long offset;
|
|
|
|
*end_of_block_code_seen = FALSE;
|
|
|
|
//
|
|
// Store these variables locally for speed
|
|
//
|
|
output_curpos = context->output_curpos;
|
|
|
|
window = context->window;
|
|
bufpos = context->bufpos;
|
|
|
|
end_input_buffer = context->end_input_buffer;
|
|
|
|
LOAD_BITBUF_VARS();
|
|
|
|
_ASSERT(context->state == STATE_DECODE_TOP);
|
|
_ASSERT(input_ptr + 12 < end_input_buffer);
|
|
_ASSERT(output_curpos + MAX_MATCH < context->end_output_buffer);
|
|
|
|
// make sure there are at least 16 bits in the bit buffer
|
|
while (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
|
|
do
|
|
{
|
|
//
|
|
// decode an element from the main tree
|
|
//
|
|
|
|
// decode an element from the literal tree
|
|
length = g_StaticLiteralTreeTable[bitbuf & STATIC_BLOCK_LITERAL_TABLE_MASK];
|
|
|
|
DUMPBITS(g_StaticLiteralTreeLength[length]);
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
}
|
|
|
|
//
|
|
// Is it a character or a match?
|
|
//
|
|
if (length < 256)
|
|
{
|
|
// it's an unmatched symbol
|
|
window[bufpos] = *output_curpos++ = (byte) length;
|
|
bufpos = (bufpos + 1) & WINDOW_MASK;
|
|
}
|
|
else
|
|
{
|
|
// it's a match
|
|
int extra_bits;
|
|
|
|
length -= 257;
|
|
|
|
// if value was 256, that was the end-of-block code
|
|
if (length < 0)
|
|
{
|
|
*end_of_block_code_seen = TRUE;
|
|
break;
|
|
}
|
|
|
|
|
|
//
|
|
// Get match length
|
|
//
|
|
|
|
//
|
|
// These matches are by far the most common case.
|
|
//
|
|
if (length < 8)
|
|
{
|
|
// no extra bits
|
|
|
|
// match length = 3,4,5,6,7,8,9,10
|
|
length += 3;
|
|
}
|
|
else
|
|
{
|
|
int extra_bits;
|
|
|
|
extra_bits = g_ExtraLengthBits[length];
|
|
|
|
if (extra_bits > 0)
|
|
{
|
|
length = g_LengthBase[length] + (bitbuf & g_BitMask[extra_bits]);
|
|
|
|
DUMPBITS(extra_bits);
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* we know length > 8 and extra_bits == 0, there the length must be 258
|
|
*/
|
|
length = 258; /* g_LengthBase[length]; */
|
|
}
|
|
}
|
|
|
|
//
|
|
// Get match distance
|
|
//
|
|
|
|
// decode distance code
|
|
dist_code = g_StaticDistanceTreeTable[bitbuf & STATIC_BLOCK_DISTANCE_TABLE_MASK];
|
|
DUMPBITS(5);
|
|
|
|
// unlike dynamic block, don't need to do this twice
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
|
|
|
|
// To avoid a table lookup we note that for dist_code >= 2,
|
|
// extra_bits = (dist_code-2) >> 1
|
|
//
|
|
// Old (intuitive) way of doing this:
|
|
// offset = distance_base_position[dist_code] +
|
|
// getBits(extra_distance_bits[dist_code]);
|
|
extra_bits = (dist_code-2) >> 1;
|
|
|
|
if (extra_bits > 0)
|
|
{
|
|
offset = g_DistanceBasePosition[dist_code] + (bitbuf & g_BitMask[extra_bits]);
|
|
|
|
DUMPBITS(extra_bits);
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
|
|
if (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
offset = dist_code + 1;
|
|
}
|
|
|
|
// copy remaining byte(s) of match
|
|
do
|
|
{
|
|
window[bufpos] = *output_curpos++ = window[(bufpos - offset) & WINDOW_MASK];
|
|
bufpos = (bufpos + 1) & WINDOW_MASK;
|
|
} while (--length != 0);
|
|
}
|
|
} while ((input_ptr + 12 < end_input_buffer) && (output_curpos + MAX_MATCH < context->end_output_buffer));
|
|
|
|
// make sure there are at least 16 bits in the bit buffer
|
|
while (bitcount <= 0)
|
|
{
|
|
bitbuf |= ((*input_ptr++) << (bitcount+16));
|
|
bitcount += 8;
|
|
}
|
|
|
|
SAVE_BITBUF_VARS();
|
|
|
|
context->output_curpos = output_curpos;
|
|
context->bufpos = bufpos;
|
|
|
|
return TRUE;
|
|
}
|