#include <stdio.h>
#include <stdlib.h>

char *array;
char *array_end;
size_t member_size;

int
compare (const void *a1, const void *b1)
{
  const char *a = a1;
  const char *b = b1;

  if (! (array <= a && a < array_end
	 && array <= b && b < array_end))
    {
      puts ("compare arguments not inside of the array");
      exit (EXIT_FAILURE);
    }
  int ret = b[0] - a[0];
  if (ret)
    return ret;
  if (member_size > 1)
    return b[1] - a[1];
  return 0;
}

int
test (size_t nmemb, size_t size)
{
  array = malloc (nmemb * size);
  if (array == NULL)
    {
      printf ("%zd x %zd: no memory", nmemb, size);
      return 1;
    }

  array_end = array + nmemb * size;
  member_size = size;

  char *p;
  size_t i;
  size_t bias = random ();
  for (i = 0, p = array; i < nmemb; i++, p += size)
    {
      p[0] = (char) (i + bias);
      if (size > 1)
	p[1] = (char) ((i + bias) >> 8);
    }

  qsort (array, nmemb, size, compare);

  for (i = 0, p = array; i < nmemb - 1; i++, p += size)
    {
      if (p[0] < p[size]
	  || (size > 1 && p[0] == p[size] && p[1] < p[size + 1]))
	{
	  printf ("%zd x %zd: failure at offset %zd\n", nmemb,
		  size, i);
	  free (array);
	  return 1;
	}
    }

  free (array);
  return 0;
}

int
main (int argc, char **argv)
{
  int ret = 0;
  if (argc >= 3)
    ret |= test (atoi (argv[1]), atoi (argv[2]));
  else
    {
      ret |= test (10000, 1);
      ret |= test (200000, 2);
      ret |= test (2000000, 3);
      ret |= test (2132310, 4);
      ret |= test (1202730, 7);
      ret |= test (1184710, 8);
      ret |= test (272710, 12);
      ret |= test (14170, 32);
      ret |= test (4170, 320);
    }

  return ret;
}