/*
 * Differential + over-read measurement driver for the instrumented copy of
 * sys/libkern/memcchr.c (memcchr_instr.c -- pristine control flow).
 *
 *  A) exhaustive differential vs a naive reference:
 *       begin-offsets 0..31, lengths 0..96, every mismatch position
 *       (incl. none), below-begin and past-end canaries != c
 *  B) randomized differential: 2,000,000 cases, len 0..8192
 *  C) over-read invariants:
 *       - below-start loads > 0 (first-word align-down, memcchr.c:83-85)
 *       - past-end   loads > 0 (word walk, memcchr.c:90-91)
 *       - max excursion <= sizeof(long)-1 in BOTH directions
 *       - zero loads outside [align_down(begin), align_up(end))
 *       - done-filter activations > 0 (mismatch found at p >= end is
 *         rejected by memcchr.c:114 and must still return NULL)
 *
 * Buffers live inside a large safe arena with >= 16-byte margins so the
 * instrumented loads themselves can never fault; the page-containment
 * property is proven separately by guard_harness.c.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>

extern unsigned long g_below_start, g_past_end, g_in;
extern unsigned long g_max_below, g_max_past, g_filtered, g_outside_granule;
void *memcchr_instr(const void *, int, size_t);

#define ASZ (1 << 20)
static unsigned char *A;

static uint64_t s_state = 0x243f6a8885a308d3ULL;
static uint64_t prng(void)
{
	s_state ^= s_state << 13; s_state ^= s_state >> 7; s_state ^= s_state << 17;
	return s_state;
}

static void *ref(const unsigned char *b, int c, size_t n)
{
	size_t i;
	for (i = 0; i < n; i++)
		if (b[i] != (unsigned char)c)
			return ((unsigned char *)(uintptr_t)(b + i));
	return (NULL);
}

static long fails, total;

static void check(unsigned char *b, int c, size_t n)
{
	void *r = memcchr_instr(b, c, n);
	void *e = ref(b, c, n);
	total++;
	if (r != e) {
		if (fails < 10)
			printf("DIFF FAIL n=%zu c=%#x off=%td got=%p want=%p\n",
			    (size_t)n, c, (ptrdiff_t)(b - A), r, e);
		fails++;
	}
}

int main(void)
{
	A = malloc(ASZ);
	if (!A) { perror("malloc"); return 2; }
	memset(A, 0x5a, ASZ);

	/* A: exhaustive */
	{
		int off, len, mpos, ci;
		int cs[4] = { 0x00, 0xff, 0x41, 0x80 };
		long base = 0;
		for (off = 0; off < 32; off++)
		for (len = 0; len <= 96; len++)
		for (ci = 0; ci < 4; ci++)
		for (mpos = 0; mpos <= len; mpos++) {
			unsigned char *b = A + 64 + off;
			int c = cs[ci];
			size_t i;
			for (i = 0; i < (size_t)len; i++)
				b[i] = (unsigned char)c;
			b[-1] = (unsigned char)~c;	/* below-begin canary */
			b[len] = (unsigned char)~c;	/* past-end canary   */
			if (mpos < len)
				b[mpos] = (unsigned char)~c;
			check(b, c, (size_t)len);
		}
		printf("exhaustive differential : %ld cases, %ld failures\n",
		    total - base, fails);
	}

	/* B: randomized */
	{
		long i;
		long base = total;
		for (i = 0; i < 2000000; i++) {
			size_t off = (size_t)(prng() & 0xffff);
			size_t n = (size_t)(prng() % 8193);
			int c = (int)(prng() & 0xff);
			size_t j;
			unsigned char *b = A + 128 + off;
			if (128 + off + n + 128 > ASZ)
				n = 0;
			for (j = 0; j < n; j++)
				b[j] = (prng() & 4) ? (unsigned char)c
				    : (unsigned char)prng();
			check(b, c, n);
		}
		printf("randomized differential : %ld cases, %ld failures\n",
		    total - base, fails);
	}

	/* C: over-read invariants over everything just executed */
	{
		int ok = 1;
		printf("over-read measurement (pristine memcchr.c):\n");
		printf("  loads below begin      : %lu (max %lu B before begin)\n",
		    g_below_start, g_max_below);
		printf("  loads past end         : %lu (max %lu B past end)\n",
		    g_past_end, g_max_past);
		printf("  fully in-range loads   : %lu\n", g_in);
		printf("  done-filter rejections : %lu (mismatch found at p >= end,"
		    " returned NULL anyway)\n", g_filtered);
		printf("  loads outside [align_down(begin), align_up(end)) : %lu"
		    " (MUST be 0)\n", g_outside_granule);
		if (g_max_below > sizeof(unsigned long) - 1 ||
		    g_max_past > sizeof(unsigned long) - 1) {
			printf("  UNEXPECTED excursion > 7 bytes\n");
			ok = 0;
		}
		if (g_outside_granule != 0) {
			printf("  CONTAINMENT INVARIANT VIOLATED\n");
			ok = 0;
		}
		if (g_below_start == 0 || g_past_end == 0 || g_filtered == 0) {
			printf("  NOTE: expected nonzero below/past/filter counts"
			    " (sweep should exercise all shapes)\n");
			ok = 0;
		}
		if (fails != 0)
			ok = 0;
		printf("RESULT: %s\n", ok ?
		    "OVERREAD-CONFIRMED (live, <=7B both directions, granule-"
		    "contained, result-filtered); semantics exact vs reference" :
		    "FAIL");
		return ok ? 0 : 1;
	}
}