xdelta3-test.h

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

/* xdelta 3 - delta compression tools and library
 * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007.  Joshua P. MacDonald
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/* This is public-domain Mersenne Twister code,
 * attributed to Michael Brundage.  Thanks!
 * http://www.qbrundage.com/michaelb/pubs/essays/random_number_generation.html
 */
static const uint32_t TEST_SEED1 = 5489UL;
#define MT_LEN 624
#define MT_IA 397
static const uint32_t UPPER_MASK = 0x80000000;
static const uint32_t LOWER_MASK = 0x7FFFFFFF;
static const uint32_t MATRIX_A = 0x9908B0DF;

typedef struct mtrand mtrand;

struct mtrand {
  int mt_index_;
  uint32_t mt_buffer_[MT_LEN];
};

void mt_init(mtrand *mt, uint32_t seed) {
  int i;
  mt->mt_buffer_[0] = seed;
  mt->mt_index_ = MT_LEN;
  for (i = 1; i < MT_LEN; i++) {
    /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
    /* In the previous versions, MSBs of the seed affect   */
    /* only MSBs of the array mt[].                        */
    /* 2002/01/09 modified by Makoto Matsumoto             */
    mt->mt_buffer_[i] = 
	(1812433253UL * (mt->mt_buffer_[i-1] ^ (mt->mt_buffer_[i-1] >> 30)) + i);
  }
}


