xdelta3.c

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

		if ( (inst->size <= 6) &&
		     (mode       <= 5) )
		  {
		    prev->code2 = 163 + (mode * 12) + (3 * (prev->size - 1)) + (inst->size - 4);

		    XD3_ASSERT (prev->code2 <= 234);
		  }
		else if ( (inst->size == 4) &&
			  (mode       >= 6) )
		  {
		    prev->code2 = 235 + ((mode - 6) * 4) + (prev->size - 1);

		    XD3_ASSERT (prev->code2 <= 246);
		  }
	      }
	  }

	XD3_ASSERT (inst->code1 <= 162);
      }
      break;
    }
}
#endif /* GENERIC_ENCODE_TABLES */

/***********************************************************************
 Instruction table encoder/decoder
 ***********************************************************************/

#if GENERIC_ENCODE_TABLES
#if GENERIC_ENCODE_TABLES_COMPUTE == 0

/* In this case, we hard-code the result of
 * compute_code_table_encoding for each alternate code table,
 * presuming that saves time/space.  This has been 131 bytes, but
 * secondary compression was turned off. */
static const uint8_t __alternate_code_table_compressed[178] =
{0xd6,0xc3,0xc4,0x00,0x00,0x01,0x8a,0x6f,0x40,0x81,0x27,0x8c,0x00,0x00,0x4a,0x4a,0x0d,0x02,0x01,0x03,
0x01,0x03,0x00,0x01,0x00,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,
0x0f,0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x00,0x01,0x01,0x01,0x02,0x02,0x02,0x03,0x03,0x03,0x04,
0x04,0x04,0x04,0x00,0x04,0x05,0x06,0x01,0x02,0x03,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x05,0x05,0x05,
0x06,0x06,0x06,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x00,0x02,0x00,0x18,0x13,0x63,0x00,0x1b,0x00,0x54,
0x00,0x15,0x23,0x6f,0x00,0x28,0x13,0x54,0x00,0x15,0x01,0x1a,0x31,0x23,0x6c,0x0d,0x23,0x48,0x00,0x15,
0x93,0x6f,0x00,0x28,0x04,0x23,0x51,0x04,0x32,0x00,0x2b,0x00,0x12,0x00,0x12,0x00,0x12,0x00,0x12,0x00,
0x12,0x00,0x12,0x53,0x57,0x9c,0x07,0x43,0x6f,0x00,0x34,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00,
0x0c,0x00,0x0c,0x00,0x15,0x00,0x82,0x6f,0x00,0x15,0x12,0x0c,0x00,0x03,0x03,0x00,0x06,0x00,};

static int
xd3_compute_alternate_table_encoding (xd3_stream *stream, const uint8_t **data, usize_t *size)
{
  (*data) = __alternate_code_table_compressed;
  (*size) = sizeof (__alternate_code_table_compressed);
  return 0;
}

#else

/* The alternate code table will be computed and stored here. */
static uint8_t __alternate_code_table_compressed[CODE_TABLE_VCDIFF_SIZE];
static usize_t  __alternate_code_table_compressed_size;

/* This function generates a delta describing the code table for
 * encoding within a VCDIFF file.  This function is NOT thread safe
 * because it is only intended that this function is used to generate
 * statically-compiled strings. */
int xd3_compute_code_table_encoding (xd3_stream *in_stream,
				     const xd3_dinst *code_table,
				     uint8_t *comp_string,
				     usize_t *comp_string_size)
{
  /* TODO: use xd3_encode_memory() */
  uint8_t dflt_string[CODE_TABLE_STRING_SIZE];
  uint8_t code_string[CODE_TABLE_STRING_SIZE];
  xd3_stream stream;
  xd3_source source;
  xd3_config config;
  int ret;

  memset (& source, 0, sizeof (source));

  xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string);
  xd3_compute_code_table_string (code_table, code_string);

  /* Use DJW secondary compression if it is on by default.  This saves
   * about 20 bytes. */
  xd3_init_config (& config, XD3_FLUSH | (SECONDARY_DJW ? XD3_SEC_DJW : 0));

  /* Be exhaustive. */
  config.sprevsz = 1<<11;
  config.srcwin_maxsz = CODE_TABLE_STRING_SIZE;

  config.smatch_cfg = XD3_SMATCH_SOFT;
  config.smatcher_soft.large_look    = 4;
  config.smatcher_soft.large_step    = 1;
  config.smatcher_soft.small_look    = 4;
  config.smatcher_soft.small_chain   = CODE_TABLE_STRING_SIZE;
  config.smatcher_soft.small_lchain  = CODE_TABLE_STRING_SIZE;
  config.smatcher_soft.max_lazy      = CODE_TABLE_STRING_SIZE;
  config.smatcher_soft.long_enough   = CODE_TABLE_STRING_SIZE;

  if ((ret = xd3_config_stream (& stream, & config))) { goto fail; }

  source.size     = CODE_TABLE_STRING_SIZE;
  source.blksize  = CODE_TABLE_STRING_SIZE;
  source.onblk    = CODE_TABLE_STRING_SIZE;
  source.name     = "";
  source.curblk   = dflt_string;
  source.curblkno = 0;

  if ((ret = xd3_set_source (& stream, & source))) { goto fail; }

  if ((ret = xd3_encode_stream (& stream, code_string, CODE_TABLE_STRING_SIZE,
				comp_string, comp_string_size, CODE_TABLE_VCDIFF_SIZE))) { goto fail; }

 fail:

  in_stream->msg = stream.msg;
  xd3_free_stream (& stream);
  return ret;
}

