nes_sim/

ppu.rs

use crate::cartridge::TVSystem;
use crate::savestate::{SaveStateError, StateReader, StateWriter};

pub const FRAME_WIDTH: usize = 256;
pub const FRAME_HEIGHT: usize = 240;
const VISIBLE_FRAME_PIXELS: usize = FRAME_WIDTH * FRAME_HEIGHT;

const STATUS_SPRITE_OVERFLOW: u8 = 0x20;
const STATUS_SPRITE_ZERO_HIT: u8 = 0x40;
const STATUS_VBLANK: u8 = 0x80;
const MASK_GRAYSCALE: u8 = 0x01;
const MASK_SHOW_BG_LEFTMOST: u8 = 0x02;
const MASK_SHOW_SPRITES_LEFTMOST: u8 = 0x04;
const MASK_SHOW_BG: u8 = 0x08;
const MASK_SHOW_SPRITES: u8 = 0x10;
const CTRL_SPRITE_TABLE: u8 = 0x08;
const CTRL_BG_TABLE: u8 = 0x10;
const CTRL_VRAM_INCREMENT: u8 = 0x04;
const CTRL_SPRITE_SIZE: u8 = 0x20;
const CTRL_NMI_ENABLE: u8 = 0x80;
const DOTS_PER_SCANLINE: u16 = 341;
const VISIBLE_SCANLINES: i16 = 240;

#[cfg(test)]
const NES_RGB_PALETTE: [[u8; 3]; 64] = [
    [84, 84, 84],
    [0, 30, 116],
    [8, 16, 144],
    [48, 0, 136],
    [68, 0, 100],
    [92, 0, 48],
    [84, 4, 0],
    [60, 24, 0],
    [32, 42, 0],
    [8, 58, 0],
    [0, 64, 0],
    [0, 60, 0],
    [0, 50, 60],
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
    [152, 150, 152],
    [8, 76, 196],
    [48, 50, 236],
    [92, 30, 228],
    [136, 20, 176],
    [160, 20, 100],
    [152, 34, 32],
    [120, 60, 0],
    [84, 90, 0],
    [40, 114, 0],
    [8, 124, 0],
    [0, 118, 40],
    [0, 102, 120],
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
    [236, 238, 236],
    [76, 154, 236],
    [120, 124, 236],
    [176, 98, 236],
    [228, 84, 236],
    [236, 88, 180],
    [236, 106, 100],
    [212, 136, 32],
    [160, 170, 0],
    [116, 196, 0],
    [76, 208, 32],
    [56, 204, 108],
    [56, 180, 204],
    [60, 60, 60],
    [0, 0, 0],
    [0, 0, 0],
    [236, 238, 236],
    [168, 204, 236],
    [188, 188, 236],
    [212, 178, 236],
    [236, 174, 236],
    [236, 174, 212],
    [236, 180, 176],
    [228, 196, 144],
    [204, 210, 120],
    [180, 222, 120],
    [168, 226, 144],
    [152, 226, 180],
    [160, 214, 228],
    [160, 162, 160],
    [0, 0, 0],
    [0, 0, 0],
];

pub trait PPUBus {
    fn ppu_read(&mut self, addr: u16) -> u8;
    fn ppu_write(&mut self, addr: u16, data: u8);
    fn check_a12(&mut self, _addr: u16, _ppu_cycle: u64) {}
    fn notify_scanline(&mut self, _scanline: i16, _rendering_on: bool) {}
    fn set_ppu_sprite_phase(&mut self, _sprite_phase: bool) {}
}

#[derive(Clone, Copy)]
struct SpriteRenderData {
    tile_id: u8,
    row: u8,
    x: u8,
    attributes: u8,
    pattern_lo: u8,
    pattern_hi: u8,
    sprite_zero: bool,
}

impl Default for SpriteRenderData {
    fn default() -> Self {
        Self {
            tile_id: 0xFF,
            row: 0,
            x: 0xFF,
            attributes: 0xFF,
            pattern_lo: 0,
            pattern_hi: 0,
            sprite_zero: false,
        }
    }
}

pub struct PPU {
    scanline: i16,
    cycles: u16,
    frame: u64,

    oam: [u8; 256],
    oam_addr: u8,

    ctrl: u8,
    mask: u8,
    status: u8,
    open_bus: u8,
    vram_addr: u16,
    temp_vram_addr: u16,
    fine_x: u8,
    write_latch: bool,
    read_buffer: u8,
    odd_frame: bool,
    next_tile_id: u8,
    next_tile_attr: u8,
    next_tile_lsb: u8,
    next_tile_msb: u8,
    bg_pattern_shift_lo: u16,
    bg_pattern_shift_hi: u16,
    bg_attr_shift_lo: u16,
    bg_attr_shift_hi: u16,

    // parameters
    tv_system: TVSystem,
    num_scanlines: i16,
    vblank_lines: i16,

    loopy_v: u16,
    loopy_t: u16,
    bit_map: [u8; 0xF000],
    bg_colors: [u8; 0x100],
    bg_pixels: [u8; 0x100],
    sprite_present: [bool; 0x100],
    sprite_behind_bg: [bool; 0x100],
    scanline_sprites: [SpriteRenderData; 8],
    scanline_sprite_count: u8,
    suppress_vblank: bool,

    even: bool,
    dot_clock: u64,

    // Cached rendering state (updated when mask register is written)
    bg_on: bool,
    sprites_on: bool,
    rendering_on: bool,
}

