ternaria_isa/lib.rs
1//! The Ternaria instruction set (D-05, D-15).
2//!
3//! # Source of truth
4//!
5//! The instruction set is declared once, in the `isa!` invocation below. The
6//! [`Opcode`] enum, the mnemonic table, the encoder, the decoder and the
7//! disassembler are generated from that declaration, so they cannot disagree.
8//!
9//! Both a `match` and a table are generated. The interpreter uses the `match`,
10//! which compiles to a jump table. The assembler and disassembler use the
11//! table, which can be enumerated and searched.
12//!
13//! # Encoding
14//!
15//! Fixed 27 trits, one word per instruction, no exceptions (D-05). Fields run
16//! from the least significant trit up:
17//!
18//! ```text
19//! trit 0 .. 6 opcode 6 trits, +/-364
20//! trit 6 .. 9 rd 3 trits, +/-13
21//! trit 9 .. 12 rs1 3 trits, +/-13
22//! trit 12 .. 15 rs2 3 trits, +/-13
23//! trit 15 .. 27 imm 12 trits, +/-265,720
24//! ```
25//!
26//! The 12-trit immediate covers +/-265,720. For comparison, RISC-V's 12-bit
27//! immediate covers +/-2,048.
28//!
29//! # Registers
30//!
31//! The register field is three balanced trits, so registers are numbered r-13
32//! through r13, with `r0` in the middle. `r0` reads as zero and discards
33//! writes.
34//!
35//! # Undefined opcodes
36//!
37//! Negative opcode values, 364 encodings, are reserved for future extension.
38//! Defined instructions occupy zero and up. Both reserved and undefined
39//! opcodes trap (D-15).
40
41//! # The immediate
42//!
43//! Width is 12 trits in every format that uses one. There is no short form.
44//!
45//! The value is a signed balanced integer covering +/-265,720. An unsigned
46//! immediate is not encodable, since a balanced ternary field carries sign in
47//! its digits.
48//!
49//! Sign extension does not apply. Widening a 12-trit field to a 27-trit word
50//! sets the upper fifteen trits to zero, which is the only possible reading.
51//!
52//! `br3` uses its immediate in both directions: the positive branch adds it and
53//! the negative branch subtracts it, so the two targets are mirrored about the
54//! branch. Where the targets cannot be mirrored, use `brn` and `brp`, which
55//! take one target each over the full immediate range.
56//!
57//! Units differ per instruction and are recorded in the table as [`ImmUnit`]:
58//!
59//! | Unit | Instructions | Meaning |
60//! |------|--------------|---------|
61//! | [`ImmUnit::Instructions`] | `jal`, `jalr`, `br3`, `brz` | Whole instructions. The interpreter scales by 3 trytes, so branch targets are word-aligned by construction. Reach is +/-797,160 trytes. |
62//! | [`ImmUnit::Trytes`] | `lw`, `sw` | Displacement from the base register, in addressable units. |
63//! | [`ImmUnit::Trits`] | `shl`, `shr` | Shift distance, an exponent of three. |
64//! | [`ImmUnit::Value`] | `addi` | A plain operand. |
65//! | [`ImmUnit::None`] | everything else | Field unused; must be zero. |
66//!
67//! # The program counter
68//!
69//! `pc` is the tryte address of the instruction being executed. It advances by
70//! 3 trytes, one word, after every instruction that does not redirect it.
71//! Control-flow immediates count instructions, so `pc += imm` in a summary
72//! below means `pc += 3 * imm` trytes.
73
74#![forbid(unsafe_code)]
75#![warn(missing_docs)]
76
77pub mod asm;
78
79use core::fmt;
80use ternaria_arith::{Trit, Word};
81
82// ---------------------------------------------------------------- field map
83
84/// Where each field sits, as `(offset, length)` in trits.
85const F_OPCODE: (usize, usize) = (0, 6);
86const F_RD: (usize, usize) = (6, 3);
87const F_RS1: (usize, usize) = (9, 3);
88const F_RS2: (usize, usize) = (12, 3);
89const F_IMM: (usize, usize) = (15, 12);
90
91/// Trytes per instruction. An instruction is one word and a word is three
92/// trytes, so a label's address is its instruction index times this.
93pub const WORD_TRYTES: i64 = 3;
94/// Largest magnitude a 3-trit register field can hold: (3^3-1)/2.
95pub const REG_MAX: i8 = 13;
96/// Largest magnitude a 12-trit immediate can hold: (3^12-1)/2.
97pub const IMM_MAX: i32 = 265_720;
98/// Number of architectural registers: 3^3.
99pub const REG_COUNT: usize = 27;
100
101/// Reads a balanced field of `len` trits starting at `offset`.
102fn get_field(trits: &[Trit; 27], (offset, len): (usize, usize)) -> i64 {
103 let mut acc = 0i64;
104 let mut place = 1i64;
105 for i in 0..len {
106 acc += trits[offset + i].value() as i64 * place;
107 place *= 3;
108 }
109 acc
110}
111
112/// Writes a balanced field of `len` trits starting at `offset`.
113fn put_field(trits: &mut [Trit; 27], (offset, len): (usize, usize), mut value: i64) {
114 for i in 0..len {
115 let mut r = value % 3;
116 value /= 3;
117 if r == 2 {
118 r = -1;
119 value += 1;
120 } else if r == -2 {
121 r = 1;
122 value -= 1;
123 }
124 trits[offset + i] = Trit::from_value(r as i8).expect("balanced digit");
125 }
126}
127
128// -------------------------------------------------------------------- table
129
130/// Which fields an instruction actually uses.
131///
132/// Fields outside a format must be zero in the encoded word. This is what makes
133/// `encode(decode(w)) == w` hold: otherwise a value in an unused field would
134/// decode successfully and re-encode differently.
135#[derive(Clone, Copy, PartialEq, Eq, Debug)]
136pub enum Format {
137 /// `rd, rs1, rs2` - three-register arithmetic and logic.
138 R,
139 /// `rd, rs1, imm` - register plus immediate.
140 I,
141 /// `rd, rs1` - unary.
142 U,
143 /// `rs1, imm` - branch.
144 B,
145 /// `rd, imm` - jump and link.
146 J,
147 /// No operands.
148 N,
149}
150
151impl Format {
152 /// True if this format uses the named field.
153 const fn uses_rd(self) -> bool {
154 matches!(self, Format::R | Format::I | Format::U | Format::J)
155 }
156 const fn uses_rs1(self) -> bool {
157 matches!(self, Format::R | Format::I | Format::U | Format::B)
158 }
159 const fn uses_rs2(self) -> bool {
160 matches!(self, Format::R)
161 }
162 const fn uses_imm(self) -> bool {
163 matches!(self, Format::I | Format::B | Format::J)
164 }
165}
166
167/// What an instruction's immediate counts.
168///
169/// Recorded in the table so that whether an offset counts instructions or
170/// trytes is answered by the data rather than by a comment.
171#[derive(Clone, Copy, PartialEq, Eq, Debug)]
172pub enum ImmUnit {
173 /// No immediate; the field must be zero.
174 None,
175 /// A plain operand value.
176 Value,
177 /// Addressable units - a displacement from a base register.
178 Trytes,
179 /// A shift distance, i.e. an exponent of three.
180 Trits,
181 /// Whole instructions. The interpreter multiplies by 3 to reach trytes,
182 /// which keeps every branch target word-aligned by construction.
183 Instructions,
184 /// A control and status register number.
185 Csr,
186}
187
188/// One row of the instruction table.
189#[derive(Clone, Copy, PartialEq, Eq, Debug)]
190pub struct Entry {
191 /// The opcode.
192 pub opcode: Opcode,
193 /// Assembly mnemonic.
194 pub mnemonic: &'static str,
195 /// Which operands it takes.
196 pub format: Format,
197 /// What the immediate counts.
198 pub imm_unit: ImmUnit,
199 /// One-line description, used by the disassembler and the docs.
200 pub summary: &'static str,
201}
202
203/// Declares the instruction set once, generating everything else.
204macro_rules! isa {
205 ($( $value:literal $variant:ident $mnemonic:literal $fmt:ident $unit:ident $summary:literal ; )*) => {
206 /// Every defined operation.
207 ///
208 /// Discriminants are the encoded opcode values. Negative values are
209 /// reserved for future extension and never appear here.
210 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
211 #[repr(i16)]
212 pub enum Opcode {
213 $( #[doc = $summary] $variant = $value, )*
214 }
215
216 /// The instruction table. Enumerable, unlike a `match`. Read by the
217 /// assembler, the disassembler and the documentation.
218 pub const TABLE: &[Entry] = &[
219 $( Entry {
220 opcode: Opcode::$variant,
221 mnemonic: $mnemonic,
222 format: Format::$fmt,
223 imm_unit: ImmUnit::$unit,
224 summary: $summary,
225 }, )*
226 ];
227
228 impl Opcode {
229 /// Decodes an opcode field value.
230 ///
231 /// A `match`, so dispatch compiles to a jump table rather than a
232 /// linear scan of [`TABLE`].
233 pub const fn from_value(v: i64) -> Result<Opcode, DecodeError> {
234 match v {
235 $( $value => Ok(Opcode::$variant), )*
236 _ if v < 0 => Err(DecodeError::ReservedOpcode { value: v }),
237 _ => Err(DecodeError::UnknownOpcode { value: v }),
238 }
239 }
240
241 /// The encoded value.
242 pub const fn value(self) -> i64 {
243 self as i16 as i64
244 }
245
246 /// The assembly mnemonic.
247 pub const fn mnemonic(self) -> &'static str {
248 match self { $( Opcode::$variant => $mnemonic, )* }
249 }
250
251 /// Which operands this instruction takes.
252 pub const fn format(self) -> Format {
253 match self { $( Opcode::$variant => Format::$fmt, )* }
254 }
255
256 /// What this instruction's immediate counts.
257 pub const fn imm_unit(self) -> ImmUnit {
258 match self { $( Opcode::$variant => ImmUnit::$unit, )* }
259 }
260
261 /// One-line description.
262 pub const fn summary(self) -> &'static str {
263 match self { $( Opcode::$variant => $summary, )* }
264 }
265 }
266 };
267}
268
269// `pc` below is the tryte address of the current instruction; `pc+1` means the
270// next instruction, three trytes on. Control-flow immediates count
271// instructions, so `pc += imm` is `pc += 3*imm` trytes. See the module docs.
272isa! {
273 0 Nop "nop" N None "do nothing; pc <- pc + 1";
274 1 Add "add" R None "rd <- rs1 + rs2";
275 2 Sub "sub" R None "rd <- rs1 - rs2";
276 3 Mul "mul" R None "rd <- rs1 * rs2";
277 4 Div "div" R None "rd <- rs1 / rs2, truncating";
278 5 Rem "rem" R None "rd <- rs1 % rs2";
279 6 Min "min" R None "rd <- per-trit minimum of rs1, rs2; Kleene AND";
280 7 Max "max" R None "rd <- per-trit maximum of rs1, rs2; Kleene OR";
281 8 Cmp3 "cmp3" R None "rd <- -1, 0 or +1 as rs1 <, ==, > rs2";
282 9 Neg "neg" U None "rd <- -rs1; also the per-trit logical NOT";
283 10 Abs "abs" U None "rd <- |rs1|; total, because the range is symmetric";
284 11 Addi "addi" I Value "rd <- rs1 + imm";
285 12 Shl "shl" I Trits "rd <- rs1 * 3^imm, an exact trit shift";
286 13 Shr "shr" I Trits "rd <- rs1 / 3^imm, rounded to nearest";
287 14 Lw "lw" I Trytes "rd <- memory word at rs1 + imm trytes";
288 15 Sw "sw" I Trytes "memory word at rs1 + imm trytes <- rd";
289 16 Jal "jal" J Instructions "rd <- pc + 1; pc <- pc + imm";
290 17 Jalr "jalr" I Instructions "rd <- pc + 1; pc <- rs1 + imm";
291 18 Br3 "br3" B Instructions "three-way: pc <- pc + imm if rs1 > 0; pc <- pc - imm if rs1 < 0; pc <- pc + 1 if rs1 == 0";
292 19 Brz "brz" B Instructions "pc <- pc + imm if rs1 == 0, else pc <- pc + 1";
293 20 Halt "halt" N None "stop execution";
294 21 Lt "lt" I Trytes "rd <- memory tryte at rs1 + imm trytes; no alignment requirement";
295 22 St "st" I Trytes "memory tryte at rs1 + imm trytes <- rd; no alignment requirement";
296 23 Brn "brn" B Instructions "pc <- pc + imm if rs1 < 0, else pc <- pc + 1";
297 24 Brp "brp" B Instructions "pc <- pc + imm if rs1 > 0, else pc <- pc + 1";
298 25 Csrr "csrr" J Csr "rd <- control register imm; supervisor or machine only";
299 26 Csrw "csrw" B Csr "control register imm <- rs1; supervisor or machine only";
300 27 Tret "tret" N None "pc <- tepc; priv <- tpriv; supervisor or machine only";
301 28 Ecall "ecall" N None "trap to tvec with cause Ecall";
302}
303
304// ------------------------------------------------------------------ operands
305
306/// An architectural register, numbered -13 through 13.
307///
308/// The register field is three balanced trits, so numbering is signed.
309/// [`Reg::ZERO`] is at the centre.
310#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
311pub struct Reg(i8);
312
313impl Reg {
314 /// `r0` - reads as zero, discards writes.
315 pub const ZERO: Reg = Reg(0);
316
317 /// Builds a register, or `None` outside -13..=13.
318 pub const fn new(n: i8) -> Option<Reg> {
319 if n >= -REG_MAX && n <= REG_MAX {
320 Some(Reg(n))
321 } else {
322 None
323 }
324 }
325
326 /// Builds a register, panicking outside -13..=13.
327 #[track_caller]
328 pub const fn r(n: i8) -> Reg {
329 match Reg::new(n) {
330 Some(x) => x,
331 None => panic!("register number out of range"),
332 }
333 }
334
335 /// The register number.
336 pub const fn number(self) -> i8 {
337 self.0
338 }
339
340 /// Index into a 27-entry register file, shifting -13..13 to 0..26.
341 pub const fn index(self) -> usize {
342 (self.0 + REG_MAX) as usize
343 }
344}
345
346impl fmt::Display for Reg {
347 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
348 write!(f, "r{}", self.0)
349 }
350}
351
352/// A 12-trit immediate, +/-265,720.
353#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
354pub struct Imm(i32);
355
356impl Imm {
357 /// Zero.
358 pub const ZERO: Imm = Imm(0);
359
360 /// Builds an immediate, or `None` if it does not fit 12 trits.
361 pub const fn new(v: i32) -> Option<Imm> {
362 if v >= -IMM_MAX && v <= IMM_MAX {
363 Some(Imm(v))
364 } else {
365 None
366 }
367 }
368
369 /// Builds an immediate, panicking if it does not fit.
370 #[track_caller]
371 pub const fn i(v: i32) -> Imm {
372 match Imm::new(v) {
373 Some(x) => x,
374 None => panic!("immediate out of range"),
375 }
376 }
377
378 /// The value.
379 pub const fn value(self) -> i32 {
380 self.0
381 }
382}
383
384impl fmt::Display for Imm {
385 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
386 write!(f, "{}", self.0)
387 }
388}
389
390// --------------------------------------------------------------- instruction
391
392/// A decoded instruction.
393///
394/// Fields not used by the opcode's [`Format`] are zero, both here and in the
395/// encoded word.
396#[derive(Clone, Copy, PartialEq, Eq, Debug)]
397pub struct Instruction {
398 /// The operation.
399 pub op: Opcode,
400 /// Destination register, or [`Reg::ZERO`] if unused.
401 pub rd: Reg,
402 /// First source register, or [`Reg::ZERO`] if unused.
403 pub rs1: Reg,
404 /// Second source register, or [`Reg::ZERO`] if unused.
405 pub rs2: Reg,
406 /// Immediate, or [`Imm::ZERO`] if unused.
407 pub imm: Imm,
408}
409
410/// Why a word is not a valid instruction.
411#[derive(Clone, Copy, PartialEq, Eq, Debug)]
412pub enum DecodeError {
413 /// Opcode is in the defined range but not assigned.
414 UnknownOpcode {
415 /// The opcode field's value.
416 value: i64,
417 },
418 /// Opcode is negative - reserved for future extension.
419 ReservedOpcode {
420 /// The opcode field's value.
421 value: i64,
422 },
423 /// A field the format does not use held a non-zero value. Rejected rather
424 /// than ignored, so re-encoding a decoded word reproduces it exactly.
425 NonZeroUnusedField {
426 /// Which field.
427 field: &'static str,
428 /// What it held.
429 value: i64,
430 },
431}
432
433impl fmt::Display for DecodeError {
434 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
435 match self {
436 DecodeError::UnknownOpcode { value } => write!(f, "unknown opcode {value}"),
437 DecodeError::ReservedOpcode { value } => {
438 write!(f, "opcode {value} is reserved for future extension")
439 }
440 DecodeError::NonZeroUnusedField { field, value } => {
441 write!(f, "unused field {field} must be zero, found {value}")
442 }
443 }
444 }
445}
446
447impl std::error::Error for DecodeError {}
448
449impl Instruction {
450 /// An R-format instruction.
451 pub const fn r(op: Opcode, rd: Reg, rs1: Reg, rs2: Reg) -> Instruction {
452 Instruction {
453 op,
454 rd,
455 rs1,
456 rs2,
457 imm: Imm::ZERO,
458 }
459 }
460 /// An I-format instruction.
461 pub const fn i(op: Opcode, rd: Reg, rs1: Reg, imm: Imm) -> Instruction {
462 Instruction {
463 op,
464 rd,
465 rs1,
466 rs2: Reg::ZERO,
467 imm,
468 }
469 }
470 /// A U-format (unary) instruction.
471 pub const fn u(op: Opcode, rd: Reg, rs1: Reg) -> Instruction {
472 Instruction {
473 op,
474 rd,
475 rs1,
476 rs2: Reg::ZERO,
477 imm: Imm::ZERO,
478 }
479 }
480 /// A B-format (branch) instruction.
481 pub const fn b(op: Opcode, rs1: Reg, imm: Imm) -> Instruction {
482 Instruction {
483 op,
484 rd: Reg::ZERO,
485 rs1,
486 rs2: Reg::ZERO,
487 imm,
488 }
489 }
490 /// A J-format instruction.
491 pub const fn j(op: Opcode, rd: Reg, imm: Imm) -> Instruction {
492 Instruction {
493 op,
494 rd,
495 rs1: Reg::ZERO,
496 rs2: Reg::ZERO,
497 imm,
498 }
499 }
500 /// An N-format (no operand) instruction.
501 pub const fn n(op: Opcode) -> Instruction {
502 Instruction {
503 op,
504 rd: Reg::ZERO,
505 rs1: Reg::ZERO,
506 rs2: Reg::ZERO,
507 imm: Imm::ZERO,
508 }
509 }
510
511 /// Encodes to a 27-trit word.
512 ///
513 /// Unused fields are written as zero regardless of what the struct holds,
514 /// so the encoding is always canonical.
515 pub fn encode(self) -> Word {
516 let fmt = self.op.format();
517 let mut trits = [Trit::Zero; 27];
518 put_field(&mut trits, F_OPCODE, self.op.value());
519 if fmt.uses_rd() {
520 put_field(&mut trits, F_RD, self.rd.number() as i64);
521 }
522 if fmt.uses_rs1() {
523 put_field(&mut trits, F_RS1, self.rs1.number() as i64);
524 }
525 if fmt.uses_rs2() {
526 put_field(&mut trits, F_RS2, self.rs2.number() as i64);
527 }
528 if fmt.uses_imm() {
529 put_field(&mut trits, F_IMM, self.imm.value() as i64);
530 }
531 Word::from_trits(trits)
532 }
533
534 /// Decodes a 27-trit word.
535 pub fn decode(word: Word) -> Result<Instruction, DecodeError> {
536 let trits = word.trits();
537 let op = Opcode::from_value(get_field(&trits, F_OPCODE))?;
538 let fmt = op.format();
539
540 let read = |used: bool, span, name| -> Result<i64, DecodeError> {
541 let v = get_field(&trits, span);
542 if !used && v != 0 {
543 return Err(DecodeError::NonZeroUnusedField {
544 field: name,
545 value: v,
546 });
547 }
548 Ok(if used { v } else { 0 })
549 };
550
551 let rd = read(fmt.uses_rd(), F_RD, "rd")?;
552 let rs1 = read(fmt.uses_rs1(), F_RS1, "rs1")?;
553 let rs2 = read(fmt.uses_rs2(), F_RS2, "rs2")?;
554 let imm = read(fmt.uses_imm(), F_IMM, "imm")?;
555
556 Ok(Instruction {
557 op,
558 // Field widths guarantee these ranges, so the unwraps cannot fire.
559 rd: Reg::new(rd as i8).expect("3-trit field is always a valid register"),
560 rs1: Reg::new(rs1 as i8).expect("3-trit field is always a valid register"),
561 rs2: Reg::new(rs2 as i8).expect("3-trit field is always a valid register"),
562 imm: Imm::new(imm as i32).expect("12-trit field is always a valid immediate"),
563 })
564 }
565}
566
567impl fmt::Display for Instruction {
568 /// Prints only the operands the format uses.
569 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
570 let m = self.op.mnemonic();
571 match self.op.format() {
572 Format::R => write!(f, "{m} {}, {}, {}", self.rd, self.rs1, self.rs2),
573 Format::I => write!(f, "{m} {}, {}, {}", self.rd, self.rs1, self.imm),
574 Format::U => write!(f, "{m} {}, {}", self.rd, self.rs1),
575 Format::B => write!(f, "{m} {}, {}", self.rs1, self.imm),
576 Format::J => write!(f, "{m} {}, {}", self.rd, self.imm),
577 Format::N => write!(f, "{m}"),
578 }
579 }
580}