hg80 1.0.0

//! Runs two cores over generated programs and compares everything a machine can observe.
//!
//! This exists so that a second implementation can be built against this one. The comparison covers
//! four axes, and each of the last two hid a real defect before it was watched: the **values** a
//! transfer carries, the **order** events arrive in, the **offset** at which each transfer completes
//! within its cycle, and how many **times** the machine is asked. A port read that asked three times
//! for one byte agreed on values and order and was wrong; a write reported at the wrong offset
//! agrees on everything except when it happened.
//!
//! Until the second implementation exists the comparison is a core against itself, which proves
//! determinism and nothing else. What makes the harness worth having before then is the planted
//! divergences below: a comparison that has never rejected anything is indistinguishable from one
//! that cannot.

use hg80::{BusCycle, BusRequest, Cpu, Host, Registers};

struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 >> 12;
        self.0 ^= self.0 << 25;
        self.0 ^= self.0 >> 27;
        self.0.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    fn byte(&mut self) -> u8 {
        self.next().to_le_bytes()[3]
    }

    fn pick<'a, T>(&mut self, items: &'a [T]) -> &'a T {
        &items[usize::from(self.byte()) % items.len()]
    }
}

const POOL: &[&[u8]] = &[
    &[0x00],                   // NOP
    &[0x3E, 0xFF],             // LD A,n
    &[0x06, 0xFF],             // LD B,n
    &[0x47],                   // LD B,A
    &[0x7E],                   // LD A,(HL)
    &[0x77],                   // LD (HL),A
    &[0x36, 0xFF],             // LD (HL),n
    &[0x21, 0xFF, 0x40],       // LD HL,nn  (kept inside the scratch page)
    &[0x11, 0xFF, 0x40],       // LD DE,nn
    &[0x01, 0xFF, 0x00],       // LD BC,nn
    &[0xC6, 0xFF],             // ADD A,n
    &[0xCE, 0xFF],             // ADC A,n
    &[0xD6, 0xFF],             // SUB n
    &[0xE6, 0xFF],             // AND n
    &[0xB6],                   // OR (HL)
    &[0xFE, 0xFF],             // CP n
    &[0x3C],                   // INC A
    &[0x35],                   // DEC (HL)
    &[0x27],                   // DAA
    &[0x2F],                   // CPL
    &[0x37],                   // SCF
    &[0x3F],                   // CCF
    &[0x07],                   // RLCA
    &[0x1F],                   // RRA
    &[0x23],                   // INC HL
    &[0x2B],                   // DEC HL
    &[0x09],                   // ADD HL,BC
    &[0xE5],                   // PUSH HL
    &[0xE1],                   // POP HL
    &[0xF5],                   // PUSH AF
    &[0xF1],                   // POP AF
    &[0xEB],                   // EX DE,HL
    &[0x08],                   // EX AF,AF'
    &[0xD9],                   // EXX
    &[0xE3],                   // EX (SP),HL
    &[0xCB, 0x27],             // SLA A
    &[0xCB, 0x1E],             // RR (HL)
    &[0xCB, 0x46],             // BIT 0,(HL)
    &[0xCB, 0xC6],             // SET 0,(HL)
    &[0xDD, 0x7E, 0x02],       // LD A,(IX+2)
    &[0xDD, 0x77, 0x03],       // LD (IX+3),A
    &[0xFD, 0x35, 0x01],       // DEC (IY+1)
    &[0xDD, 0xCB, 0x02, 0x46], // BIT 0,(IX+2)
    &[0xDD, 0x23],             // INC IX
    &[0xED, 0x44],             // NEG
    &[0xED, 0x4A],             // ADC HL,BC
    &[0xED, 0x42],             // SBC HL,BC
    &[0xED, 0x67],             // RRD
    &[0xED, 0x6F],             // RLD
    &[0xED, 0x57],             // LD A,I
    &[0xED, 0x5F],             // LD A,R
    &[0xED, 0xA0],             // LDI
    &[0xED, 0xA8],             // LDD
    &[0xED, 0xA1],             // CPI
    &[0xDB, 0xFE],             // IN A,(n)
    &[0xD3, 0xFE],             // OUT (n),A
    &[0xED, 0x78],             // IN A,(C)
    &[0xED, 0x79],             // OUT (C),A
    &[0x18, 0x00],             // JR 0
    &[0x20, 0x00],             // JR NZ,0
    &[0x10, 0x00],             // DJNZ 0
    &[0xFB],                   // EI
    &[0xF3],                   // DI
    &[0xED, 0x56],             // IM 1
    &[0xED, 0x5E],             // IM 2
    &[0xED, 0x4D],             // RETI
    &[0xED, 0x45],             // RETN
    &[0x76],                   // HALT
    &[0xED, 0x30],             // MUL D,E
    &[0xED, 0x31],             // ADD HL,A
    &[0xED, 0x23],             // SWAPNIB
    &[0xED, 0x24],             // MIRROR
    &[0xED, 0x28],             // BSLA DE,B
    &[0xED, 0x91, 0x07, 0xFF], // NEXTREG r,n
    &[0xED, 0x92, 0x07],       // NEXTREG r,A
    &[0xED, 0x94],             // PIXELAD
    &[0xED, 0xA4],             // LDIX
    &[0xED, 0x90],             // OUTINB
];