impl PPU {
    pub fn new() -> Self {
        Self {
            oam: [0; 256],
            oam_addr: 0,
            frame: 0,
            ctrl: 0,
            mask: 0,
            status: 0,
            open_bus: 0,
            vram_addr: 0,
            temp_vram_addr: 0,
            fine_x: 0,
            write_latch: false,
            read_buffer: 0,
            scanline: 261,
            cycles: 0,
            odd_frame: false,
            next_tile_id: 0,
            next_tile_attr: 0,
            next_tile_lsb: 0,
            next_tile_msb: 0,
            bg_pattern_shift_lo: 0,
            bg_pattern_shift_hi: 0,
            bg_attr_shift_lo: 0,
            bg_attr_shift_hi: 0,
            tv_system: TVSystem::NTSC,
            num_scanlines: 262,
            vblank_lines: 241,

            loopy_v: 0,
            loopy_t: 0,
            bit_map: [0; 0xF000],
            bg_colors: [0; 0x100],
            bg_pixels: [0; 0x100],
            sprite_present: [false; 0x100],
            sprite_behind_bg: [false; 0x100],
            scanline_sprites: [SpriteRenderData::default(); 8],
            scanline_sprite_count: 0,
            suppress_vblank: false,

            even: false,
            dot_clock: 0,

            bg_on: false,
            sprites_on: false,
            rendering_on: false,
        }
    }

    pub fn reset(&mut self) {
        self.ctrl = 0;
        self.mask = 0;
        self.update_rendering_flags();
        self.status &= !(STATUS_SPRITE_OVERFLOW | STATUS_SPRITE_ZERO_HIT | STATUS_VBLANK);
        self.open_bus = 0;
        self.vram_addr = 0;
        self.temp_vram_addr = 0;
        self.fine_x = 0;
        self.write_latch = false;
        self.read_buffer = 0;
        self.scanline = 261;
        self.cycles = 0;
        self.frame = 0;
        self.odd_frame = false;
        self.next_tile_id = 0;
        self.next_tile_attr = 0;
        self.next_tile_lsb = 0;
        self.next_tile_msb = 0;
        self.bg_pattern_shift_lo = 0;
        self.bg_pattern_shift_hi = 0;
        self.bg_attr_shift_lo = 0;
        self.bg_attr_shift_hi = 0;
        self.set_current_vram_addr(0);
        self.set_temp_vram_addr(0);
        self.bg_pixels = [0; 0x100];
        self.sprite_present = [false; 0x100];
        self.sprite_behind_bg = [false; 0x100];
        self.scanline_sprites = [SpriteRenderData::default(); 8];
        self.scanline_sprite_count = 0;
        self.suppress_vblank = false;
        self.dot_clock = 0;
    }

    pub fn set_parameters(&mut self, tv_system: TVSystem) {
        self.tv_system = tv_system;
        match tv_system {
            TVSystem::NTSC => {
                self.num_scanlines = 262;
                self.vblank_lines = 241;
            }
            TVSystem::PAL => {
                self.num_scanlines = 312;
                self.vblank_lines = 241;
            }
            TVSystem::DENDY => {
                self.num_scanlines = 312;
                self.vblank_lines = 241;
            }
        }
    }

    #[cfg(test)]
    pub fn cpu_read_register(&mut self, bus: &mut impl PPUBus, addr: u16) -> u8 {
        self.cpu_read_register_timed(bus, addr, 0)
    }

    pub fn cpu_read_register_timed(
        &mut self,
        bus: &mut impl PPUBus,
        addr: u16,
        cpu_cycle_offset: u8,
    ) -> u8 {
        match addr {
            0x2002 => self.read_status_timed(cpu_cycle_offset),
            0x2004 => {
                let data = self.read_oam_data();
                self.open_bus = data;
                data
            }
            0x2007 => self.read_data(bus),
            _ => self.open_bus,
        }
    }

    #[cfg(test)]
    pub fn cpu_write_register(&mut self, bus: &mut impl PPUBus, addr: u16, data: u8) {
        self.cpu_write_register_timed(bus, addr, data, 0);
    }

    pub fn cpu_write_register_timed(
        &mut self,
        bus: &mut impl PPUBus,
        addr: u16,
        data: u8,
        cpu_cycle_offset: u8,
    ) {
        self.open_bus = data;
        let (future_scanline, _, _) = self.predict_status_timing(u16::from(cpu_cycle_offset) * 3);

        match addr {
            0x2000 => {
                self.ctrl = data;
                self.set_temp_vram_addr(
                    (self.temp_vram_addr & !0x0C00) | (((data as u16) & 0x03) << 10),
                );
            }
            0x2001 => {
                self.mask = data;
                self.update_rendering_flags();
            }
            0x2003 => self.oam_addr = data,
            0x2004 => self.write_oam_data_timed(data, future_scanline),
            0x2005 => self.write_scroll(data),
            0x2006 => self.write_addr(data),
            0x2007 => self.write_data_timed(bus, data, future_scanline),
            _ => {}
        }
    }

    pub fn clock(&mut self, bus: &mut impl PPUBus) {
        // Vblank 快速路径：跳过所有渲染检查
        if self.scanline >= self.vblank_lines && self.scanline < self.num_scanlines - 1 {
            if self.scanline == self.vblank_lines && self.cycles == 1 && !self.suppress_vblank {
                self.status |= STATUS_VBLANK;
            }
            self.cycles += 1;
            if self.cycles >= DOTS_PER_SCANLINE {
                self.cycles = 0;
                self.scanline += 1;
                bus.notify_scanline(self.scanline, false);
            }
            self.dot_clock = self.dot_clock.wrapping_add(1);
            return;
        }

        let visible_scanline = self.scanline < VISIBLE_SCANLINES;
        let pre_render_scanline = self.scanline == self.num_scanlines - 1;
        let render_scanline = visible_scanline || pre_render_scanline;
        let visible_cycle = self.cycles < 256;
        let fetch_cycle = visible_cycle || (320..337).contains(&self.cycles);

        if self.scanline == self.num_scanlines - 1 && self.cycles == 1 {
            self.status &= !(STATUS_SPRITE_OVERFLOW | STATUS_SPRITE_ZERO_HIT | STATUS_VBLANK);
            self.suppress_vblank = false;
        }

        if render_scanline && self.rendering_on() {
            if visible_scanline && self.cycles == 0 {
                self.sprite_present = [false; 0x100];
                self.sprite_behind_bg = [false; 0x100];
            }

            if self.bg_on() && fetch_cycle {
                self.update_bg_shifters();
                bus.set_ppu_sprite_phase(false);
                self.fetch_bg(bus);
            }

            if visible_scanline && visible_cycle {
                self.draw_bg_pixel(self.cycles as i16, bus);
                self.draw_sprite_pixel(self.cycles as i16, bus);
            }

            match self.cycles {
                255 => self.increment_y(),
                256 => {
                    self.load_bg_shifters();
                    self.transfer_x();
                    if self.rendering_on() && (visible_scanline || pre_render_scanline) {
                        self.eval_sprites(bus);
                    }
                }
                279..=303 if pre_render_scanline => self.transfer_y(),
                _ => {}
            }

            if (257..321).contains(&self.cycles) {
                bus.set_ppu_sprite_phase(true);
                self.fetch_sprite_data(bus);
            }
        }

        if self.should_skip_odd_frame_cycle(pre_render_scanline) {
            self.dot_clock = self.dot_clock.wrapping_add(1);
            self.start_next_frame();
            return;
        }

        self.cycles += 1;
        if self.cycles >= DOTS_PER_SCANLINE {
            self.cycles = 0;
            self.scanline += 1;
            bus.notify_scanline(self.scanline, self.rendering_on());

            if self.scanline >= self.num_scanlines {
                self.start_next_frame();
            }
        }
        self.dot_clock = self.dot_clock.wrapping_add(1);
    }

