/*
 * DF-5714 / neg-evidence-strcmp pass-2 differential harness (GLM 5.3).
 *
 * Targets, compiled VERBATIM from the guest's /usr/src/sys/libkern (see
 * build.sh for the identity pin):
 *   k_ffs    <- sys/libkern/ffs.c    (-Dffs=k_ffs, nothing stripped)
 *   k_ffsl   <- sys/libkern/ffsl.c   (-Dffsl=k_ffsl, nothing stripped)
 *   k_strcmp <- sys/libkern/strcmp.c (-Dstrcmp=k_strcmp, only the kernel-only
 *                                      #include <sys/libkern.h> dropped)
 *
 * Tests:
 *   T1  ffs   FULL domain sweep: every uint32 value, kernel body vs
 *              __builtin_ffs == the LIVE kernel semantics (cpufunc.h:269-273
 *              static __inline ffs(){ return __builtin_ffs(mask); }).
 *   T2  ffsl  edge+exhaustive-small+random-64bit vs __builtin_ffsl (context
 *              for the family; ffsl.c is equally dead per conf/files).
 *   T3  strcmp differential vs the guest's libc strcmp:
 *        a) 1-char full byte domain (65536 ordered pairs)
 *        b) 2-char domain over a 32-byte boundary alphabet (32^4 = 1,048,576)
 *        c) 200M seeded-random pairs, full byte domain, lengths 0..24,
 *           half sharing a random common prefix (deep equal walks)
 *        d) identical 4 KiB strings
 *       Metrics: sign-class mismatches (MUST be 0 -- C99 contract) and
 *       exact-value mismatches (informational: libc implementations that
 *       return the byte difference must match Torek's return exactly).
 *   T4  guard-page differential (strcmp): two data pages + PROT_NONE guard.
 *        G1 NUL exactly at page edge, strings equal  -> expect 0, NO fault
 *        G2 mismatch at the LAST in-bounds byte      -> expect a-b, NO fault
 *           (proves the *(s2 - 1) re-read at strcmp.c:47 stays in bounds)
 *        G3 s1 runs non-NUL to the edge, s2 longer  -> expect SIGSEGV at
 *           the guard page (si_addr recorded) -- the unbounded NUL-walk
 *           contract of strcmp.c:44-46, demonstrated
 *        G4 same with s2 at the edge                 -> expect SIGSEGV
 *        G5 libc parity control for G3/G4 (same contract, same fault)
 *   T5  ffs guard-page: N/A by construction -- ffs.c takes no pointers and
 *       never dereferences memory (ffs.c:39-47 is pure register arithmetic).
 */
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <signal.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int   k_ffs(int);
long  k_ffsl(long);
int   k_strcmp(const char *, const char *);

static int        (*volatile vffs)(int)       = k_ffs;
static long       (*volatile vffsl)(long)     = k_ffsl;
static int        (*volatile vstrcmp)(const char *, const char *) = k_strcmp;

static uint64_t g_exact_mism, g_sign_mism, g_cases;
static const char *g_first_sign;

static void
cmp_one(const char *a, const char *b)
{
	int k = vstrcmp(a, b);
	int r = strcmp(a, b);

	g_cases++;
	if (((k < 0) != (r < 0)) || ((k > 0) != (r > 0)) || ((k == 0) != (r == 0))) {
		if (g_sign_mism == 0)
			g_first_sign = __builtin_return_address(0), g_first_sign = a;
		g_sign_mism++;
	}
	if (k != r)
		g_exact_mism++;
}

static uint64_t
xs64(uint64_t *s)
{
	uint64_t x = *s;
	x ^= x << 13; x ^= x >> 7; x ^= x << 17;
	return (*s = x);
}

