trees.c

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

  /* Find the first bit length which could increase: */
  do
  {
    bits = max_length - 1;
    while (s->bl_count[bits] == 0)bits--;
    s->bl_count[bits]--; /* move one leaf down the tree */
    s->bl_count[bits + 1] += 2; /* move one overflow item as its brother */
    s->bl_count[max_length]--;
    /* The brother of the overflow item also moves one step up,
     * but this does not affect bl_count[max_length]
     */
    overflow -= 2;
  }
  while (overflow > 0)
    ;

  /* Now recompute all bit lengths, scanning in increasing frequency.
   * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
   * lengths instead of fixing only the wrong ones. This idea is taken
   * from 'ar' written by Haruhiko Okumura.)
   */
  for (bits = max_length; bits != 0; bits--)
  {
    n = s->bl_count[bits];
    while (n != 0)
    {
      m = s->heap[--h];
      if (m > max_code)
      {
        continue;
      }
      if (tree[m].Len != (DWORD)bits)
      {
        s->opt_len += ((long)bits - (long)tree[m].Len)*(long)tree[m].Freq;
        tree[m].Len = (WORD)bits;
      }
      n--;
    }
  }
}

/* ===========================================================================
 * Generate the codes for a given tree and bit counts (which need not be
 * optimal).
 * IN assertion: the array bl_count contains the bit length statistics for
 * the given tree and the field len is set for all tree elements.
 * OUT assertion: the field code is set for all tree elements of non
 *     zero code length.
 */

static void gen_codes(ct_data *tree, int max_code, WORD *bl_count)
{
  WORD next_code[MAX_BITS + 1]; /* next code value for each bit length */
  WORD code = 0; /* running code value */
  int bits; /* bit index */
  int n; /* code index */

  /* The distribution counts are first used to generate the code values
   * without bit reversal.
   */
  for (bits = 1; bits <= MAX_BITS; bits++)
  {
    next_code[bits] = code = (code + bl_count[bits - 1]) << 1;
  }
  /* Check that the bit counts in bl_count are consistent. The last code
   * must be all ones.
   */

  for (n = 0; n <= max_code; n++)
  {
    int len = tree[n].Len;
    if (len == 0)
    {
      continue;
    }
    /* Now reverse the bits - DW */
    tree[n].Code = (WORD)bi_reverse(next_code[len]++, len);

  }
}

/* ===========================================================================
 * Construct one Huffman tree and assigns the code bit strings and lengths.
 * Update the total bit length for the current block.
 * IN assertion: the field freq is set for all tree elements.
 * OUT assertions: the fields len and code are set to the optimal bit length
 *     and corresponding code. The length opt_len is updated; static_len is
 *     also updated if stree is not null. The field max_code is set.
 */
static void build_tree(deflate_state *s, tree_desc *desc)
{
  ct_data *tree = desc->dyn_tree;
  const ct_data *stree = desc->stat_desc->static_tree;
  int elems = desc->stat_desc->elems;
  int n, m; /* iterate over heap elements */
  int max_code =  - 1; /* largest code with non zero frequency */
  int node; /* new node being created */

  /* Construct the initial heap, with least frequent element in
   * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
   * heap[0] is not used.
   */
  s->heap_len = 0, s->heap_max = HEAP_SIZE;

  for (n = 0; n < elems; n++)
  {
    if (tree[n].Freq != 0)
    {
      s->heap[++(s->heap_len)] = max_code = n;
      s->depth[n] = 0;
    }
    else
    {
      tree[n].Len = 0;
    }
  }

  /* The pkzip format requires that at least one distance code exists,
   * and that at least one bit should be sent even if there is only one
   * possible code. So to avoid special checks later on we force at least
   * two codes of non zero frequency.
   */
  while (s->heap_len < 2)
  {
    node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code: 0);
    tree[node].Freq = 1;
    s->depth[node] = 0;
    s->opt_len--;

    if (stree)
    {
      s->static_len -= stree[node].Len;
    }
    /* node is 0 or 1 so it does not have extra bits */
  }
  desc->max_code = max_code;

  /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
   * establish sub-heaps of increasing lengths:
   */
  for (n = s->heap_len / 2; n >= 1; n--)
  {
    pqdownheap(s, tree, n);
  }

  /* Construct the Huffman tree by repeatedly combining the least two
   * frequent nodes.
   */
  node = elems; /* next internal node of the tree */

  do
  {
    pqremove(s, tree, n); /* n = node of least frequency */
    m = s->heap[SMALLEST]; /* m = node of next least frequency */

    s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
    s->heap[--(s->heap_max)] = m;

    /* Create a new node father of n and m */
    tree[node].Freq = tree[n].Freq + tree[m].Freq;
    s->depth[node] = (BYTE)((s->depth[n] >= s->depth[m] ? s->depth[n]: s->depth[m]) + 1);
    tree[n].Dad = tree[m].Dad = (WORD)node;
    #ifdef DUMP_BL_TREE
      if (tree == s->bl_tree)
      {
        fprintf(stderr, "\nnode %d(%d), sons %d(%d) %d(%d)", node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
      }
    #endif
    /* and insert the new node in the heap */
    s->heap[SMALLEST] = node++;
    pqdownheap(s, tree, SMALLEST);

  }
  while (s->heap_len >= 2);

  s->heap[--(s->heap_max)] = s->heap[SMALLEST];  

  /* At this point, the fields freq and dad are set. We can now
   * generate the bit lengths.
   */
  gen_bitlen(s, (tree_desc*)desc);

  /* The field len is now set, we can generate the bit codes */
  gen_codes((ct_data*)tree, max_code, s->bl_count);
}