    pub fn bg_on(&self) -> bool {
        self.bg_on
    }

    pub fn sprites_on(&self) -> bool {
        self.sprites_on
    }

    pub fn rendering_on(&self) -> bool {
        self.rendering_on
    }

    fn update_rendering_flags(&mut self) {
        self.bg_on = (self.mask & MASK_SHOW_BG) != 0;
        self.sprites_on = (self.mask & MASK_SHOW_SPRITES) != 0;
        self.rendering_on = self.bg_on || self.sprites_on;
    }

    pub fn nmi_line(&self) -> bool {
        (self.ctrl & CTRL_NMI_ENABLE) != 0 && (self.status & STATUS_VBLANK) != 0
    }

    pub fn in_vblank(&self) -> bool {
        (self.status & STATUS_VBLANK) != 0
    }

    pub fn scanline(&self) -> i16 {
        self.scanline
    }

    pub fn frame(&self) -> u64 {
        self.frame
    }

    pub fn frame_pixels(&self) -> &[u8] {
        &self.bit_map[..VISIBLE_FRAME_PIXELS]
    }

    #[cfg(test)]
    pub fn frame_rgb(&self) -> Vec<u8> {
        let mut rgb = Vec::with_capacity(VISIBLE_FRAME_PIXELS * 3);
        for &pixel in self.frame_pixels() {
            rgb.extend_from_slice(&palette_index_to_rgb(pixel));
        }
        rgb
    }

    pub fn tv_system(&self) -> TVSystem {
        self.tv_system
    }

    pub(crate) fn write_oam_dma(&mut self, data: u8) {
        self.write_oam_data(data);
    }

    #[cfg(test)]
    pub fn oam_byte(&self, index: u8) -> u8 {
        self.oam[index as usize]
    }

    pub fn oam_addr(&self) -> u8 {
        self.oam_addr
    }

    pub(crate) fn save_state(&self, writer: &mut StateWriter) {
        writer.write_i16(self.scanline);
        writer.write_u16(self.cycles);
        writer.write_u64(self.frame);
        writer.write_bytes(&self.oam);
        writer.write_u8(self.oam_addr);
        writer.write_u8(self.ctrl);
        writer.write_u8(self.mask);
        writer.write_u8(self.status);
        writer.write_u8(self.open_bus);
        writer.write_u16(self.vram_addr);
        writer.write_u16(self.temp_vram_addr);
        writer.write_u8(self.fine_x);
        writer.write_bool(self.write_latch);
        writer.write_u8(self.read_buffer);
        writer.write_bool(self.odd_frame);
        writer.write_u8(self.next_tile_id);
        writer.write_u8(self.next_tile_attr);
        writer.write_u8(self.next_tile_lsb);
        writer.write_u8(self.next_tile_msb);
        writer.write_u16(self.bg_pattern_shift_lo);
        writer.write_u16(self.bg_pattern_shift_hi);
        writer.write_u16(self.bg_attr_shift_lo);
        writer.write_u16(self.bg_attr_shift_hi);
        writer.write_u8(match self.tv_system {
            TVSystem::NTSC => 0,
            TVSystem::PAL => 1,
            TVSystem::DENDY => 2,
        });
        writer.write_i16(self.num_scanlines);
        writer.write_i16(self.vblank_lines);
        writer.write_u16(self.loopy_v);
        writer.write_u16(self.loopy_t);
        writer.write_bytes(&self.bit_map);
        writer.write_bytes(&self.bg_colors);
        writer.write_bytes(&self.bg_pixels);
        for &present in &self.sprite_present {
            writer.write_bool(present);
        }
        for &behind in &self.sprite_behind_bg {
            writer.write_bool(behind);
        }
        for sprite in &self.scanline_sprites {
            writer.write_u8(sprite.tile_id);
            writer.write_u8(sprite.row);
            writer.write_u8(sprite.x);
            writer.write_u8(sprite.attributes);
            writer.write_u8(sprite.pattern_lo);
            writer.write_u8(sprite.pattern_hi);
            writer.write_bool(sprite.sprite_zero);
        }
        writer.write_u8(self.scanline_sprite_count);
        writer.write_bool(self.suppress_vblank);
        writer.write_bool(self.even);
        writer.write_u64(self.dot_clock);
    }

