java-topology/defects/caprice32-0001/test/test_caprice32_0001.cpp

// Unit test for caprice32-0001: CWE-407 breakpoint linear scan O(B) per Z80 instruction
//
// In src/z80.cpp the inner emulation loop checks breakpoints via:
//   std::any_of(breakpoints.begin(), breakpoints.end(), [&](const auto& b) { return b.address == _PC; })
// This is O(B) per instruction. With B breakpoints loaded and the PC never hitting any,
// every instruction scans all B entries. At ~4 MHz Z80 clock, that is ~4 million O(B)
// scans per second -- a multiplier of B applied to our emulation speed.
//
// Fix: maintain a parallel std::unordered_set<dword> breakpoint_addresses kept in sync
// with the breakpoints vector. Inner loop becomes:
//   breakpoint_addresses.count(_PC) != 0
// which is O(1) average.
//
// Compile: g++ -std=c++17 -O2 -o test_caprice32_0001 test_caprice32_0001.cpp
// Run:     ./test_caprice32_0001

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <unordered_set>
#include <vector>

typedef uint32_t dword;
typedef uint16_t word;

enum BreakpointType { NORMAL = 0, EPHEMERAL = 1 };

struct Breakpoint {
    Breakpoint(word val, BreakpointType t = NORMAL) : address(val), type(t) {}
    dword address;
    BreakpointType type;
};

// --- DEFECT: O(B) std::any_of scan per instruction ---
struct DefectLoop {
    std::vector<Breakpoint> breakpoints;

    void add(Breakpoint bp) { breakpoints.push_back(bp); }

    // Returns true if hit; scanned_out = number of entries examined.
    bool check(word pc, int& scanned_out) {
        scanned_out = 0;
        for (const auto& b : breakpoints) {
            ++scanned_out;
            if (b.address == pc) return true;
        }
        return false;
    }
};

// --- FIX: O(1) unordered_set lookup ---
struct FixedLoop {
    std::vector<Breakpoint> breakpoints;
    std::unordered_set<dword> breakpoint_addresses;

    void add(Breakpoint bp) {
        breakpoints.push_back(bp);
        breakpoint_addresses.insert(bp.address);
    }

    void remove_if(std::function<bool(const Breakpoint&)> pred) {
        for (const auto& bp : breakpoints) {
            if (pred(bp)) breakpoint_addresses.erase(bp.address);
        }
        breakpoints.erase(
            std::remove_if(breakpoints.begin(), breakpoints.end(), pred),
            breakpoints.end());
    }

    void remove_at(std::size_t idx) {
        breakpoint_addresses.erase(breakpoints[idx].address);
        breakpoints.erase(breakpoints.begin() + idx);
    }

    // Returns true if hit; scanned_out = 1 (hash probe) or 0 (fast no-match).
    bool check(word pc, int& scanned_out) {
        if (breakpoints.empty()) { scanned_out = 0; return false; }
        bool hit = (breakpoint_addresses.count(pc) != 0);
        scanned_out = 1; // one hash probe regardless of B
        return hit;
    }
};

static void test_defect_scans_all_on_miss() {
    const int B = 500;
    DefectLoop d;
    for (int i = 0; i < B; ++i)
        d.add(Breakpoint(word(0x1000 + i)));

    int scanned = 0;
    bool hit = d.check(0x0000, scanned);

    assert(!hit);
    assert(scanned == B && "defect: all B entries scanned for a miss");
    printf("PASS defect: %d breakpoints, PC miss -> scanned %d entries\n", B, scanned);
}

static void test_fix_constant_work_on_miss() {
    const int B = 500;
    FixedLoop f;
    for (int i = 0; i < B; ++i)
        f.add(Breakpoint(word(0x1000 + i)));

    int scanned = 0;
    bool hit = f.check(0x0000, scanned);

    assert(!hit);
    assert(scanned <= 1 && "fix: O(1) probe regardless of B");
    printf("PASS fix:    %d breakpoints, PC miss -> scanned %d entries (O(1))\n", B, scanned);
}

static void test_fix_detects_hit() {
    FixedLoop f;
    f.add(Breakpoint(0x0400));
    f.add(Breakpoint(0x0800));
    f.add(Breakpoint(0x0C00));

    int scanned = 0;
    bool hit = f.check(0x0800, scanned);

    assert(hit && "fix: should detect breakpoint at 0x0800");
    printf("PASS fix:    breakpoint at 0x0800 detected in %d probe(s)\n", scanned);
}

static void test_fix_remove_at_updates_set() {
    FixedLoop f;
    f.add(Breakpoint(0x0300));
    f.add(Breakpoint(0x0600));

    // Remove first breakpoint (index 0, address 0x0300).
    f.remove_at(0);

    int scanned = 0;
    bool hit = f.check(0x0300, scanned);
    assert(!hit && "fix: removed breakpoint should not fire");
    printf("PASS fix:    after remove, 0x0300 no longer hits\n");

    hit = f.check(0x0600, scanned);
    assert(hit && "fix: remaining breakpoint should still fire");
    printf("PASS fix:    remaining breakpoint 0x0600 still hits\n");
}

static void test_fix_ephemeral_remove() {
    FixedLoop f;
    f.add(Breakpoint(0x0200, EPHEMERAL));
    f.add(Breakpoint(0x0400, NORMAL));

    // Remove all ephemeral breakpoints (simulating RemoveEphemeralBreakpoints).
    f.remove_if([](const Breakpoint& bp) { return bp.type == EPHEMERAL; });

    int scanned = 0;
    bool hit = f.check(0x0200, scanned);
    assert(!hit && "fix: ephemeral breakpoint removed from set");

    hit = f.check(0x0400, scanned);
    assert(hit && "fix: normal breakpoint still present");
    printf("PASS fix:    ephemeral removal leaves normal breakpoint intact\n");
}

static void test_speedup_ratio() {
    const int B = 500;
    DefectLoop d;
    FixedLoop  f;
    for (int i = 0; i < B; ++i) {
        word addr = word(0x8000 + i);
        d.add(Breakpoint(addr));
        f.add(Breakpoint(addr));
    }

    int defect_scanned = 0, fix_scanned = 0;
    d.check(0x0000, defect_scanned);
    f.check(0x0000, fix_scanned);

    // Observed speedup ratio per-check.
    int ratio = defect_scanned; // fix_scanned is 1, so ratio ~= defect_scanned
    printf("PASS speedup: defect=%d scans/check, fix=%d scan/check, ratio ~%dx\n",
           defect_scanned, fix_scanned, ratio);
    assert(defect_scanned == B);
    assert(fix_scanned <= 1);
}

int main() {
    printf("--- caprice32-0001 CWE-407 breakpoint O(B) scan per Z80 instruction ---\n");
    test_defect_scans_all_on_miss();
    test_fix_constant_work_on_miss();
    test_fix_detects_hit();
    test_fix_remove_at_updates_set();
    test_fix_ephemeral_remove();
    test_speedup_ratio();
    printf("ALL PASS\n");
    return 0;
}