1//! SH7604 CPU cache
2//!
3//! This is a 4-way set-associative cache that uses a pseudo-LRU algorithm for cache replacement.
4//!
5//! Cache replacement is performed when a cached read misses. The cache is write-through, so writes
6//! will only update cache if there is a cache hit.
7//!
8//! Games that are known to depend on CPU cache emulation (specifically data cache):
9//! * WWF Raw (32X) writes to cartridge ROM addresses and expects to be able to read back the written
10//!   values from CPU cache. Without cache, it won't correctly populate 32X palette RAM which causes
11//!   missing graphics in menus.
12//! * Pitfall: The Mayan Adventure (32X) writes to addresses around $00090000 (out-of-bounds in boot
13//!   ROM area) and expects to be able to read back the written values from CPU cache. Without cache,
14//!   objects/"sprites" that are partially offscreen will not display at all until they are entirely
15//!   onscreen.
16
17use crate::debug::CacheDebugState;
18use bincode::{Decode, Encode};
19use jgenesis_common::boxedarray::BoxedWordArray;
20use jgenesis_common::debug::{DebugMemoryView, DebugWordsView, Endian};
21use jgenesis_common::num::{GetBit, U16Ext};
22use std::array;
23
24const CACHE_RAM_LEN_WORDS: usize = 4 * 1024 / 2;
25
26const WAYS: usize = 4;
27
28// Cache lines are 16 bytes and there are 4 ways in each cache line
29// 4096 / 16 / 4 = 64
30const CACHE_ENTRIES: usize = 64;
31
32#[derive(Debug, Clone, Default, Encode, Decode)]
33pub struct CacheControlRegister {
34    // Specifies which way is accessed when the address array is accessed directly
35    pub way: u8,
36    pub mode: CacheMode,
37    pub disable_data_replacement: bool,
38    pub disable_instruction_replacement: bool,
39    pub cache_enabled: bool,
40}
41
42impl CacheControlRegister {
43    fn read(&self) -> u8 {
44        (self.way << 6)
45            | ((self.mode as u8) << 3)
46            | (u8::from(self.disable_data_replacement) << 2)
47            | (u8::from(self.disable_instruction_replacement) << 1)
48            | u8::from(self.cache_enabled)
49    }
50
51    fn write(&mut self, value: u8) {
52        self.way = value >> 6;
53        self.mode = CacheMode::from_bit(value.bit(3));
54        self.disable_data_replacement = value.bit(2);
55        self.disable_instruction_replacement = value.bit(1);
56        self.cache_enabled = value.bit(0);
57
58        log::trace!("CCR write: {value:02X}");
59        log::trace!("  Way specification: {}", self.way);
60        log::trace!("  Cache mode: {:?}", self.mode);
61        log::trace!("  Cache purged: {}", value.bit(4));
62        log::trace!("  Disable data replacement: {}", self.disable_data_replacement);
63        log::trace!("  Disable instruction replacement: {}", self.disable_instruction_replacement);
64        log::trace!("  Cache enabled: {}", self.cache_enabled);
65    }
66}
67
68#[derive(Debug, Clone, Encode, Decode)]
69struct Way {
70    // Tag is address bits 10-28
71    tags: [u32; CACHE_ENTRIES],
72    valid_bits: u64,
73}
74
75impl Way {
76    fn new() -> Self {
77        Self { tags: array::from_fn(|_| 0), valid_bits: 0 }
78    }
79}
80
81#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Encode, Decode)]
82pub enum CacheMode {
83    #[default]
84    FourWay = 0,
85    TwoWay = 1,
86}
87
88impl CacheMode {
89    fn from_bit(bit: bool) -> Self {
90        if bit { Self::TwoWay } else { Self::FourWay }
91    }
92}
93
94#[derive(Debug, Clone, Encode, Decode)]
95pub struct CpuCache {
96    // Store cache as u16s because the most common fetches are opcodes which are 16-bit
97    ram: BoxedWordArray<CACHE_RAM_LEN_WORDS>,
98    ways: Box<[Way; WAYS]>,
99    lru_bits: [u8; CACHE_ENTRIES],
100    control: CacheControlRegister,
101}
102
103impl CpuCache {
104    pub fn new() -> Self {
105        Self {
106            ram: BoxedWordArray::new(),
107            ways: Box::new(array::from_fn(|_| Way::new())),
108            lru_bits: array::from_fn(|_| 0),
109            control: CacheControlRegister::default(),
110        }
111    }
112
113    pub fn read_u8(&mut self, address: u32) -> Option<u8> {
114        self.cache_read(address, move |cache, way_idx, entry_idx| {
115            let address = cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xF);
116            cache.ram[address >> 1].to_be_bytes()[address & 1]
117        })
118    }
119
120    #[inline(always)]
121    pub fn read_u16(&mut self, address: u32) -> Option<u16> {
122        self.cache_read(address, move |cache, way_idx, entry_idx| {
123            let address = cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xE);
124            cache.ram[address >> 1]
125        })
126    }
127
128    pub fn read_u32(&mut self, address: u32) -> Option<u32> {
129        self.cache_read(address, move |cache, way_idx, entry_idx| {
130            let address = (cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xC)) >> 1;
131            let high_word = cache.ram[address];
132            let low_word = cache.ram[address + 1];
133            (u32::from(high_word) << 16) | u32::from(low_word)
134        })
135    }
136
137    #[inline(always)]
138    fn cache_read<T>(
139        &mut self,
140        address: u32,
141        read_fn: impl FnOnce(&Self, usize, usize) -> T,
142    ) -> Option<T> {
143        if !self.control.cache_enabled {
144            return None;
145        }
146
147        let entry_idx = cache_entry_index(address);
148        let tag = tag_address(address);
149
150        // Iterate in reverse for slightly better performance when cache is in 2-way mode.
151        // Per SH7604 documentation, all 4 ways are checked even in 2-way mode; 2-way mode only
152        // changes replacement behavior
153        for way_idx in (0..4).rev() {
154            if self.ways[way_idx].valid_bits.bit(entry_idx as u8)
155                && self.ways[way_idx].tags[entry_idx] == tag
156            {
157                self.update_lru_bits(way_idx, entry_idx);
158                return Some(read_fn(self, way_idx, entry_idx));
159            }
160        }
161
162        None
163    }
164
165    pub fn peek(&self, address: u32) -> Option<u16> {
166        if !self.control.cache_enabled {
167            return None;
168        }
169
170        let entry_idx = cache_entry_index(address);
171        let tag = tag_address(address);
172
173        for way_idx in (0..4).rev() {
174            if self.ways[way_idx].valid_bits.bit(entry_idx as u8)
175                && self.ways[way_idx].tags[entry_idx] == tag
176            {
177                let address = cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xE);
178                return Some(self.ram[address >> 1]);
179            }
180        }
181
182        None
183    }
184
185    pub fn peek_data_array(&self, address: u32) -> u16 {
186        self.ram[((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1)]
187    }
188
189    #[inline]
190    pub fn should_replace_instruction(&self) -> bool {
191        self.control.cache_enabled && !self.control.disable_instruction_replacement
192    }
193
194    #[inline]
195    pub fn should_replace_data(&self) -> bool {
196        self.control.cache_enabled && !self.control.disable_data_replacement
197    }
198
199    #[must_use]
200    pub fn replace(&mut self, address: u32, cache_line: [u16; 8]) -> u32 {
201        let entry_idx = cache_entry_index(address);
202
203        let lru_bits = self.lru_bits[entry_idx];
204        let way_idx = match self.control.mode {
205            CacheMode::FourWay => {
206                usize::from(lru_bits & 0b100110 == 0b000110)
207                    | (usize::from(lru_bits & 0b010101 == 0b000001) << 1)
208                    | (3 * usize::from(lru_bits & 0b001011 == 0))
209            }
210            CacheMode::TwoWay => {
211                if lru_bits.bit(0) {
212                    2
213                } else {
214                    3
215                }
216            }
217        };
218
219        self.ways[way_idx].tags[entry_idx] = tag_address(address);
220        self.ways[way_idx].valid_bits |= 1 << entry_idx;
221        self.update_lru_bits(way_idx, entry_idx);
222
223        let ram_addr = cache_ram_addr(way_idx, entry_idx) >> 1;
224        self.ram[ram_addr..ram_addr + 8].copy_from_slice(&cache_line);
225
226        let cache_line_addr = ((address >> 1) & 7 & !1) as usize;
227        let high: u32 = cache_line[cache_line_addr].into();
228        let low: u32 = cache_line[cache_line_addr + 1].into();
229        low | (high << 16)
230    }
231
232    #[inline(always)]
233    fn update_lru_bits(&mut self, way_idx: usize, entry_idx: usize) {
234        // Bit 5: 0 -> 1
235        // Bit 4: 0 -> 2
236        // Bit 3: 0 -> 3
237        // Bit 2: 1 -> 2
238        // Bit 1: 1 -> 3
239        // Bit 0: 2 -> 3
240        let (and_mask, or_mask) = match way_idx {
241            // Clear bits 5-3
242            0 => (!0b111000, 0b000000),
243            // Clear bits 2-1 and set bit 5
244            1 => (!0b000110, 0b100000),
245            // Clear bit 0 and set bits 4 and 2
246            2 => (!0b000001, 0b010100),
247            // Set bits 3, 1, and 0
248            3 => (!0b000000, 0b001011),
249            _ => panic!("Invalid way index, should be 0-3: {way_idx}"),
250        };
251
252        self.lru_bits[entry_idx] &= and_mask;
253        self.lru_bits[entry_idx] |= or_mask;
254    }
255
256    pub fn write_through_u8(&mut self, address: u32, value: u8) {
257        self.cache_write_through(address, move |cache, way_idx, entry_idx| {
258            let address = cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xF);
259            if !address.bit(0) {
260                cache.ram[address >> 1].set_msb(value);
261            } else {
262                cache.ram[address >> 1].set_lsb(value);
263            }
264        });
265    }
266
267    pub fn write_through_u16(&mut self, address: u32, value: u16) {
268        self.cache_write_through(address, move |cache, way_idx, entry_idx| {
269            let address = cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xE);
270            cache.ram[address >> 1] = value;
271        });
272    }
273
274    pub fn write_through_u32(&mut self, address: u32, value: u32) {
275        self.cache_write_through(address, move |cache, way_idx, entry_idx| {
276            let address = (cache_ram_addr(way_idx, entry_idx) | ((address as usize) & 0xC)) >> 1;
277            cache.ram[address] = (value >> 16) as u16;
278            cache.ram[address + 1] = value as u16;
279        });
280    }
281
282    fn cache_write_through(&mut self, address: u32, set_fn: impl FnOnce(&mut Self, usize, usize)) {
283        if !self.control.cache_enabled {
284            return;
285        }
286
287        let entry_idx = cache_entry_index(address);
288        let tag = tag_address(address);
289
290        // Iterate in reverse for slightly better performance when cache is in 2-way mode
291        for way_idx in (0..4).rev() {
292            if self.ways[way_idx].valid_bits.bit(entry_idx as u8)
293                && self.ways[way_idx].tags[entry_idx] == tag
294            {
295                self.update_lru_bits(way_idx, entry_idx);
296                set_fn(self, way_idx, entry_idx);
297                return;
298            }
299        }
300    }
301
302    // $FFFFFE92: CCR (Cache control register)
303    pub fn read_control(&self) -> u8 {
304        self.control.read()
305    }
306
307    // $FFFFFE92: CCR (Cache control register)
308    pub fn write_control(&mut self, value: u8) {
309        self.control.write(value);
310
311        if value.bit(4) {
312            self.purge_all();
313        }
314    }
315
316    pub fn purge_all(&mut self) {
317        for way in self.ways.as_mut() {
318            way.valid_bits = 0;
319        }
320
321        self.lru_bits.fill(0);
322    }
323
324    // A29-31 = 010
325    pub fn associative_purge(&mut self, address: u32) {
326        // Invalidates a single cache line
327        let idx = cache_entry_index(address);
328        let mask = !(1 << idx);
329        for way in self.ways.as_mut() {
330            way.valid_bits &= mask;
331        }
332
333        // TODO should associative purge clear the LRU bits?
334        self.lru_bits[idx] = 0;
335    }
336
337    // A29-31 = 011
338    pub fn read_address_array(&self, address: u32) -> u32 {
339        let entry_idx = cache_entry_index(address);
340        let way_idx = self.control.way as usize;
341
342        (u32::from(self.ways[way_idx].valid_bits.bit(entry_idx as u8)) << 1)
343            | (u32::from(self.lru_bits[entry_idx]) << 3)
344            | (self.ways[way_idx].tags[entry_idx] << 10)
345    }
346
347    // A29-31 = 011
348    pub fn write_address_array(&mut self, address: u32, value: u32) {
349        let entry_idx = cache_entry_index(address);
350        let way_idx = self.control.way as usize;
351        let tag = tag_address(address);
352        let valid = address.bit(1);
353        let lru_bits = ((value >> 3) & 0x3F) as u8;
354
355        if valid {
356            self.ways[way_idx].valid_bits |= 1 << entry_idx;
357        } else {
358            self.ways[way_idx].valid_bits &= !(1 << entry_idx);
359        }
360
361        self.ways[way_idx].tags[entry_idx] = tag;
362        self.lru_bits[entry_idx] = lru_bits;
363    }
364
365    // A29-31 = 110
366    pub fn read_data_array_u8(&self, address: u32) -> u8 {
367        let word = self.ram[((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1)];
368        word.to_be_bytes()[(address & 1) as usize]
369    }
370
371    // A29-31 = 110
372    pub fn read_data_array_u16(&self, address: u32) -> u16 {
373        self.ram[((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1)]
374    }
375
376    // A29-31 = 110
377    pub fn read_data_array_u32(&self, address: u32) -> u32 {
378        let address = ((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1) & !1;
379        let high_word = self.ram[address];
380        let low_word = self.ram[address + 1];
381        (u32::from(high_word) << 16) | u32::from(low_word)
382    }
383
384    // A29-31 = 110
385    pub fn write_data_array_u8(&mut self, address: u32, value: u8) {
386        let word_addr = ((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1);
387        if !address.bit(0) {
388            self.ram[word_addr].set_msb(value);
389        } else {
390            self.ram[word_addr].set_lsb(value);
391        }
392    }
393
394    // A29-31 = 110
395    pub fn write_data_array_u16(&mut self, address: u32, value: u16) {
396        self.ram[((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1)] = value;
397    }
398
399    // A29-31 = 110
400    pub fn write_data_array_u32(&mut self, address: u32, value: u32) {
401        let address = ((address >> 1) as usize) & (CACHE_RAM_LEN_WORDS - 1) & !1;
402        self.ram[address] = (value >> 16) as u16;
403        self.ram[address + 1] = value as u16;
404    }
405
406    pub fn debug_view(&mut self) -> impl DebugMemoryView {
407        DebugWordsView(self.ram.as_mut_slice(), Endian::Big)
408    }
409
410    pub(crate) fn debug_state(&self) -> CacheDebugState {
411        CacheDebugState {
412            enabled: self.control.cache_enabled,
413            instruction_replacement_enabled: !self.control.disable_instruction_replacement,
414            data_replacement_enabled: !self.control.disable_data_replacement,
415            mode: self.control.mode,
416        }
417    }
418}
419
420#[inline(always)]
421fn cache_ram_addr(way_idx: usize, entry_idx: usize) -> usize {
422    (way_idx << 10) | (entry_idx << 4)
423}
424
425#[inline(always)]
426fn cache_entry_index(address: u32) -> usize {
427    // Cache is indexed using address bits 4-9
428    ((address as usize) >> 4) & 0x3F
429}
430
431#[inline(always)]
432fn tag_address(address: u32) -> u32 {
433    // Cache entries are tagged using address bits 10-28
434    (address & 0x1FFFFFFF) >> 10
435}