    pub(crate) fn load_state(
        &mut self,
        reader: &mut StateReader<'_>,
    ) -> Result<(), SaveStateError> {
        self.scanline = reader.read_i16()?;
        self.cycles = reader.read_u16()?;
        self.frame = reader.read_u64()?;
        reader.read_bytes_into(&mut self.oam)?;
        self.oam_addr = reader.read_u8()?;
        self.ctrl = reader.read_u8()?;
        self.mask = reader.read_u8()?;
        self.status = reader.read_u8()?;
        self.open_bus = reader.read_u8()?;
        self.vram_addr = reader.read_u16()?;
        self.temp_vram_addr = reader.read_u16()?;
        self.fine_x = reader.read_u8()?;
        self.write_latch = reader.read_bool()?;
        self.read_buffer = reader.read_u8()?;
        self.odd_frame = reader.read_bool()?;
        self.next_tile_id = reader.read_u8()?;
        self.next_tile_attr = reader.read_u8()?;
        self.next_tile_lsb = reader.read_u8()?;
        self.next_tile_msb = reader.read_u8()?;
        self.bg_pattern_shift_lo = reader.read_u16()?;
        self.bg_pattern_shift_hi = reader.read_u16()?;
        self.bg_attr_shift_lo = reader.read_u16()?;
        self.bg_attr_shift_hi = reader.read_u16()?;
        self.tv_system = match reader.read_u8()? {
            0 => TVSystem::NTSC,
            1 => TVSystem::PAL,
            2 => TVSystem::DENDY,
            _ => {
                return Err(SaveStateError::InvalidData(
                    "invalid TV system in PPU state",
                ));
            }
        };
        self.num_scanlines = reader.read_i16()?;
        self.vblank_lines = reader.read_i16()?;
        self.loopy_v = reader.read_u16()?;
        self.loopy_t = reader.read_u16()?;
        reader.read_bytes_into(&mut self.bit_map)?;
        reader.read_bytes_into(&mut self.bg_colors)?;
        reader.read_bytes_into(&mut self.bg_pixels)?;
        for present in &mut self.sprite_present {
            *present = reader.read_bool()?;
        }
        for behind in &mut self.sprite_behind_bg {
            *behind = reader.read_bool()?;
        }
        for sprite in &mut self.scanline_sprites {
            sprite.tile_id = reader.read_u8()?;
            sprite.row = reader.read_u8()?;
            sprite.x = reader.read_u8()?;
            sprite.attributes = reader.read_u8()?;
            sprite.pattern_lo = reader.read_u8()?;
            sprite.pattern_hi = reader.read_u8()?;
            sprite.sprite_zero = reader.read_bool()?;
        }
        self.scanline_sprite_count = reader.read_u8()?;
        self.suppress_vblank = reader.read_bool()?;
        self.even = reader.read_bool()?;
        self.dot_clock = reader.read_u64()?;
        self.update_rendering_flags();
        Ok(())
    }

    fn read_status_timed(&mut self, cpu_cycle_offset: u8) -> u8 {
        let ppu_cycle_offset = u16::from(cpu_cycle_offset) * 3;
        let (future_scanline, future_cycles, future_status) =
            self.predict_status_timing(ppu_cycle_offset);

        let mut status_bits = future_status;
        // Only apply imminent sprite-0-hit lookahead for sub-cycle peeks.
        // Wider lookahead windows were causing unstable split timing in games
        // that poll PPUSTATUS at instruction-level granularity.
        if cpu_cycle_offset <= 1
            && (status_bits & STATUS_SPRITE_ZERO_HIT) == 0
            && self.predict_sprite_zero_hit_within_offset(ppu_cycle_offset)
        {
            status_bits |= STATUS_SPRITE_ZERO_HIT;
        }
        if future_scanline == self.vblank_lines && future_cycles == 1 {
            status_bits &= !STATUS_VBLANK;
            self.suppress_vblank = true;
        }

        let status = (status_bits & 0xE0) | (self.open_bus & 0x1F);
        self.status &= !STATUS_VBLANK;
        self.write_latch = false;
        self.open_bus = status;
        status
    }

    fn predict_status_timing(&self, ppu_cycle_offset: u16) -> (i16, u16, u8) {
        let mut scanline = self.scanline;
        let mut cycles = self.cycles;
        let mut odd_frame = self.odd_frame;
        let mut status = self.status;
        let mut suppress_vblank = self.suppress_vblank;

        for _ in 0..ppu_cycle_offset {
            if scanline == self.vblank_lines && cycles == 1 && !suppress_vblank {
                status |= STATUS_VBLANK;
            }

            if scanline == self.num_scanlines - 1 && cycles == 1 {
                status &= !(STATUS_SPRITE_OVERFLOW | STATUS_SPRITE_ZERO_HIT | STATUS_VBLANK);
                suppress_vblank = false;
            }

            let pre_render_scanline = scanline == self.num_scanlines - 1;
            let skip_odd_frame_cycle = self.num_scanlines == 262
                && pre_render_scanline
                && self.rendering_on()
                && odd_frame
                && cycles == DOTS_PER_SCANLINE - 2;

            if skip_odd_frame_cycle {
                scanline = 0;
                cycles = 0;
                odd_frame = !odd_frame;
                continue;
            }

            cycles += 1;
            if cycles >= DOTS_PER_SCANLINE {
                cycles = 0;
                scanline += 1;
                if scanline >= self.num_scanlines {
                    scanline = 0;
                    odd_frame = !odd_frame;
                }
            }
        }

        (scanline, cycles, status)
    }

