252 lines
8 KiB
C
252 lines
8 KiB
C
|
/*
|
||
|
|
* dectree.c
|
||
|
|
*
|
||
|
|
* Decoding the encoded tree structures
|
||
|
|
*
|
||
|
|
* To save much code size, the fillbuf()/getbits() calls have
|
||
|
|
* been made into functions, rather than being inlined macros.
|
||
|
|
* The macros actually take up a lot of space. There is no
|
||
|
|
* performance loss from doing so here.
|
||
|
|
*/
|
||
|
|
#include "decoder.h"
|
||
|
|
|
||
|
|
/* number of elements in pre-tree */
|
||
|
|
#define NUM_DECODE_SMALL 20
|
||
|
|
|
||
|
|
/* lookup table size */
|
||
|
|
#define DS_TABLE_BITS 8
|
||
|
|
|
||
|
|
/* macro to decode a pre-tree element */
|
||
|
|
#define DECODE_SMALL(item) \
|
||
|
|
{ \
|
||
|
|
item = small_table[context->dec_bitbuf >> (32-DS_TABLE_BITS) ]; \
|
||
|
|
if (item < 0) \
|
||
|
|
{ \
|
||
|
|
mask = (1L << (32-1-DS_TABLE_BITS)); \
|
||
|
|
do \
|
||
|
|
{ \
|
||
|
|
item = -item; \
|
||
|
|
if (context->dec_bitbuf & mask) \
|
||
|
|
item = leftright_s[2*item+1]; \
|
||
|
|
else \
|
||
|
|
item = leftright_s[2*item]; \
|
||
|
|
mask >>= 1; \
|
||
|
|
} while (item < 0); \
|
||
|
|
} \
|
||
|
|
fillbuf(context, small_bitlen[item]); \
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Reads a compressed tree structure
|
||
|
|
*/
|
||
|
|
static bool NEAR ReadRepTree(
|
||
|
|
t_decoder_context *context,
|
||
|
|
int num_elements,
|
||
|
|
byte *lastlen,
|
||
|
|
byte *len
|
||
|
|
)
|
||
|
|
{
|
||
|
|
ulong mask;
|
||
|
|
int i;
|
||
|
|
int consecutive;
|
||
|
|
byte small_bitlen[24];
|
||
|
|
short small_table[1 << DS_TABLE_BITS];
|
||
|
|
short leftright_s [2*(2 * 24 - 1)];
|
||
|
|
short Temp;
|
||
|
|
|
||
|
|
/* Declare this inline to help compilers see the optimisation */
|
||
|
|
static const byte Modulo17Lookup[] =
|
||
|
|
{
|
||
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
|
||
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
|
||
|
|
};
|
||
|
|
|
||
|
|
/* read pre-tree */
|
||
|
|
for (i = 0; i < NUM_DECODE_SMALL; i++)
|
||
|
|
{
|
||
|
|
small_bitlen[i] = (byte) getbits(context, 4);
|
||
|
|
}
|
||
|
|
|
||
|
|
/* exceeded input buffer? */
|
||
|
|
if (context->dec_error_condition)
|
||
|
|
return false;
|
||
|
|
|
||
|
|
/* make a table for this pre-tree */
|
||
|
|
make_table(
|
||
|
|
context,
|
||
|
|
NUM_DECODE_SMALL,
|
||
|
|
small_bitlen,
|
||
|
|
DS_TABLE_BITS,
|
||
|
|
small_table,
|
||
|
|
leftright_s
|
||
|
|
);
|
||
|
|
|
||
|
|
for (i = 0; i < num_elements; i++)
|
||
|
|
{
|
||
|
|
DECODE_SMALL(Temp);
|
||
|
|
|
||
|
|
/* exceeded input buffer? */
|
||
|
|
if (context->dec_error_condition)
|
||
|
|
return false;
|
||
|
|
|
||
|
|
/* Repeat "TREE_ENC_REP_MIN...TREE_ENC_REP_MIN+(1<<TREE_ENC_REPZ_FIRST_EXTRA_BITS)-1" zeroes */
|
||
|
|
if (Temp == 17)
|
||
|
|
{
|
||
|
|
/* code 17 means "a small number of repeated zeroes" */
|
||
|
|
consecutive = (byte) getbits(context, TREE_ENC_REPZ_FIRST_EXTRA_BITS);
|
||
|
|
consecutive += TREE_ENC_REP_MIN;
|
||
|
|
|
||
|
|
/* boundary check */
|
||
|
|
if (i + consecutive >= num_elements)
|
||
|
|
consecutive = num_elements-i;
|
||
|
|
|
||
|
|
while (consecutive-- > 0)
|
||
|
|
len[i++] = 0;
|
||
|
|
|
||
|
|
i--;
|
||
|
|
}
|
||
|
|
else if (Temp == 18)
|
||
|
|
{
|
||
|
|
/* code 18 means "a large number of repeated zeroes" */
|
||
|
|
|
||
|
|
/* Repeat "TREE_ENC_REP_MIN+(1<<TREE_ENC_REPZ_FIRST_EXTRA_BITS)-1...<ditto>+(1<<TREE_ENC_REPZ_SECOND_EXTRA_BITS)-1" zeroes */
|
||
|
|
consecutive = (byte) getbits(context, TREE_ENC_REPZ_SECOND_EXTRA_BITS);
|
||
|
|
consecutive += (TREE_ENC_REP_MIN+TREE_ENC_REP_ZERO_FIRST);
|
||
|
|
|
||
|
|
/* boundary check */
|
||
|
|
if (i + consecutive >= num_elements)
|
||
|
|
consecutive = num_elements-i;
|
||
|
|
|
||
|
|
while (consecutive-- > 0)
|
||
|
|
len[i++] = 0;
|
||
|
|
|
||
|
|
i--;
|
||
|
|
}
|
||
|
|
else if (Temp == 19)
|
||
|
|
{
|
||
|
|
byte value;
|
||
|
|
|
||
|
|
/* code 19 means "a small number of repeated somethings" */
|
||
|
|
/* Repeat "TREE_ENC_REP_MIN...TREE_ENC_REP_MIN+(1<<TREE_ENC_REP_SAME_EXTRA_BITS)-1" elements */
|
||
|
|
consecutive = (byte) getbits(context, TREE_ENC_REP_SAME_EXTRA_BITS);
|
||
|
|
consecutive += TREE_ENC_REP_MIN;
|
||
|
|
|
||
|
|
/* boundary check */
|
||
|
|
if (i + consecutive >= num_elements)
|
||
|
|
consecutive = num_elements-i;
|
||
|
|
|
||
|
|
/* get the element number to repeat */
|
||
|
|
DECODE_SMALL(Temp);
|
||
|
|
value = Modulo17Lookup[(lastlen[i] - Temp)+17];
|
||
|
|
|
||
|
|
while (consecutive-- > 0)
|
||
|
|
len[i++] = value;
|
||
|
|
|
||
|
|
i--;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
len[i] = Modulo17Lookup[(lastlen[i] - Temp)+17];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* exceeded input buffer? */
|
||
|
|
if (context->dec_error_condition)
|
||
|
|
return false;
|
||
|
|
else
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
bool NEAR read_main_and_secondary_trees(t_decoder_context *context)
|
||
|
|
{
|
||
|
|
/* read first 256 elements (characters) of the main tree */
|
||
|
|
if (false == ReadRepTree(
|
||
|
|
context,
|
||
|
|
256,
|
||
|
|
context->dec_main_tree_prev_len,
|
||
|
|
context->dec_main_tree_len))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* read remaining elements (primary match lengths * positions)
|
||
|
|
* of the main tree
|
||
|
|
*/
|
||
|
|
if (false == ReadRepTree(
|
||
|
|
context,
|
||
|
|
context->dec_num_position_slots*NUM_LENGTHS,
|
||
|
|
&context->dec_main_tree_prev_len[256],
|
||
|
|
&context->dec_main_tree_len[256]))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* create lookup table for the main tree */
|
||
|
|
if (false == make_table(
|
||
|
|
context,
|
||
|
|
MAIN_TREE_ELEMENTS,
|
||
|
|
context->dec_main_tree_len,
|
||
|
|
MAIN_TREE_TABLE_BITS,
|
||
|
|
context->dec_main_tree_table,
|
||
|
|
context->dec_main_tree_left_right))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* read secondary length tree */
|
||
|
|
if (false == ReadRepTree(
|
||
|
|
context,
|
||
|
|
NUM_SECONDARY_LENGTHS,
|
||
|
|
context->dec_secondary_length_tree_prev_len,
|
||
|
|
context->dec_secondary_length_tree_len))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* create lookup table for the secondary length tree */
|
||
|
|
if (false == make_table(
|
||
|
|
context,
|
||
|
|
NUM_SECONDARY_LENGTHS,
|
||
|
|
context->dec_secondary_length_tree_len,
|
||
|
|
SECONDARY_LEN_TREE_TABLE_BITS,
|
||
|
|
context->dec_secondary_length_tree_table,
|
||
|
|
context->dec_secondary_length_tree_left_right))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
/* read 8 element aligned offset tree */
|
||
|
|
bool NEAR read_aligned_offset_tree(t_decoder_context *context)
|
||
|
|
{
|
||
|
|
int i;
|
||
|
|
|
||
|
|
/* read bit lengths of the 8 codes */
|
||
|
|
for (i = 0; i < 8; i++)
|
||
|
|
{
|
||
|
|
context->dec_aligned_len[i] = (byte) getbits(context, 3);
|
||
|
|
}
|
||
|
|
|
||
|
|
if (context->dec_error_condition)
|
||
|
|
return false;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Make table with no left/right, and byte Table[] instead of
|
||
|
|
* short Table[]
|
||
|
|
*/
|
||
|
|
if (false == make_table_8bit(
|
||
|
|
context,
|
||
|
|
context->dec_aligned_len,
|
||
|
|
(byte *) context->dec_aligned_table))
|
||
|
|
{
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
return true;
|
||
|
|
}
|