/*
 * qsort_rig.c — pass-2 (GLM 5.3) differential / contract harness for
 * sys/libkern/qsort.c (DragonFlyBSD kqsort, Bentley-McIlroy).
 *
 * Compiles the AUDITED SOURCE VERBATIM (qsort_v.c, copied from
 * sys/libkern/qsort.c, sha256-pinned by build.sh) plus patched variants:
 *   kqsort_v   — verbatim sys/libkern/qsort.c              (bq_kqsort_v)
 *   kqsort_rv  — verbatim sys/libkern/qsort_r.c body       (kqsort_r_v)
 *   kqsort_f6  — types fix (size_t d/r2, size_t swapfunc n)
 *   kqsort_f67 — types fix + es==0 guard
 *
 * Modes:
 *   selftest                     rig sanity
 *   fuzz <iters> <seed>          randomized differential vs libc qsort:
 *                                byte-exact output, canaries, comparator
 *                                arg bounds/alignment, comparison-count cap
 *   fuzz_lie <iters> <seed>      adversarial/inconsistent comparators;
 *                                memory-safety assertions only
 *   truncate                     >=2.3GiB-partition ptrdiff->int truncation
 *                                mis-sort demo (A/B verbatim vs f6) + small
 *                                control (no truncation at small n)
 *   med3_oob                     >=16GiB array: med3 d=(n/8)*es int overflow
 *                                hands OOB pointers to the comparator
 *   es0 hang                     es==0, n>=7: non-termination proof
 *   es0 contrast                 es==0 with n<=6 and n>=7 on the guarded
 *                                variant f67 (returns immediately)
 *   es0 access                   es==0, n==7: the n==0 do-while-once in
 *                                swapcode performs an 8-byte self-swap at
 *                                base (build the rig with -fsanitize=address)
 *
 * Exit codes: 0 ok; 4 assertion failure; 3 med3-OOB confirmed (verdict);
 * 7 es0-hang confirmed (verdict); 9 truncate mis-sort confirmed (verdict).
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdarg.h>
#include <time.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <signal.h>

#ifndef MAP_NORESERVE		/* DragonFly does not have it */
#define MAP_NORESERVE 0
#endif

/* ------------------------------------------------------------------ */
/* variants (built by build.sh from the verbatim audited source)       */
void bq_kqsort_v(void *, size_t, size_t, int (*)(const void *, const void *));
void bq_kqsort_f6(void *, size_t, size_t, int (*)(const void *, const void *));
void bq_kqsort_f67(void *, size_t, size_t, int (*)(const void *, const void *));
void bq_kqsort_f7(void *, size_t, size_t, int (*)(const void *, const void *));
void bq_kqsort_rv(void *, size_t, size_t, void *,
    int (*)(void *, const void *, const void *));

/* ------------------------------------------------------------------ */
/* deterministic PRNG (xorshift64*) — identical results host/guest     */
static uint64_t prng_s;
static void prng_seed(uint64_t s) { prng_s = s ? s : 0x9e3779b97f4a7c15ULL; }
static uint64_t prng(void)
{
	prng_s ^= prng_s << 13; prng_s ^= prng_s >> 7; prng_s ^= prng_s << 17;
	return prng_s * 0x2545F4914F6CDD1DULL;
}
static uint64_t rnd_below(uint64_t n) { return n ? prng() % n : 0; }

/* ------------------------------------------------------------------ */
/* instrumentation: comparator arg bounds / alignment / call counting  */
static const unsigned char *g_base;
static size_t g_n, g_es;
static unsigned long g_calls, g_oob_args, g_unaligned;
static const void *g_oob_x, *g_oob_y;
static int g_mode;		/* 0 real(memcmp) 1 zero-no-deref 2 lie-family */
static int g_lie;		/* which lying comparator */
static void *g_thunk_expect;
static unsigned long g_exit_after;	/* comparator-call watchdog */
static int g_exit_code;
static const char *g_exit_msg;
static int g_trace;			/* print comparator arg trace (ring of 64) */
static int g_oob_is_success;		/* truncate mode: OOB args = verdict */
static long long g_tr_x[64], g_tr_y[64];
static unsigned g_tr_n, g_tr_total;

