xdelta3-test.h

This program is free software you can redistribute it and/or modify it under the terms of the GNU G

  for (i = 0; i < encoded_size*8; i += 1)
    {
      /* Single bit error. */
      encoded[i/8] ^= 1 << (i%8);

      if ((ret = test_decompress_text (stream, encoded, encoded_size, sizeof (test_text))) == 0)
	{
	  non_failures += 1;
	  /*DP(RINT "%u[%u] non-failure %u\n", i/8, i%8, non_failures);*/
	  TEST_FAILURES();
	}
      else
	{
	  /*DP(RINT "%u[%u] failure: %s\n", i/8, i%8, stream->msg);*/
	}

      /* decompress_text returns EIO when the final memcmp() fails, but that
       * should never happen with checksumming on. */
      if (cksum && ret == EIO)
	{
	  /*DP(RINT "%u[%u] cksum mismatch\n", i/8, i%8);*/
	  stream->msg = "checksum mismatch";
	  return XD3_INTERNAL;
	}

      /* Undo single bit error. */
      encoded[i/8] ^= 1 << (i%8);
    }

  /* Test correct input again */
  if ((ret = test_decompress_text (stream, encoded, encoded_size, 1)))
    {
      /*stream->msg = "without error: decode failure";*/
      return ret;
    }

  /* Check expected non-failures */
  if (non_failures != expected_non_failures)
    {
      DP(RINT "non-failures %u; expected %u", non_failures, expected_non_failures);
      stream->msg = "incorrect";
      return XD3_INTERNAL;
    }

  DOT ();

  return 0;
}

/******************************************************************************************
 Secondary compression tests
 ******************************************************************************************/

#if SECONDARY_ANY
typedef int (*sec_dist_func) (xd3_stream *stream, xd3_output *data);

static int sec_dist_func1 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func2 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func3 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func4 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func5 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func6 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func7 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func8 (xd3_stream *stream, xd3_output *data);
static int sec_dist_func9 (xd3_stream *stream, xd3_output *data);

static sec_dist_func sec_dists[] =
{
  sec_dist_func1,
  sec_dist_func2,
  sec_dist_func3,
  sec_dist_func4,
  sec_dist_func5,
  sec_dist_func6,
  sec_dist_func7,
  sec_dist_func8,
  sec_dist_func9,
};

/* Test ditsribution: 100 bytes of the same character (13). */
static int
sec_dist_func1 (xd3_stream *stream, xd3_output *data)
{
  int i, ret;
  for (i = 0; i < 100; i += 1)
    {
      if ((ret = xd3_emit_byte (stream, & data, 13))) { return ret; }
    }
  return 0;
}

/* Test ditsribution: uniform covering half the alphabet. */
static int
sec_dist_func2 (xd3_stream *stream, xd3_output *data)
{
  int i, ret;
  for (i = 0; i < ALPHABET_SIZE; i += 1)
    {
      if ((ret = xd3_emit_byte (stream, & data, i%(ALPHABET_SIZE/2)))) { return ret; }
    }
  return 0;
}

/* Test ditsribution: uniform covering the entire alphabet. */
static int
sec_dist_func3 (xd3_stream *stream, xd3_output *data)
{
  int i, ret;
  for (i = 0; i < ALPHABET_SIZE; i += 1)
    {
      if ((ret = xd3_emit_byte (stream, & data, i%ALPHABET_SIZE))) { return ret; }
    }
  return 0;
}

/* Test distribution: An exponential distribution covering half the alphabet */
static int
sec_dist_func4 (xd3_stream *stream, xd3_output *data)
{
  int i, ret, x;
  for (i = 0; i < ALPHABET_SIZE*20; i += 1)
    {
      x = test_exponential_dist (10, ALPHABET_SIZE/2);
      if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
    }
  return 0;
}

/* Test distribution: An exponential distribution covering the entire alphabet */
static int
sec_dist_func5 (xd3_stream *stream, xd3_output *data)
{
  int i, ret, x;
  for (i = 0; i < ALPHABET_SIZE*20; i += 1)
    {
      x = test_exponential_dist (10, ALPHABET_SIZE-1);
      if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
    }
  return 0;
}

/* Test distribution: An uniform random distribution covering half the alphabet */
static int
sec_dist_func6 (xd3_stream *stream, xd3_output *data)
{
  int i, ret, x;
  for (i = 0; i < ALPHABET_SIZE*20; i += 1)
    {
      x = rand () % (ALPHABET_SIZE/2);
      if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
    }
  return 0;
}