    fn predict_sprite_zero_hit_within_offset(&self, ppu_cycle_offset: u16) -> bool {
        if ppu_cycle_offset == 0
            || !self.bg_on()
            || !self.sprites_on()
            || self.scanline < 0
            || self.scanline >= VISIBLE_SCANLINES
        {
            return false;
        }

        let Some(sprite) = self
            .scanline_sprites
            .iter()
            .take(self.scanline_sprite_count as usize)
            .find(|sprite| sprite.sprite_zero)
            .copied()
        else {
            return false;
        };

        let mut cycles = self.cycles;
        let mut scanline = self.scanline;
        let mut odd_frame = self.odd_frame;

        let mut bg_pattern_shift_lo = self.bg_pattern_shift_lo;
        let mut bg_pattern_shift_hi = self.bg_pattern_shift_hi;
        let mut bg_attr_shift_lo = self.bg_attr_shift_lo;
        let mut bg_attr_shift_hi = self.bg_attr_shift_hi;

        let show_leftmost_bg = (self.mask & MASK_SHOW_BG_LEFTMOST) != 0;
        let show_leftmost_sprites = (self.mask & MASK_SHOW_SPRITES_LEFTMOST) != 0;

        for _ in 0..ppu_cycle_offset {
            let visible_scanline = scanline < VISIBLE_SCANLINES;
            let pre_render_scanline = scanline == self.num_scanlines - 1;
            let render_scanline = visible_scanline || pre_render_scanline;
            let visible_cycle = cycles < 256;
            let fetch_cycle = visible_cycle || (320..337).contains(&cycles);

            if render_scanline && self.rendering_on() {
                if visible_scanline && visible_cycle {
                    let x = cycles as usize;

                    let bg_pixel = if show_leftmost_bg || x >= 8 {
                        let bit = 0x8000 >> self.fine_x;
                        let lo = u8::from((bg_pattern_shift_lo & bit) != 0);
                        let hi = u8::from((bg_pattern_shift_hi & bit) != 0);
                        (hi << 1) | lo
                    } else {
                        0
                    };

                    if (show_leftmost_sprites || x >= 8) && x < 255 {
                        let sprite_x = usize::from(sprite.x);
                        if x >= sprite_x && x < sprite_x + 8 {
                            let sprite_pixel = self.sprite_pixel(&sprite, (x - sprite_x) as u8);
                            if sprite_pixel != 0 && bg_pixel != 0 {
                                return true;
                            }
                        }
                    }
                }

                if self.bg_on() && fetch_cycle {
                    bg_pattern_shift_lo <<= 1;
                    bg_pattern_shift_hi <<= 1;
                    bg_attr_shift_lo <<= 1;
                    bg_attr_shift_hi <<= 1;
                }

                if self.bg_on() && fetch_cycle && (cycles & 0x07) == 0 {
                    bg_pattern_shift_lo =
                        (bg_pattern_shift_lo & 0xFF00) | u16::from(self.next_tile_lsb);
                    bg_pattern_shift_hi =
                        (bg_pattern_shift_hi & 0xFF00) | u16::from(self.next_tile_msb);

                    let attr_lo = if (self.next_tile_attr & 0x01) != 0 {
                        0xFF
                    } else {
                        0x00
                    };
                    let attr_hi = if (self.next_tile_attr & 0x02) != 0 {
                        0xFF
                    } else {
                        0x00
                    };

                    bg_attr_shift_lo = (bg_attr_shift_lo & 0xFF00) | attr_lo;
                    bg_attr_shift_hi = (bg_attr_shift_hi & 0xFF00) | attr_hi;
                }
            }

            let skip_odd_frame_cycle = self.num_scanlines == 262
                && pre_render_scanline
                && self.rendering_on()
                && odd_frame
                && cycles == DOTS_PER_SCANLINE - 2;

            if skip_odd_frame_cycle {
                scanline = 0;
                cycles = 0;
                odd_frame = !odd_frame;
                continue;
            }

            cycles += 1;
            if cycles >= DOTS_PER_SCANLINE {
                cycles = 0;
                scanline += 1;
                if scanline >= self.num_scanlines {
                    scanline = 0;
                    odd_frame = !odd_frame;
                }
            }
        }

        false
    }

    fn read_data(&mut self, bus: &mut impl PPUBus) -> u8 {
        let addr = self.loopy_v & 0x3FFF;
        let data = if addr >= 0x3F00 {
            self.read_buffer = self.ppu_read_bus(bus, addr.wrapping_sub(0x1000));
            let palette_data = self.ppu_read_bus(bus, addr);
            self.mask_palette_color(palette_data)
        } else {
            let buffered = self.read_buffer;
            self.read_buffer = self.ppu_read_bus_exposed(bus, addr);
            buffered
        };

        self.increment_data_access_vram_addr();
        self.open_bus = data;
        data
    }

    fn write_data_timed(&mut self, bus: &mut impl PPUBus, data: u8, effective_scanline: i16) {
        let addr = self.loopy_v & 0x3FFF;
        self.ppu_write_bus_exposed(bus, addr, data);
        self.increment_data_access_vram_addr_on_scanline(effective_scanline);
    }

    fn write_scroll(&mut self, data: u8) {
        if !self.write_latch {
            self.fine_x = data & 0x07;
            self.set_temp_vram_addr((self.temp_vram_addr & !0x001F) | ((data as u16) >> 3));
            self.write_latch = true;
        } else {
            self.set_temp_vram_addr(
                (self.temp_vram_addr & !0x73E0)
                    | ((((data as u16) >> 3) & 0x1F) << 5)
                    | (((data as u16) & 0x07) << 12),
            );
            self.write_latch = false;
        }
    }

    fn write_addr(&mut self, data: u8) {
        if !self.write_latch {
            self.set_temp_vram_addr((self.temp_vram_addr & 0x00FF) | (((data as u16) & 0x3F) << 8));
            self.write_latch = true;
        } else {
            self.set_temp_vram_addr((self.temp_vram_addr & 0x7F00) | data as u16);
            self.set_current_vram_addr(self.temp_vram_addr);
            self.write_latch = false;
        }
    }

    fn increment_vram_addr(&mut self) {
        let increment = if (self.ctrl & CTRL_VRAM_INCREMENT) != 0 {
            32
        } else {
            1
        };
        self.set_current_vram_addr(self.loopy_v.wrapping_add(increment));
    }

    fn increment_data_access_vram_addr_on_scanline(&mut self, scanline: i16) {
        if self.rendering_vram_access_active_on_scanline(scanline) {
            self.increment_x();
            self.increment_y();
        } else {
            self.increment_vram_addr();
        }
    }

    fn increment_data_access_vram_addr(&mut self) {
        self.increment_data_access_vram_addr_on_scanline(self.scanline);
    }

    fn write_oam_data(&mut self, data: u8) {
        self.write_oam_data_timed(data, self.scanline);
    }

