shuyi_playdate/
stack.rs

1//! The arithmetic of the game's own stack (`crate::device`).
2//!
3//! The device gives the C stack about 10 KB, and a game's load or search can
4//! go deeper. So the backend runs the game on a block from the heap, filled
5//! with [`PAINT`] first. A stack grows down from its top, so the painted bytes
6//! left at the bottom say how deep it ever went ([`high_water`]).
7
8use core::sync::atomic::{AtomicBool, Ordering};
9
10/// The game's stack unless its `main!` says otherwise, in bytes. The first
11/// game on the backend measured 15,256 bytes at its deepest, in its load.
12pub const DEFAULT_BYTES: usize = 64 * 1024;
13
14/// The byte the stack is filled with before the game first runs on it.
15pub const PAINT: u8 = 0xA5;
16
17/// The bottom bytes of the stack that count as an overflow once used: the
18/// game has gone, or is about to go, past its stack.
19pub const RED_ZONE: usize = 256;
20
21/// The bytes ever used of a stack of `size` bytes, given its `bytes` lowest
22/// address first: everything above the painted bytes at its bottom.
23pub fn high_water(size: usize, bytes: impl IntoIterator<Item = u8>) -> usize {
24    let untouched = bytes.into_iter().take_while(|&byte| byte == PAINT).count();
25    size.saturating_sub(untouched)
26}
27
28/// Whether a stack, given its `bytes` lowest address first, has been used
29/// into its [`RED_ZONE`]. It reads that zone alone, so it can run every frame.
30pub fn overflowed(bytes: impl IntoIterator<Item = u8>) -> bool {
31    bytes.into_iter().take(RED_ZONE).any(|byte| byte != PAINT)
32}
33
34/// The starting stack pointer for a stack of `size` bytes at `base`: its top,
35/// rounded down to 8 bytes as the ARM procedure call standard asks.
36pub fn top(base: usize, size: usize) -> usize {
37    (base + size) & !7
38}
39
40/// Runs `f` through `switch`, which moves to the stack, makes the call it is
41/// handed and comes back. A call made while `inside` says the game is on the
42/// stack already is a plain one, so it doesn't start again from the top.
43pub fn run<R>(
44    inside: &AtomicBool,
45    f: impl FnOnce() -> R,
46    switch: impl FnOnce(&mut dyn FnMut()),
47) -> R {
48    if inside.swap(true, Ordering::Relaxed) {
49        return f();
50    }
51    let mut f = Some(f);
52    let mut out = None;
53    switch(&mut || out = f.take().map(|f| f()));
54    inside.store(false, Ordering::Relaxed);
55    match out {
56        Some(out) => out,
57        // check-text: not player text (a backend's bug, for the console)
58        None => panic!("the game's stack came back without making the call"),
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use core::cell::Cell;
65
66    use super::*;
67
68    /// The bytes of `stack`, as the device reads them.
69    fn bytes(stack: &[u8]) -> impl Iterator<Item = u8> {
70        stack.iter().copied()
71    }
72
73    #[test]
74    fn an_untouched_stack_has_used_nothing() {
75        assert_eq!(high_water(64, bytes(&[PAINT; 64])), 0);
76    }
77
78    #[test]
79    fn a_use_of_3_kb_reads_3_kb() {
80        let mut stack = alloc::vec![PAINT; DEFAULT_BYTES];
81        for byte in &mut stack[DEFAULT_BYTES - 3 * 1024..] {
82            *byte = 0;
83        }
84        assert_eq!(high_water(DEFAULT_BYTES, bytes(&stack)), 3 * 1024);
85    }
86
87    #[test]
88    fn the_used_bytes_are_those_above_the_deepest_write() {
89        let mut stack = [PAINT; 64];
90        stack[40] = 0;
91        stack[63] = 1;
92        // Bytes 41 to 62 kept the paint's value, but byte 40 was written.
93        assert_eq!(high_water(64, bytes(&stack)), 24);
94        stack[0] = 7;
95        assert_eq!(high_water(64, bytes(&stack)), 64);
96    }
97
98    #[test]
99    fn the_red_zone_is_the_bottom_of_the_stack() {
100        let mut stack = [PAINT; 1024];
101        assert!(!overflowed(bytes(&stack)));
102        stack[RED_ZONE] = 0;
103        assert!(!overflowed(bytes(&stack)));
104        stack[RED_ZONE - 1] = 0;
105        assert!(overflowed(bytes(&stack)));
106        stack[RED_ZONE - 1] = PAINT;
107        stack[0] = 0;
108        assert!(overflowed(bytes(&stack)));
109    }
110
111    #[test]
112    fn the_top_is_eight_byte_aligned_and_inside_the_block() {
113        assert_eq!(top(0x2000_0000, DEFAULT_BYTES), 0x2001_0000);
114        assert_eq!(top(0x2000_0004, 100), 0x2000_0068);
115        assert_eq!(top(0x2000_0003, 16), 0x2000_0010);
116    }
117
118    /// A switch that counts how often it was asked to move.
119    fn counted(switches: &Cell<u32>) -> impl Fn(&mut dyn FnMut()) {
120        |call| {
121            switches.set(switches.get() + 1);
122            call();
123        }
124    }
125
126    #[test]
127    fn a_call_moves_to_the_stack_and_hands_back_what_it_returned() {
128        let inside = AtomicBool::new(false);
129        let switches = Cell::new(0);
130        let seen = run(
131            &inside,
132            || inside.load(Ordering::Relaxed),
133            counted(&switches),
134        );
135        assert!(seen, "the guard is up during the call");
136        assert_eq!(switches.get(), 1);
137        assert!(!inside.load(Ordering::Relaxed), "and down after it");
138        run(&inside, || (), counted(&switches));
139        assert_eq!(switches.get(), 2, "the next call moves again");
140    }
141
142    #[test]
143    fn a_nested_call_does_not_start_again_from_the_top() {
144        let inside = AtomicBool::new(false);
145        let switches = Cell::new(0);
146        let (outer, still_inside) = run(
147            &inside,
148            || {
149                let inner = run(&inside, || 7, counted(&switches));
150                (inner + 1, inside.load(Ordering::Relaxed))
151            },
152            counted(&switches),
153        );
154        assert_eq!(outer, 8);
155        assert_eq!(switches.get(), 1);
156        assert!(still_inside, "the inner call leaves the guard up");
157        assert!(!inside.load(Ordering::Relaxed));
158    }
159}
shuyi_playdate/stack.rs

shuyi_playdate/
stack.rs
