xdelta3-fgk.h

Linux下一个可以比较二进制文件的工具xdelta3.0u的源码。

      return;
    }

  if (my_left == h->remaining_zeros)
    {
      return;
    }

  /* true if not the leftmost node */
  if (my_left->my_block == cur_block)
    {
      my_left->my_block->block_leader = my_left;
    }
  else
    {
      fgk_free_block (h, cur_block);
    }

  /* node->parent != my_right */
  if ((node->weight == (my_right->weight - 1)) && (my_right != h->root_node))
    {
      node->my_block = my_right->my_block;
    }
  else
    {
      node->my_block = fgk_make_block (h, node);
    }
}

/* When an element is seen the first time this is called to remove it from the list of
 * zero weight elements and introduce a new internal node to the tree.  */
static fgk_node* fgk_increase_zero_weight (fgk_stream *h, int n)
{
  fgk_node *this_zero, *new_internal, *zero_ptr;

  this_zero = h->alphabet + n;

  if (h->zero_freq_count == 1)
    {
      /* this is the last one */
      this_zero->right_child = NULL;

      if (this_zero->right->weight == 1)
	{
	  this_zero->my_block = this_zero->right->my_block;
	}
      else
	{
	  this_zero->my_block = fgk_make_block (h, this_zero);
	}

      h->remaining_zeros = NULL;

      return this_zero;
    }

  zero_ptr = h->remaining_zeros;

  new_internal = h->free_node++;

  new_internal->parent      = zero_ptr->parent;
  new_internal->right       = zero_ptr->right;
  new_internal->weight      = 0;
  new_internal->right_child = this_zero;
  new_internal->left        = this_zero;

  if (h->remaining_zeros == h->root_node)
    {
      /* This is the first element to be coded */
      h->root_node           = new_internal;
      this_zero->my_block    = fgk_make_block (h, this_zero);
      new_internal->my_block = fgk_make_block (h, new_internal);
    }
  else
    {
      new_internal->right->left = new_internal;

      if (zero_ptr->parent->right_child == zero_ptr)
	{
	  zero_ptr->parent->right_child = new_internal;
	}
      else
	{
	  zero_ptr->parent->left_child = new_internal;
	}

      if (new_internal->right->weight == 1)
	{
	  new_internal->my_block = new_internal->right->my_block;
	}
      else
	{
	  new_internal->my_block = fgk_make_block (h, new_internal);
	}

      this_zero->my_block = new_internal->my_block;
    }

  fgk_eliminate_zero (h, this_zero);

  new_internal->left_child = h->remaining_zeros;

  this_zero->right       = new_internal;
  this_zero->left        = h->remaining_zeros;
  this_zero->parent      = new_internal;
  this_zero->left_child  = NULL;
  this_zero->right_child = NULL;

  h->remaining_zeros->parent = new_internal;
  h->remaining_zeros->right  = this_zero;

  return this_zero;
}

/* When a zero frequency element is encoded, it is followed by the
 * binary representation of the index into the remaining elements.
 * Sets a cache to the element before it so that it can be removed
 * without calling this procedure again.  */
static unsigned int fgk_find_nth_zero (fgk_stream* h, int n)
{
  fgk_node *target_ptr = h->alphabet + n;
  fgk_node *head_ptr = h->remaining_zeros;
  unsigned int idx = 0;

  while (target_ptr != head_ptr)
    {
      head_ptr = head_ptr->right_child;
      idx += 1;
    }

  return idx;
}

/* Splices node out of the list of zeros. */
static void fgk_eliminate_zero (fgk_stream* h, fgk_node *node)
{
  if (h->zero_freq_count == 1)
    {
      return;
    }

  fgk_factor_remaining(h);

  if (node->left_child == NULL)
    {
      h->remaining_zeros = h->remaining_zeros->right_child;
      h->remaining_zeros->left_child = NULL;
    }
  else if (node->right_child == NULL)
    {
      node->left_child->right_child = NULL;
    }
  else
    {
      node->right_child->left_child = node->left_child;
      node->left_child->right_child = node->right_child;
    }
}

static void fgk_init_node (fgk_node *node, int i, int size)
{
  if (i < size - 1)
    {
      node->right_child = node + 1;
    }
  else
    {
      node->right_child = NULL;
    }

  if (i >= 1)
    {
      node->left_child = node - 1;
    }
  else
    {
      node->left_child = NULL;
    }

  node->weight      = 0;
  node->parent      = NULL;
  node->right = NULL;
  node->left  = NULL;
  node->my_block    = NULL;
}

/* The data structure used is an array of blocks, which are unions of
 * free pointers and huffnode pointers.  free blocks are a linked list
 * of free blocks, the front of which is h->free_block.  The used
 * blocks are pointers to the head of each block.  */
static fgk_block* fgk_make_block (fgk_stream *h, fgk_node* lead)
{
  fgk_block *ret = h->free_block;

  XD3_ASSERT (h->free_block != NULL);

  h->free_block = h->free_block->block_freeptr;

  ret->block_leader = lead;

  return ret;
}

/* Restores the block to the front of the free list. */
static void fgk_free_block (fgk_stream *h, fgk_block *b)
{
  b->block_freeptr = h->free_block;
  h->free_block = b;
}

/* sets zero_freq_count, zero_freq_rem, and zero_freq_exp to satsity
 * the equation given above.  */