static void fatal(int code, const char *fmt, ...)
{
	va_list ap; va_start(ap, fmt);
	vfprintf(stderr, fmt, ap); va_end(ap);
	fprintf(stderr, "\n");
	exit(code);
}

static void set_exit_after(unsigned long n, int code, const char *msg)
{
	g_exit_after = n; g_exit_code = code; g_exit_msg = msg;
}

static int args_bad(const void *x, const void *y)
{
	const unsigned char *lo = g_base, *hi = g_base + g_n * g_es;
	int bad = 0;
	if ((const unsigned char *)x < lo || (const unsigned char *)x + g_es > hi) bad = 1;
	if ((const unsigned char *)y < lo || (const unsigned char *)y + g_es > hi) bad = 1;
	if (bad) { g_oob_args++; if (!g_oob_x) { g_oob_x = x; g_oob_y = y; } }
	else if (g_es && (((const unsigned char *)x - lo) % g_es ||
	    ((const unsigned char *)y - lo) % g_es)) g_unaligned++;
	return bad;
}

static int real_cmp(const void *x, const void *y)
{
	return memcmp(x, y, g_es ? g_es : 1);
}

static int lie_cmp(const void *x, const void *y)
{
	switch (g_lie) {
	case 0:	/* deterministic pointer-hash noise */
		return (int)(((uintptr_t)x * 0x9e3779b1u ^ (uintptr_t)y * 0x85ebca6bu) % 7u) - 3;
	case 1: return 1;	/* always greater */
	case 2: return -1;	/* always less */
	case 3: return 0;	/* everything equal */
	case 4:			/* antisymmetric, intransitive, never 0 */
		return (uintptr_t)x < (uintptr_t)y ? 1 : -1;
	case 5:			/* prng noise */
		return (int)(prng() % 7) - 3;
	}
	return 0;
}

static void trace_dump(void);	/* fwd */

static int rig_cmp(const void *x, const void *y)
{
	g_calls++;
	if (g_trace) {
		g_tr_x[g_tr_n] = (long long)((const char *)x - (const char *)g_base);
		g_tr_y[g_tr_n] = (long long)((const char *)y - (const char *)g_base);
		g_tr_n = (g_tr_n + 1) & 63;
		g_tr_total++;
	}
	if (g_exit_after && g_calls >= g_exit_after) {
		printf("%s (calls=%lu)\n", g_exit_msg ? g_exit_msg : "watchdog", g_calls);
		fflush(stdout);
		_exit(g_exit_code);
	}
	if (g_base && args_bad(x, y)) {
		if (g_mode == 1) {
			/* med3 demo: stop BEFORE any deref of the wild pointer */
			fprintf(stderr, "OOB COMPARATOR ARGS CONFIRMED: x=%p (x-base=%lld) "
			    "y=%p (y-base=%lld) base=%p n*es=%llu\n",
			    x, (long long)((const char *)x - (const char *)g_base),
			    y, (long long)((const char *)y - (const char *)g_base),
			    g_base, (unsigned long long)(g_n * g_es));
			_exit(3);
		}
		if (g_oob_is_success) {
			printf("TRUNCATION OOB CONFIRMED: comparator called with "
			    "args past the array end (x-base=%lld y-base=%lld, "
			    "n*es=%llu). Mechanism: byte distance 2,160,000,000 "
			    "truncates to int -2,134,967,296; 'if ((r = pd - pc) > es)' "
			    "promotes r (int) to size_t vs es -> huge -> guard PASSES; "
			    "'a = pn - r' lands %lld bytes PAST the array end and "
			    "'n = r / es' becomes ~2^64 -> next partition compares/"
			    "swaps wildly out of bounds.\n",
			    (long long)((const char *)x - (const char *)g_base),
			    (long long)((const char *)y - (const char *)g_base),
			    (unsigned long long)(g_n * g_es),
			    (long long)((const char *)x - (const char *)g_base) -
			    (long long)(g_n * g_es));
			fflush(stdout);
			_exit(9);
		}
		trace_dump();
		fatal(4, "comparator got OOB args: x=%p y=%p base=%p n*es=%zu "
		    "(x-base=%lld y-base=%lld)",
		    x, y, g_base, g_n * g_es,
		    (long long)((const char *)x - (const char *)g_base),
		    (long long)((const char *)y - (const char *)g_base));
	}
	if (g_mode == 0) return real_cmp(x, y);
	if (g_mode == 2) return lie_cmp(x, y);
	return 0;			/* mode 1: zero, no deref */
}

