/*
 * DF-5715 / DF-5716 / DF-5717 pass-2 differential harness (rig pattern:
 * DF-5714).  Runs on the DragonFly guest as a plain userland binary.
 *
 * Compares the VERBATIM kernel bodies (k_ffsl / k_flsl / k_flsll, compiled
 * from the guest's own /usr/src/sys/libkern/{ffsl,flsl,flsll}.c with only
 * the kernel-only #include line stripped and the identifier renamed at the
 * preprocessor level, cksum-pinned in build.log) against:
 *
 *   (1) the LIVE kernel inline implementations exactly as defined in
 *       sys/cpu/x86_64/include/cpufunc.h (bsrl/bsrq asm copied verbatim
 *       from cpufunc.h:110-126; ffsl :276-280 -> __builtin_ffsl;
 *       flsl :292-296 -> bsrq+1; flsll :300-304 -> flsl((long)mask)), and
 *   (2) builtin-clz references (64-__builtin_clz{,l,ll} for nonzero).
 *
 * Domains per function (structure-complete for this family: the output of
 * fls* depends only on the MSB position, that of ffs* only on the LSB
 * position; random words additionally cross-check everything else):
 *   - 0, ~0, and the sign-only words (1<<63), all 64 single-bit words
 *   - exhaustive over all values with bits confined to the low 22 positions
 *   - exhaustive over all values with bits confined to the top 22 positions
 *   - for every MSB position h in 0..63: 1024 random words with highest
 *     set bit exactly h
 *   - 50,000,000 uniform random 64-bit words (splitmix64, fixed seed)
 */
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

typedef unsigned int  u_int;
typedef unsigned long u_long;

/* ---- verbatim kernel bodies, linked from k_*.o (renamed -Dffsl=k_ffsl ...) */
int k_ffsl(long mask);
int k_flsl(long mask);
int k_flsll(long long mask);

/* ---- live inline bodies, copied VERBATIM from cpufunc.h ---- */

/* cpufunc.h:110-117 */
static __inline u_int
live_bsrl(u_int mask)
{
	u_int	result;

	__asm __volatile("bsrl %1,%0" : "=r" (result) : "rm" (mask));
	return (result);
}

/* cpufunc.h:119-126 */
static __inline u_long
live_bsrq(u_long mask)
{
	u_long	result;

	__asm __volatile("bsrq %1,%0" : "=r" (result) : "rm" (mask));
	return (result);
}

/* cpufunc.h:276-280 (HAVE_INLINE_FFSL) */
static __inline int
live_ffsl(long mask)
{
	return (__builtin_ffsl(mask));
}

/* cpufunc.h:292-296 (HAVE_INLINE_FLSL) */
static __inline int
live_flsl(long mask)
{
	return (mask == 0 ? mask : (int)live_bsrq((u_long)mask) + 1);
}

/* cpufunc.h:300-304 (HAVE_INLINE_FLSLL) */
static __inline int
live_flsll(long long mask)
{
	return (live_flsl((long)mask));
}

/* ---- builtin-clz references ---- */
static int
ref_ffsl(long v)
{
	return (__builtin_ffsl(v));
}
static int
ref_flsl(long v)
{
	return (v == 0 ? 0 : 64 - __builtin_clzl((unsigned long)v));
}
static int
ref_flsll(long long v)
{
	return (v == 0 ? 0 : 64 - __builtin_clzll((unsigned long long)v));
}

/* ---- volatile trampolines so nothing inlines/DCEs the out-of-line bodies ---- */
static int (*volatile pk_ffsl)(long) = k_ffsl;
static int (*volatile pk_flsl)(long) = k_flsl;
static int (*volatile pk_flsll)(long long) = k_flsll;

/* splitmix64, fixed seed */
static uint64_t sm64_state = 0xDF5715000ULL;
static uint64_t
sm64(void)
{
	uint64_t z = (sm64_state += 0x9E3779B97F4A7C15ULL);
	z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
	z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
	return (z ^ (z >> 31));
}

static uint64_t cases, bad_vs_live_ffsl, bad_vs_ref_ffsl;
static uint64_t bad_vs_live_flsl, bad_vs_ref_flsl;
static uint64_t bad_vs_live_flsll, bad_vs_ref_flsll, bad_flsll_vs_flsl;

static void
chk(uint64_t v)
{
	int a, b, c, d, e, f, g;

	cases++;

	/* ffsl family */
	a = pk_ffsl((long)v);
	b = live_ffsl((long)v);
	c = ref_ffsl((long)v);
	if (a != b) bad_vs_live_ffsl++;
	if (a != c) bad_vs_ref_ffsl++;

	/* flsl family */
	d = pk_flsl((long)v);
	e = live_flsl((long)v);
	f = ref_flsl((long)v);
	if (d != e) bad_vs_live_flsl++;
	if (d != f) bad_vs_ref_flsl++;

	/* flsll family (kernel body vs live inline vs clzll ref vs flsl twin) */
	g = pk_flsll((long long)v);
	if (g != live_flsll((long long)v)) bad_vs_live_flsll++;
	if (g != ref_flsll((long long)v)) bad_vs_ref_flsll++;
	if (g != d) bad_flsll_vs_flsl++;
}

int
main(void)
{
	uint64_t v, x, h, i, n;

	/* hand-picked edges: 0, ~0, sign-only, single bits */
	chk(0);
	chk(~(uint64_t)0);
	chk(1ULL << 63);
	for (h = 0; h < 64; h++)
		chk(1ULL << h);

	/* exhaustive: bits confined to low 22 positions (4,194,304 words) */
	for (x = 0; x < (1ULL << 22); x++)
		chk(x);

	/* exhaustive: bits confined to top 22 positions (4,194,304 words) */
	for (x = 0; x < (1ULL << 22); x++)
		chk(x << 42);

	/* structure-complete MSB sweep: every MSB position, random below it */
	for (h = 0; h < 64; h++)
		for (i = 0; i < 1024; i++) {
			v = sm64();
			if (h == 0)
				v = 0;
			else
				v = ((v & ((1ULL << h) - 1)) | (1ULL << h));
			chk(v);
		}

	/* large uniform random sample */
	n = 50000000ULL;
	for (i = 0; i < n; i++)
		chk(sm64());

	printf("T1 ffsl : %10" PRIu64 " cases, %10" PRIu64
	    " mism vs live-inline, %10" PRIu64 " mism vs clz-ref\n",
	    cases, bad_vs_live_ffsl, bad_vs_ref_ffsl);
	printf("T2 flsl : %10" PRIu64 " cases, %10" PRIu64
	    " mism vs live-inline, %10" PRIu64 " mism vs clz-ref\n",
	    cases, bad_vs_live_flsl, bad_vs_ref_flsl);
	printf("T3 flsll: %10" PRIu64 " cases, %10" PRIu64
	    " mism vs live-inline, %10" PRIu64 " mism vs clz-ref,"
	    " %10" PRIu64 " mism vs kernel-flsl-twin\n",
	    cases, bad_vs_live_flsll, bad_vs_ref_flsll, bad_flsll_vs_flsl);

	if (bad_vs_live_ffsl || bad_vs_ref_ffsl ||
	    bad_vs_live_flsl || bad_vs_ref_flsl ||
	    bad_vs_live_flsll || bad_vs_ref_flsll || bad_flsll_vs_flsl) {
		printf("HARNESS-FAIL: at least one kernel body diverges\n");
		return (1);
	}
	printf("HARNESS-PASS: all three verbatim kernel bodies are output-"
	    "identical to the live cpufunc.h inlines and clz references on "
	    "every tested input\n");
	return (0);
}