static void fgk_factor_remaining (fgk_stream *h)
{
  unsigned int i;

  i = (--h->zero_freq_count);
  h->zero_freq_exp = 0;

  while (i > 1)
    {
      h->zero_freq_exp += 1;
      i >>= 1;
    }

  i = 1 << h->zero_freq_exp;

  h->zero_freq_rem = h->zero_freq_count - i;
}

/* receives a bit at a time and returns true when a complete code has
 * been received.
 */
static int inline fgk_decode_bit (fgk_stream* h, fgk_bit b)
{
  XD3_ASSERT (b == 1 || b == 0);

  if (IS_ADAPTIVE && h->decode_ptr->weight == 0)
    {
      int bitsreq;

      if (h->zero_freq_rem == 0)
	{
	  bitsreq = h->zero_freq_exp;
	}
      else
	{
	  bitsreq = h->zero_freq_exp + 1;
	}

      h->coded_bits[h->coded_depth] = b;
      h->coded_depth += 1;

      return h->coded_depth >= bitsreq;
    }
  else
    {
      if (b)
	{
	  h->decode_ptr = h->decode_ptr->right_child;
	}
      else
	{
	  h->decode_ptr = h->decode_ptr->left_child;
	}

      if (h->decode_ptr->left_child == NULL)
	{
	  /* If the weight is non-zero, finished. */
	  if (h->decode_ptr->weight != 0)
	    {
	      return 1;
	    }

	  /* zero_freq_count is dropping to 0, finished. */
	  return h->zero_freq_count == 1;
	}
      else
	{
	  return 0;
	}
    }
}

static int fgk_nth_zero (fgk_stream* h, int n)
{
  fgk_node *ret = h->remaining_zeros;

  /* ERROR: if during this loop (ret->right_child == NULL) then the
   * encoder's zero count is too high.  Could return an error code
   * now, but is probably unnecessary overhead, since the caller
   * should check integrity anyway. */
  for (; n != 0 && ret->right_child != NULL; n -= 1)
    {
      ret = ret->right_child;
    }

  return ret - h->alphabet;
}

/* once fgk_decode_bit returns 1, this retrieves an index into the
 * alphabet otherwise this returns 0, indicating more bits are
 * required.
 */
static int fgk_decode_data (fgk_stream* h)
{
  unsigned int elt = h->decode_ptr - h->alphabet;

  if (IS_ADAPTIVE && h->decode_ptr->weight == 0) {
    int i;
    unsigned int n = 0;

    for (i = 0; i < h->coded_depth - 1; i += 1)
      {
	n |= h->coded_bits[i];
	n <<= 1;
      }

    n |= h->coded_bits[i];
    elt = fgk_nth_zero(h, n);
  }

  h->coded_depth = 0;

  if (IS_ADAPTIVE)
    {
      fgk_update_tree(h, elt);
    }

  h->decode_ptr = h->root_node;

  return elt;
}

static void fgk_destroy (xd3_stream *stream,
			 fgk_stream *h)
{
  if (h != NULL)
    {
      xd3_free (stream, h->alphabet);
      xd3_free (stream, h->coded_bits);
      xd3_free (stream, h->block_array);
      xd3_free (stream, h);
    }
}

/*********************************************************************/
/* 			       Xdelta                                */
/*********************************************************************/

static int
xd3_encode_fgk (xd3_stream *stream, fgk_stream *sec_stream, xd3_output *input, xd3_output *output, xd3_sec_cfg *cfg)
{
  bit_state   bstate = BIT_STATE_ENCODE_INIT;
  xd3_output *cur_page;
  int ret;

  /* OPT: quit compression early if it looks bad */
  for (cur_page = input; cur_page; cur_page = cur_page->next_page)
    {
      const uint8_t *inp     = cur_page->base;
      const uint8_t *inp_max = inp + cur_page->next;

      while (inp < inp_max)
	{
	  usize_t bits = fgk_encode_data (sec_stream, *inp++);

	  while (bits--)
	    {
	      if ((ret = xd3_encode_bit (stream, & output, & bstate, fgk_get_encoded_bit (sec_stream)))) { return ret; }
	    }
	}
    }

  return xd3_flush_bits (stream, & output, & bstate);
}

static int
xd3_decode_fgk (xd3_stream     *stream,
		fgk_stream     *sec_stream,
		const uint8_t **input_pos,
		const uint8_t  *const input_max,
		uint8_t       **output_pos,
		const uint8_t  *const output_max)
{
  bit_state bstate;
  uint8_t *output = *output_pos;
  const uint8_t *input = *input_pos;

  for (;;)
    {
      if (input == input_max)
	{
	  stream->msg = "secondary decoder end of input";
	  return XD3_INTERNAL;
	}

      bstate.cur_byte = *input++;

      for (bstate.cur_mask = 1; bstate.cur_mask != 0x100; bstate.cur_mask <<= 1)
	{
	  int done = fgk_decode_bit (sec_stream, (bstate.cur_byte & bstate.cur_mask) && 1);

	  if (! done) { continue; }

	  *output++ = fgk_decode_data (sec_stream);

	  if (output == output_max)
	    {
	      /* During regression testing: */
	      IF_REGRESSION ({
		int ret;
		bstate.cur_mask <<= 1;
		if ((ret = xd3_test_clean_bits (stream, & bstate))) { return ret; }
	      });

	      (*output_pos) = output;
	      (*input_pos) = input;
	      return 0;
	    }
	}
    }
}

#endif /* _XDELTA3_FGK_ */