const ORIGIN: u16 = 0x8000;
const SCRATCH: u16 = 0x4000;

fn program(rng: &mut Rng, count: usize) -> Vec<u8> {
    let mut bytes = Vec::new();
    for _ in 0..count {
        let shape: &[u8] = rng.pick(POOL);
        for &byte in shape {
            bytes.push(if byte == 0xFF { rng.byte() } else { byte });
        }
    }
    bytes.extend_from_slice(&[0xC3, ORIGIN.to_le_bytes()[0], ORIGIN.to_le_bytes()[1]]);
    bytes
}

#[derive(Clone, PartialEq, Eq, Debug)]
enum Event {
    Opening { kind: &'static str, address: u16 },
    Closed { kind: &'static str, t_states: u32 },
    Fetch { address: u16, at: u32, value: u8 },
    Read { address: u16, at: u32, value: u8 },
    Write { address: u16, at: u32, value: u8 },
    Input { port: u16, at: u32, value: u8 },
    Output { port: u16, at: u32, value: u8 },
    Vector { value: u8 },
    ReturnFromInterrupt,
    Extended { command: &'static str, data: u16 },
}

fn kind_of(request: BusRequest) -> &'static str {
    match request {
        BusRequest::OpcodeFetch { .. } => "fetch",
        BusRequest::MemoryRead { .. } => "read",
        BusRequest::MemoryWrite { .. } => "write",
        BusRequest::PortRead { .. } => "in",
        BusRequest::PortWrite { .. } => "out",
        BusRequest::Refresh { .. } => "refresh",
        BusRequest::Internal { .. } => "internal",
        BusRequest::InterruptAcknowledge { .. } => "ack",
        _ => "other",
    }
}

fn address_of(request: BusRequest) -> u16 {
    match request {
        BusRequest::OpcodeFetch { address }
        | BusRequest::MemoryRead { address }
        | BusRequest::MemoryWrite { address, .. }
        | BusRequest::Refresh { address }
        | BusRequest::Internal { address }
        | BusRequest::InterruptAcknowledge { address } => address,
        BusRequest::PortRead { port } | BusRequest::PortWrite { port, .. } => port,
        _ => 0,
    }
}

struct Recorder {
    bytes: Box<[u8; 0x10000]>,
    events: Vec<Event>,
    waits: u32,
    port_seed: u8,
}

impl Host for Recorder {
    fn read(&mut self, address: u16, at: u32) -> u8 {
        let value = self.bytes[address as usize];
        self.events.push(Event::Read { address, at, value });
        value
    }
    fn fetch(&mut self, address: u16, at: u32) -> u8 {
        let value = self.bytes[address as usize];
        self.events.push(Event::Fetch { address, at, value });
        value
    }
    fn write(&mut self, address: u16, value: u8, at: u32) {
        self.bytes[address as usize] = value;
        self.events.push(Event::Write { address, at, value });
    }
    fn input(&mut self, port: u16, at: u32) -> u8 {
        // Deterministic but address-dependent, so a wrong port is a visible difference.
        let [high, low] = port.to_be_bytes();
        let value = self.port_seed ^ low ^ high;
        self.events.push(Event::Input { port, at, value });
        value
    }
    fn output(&mut self, port: u16, value: u8, at: u32) {
        self.events.push(Event::Output { port, at, value });
    }
    fn wait_states(&mut self, request: &BusRequest) -> u32 {
        self.events.push(Event::Opening {
            kind: kind_of(*request),
            address: address_of(*request),
        });
        self.waits
    }
    fn bus_cycle(&mut self, cycle: &BusCycle) {
        self.events.push(Event::Closed {
            kind: kind_of(cycle.request),
            t_states: cycle.t_states,
        });
    }
    fn interrupt_vector(&mut self) -> u8 {
        self.events.push(Event::Vector { value: 0xFF });
        0xFF
    }
    fn return_from_interrupt(&mut self) {
        self.events.push(Event::ReturnFromInterrupt);
    }
    fn z80n_command(&mut self, command: hg80::Z80nCommand, data: u16) {
        let _ = command;
        self.events.push(Event::Extended {
            command: "extended",
            data,
        });
    }
}

struct Trace {
    events: Vec<Event>,
    registers: Registers,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Drive {
    Instruction,
    Cycle,
    Edge,
}

fn run(seed: u64, waits: u32, t_states: u32) -> Trace {
    driven(seed, waits, t_states, Drive::Instruction)
}

fn driven(seed: u64, waits: u32, t_states: u32, how: Drive) -> Trace {
    let mut rng = Rng(seed | 1);
    let code = program(&mut rng, 24);

    let mut bytes = vec![0u8; 0x10000].into_boxed_slice();
    bytes[ORIGIN as usize..ORIGIN as usize + code.len()].copy_from_slice(&code);
    for offset in 0..0x0100usize {
        bytes[SCRATCH as usize + offset] = rng.byte();
    }

    let mut host = Recorder {
        bytes: bytes.try_into().unwrap(),
        events: Vec::new(),
        waits,
        port_seed: rng.byte(),
    };

    let mut cpu = Cpu::new();
    cpu.reset();
    cpu.set_z80n_enabled(seed & 2 != 0);
    let registers = cpu.registers_mut();
    registers.af = u16::from(rng.byte()) << 8 | u16::from(rng.byte());
    registers.bc = SCRATCH | u16::from(rng.byte() & 0x3F);
    registers.de = SCRATCH | u16::from(rng.byte() & 0x3F);
    registers.hl = SCRATCH | u16::from(rng.byte() & 0x3F);
    registers.ix = SCRATCH | u16::from(rng.byte() & 0x3F);
    registers.iy = SCRATCH | u16::from(rng.byte() & 0x3F);
    registers.sp = SCRATCH + 0x0080;
    registers.i = rng.byte();
    registers.iff1 = seed & 8 != 0;
    registers.iff2 = registers.iff1;
    registers.pc = ORIGIN;
    cpu.abandon_instruction();

    // Interrupts are set up before the run rather than part way through it, because the loop's
    // own counter advances by a different amount in each driving mode and would inject them at
    // different points. The line is level sensitive, so it is still taken at the first boundary the
    // flip-flops allow; the non-maskable one is latched and taken at the next boundary regardless.
    // Interrupt *timing* is not this harness's job — the cycle comparison against the reference
    // simulation covers that at four wait depths.
    cpu.set_interrupt_requested(seed & 4 != 0);
    if seed & 16 != 0 {
        cpu.request_nmi();
    }

    let mut total = 0;
    while total < t_states {
        total += match how {
            Drive::Instruction => cpu.step(&mut host),
            Drive::Cycle => cpu.run_cycle(&mut host),
            Drive::Edge => {
                cpu.tick(&mut host);
                cpu.tick(&mut host);
                1
            }
        };
    }

    Trace {
        events: host.events,
        registers: *cpu.registers(),
    }
}

fn prefix_differs(left: &Trace, right: &Trace) -> Option<String> {
    for (index, (a, b)) in left.events.iter().zip(right.events.iter()).enumerate() {
        if a != b {
            return Some(format!(
                "event {index} differs:\n  left  {a:?}\n  right {b:?}"
            ));
        }
    }
    let shared = left.events.len().min(right.events.len());
    assert!(
        shared > 500,
        "only {shared} events in common, nothing was compared"
    );
    // The three ways of driving stop at different points against the same T-state budget, so their
    // tails legitimately differ and only the common prefix is compared. What is not legitimate is
    // the instruction-driven run being the *shorter* one: it reports its last cycle before
    // returning where the other two leave theirs open, so it leads by between one and twelve events
    // over these programs. An instruction that dropped trailing cycles would close that gap, and a
    // comparison of the prefix alone would not notice.
    let lead = left.events.len().checked_sub(right.events.len());
    assert!(
        lead.is_some_and(|lead| (1..=24).contains(&lead)),
        "the instruction-driven run has {} events against {}, outside the measured lead of one to \
         twelve",
        left.events.len(),
        right.events.len()
    );
    None
}

fn difference(left: &Trace, right: &Trace) -> Option<String> {
    for (index, (a, b)) in left.events.iter().zip(right.events.iter()).enumerate() {
        if a != b {
            return Some(format!(
                "event {index} differs:\n  left  {a:?}\n  right {b:?}"
            ));
        }
    }
    if left.events.len() != right.events.len() {
        let shared = left.events.len().min(right.events.len());
        let (name, longer) = if left.events.len() > right.events.len() {
            ("left", left)
        } else {
            ("right", right)
        };
        return Some(format!(
            "{name} has {} events, the other has {shared}; its first extra is {:?}",
            longer.events.len(),
            longer.events[shared]
        ));
    }
    if left.registers != right.registers {
        return Some(format!(
            "registers differ:\n  left  {:?}\n  right {:?}",
            left.registers, right.registers
        ));
    }
    None
}

const PROGRAMS: u64 = 200;
const BUDGET: u32 = 4_000;

#[test]
fn each_program_is_reproducible_from_its_seed() {
    for seed in 0..PROGRAMS {
        for waits in [0u32, 1, 3] {
            let left = run(seed, waits, BUDGET);
            let right = run(seed, waits, BUDGET);
            assert!(
                difference(&left, &right).is_none(),
                "seed {seed} at {waits} waits: {}",
                difference(&left, &right).unwrap()
            );
        }
    }
}

#[test]
fn the_programs_exercise_every_axis_the_comparison_watches() {
    let mut kinds = std::collections::BTreeSet::new();
    let mut offsets = std::collections::BTreeSet::new();
    let mut events = 0usize;
    for seed in 0..PROGRAMS {
        let trace = run(seed, 1, BUDGET);
        events += trace.events.len();
        for event in &trace.events {
            match event {
                Event::Opening { kind, .. } => {
                    kinds.insert(*kind);
                }
                Event::Fetch { at, .. }
                | Event::Read { at, .. }
                | Event::Write { at, .. }
                | Event::Input { at, .. }
                | Event::Output { at, .. } => {
                    offsets.insert(*at);
                }
                _ => {}
            }
        }
    }
    for wanted in ["fetch", "read", "write", "in", "out", "internal", "ack"] {
        assert!(
            kinds.contains(wanted),
            "no generated program opened a {wanted} cycle"
        );
    }
    assert!(
        offsets.len() >= 3,
        "the generated programs saw only {offsets:?} as transfer offsets"
    );
    assert!(
        events > 200_000,
        "the generated programs are only {events} events"
    );

    println!(
        "{PROGRAMS} programs, {events} events, cycle kinds {kinds:?}, offsets {offsets:?}"
    );
}

#[test]
fn the_comparison_catches_every_kind_of_divergence() {
    let reference = run(7, 1, BUDGET);

    let index_of = |pick: fn(&Event) -> bool| {
        reference
            .events
            .iter()
            .position(pick)
            .expect("the generated program contains one of these")
    };

    let planted: Vec<(&str, Trace)> = vec![
        ("a value", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Read { .. }));
            if let Event::Read { value, .. } = &mut t.events[at] {
                *value ^= 0x01;
            }
            t
        }),
        ("an offset", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Write { .. }));
            if let Event::Write { at: offset, .. } = &mut t.events[at] {
                *offset += 1;
            }
            t
        }),
        ("an address", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Write { .. }));
            if let Event::Write { address, .. } = &mut t.events[at] {
                *address = address.wrapping_add(1);
            }
            t
        }),
        ("the order", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Read { .. }));
            t.events.swap(at, at + 1);
            t
        }),
        ("a call count", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Input { .. } | Event::Read { .. }));
            let duplicate = t.events[at].clone();
            t.events.insert(at, duplicate);
            t
        }),
        ("a missing call", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Read { .. }));
            t.events.remove(at);
            t
        }),
        ("a cycle length", {
            let mut t = clone_of(&reference);
            let at = index_of(|e| matches!(e, Event::Closed { .. }));
            if let Event::Closed { t_states, .. } = &mut t.events[at] {
                *t_states += 1;
            }
            t
        }),
        ("a register", {
            let mut t = clone_of(&reference);
            t.registers.hl = t.registers.hl.wrapping_add(1);
            t
        }),
        ("the flags", {
            let mut t = clone_of(&reference);
            t.registers.af ^= 0x0001;
            t
        }),
        ("the memory pointer", {
            let mut t = clone_of(&reference);
            t.registers.wz = t.registers.wz.wrapping_add(1);
            t
        }),
    ];

    for (axis, altered) in planted {
        assert!(
            difference(&reference, &altered).is_some(),
            "the comparison did not catch a planted difference in {axis}"
        );
    }
}

