ternaria_mem/

lib.rs

//! Guest memory for the Ternaria emulator (D-14).
//!
//! # Shape
//!
//! - The addressable unit is the 9-trit [`Tryte`] (D-02).
//! - Addresses are signed, covering +/-3.81*10^12 with zero at the centre.
//! - Little-endian: the least significant tryte is at the lowest address. This
//!   matches `ternaria-arith`, which orders trits least-significant-first.
//! - Everything aligns to the word (3 trytes), including double words. See
//!   [`Memory::read_double`].
//! - Sparse. The full address space is about 8.6 TB at BCT density, so pages
//!   are allocated on first write and never materialised for reads.
//! - Memory that has never been written reads as an error rather than zero.
//!
//! # Storage format
//!
//! Trytes are stored as BCT rather than as numeric values. Every `i32` is a
//! valid tryte value, so a value representation would leave nowhere to record
//! that a location has never been written. BCT has a spare codepoint for it
//! (D-03).

#![forbid(unsafe_code)]
#![warn(missing_docs)]

pub mod bytes;

use std::collections::BTreeMap;
use std::fmt;

use ternaria_arith::{DoubleWord, Tryte, Word};

/// Trytes per page: 3^6 = 729 (D-14). The smaller of the two candidates
/// considered; smaller pages waste less on a sparse address space at the cost
/// of more host allocations.
pub const PAGE_TRYTES: usize = 729;

/// Trytes per word - 27 trits / 9.
pub const WORD_TRYTES: i64 = 3;

/// Trytes per double word - 54 trits / 9.
pub const DOUBLE_TRYTES: i64 = 6;

/// A tryte of pure NaT: all nine trits carry the `10` poison pattern.
///
/// `0b10` repeated nine times across 18 bits.
const NAT_TRYTE: u32 = 0b10_1010_1010_1010_1010;

/// Something went wrong with a memory access.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum MemoryError {
    /// Read of memory that was never written.
    Uninitialised {
        /// The offending address.
        addr: i64,
    },
    /// Access not aligned to a word boundary.
    Misaligned {
        /// The offending address.
        addr: i64,
    },
    /// A tryte outside 0..=255 was written to a byte-oriented device (D-04).
    NotAByte {
        /// The offending value.
        value: i64,
    },
    /// A device rejected the access.
    Device {
        /// The address accessed.
        addr: i64,
        /// What the device reported.
        reason: &'static str,
    },
    /// The access would run off the end of the address space.
    AddressOverflow {
        /// The base address of the access.
        addr: i64,
        /// How many trytes the access needed.
        len: i64,
    },
}

impl MemoryError {
    /// For an [`AddressOverflow`](MemoryError::AddressOverflow), how many
    /// trytes past the end of the address space the access would have reached.
    /// `None` for the other variants.
    pub fn overshoot(&self) -> Option<i64> {
        match *self {
            MemoryError::AddressOverflow { addr, len } => {
                let last = addr.saturating_add(len - 1);
                Some((last - Word::MAX.value()).max(0))
            }
            _ => None,
        }
    }
}

impl fmt::Display for MemoryError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            MemoryError::Uninitialised { addr } => {
                write!(f, "read of uninitialised memory at {addr}")
            }
            MemoryError::Misaligned { addr } => {
                write!(f, "unaligned access at {addr}; must be a multiple of 3")
            }
            MemoryError::NotAByte { value } => {
                write!(f, "value {value} is outside 0..=255 and is not a byte")
            }
            MemoryError::Device { addr, reason } => {
                write!(f, "device at {addr} rejected the access: {reason}")
            }
            MemoryError::AddressOverflow { addr, len } => {
                write!(
                    f,
                    "access of {len} trytes at {addr} leaves the address space by {} tryte(s)",
                    self.overshoot().unwrap_or(0)
                )
            }
        }
    }
}

impl std::error::Error for MemoryError {}

/// One page of guest memory. Boxed by [`Memory`] to keep the map nodes small.
struct Page {
    trytes: [u32; PAGE_TRYTES],
}

impl Page {
    /// A fresh page is entirely poison.
    fn poisoned() -> Box<Page> {
        Box::new(Page {
            trytes: [NAT_TRYTE; PAGE_TRYTES],
        })
    }
}

/// Sparse, BCT-backed guest memory.
#[derive(Default)]
pub struct Memory {
    pages: BTreeMap<i64, Box<Page>>,
}

impl Memory {
    /// Empty memory. Every address reads as uninitialised.
    pub fn new() -> Self {
        Memory {
            pages: BTreeMap::new(),
        }
    }

