xdelta3.c

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

#if REGRESSION_TEST
#include "xdelta3-test.h"
#endif

#if PYTHON_MODULE
#include "xdelta3-python.h"
#endif

#endif /* __XDELTA3_C_HEADER_PASS__ */
#ifdef __XDELTA3_C_INLINE_PASS__

/****************************************************************
 Instruction tables
 *****************************************************************/

/* The following code implements a parametrized description of the
 * code table given above for a few reasons.  It is not necessary for
 * implementing the standard, to support compression with variable
 * tables, so an implementation is only required to know the default
 * code table to begin decompression.  (If the encoder uses an
 * alternate table, the table is included in compressed form inside
 * the VCDIFF file.)
 *
 * Before adding variable-table support there were two functions which
 * were hard-coded to the default table above.
 * xd3_compute_default_table() would create the default table by
 * filling a 256-elt array of xd3_dinst values.  The corresponding
 * function, xd3_choose_instruction(), would choose an instruction
 * based on the hard-coded parameters of the default code table.
 *
 * Notes: The parametrized code table description here only generates
 * tables of a certain regularity similar to the default table by
 * allowing to vary the distribution of single- and
 * double-instructions and change the number of near and same copy
 * modes.  More exotic tables are only possible by extending this
 * code.
 *
 * For performance reasons, both the parametrized and non-parametrized
 * versions of xd3_choose_instruction remain.  The parametrized
 * version is only needed for testing multi-table decoding support.
 * If ever multi-table encoding is required, this can be optimized by
 * compiling static functions for each table.
 */

/* The XD3_CHOOSE_INSTRUCTION calls xd3_choose_instruction with the
 * table description when GENERIC_ENCODE_TABLES are in use.  The
 * IF_GENCODETBL macro enables generic-code-table specific code. */
#if GENERIC_ENCODE_TABLES
#define XD3_CHOOSE_INSTRUCTION(stream,prev,inst) xd3_choose_instruction (stream->code_table_desc, prev, inst)
#define IF_GENCODETBL(x) x
#else
#define XD3_CHOOSE_INSTRUCTION(stream,prev,inst) xd3_choose_instruction (prev, inst)
#define IF_GENCODETBL(x)
#endif

/* This structure maintains information needed by
 * xd3_choose_instruction to compute the code for a double instruction
 * by first indexing an array of code_table_sizes by copy mode, then
 * using (offset + (muliplier * X)) */
struct _xd3_code_table_sizes {
  uint8_t cpy_max;
  uint8_t offset;
  uint8_t mult;
};

/* This contains a complete description of a code table. */
struct _xd3_code_table_desc
{
  /* Assumes a single RUN instruction */
  /* Assumes that MIN_MATCH is 4 */

  uint8_t add_sizes;            /* Number of immediate-size single adds (default 17) */
  uint8_t near_modes;           /* Number of near copy modes (default 4) */
  uint8_t same_modes;           /* Number of same copy modes (default 3) */
  uint8_t cpy_sizes;            /* Number of immediate-size single copies (default 15) */

  uint8_t addcopy_add_max;      /* Maximum add size for an add-copy double instruction,
				   all modes (default 4) */
  uint8_t addcopy_near_cpy_max; /* Maximum cpy size for an add-copy double instruction,
				   up through VCD_NEAR modes (default 6) */
  uint8_t addcopy_same_cpy_max; /* Maximum cpy size for an add-copy double instruction,
				   VCD_SAME modes (default 4) */

  uint8_t copyadd_add_max;      /* Maximum add size for a copy-add double instruction,
				   all modes (default 1) */
  uint8_t copyadd_near_cpy_max; /* Maximum cpy size for a copy-add double instruction,
				   up through VCD_NEAR modes (default 4) */
  uint8_t copyadd_same_cpy_max; /* Maximum cpy size for a copy-add double instruction,
				   VCD_SAME modes (default 4) */

  xd3_code_table_sizes addcopy_max_sizes[MAX_MODES];
  xd3_code_table_sizes copyadd_max_sizes[MAX_MODES];
};

/* The rfc3284 code table is represented: */
static const xd3_code_table_desc __rfc3284_code_table_desc = {
  17, /* add sizes */
  4,  /* near modes */
  3,  /* same modes */
  15, /* copy sizes */

  4,  /* add-copy max add */
  6,  /* add-copy max cpy, near */
  4,  /* add-copy max cpy, same */

  1,  /* copy-add max add */
  4,  /* copy-add max cpy, near */
  4,  /* copy-add max cpy, same */

  /* addcopy */
  { {6,163,3},{6,175,3},{6,187,3},{6,199,3},{6,211,3},{6,223,3},{4,235,1},{4,239,1},{4,243,1} },
  /* copyadd */
  { {4,247,1},{4,248,1},{4,249,1},{4,250,1},{4,251,1},{4,252,1},{4,253,1},{4,254,1},{4,255,1} },
};