uint32_t mt_random (mtrand *mt) {
  uint32_t y;
  unsigned long mag01[2];
  mag01[0] = 0;
  mag01[1] = MATRIX_A;

  if (mt->mt_index_ >= MT_LEN) {
    int kk;

    for (kk = 0; kk < MT_LEN - MT_IA; kk++) {
      y = (mt->mt_buffer_[kk] & UPPER_MASK) | (mt->mt_buffer_[kk + 1] & LOWER_MASK);
      mt->mt_buffer_[kk] = mt->mt_buffer_[kk + MT_IA] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    for (;kk < MT_LEN - 1; kk++) {
      y = (mt->mt_buffer_[kk] & UPPER_MASK) | (mt->mt_buffer_[kk + 1] & LOWER_MASK);
      mt->mt_buffer_[kk] = mt->mt_buffer_[kk + (MT_IA - MT_LEN)] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    y = (mt->mt_buffer_[MT_LEN - 1] & UPPER_MASK) | (mt->mt_buffer_[0] & LOWER_MASK);
    mt->mt_buffer_[MT_LEN - 1] = mt->mt_buffer_[MT_IA - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
    mt->mt_index_ = 0;
  }
  
  y = mt->mt_buffer_[mt->mt_index_++];
  
  y ^= (y >> 11);
  y ^= (y << 7) & 0x9d2c5680UL;
  y ^= (y << 15) & 0xefc60000UL;
  y ^= (y >> 18);
  
  return y;
}

static mtrand static_mtrand;

#include <math.h>

static uint32_t
mt_exp_rand (uint32_t mean, uint32_t max_value)
{
  double mean_d = mean;
  double erand  = log (1.0 / (mt_random (&static_mtrand) / 
			      (double)UINT32_MAX));
  uint32_t x = (uint32_t) (mean_d * erand + 0.5);

  return min (x, max_value);
}

#ifndef WIN32
#include <sys/wait.h>
#endif

#define MSG_IS(x) (stream->msg != NULL && strcmp ((x), stream->msg) == 0)

static const usize_t TWO_MEGS_AND_DELTA = (2 << 20) + (1 << 10);
static const usize_t ADDR_CACHE_ROUNDS = 10000;

static const usize_t TEST_FILE_MEAN   = 16384;
static const double TEST_ADD_MEAN     = 128;
static const double TEST_ADD_MAX      = 512;
static const double TEST_ADD_RATIO    = 0.1;
static const double TEST_EPSILON      = 0.25;

#define TESTBUFSIZE (1024 * 16)

#define TESTFILESIZE (1024)

static char   TEST_TARGET_FILE[TESTFILESIZE];
static char   TEST_SOURCE_FILE[TESTFILESIZE];
static char   TEST_DELTA_FILE[TESTFILESIZE];
static char   TEST_RECON_FILE[TESTFILESIZE];
static char   TEST_RECON2_FILE[TESTFILESIZE];
static char   TEST_COPY_FILE[TESTFILESIZE];
static char   TEST_NOPERM_FILE[TESTFILESIZE];

#define CHECK(cond) if (!(cond)) { DP(RINT "check failure: " #cond); abort(); }

/* Use a fixed soft config so that test values are fixed.  See also
 * test_compress_text(). */
static const char* test_softcfg_str = "-C9,3,4,8,2,36,70";

static int test_setup (void);

/***********************************************************************
 TEST HELPERS
 ***********************************************************************/

static void DOT (void) { DP(RINT "."); }
static int do_cmd (xd3_stream *stream, const char *buf)
{
  int ret;
  if ((ret = system (buf)) != 0)
    {
      if (WIFEXITED (ret))
	{
	  stream->msg = "command exited non-zero";
	}
      else
	{
	  stream->msg = "abnormal command termination";
	}
      return XD3_INTERNAL;
    }
  return 0;
}

static int do_fail (xd3_stream *stream, const char *buf)
{
  int ret;
  ret = system (buf);
  if (! WIFEXITED (ret) || WEXITSTATUS (ret) != 1)
    {
      stream->msg = "command should have not succeeded";
      DP(RINT "command was %s", buf);
      return XD3_INTERNAL;
    }
  return 0;
}

/* Test that the exponential distribution actually produces its mean. */
static int
test_random_numbers (xd3_stream *stream, int ignore)
{
  usize_t i;
  usize_t sum = 0;
  usize_t mean = 50;
  usize_t n_rounds = 1000000;
  double average, error;
  double allowed_error = 0.1;

  mt_init (& static_mtrand, 0x9f73f7fe);

  for (i = 0; i < n_rounds; i += 1)
    {
      sum += mt_exp_rand (mean, USIZE_T_MAX);
    }

  average = (double) sum / (double) n_rounds;
  error   = average - (double) mean;

  if (error < allowed_error && error > -allowed_error)
    {
      return 0;
    }

  /*DP(RINT "error is %f\n", error);*/
  stream->msg = "random distribution looks broken";
  return XD3_INTERNAL;
}

static void
test_unlink (char* file)
{
  char buf[TESTBUFSIZE];
  while (unlink (file) != 0)
    {
      if (errno == ENOENT)
	{
	  break;
	}
      sprintf (buf, "rm -f %s", file);
      system (buf);
    }
}

static void
test_cleanup (void)
{
  test_unlink (TEST_TARGET_FILE);
  test_unlink (TEST_SOURCE_FILE);
  test_unlink (TEST_DELTA_FILE);
  test_unlink (TEST_RECON_FILE);
  test_unlink (TEST_RECON2_FILE);
  test_unlink (TEST_COPY_FILE);
  test_unlink (TEST_NOPERM_FILE);
}

static int
test_setup (void)
{
  static int x = 0;
  x++;
  sprintf (TEST_TARGET_FILE, "/tmp/xdtest.target.%d", x);
  sprintf (TEST_SOURCE_FILE, "/tmp/xdtest.source.%d", x);
  sprintf (TEST_DELTA_FILE, "/tmp/xdtest.delta.%d", x);
  sprintf (TEST_RECON_FILE, "/tmp/xdtest.recon.%d", x);
  sprintf (TEST_RECON2_FILE, "/tmp/xdtest.recon2.%d", x);
  sprintf (TEST_COPY_FILE, "/tmp/xdtest.copy.%d", x);
  sprintf (TEST_NOPERM_FILE, "/tmp/xdtest.noperm.%d", x);
  test_cleanup();
  return 0;
}

static int
test_make_inputs (xd3_stream *stream, xoff_t *ss_out, xoff_t *ts_out)
{
  usize_t ts = (mt_random (&static_mtrand) % TEST_FILE_MEAN) + TEST_FILE_MEAN / 2;
  usize_t ss = (mt_random (&static_mtrand) % TEST_FILE_MEAN) + TEST_FILE_MEAN / 2;
  uint8_t *buf = (uint8_t*) malloc (ts + ss), *sbuf = buf, *tbuf = buf + ss;
  usize_t sadd = 0, sadd_max = ss * TEST_ADD_RATIO;
  FILE  *tf = NULL, *sf = NULL;
  usize_t i, j;
  int ret;

  if (buf == NULL) { return ENOMEM; }

  if ((tf = fopen (TEST_TARGET_FILE, "w")) == NULL ||
      (ss_out != NULL && (sf = fopen (TEST_SOURCE_FILE, "w")) == NULL))
    {
      stream->msg = "write failed";
      ret = get_errno ();
      goto failure;
    }

  if (ss_out != NULL)
    {
      for (i = 0; i < ss; )
	{
	  sbuf[i++] = mt_random (&static_mtrand);
	}
    }

  /* Then modify the data to produce copies, everything not copied is
   * an add.  The following logic produces the TEST_ADD_RATIO.  The
   * variable SADD contains the number of adds so far, which should
   * not exceed SADD_MAX. */

  /* DP(RINT "ss = %u ts = %u\n", ss, ts); */
  for (i = 0; i < ts; )
    {
      size_t left = ts - i;
      size_t next = mt_exp_rand (TEST_ADD_MEAN, TEST_ADD_MAX);
      size_t add_left = sadd_max - sadd;
      double add_prob = (left == 0) ? 0 : (add_left / (double) left);
      int do_copy;

      next = min (left, next);
      do_copy = (next > add_left || (mt_random (&static_mtrand) / (double)USIZE_T_MAX) >= add_prob);

      if (ss_out == NULL)
	{
	  do_copy &= (i > 0);
	}
      else
	{
	  do_copy &= (ss - next) > 0;
	}

      if (do_copy)
	{
	  /* Copy */
	  size_t offset = mt_random (&static_mtrand) % ((ss_out == NULL) ? i : (ss - next));
	  /* DP(RINT "[%u] copy %u at %u ", i, next, offset); */

	  for (j = 0; j < next; j += 1)
	    {
	      char c = ((ss_out == NULL) ? tbuf : sbuf)[offset + j];
	      /* DP(RINT "%x%x", (c >> 4) & 0xf, c & 0xf); */
	      tbuf[i++] = c;
	    }
	  /* DP(RINT "\n"); */
	}
      else
	{
	  /* Add */
	  /* DP(RINT "[%u] add %u ", i, next); */
	  for (j = 0; j < next; j += 1)
	    {
	      char c = mt_random (&static_mtrand);
	      /* DP(RINT "%x%x", (c >> 4) & 0xf, c & 0xf); */
	      tbuf[i++] = c;
	    }
	  /* DP(RINT "\n"); */
	  sadd += next;
	}
    }

  /* DP(RINT "sadd = %u max = %u\n", sadd, sadd_max); */

  if ((fwrite (tbuf, 1, ts, tf) != ts) ||
      (ss_out != NULL && (fwrite (sbuf, 1, ss, sf) != ss)))
    {
      stream->msg = "write failed";
      ret = get_errno ();
      goto failure;
    }

  if ((ret = fclose (tf)) || (ss_out != NULL && (ret = fclose (sf))))
    {
      stream->msg = "close failed";
      ret = get_errno ();
      goto failure;
    }

  if (ts_out) { (*ts_out) = ts; }
  if (ss_out) { (*ss_out) = ss; }

 failure:
  free (buf);
  return ret;
}

static int
compare_files (xd3_stream *stream, const char* tgt, const char *rec)
{
  FILE *orig, *recons;
  static uint8_t obuf[TESTBUFSIZE], rbuf[TESTBUFSIZE];
  int offset = 0;
  int i;
  int oc, rc;

  if ((orig = fopen (tgt, "r")) == NULL)
    {
      DP(RINT "open %s failed", tgt);
      stream->msg = "open failed";
      return get_errno ();
    }

    if ((recons = fopen (rec, "r")) == NULL)
      {
	DP(RINT "open %s failed", rec);
	stream->msg = "open failed";
	return get_errno ();
      }

  for (;;)
    {
      oc = fread (obuf, 1, TESTBUFSIZE, orig);
      rc = fread (rbuf, 1, TESTBUFSIZE, recons);

      if (oc < 0 || rc < 0)
	{
	  stream->msg = "read failed";
	  return get_errno ();
	}

	if (oc != rc)
	  {
	    stream->msg = "compare files: different length";
	    return XD3_INTERNAL;
	  }

	if (oc == 0)
	  {
	    break;
	  }

	for (i = 0; i < oc; i += 1)
	  {
	    if (obuf[i] != rbuf[i])
	      {
		stream->msg = "compare files: different values";
		return XD3_INTERNAL;
	      }
	  }

	offset += oc;
    }

    fclose (orig);
    fclose (recons);
    return 0;
}

static int
test_save_copy (const char *origname)
{
  char buf[TESTBUFSIZE];
  int ret;

  sprintf (buf, "cp -f %s %s", origname, TEST_COPY_FILE);

  if ((ret = system (buf)) != 0)
    {
      return XD3_INTERNAL;
    }

  return 0;
}

static int
test_file_size (const char* file, xoff_t *size)
{
  struct stat sbuf;
  int ret;
  (*size) = 0;

  if (stat (file, & sbuf) < 0)
    {
      ret = get_errno ();
      DP(RINT "xdelta3: stat failed: %s: %s\n", file, strerror (ret));
      return ret;
    }

  if (! S_ISREG (sbuf.st_mode))
    {
      ret = XD3_INTERNAL;
      DP(RINT "xdelta3: not a regular file: %s: %s\n", file, strerror (ret));
      return ret;
    }

  (*size) = sbuf.st_size;
  return 0;
}

/***********************************************************************
 READ OFFSET
 ***********************************************************************/

/* Common test for read_integer errors: encodes a 64-bit value and
 * then attempts to read as a 32-bit value.  If TRUNC is non-zero,
 * attempts to get errors by shortening the input, otherwise it should
 * overflow.  Expects XD3_INTERNAL and MSG. */
static int
test_read_integer_error (xd3_stream *stream, usize_t trunto, const char *msg)
{
  uint64_t eval = 1ULL << 34;
  uint32_t rval;
  xd3_output *buf = NULL;
  const uint8_t *max;
  const uint8_t *inp;
  int ret;

  buf = xd3_alloc_output (stream, buf);

  if ((ret = xd3_emit_uint64_t (stream, & buf, eval)))
    {
      goto fail;
    }

 again:

  inp = buf->base;
  max = buf->base + buf->next - trunto;

  if ((ret = xd3_read_uint32_t (stream, & inp, max, & rval)) != XD3_INVALID_INPUT ||
      !MSG_IS (msg))
    {
      ret = XD3_INTERNAL;
    }
  else if (trunto && trunto < buf->next)
    {
      trunto += 1;
      goto again;
    }