    /// How many pages are currently allocated. For tests and diagnostics.
    pub fn pages_allocated(&self) -> usize {
        self.pages.len()
    }

    /// Splits an address into (page index, offset within page).
    ///
    /// Euclidean rather than truncating division, so the offset is in
    /// `0..PAGE_TRYTES` for negative addresses as well. Truncating division
    /// would produce negative offsets.
    #[inline]
    fn split(addr: i64) -> (i64, usize) {
        let page = addr.div_euclid(PAGE_TRYTES as i64);
        let offset = addr.rem_euclid(PAGE_TRYTES as i64) as usize;
        (page, offset)
    }

    /// True when `addr` is word-aligned. Equivalent to testing whether the low
    /// trit is zero. Applies at every width, since everything aligns to the
    /// word (D-14).
    #[inline]
    pub fn is_aligned(addr: Word) -> bool {
        addr.value().rem_euclid(WORD_TRYTES) == 0
    }

    /// Checks that `len` trytes starting at `addr` stay inside the space.
    fn check_span(addr: Word, len: i64) -> Result<i64, MemoryError> {
        let base = addr.value();
        let last = base
            .checked_add(len - 1)
            .ok_or(MemoryError::AddressOverflow { addr: base, len })?;
        if Word::new(last).is_none() {
            return Err(MemoryError::AddressOverflow { addr: base, len });
        }
        Ok(base)
    }

    /// Reads one tryte. Errors if it was never written.
    pub fn read_tryte(&self, addr: Word) -> Result<Tryte, MemoryError> {
        let a = Self::check_span(addr, 1)?;
        let (page, offset) = Self::split(a);
        // An unallocated page is unwritten, so there is no need to
        // materialise a poisoned page in order to fail on it.
        let bits = match self.pages.get(&page) {
            Some(p) => p.trytes[offset],
            None => return Err(MemoryError::Uninitialised { addr: a }),
        };
        // Mapping NatError to Uninitialised is exact, given one invariant:
        // page poisoning is the only way a NaT code enters memory.
        // `write_tryte` stores `Tryte::to_bct()`, and a `Tryte` is nine valid
        // trits, so no write can produce the 10 pattern.
        // `no_write_can_produce_nat` checks this.
        //
        // A future path that writes raw BCT, such as a loader or a snapshot
        // restore, must reject NaT itself or this mapping becomes wrong.
        Tryte::from_bct(bits).map_err(|_| MemoryError::Uninitialised { addr: a })
    }

    /// Writes one tryte, allocating its page if needed.
    pub fn write_tryte(&mut self, addr: Word, value: Tryte) -> Result<(), MemoryError> {
        let a = Self::check_span(addr, 1)?;
        let (page, offset) = Self::split(a);
        let p = self.pages.entry(page).or_insert_with(Page::poisoned);
        p.trytes[offset] = value.to_bct();
        Ok(())
    }

    /// True when this address holds a value that was actually written.
    pub fn is_initialised(&self, addr: Word) -> bool {
        self.read_tryte(addr).is_ok()
    }

    /// Reads a word: three trytes, least significant first.
    ///
    /// Requires word alignment. The tryte at `addr` holds trits 0..9, the next
    /// holds 9..18, and the last holds 18..27, so the weights are 3^0, 3^9 and
    /// 3^18.
    pub fn read_word(&self, addr: Word) -> Result<Word, MemoryError> {
        if !Self::is_aligned(addr) {
            return Err(MemoryError::Misaligned { addr: addr.value() });
        }
        let base = Self::check_span(addr, WORD_TRYTES)?;
        let mut trytes = [Tryte::ZERO; Word::TRYTES];
        for (i, slot) in trytes.iter_mut().enumerate() {
            *slot = self.read_tryte(Word::from_value(base + i as i64))?;
        }
        Ok(Word::from_trytes(trytes))
    }

    /// Writes a word: three trytes, least significant first.
    pub fn write_word(&mut self, addr: Word, value: Word) -> Result<(), MemoryError> {
        if !Self::is_aligned(addr) {
            return Err(MemoryError::Misaligned { addr: addr.value() });
        }
        let base = Self::check_span(addr, WORD_TRYTES)?;
        for i in 0..Word::TRYTES {
            self.write_tryte(Word::from_value(base + i as i64), value.tryte(i))?;
        }
        Ok(())
    }

