ternaria_os/
exec.rs

1//! The executable format (D-20).
2//!
3//! A header of five stored words, then the code.
4//!
5//! # Why an instruction is six bytes
6//!
7//! The byte boundary (D-04) maps a byte to a tryte and does not run backwards:
8//! a tryte holds 19,683 values and a byte holds 256. An instruction is three
9//! trytes, so storing one means splitting each tryte across more than one byte.
10//!
11//! Each tryte is biased by 9,841 to make it non-negative, then split into two
12//! digits in base 243. Base 243 because it is 3^5, so a digit is a trit shift
13//! rather than a multiply, and because it is under 256, so a digit is still a
14//! byte. Two digits reach 59,049, past the 19,683 a tryte needs.
15
16use ternaria_arith::{Tryte, Word};
17use ternaria_isa::asm;
18
19/// Digits are base 243, as in the filesystem.
20pub const RADIX: i64 = 243;
21
22/// Trits per digit: `RADIX` is 3 to this power.
23pub const RADIX_TRITS: u32 = 5;
24
25/// Added to a tryte to make it non-negative before splitting.
26pub const BIAS: i64 = 9_841;
27
28/// Bytes per tryte in the encoded form.
29pub const BYTES_PER_TRYTE: usize = 2;
30
31/// Bytes per instruction.
32pub const BYTES_PER_INSTRUCTION: usize = 3 * BYTES_PER_TRYTE;
33
34/// Words in the header.
35pub const HEADER_WORDS: usize = 5;
36
37/// Bytes in the header. Header fields are small, so they are stored the way
38/// filesystem fields are: three trytes in base 243, one byte each.
39pub const HEADER_BYTES: usize = HEADER_WORDS * 3;
40
41/// Identifies an executable. `3^9 + 3^5 + 3` and chosen only to be recognisable.
42pub const MAGIC: i64 = 19_683 + 243 + 3;
43
44/// Word offsets within the header.
45pub mod hdr {
46    /// Identifies the format.
47    pub const MAGIC: usize = 0;
48    /// The tryte address the code was linked for.
49    pub const LINK: usize = 1;
50    /// Entry point, a tryte address.
51    pub const ENTRY: usize = 2;
52    /// Code length in trytes.
53    pub const CODE: usize = 3;
54    /// Trytes of zeroed space to reserve after the code.
55    pub const BSS: usize = 4;
56}
57
58/// Something wrong with a program or its source.
59#[derive(Clone, PartialEq, Eq, Debug)]
60pub enum ExecError {
61    /// The source did not assemble.
62    Assembly(String),
63    /// The bytes are not an executable.
64    NotAnExecutable,
65    /// The image is shorter than its header claims.
66    Truncated,
67}
68
69impl std::fmt::Display for ExecError {
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        match self {
72            ExecError::Assembly(e) => write!(f, "{e}"),
73            ExecError::NotAnExecutable => write!(f, "not an executable"),
74            ExecError::Truncated => write!(f, "truncated executable"),
75        }
76    }
77}
78
79impl std::error::Error for ExecError {}
80
81/// Splits a small non-negative value into three base-243 bytes.
82fn put_word(out: &mut Vec<u8>, value: i64) {
83    let mut v = value;
84    for _ in 0..3 {
85        out.push((v % RADIX) as u8);
86        v /= RADIX;
87    }
88}
89
90/// Reads a value written by [`put_word`].
91fn get_word(bytes: &[u8], at: usize) -> i64 {
92    let mut acc = 0i64;
93    let mut weight = 1i64;
94    for k in 0..3 {
95        acc += bytes[at + k] as i64 * weight;
96        weight *= RADIX;
97    }
98    acc
99}
100
101/// Encodes one tryte as two bytes.
102fn put_tryte(out: &mut Vec<u8>, t: Tryte) {
103    let v = t.value() as i64 + BIAS;
104    out.push((v % RADIX) as u8);
105    out.push((v / RADIX) as u8);
106}
107
108/// Reads a tryte written by [`put_tryte`].
109fn get_tryte(bytes: &[u8], at: usize) -> Tryte {
110    let v = bytes[at] as i64 + bytes[at + 1] as i64 * RADIX - BIAS;
111    Tryte::from_value(v as i32)
112}
113
114/// Assembles `source` for `link` and returns an executable image.
115///
116/// `bss` is trytes of zeroed space the loader reserves after the code, for a
117/// program that wants scratch it did not have to place by hand.
118pub fn build(source: &str, link: i64, bss: i64) -> Result<Vec<u8>, ExecError> {
119    let program = asm::assemble_at(source, link).map_err(|e| ExecError::Assembly(e.to_string()))?;
120    let entry = program
121        .labels
122        .get("_start")
123        .map(|i| link + *i as i64 * 3)
124        .unwrap_or(link);
125
126    let code_trytes = program.instructions.len() as i64 * 3;
127    let mut out = Vec::with_capacity(HEADER_BYTES + program.instructions.len() * 6);
128    put_word(&mut out, MAGIC);
129    put_word(&mut out, link);
130    put_word(&mut out, entry);
131    put_word(&mut out, code_trytes);
132    put_word(&mut out, bss);
133
134    for instr in &program.instructions {
135        let w = instr.encode();
136        for k in 0..3 {
137            put_tryte(&mut out, w.tryte(k));
138        }
139    }
140    Ok(out)
141}
142
143/// A parsed executable header.
144#[derive(Clone, Copy, PartialEq, Eq, Debug)]
145pub struct Header {
146    /// The address the code was linked for.
147    pub link: i64,
148    /// Entry point.
149    pub entry: i64,
150    /// Code length in trytes.
151    pub code_trytes: i64,
152    /// Zeroed space to reserve after the code.
153    pub bss_trytes: i64,
154}
155
156/// Reads the header, checking the magic and the length.
157pub fn header(image: &[u8]) -> Result<Header, ExecError> {
158    if image.len() < HEADER_BYTES || get_word(image, hdr::MAGIC * 3) != MAGIC {
159        return Err(ExecError::NotAnExecutable);
160    }
161    let h = Header {
162        link: get_word(image, hdr::LINK * 3),
163        entry: get_word(image, hdr::ENTRY * 3),
164        code_trytes: get_word(image, hdr::CODE * 3),
165        bss_trytes: get_word(image, hdr::BSS * 3),
166    };
167    let need = HEADER_BYTES + (h.code_trytes as usize) * BYTES_PER_TRYTE;
168    if image.len() < need {
169        return Err(ExecError::Truncated);
170    }
171    Ok(h)
172}
173
174/// Decodes the code as words, for a host checking what a program contains.
175pub fn words(image: &[u8]) -> Result<Vec<Word>, ExecError> {
176    let h = header(image)?;
177    let mut out = Vec::new();
178    let mut at = HEADER_BYTES;
179    for _ in 0..(h.code_trytes / 3) {
180        let trytes = [
181            get_tryte(image, at),
182            get_tryte(image, at + 2),
183            get_tryte(image, at + 4),
184        ];
185        out.push(Word::from_trytes(trytes));
186        at += BYTES_PER_INSTRUCTION;
187    }
188    Ok(out)
189}
190
191/// Assembler `.equ` lines naming the format's constants.
192pub fn prelude() -> String {
193    let entries: [(&str, i64); 9] = [
194        ("EXE_MAGIC", MAGIC),
195        ("EXE_RADIX", RADIX),
196        ("EXE_RADIX_TRITS", RADIX_TRITS as i64),
197        ("EXE_BIAS", BIAS),
198        ("EXE_HEADER_TRYTES", HEADER_BYTES as i64),
199        ("HDR_LINK", hdr::LINK as i64),
200        ("HDR_ENTRY", hdr::ENTRY as i64),
201        ("HDR_CODE", hdr::CODE as i64),
202        ("HDR_BSS", hdr::BSS as i64),
203    ];
204    let mut out = String::new();
205    for (name, value) in entries {
206        out.push_str(&format!(".equ {name}, {value}\n"));
207    }
208    out
209}
ternaria_os/exec.rs

ternaria_os/
exec.rs