#if GENERIC_ENCODE_TABLES
/* An alternate code table for testing (5 near, 0 same):
 *
 *         TYPE      SIZE     MODE    TYPE     SIZE     MODE     INDEX
 *        ---------------------------------------------------------------
 *     1.  Run         0        0     Noop       0        0        0
 *     2.  Add    0, [1,23]     0     Noop       0        0      [1,24]
 *     3.  Copy   0, [4,20]     0     Noop       0        0     [25,42]
 *     4.  Copy   0, [4,20]     1     Noop       0        0     [43,60]
 *     5.  Copy   0, [4,20]     2     Noop       0        0     [61,78]
 *     6.  Copy   0, [4,20]     3     Noop       0        0     [79,96]
 *     7.  Copy   0, [4,20]     4     Noop       0        0     [97,114]
 *     8.  Copy   0, [4,20]     5     Noop       0        0    [115,132]
 *     9.  Copy   0, [4,20]     6     Noop       0        0    [133,150]
 *    10.  Add       [1,4]      0     Copy     [4,6]      0    [151,162]
 *    11.  Add       [1,4]      0     Copy     [4,6]      1    [163,174]
 *    12.  Add       [1,4]      0     Copy     [4,6]      2    [175,186]
 *    13.  Add       [1,4]      0     Copy     [4,6]      3    [187,198]
 *    14.  Add       [1,4]      0     Copy     [4,6]      4    [199,210]
 *    15.  Add       [1,4]      0     Copy     [4,6]      5    [211,222]
 *    16.  Add       [1,4]      0     Copy     [4,6]      6    [223,234]
 *    17.  Copy        4      [0,6]   Add      [1,3]      0    [235,255]
 *        --------------------------------------------------------------- */
static const xd3_code_table_desc __alternate_code_table_desc = {
  23, /* add sizes */
  5,  /* near modes */
  0,  /* same modes */
  17, /* copy sizes */

  4,  /* add-copy max add */
  6,  /* add-copy max cpy, near */
  0,  /* add-copy max cpy, same */

  3,  /* copy-add max add */
  4,  /* copy-add max cpy, near */
  0,  /* copy-add max cpy, same */

  /* addcopy */
  { {6,151,3},{6,163,3},{6,175,3},{6,187,3},{6,199,3},{6,211,3},{6,223,3},{0,0,0},{0,0,0} },
  /* copyadd */
  { {4,235,1},{4,238,1},{4,241,1},{4,244,1},{4,247,1},{4,250,1},{4,253,1},{0,0,0},{0,0,0} },
};
#endif

/* Computes code table entries of TBL using the specified description. */
static void
xd3_build_code_table (const xd3_code_table_desc *desc, xd3_dinst *tbl)
{
  usize_t size1, size2, mode;
  usize_t cpy_modes = 2 + desc->near_modes + desc->same_modes;
  xd3_dinst *d = tbl;

  (d++)->type1 = XD3_RUN;
  (d++)->type1 = XD3_ADD;

  for (size1 = 1; size1 <= desc->add_sizes; size1 += 1, d += 1)
    {
      d->type1 = XD3_ADD;
      d->size1 = size1;
    }

  for (mode = 0; mode < cpy_modes; mode += 1)
    {
      (d++)->type1 = XD3_CPY + mode;

      for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes; size1 += 1, d += 1)
	{
	  d->type1 = XD3_CPY + mode;
	  d->size1 = size1;
	}
    }

  for (mode = 0; mode < cpy_modes; mode += 1)
    {
      for (size1 = 1; size1 <= desc->addcopy_add_max; size1 += 1)
	{
	  usize_t max = (mode < 2U + desc->near_modes) ?
	    desc->addcopy_near_cpy_max :
	    desc->addcopy_same_cpy_max;

	  for (size2 = MIN_MATCH; size2 <= max; size2 += 1, d += 1)
	    {
	      d->type1 = XD3_ADD;
	      d->size1 = size1;
	      d->type2 = XD3_CPY + mode;
	      d->size2 = size2;
	    }
	}
    }

  for (mode = 0; mode < cpy_modes; mode += 1)
    {
      usize_t max = (mode < 2U + desc->near_modes) ?
	desc->copyadd_near_cpy_max :
	desc->copyadd_same_cpy_max;

      for (size1 = MIN_MATCH; size1 <= max; size1 += 1)
	{
	  for (size2 = 1; size2 <= desc->copyadd_add_max; size2 += 1, d += 1)
	    {
	      d->type1 = XD3_CPY + mode;
	      d->size1 = size1;
	      d->type2 = XD3_ADD;
	      d->size2 = size2;
	    }
	}
    }

  XD3_ASSERT (d - tbl == 256);
}

/* This function generates the static default code table. */
static const xd3_dinst*
xd3_rfc3284_code_table (void)
{
  static xd3_dinst __rfc3284_code_table[256];

  if (__rfc3284_code_table[0].type1 != XD3_RUN)
    {
      xd3_build_code_table (& __rfc3284_code_table_desc, __rfc3284_code_table);
    }

  return __rfc3284_code_table;
}