static void trace_dump(void)
{
	unsigned i, start;
	if (g_tr_total <= 64) {
		printf("all %u comparator calls (x-off,y-off):\n", g_tr_total);
		start = 0;
		for (i = 0; i < g_tr_total && i < 64; i++)
			printf("  [%02u] x=%lld y=%lld\n", i, g_tr_x[i], g_tr_y[i]);
	} else {
		printf("last 64 of %u comparator calls (x-off,y-off):\n", g_tr_total);
		start = g_tr_n;		/* oldest in ring */
		for (i = 0; i < 64; i++) {
			unsigned j = (start + i) & 63;
			printf("  [%02u] x=%lld y=%lld\n", g_tr_total - 64 + i,
			    g_tr_x[j], g_tr_y[j]);
		}
	}
}
static int rig_cmp_r(void *thunk, const void *x, const void *y)
{
	if (thunk != g_thunk_expect)
		fatal(4, "kqsort_r thunk corrupted: got %p want %p", thunk, g_thunk_expect);
	return rig_cmp(x, y);
}

static void arm(const void *base, size_t n, size_t es, int mode, int lie)
{
	g_base = base; g_n = n; g_es = es; g_mode = mode; g_lie = lie;
	g_calls = g_oob_args = g_unaligned = 0; g_oob_x = g_oob_y = NULL;
}

/* ------------------------------------------------------------------ */
/* contiguous large mappings: this sandbox rejects single anon mmaps
 * >= ~3GiB, so chain 1GiB MAP_FIXED chunks into one VA range.         */
