/*
 * sameboy-0002: test — breakpoint linear scan O(B) per CPU instruction
 *
 * should_break() scans gb->breakpoints[0..n] on every instruction fetch
 * when debug_active is set. With B breakpoints all at high addresses,
 * an instruction fetch at 0x0100 (ROM entry point) incurs O(B) scan.
 *
 * Fix: breakpoint_address_set[addr] boolean lookup gives O(1) early exit.
 *
 * Test verifies:
 *   1. O(B) baseline: op count grows linearly with B
 *   2. O(1) fixed:    op count is constant regardless of B
 *   3. Speedup >= 5x at B=64
 */

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

#define ADDR_SPACE   0x10000
#define INSTRUCTIONS 100000

typedef struct {
    unsigned id;
    uint16_t addr;
    uint16_t bank;
    char *condition;
    bool is_jump_to;
    uint16_t length;
    bool inclusive;
} breakpoint_t;

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

static unsigned should_break_linear(breakpoint_t *bps, int n, uint16_t addr)
{
    for (int i = 0; i < n; i++) {
        baseline_ops++;
        breakpoint_t *bp = &bps[i];
        if (bp->bank != (uint16_t)-1) {
            /* bank check omitted for simplicity — bank always any */
        }
        if (addr < bp->addr) continue;
        if (addr > (uint32_t)bp->addr + bp->length + bp->inclusive) continue;
        if (!bp->condition) return bp->id;
    }
    return 0;
}

/* ---------- fixed: O(1) address-set table ---------- */
static long long fixed_ops;
static bool breakpoint_address_set[ADDR_SPACE];

static void rebuild_address_set(breakpoint_t *bps, int n)
{
    memset(breakpoint_address_set, 0, sizeof(breakpoint_address_set));
    for (int i = 0; i < n; i++) {
        breakpoint_t *bp = &bps[i];
        for (uint32_t a = bp->addr; a <= (uint32_t)bp->addr + bp->length + bp->inclusive; a++) {
            breakpoint_address_set[(uint16_t)a] = true;
        }
    }
}

static unsigned should_break_fixed(breakpoint_t *bps, int n, uint16_t addr)
{
    fixed_ops++;
    if (!breakpoint_address_set[addr]) return 0; /* O(1) exit */
    /* full scan only when address is registered */
    for (int i = 0; i < n; i++) {
        fixed_ops++;
        breakpoint_t *bp = &bps[i];
        if (addr < bp->addr) continue;
        if (addr > (uint32_t)bp->addr + bp->length + bp->inclusive) continue;
        if (!bp->condition) return bp->id;
    }
    return 0;
}

static void run_scenario(int n_bp, long long *out_baseline, long long *out_fixed)
{
    breakpoint_t *bps = calloc(n_bp, sizeof(breakpoint_t));
    /* Place all breakpoints at high addresses so PC=0x0100 never hits */
    for (int i = 0; i < n_bp; i++) {
        bps[i].id = i + 1;
        bps[i].addr = 0xFF00 + (i % 0x100);
        bps[i].bank = (uint16_t)-1;
        bps[i].length = 0;
        bps[i].inclusive = false;
        bps[i].is_jump_to = false;
        bps[i].condition = NULL;
    }
    rebuild_address_set(bps, n_bp);

    baseline_ops = 0;
    fixed_ops = 0;

    for (int i = 0; i < INSTRUCTIONS; i++) {
        should_break_linear(bps, n_bp, 0x0100);
    }
    *out_baseline = baseline_ops;

    for (int i = 0; i < INSTRUCTIONS; i++) {
        should_break_fixed(bps, n_bp, 0x0100);
    }
    *out_fixed = fixed_ops;

    free(bps);
}

int main(void)
{
    printf("sameboy-0002: breakpoint O(B) scan per CPU instruction\n");
    printf("%-12s %14s %10s %10s\n", "breakpoints", "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 b = sizes[s];
        long long bl, fx;
        run_scenario(b, &bl, &fx);
        double speedup = (double)bl / (double)fx;
        printf("%-12d %14lld %10lld %9.1fx\n", b, bl, fx, speedup);
        last_speedup = speedup;
    }

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