    /// Reads a double word: six trytes, least significant first.
    ///
    /// Aligned to the word rather than to its own six trytes. Six-tryte
    /// alignment would require testing `addr mod 6 == 0`, which in base 3 means
    /// checking that the low trit is zero and the digit sum is even, a 27-trit
    /// reduction rather than a single trit test (D-14).
    pub fn read_double(&self, addr: Word) -> Result<DoubleWord, MemoryError> {
        if !Self::is_aligned(addr) {
            return Err(MemoryError::Misaligned { addr: addr.value() });
        }
        let base = Self::check_span(addr, DOUBLE_TRYTES)?;
        let mut trytes = [Tryte::ZERO; DoubleWord::TRYTES];
        for (i, slot) in trytes.iter_mut().enumerate() {
            *slot = self.read_tryte(Word::from_value(base + i as i64))?;
        }
        Ok(DoubleWord::from_trytes(trytes))
    }

    /// Writes a double word: six trytes, least significant first.
    pub fn write_double(&mut self, addr: Word, value: DoubleWord) -> Result<(), MemoryError> {
        if !Self::is_aligned(addr) {
            return Err(MemoryError::Misaligned { addr: addr.value() });
        }
        let base = Self::check_span(addr, DOUBLE_TRYTES)?;
        for i in 0..DoubleWord::TRYTES {
            self.write_tryte(Word::from_value(base + i as i64), value.tryte(i))?;
        }
        Ok(())
    }
}

/// Anything a program can load from and store to.
///
/// Reads take `&mut self` because a device read can have a side effect, such as
/// consuming a byte from a console input queue.
pub trait Addressable {
    /// Reads one tryte.
    fn read_tryte(&mut self, addr: Word) -> Result<Tryte, MemoryError>;
    /// Writes one tryte.
    fn write_tryte(&mut self, addr: Word, value: Tryte) -> Result<(), MemoryError>;
    /// Reads a word: three trytes, least significant first.
    fn read_word(&mut self, addr: Word) -> Result<Word, MemoryError>;
    /// Writes a word: three trytes, least significant first.
    fn write_word(&mut self, addr: Word, value: Word) -> Result<(), MemoryError>;

    /// True if reaching `addr` should require supervisor privilege.
    ///
    /// Plain memory returns false for everything. A bus that maps devices
    /// returns true for their addresses, which is what stops a user program
    /// driving hardware directly.
    fn is_privileged(&self, _addr: Word) -> bool {
        false
    }

    /// Which interrupt sources are asserting, one trit per source.
    ///
    /// See [`irq`] for what each trit means. Zero for anything with no devices
    /// attached.
    fn interrupts(&self) -> Word {
        Word::ZERO
    }
}

/// Interrupt request lines: which trit of the interrupt masks each device owns.
///
/// An interrupt request, conventionally shortened to IRQ, is a device asking
/// the processor for attention. Ternaria gives each device one trit, in two
/// control registers the processor holds:
///
/// - `ip`, interrupt pending. Written by the hardware. Trit `k` is positive
///   while device `k` is asking. A device keeps asking until something attends
///   to it, so the trit stays positive; it is a level, not a pulse.
/// - `ie`, interrupt enable. Written by the operating system. Trit `k` is
///   positive while the operating system is willing to be interrupted by
///   device `k`.
///
/// A source fires when both trits are positive, which is the per-trit minimum
/// of the two masks: Kleene AND (D-06).
///
/// # Why the numbering lives here
///
/// A bus fills this mask in and a processor reads it, and the two are separate
/// crates that must agree on what each trit means. Neither can own the
/// numbering without the other duplicating it, so it belongs to the trait they
/// meet at, next to [`Addressable::interrupts`].
pub mod irq {
    /// The timer reached its compare value.
    pub const TIMER: usize = 0;
    /// The console has input waiting.
    pub const CONSOLE: usize = 1;
    /// How many sources are defined.
    pub const COUNT: usize = 2;

    /// The value that enables one source when written to `ie`.
    ///
    /// A power of three, not of two, because the position is a trit position:
    /// enabling source `k` means putting a `+1` in trit `k`.
    pub const fn mask(source: usize) -> i64 {
        3i64.pow(source as u32)
    }
}

