/*
 * Load-instrumented copy of sys/libkern/memcchr.c -- identical control flow.
 *
 * The two longword load sites of the pristine source are wrapped by LDC():
 *   - memcchr.c:83-85  first-word align-down load (`*lp++')
 *   - memcchr.c:90-91  word-walk load (`*lp')
 * and every TESTBYTE byte load by LDB().  NOTE() records each loaded range
 * against the caller region [g_lo, g_hi) = [begin, begin+n):
 *   - loads starting below begin   (backward over-read)
 *   - loads extending past  end    (forward over-read)
 *   - loads escaping the enclosing word granules [align_down(begin),
 *     align_up(end))  (containment invariant: must NEVER happen)
 * plus the done-filter observer: `goto done' reached with p >= end
 * (mismatch found only in over-read bytes; memcchr.c:114 must reject it).
 *
 * Semantics are cross-checked against a naive reference by instr_driver.c:
 * zero differential mismatches proves the instrumentation did not change
 * behavior.
 */
#include "prelude.h"

#define	LONGPTR_MASK (sizeof(long) - 1)

unsigned long g_below_start, g_past_end, g_in;
unsigned long g_max_below, g_max_past;
unsigned long g_filtered;         /* done reached with p >= end */
unsigned long g_outside_granule;  /* load outside enclosing granules: must stay 0 */
const unsigned char *g_lo, *g_hi;

#define NOTE(p, sz) do {                                                    \
    const unsigned char *_p = (const unsigned char *)(p);                   \
    if (_p < g_lo) {                                                        \
        g_below_start++;                                                    \
        { unsigned long _d = (unsigned long)(g_lo - _p);                    \
          if (_d > g_max_below) g_max_below = _d; }                         \
    } else if (_p + (sz) > g_hi) {                                          \
        g_past_end++;                                                       \
        { unsigned long _d = (unsigned long)(_p + (sz) - g_hi);             \
          if (_d > g_max_past) g_max_past = _d; }                           \
    } else g_in++;                                                          \
    if (_p < (const unsigned char *)((uintptr_t)g_lo & ~(uintptr_t)7) ||    \
        _p + (sz) >                                                         \
        (const unsigned char *)(((uintptr_t)g_hi + 7) & ~(uintptr_t)7))     \
        g_outside_granule++;                                                \
} while (0)

/* statement-expression loads: record, then perform the exact original load */
#define LDC(e) ({ const unsigned long *_q = (e);                               \
    NOTE((const unsigned char *)_q, sizeof(unsigned long)); *_q; })
#define LDB(e) ({ const unsigned char *_q = (e); NOTE(_q, 1); *_q; })

static int g_c;
#define TESTBYTE_I                              \
	do {                                        \
		if (LDB(p) != (unsigned char)g_c)       \
			goto done;                          \
		p++;                                    \
	} while (0)

void *
memcchr_instr(const void *begin, int c, size_t n)
{
	const unsigned long *lp;
	const unsigned char *p, *end;
	unsigned long word, first;

	g_c = c;
	g_lo = (const unsigned char *)begin;
	g_hi = (const unsigned char *)begin + n;

	/* Four or eight repetitions of `c'. */
	word = (unsigned char)c;
	word |= word << 8;
	word |= word << 16;
#if LONG_BIT >= 64
	word |= word << 32;
#endif

	/* Don't perform memory I/O when passing a zero-length buffer. */
	if (n == 0)
		return (NULL);

	lp = (const unsigned long *)((uintptr_t)begin & ~LONGPTR_MASK);
	end = (const unsigned char *)begin + n;
	first = LDC(lp);
	lp++;
	if (first != word)
		for (p = begin; p < (const unsigned char *)lp;)
			TESTBYTE_I;

	/* Now compare the data one word at a time. */
	for (; (const unsigned char *)lp < end; lp++) {
		unsigned long w = LDC(lp);
		if (w != word) {
			p = (const unsigned char *)lp;
			TESTBYTE_I;
			TESTBYTE_I;
			TESTBYTE_I;
#if LONG_BIT >= 64
			TESTBYTE_I;
			TESTBYTE_I;
			TESTBYTE_I;
			TESTBYTE_I;
#endif
			goto done;
		}
	}

	return (NULL);

done:
	/*
	 * If the end of the buffer is not word aligned, the previous
	 * loops may obtain an address that's beyond the end of the
	 * buffer.
	 */
	if (p >= end)
		g_filtered++;
	if (p < end)
		return (__DECONST(void *, p));
	return (NULL);
}