trees.c

HEG是一个易用的强大的硬件加速2D游戏引擎 他完全具备了具有开发商业质量的2D游戏的中层引擎

/* trees.c -- output deflated data using Huffman coding
 * Copyright (C) 1995-2003 Jean-loup Gailly
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 *  ALGORITHM
 *
 *      The "deflation" process uses several Huffman trees. The more
 *      common source values are represented by shorter bit sequences.
 *
 *      Each code tree is stored in a compressed form which is itself
 * a Huffman encoding of the lengths of all the code strings (in
 * ascending order by source values).  The actual code strings are
 * reconstructed from the lengths in the inflate process, as described
 * in the deflate specification.
 *
 *  REFERENCES
 *
 *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
 *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
 *
 *      Storer, James A.
 *          Data Compression:  Methods and Theory, pp. 49-50.
 *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
 *
 *      Sedgewick, R.
 *          Algorithms, p290.
 *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
 */

/* @(#) $Id: trees.c,v 1.1 2005/11/23 14:29:59 stingerx Exp $ */

#include "deflate.h"


/* ===========================================================================
 * Constants
 */

#define MAX_BL_BITS 7
#define END_BLOCK 256
#define REP_3_6      16
#define REPZ_3_10    17
#define REPZ_11_138  18

static const int extra_lbits[LENGTH_CODES] =
{
  0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
};

static const int extra_dbits[D_CODES] =
{
  0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
};

static const int extra_blbits[BL_CODES] =
{
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7
};

static const BYTE bl_order[BL_CODES] =
{
  16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};

/* The lengths of the bit length codes are sent in order of decreasing
 * probability, to avoid transmitting the lengths for unused bit length codes.
 */

#define Buf_size (8 * 2*sizeof(char))
/* Number of bits used within bi_buf. (bi_buf might be implemented on
 * more than 16 bits on some systems.)
 */

/* ===========================================================================
 * static data. These are initialized only once.
 */

#define DIST_CODE_LEN  512 /* see definition of array dist_code below */

#include "trees.h"

struct static_tree_desc_s
{
  const ct_data *static_tree; /* static tree or NULL */
  const intf *extra_bits; /* extra bits for each code or NULL */
  int extra_base; /* base index for extra_bits */
  int elems; /* max number of elements in the tree */
  int max_length; /* max bit length for the codes */
};

static static_tree_desc static_l_desc =
{
  static_ltree, extra_lbits, LITERALS + 1, L_CODES, MAX_BITS
};

static static_tree_desc static_d_desc =
{
  static_dtree, extra_dbits, 0, D_CODES, MAX_BITS
};

static static_tree_desc static_bl_desc =
{
  (const ct_data*)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS
};

/* ===========================================================================
 * Local (static) routines in this file.
 */

static void tr_static_init(void);

static void init_block(deflate_state *s);

static void pqdownheap OF((deflate_state *s, ct_data *tree, int k));

static void gen_bitlen OF((deflate_state *s, tree_desc *desc));

static void gen_codes OF((ct_data *tree, int max_code, WORD *bl_count));

static void build_tree OF((deflate_state *s, tree_desc *desc));

static void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));

static void send_tree OF((deflate_state *s, ct_data *tree, int max_code));

static int build_bl_tree OF((deflate_state *s));

static void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, int blcodes));

static void compress_block OF((deflate_state *s, ct_data *ltree, ct_data *dtree));

static void set_data_type OF((deflate_state *s));

static DWORD bi_reverse OF((DWORD value, int length));

static void bi_windup OF((deflate_state *s));

static void bi_flush OF((deflate_state *s));

static void copy_block OF((deflate_state *s, BYTE *buf, DWORD len, int header));

#define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)

/* Send a code of the given tree. c and tree must not have side effects */


/* ===========================================================================
 * Output a short LSB first on the stream.
 * IN assertion: there is enough room in pendingBuf.
 */

#define put_short(s, w) { put_byte(s, (BYTE)((w) & 0xff)); put_byte(s, (BYTE)((WORD)(w) >> 8)); }

/* ===========================================================================
 * Send a value on a given number of bits.
 * IN assertion: length <= 16 and value fits in length bits.
 */
#define send_bits(s, value, length) \
{ int len = length;\
if (s->bi_valid > (int)Buf_size - len) {\
int val = value;\
s->bi_buf |= (val << s->bi_valid);\
put_short(s, s->bi_buf);\
s->bi_buf = (WORD)val >> (Buf_size - s->bi_valid);\
s->bi_valid += len - Buf_size;\
} else {\
s->bi_buf |= (value) << s->bi_valid;\
s->bi_valid += len;\
}\
}

/* the arguments must not have side effects */

/* ===========================================================================
 * Initialize the tree data structures for a new zlib stream.
 */