/* Test distribution: An uniform random distribution covering the entire alphabet */
static int
sec_dist_func7 (xd3_stream *stream, xd3_output *data)
{
  int i, ret, x;
  for (i = 0; i < ALPHABET_SIZE*20; i += 1)
    {
      x = rand () % ALPHABET_SIZE;
      if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
    }
  return 0;
}

/* Test distribution: A small number of frequent characters, difficult to divide into many
 * groups */
static int
sec_dist_func8 (xd3_stream *stream, xd3_output *data)
{
  int i, ret;
  for (i = 0; i < ALPHABET_SIZE*5; i += 1)
    {
      if ((ret = xd3_emit_byte (stream, & data, 0))) { return ret; }
      if ((ret = xd3_emit_byte (stream, & data, 64))) { return ret; }
      if ((ret = xd3_emit_byte (stream, & data, 128))) { return ret; }
      if ((ret = xd3_emit_byte (stream, & data, 255))) { return ret; }
    }
  return 0;
}

/* Test distribution: One that causes many FGK block promotions (found a bug) */
static int
sec_dist_func9 (xd3_stream *stream, xd3_output *data)
{
  int i, ret;

  int ramp   = 0;
  int rcount = 0;
  int prom   = 0;
  int pcount = 0;

  /* 200 was long enough to trigger it--only when stricter checking that counted all
   * blocks was turned on, but it seems I deleted this code. (missing fgk_free_block on
   * line 398). */
  for (i = 0; i < ALPHABET_SIZE*200; i += 1)
    {
    repeat:
      if (ramp < ALPHABET_SIZE)
	{
	  /* Initially Nth symbol has (N+1) frequency */
	  if (rcount <= ramp)
	    {
	      rcount += 1;
	      if ((ret = xd3_emit_byte (stream, & data, ramp))) { return ret; }
	      continue;
	    }

	  ramp   += 1;
	  rcount  = 0;
	  goto repeat;
	}

      /* Thereafter, promote least freq to max freq */
      if (pcount == ALPHABET_SIZE)
	{
	  pcount = 0;
	  prom   = (prom + 1) % ALPHABET_SIZE;
	}

      pcount += 1;
      if ((ret = xd3_emit_byte (stream, & data, prom))) { return ret; }
    }

  return 0;
}

static int
test_secondary_decode (xd3_stream         *stream,
		       const xd3_sec_type *sec,
		       usize_t              input_size,
		       usize_t              compress_size,
		       const uint8_t      *dec_input,
		       const uint8_t      *dec_correct,
		       uint8_t            *dec_output)
{
  int ret;
  xd3_sec_stream *dec_stream;
  const uint8_t *dec_input_used, *dec_input_end;
  uint8_t *dec_output_used, *dec_output_end;

  if ((dec_stream = sec->alloc (stream)) == NULL) { return ENOMEM; }

  sec->init (dec_stream);

  dec_input_used = dec_input;
  dec_input_end  = dec_input + compress_size;

  dec_output_used = dec_output;
  dec_output_end  = dec_output + input_size;

  if ((ret = sec->decode (stream, dec_stream,
			  & dec_input_used, dec_input_end,
			  & dec_output_used, dec_output_end)))
    {
      goto fail;
    }

  if (dec_input_used != dec_input_end)
    {
      stream->msg = "unused input";
      ret = XD3_INTERNAL;
      goto fail;
    }

  if (dec_output_used != dec_output_end)
    {
      stream->msg = "unfinished output";
      ret = XD3_INTERNAL;
      goto fail;
    }

  if (memcmp (dec_output, dec_correct, input_size) != 0)
    {
      stream->msg = "incorrect output";
      ret = XD3_INTERNAL;
      goto fail;
    }

 fail:
  sec->destroy (stream, dec_stream);
  return ret;
}