    fn write_oam_data_timed(&mut self, data: u8, effective_scanline: i16) {
        if self.rendering_oam_access_active_on_scanline(effective_scanline) {
            self.oam_addr = self.oam_addr.wrapping_add(4);
            return;
        }

        self.oam[self.oam_addr as usize] = data;
        self.oam_addr = self.oam_addr.wrapping_add(1);
    }

    fn read_oam_data(&self) -> u8 {
        if self.rendering_oam_clear_phase() {
            return 0xFF;
        }

        let data = self.oam[self.oam_addr as usize];
        if (self.oam_addr & 0x03) == 0x02 {
            data & 0xE3
        } else {
            data
        }
    }

    fn fetch_bg(&mut self, bus: &mut impl PPUBus) {
        match self.cycles & 0x07 {
            0 => {
                self.load_bg_shifters();
                self.fetch_nt(bus);
            }
            2 => {
                let addr = 0x23C0
                    | (self.loopy_v & 0x0C00)
                    | ((self.loopy_v >> 4) & 0x38)
                    | ((self.loopy_v >> 2) & 0x07);
                let attr = self.ppu_read_bus(bus, addr);
                let shift = ((self.loopy_v >> 4) & 0x04) | (self.loopy_v & 0x02);
                self.next_tile_attr = (attr >> shift) as u8 & 0x03;
            }
            4 => {
                let addr = self.bg_pattern_addr(self.next_tile_id);
                self.next_tile_lsb = self.ppu_read_bus_exposed(bus, addr);
            }
            6 => {
                let addr = self.bg_pattern_addr(self.next_tile_id).wrapping_add(8);
                self.next_tile_msb = self.ppu_read_bus_exposed(bus, addr);
            }
            7 => self.increment_x(),
            _ => {}
        }
    }

    fn fetch_nt(&mut self, bus: &mut impl PPUBus) {
        let addr = 0x2000 | (self.loopy_v & 0x0FFF);
        self.next_tile_id = self.ppu_read_bus(bus, addr);
    }

    fn eval_sprites(&mut self, _bus: &mut impl PPUBus) {
        let target_scanline = if self.scanline == self.num_scanlines - 1 {
            0
        } else {
            (self.scanline as u8).wrapping_add(1)
        };

        self.scanline_sprites = [SpriteRenderData::default(); 8];
        self.scanline_sprite_count = 0;

        let sprite_height = self.sprite_height();
        let mut overflow_start = None;
        for index in 0..64 {
            let row = match self.sprite_row_for_scanline(index, target_scanline, sprite_height) {
                Some(row) => row,
                None => continue,
            };

            if self.scanline_sprite_count >= 8 {
                overflow_start = Some(index);
                break;
            }

            let base = index * 4;
            let tile = self.oam[base + 1];
            let attributes = self.oam[base + 2];
            let x = self.oam[base + 3];

            self.scanline_sprites[self.scanline_sprite_count as usize] = SpriteRenderData {
                tile_id: tile,
                row,
                x,
                attributes,
                pattern_lo: 0,
                pattern_hi: 0,
                sprite_zero: index == 0,
            };
            self.scanline_sprite_count += 1;

            if self.scanline_sprite_count >= 8 {
                overflow_start = Some(index + 1);
                break;
            }
        }

        if let Some(start_index) = overflow_start {
            if self.sprite_overflow_bugged(start_index, target_scanline, sprite_height) {
                self.status |= STATUS_SPRITE_OVERFLOW;
            }
        }
    }

    fn sprite_row_for_scanline(
        &self,
        sprite_index: usize,
        target_scanline: u8,
        sprite_height: u8,
    ) -> Option<u8> {
        let sprite_y = self.oam[sprite_index * 4];
        let sprite_top = if sprite_y == 0xFF {
            0
        } else {
            u16::from(sprite_y) + 1
        };
        let target = u16::from(target_scanline);
        if target < sprite_top {
            None
        } else {
            let row = target - sprite_top;
            if row >= u16::from(sprite_height) {
                None
            } else {
                Some(row as u8)
            }
        }
    }

    fn sprite_overflow_bugged(
        &self,
        start_index: usize,
        target_scanline: u8,
        sprite_height: u8,
    ) -> bool {
        let mut n = start_index;
        let mut m = 0usize;
        while n < 64 {
            let value = self.oam[n * 4 + m];
            let sprite_top = if value == 0xFF {
                0
            } else {
                u16::from(value) + 1
            };
            let target = u16::from(target_scanline);
            if target >= sprite_top && (target - sprite_top) < u16::from(sprite_height) {
                return true;
            }

            n += 1;
            m = (m + 1) & 0x03;
        }

        false
    }

    fn fetch_sprite_data(&mut self, bus: &mut impl PPUBus) {
        let slot = ((self.cycles - 257) / 8) as usize;
        if slot >= 8 {
            return;
        }

        let subcycle = (self.cycles - 257) & 0x07;
        match subcycle {
            0 | 2 => {
                let _ = self.ppu_read_bus(bus, 0x2000 | (self.loopy_v & 0x0FFF));
            }
            4 => {
                let sprite = self.scanline_sprites[slot];
                let addr = self.sprite_pattern_addr(sprite.tile_id, sprite.attributes, sprite.row);
                self.scanline_sprites[slot].pattern_lo = self.ppu_read_bus_exposed(bus, addr);
            }
            6 => {
                let sprite = self.scanline_sprites[slot];
                let addr = self
                    .sprite_pattern_addr(sprite.tile_id, sprite.attributes, sprite.row)
                    .wrapping_add(8);
                self.scanline_sprites[slot].pattern_hi = self.ppu_read_bus_exposed(bus, addr);
            }
            _ => {}
        }
    }