int
main(void)
{
	int fail = 0;

	setvbuf(stdout, NULL, _IOLBF, 0);

	/* ---------------- T1: ffs full 2^32 domain ---------------- */
	{
		uint32_t i = 0;
		uint64_t n = 0, mism = 0;
		int printed = 0;
		do {
			int kk = vffs((int)i);
			int bb = __builtin_ffs((int)i);
			if (kk != bb) {
				if (!printed) {
					printf("T1 FIRST-MISMATCH i=0x%08x kernel-body=%d builtin=%d\n",
					       i, kk, bb);
					printed = 1;
				}
				mism++;
			}
			n++;
			i++;
		} while (i != 0);
		printf("T1 ffs full-domain: %llu cases, %llu mismatches "
		       "(kernel ffs.c body vs __builtin_ffs == live cpufunc.h inline)\n",
		       (unsigned long long)n, (unsigned long long)mism);
		if (mism)
			fail |= 1;
	}

	/* ---------------- T2: ffsl (family context) ---------------- */
	{
		uint64_t mism = 0, n = 0, s = 0x9E3779B97F4A7C15ULL;
		int k, b;
		for (int i = 0; i < 64; i++) {			/* single bits */
			uint64_t v = 1ULL << i;
			k = (int)vffsl((long)v); b = __builtin_ffsl((long)v);
			if (k != b) { mism++; }
			n++;
		}
		for (int i = 0; i < 64; i++)			/* all bit pairs */
			for (int j = i + 1; j < 64; j++) {
				uint64_t v = (1ULL << i) | (1ULL << j);
				k = (int)vffsl((long)v); b = __builtin_ffsl((long)v);
				if (k != b) { mism++; }
			n++;
			}
		{	uint64_t edges[] = {0, ~0ULL, 1, 1ULL<<63, 0xffffffffULL,
					     ~0ULL ^ 0xffffffffULL,
					     0x8000000000000000ULL | 1,
					     0x0000ffff0000ffffULL};
			for (size_t e = 0; e < sizeof(edges)/sizeof(edges[0]); e++) {
				k = (int)vffsl((long)edges[e]);
				b = __builtin_ffsl((long)edges[e]);
				if (k != b) { mism++; }
			n++;
			}
		}
		for (uint64_t r = 0; r < 50000000ULL; r++) {	/* random 64-bit */
			uint64_t v = xs64(&s);
			k = (int)vffsl((long)v); b = __builtin_ffsl((long)v);
			if (k != b) { mism++; }
			n++;
		}
		printf("T2 ffsl: %llu cases, %llu mismatches (vs __builtin_ffsl)\n",
		       (unsigned long long)n, (unsigned long long)mism);
		if (mism)
			fail |= 2;
	}

	/* ---------------- T3: strcmp differential ---------------- */
	{
		/* a) 1-char full byte domain */
		for (int a = 0; a < 256; a++)
			for (int c = 0; c < 256; c++) {
				char x[2] = { (char)a, 0 }, y[2] = { (char)c, 0 };
				cmp_one(x, y);
			}
		printf("T3a 1-char full domain done: %llu cases so far, "
		       "%llu sign-mismatch, %llu exact-mismatch\n",
		       (unsigned long long)g_cases,
		       (unsigned long long)g_sign_mism,
		       (unsigned long long)g_exact_mism);

		/* b) 2-char domain over boundary alphabet */
		{
			unsigned char al[32] = {
				0x00, 0x01, 0x02, 0x09, 0x0a, 0x1b, 0x20, 0x41,
				0x5a, 0x5f, 0x60, 0x61, 0x7a, 0x7e, 0x7f, 0x80,
				0x81, 0x8f, 0x90, 0xa0, 0xaa, 0xc0, 0xdf, 0xe0,
				0xf0, 0xfe, 0xff, 0x7f, 0x80, 0xff, 0x00, 0x41
			};
			for (int i = 0; i < 32; i++)
			for (int j = 0; j < 32; j++)
			for (int p = 0; p < 32; p++)
			for (int q = 0; q < 32; q++) {
				char x[3] = { (char)al[i], (char)al[j], 0 };
				char y[3] = { (char)al[p], (char)al[q], 0 };
				cmp_one(x, y);
			}
		}
		printf("T3b 2-char boundary alphabet done: %llu cases so far, "
		       "%llu sign-mismatch, %llu exact-mismatch\n",
		       (unsigned long long)g_cases,
		       (unsigned long long)g_sign_mism,
		       (unsigned long long)g_exact_mism);

		/* c) 200M seeded random pairs, half sharing a common prefix */
		{
			uint64_t s = 0x243F6A8885A308D3ULL;
			char x[40], y[40];
			for (uint64_t r = 0; r < 200000000ULL; r++) {
				int l1 = (int)(xs64(&s) % 25);
				int l2 = (int)(xs64(&s) % 25);
				int cp = -1;
				if (r & 1) {			/* common prefix */
					int m = l1 < l2 ? l1 : l2;
					cp = (int)(xs64(&s) % (uint64_t)(m + 1));
				}
				for (int t = 0; t < l1; t++)
					x[t] = (char)(xs64(&s) & 0xff);
				for (int t = 0; t < l2; t++) {
					y[t] = (char)(xs64(&s) & 0xff);
					if (cp >= 0 && t < cp)
						y[t] = x[t];
				}
				/* keep at least one NUL somewhere reachable-ish;
				 * unterminated is fine, buffers are 40 bytes */
				x[l1] = 0; y[l2] = 0;
				cmp_one(x, y);
			}
		}
		printf("T3c 200M random pairs done: %llu cases so far, "
		       "%llu sign-mismatch, %llu exact-mismatch\n",
		       (unsigned long long)g_cases,
		       (unsigned long long)g_sign_mism,
		       (unsigned long long)g_exact_mism);

		/* d) identical 4 KiB strings */
		{
			static char big[4096 + 1];
			memset(big, 'A', 4096);
			big[4096] = 0;
			cmp_one(big, big);
			cmp_one(big, ""); cmp_one("", big); cmp_one("", "");
		}
		printf("T3d identical-4K + empty: %llu total cases, "
		       "%llu sign-mismatch, %llu exact-mismatch\n",
		       (unsigned long long)g_cases,
		       (unsigned long long)g_sign_mism,
		       (unsigned long long)g_exact_mism);
		if (g_sign_mism)
			fail |= 4;
	}

	/* ---------------- T4: guard-page differential ---------------- */
	{
		size_t pg = (size_t)getpagesize();
		char *base = mmap(NULL, 2 * pg, PROT_READ | PROT_WRITE,
				  MAP_ANON | MAP_PRIVATE, -1, 0);
		if (base == MAP_FAILED) { perror("mmap"); fail |= 8; goto t4done; }
		if (mprotect(base + pg, pg, PROT_NONE) == -1) { perror("mprotect"); fail |= 8; goto t4done; }
		char *edge = base + pg;			/* first byte of guard */

		/* G1: equal strings, NUL exactly at the edge of BOTH */
		memset(base, 'K', pg - 1);
		base[pg - 1] = 0;			/* s1: NUL at last byte  */
		{
			char *s2 = strdup(base);	/* terminated copy away from guard */
			int k = vstrcmp(base, s2);
			int r = strcmp(base, s2);
			printf("T4-G1 NUL-at-edge equal: kernel=%d libc=%d (expect 0, no fault) %s\n",
			       k, r, (k == 0 && r == 0) ? "OK" : "FAIL");
			if (k != 0 || r != 0) fail |= 16;
			free(s2);
		}

		/* G2: mismatch at the LAST in-bounds byte; everything before equal */
		{
			char *s1 = base;			/* ...'K' 'A' NUL  */
			char s2buf[pg];				/* ...'K' 'B' NUL  */
			memset(s2buf, 'K', pg - 2);
			s1[pg - 2] = 'A'; s1[pg - 1] = 0;
			s2buf[pg - 2] = 'B'; s2buf[pg - 1] = 0;
			int k = vstrcmp(s1, s2buf);
			int r = strcmp(s1, s2buf);
			printf("T4-G2 mismatch-at-edge: kernel=%d libc=%d (expect -1, no fault: "
			       "*(s2-1) re-read strcmp.c:47 stays in bounds) %s\n",
			       k, r, (k < 0 && r < 0 && k == r) ? "OK" : "FAIL");
			if (!(k < 0 && r < 0 && k == r)) fail |= 16;
		}

		/* G3/G4: non-terminated walk off the guard page (forked) */
		{
			static const struct { int which; int use_libc; } cases[] = {
				{ 3, 0 }, { 3, 1 }, { 4, 0 }, { 4, 1 }
			};
			for (size_t c = 0; c < sizeof(cases)/sizeof(cases[0]); c++) {
				/* re-arm: base must be ALL 'K', NO NUL anywhere
				 * (G2 above left 'A',NUL at the edge) */
				memset(base, 'K', pg);
				pid_t p = fork();
				if (p == 0) {
					char big[8192];
					int r;
					memset(big, 'K', sizeof(big));
					/* G3: s1 non-NUL to the edge; G4: s2 at edge */
					if (cases[c].which == 3) {
						if (cases[c].use_libc)
							r = strcmp(base, big);
						else
							r = vstrcmp(base, big);
					} else {
						if (cases[c].use_libc)
							r = strcmp(big, base);
						else
							r = vstrcmp(big, base);
					}
					if (r == 0x12345678)	/* observable: defeats DCE */
						write(2, "x", 1);
					_exit(0);			/* no fault */
				}
				int st = 0;
				waitpid(p, &st, 0);
				int sig = WIFSIGNALED(st) ? WTERMSIG(st) : 0;
				printf("T4-G%d %s non-terminated to edge: %s (expect SIGSEGV=11 "
				       "from the guard page: unbounded NUL-walk contract "
				       "strcmp.c:44-46)\n",
				       cases[c].which,
				       cases[c].use_libc ? "libc  " : "kernel",
				       sig == SIGSEGV ? "SIGSEGV-OK" :
				       (WIFEXITED(st) ? "NO-FAULT(unexpected)" : "?"));
				if (sig != SIGSEGV) fail |= 32;
			}
		}
		printf("T4-G3/G4 note: base[0..pg-1]='K' with NO NUL anywhere; walk "
		       "must fault exactly at guard base %p\n", (void *)edge);
t4done:	;
	}

	/* ---------------- T5: ffs takes no pointers ---------------- */
	printf("T5 ffs guard-page: N/A -- ffs.c:39-47 is pure register "
	       "arithmetic (no pointer parameters, no dereference, verified "
	       "by inspection; differential T1 covers its full input space)\n");

	printf(fail ? "HARNESS-FAIL mask=0x%x\n" : "HARNESS-PASS\n", fail);
	return (fail ? 1 : 0);
}