#define CHUNK (1ULL << 30)
static void *xmap_contig(size_t bytes)
{
	size_t done = 0;
	char *p, *hint;
	if (bytes == 0) bytes = 1;
	p = mmap(NULL, bytes < CHUNK ? bytes : (size_t)CHUNK,
	    PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
	if (p == MAP_FAILED) return NULL;
	done = bytes < CHUNK ? bytes : (size_t)CHUNK;
	while (done < bytes) {
		size_t rem = bytes - done, now = rem < CHUNK ? rem : (size_t)CHUNK;
		hint = p + done;
		hint = mmap(hint, now, PROT_READ | PROT_WRITE,
		    MAP_ANONYMOUS | MAP_NORESERVE | MAP_FIXED, -1, 0);
		if (hint == MAP_FAILED) { munmap(p, done); return NULL; }
		done += now;
	}
	return p;
}

static double now_sec(void)
{
	struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
	return ts.tv_sec + ts.tv_nsec / 1e9;
}

static int arr_is_sorted(const unsigned char *a, size_t n, size_t es)
{
	size_t i;
	g_es = es;
	for (i = 1; i < n; i++)
		if (real_cmp(a + (i - 1) * es, a + i * es) > 0)
			return (int)i;	/* 1-based first violation index */
	return 0;
}

static const size_t ES_SET[] = { 1, 2, 3, 4, 5, 6, 7, 8, 12, 16, 24, 32, 40 };
#define ES_N (sizeof(ES_SET) / sizeof(ES_SET[0]))
#define CAN 32			/* canary bytes each side */

#define CANPAT(i) ((unsigned char)(0xC3 ^ ((i) * 41)))

static void fill_canary(unsigned char *p, size_t len, size_t phase)
{
	size_t i;
	for (i = 0; i < len; i++) p[i] = CANPAT(phase + i);
}

static int canary_ok(const unsigned char *p, size_t len, size_t phase)
{
	size_t i;
	for (i = 0; i < len; i++) if (p[i] != CANPAT(phase + i)) return 0;
	return 1;
}

static long canary_first_bad(const unsigned char *p, size_t len, size_t phase)
{
	size_t i;
	for (i = 0; i < len; i++) if (p[i] != CANPAT(phase + i)) return (long)i;
	return -1;
}

static unsigned long g_max_ratio_num = 0, g_max_ratio_den = 1;	/* worst cmp-count ratio */

static void check_cmp_count(size_t n, const char *tag)
{
	/* generous generous bound: 6*n*log2(n)+16n+64 comparisons */
	unsigned long long bound;
	double log2n = 1.0;
	size_t m = n;
	if (n < 2) return;
	while (m >>= 1) log2n += 1.0;
	bound = 6ULL * n * (unsigned long long)log2n + 16ULL * n + 64;
	if ((unsigned long long)g_calls > bound)
		fatal(4, "cmp-count blowup: %s n=%zu calls=%lu bound=%llu",
		    tag, n, g_calls, bound);
	if (6ULL * n * (unsigned long long)log2n) {
		unsigned long long num = g_calls, den = (unsigned long long)n * (unsigned long long)log2n;
		if (num * g_max_ratio_den > g_max_ratio_num * den) {
			g_max_ratio_num = (unsigned long)num; g_max_ratio_den = (unsigned long)den;
		}
	}
}

/* one differential fuzz iteration against libc qsort; also runs the
 * patched variants on fresh copies (no-regression) and the _r variant. */
static void fuzz_once(uint64_t iter, int use_lie)
{
	size_t es = ES_SET[rnd_below(ES_N)];
	size_t n = use_lie ? rnd_below(513) :
	    (rnd_below(5) == 0 ? rnd_below(64) : rnd_below(3001));
	size_t off = rnd_below(8);			/* base misalignment */
	size_t total = CAN + off + n * es + CAN;
	unsigned char *work = malloc(total ? total : 1);
	unsigned char *ref = malloc(n * es ? n * es : 1);
	unsigned char *cp = malloc(n * es ? n * es : 1);
	unsigned char *base;
	size_t i;
	if (!work || !ref || !cp) fatal(4, "oom");
	fill_canary(work, total, 0);
	for (i = 0; i < n * es; i++) work[CAN + off + i] = (unsigned char)prng();
	base = work + CAN + off;

	memcpy(ref, base, n * es);
	memcpy(cp, base, n * es);
	g_base = ref; g_n = n; g_es = es; g_mode = 0; g_lie = 0;
	g_calls = g_oob_args = g_unaligned = 0;
	qsort(ref, n, es, rig_cmp);			/* libc reference */

	arm(base, n, es, use_lie ? 2 : 0, (int)rnd_below(6));
	bq_kqsort_v(base, n, es, rig_cmp);
	if (!use_lie) {
		if (memcmp(base, ref, n * es))
			fatal(4, "DIFF iter=%llu n=%zu es=%zu: verbatim kqsort != libc reference",
			    (unsigned long long)iter, n, es);
		check_cmp_count(n, "verbatim");
	}
	if (g_oob_args) fatal(4, "iter=%llu n=%zu es=%zu: comparator got %lu OOB args "
	    "(x=%p y=%p)", (unsigned long long)iter, n, es, g_oob_args, g_oob_x, g_oob_y);
	if (g_unaligned) fatal(4, "iter=%llu: %lu unaligned comparator args",
	    (unsigned long long)iter, g_unaligned);
	if (!canary_ok(work, CAN + off, 0) || !canary_ok(work + CAN + off + n * es, CAN, CAN + off + n * es))
		fatal(4, "iter=%llu n=%zu es=%zu off=%zu: CANARY CORRUPT (write OOB) "
		    "head_ok=%d tail_ok=%d first_head_bad=%ld first_tail_bad=%ld",
		    (unsigned long long)iter, n, es, off,
		    canary_ok(work, CAN + off, 0),
		    canary_ok(work + CAN + off + n * es, CAN, CAN + off + n * es),
		    canary_first_bad(work, CAN + off, 0),
		    canary_first_bad(work + CAN + off + n * es, CAN, CAN + off + n * es));

	if (!use_lie) {
		/* patched f6 no-regression */
		memcpy(base, cp, n * es);
		arm(base, n, es, 0, 0);
		bq_kqsort_f6(base, n, es, rig_cmp);
		if (memcmp(base, ref, n * es))
			fatal(4, "DIFF iter=%llu: patched f6 != libc reference",
			    (unsigned long long)iter);
		if (g_oob_args) fatal(4, "iter=%llu: f6 OOB comparator args",
		    (unsigned long long)iter);
		/* guarded f67 no-regression */
		memcpy(base, cp, n * es);
		arm(base, n, es, 0, 0);
		bq_kqsort_f67(base, n, es, rig_cmp);
		if (memcmp(base, ref, n * es))
			fatal(4, "DIFF iter=%llu: patched f67 != libc reference",
			    (unsigned long long)iter);
		/* _r variant with thunk identity check */
		memcpy(base, cp, n * es);
		arm(base, n, es, 0, 0);
		{ void *th = (void *)(uintptr_t)0x5eedULL;
		  g_thunk_expect = th;
		  bq_kqsort_rv(base, n, es, th, rig_cmp_r); }
		if (memcmp(base, ref, n * es))
			fatal(4, "DIFF iter=%llu: kqsort_r != libc reference",
			    (unsigned long long)iter);
	}
	if (!canary_ok(work, CAN + off, 0) || !canary_ok(work + CAN + off + n * es, CAN, CAN + off + n * es))
		fatal(4, "iter=%llu: CANARY CORRUPT after variants",
		    (unsigned long long)iter);
	free(work); free(ref); free(cp);
}

/* ------------------------------------------------------------------ */
/* truncate demo: n=720,000,000 x es=8 (5.76 GiB).
 * Layout: A=[0,270M) ascending distinct smalls; M=[270M,720M) constant
 * medium. med3 picks pivot=medium (pl-samples small, pm/pn-samples medium;
 * NB under memcmp/LE the 'smalls' compare GREATER than the medium constant,
 * which only changes which loop marches). Actual measured dynamics on the
 * guest (see VERDICT.md trace): pivot swap; first while stops immediately;
 * second while marches pc over all 720M elements with 449,999,999 equal
 * (r==0) swaps -> pd ends at element 270,000,000, pc at 0 -> pd-pc =
 * 2,160,000,000 bytes -> (int)r = -2,134,967,296 -> 'if ((r = pd - pc) >
 * es)' promotes r to size_t (es is size_t) -> 1.8e19 > 8 -> guard PASSES
 * -> 'a = pn - r' = array_end + 2,134,967,296, 'n = r/es' = (size_t)
 * -266,870,912 -> goto loop -> med3/partition hand the comparator args
 * exactly a and a+d, both far out of bounds (a dereferencing comparator =
 * OOB read; the following swap(a, pm) = OOB write). Patched f6 (size_t
 * r2/d, size_t swapfunc n) sorts the same input correctly.             */
#define TR_N 720000000ULL
#define TR_A 270000000ULL
#define TR_MED 0x100000000ULL

static void trunc_fill(uint64_t *k)
{
	uint64_t i;
	for (i = 0; i < TR_N; i++)
		k[i] = (i < TR_A) ? i + 1 : TR_MED;	/* A distinct, M medium */
}

static int trunc_run(int fixed)
{
	size_t bytes = (size_t)(TR_N * 8);
	uint64_t *k = xmap_contig(bytes + 4096);
	double t0, t1;
	int v;
	if (k == NULL) { perror("xmap_contig"); exit(4); }
	g_oob_is_success = !fixed;
	trunc_fill(k);
	arm(k, TR_N, 8, 0, 0);
	t0 = now_sec();
	if (fixed) bq_kqsort_f6(k, TR_N, 8, rig_cmp);
	else       bq_kqsort_v(k, TR_N, 8, rig_cmp);
	t1 = now_sec();
	printf("%s: n=%llu es=8 bytes=%zu cmp_calls=%lu time=%.1fs\n",
	    fixed ? "PATCHED(f6)" : "VERBATIM", (unsigned long long)TR_N,
	    bytes, g_calls, t1 - t0);
	if (g_oob_args) printf("  !! %lu OOB comparator args (x=%p y=%p)\n",
	    g_oob_args, g_oob_x, g_oob_y);
	if (fixed) {
		v = arr_is_sorted((unsigned char *)k, TR_N, 8);
		printf("  patched: array %s\n", v ? "NOT SORTED (BAD)" : "IS SORTED");
		munmap(k, bytes + 4096);
		return v ? 0 : 1;	/* 1 => sorted (good) */
	}
	munmap(k, bytes + 4096);
	return 1;			/* verbatim: OOB exit(9) is the verdict */
}

static int trunc_small(void)
{
	/* same shape at n=720,000: gaps far below INT_MAX -> verbatim sorts
	 * fine (and matches libc): proves the failure is a size threshold. */
	size_t n = 720000, a = n / 8 * 3, i, bytes = n * 8;
	uint64_t *k = malloc(bytes), *ref = malloc(bytes);
	if (!k || !ref) fatal(4, "oom");
	for (i = 0; i < n; i++) k[i] = (i < a) ? i + 1 : TR_MED;
	memcpy(ref, k, bytes);
	arm(k, n, 8, 0, 0);
	bq_kqsort_v(k, n, 8, rig_cmp);
	g_base = (const unsigned char *)ref; g_n = n; g_es = 8; g_mode = 0;
	qsort(ref, n, 8, rig_cmp);
	printf("small control n=%zu: verbatim %s libc-reference, calls=%lu\n",
	    n, memcmp(k, ref, bytes) ? "!= (BAD)" : "==", g_calls);
	{ int s = memcmp(k, ref, bytes) != 0; free(k); free(ref); return s; }
}

/* ------------------------------------------------------------------ */
/* med3_oob demo: es=1, n=17,200,000,000 (16.0 GiB) -> d=(n/8)=2.15e9
 * overflows int -> med3(pl, pl+d, pl+2d) feeds the comparator pointers
 * ~2GiB / ~4GiB BELOW the array. Comparator bounds-checks args BEFORE
 * any deref and reports; mode-1 comparator never derefs array data.   */
#define MO_N 17200000000ULL

static void med3_run(int fixed)
{
	size_t bytes = (size_t)MO_N;
	unsigned char *k = xmap_contig(bytes);
	if (k == NULL) { perror("xmap_contig"); exit(4); }
	printf("%s: n=%llu es=1 bytes=%zu (predicted d=(n/8)*es=%llu -> int d=%d)\n",
	    fixed ? "PATCHED(f6)" : "VERBATIM", (unsigned long long)MO_N, bytes,
	    (unsigned long long)(MO_N / 8), (int)(MO_N / 8));
	arm(k, MO_N, 1, 1, 0);			/* mode 1: bounds-check, no deref */
	if (fixed)
		set_exit_after(1000, 0,
		    "PATCHED med3: 0 OOB comparator args in first 1000 calls "
		    "(aborting before full 17GiB sort)");
	else
		set_exit_after(0, 0, NULL);
	if (fixed)	bq_kqsort_f6(k, (size_t)MO_N, 1, rig_cmp);
	else		bq_kqsort_v(k, (size_t)MO_N, 1, rig_cmp);
	printf("%s: RETURNED after %lu calls (no OOB args?)\n",
	    fixed ? "PATCHED(f6)" : "VERBATIM", g_calls);
	munmap(k, bytes);
}

/* ------------------------------------------------------------------ */
static int es0_hang(void)
{
	/* es==0, n=64: pivot swap, then partition loop never advances
	 * pb (pb += es == +0) -> comparator called forever. rig_cmp exits 7
	 * once it sees 5,000,000 calls (a correct 64-elem sort needs <3000). */
	static unsigned char buf[64] __attribute__((aligned(8)));
	arm(NULL, 0, 0, 1, 0);			/* no bounds check; return 0 */
	set_exit_after(5000000UL, 7,
	    "ES0 HANG CONFIRMED: comparator called 5,000,000 times with es=0 "
	    "(pb frozen at +0; a correct 64-element sort needs <3000)");
	bq_kqsort_v(buf, 64, 0, rig_cmp);
	printf("es0 hang: RETURNED after %lu calls (unexpected)\n", g_calls);
	return 0;
}

static int es0_contrast(void)
{
	static unsigned char buf[64] __attribute__((aligned(8)));
	size_t i; int rc = 0;
	for (i = 0; i <= 8; i++) {
		arm(buf, i, 0, 1, 0);
		bq_kqsort_f7(buf, i, 0, rig_cmp);	/* guard-only fix: must not hang */
		printf("guarded f7 (es==0 guard only) es=0 n=%zu: returned, cmp_calls=%lu\n", i, g_calls);
	}
	for (i = 0; i <= 8; i++) {
		arm(buf, i, 0, 1, 0);
		bq_kqsort_f67(buf, i, 0, rig_cmp);	/* guard + types fix: must not hang */
		printf("guarded f67 es=0 n=%zu: returned, cmp_calls=%lu\n", i, g_calls);
	}
	for (i = 0; i <= 6; i++) {
		arm(buf, i, 0, 1, 0);
		bq_kqsort_v(buf, i, 0, rig_cmp);
		printf("verbatim  es=0 n=%zu: returned, cmp_calls=%lu\n", i, g_calls);
	}
	printf("verbatim  es=0 n=7: expected to hang (see 'es0 hang' mode)\n");
	return rc;
}

static int es0_segv(int fixed)	/* 0=verbatim 1=f67 2=f7 */
{
	/* es==0, n==7: first access in the sort is swap(a, pm==a) (qsort.c:132)
	 * -> swapfunc(a, a, 0, swaptype=1) -> swapcode(long, ..., n=0): the
	 * do-while runs its body ONCE -> an 8-byte load at base. base points
	 * into a PROT_NONE page: the array has ZERO length, so ANY access is
	 * out of contract; the load faults with SIGSEGV. Guarded f67 must
	 * return cleanly without touching memory. */
	pid_t pid = fork();
	int st;
	if (pid == 0) {
		void *guard = mmap(NULL, 4096, PROT_NONE,
		    MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
		unsigned char *base;
		if (guard == MAP_FAILED) _exit(9);
		base = (unsigned char *)guard + 16;	/* 8-aligned */
		arm(NULL, 0, 0, 1, 0);
		if (fixed == 1) bq_kqsort_f67(base, 7, 0, rig_cmp);
		else if (fixed == 2) bq_kqsort_f7(base, 7, 0, rig_cmp);
		else       bq_kqsort_v(base, 7, 0, rig_cmp);
		_exit(0);		/* reached only if no fault */
	}
	waitpid(pid, &st, 0);
	if (WIFSIGNALED(st) && WTERMSIG(st) == SIGSEGV) {
		printf("%s: SIGSEGV inside kqsort with es=0 n=7 "
		    "(8-byte self-swap load at base of a zero-length array)\n",
		    fixed ? "es0_segv FIXED" : "ES0 ACCESS CONFIRMED (verbatim)");
		return 1;
	}
	printf("es0_segv(%d): child exited st=%d (no fault)\n", fixed, st);
	return fixed ? 1 : 0;
}

/* ------------------------------------------------------------------ */
int main(int argc, char **argv)
{
	const char *mode = argc > 1 ? argv[1] : "selftest";
	unsigned long it = argc > 2 ? strtoul(argv[2], NULL, 0) : 20000;
	uint64_t seed = argc > 3 ? strtoull(argv[3], NULL, 0) : 0xDF5696ULL;
	uint64_t i;
	int bad = 0;

	if (!strcmp(mode, "selftest")) {
		unsigned char t[] = { 3, 1, 2 };
		g_es = 1;
		printf("selftest: is_sorted(unsorted)=%d (want 1) ",
		    arr_is_sorted(t, 3, 1));
		t[1] = 1; t[2] = 2; t[0] = 0;
		printf("is_sorted(sorted)=%d (want 0)\n", arr_is_sorted(t, 3, 1));
		return 0;
	}
	if (!strcmp(mode, "fuzz")) {
		prng_seed(seed);
		for (i = 0; i < it; i++) fuzz_once(i, 0);
		printf("FUZZ OK: %lu iterations (verbatim+f6+f67+kqsort_r vs libc), "
		    "0 diff, 0 canary corrupt, 0 OOB/unaligned comparator args\n", it);
		printf("worst cmp-count ratio ~ %lu/%lu = %.2f x n*log2(n)\n",
		    g_max_ratio_num, g_max_ratio_den,
		    g_max_ratio_den ? (double)g_max_ratio_num / g_max_ratio_den : 0.0);
		return 0;
	}
	if (!strcmp(mode, "fuzz_lie")) {
		prng_seed(seed ^ 0xBADULL);
		for (i = 0; i < it; i++) fuzz_once(i, 1);
		printf("FUZZ_LIE OK: %lu iterations x 6 inconsistent comparators "
		    "(rng/always+1/always-1/all-equal/antisym-intrans/prng): "
		    "0 canary corrupt, 0 OOB comparator args "
		    "(partition+insertion stay in-bounds under any comparator)\n", it);
		return 0;
	}
	if (!strcmp(mode, "truncate")) {
		int s = trunc_small(); if (s) return 4;
		{	pid_t pid = fork();
			int st = 0, okv;
			if (pid == 0) { trunc_run(0); _exit(0); }
			waitpid(pid, &st, 0);
			okv = WIFEXITED(st) && WEXITSTATUS(st) == 9;
			printf("VERBATIM run: %s\n", okv ?
			    "comparator received OOB args (exit 9)" :
			    "unexpected child status");
			{	int f = trunc_run(1);
				printf("truncate verdict: verbatim OOB=%d patched sorted=%d\n",
				    okv, f == 1);
				if (okv && f == 1) {
					printf("TRUNCATION CONFIRMED (OOB partition state on "
					    "verbatim; correct sort on patched)\n");
					return 9;
				}
				return 4; }
		}
	}
	if (!strcmp(mode, "truncate_trace")) {
		int s = trunc_small(); if (s) return 4;
		g_trace = 1;
		{ int v = trunc_run(0);
		  trace_dump();
		  (void)v; }
		return 4;
	}
	if (!strcmp(mode, "med3_oob")) {
		med3_run(0);
		/* not reached for verbatim: rig_cmp exits 3 on OOB args */
		return 4;
	}
	if (!strcmp(mode, "med3_oob_fixed")) {
		med3_run(1);
		return 4;
	}
	if (!strcmp(mode, "es0_hang"))		return es0_hang();
	if (!strcmp(mode, "es0_contrast"))	return es0_contrast();
	if (!strcmp(mode, "es0_segv"))		return es0_segv(0) ? 0 : 4;
	if (!strcmp(mode, "es0_segv_fixed"))	return es0_segv(1) ? 0 : 4;
	if (!strcmp(mode, "es0_segv_f7"))	return es0_segv(2) ? 0 : 4;
	fprintf(stderr, "unknown mode %s\n", mode);
	return 64;
	(void)bad;
}