impl Addressable for Memory {
    fn read_tryte(&mut self, addr: Word) -> Result<Tryte, MemoryError> {
        Memory::read_tryte(self, addr)
    }
    fn write_tryte(&mut self, addr: Word, value: Tryte) -> Result<(), MemoryError> {
        Memory::write_tryte(self, addr, value)
    }
    fn read_word(&mut self, addr: Word) -> Result<Word, MemoryError> {
        Memory::read_word(self, addr)
    }
    fn write_word(&mut self, addr: Word, value: Word) -> Result<(), MemoryError> {
        Memory::write_word(self, addr, value)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use ternaria_arith::Trit;

    fn w(v: i64) -> Word {
        Word::from_value(v)
    }

    #[test]
    fn nat_tryte_is_all_poison() {
        // Every one of the nine trit slots must carry the NaT pattern, or
        // fresh memory would decode as a legitimate value somewhere.
        for i in 0..9 {
            assert_eq!((NAT_TRYTE >> (2 * i)) & 0b11, Trit::NAT_CODE as u32);
        }
        assert!(Tryte::from_bct(NAT_TRYTE).is_err());
    }

    #[test]
    fn fresh_memory_is_uninitialised_not_zero() {
        let m = Memory::new();
        for addr in [0i64, 1, -1, 1_000_000, -1_000_000] {
            assert_eq!(
                m.read_tryte(w(addr)),
                Err(MemoryError::Uninitialised { addr }),
                "addr {addr}"
            );
        }
        assert_eq!(m.pages_allocated(), 0, "reads must not allocate");
    }

    #[test]
    fn tryte_round_trips_including_negative_addresses() {
        let mut m = Memory::new();
        for addr in [0i64, 1, 728, 729, 730, -1, -728, -729, -730, 5_000_000] {
            for v in [0i32, 1, -1, 9841, -9841, 4242] {
                m.write_tryte(w(addr), Tryte::from_value(v)).unwrap();
                assert_eq!(
                    m.read_tryte(w(addr)).unwrap().value(),
                    v,
                    "addr {addr} v {v}"
                );
            }
        }
    }

    /// Euclidean splitting is the whole reason negative addresses work. A
    /// truncating split would give negative offsets and index out of bounds.
    #[test]
    fn negative_addresses_split_into_valid_offsets() {
        for addr in [-1i64, -728, -729, -730, -1_000_000, 0, 1, 728, 729] {
            let (_page, offset) = Memory::split(addr);
            assert!(offset < PAGE_TRYTES, "addr {addr} gave offset {offset}");
        }
        // Adjacent addresses across a page boundary must land in adjacent pages.
        assert_eq!(Memory::split(-1), (-1, PAGE_TRYTES - 1));
        assert_eq!(Memory::split(0), (0, 0));
    }

    #[test]
    fn word_round_trips() {
        let mut m = Memory::new();
        for v in [
            0i64,
            1,
            -1,
            42,
            -42,
            Word::MAX.value(),
            Word::MIN.value(),
            1_234_567_890,
        ] {
            m.write_word(w(0), w(v)).unwrap();
            assert_eq!(m.read_word(w(0)).unwrap().value(), v, "value {v}");
        }
    }

    #[test]
    fn word_is_little_endian() {
        let mut m = Memory::new();
        // A tryte is 9 trits, so a word's three trytes carry trits 0..9, 9..18
        // and 18..27 - place values 3^0, 3^9 and 3^18. Writing exactly one of
        // those powers puts a single +1 in exactly one tryte and zero in the
        // others, which is what makes the placement observable at all.
        //
        // The low and high cases are the ones that discriminate: under
        // big-endian they would swap. A middle-tryte value proves nothing on
        // its own, since three trytes are symmetric about their centre.
        for (value, expected) in [
            (1i64, [1i32, 0, 0]),      // 3^0  -> lowest address
            (3i64.pow(9), [0, 1, 0]),  // 3^9  -> middle
            (3i64.pow(18), [0, 0, 1]), // 3^18 -> highest address
        ] {
            m.write_word(w(0), w(value)).unwrap();
            for (i, want) in expected.iter().enumerate() {
                assert_eq!(
                    m.read_tryte(w(i as i64)).unwrap().value(),
                    *want,
                    "value {value}, tryte {i}"
                );
            }
        }
    }

    /// The invariant that makes collapsing `NatError` into `Uninitialised`
    /// exact rather than lossy: no write can ever store a NaT code, so NaT in
    /// memory means "never written" and nothing else.
    #[test]
    fn no_write_can_produce_nat() {
        for v in Tryte::MIN.value()..=Tryte::MAX.value() {
            let bits = Tryte::from_value(v).to_bct();
            for i in 0..9 {
                assert_ne!(
                    (bits >> (2 * i)) & 0b11,
                    Trit::NAT_CODE as u32,
                    "value {v} produced NaT at trit {i}"
                );
            }
        }
    }

    #[test]
    fn overflow_reports_how_far_it_overshot() {
        let mut m = Memory::new();
        let top = Word::MAX.value();
        let err = m.write_word(w(top - 1), w(0)).unwrap_err();
        // Needs trytes top-1, top, top+1 - one past the end.
        assert_eq!(err.overshoot(), Some(1));
        assert!(err.to_string().contains("by 1 tryte"));

        // A double at the same place overshoots by four.
        let err = m.write_double(w(top - 1), DoubleWord::ZERO).unwrap_err();
        assert_eq!(err.overshoot(), Some(4));

        // The other variants do not overshoot anything.
        assert_eq!(MemoryError::Misaligned { addr: 1 }.overshoot(), None);
        assert_eq!(MemoryError::Uninitialised { addr: 0 }.overshoot(), None);
    }

    #[test]
    fn double_round_trips_and_aligns_to_the_word() {
        let mut m = Memory::new();
        for v in [
            0i128,
            1,
            -1,
            DoubleWord::MAX.value(),
            DoubleWord::MIN.value(),
        ] {
            m.write_double(w(0), DoubleWord::from_value(v)).unwrap();
            assert_eq!(m.read_double(w(0)).unwrap().value(), v);
        }
        // Address 3 is word-aligned but not 6-aligned. It must still work:
        // doubles align to the word, not to their own width.
        m.write_double(w(3), DoubleWord::from_value(-777)).unwrap();
        assert_eq!(m.read_double(w(3)).unwrap().value(), -777);
    }

    #[test]
    fn misalignment_traps() {
        let mut m = Memory::new();
        for addr in [1i64, 2, 4, 5, -1, -2] {
            assert_eq!(
                m.write_word(w(addr), w(0)),
                Err(MemoryError::Misaligned { addr })
            );
            assert_eq!(m.read_word(w(addr)), Err(MemoryError::Misaligned { addr }));
        }
        // Multiples of three are fine in both directions.
        for addr in [0i64, 3, -3, 729, -729] {
            m.write_word(w(addr), w(1)).unwrap();
        }
    }

    #[test]
    fn partially_written_word_still_faults() {
        let mut m = Memory::new();
        // Write only the low tryte of a word; the other two stay poisoned.
        m.write_tryte(w(0), Tryte::from_value(5)).unwrap();
        assert_eq!(
            m.read_word(w(0)),
            Err(MemoryError::Uninitialised { addr: 1 })
        );
    }

    #[test]
    fn allocation_is_sparse() {
        let mut m = Memory::new();
        // Touch addresses far apart; only the touched pages should exist.
        m.write_tryte(w(0), Tryte::ZERO).unwrap();
        m.write_tryte(w(1_000_000_000), Tryte::ZERO).unwrap();
        m.write_tryte(w(-1_000_000_000), Tryte::ZERO).unwrap();
        assert_eq!(m.pages_allocated(), 3);

        // Filling one page must not allocate more.
        for i in 0..PAGE_TRYTES as i64 {
            m.write_tryte(w(i), Tryte::ZERO).unwrap();
        }
        assert_eq!(m.pages_allocated(), 3);
    }

    #[test]
    fn access_at_the_edge_of_the_address_space() {
        let mut m = Memory::new();
        let top = Word::MAX.value();

        // MAX itself sits one past an aligned address, so MAX-1 is aligned.
        // Alignment therefore passes and the span check is what has to catch
        // it: a word there would need a tryte one past the top of the space.
        assert_eq!(top.rem_euclid(WORD_TRYTES), 1);
        let over = MemoryError::AddressOverflow {
            addr: top - 1,
            len: WORD_TRYTES,
        };
        assert_eq!(m.write_word(w(top - 1), w(1)), Err(over));
        assert_eq!(m.read_word(w(top - 1)), Err(over));

        // The highest aligned address that does fit a whole word works.
        let highest = top - 4;
        assert_eq!(highest.rem_euclid(WORD_TRYTES), 0);
        assert!(highest + WORD_TRYTES - 1 <= top);
        m.write_word(w(highest), w(-12_345)).unwrap();
        assert_eq!(m.read_word(w(highest)).unwrap().value(), -12_345);

        // And the same at the bottom of the space, which is where a truncating
        // address split would have gone wrong.
        let bottom = Word::MIN.value() + 1;
        assert_eq!(bottom.rem_euclid(WORD_TRYTES), 0);
        m.write_word(w(bottom), w(999)).unwrap();
        assert_eq!(m.read_word(w(bottom)).unwrap().value(), 999);

        // A double needs six trytes, so it runs out of room sooner than a word
        // does at the same address.
        assert_eq!(
            m.write_double(w(highest), DoubleWord::ZERO),
            Err(MemoryError::AddressOverflow {
                addr: highest,
                len: DOUBLE_TRYTES
            })
        );
    }
}