/* Compute a delta between alternate and rfc3284 tables.  As soon as
 * another alternate table is added, this code should become generic.
 * For now there is only one alternate table for testing. */
static int
xd3_compute_alternate_table_encoding (xd3_stream *stream, const uint8_t **data, usize_t *size)
{
  int ret;

  if (__alternate_code_table_compressed[0] == 0)
    {
      if ((ret = xd3_compute_code_table_encoding (stream, xd3_alternate_code_table (),
						  __alternate_code_table_compressed,
						  & __alternate_code_table_compressed_size)))
	{
	  return ret;
	}

      /* During development of a new code table, enable this variable to print
       * the new static contents and determine its size.  At run time the
       * table will be filled in appropriately, but at least it should have
       * the proper size beforehand. */
#if GENERIC_ENCODE_TABLES_COMPUTE_PRINT
      {
	int i;

	DP(RINT, "\nstatic const usize_t __alternate_code_table_compressed_size = %u;\n",
		 __alternate_code_table_compressed_size);

	DP(RINT, "static const uint8_t __alternate_code_table_compressed[%u] =\n{",
		 __alternate_code_table_compressed_size);

	for (i = 0; i < __alternate_code_table_compressed_size; i += 1)
	  {
	    DP(RINT, "0x%02x,", __alternate_code_table_compressed[i]);
	    if ((i % 20) == 19) { DP(RINT, "\n"); }
	  }

	DP(RINT, "};\n");
      }
#endif
    }

  (*data) = __alternate_code_table_compressed;
  (*size) = __alternate_code_table_compressed_size;

  return 0;
}
#endif /* GENERIC_ENCODE_TABLES_COMPUTE != 0 */
#endif /* GENERIC_ENCODE_TABLES */

#endif /* XD3_ENCODER */

/* This function generates the 1536-byte string specified in sections 5.4 and
 * 7 of rfc3284, which is used to represent a code table within a VCDIFF
 * file. */
void xd3_compute_code_table_string (const xd3_dinst *code_table, uint8_t *str)
{
  int i, s;

  XD3_ASSERT (CODE_TABLE_STRING_SIZE == 6 * 256);

  for (s = 0; s < 6; s += 1)
    {
      for (i = 0; i < 256; i += 1)
	{
	  switch (s)
	    {
	    case 0: *str++ = (code_table[i].type1 >= XD3_CPY ? XD3_CPY : code_table[i].type1); break;
	    case 1: *str++ = (code_table[i].type2 >= XD3_CPY ? XD3_CPY : code_table[i].type2); break;
	    case 2: *str++ = (code_table[i].size1); break;
	    case 3: *str++ = (code_table[i].size2); break;
	    case 4: *str++ = (code_table[i].type1 >= XD3_CPY ? code_table[i].type1 - XD3_CPY : 0); break;
	    case 5: *str++ = (code_table[i].type2 >= XD3_CPY ? code_table[i].type2 - XD3_CPY : 0); break;
	    }
	}
    }
}

/* This function translates the code table string into the internal representation.  The
 * stream's near and same-modes should already be set. */
