trees.c

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

 * Send the header for a block using dynamic Huffman trees: the counts, the
 * lengths of the bit length codes, the literal tree and the distance tree.
 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
 */
static void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
{
  int rank; /* index in bl_order */

  send_bits(s, lcodes - 257, 5); /* not +255 as stated in appnote.txt */
  send_bits(s, dcodes - 1, 5);
  send_bits(s, blcodes - 4, 4); /* not -3 as stated in appnote.txt */
  for (rank = 0; rank < blcodes; rank++)
  {
    send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
  }
  send_tree(s, (ct_data*)s->dyn_ltree, lcodes - 1); /* literal tree */
  send_tree(s, (ct_data*)s->dyn_dtree, dcodes - 1); /* distance tree */
}

/* ===========================================================================
 * Send a stored block
 */
void _tr_stored_block(deflate_state *s, BYTE *buf, DWORD stored_len, int eof)
{
  send_bits(s, (STORED_BLOCK << 1) + eof, 3); /* send block type */
  copy_block(s, buf, (DWORD)stored_len, 1); /* with header */
}

/* ===========================================================================
 * Send one empty static block to give enough lookahead for inflate.
 * This takes 10 bits, of which 7 may remain in the bit buffer.
 * The current inflate code requires 9 bits of lookahead. If the
 * last two codes for the previous block (real code plus EOB) were coded
 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
 * the last real code. In this case we send two empty static blocks instead
 * of one. (There are no problems if the previous block is stored or fixed.)
 * To simplify the code, we assume the worst case of last real code encoded
 * on one bit only.
 */
void _tr_align(deflate_state *s)
{
  send_bits(s, STATIC_TREES << 1, 3);
  send_code(s, END_BLOCK, static_ltree);

  bi_flush(s);
  /* Of the 10 bits for the empty block, we have already sent
   * (10 - bi_valid) bits. The lookahead for the last real code (before
   * the EOB of the previous block) was thus at least one plus the length
   * of the EOB plus what we have just sent of the empty static block.
   */
  if (1+s->last_eob_len + 10-s->bi_valid < 9)
  {
    send_bits(s, STATIC_TREES << 1, 3);
    send_code(s, END_BLOCK, static_ltree);

    bi_flush(s);
  }

  s->last_eob_len = 7;
}

/* ===========================================================================
 * Determine the best encoding for the current block: dynamic trees, static
 * trees or store, and output the encoded block to the zip file.
 */
