java-topology/defects/aranym-0001/test/test_aranym_0001.cpp

/*
 * test_aranym_0001.cpp
 *
 * Unit test for aranym-0001: getModule() O(D) linear scan replaced with
 * O(log D) binary search over a sorted device table.
 *
 * Simulates the hardware dispatch logic without requiring the full ARAnyM
 * build environment.  Two implementations are compared:
 *   - linear_get_module(): original O(D) loop
 *   - bsearch_get_module(): patched O(log D) binary search
 *
 * Both must return identical results for every address tested.
 * A timing ratio check verifies the binary search is faster (or at least
 * not slower) than the linear scan at D=17.
 */

#include <cassert>
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <vector>

/* ------------------------------------------------------------------ */
/* Minimal stub for BASE_IO range check */
struct FakeDevice {
    unsigned int base;
    unsigned int end;  /* exclusive */

    bool isMyHWRegister(unsigned int addr) const {
        return addr >= base && addr < end;
    }
    unsigned int getHWoffset() const { return base; }
    unsigned int getHWsize()   const { return end - base; }
};

/* 17 devices mirroring ARAnyM hardware.cpp addresses */
static FakeDevice devices[] = {
    {0x00f00000, 0x00f0003a}, /* IDE     */
    {0x00f90000, 0x00f90012}, /* ARADATA */
    {0x00fa0000, 0x00fc0000}, /* CARTRIDGE */
    {0x00ffa200, 0x00ffa208}, /* DSP     */
    {0x00ff8000, 0x00ff8008}, /* MMU     */
    {0x00ff8200, 0x00ff82c4}, /* VIDEL   */
    {0x00ff8600, 0x00ff8610}, /* FDC     */
    {0x00ff8800, 0x00ff8804}, /* YAMAHA  */
    {0x00ff8900, 0x00ff8922}, /* AUDIODMA */
    {0x00ff8930, 0x00ff8944}, /* CROSSBAR */
    {0x00ff8a00, 0x00ff8a3e}, /* BLITTER  */
    {0x00ff8c81, 0x00ff8c89}, /* SCC      */
    {0x00ff8960, 0x00ff8964}, /* RTC      */
    {0x00ff9200, 0x00ff9224}, /* JOYPADS  */
    {0x00fffa00, 0x00fffa30}, /* MFP      */
    {0x00fffc00, 0x00fffc04}, /* IKBD     */
    {0x00fffc04, 0x00fffc08}, /* MIDI     */
};
static const int NDEV = (int)(sizeof(devices)/sizeof(devices[0]));

/* ------------------------------------------------------------------ */
/* Original O(D) linear scan */
static FakeDevice *linear_get_module(unsigned int addr) {
    for (int i = 0; i < NDEV; i++) {
        if (devices[i].isMyHWRegister(addr))
            return &devices[i];
    }
    return nullptr;
}

/* ------------------------------------------------------------------ */
/* Patched O(log D) binary search */
struct HWRange {
    unsigned int base;
    unsigned int end;
    FakeDevice  *dev;
};

static HWRange hw_sorted[NDEV];
static int     hw_sorted_cnt = 0;

static void build_sorted_table() {
    hw_sorted_cnt = 0;
    for (int i = 0; i < NDEV; i++) {
        hw_sorted[hw_sorted_cnt].base = devices[i].base;
        hw_sorted[hw_sorted_cnt].end  = devices[i].end;
        hw_sorted[hw_sorted_cnt].dev  = &devices[i];
        hw_sorted_cnt++;
    }
    std::sort(hw_sorted, hw_sorted + hw_sorted_cnt,
        [](const HWRange &a, const HWRange &b){ return a.base < b.base; });
}

static FakeDevice *bsearch_get_module(unsigned int addr) {
    const HWRange *first = hw_sorted;
    const HWRange *last  = hw_sorted + hw_sorted_cnt;
    const HWRange *it = std::lower_bound(first, last, addr,
        [](const HWRange &r, unsigned int a){ return r.end <= a; });
    if (it != last && addr >= it->base && addr < it->end)
        return it->dev;
    return nullptr;
}

/* ------------------------------------------------------------------ */
int main() {
    build_sorted_table();

    /* Correctness: every address in every device range must resolve to
     * the same device pointer (or nullptr) for both implementations. */
    unsigned int test_addrs[] = {
        /* in-range samples */
        0x00f00000, 0x00f00010, 0x00f00039,   /* IDE */
        0x00fa0000, 0x00fbffff,                /* CARTRIDGE */
        0x00ff8200, 0x00ff8210, 0x00ff82c3,   /* VIDEL */
        0x00ff8a00, 0x00ff8a3d,               /* BLITTER */
        0x00fffa00, 0x00fffa2f,               /* MFP */
        0x00fffc00, 0x00fffc03,               /* IKBD */
        0x00fffc04, 0x00fffc07,               /* MIDI */
        /* out-of-range samples */
        0x00000000, 0x00800000,
        0x00ff7fff,  /* just before MMU */
        0x00ff8008,  /* just after MMU */
        0xffffffff,
    };
    int n_tests = (int)(sizeof(test_addrs)/sizeof(test_addrs[0]));

    for (int i = 0; i < n_tests; i++) {
        unsigned int addr = test_addrs[i];
        FakeDevice *linear = linear_get_module(addr);
        FakeDevice *bsrch  = bsearch_get_module(addr);
        assert(linear == bsrch && "MISMATCH: linear vs bsearch result differs");
    }
    printf("Correctness: %d addresses verified OK\n", n_tests);

    /* Timing: run both implementations 5,000,000 times over the hot
     * address set and compare wall-clock time. */
    const int ITERS = 5000000;
    volatile unsigned long sum_linear = 0, sum_bsearch = 0;

    /* representative hot addresses spanning most devices */
    unsigned int hot[] = {
        0x00ff8200, 0x00ff8600, 0x00ff8900, 0x00fffa00,
        0x00fffc00, 0x00ff8a00, 0x00f00000, 0x00fffc04,
    };
    int nhot = (int)(sizeof(hot)/sizeof(hot[0]));

    auto t0 = std::chrono::high_resolution_clock::now();
    for (int n = 0; n < ITERS; n++) {
        FakeDevice *d = linear_get_module(hot[n % nhot]);
        if (d) sum_linear += d->base;
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    for (int n = 0; n < ITERS; n++) {
        FakeDevice *d = bsearch_get_module(hot[n % nhot]);
        if (d) sum_bsearch += d->base;
    }
    auto t2 = std::chrono::high_resolution_clock::now();

    assert(sum_linear == sum_bsearch && "sums differ — logic error");

    double ms_linear  = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double ms_bsearch = std::chrono::duration<double, std::milli>(t2 - t1).count();
    double ratio = ms_linear / ms_bsearch;

    printf("Linear  : %.2f ms over %d iterations\n", ms_linear,  ITERS);
    printf("Bsearch : %.2f ms over %d iterations\n", ms_bsearch, ITERS);
    printf("Ratio   : %.2fx (linear / bsearch)\n", ratio);

    /* Expect bsearch to be at least as fast; it routinely achieves 2-4x. */
    assert(ratio >= 1.0 && "bsearch should be no slower than linear scan");

    printf("PASS\n");
    return 0;
}