static int
xd3_apply_table_string (xd3_stream *stream, const uint8_t *code_string)
{
  int i, s;
  int modes = TOTAL_MODES (stream);
  xd3_dinst *code_table;

  if ((code_table = stream->code_table_alloc =
       (xd3_dinst*) xd3_alloc (stream, sizeof (xd3_dinst), 256)) == NULL)
    {
      return ENOMEM;
    }

  for (s = 0; s < 6; s += 1)
    {
      for (i = 0; i < 256; i += 1)
	{
	  switch (s)
	    {
	    case 0:
	      if (*code_string > XD3_CPY)
		{
		  stream->msg = "invalid code-table opcode";
		  return XD3_INTERNAL;
		}
	      code_table[i].type1 = *code_string++;
	      break;
	    case 1:
	      if (*code_string > XD3_CPY)
		{
		  stream->msg = "invalid code-table opcode";
		  return XD3_INTERNAL;
		}
	      code_table[i].type2 = *code_string++;
	      break;
	    case 2:
	      if (*code_string != 0 && code_table[i].type1 == XD3_NOOP)
		{
		  stream->msg = "invalid code-table size";
		  return XD3_INTERNAL;
		}
	      code_table[i].size1 = *code_string++;
	      break;
	    case 3:
	      if (*code_string != 0 && code_table[i].type2 == XD3_NOOP)
		{
		  stream->msg = "invalid code-table size";
		  return XD3_INTERNAL;
		}
	      code_table[i].size2 = *code_string++;
	      break;
	    case 4:
	      if (*code_string >= modes)
		{
		  stream->msg = "invalid code-table mode";
		  return XD3_INTERNAL;
		}
	      if (*code_string != 0 && code_table[i].type1 != XD3_CPY)
		{
		  stream->msg = "invalid code-table mode";
		  return XD3_INTERNAL;
		}
	      code_table[i].type1 += *code_string++;
	      break;
	    case 5:
	      if (*code_string >= modes)
		{
		  stream->msg = "invalid code-table mode";
		  return XD3_INTERNAL;
		}
	      if (*code_string != 0 && code_table[i].type2 != XD3_CPY)
		{
		  stream->msg = "invalid code-table mode";
		  return XD3_INTERNAL;
		}
	      code_table[i].type2 += *code_string++;
	      break;
	    }
	}
    }

  stream->code_table = code_table;
  return 0;
}

/* This function applies a code table delta and returns an actual code table. */
static int
xd3_apply_table_encoding (xd3_stream *in_stream, const uint8_t *data, usize_t size)
{
  uint8_t dflt_string[CODE_TABLE_STRING_SIZE];
  uint8_t code_string[CODE_TABLE_STRING_SIZE];
  usize_t code_size;
  xd3_stream stream;
  xd3_source source;
  int ret;

  /* The default code table string can be cached if alternate code tables ever become
   * popular. */
  xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string);

  source.size     = CODE_TABLE_STRING_SIZE;
  source.blksize  = CODE_TABLE_STRING_SIZE;
  source.onblk    = CODE_TABLE_STRING_SIZE;
  source.name     = "rfc3284 code table";
  source.curblk   = dflt_string;
  source.curblkno = 0;

  if ((ret = xd3_config_stream (& stream, NULL)) ||
      (ret = xd3_set_source (& stream, & source)) ||
      (ret = xd3_decode_stream (& stream, data, size, code_string, & code_size, sizeof (code_string))))
    {
      in_stream->msg = stream.msg;
      goto fail;
    }

  if (code_size != sizeof (code_string))
    {
      stream.msg = "corrupt code-table encoding";
      ret = XD3_INTERNAL;
      goto fail;
    }

  if ((ret = xd3_apply_table_string (in_stream, code_string))) { goto fail; }

 fail:

  xd3_free_stream (& stream);
  return ret;
}

/***********************************************************************/

static inline void
xd3_swap_uint8p (uint8_t** p1, uint8_t** p2)
{
  uint8_t *t = (*p1);
  (*p1) = (*p2);
  (*p2) = t;
}

static inline void
xd3_swap_usize_t (usize_t* p1, usize_t* p2)
{
  usize_t t = (*p1);
  (*p1) = (*p2);
  (*p2) = t;
}

/* It's not constant time, but it computes the log. */
static int
xd3_check_pow2 (usize_t value, usize_t *logof)
{
  usize_t x = 1;
  usize_t nolog;
  if (logof == NULL) {
    logof = &nolog;
  }

  *logof = 0;

  for (; x != 0; x <<= 1, *logof += 1)
    {
      if (x == value)
	{
	  return 0;
	}
    }

  return XD3_INTERNAL;
}

static usize_t
xd3_pow2_roundup (usize_t x)
{
  usize_t i = 1;
  while (x > i) {
    i <<= 1;
  }
  return i;
}

static usize_t
xd3_round_blksize (usize_t sz, usize_t blksz)
{
  usize_t mod = sz & (blksz-1);

  XD3_ASSERT (xd3_check_pow2 (blksz, NULL) == 0);

  return mod ? (sz + (blksz - mod)) : sz;
}

/***********************************************************************
 Adler32 stream function: code copied from Zlib, defined in RFC1950
 ***********************************************************************/

#define A32_BASE 65521L /* Largest prime smaller than 2^16 */