windows-xp/Source/XPSP1/NT/base/mspatch/lzx/decoder/dectree.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;
}