    fn draw_bg_pixel(&mut self, offset: i16, bus: &mut impl PPUBus) {
        let x = offset as usize;
        let y = self.scanline as usize;
        if x >= 256 || y >= VISIBLE_SCANLINES as usize {
            return;
        }

        let show_leftmost = (self.mask & MASK_SHOW_BG_LEFTMOST) != 0;
        let bg_pixel = if self.bg_on() && (show_leftmost || x >= 8) {
            self.current_bg_pixel()
        } else {
            0
        };
        let bg_palette = if bg_pixel == 0 {
            0
        } else {
            self.current_bg_palette()
        };

        let palette_addr = if bg_pixel == 0 {
            0x3F00
        } else {
            0x3F00 | (u16::from(bg_palette) << 2) | u16::from(bg_pixel)
        };
        let palette_data = self.ppu_read_bus(bus, palette_addr);
        let color = self.mask_palette_color(palette_data);
        let pixel_index = y * 256 + x;

        let sprite_in_front = self.sprite_present[x] && !self.sprite_behind_bg[x];
        let sprite_visible_behind_bg =
            self.sprite_present[x] && self.sprite_behind_bg[x] && bg_pixel == 0;
        if !sprite_in_front && !sprite_visible_behind_bg {
            self.bit_map[pixel_index] = color;
        }
        self.bg_colors[x] = color;
        self.bg_pixels[x] = bg_pixel;
    }

    fn draw_sprite_pixel(&mut self, offset: i16, bus: &mut impl PPUBus) {
        if !self.sprites_on() {
            return;
        }

        let x = offset as usize;
        let y = self.scanline as usize;
        if x >= 256 || y >= VISIBLE_SCANLINES as usize {
            return;
        }

        if x < 8 && (self.mask & MASK_SHOW_SPRITES_LEFTMOST) == 0 {
            return;
        }

        for sprite in self
            .scanline_sprites
            .iter()
            .take(self.scanline_sprite_count as usize)
            .copied()
        {
            let sprite_x = usize::from(sprite.x);
            if x < sprite_x || x >= sprite_x + 8 {
                continue;
            }

            let sprite_pixel = self.sprite_pixel(&sprite, (x - sprite_x) as u8);
            if sprite_pixel == 0 {
                continue;
            }

            let bg_pixel_for_hit = self.bg_pixel_visible_for_sprite_zero_hit(x);
            if sprite.sprite_zero && bg_pixel_for_hit != 0 && x < 255 {
                self.status |= STATUS_SPRITE_ZERO_HIT;
            }

            let bg_pixel_visible = self.bg_pixel_visible_to_sprite(x);
            let behind_background = (sprite.attributes & 0x20) != 0;
            if behind_background && bg_pixel_visible != 0 {
                break;
            }

            let palette = sprite.attributes & 0x03;
            let palette_addr = 0x3F10 | (u16::from(palette) << 2) | u16::from(sprite_pixel);
            let palette_data = self.ppu_read_bus(bus, palette_addr);
            let color = self.mask_palette_color(palette_data);
            self.bit_map[y * 256 + x] = color;
            self.sprite_present[x] = true;
            self.sprite_behind_bg[x] = behind_background;
            break;
        }
    }

    fn set_current_vram_addr(&mut self, addr: u16) {
        self.vram_addr = addr;
        self.loopy_v = addr;
    }

    fn set_temp_vram_addr(&mut self, addr: u16) {
        self.temp_vram_addr = addr;
        self.loopy_t = addr;
    }

    fn should_skip_odd_frame_cycle(&self, pre_render_scanline: bool) -> bool {
        self.num_scanlines == 262
            && pre_render_scanline
            && self.rendering_on()
            && self.odd_frame
            && self.cycles == DOTS_PER_SCANLINE - 2
    }

    fn rendering_vram_access_active_on_scanline(&self, scanline: i16) -> bool {
        self.rendering_on() && (scanline < VISIBLE_SCANLINES || scanline == self.num_scanlines - 1)
    }

    fn rendering_oam_access_active(&self) -> bool {
        self.rendering_oam_access_active_on_scanline(self.scanline)
    }

    fn rendering_oam_access_active_on_scanline(&self, scanline: i16) -> bool {
        self.rendering_on() && scanline < VISIBLE_SCANLINES
    }

    fn rendering_oam_clear_phase(&self) -> bool {
        self.rendering_oam_access_active() && (1..=64).contains(&self.cycles)
    }

    fn start_next_frame(&mut self) {
        self.scanline = 0;
        self.cycles = 0;
        self.frame += 1;
        self.odd_frame = !self.odd_frame;
        self.even = !self.even;
    }

    fn ppu_read_bus(&mut self, bus: &mut impl PPUBus, addr: u16) -> u8 {
        let addr = addr & 0x3FFF;
        self.observe_mapper_a12_line(bus, addr);
        bus.ppu_read(addr)
    }

    fn ppu_read_bus_exposed(&mut self, bus: &mut impl PPUBus, addr: u16) -> u8 {
        let addr = addr & 0x3FFF;
        self.observe_mapper_a12_line(bus, addr);
        bus.ppu_read(addr)
    }

    fn ppu_write_bus_exposed(&mut self, bus: &mut impl PPUBus, addr: u16, data: u8) {
        let addr = addr & 0x3FFF;
        self.observe_mapper_a12_line(bus, addr);
        bus.ppu_write(addr, data);
    }

    fn observe_mapper_a12_line(&mut self, bus: &mut impl PPUBus, addr: u16) {
        match addr {
            0x0000..=0x1FFF => bus.check_a12(addr, self.dot_clock),
            // MMC3 watches the PPU A12 line itself, so nametable/attribute/garbage fetches
            // still drive the line low even though they must not create CHR high pulses.
            0x2000..=0x2FFF => bus.check_a12(0x0000, self.dot_clock),
            _ => {}
        }
    }

    fn bg_pattern_addr(&self, tile_id: u8) -> u16 {
        let table = if (self.ctrl & CTRL_BG_TABLE) != 0 {
            0x1000
        } else {
            0x0000
        };
        let fine_y = (self.loopy_v >> 12) & 0x0007;
        table | (u16::from(tile_id) << 4) | fine_y
    }

