xdelta3.c

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

#define A32_NMAX 5552   /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */

#define A32_DO1(buf,i)  {s1 += buf[i]; s2 += s1;}
#define A32_DO2(buf,i)  A32_DO1(buf,i); A32_DO1(buf,i+1);
#define A32_DO4(buf,i)  A32_DO2(buf,i); A32_DO2(buf,i+2);
#define A32_DO8(buf,i)  A32_DO4(buf,i); A32_DO4(buf,i+4);
#define A32_DO16(buf)   A32_DO8(buf,0); A32_DO8(buf,8);

static unsigned long adler32 (unsigned long adler, const uint8_t *buf, usize_t len)
{
    unsigned long s1 = adler & 0xffff;
    unsigned long s2 = (adler >> 16) & 0xffff;
    int k;

    while (len > 0)
      {
        k    = (len < A32_NMAX) ? len : A32_NMAX;
        len -= k;

	while (k >= 16)
	  {
	    A32_DO16(buf);
	    buf += 16;
            k -= 16;
	  }

	if (k != 0)
	  {
	    do
	      {
		s1 += *buf++;
		s2 += s1;
	      }
	    while (--k);
	  }

        s1 %= A32_BASE;
        s2 %= A32_BASE;
    }

    return (s2 << 16) | s1;
}

/***********************************************************************
 Run-length function
 ***********************************************************************/

#if XD3_ENCODER
static int
xd3_comprun (const uint8_t *seg, int slook, uint8_t *run_cp)
{
  int i;
  int     run_l = 0;
  uint8_t run_c = 0;

  for (i = 0; i < slook; i += 1)
    {
      NEXTRUN(seg[i]);
    }

  (*run_cp) = run_c;

  return run_l;
}
#endif

/***********************************************************************
 Basic encoder/decoder functions
 ***********************************************************************/

static inline int
xd3_decode_byte (xd3_stream *stream, usize_t *val)
{
  if (stream->avail_in == 0)
    {
      stream->msg = "further input required";
      return XD3_INPUT;
    }

  (*val) = stream->next_in[0];

  DECODE_INPUT (1);
  return 0;
}

static inline int
xd3_decode_bytes (xd3_stream *stream, uint8_t *buf, usize_t *pos, usize_t size)
{
  usize_t want;
  usize_t take;

  /* Note: The case where (*pos == size) happens when a zero-length appheader or code
   * table is transmitted, but there is nothing in the standard against that. */

  while (*pos < size)
    {
      if (stream->avail_in == 0)
	{
	  stream->msg = "further input required";
	  return XD3_INPUT;
	}

      want = size - *pos;
      take = min (want, stream->avail_in);

      memcpy (buf + *pos, stream->next_in, take);

      DECODE_INPUT (take);
      (*pos) += take;
    }

  return 0;
}

#if XD3_ENCODER
static inline int
xd3_emit_byte (xd3_stream  *stream,
	       xd3_output **outputp,
	       uint8_t      code)
{
  xd3_output *output = (*outputp);

  if (output->next == output->avail)
    {
      xd3_output *aoutput;

      if ((aoutput = xd3_alloc_output (stream, output)) == NULL)
	{
	  return ENOMEM;
	}

      output = (*outputp) = aoutput;
    }

  output->base[output->next++] = code;

  return 0;
}

static inline int
xd3_emit_bytes (xd3_stream     *stream,
		xd3_output    **outputp,
		const uint8_t  *base,
		usize_t          size)
{
  xd3_output *output = (*outputp);

  do
    {
      usize_t take;

      if (output->next == output->avail)
	{
	  xd3_output *aoutput;

	  if ((aoutput = xd3_alloc_output (stream, output)) == NULL)
	    {
	      return ENOMEM;
	    }

	  output = (*outputp) = aoutput;
	}

      take = min (output->avail - output->next, size);

      memcpy (output->base + output->next, base, take);

      output->next += take;
      size -= take;
      base += take;
    }
  while (size > 0);

  return 0;
}
#endif /* XD3_ENCODER */

/*********************************************************************
 Integer encoder/decoder functions
 **********************************************************************/

#define DECODE_INTEGER_TYPE(PART,OFLOW)                                \
  while (stream->avail_in != 0)                                        \
    {                                                                  \
      usize_t next = stream->next_in[0];                               \
                                                                       \
      DECODE_INPUT(1);                                                 \
                                                                       \
      if (PART & OFLOW)                                                \
	{                                                              \
	  stream->msg = "overflow in decode_integer";                  \
	  return XD3_INVALID_INPUT;                                    \
	}                                                              \
                                                                       \
      PART = (PART << 7) | (next & 127);                               \
                                                                       \
      if ((next & 128) == 0)                                           \
	{                                                              \
	  (*val) = PART;                                               \
	  PART = 0;                                                    \
	  return 0;                                                    \
	}                                                              \
    }                                                                  \
                                                                       \
  stream->msg = "further input required";                              \
  return XD3_INPUT