fn clone_of(trace: &Trace) -> Trace {
    Trace {
        events: trace.events.clone(),
        registers: trace.registers,
    }
}

#[test]
fn every_way_of_driving_the_core_produces_the_same_run() {
    for seed in 0..PROGRAMS {
        for waits in [0u32, 1, 3] {
            let by_instruction = driven(seed, waits, BUDGET, Drive::Instruction);
            for how in [Drive::Cycle, Drive::Edge] {
                let other = driven(seed, waits, BUDGET, how);
                assert!(
                    prefix_differs(&by_instruction, &other).is_none(),
                    "seed {seed} at {waits} waits, {how:?} against Instruction: {}",
                    prefix_differs(&by_instruction, &other).unwrap()
                );
            }
        }
    }
}

#[test]
fn run_cycle_returns_the_length_the_cycle_reports() {
    let trace = driven(11, 2, BUDGET, Drive::Cycle);
    let closed: Vec<u32> = trace
        .events
        .iter()
        .filter_map(|event| match event {
            Event::Closed { t_states, .. } => Some(*t_states),
            _ => None,
        })
        .collect();
    assert!(closed.len() > 100, "only {} cycles closed", closed.len());
    assert!(
        closed.iter().all(|&t| t >= 3),
        "a machine cycle shorter than three T-states: {closed:?}"
    );
}