void _tr_flush_block(deflate_state *s, BYTE *buf, DWORD stored_len, int eof)
{
  DWORD opt_lenb, static_lenb; /* opt_len and static_len in bytes */
  int max_blindex = 0; /* index of last bit length code of non zero freq */

  /* Build the Huffman trees unless a stored block is forced */
  if (s->level > 0)
  {
    /* Check if the file is ascii or binary */
    if (s->data_type == Z_UNKNOWN)
    {
      set_data_type(s);
    }

    /* Construct the literal and distance trees */
    build_tree(s, (tree_desc*)(&(s->l_desc)));
    build_tree(s, (tree_desc*)(&(s->d_desc)));
    /* At this point, opt_len and static_len are the total bit lengths of
     * the compressed block data, excluding the tree representations.
     */

    /* Build the bit length tree for the above two trees, and get the index
     * in bl_order of the last bit length code to send.
     */
    max_blindex = build_bl_tree(s);

    /* Determine the best encoding. Compute the block lengths in bytes. */
    opt_lenb = (s->opt_len + 3+7) >> 3;
    static_lenb = (s->static_len + 3+7) >> 3;

    if (static_lenb <= opt_lenb)
    {
      opt_lenb = static_lenb;
    }

  }
  else
  {
    opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
  }

  #ifdef FORCE_STORED
    if (buf != (char*)0)
    {
      /* force stored block */
    #else
      if (stored_len + 4 <= opt_lenb && buf != (char*)0)
      {
        /* 4: two words for the lengths */
      #endif
      /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
       * Otherwise we can't have processed more than WSIZE input bytes since
       * the last block flush, because compression would have been
       * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
       * transform a block into a stored block.
       */
      _tr_stored_block(s, buf, stored_len, eof);

      #ifdef FORCE_STATIC
      }
      else if (static_lenb >= 0)
      {
        /* force static trees */
      #else
      }
      else if (static_lenb == opt_lenb)
      {
      #endif
      send_bits(s, (STATIC_TREES << 1) + eof, 3);
      compress_block(s, (ct_data*)static_ltree, (ct_data*)static_dtree);
    }
    else
    {
      send_bits(s, (DYN_TREES << 1) + eof, 3);
      send_all_trees(s, s->l_desc.max_code + 1, s->d_desc.max_code + 1, max_blindex + 1);
      compress_block(s, (ct_data*)s->dyn_ltree, (ct_data*)s->dyn_dtree);
    }
    /* The above check is made mod 2^32, for files larger than 512 MB
     * and uLong implemented on 32 bits.
     */
    init_block(s);

    if (eof)
    {
      bi_windup(s);
    }
  }

  /* ===========================================================================
   * Save the match info and tally the frequency counts. Return true if
   * the current block must be flushed.
   */
  int _tr_tally(s, dist, lc)deflate_state *s;
  DWORD dist; /* distance of matched string */
  DWORD lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
  {
    s->d_buf[s->last_lit] = (WORD)dist;
    s->l_buf[s->last_lit++] = (BYTE)lc;
    if (dist == 0)
    {
      /* lc is the unmatched char */
      s->dyn_ltree[lc].Freq++;
    }
    else
    {
      s->matches++;
      /* Here, lc is the match length - MIN_MATCH */
      dist--; /* dist = match distance - 1 */
      s->dyn_ltree[_length_code[lc] + LITERALS + 1].Freq++;
      s->dyn_dtree[d_code(dist)].Freq++;
    }

    #ifdef TRUNCATE_BLOCK
      /* Try to guess if it is profitable to stop the current block here */
      if ((s->last_lit &0x1fff) == 0 && s->level > 2)
      {
        /* Compute an upper bound for the compressed length */
        ulg out_length = (ulg)s->last_lit *8L;
        ulg in_length = (ulg)((long)s->strstart - s->block_start);
        int dcode;
        for (dcode = 0; dcode < D_CODES; dcode++)
        {
          out_length += (ulg)s->dyn_dtree[dcode].Freq *(5L + extra_dbits[dcode]);
        }
        out_length >>= 3;
        Tracev((stderr, "\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", s->last_lit, in_length, out_length, 100L - out_length * 100L / in_length));
        if (s->matches < s->last_lit / 2 && out_length < in_length / 2)
        {
          return 1;
        }
      }
    #endif
    return (s->last_lit == s->lit_bufsize - 1);
    /* We avoid equality with lit_bufsize because of wraparound at 64K
     * on 16 bit machines and because stored blocks are restricted to
     * 64K-1 bytes.
     */
  }

  /* ===========================================================================
   * Send the block data compressed using the given Huffman trees
   */
  static void compress_block(deflate_state *s, ct_data *ltree, ct_data *dtree)
  {
    DWORD dist; /* distance of matched string */
    int lc; /* match length or unmatched char (if dist == 0) */
    DWORD lx = 0; /* running index in l_buf */
    DWORD code; /* the code to send */
    int extra; /* number of extra bits to send */

    if (s->last_lit != 0)
    {
      do
      {
        dist = s->d_buf[lx];
        lc = s->l_buf[lx++];
        if (dist == 0)
        {
          send_code(s, lc, ltree); /* send a literal byte */
        }
        else
        {
          /* Here, lc is the match length - MIN_MATCH */
          code = _length_code[lc];
          send_code(s, code + LITERALS + 1, ltree); /* send the length code */
          extra = extra_lbits[code];
          if (extra != 0)
          {
            lc -= base_length[code];
            send_bits(s, lc, extra); /* send the extra length bits */
          }
          dist--; /* dist is now the match distance - 1 */
          code = d_code(dist);
          send_code(s, code, dtree); /* send the distance code */
          extra = extra_dbits[code];

          if (extra != 0)
          {
            dist -= base_dist[code];
            send_bits(s, dist, extra); /* send the extra distance bits */
          }
        } /* literal or match pair ? */

        /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
      }
      while (lx < s->last_lit);
    }

    send_code(s, END_BLOCK, ltree)
      ;
    s->last_eob_len = ltree[END_BLOCK].Len;
  }

  /* ===========================================================================
   * Set the data type to ASCII or BINARY, using a crude approximation:
   * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
   * IN assertion: the fields freq of dyn_ltree are set and the total of all
   * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
   */
  static void set_data_type(deflate_state *s)
  {
    int n = 0;
    DWORD ascii_freq = 0;
    DWORD bin_freq = 0;

    while (n < 7)
    {
      bin_freq += s->dyn_ltree[n++].Freq;
    }
    while (n < 128)
    {
      ascii_freq += s->dyn_ltree[n++].Freq;
    }
    while (n < LITERALS)
    {
      bin_freq += s->dyn_ltree[n++].Freq;
    }
    s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
  }

  /* ===========================================================================
   * Reverse the first len bits of a code, using straightforward code (a faster
   * method would use a table)
   * IN assertion: 1 <= len <= 15
   */
  static DWORD bi_reverse(DWORD code, int len)
  {
    register DWORD res = 0;

    do
    {
      res |= code &1;
      code >>= 1, res <<= 1;
    }
    while (--len > 0);

    return res >> 1;
  }

  /* ===========================================================================
   * Flush the bit buffer, keeping at most 7 bits in it.
   */
  static void bi_flush(deflate_state *s)
  {
    if (s->bi_valid == 16)
    {
      put_short(s, s->bi_buf);
      s->bi_buf = 0;
      s->bi_valid = 0;
    }
    else if (s->bi_valid >= 8)
    {
      put_byte(s, (Byte)s->bi_buf);
      s->bi_buf >>= 8;
      s->bi_valid -= 8;
    }
  }

  /* ===========================================================================
   * Flush the bit buffer and align the output on a byte boundary
   */
  static void bi_windup(deflate_state *s)
  {
    if (s->bi_valid > 8)
    {
      put_short(s, s->bi_buf);
    }
    else if (s->bi_valid > 0)
    {
      put_byte(s, (Byte)s->bi_buf);
    }
    s->bi_buf = 0;
    s->bi_valid = 0;
  }

  /* ===========================================================================
   * Copy a stored block, storing first the length and its
   * one's complement if requested.
   */
  static void copy_block(deflate_state *s, BYTE *buf, DWORD len, int header)
  {
    bi_windup(s); /* align on byte boundary */
    s->last_eob_len = 8; /* enough lookahead for inflate */

    if (header)
    {
      put_short(s, (WORD)len);
      put_short(s, (WORD)~len);

    }

    while (len--)
    {
      put_byte(s,  *buf++);
    }
  }