#define READ_INTEGER_TYPE(TYPE, OFLOW)                                 \
  TYPE val = 0;                                                        \
  const uint8_t *inp = (*inpp);                                        \
  usize_t next;                                                        \
                                                                       \
  do                                                                   \
    {                                                                  \
      if (inp == max)                                                  \
	{                                                              \
	  stream->msg = "end-of-input in read_integer";                \
	  return XD3_INVALID_INPUT;                                    \
	}                                                              \
                                                                       \
      if (val & OFLOW)                                                 \
	{                                                              \
	  stream->msg = "overflow in read_intger";                     \
	  return XD3_INVALID_INPUT;                                    \
	}                                                              \
                                                                       \
      next = (*inp++);                                                 \
      val  = (val << 7) | (next & 127);                                \
    }                                                                  \
  while (next & 128);                                                  \
                                                                       \
  (*valp) = val;                                                       \
  (*inpp) = inp;                                                       \
                                                                       \
  return 0

#define EMIT_INTEGER_TYPE()                                            \
  /* max 64-bit value in base-7 encoding is 9.1 bytes */               \
  uint8_t buf[10];                                                     \
  usize_t  bufi = 10;                                                  \
                                                                       \
  XD3_ASSERT (num >= 0);                                               \
                                                                       \
  /* This loop performs division and turns on all MSBs. */             \
  do                                                                   \
    {                                                                  \
      buf[--bufi] = (num & 127) | 128;                                 \
      num >>= 7;                                                       \
    }                                                                  \
  while (num != 0);                                                    \
                                                                       \
  /* Turn off MSB of the last byte. */                                 \
  buf[9] &= 127;                                                       \
                                                                       \
  XD3_ASSERT (bufi >= 0);                                              \
                                                                       \
  return xd3_emit_bytes (stream, output, buf + bufi, 10 - bufi)

#define IF_SIZEOF32(x) if (num < (1U   << (7 * (x)))) return (x);
#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x);

#if USE_UINT32
static inline uint32_t
xd3_sizeof_uint32_t (uint32_t num)
{
  IF_SIZEOF32(1);
  IF_SIZEOF32(2);
  IF_SIZEOF32(3);
  IF_SIZEOF32(4);
  return 5;
}

static inline int
xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val)
{ DECODE_INTEGER_TYPE (stream->dec_32part, UINT32_OFLOW_MASK); }

static inline int
xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
		   const uint8_t *max, uint32_t *valp)
{ READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK); }

#if XD3_ENCODER
static inline int
xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num)
{ EMIT_INTEGER_TYPE (); }
#endif
#endif

#if USE_UINT64
static inline int
xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val)
{ DECODE_INTEGER_TYPE (stream->dec_64part, UINT64_OFLOW_MASK); }

#if XD3_ENCODER
static inline int
xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num)
{ EMIT_INTEGER_TYPE (); }
#endif

/* These are tested but not used */
#if REGRESSION_TEST
static int
xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp,
		   const uint8_t *max, uint64_t *valp)
{ READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK); }

static uint32_t
xd3_sizeof_uint64_t (uint64_t num)
{
  IF_SIZEOF64(1);
  IF_SIZEOF64(2);
  IF_SIZEOF64(3);
  IF_SIZEOF64(4);
  IF_SIZEOF64(5);
  IF_SIZEOF64(6);
  IF_SIZEOF64(7);
  IF_SIZEOF64(8);
  IF_SIZEOF64(9);

  return 10;
}
#endif

#endif

/***********************************************************************
 Address cache stuff
 ***********************************************************************/

static int
xd3_alloc_cache (xd3_stream *stream)
{
  if (stream->acache.near_array != NULL)
    {
      xd3_free (stream, stream->acache.near_array);
    }

  if (stream->acache.same_array != NULL)
    {
      xd3_free (stream, stream->acache.same_array);
    }

  if (((stream->acache.s_near > 0) &&
       (stream->acache.near_array = (usize_t*)
	xd3_alloc (stream, stream->acache.s_near, sizeof (usize_t)))
       == NULL) ||
      ((stream->acache.s_same > 0) &&
       (stream->acache.same_array = (usize_t*)
	xd3_alloc (stream, stream->acache.s_same * 256, sizeof (usize_t)))
       == NULL))
    {
      return ENOMEM;
    }

  return 0;
}

void
xd3_init_cache (xd3_addr_cache* acache)
{
  if (acache->s_near > 0)
    {
      memset (acache->near_array, 0, acache->s_near * sizeof (usize_t));
      acache->next_slot = 0;
    }

  if (acache->s_same > 0)
    {
      memset (acache->same_array, 0, acache->s_same * 256 * sizeof (usize_t));
    }
}

static void
xd3_update_cache (xd3_addr_cache* acache, usize_t addr)
{
  if (acache->s_near > 0)
    {
      acache->near_array[acache->next_slot] = addr;
      acache->next_slot = (acache->next_slot + 1) % acache->s_near;
    }

  if (acache->s_same > 0)
    {
      acache->same_array[addr % (acache->s_same*256)] = addr;
    }
}

#if XD3_ENCODER
/* OPT: this gets called a lot, can it be optimized? */
static int
xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mode)
{
  usize_t d, bestd;
  us