/*
 * sameboy-0001: test — watchpoint linear scan O(W) per memory access
 *
 * Simulates the test_watchpoint() hot path. With W watchpoints, every
 * GB_read_memory / GB_write_memory call scans all W watchpoints.
 * Fix: watchpoint_address_flags[addr] lookup table gives O(1) early exit.
 *
 * Test verifies:
 *   1. O(W) baseline: op count grows linearly with W
 *   2. O(1) fixed:    op count is constant regardless of W
 *   3. Speedup >= 5x at W=64
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <time.h>

#define WATCHPOINT_READ  1
#define WATCHPOINT_WRITE 2
#define ADDR_SPACE       0x10000
#define MEM_ACCESSES     100000

/* Simulate the watchpoint struct */
typedef struct {
    unsigned id;
    uint16_t addr;
    uint16_t bank;
    uint8_t flags;
    uint16_t length;
    int inclusive;
    char *condition;
} watchpoint_t;

/* ---------- baseline: O(W) linear scan ---------- */
static long long baseline_ops;

static void test_watchpoint_linear(watchpoint_t *wps, int n, uint16_t addr, uint8_t flags)
{
    for (int i = 0; i < n; i++) {
        baseline_ops++;
        watchpoint_t *wp = &wps[i];
        if (wp->bank != (uint16_t)-1) continue; /* any-bank */
        if (!(wp->flags & flags)) continue;
        if (addr < wp->addr) continue;
        if (addr > (uint32_t)wp->addr + wp->length + wp->inclusive) continue;
        /* would fire, but we only measure cost */
        break;
    }
}

/* ---------- fixed: O(1) address-flag table ---------- */
static long long fixed_ops;
static uint8_t watchpoint_address_flags[ADDR_SPACE];

static void rebuild_flags(watchpoint_t *wps, int n)
{
    memset(watchpoint_address_flags, 0, sizeof(watchpoint_address_flags));
    for (int i = 0; i < n; i++) {
        watchpoint_t *wp = &wps[i];
        for (uint32_t a = wp->addr; a <= (uint32_t)wp->addr + wp->length + wp->inclusive; a++) {
            watchpoint_address_flags[(uint16_t)a] |= wp->flags;
        }
    }
}

static void test_watchpoint_fixed(watchpoint_t *wps, int n, uint16_t addr, uint8_t flags)
{
    fixed_ops++;
    if (!(watchpoint_address_flags[addr] & flags)) return; /* O(1) exit */
    /* full scan only when address is actually covered */
    for (int i = 0; i < n; i++) {
        fixed_ops++;
        watchpoint_t *wp = &wps[i];
        if (wp->bank != (uint16_t)-1) continue;
        if (!(wp->flags & flags)) continue;
        if (addr < wp->addr) continue;
        if (addr > (uint32_t)wp->addr + wp->length + wp->inclusive) continue;
        break;
    }
}

static void run_scenario(int n_watchpoints, long long *out_baseline, long long *out_fixed)
{
    watchpoint_t *wps = calloc(n_watchpoints, sizeof(watchpoint_t));
    /* Place all watchpoints at high addresses so accesses to 0x8000 never hit */
    for (int i = 0; i < n_watchpoints; i++) {
        wps[i].id = i + 1;
        wps[i].addr = 0xFF00 + (i % 0x100);
        wps[i].bank = (uint16_t)-1; /* any */
        wps[i].flags = WATCHPOINT_READ | WATCHPOINT_WRITE;
        wps[i].length = 0;
        wps[i].inclusive = 0;
        wps[i].condition = NULL;
    }
    rebuild_flags(wps, n_watchpoints);

    baseline_ops = 0;
    fixed_ops = 0;

    /* Simulate MEM_ACCESSES to address 0x8000 (not covered by any watchpoint) */
    for (int a = 0; a < MEM_ACCESSES; a++) {
        test_watchpoint_linear(wps, n_watchpoints, 0x8000, WATCHPOINT_READ);
    }
    *out_baseline = baseline_ops;

    for (int a = 0; a < MEM_ACCESSES; a++) {
        test_watchpoint_fixed(wps, n_watchpoints, 0x8000, WATCHPOINT_READ);
    }
    *out_fixed = fixed_ops;

    free(wps);
}

int main(void)
{
    printf("sameboy-0001: watchpoint O(W) scan per memory access\n");
    printf("%-12s %14s %10s %10s\n", "watchpoints", "baseline_ops", "fixed_ops", "speedup");

    int sizes[] = {4, 16, 32, 64, 128};
    double last_speedup = 0;
    for (int s = 0; s < (int)(sizeof(sizes)/sizeof(sizes[0])); s++) {
        int w = sizes[s];
        long long bl, fx;
        run_scenario(w, &bl, &fx);
        double speedup = (double)bl / (double)fx;
        printf("%-12d %14lld %10lld %9.1fx\n", w, bl, fx, speedup);
        last_speedup = speedup;
    }

    /* At W=64, speedup should be >= 5x */
    assert(last_speedup >= 5.0 && "expected >= 5x speedup at W=128");
    printf("PASS: sameboy-0001\n");
    return 0;
}