static int
test_secondary (xd3_stream *stream, const xd3_sec_type *sec, int groups)
{
  int test_i, ret;
  xd3_output *in_head, *out_head, *p;
  usize_t p_off, input_size, compress_size;
  uint8_t *dec_input = NULL, *dec_output = NULL, *dec_correct = NULL;
  xd3_sec_stream *enc_stream;
  xd3_sec_cfg cfg;

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

  cfg.inefficient = 1;

  for (cfg.ngroups = 1; cfg.ngroups <= groups; cfg.ngroups += 1)
    {
      DP(RINT "\n...");
      for (test_i = 0; test_i < SIZEOF_ARRAY (sec_dists); test_i += 1)
	{
	  srand (0x84687674);

	  in_head  = xd3_alloc_output (stream, NULL);
	  out_head = xd3_alloc_output (stream, NULL);
	  enc_stream = sec->alloc (stream);
	  dec_input = NULL;
	  dec_output = NULL;
	  dec_correct = NULL;

	  if (in_head == NULL || out_head == NULL || enc_stream == NULL) { goto nomem; }

	  if ((ret = sec_dists[test_i] (stream, in_head))) { goto fail; }

	  sec->init (enc_stream);

	  /* Encode data */
	  if ((ret = sec->encode (stream, enc_stream, in_head, out_head, & cfg)))
	    {
	      DP(RINT "test %u: encode: %s", test_i, stream->msg);
	      goto fail;
	    }

	  /* Calculate sizes, allocate contiguous arrays for decoding */
	  input_size    = xd3_sizeof_output (in_head);
	  compress_size = xd3_sizeof_output (out_head);

	  DP(RINT "%.3f", 8.0 * (double) compress_size / (double) input_size);

	  if ((dec_input   = xd3_alloc (stream, compress_size, 1)) == NULL ||
	      (dec_output  = xd3_alloc (stream, input_size, 1)) == NULL ||
	      (dec_correct = xd3_alloc (stream, input_size, 1)) == NULL) { goto nomem; }

	  /* Fill the compressed data array */
	  for (p_off = 0, p = out_head; p != NULL; p_off += p->next, p = p->next_page)
	    {
	      memcpy (dec_input + p_off, p->base, p->next);
	    }

	  CHECK(p_off == compress_size);

	  /* Fill the input data array */
	  for (p_off = 0, p = in_head; p != NULL; p_off += p->next, p = p->next_page)
	    {
	      memcpy (dec_correct + p_off, p->base, p->next);
	    }

	  CHECK(p_off == input_size);

	  if ((ret = test_secondary_decode (stream, sec, input_size, compress_size, dec_input, dec_correct, dec_output)))
	    {
	      DP(RINT "test %u: decode: %s", test_i, stream->msg);
	      goto fail;
	    }

	  /* Single-bit error test, only cover the first 10 bytes.  Some non-failures are
	   * expected in the Huffman case: Changing the clclen array, for example, may not
	   * harm the decoding.  Really looking for faults here. */
	  {
	    int i;
	    int bytes = min (compress_size, 10U);
	    for (i = 0; i < bytes * 8; i += 1)
	      {
		dec_input[i/8] ^= 1 << (i%8);

		if ((ret = test_secondary_decode (stream, sec, input_size, compress_size, dec_input, dec_correct, dec_output)) == 0)
		  {
		    /*DP(RINT "test %u: decode single-bit [%u/%u] error non-failure", test_i, i/8, i%8);*/
		  }

		dec_input[i/8] ^= 1 << (i%8);

		if ((i % (2*bytes)) == (2*bytes)-1)
		  {
		    DOT ();
		  }
	      }
	    ret = 0;
	  }

	  if (0) { nomem: ret = ENOMEM; }

	fail:
	  sec->destroy (stream, enc_stream);
	  xd3_free_output (stream, in_head);
	  xd3_free_output (stream, out_head);
	  xd3_free (stream, dec_input);
	  xd3_free (stream, dec_output);
	  xd3_free (stream, dec_correct);

	  if (ret != 0) { return ret; }
	}
    }

  return 0;
}

IF_FGK (static int test_secondary_fgk  (xd3_stream *stream, int gp) { return test_secondary (stream, & fgk_sec_type, gp); })
IF_DJW (static int test_secondary_huff (xd3_stream *stream, int gp) { return test_secondary (stream, & djw_sec_type, gp); })
#endif

/******************************************************************************************
 TEST INSTRUCTION TABLE
 ******************************************************************************************/

/* Test that xd3_choose_instruction() does the right thing for its code table. */
static int
test_choose_instruction (xd3_stream *stream, int ignore)
{
  int i;

  stream->code_table = (*stream->code_table_func) ();

  for (i = 0; i < 256; i += 1)
    {
      const xd3_dinst *d = stream->code_table + i;
      xd3_rinst prev, inst;

      CHECK(d->type1 > 0);

      memset (& prev, 0, sizeof (prev));
      memset (& inst, 0, sizeof (inst));

      if (d->type2 == 0)
	{
	  inst.type = d->type1;