void _tr_init(deflate_state *s)
{
  s->l_desc.dyn_tree = s->dyn_ltree;
  s->l_desc.stat_desc = &static_l_desc;

  s->d_desc.dyn_tree = s->dyn_dtree;
  s->d_desc.stat_desc = &static_d_desc;

  s->bl_desc.dyn_tree = s->bl_tree;
  s->bl_desc.stat_desc = &static_bl_desc;

  s->bi_buf = 0;
  s->bi_valid = 0;
  s->last_eob_len = 8; /* enough lookahead for inflate */

  /* Initialize the first block of the first file: */
  init_block(s);
}

/* ===========================================================================
 * Initialize a new block.
 */
static void init_block(deflate_state *s)
{
  int n;

  for (n = 0; n < L_CODES; n++)
  {
    s->dyn_ltree[n].Freq = 0;
  }

  for (n = 0; n < D_CODES; n++)
  {
    s->dyn_dtree[n].Freq = 0;
  }

  for (n = 0; n < BL_CODES; n++)
  {
    s->bl_tree[n].Freq = 0;
  }

  s->dyn_ltree[END_BLOCK].Freq = 1;
  s->opt_len = s->static_len = 0L;
  s->last_lit = s->matches = 0;
}

//-------------------------------------------------------------------------

#define SMALLEST 1

/* ===========================================================================
 * Remove the smallest element from the heap and recreate the heap with
 * one less element. Updates heap and heap_len.
 */

#define pqremove(s, tree, top) \
{\
top = s->heap[SMALLEST]; \
s->heap[SMALLEST] = s->heap[s->heap_len--]; \
pqdownheap(s, tree, SMALLEST); \
}

/* ===========================================================================
 * Compares to subtrees, using the tree depth as tie breaker when
 * the subtrees have equal frequency. This minimizes the worst case length.
 */

#define smaller(tree, n, m, depth) \
(tree[n].Freq < tree[m].Freq || \
(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

/* ===========================================================================
 * Restore the heap property by moving down the tree starting at node k,
 * exchanging a node with the smallest of its two sons if necessary, stopping
 * when the heap property is re-established (each father smaller than its
 * two sons).
 */

static void pqdownheap(deflate_state *s, ct_data *tree, int k)
{
  int v = s->heap[k];
  int j = k << 1; /* left son of k */

  while (j <= s->heap_len)
  {
    /* Set j to the smallest of the two sons: */
    if (j < s->heap_len && smaller(tree, s->heap[j + 1], s->heap[j], s->depth))
    {
      j++;
    }

    /* Exit if v is smaller than both sons */
    if (smaller(tree, v, s->heap[j], s->depth))
    {
      break;
    }

    /* Exchange v with the smallest son */
    s->heap[k] = s->heap[j];
    k = j;

    /* And continue down the tree, setting j to the left son of k */
    j <<= 1;
  }
  s->heap[k] = v;
}

/* ===========================================================================
 * Compute the optimal bit lengths for a tree and update the total bit length
 * for the current block.
 * IN assertion: the fields freq and dad are set, heap[heap_max] and
 *    above are the tree nodes sorted by increasing frequency.
 * OUT assertions: the field len is set to the optimal bit length, the
 *     array bl_count contains the frequencies for each bit length.
 *     The length opt_len is updated; static_len is also updated if stree is
 *     not null.
 */

static void gen_bitlen(deflate_state *s, tree_desc *desc)
{
  ct_data *tree = desc->dyn_tree;
  int max_code = desc->max_code;
  const ct_data *stree = desc->stat_desc->static_tree;
  const intf *extra = desc->stat_desc->extra_bits;
  int base = desc->stat_desc->extra_base;
  int max_length = desc->stat_desc->max_length;
  int h; /* heap index */
  int n, m; /* iterate over the tree elements */
  int bits; /* bit length */
  int xbits; /* extra bits */
  WORD f; /* frequency */
  int overflow = 0; /* number of elements with bit length too large */

  for (bits = 0; bits <= MAX_BITS; bits++)
  {
    s->bl_count[bits] = 0;
  }

  /* In a first pass, compute the optimal bit lengths (which may
   * overflow in the case of the bit length tree).
   */
  tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */

  for (h = s->heap_max + 1; h < HEAP_SIZE; h++)
  {
    n = s->heap[h];
    bits = tree[tree[n].Dad].Len + 1;

    if (bits > max_length)
    {
      bits = max_length, overflow++;
    }

    tree[n].Len = (WORD)bits;
    /* We overwrite tree[n].Dad which is no longer needed */

    if (n > max_code)
    {
      continue;
    }
    /* not a leaf node */

    s->bl_count[bits]++;
    xbits = 0;

    if (n >= base)
    {
      xbits = extra[n - base];
    }
    f = tree[n].Freq;
    s->opt_len += (DWORD)f *(bits + xbits);

    if (stree)
    {
      s->static_len += (DWORD)f *(stree[n].Len + xbits);
    }
  }
  if (!overflow)
  {
    return ;
  }

  /* This happens for example on obj2 and pic of the Calgary corpus */