#if XD3_ENCODER
#if GENERIC_ENCODE_TABLES
/* This function generates the alternate code table. */
static const xd3_dinst*
xd3_alternate_code_table (void)
{
  static xd3_dinst __alternate_code_table[256];

  if (__alternate_code_table[0].type1 != XD3_RUN)
    {
      xd3_build_code_table (& __alternate_code_table_desc, __alternate_code_table);
    }

  return __alternate_code_table;
}

/* This function computes the ideal second instruction INST based on
 * preceding instruction PREV.  If it is possible to issue a double
 * instruction based on this pair it sets PREV->code2, otherwise it
 * sets INST->code1. */
static void
xd3_choose_instruction (const xd3_code_table_desc *desc, xd3_rinst *prev, xd3_rinst *inst)
{
  switch (inst->type)
    {
    case XD3_RUN:
      /* The 0th instruction is RUN */
      inst->code1 = 0;
      break;

    case XD3_ADD:

      if (inst->size > desc->add_sizes)
	{
	  /* The first instruction is non-immediate ADD */
	  inst->code1 = 1;
	}
      else
	{
	  /* The following ADD_SIZES instructions are immediate ADDs */
	  inst->code1 = 1 + inst->size;

	  /* Now check for a possible COPY-ADD double instruction */
	  if (prev != NULL)
	    {
	      int prev_mode = prev->type - XD3_CPY;

	      /* If previous is a copy.  Note: as long as the previous
	       * is not a RUN instruction, it should be a copy because
	       * it cannot be an add.  This check is more clear. */
	      if (prev_mode >= 0 && inst->size <= desc->copyadd_add_max)
		{
		  const xd3_code_table_sizes *sizes = & desc->copyadd_max_sizes[prev_mode];

		  /* This check and the inst->size-<= above are == in
		     the default table. */
		  if (prev->size <= sizes->cpy_max)
		    {
		      /* The second and third exprs are 0 in the
			 default table. */
		      prev->code2 = sizes->offset +
			(sizes->mult * (prev->size - MIN_MATCH)) +
			(inst->size - MIN_ADD);
		    }
		}
	    }
	}
      break;

    default:
      {
	int mode = inst->type - XD3_CPY;

	/* The large copy instruction is offset by the run, large add,
	 * and immediate adds, then multipled by the number of
	 * immediate copies plus one (the large copy) (i.e., if there
	 * are 15 immediate copy instructions then there are 16 copy
	 * instructions per mode). */
	inst->code1 = 2 + desc->add_sizes + (1 + desc->cpy_sizes) * mode;

	/* Now if the copy is short enough for an immediate instruction. */
	if (inst->size < MIN_MATCH + desc->cpy_sizes &&
	    /* TODO: there needs to be a more comprehensive test for this
	     * boundary condition, merge is now exercising code in which
	     * size < MIN_MATCH is possible and it's unclear if the above
	     * size < (MIN_MATCH + cpy_sizes) should be a <= from inspection
	     * of the default table version below. */
	    inst->size >= MIN_MATCH)
	  {
	    inst->code1 += inst->size + 1 - MIN_MATCH;

	    /* Now check for a possible ADD-COPY double instruction. */
	    if ( (prev != NULL) &&
		 (prev->type == XD3_ADD) &&
		 (prev->size <= desc->addcopy_add_max) )
	      {
		const xd3_code_table_sizes *sizes = & desc->addcopy_max_sizes[mode];

		if (inst->size <= sizes->cpy_max)
		  {
		    prev->code2 = sizes->offset +
		      (sizes->mult * (prev->size - MIN_ADD)) +
		      (inst->size - MIN_MATCH);
		  }
	      }
	  }
      }
    }
}
#else /* GENERIC_ENCODE_TABLES */

/* This version of xd3_choose_instruction is hard-coded for the default
   table. */
static void
xd3_choose_instruction (xd3_rinst *prev, xd3_rinst *inst)
{
  switch (inst->type)
    {
    case XD3_RUN:
      inst->code1 = 0;
      break;

    case XD3_ADD:
      inst->code1 = 1;

      if (inst->size <= 17)
	{
	  inst->code1 += inst->size;

	  if ( (inst->size == 1) &&
	       (prev != NULL) &&
	       (prev->size == 4) &&
	       (prev->type >= XD3_CPY) )
	    {
	      prev->code2 = 247 + (prev->type - XD3_CPY);
	    }
	}

      break;

    default:
      {
	int mode = inst->type - XD3_CPY;

	XD3_ASSERT (inst->type >= XD3_CPY && inst->type < 12);

	inst->code1 = 19 + 16 * mode;

	if (inst->size <= 18 && inst->size >= 4)
	  {
	    inst->code1 += inst->size - 3;

	    if ( (prev != NULL) &&
		 (prev->type == XD3_ADD) &&
		 (prev->size <= 4) )
	      {