/* ===========================================================================
 * Scan a literal or distance tree to determine the frequencies of the codes
 * in the bit length tree.
 */
static void scan_tree(deflate_state *s, ct_data *tree, int max_code)
{
  int n; /* iterates over all tree elements */
  int prevlen =  - 1; /* last emitted length */
  int curlen; /* length of current code */
  int nextlen = tree[0].Len; /* length of next code */
  int count = 0; /* repeat count of the current code */
  int max_count = 7; /* max repeat count */
  int min_count = 4; /* min repeat count */

  if (nextlen == 0)
  {
    max_count = 138, min_count = 3;
  }
  tree[max_code + 1].Len = (WORD)0xffff; /* guard */

  for (n = 0; n <= max_code; n++)
  {
    curlen = nextlen;
    nextlen = tree[n + 1].Len;
    if (++count < max_count && curlen == nextlen)
    {
      continue;
    }
    else if (count < min_count)
    {
      s->bl_tree[curlen].Freq += count;
    }
    else if (curlen != 0)
    {
      if (curlen != prevlen)
      {
        s->bl_tree[curlen].Freq++;
      }
      s->bl_tree[REP_3_6].Freq++;
    }
    else if (count <= 10)
    {
      s->bl_tree[REPZ_3_10].Freq++;
    }
    else
    {
      s->bl_tree[REPZ_11_138].Freq++;
    }
    count = 0;
    prevlen = curlen;
    if (nextlen == 0)
    {
      max_count = 138, min_count = 3;
    }
    else if (curlen == nextlen)
    {
      max_count = 6, min_count = 3;
    }
    else
    {
      max_count = 7, min_count = 4;
    }
  }
}

/* ===========================================================================
 * Send a literal or distance tree in compressed form, using the codes in
 * bl_tree.
 */
static void send_tree(deflate_state *s, ct_data *tree, int max_code)
{
  int n; /* iterates over all tree elements */
  int prevlen =  - 1; /* last emitted length */
  int curlen; /* length of current code */
  int nextlen = tree[0].Len; /* length of next code */
  int count = 0; /* repeat count of the current code */
  int max_count = 7; /* max repeat count */
  int min_count = 4; /* min repeat count */

   /* tree[max_code+1].Len = -1; */ /* guard already set */
  if (nextlen == 0)
  {
    max_count = 138, min_count = 3;
  }

  for (n = 0; n <= max_code; n++)
  {
    curlen = nextlen;
    nextlen = tree[n + 1].Len;
    if (++count < max_count && curlen == nextlen)
    {
      continue;
    }
    else if (count < min_count)
    {
      do
      {
        send_code(s, curlen, s->bl_tree);
      }
      while (--count != 0);

    }
    else if (curlen != 0)
    {
      if (curlen != prevlen)
      {
        send_code(s, curlen, s->bl_tree);
        count--;
      }
      send_code(s, REP_3_6, s->bl_tree);
      send_bits(s, count - 3, 2);

    }
    else if (count <= 10)
    {
      send_code(s, REPZ_3_10, s->bl_tree);
      send_bits(s, count - 3, 3);

    }
    else
    {
      send_code(s, REPZ_11_138, s->bl_tree);
      send_bits(s, count - 11, 7);
    }
    count = 0;
    prevlen = curlen;
    if (nextlen == 0)
    {
      max_count = 138, min_count = 3;
    }
    else if (curlen == nextlen)
    {
      max_count = 6, min_count = 3;
    }
    else
    {
      max_count = 7, min_count = 4;
    }
  }
}

/* ===========================================================================
 * Construct the Huffman tree for the bit lengths and return the index in
 * bl_order of the last bit length code to send.
 */
static int build_bl_tree(deflate_state *s)
{
  int max_blindex; /* index of last bit length code of non zero freq */

  /* Determine the bit length frequencies for literal and distance trees */
  scan_tree(s, (ct_data*)s->dyn_ltree, s->l_desc.max_code);
  scan_tree(s, (ct_data*)s->dyn_dtree, s->d_desc.max_code);

  /* Build the bit length tree: */
  build_tree(s, (tree_desc*)(&(s->bl_desc)));
  /* opt_len now includes the length of the tree representations, except
   * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
   */

  /* Determine the number of bit length codes to send. The pkzip format
   * requires that at least 4 bit length codes be sent. (appnote.txt says
   * 3 but the actual value used is 4.)
   */
  for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--)
  {
    if (s->bl_tree[bl_order[max_blindex]].Len != 0)
    {
      break;
    }
  }
  /* Update opt_len to include the bit length tree and counts */
  s->opt_len += 3 *(max_blindex + 1) + 5+5+4;

  return max_blindex;
}

/* ===========================================================================