root/xdelta30r/xdelta3-test.h

/* xdelta 3 - delta compression tools and library
 * Copyright (C) 2001, 2003, 2004, 2005, 2006.  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
 */

#include <math.h>

#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     = 16;
static const double TEST_ADD_MAX      = 256;
static const double TEST_ADD_RATIO    = 0.1;
static const double TEST_EPSILON      = 0.55;

#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];

static int test_exponential_dist (usize_t mean, usize_t max);

#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 = "-C64,64,4,128,16,8,128";

/******************************************************************************************
 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;
    }
  DOT ();
  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;
    }
  DOT ();
  return 0;
}

static int
test_exponential_dist (usize_t mean, usize_t max)
{
  double mean_d = mean;
  double erand  = log (1.0 / (rand () / (double)RAND_MAX));
  usize_t x = (usize_t) (mean_d * erand + 0.5);

  return min (x, max);
}

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

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

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

  if (error < allowed_error && error > -allowed_error)
    {
      /*DP(RINT "error is %f\n", error);*/
      return 0;
    }

  stream->msg = "random distribution looks broken";
  return XD3_INTERNAL;
}

static int
test_setup (void)
{
  static int x = 0;
  x++;
  //DP(RINT "test setup: %d", 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);
  return 0;
}

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)
{
  static int x = 0;
  x++;
  //DP(RINT "test cleanup: %d", x);  
  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_make_inputs (xd3_stream *stream, xoff_t *ss_out, xoff_t *ts_out)
{
  usize_t ts = (rand () % TEST_FILE_MEAN) + TEST_FILE_MEAN;
  usize_t ss = (rand () % TEST_FILE_MEAN) + TEST_FILE_MEAN;
  uint8_t *buf = malloc (ts + ss), *sbuf = buf /*, *tbuf = buf + ss*/;
  usize_t sadd = 0, sadd_max = ss * TEST_ADD_RATIO;
  FILE  *tf /*, *sf*/;
  usize_t i, j;
  int ret;

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

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

  /* 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. */
  for (i = 0; i < ss; )
    {
      usize_t left = ss - i;
      usize_t next = test_exponential_dist (TEST_ADD_MEAN, TEST_ADD_MAX);
      usize_t add_left = sadd_max - sadd;
      double add_prob = (left == 0) ? 0 : (add_left / left);

      next = min (left, next);

      if (i > 0 && (next > add_left || (rand() / (double)RAND_MAX) >= add_prob))
        {
          /* Copy */
          usize_t offset = rand () % i;

          for (j = 0; j < next; j += 1)
            {
              sbuf[i++] = sbuf[offset + j];
            }
        }
      else
        {
          /* Add */
          for (j = 0; j < next; j += 1)
            {
              sbuf[i++] = rand ();
            }
        }
    }

  if ((fwrite (sbuf, 1, ss, tf) != ss))
    {
      stream->msg = "write failed";
      ret = get_errno ();
      goto failure;
    }

  if ((ret = fclose (tf)) /* || (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, int 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;
    }
  else
    {
      ret = 0;
    }

 fail:
  xd3_free_output (stream, buf);
  return ret;
}

/* Test integer overflow using the above routine. */
static int
test_decode_integer_overflow (xd3_stream *stream, int unused)
{
  return test_read_integer_error (stream, 0, "overflow in read_intger");
}

/* Test integer EOI using the above routine. */
static int
test_decode_integer_end_of_input (xd3_stream *stream, int unused)
{
  return test_read_integer_error (stream, 1, "end-of-input in read_integer");
}

/* Test that emit_integer/decode_integer/sizeof_integer/read_integer work on correct
 * inputs.  Tests powers of (2^7), plus or minus, up to the maximum value. */
#define TEST_ENCODE_DECODE_INTEGER(TYPE,ONE,MAX)                                \
  xd3_output *rbuf = NULL;                                                      \
  xd3_output *dbuf = NULL;                                                      \
  TYPE values[64];                                                              \
  int nvalues = 0;                                                              \
  int i, ret = 0;                                                               \
                                                                                \
  for (i = 0; i < (sizeof (TYPE) * 8); i += 7)                                  \
    {                                                                           \
      values[nvalues++] = (ONE << i) - ONE;                                     \
      values[nvalues++] = (ONE << i);                                           \
      values[nvalues++] = (ONE << i) + ONE;                                     \
    }                                                                           \
                                                                                \
  values[nvalues++] = MAX-ONE;                                                  \
  values[nvalues++] = MAX;                                                      \
                                                                                \
  rbuf = xd3_alloc_output (stream, rbuf);                                       \
  dbuf = xd3_alloc_output (stream, dbuf);                                       \
                                                                                \
  for (i = 0; i < nvalues; i += 1)                                              \
    {                                                                           \
      const uint8_t *max;                                                       \
      const uint8_t *inp;                                                       \
      TYPE val;                                                                 \
                                                                                \
      DOT ();                                                                   \
      rbuf->next = 0;                                                           \
                                                                                \
      if ((ret = xd3_emit_ ## TYPE (stream, & rbuf, values[i])) ||              \
          (ret = xd3_emit_ ## TYPE (stream, & dbuf, values[i])))                \
        {                                                                       \
          goto fail;                                                            \
        }                                                                       \
                                                                                \
      inp = rbuf->base;                                                         \
      max = rbuf->base + rbuf->next;                                            \
                                                                                \
      if (rbuf->next != xd3_sizeof_ ## TYPE (values[i]))                        \
        {                                                                       \
          ret = XD3_INTERNAL;                                                         \
          goto fail;                                                            \
        }                                                                       \
                                                                                \
      if ((ret = xd3_read_ ## TYPE (stream, & inp, max, & val)))                \
        {                                                                       \
          goto fail;                                                            \
        }                                                                       \
                                                                                \
      if (val != values[i])                                                     \
        {                                                                       \
          ret = XD3_INTERNAL;                                                         \
          goto fail;                                                            \
        }                                                                       \
                                                                                \
      DOT ();                                                                   \
    }                                                                           \
                                                                                \
  stream->next_in  = dbuf->base;                                                \
  stream->avail_in = dbuf->next;                                                \
                                                                                \
  for (i = 0; i < nvalues; i += 1)                                              \
    {                                                                           \
      TYPE val;                                                                 \
                                                                                \
      if ((ret = xd3_decode_ ## TYPE (stream, & val)))                          \
        {                                                                       \
          goto fail;                                                            \
        }                                                                       \
                                                                                \
      if (val != values[i])                                                     \
        {                                                                       \
          ret = XD3_INTERNAL;                                                         \
          goto fail;                                                            \
        }                                                                       \
    }                                                                           \
                                                                                \
  if (stream->avail_in != 0)                                                    \
    {                                                                           \
      ret = XD3_INTERNAL;                                                             \
      goto fail;                                                                \
    }                                                                           \
                                                                                \
 fail:                                                                          \
  xd3_free_output (stream, rbuf);                                               \
  xd3_free_output (stream, dbuf);                                               \
                                                                                \
  return ret

static int
test_encode_decode_uint32_t (xd3_stream *stream, int unused)
{
  TEST_ENCODE_DECODE_INTEGER(uint32_t,1U,UINT32_MAX);
}

static int
test_encode_decode_uint64_t (xd3_stream *stream, int unused)
{
  TEST_ENCODE_DECODE_INTEGER(uint64_t,1ULL,UINT64_MAX);
}

static int
test_usize_t_overflow (xd3_stream *stream, int unused)
{
  if (USIZE_T_OVERFLOW (0, 0)) { goto fail; }
  if (USIZE_T_OVERFLOW (USIZE_T_MAX, 0)) { goto fail; }
  if (USIZE_T_OVERFLOW (0, USIZE_T_MAX)) { goto fail; }
  if (USIZE_T_OVERFLOW (USIZE_T_MAX / 2, 0)) { goto fail; }
  if (USIZE_T_OVERFLOW (