    fn sprite_pattern_addr(&self, tile_id: u8, attributes: u8, row: u8) -> u16 {
        let mut fine_y = u16::from(row);
        let sprite_height = u16::from(self.sprite_height());
        if (attributes & 0x80) != 0 {
            fine_y = sprite_height - 1 - fine_y;
        }

        if sprite_height == 16 {
            let table = u16::from(tile_id & 0x01) << 12;
            let tile = u16::from(tile_id & 0xFE) + (fine_y >> 3);
            table | (tile << 4) | (fine_y & 0x07)
        } else {
            let table = if (self.ctrl & CTRL_SPRITE_TABLE) != 0 {
                0x1000
            } else {
                0x0000
            };
            table | (u16::from(tile_id) << 4) | fine_y
        }
    }

    fn sprite_height(&self) -> u8 {
        if (self.ctrl & CTRL_SPRITE_SIZE) != 0 {
            16
        } else {
            8
        }
    }

    fn sprite_pixel(&self, sprite: &SpriteRenderData, offset: u8) -> u8 {
        let bit = if (sprite.attributes & 0x40) != 0 {
            offset
        } else {
            7 - offset
        };
        let lo = (sprite.pattern_lo >> bit) & 0x01;
        let hi = (sprite.pattern_hi >> bit) & 0x01;
        (hi << 1) | lo
    }

    fn mask_palette_color(&self, color: u8) -> u8 {
        let color = color & 0x3F;
        if (self.mask & MASK_GRAYSCALE) != 0 {
            color & 0x30
        } else {
            color
        }
    }

    fn update_bg_shifters(&mut self) {
        if !self.bg_on() {
            return;
        }

        self.bg_pattern_shift_lo <<= 1;
        self.bg_pattern_shift_hi <<= 1;
        self.bg_attr_shift_lo <<= 1;
        self.bg_attr_shift_hi <<= 1;
    }

    fn load_bg_shifters(&mut self) {
        self.bg_pattern_shift_lo =
            (self.bg_pattern_shift_lo & 0xFF00) | u16::from(self.next_tile_lsb);
        self.bg_pattern_shift_hi =
            (self.bg_pattern_shift_hi & 0xFF00) | u16::from(self.next_tile_msb);

        let attr_lo = if (self.next_tile_attr & 0x01) != 0 {
            0xFF
        } else {
            0x00
        };
        let attr_hi = if (self.next_tile_attr & 0x02) != 0 {
            0xFF
        } else {
            0x00
        };

        self.bg_attr_shift_lo = (self.bg_attr_shift_lo & 0xFF00) | attr_lo;
        self.bg_attr_shift_hi = (self.bg_attr_shift_hi & 0xFF00) | attr_hi;
    }

    fn current_bg_pixel(&self) -> u8 {
        let bit = 0x8000 >> self.fine_x;
        let lo = u8::from((self.bg_pattern_shift_lo & bit) != 0);
        let hi = u8::from((self.bg_pattern_shift_hi & bit) != 0);
        (hi << 1) | lo
    }

    fn current_bg_palette(&self) -> u8 {
        let bit = 0x8000 >> self.fine_x;
        let lo = u8::from((self.bg_attr_shift_lo & bit) != 0);
        let hi = u8::from((self.bg_attr_shift_hi & bit) != 0);
        (hi << 1) | lo
    }

    fn bg_pixel_visible_to_sprite(&self, x: usize) -> u8 {
        // draw_bg_pixel runs before draw_sprite_pixel in the same cycle and
        // writes the committed BG pixel value into bg_pixels[x], so the sprite
        // priority check can use it directly — no shift-register lookahead needed.
        self.bg_pixels[x]
    }

    fn bg_pixel_visible_for_sprite_zero_hit(&self, x: usize) -> u8 {
        if !self.bg_on() {
            return 0;
        }

        let show_leftmost = (self.mask & MASK_SHOW_BG_LEFTMOST) != 0;
        if !show_leftmost && x < 8 {
            return 0;
        }

        let bit = 0x8000 >> self.fine_x;
        let lo = u8::from((self.bg_pattern_shift_lo & bit) != 0);
        let hi = u8::from((self.bg_pattern_shift_hi & bit) != 0);
        (hi << 1) | lo
    }

    fn increment_x(&mut self) {
        if !self.rendering_on() {
            return;
        }

        if (self.loopy_v & 0x001F) == 31 {
            self.loopy_v &= !0x001F;
            self.loopy_v ^= 0x0400;
        } else {
            self.loopy_v = self.loopy_v.wrapping_add(1);
        }

        self.vram_addr = self.loopy_v;
    }

    fn increment_y(&mut self) {
        if !self.rendering_on() {
            return;
        }

        if (self.loopy_v & 0x7000) != 0x7000 {
            self.loopy_v = self.loopy_v.wrapping_add(0x1000);
        } else {
            self.loopy_v &= !0x7000;
            let mut coarse_y = (self.loopy_v & 0x03E0) >> 5;
            if coarse_y == 29 {
                coarse_y = 0;
                self.loopy_v ^= 0x0800;
            } else if coarse_y == 31 {
                coarse_y = 0;
            } else {
                coarse_y += 1;
            }
            self.loopy_v = (self.loopy_v & !0x03E0) | (coarse_y << 5);
        }

        self.vram_addr = self.loopy_v;
    }

    fn transfer_x(&mut self) {
        if !self.rendering_on() {
            return;
        }

        self.loopy_v = (self.loopy_v & !0x041F) | (self.loopy_t & 0x041F);
        self.vram_addr = self.loopy_v;
    }

    fn transfer_y(&mut self) {
        if !self.rendering_on() {
            return;
        }

        self.loopy_v = (self.loopy_v & !0x7BE0) | (self.loopy_t & 0x7BE0);
        self.vram_addr = self.loopy_v;
    }
}

#[cfg(test)]
pub(crate) fn palette_index_to_rgb(index: u8) -> [u8; 3] {
    NES_RGB_PALETTE[(index & 0x3F) as usize]
}

impl Default for PPU {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests;