triton_isa/
instruction.rs

1use std::collections::HashMap;
2use std::fmt::Display;
3use std::fmt::Formatter;
4use std::fmt::Result as FmtResult;
5use std::num::TryFromIntError;
6use std::result;
7
8use arbitrary::Arbitrary;
9use arbitrary::Unstructured;
10use get_size2::GetSize;
11use itertools::Itertools;
12use lazy_static::lazy_static;
13use num_traits::ConstZero;
14use serde::Deserialize;
15use serde::Serialize;
16use strum::EnumCount;
17use strum::EnumIter;
18use strum::IntoEnumIterator;
19use thiserror::Error;
20use twenty_first::prelude::*;
21
22use crate::op_stack::NumberOfWords;
23use crate::op_stack::OpStackElement;
24use crate::op_stack::OpStackError;
25
26type Result<T> = result::Result<T, InstructionError>;
27
28/// An `Instruction` has `call` addresses encoded as absolute integers.
29pub type Instruction = AnInstruction<BFieldElement>;
30
31pub const ALL_INSTRUCTIONS: [Instruction; Instruction::COUNT] = [
32    Instruction::Pop(NumberOfWords::N1),
33    Instruction::Push(BFieldElement::ZERO),
34    Instruction::Divine(NumberOfWords::N1),
35    Instruction::Pick(OpStackElement::ST0),
36    Instruction::Place(OpStackElement::ST0),
37    Instruction::Dup(OpStackElement::ST0),
38    Instruction::Swap(OpStackElement::ST0),
39    Instruction::Halt,
40    Instruction::Nop,
41    Instruction::Skiz,
42    Instruction::Call(BFieldElement::ZERO),
43    Instruction::Return,
44    Instruction::Recurse,
45    Instruction::RecurseOrReturn,
46    Instruction::Assert,
47    Instruction::ReadMem(NumberOfWords::N1),
48    Instruction::WriteMem(NumberOfWords::N1),
49    Instruction::Hash,
50    Instruction::AssertVector,
51    Instruction::SpongeInit,
52    Instruction::SpongeAbsorb,
53    Instruction::SpongeAbsorbMem,
54    Instruction::SpongeSqueeze,
55    Instruction::Add,
56    Instruction::AddI(BFieldElement::ZERO),
57    Instruction::Mul,
58    Instruction::Invert,
59    Instruction::Eq,
60    Instruction::Split,
61    Instruction::Lt,
62    Instruction::And,
63    Instruction::Xor,
64    Instruction::Log2Floor,
65    Instruction::Pow,
66    Instruction::DivMod,
67    Instruction::PopCount,
68    Instruction::XxAdd,
69    Instruction::XxMul,
70    Instruction::XInvert,
71    Instruction::XbMul,
72    Instruction::ReadIo(NumberOfWords::N1),
73    Instruction::WriteIo(NumberOfWords::N1),
74    Instruction::MerkleStep,
75    Instruction::MerkleStepMem,
76    Instruction::XxDotStep,
77    Instruction::XbDotStep,
78];
79
80pub const ALL_INSTRUCTION_NAMES: [&str; Instruction::COUNT] = {
81    let mut names = [""; Instruction::COUNT];
82    let mut i = 0;
83    while i < Instruction::COUNT {
84        names[i] = ALL_INSTRUCTIONS[i].name();
85        i += 1;
86    }
87    names
88};
89
90lazy_static! {
91    pub static ref OPCODE_TO_INSTRUCTION_MAP: HashMap<u32, Instruction> = {
92        let mut opcode_to_instruction_map = HashMap::new();
93        for instruction in Instruction::iter() {
94            opcode_to_instruction_map.insert(instruction.opcode(), instruction);
95        }
96        opcode_to_instruction_map
97    };
98}
99
100/// A `LabelledInstruction` has `call` addresses encoded as label names.
101#[derive(Debug, Clone, Eq, PartialEq, Hash, EnumCount)]
102pub enum LabelledInstruction {
103    /// An instructions from the [instruction set architecture][isa].
104    ///
105    /// [isa]: https://triton-vm.org/spec/isa.html
106    Instruction(AnInstruction<String>),
107
108    /// Labels look like "`<name>:`" and are translated into absolute addresses.
109    Label(String),
110
111    Breakpoint,
112
113    TypeHint(TypeHint),
114
115    AssertionContext(AssertionContext),
116}
117
118/// A hint about a range of stack elements. Helps debugging programs written for Triton VM.
119/// **Does not enforce types.**
120///
121/// Usually constructed by parsing special annotations in the assembly code, for example:
122/// ```tasm
123/// hint variable_name: the_type = stack[0]
124/// hint my_list = stack[1..4]
125/// ```
126#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize, GetSize)]
127pub struct TypeHint {
128    pub starting_index: usize,
129    pub length: usize,
130
131    /// The name of the type, _e.g._, `u32`, `list`, `Digest`, et cetera.
132    pub type_name: Option<String>,
133
134    /// The name of the variable.
135    pub variable_name: String,
136}
137
138/// Context to help debugging failing instructions [`assert`](Instruction::Assert) or
139/// [`assert_vector`](Instruction::AssertVector).
140#[non_exhaustive]
141#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize, GetSize, Arbitrary)]
142pub enum AssertionContext {
143    ID(i128),
144    // Message(String),
145}
146
147impl LabelledInstruction {
148    pub const fn op_stack_size_influence(&self) -> i32 {
149        match self {
150            LabelledInstruction::Instruction(instruction) => instruction.op_stack_size_influence(),
151            _ => 0,
152        }
153    }
154}
155
156impl Display for LabelledInstruction {
157    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
158        match self {
159            LabelledInstruction::Instruction(instruction) => write!(f, "{instruction}"),
160            LabelledInstruction::Label(label) => write!(f, "{label}:"),
161            LabelledInstruction::Breakpoint => write!(f, "break"),
162            LabelledInstruction::TypeHint(type_hint) => write!(f, "{type_hint}"),
163            LabelledInstruction::AssertionContext(ctx) => write!(f, "{ctx}"),
164        }
165    }
166}
167
168impl Display for TypeHint {
169    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
170        let variable = &self.variable_name;
171
172        let format_type = |t| format!(": {t}");
173        let maybe_type = self.type_name.as_ref();
174        let type_name = maybe_type.map(format_type).unwrap_or_default();
175
176        let start = self.starting_index;
177        let range = match self.length {
178            1 => format!("{start}"),
179            _ => format!("{start}..{end}", end = start + self.length),
180        };
181
182        write!(f, "hint {variable}{type_name} = stack[{range}]")
183    }
184}
185
186impl Display for AssertionContext {
187    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
188        let Self::ID(id) = self;
189        write!(f, "error_id {id}")
190    }
191}
192
193impl<'a> Arbitrary<'a> for TypeHint {
194    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
195        let starting_index = u.arbitrary()?;
196        let length = u.int_in_range(1..=500)?;
197        let type_name = if u.arbitrary()? {
198            Some(u.arbitrary::<TypeHintTypeName>()?.into())
199        } else {
200            None
201        };
202        let variable_name = u.arbitrary::<TypeHintVariableName>()?.into();
203
204        let type_hint = Self {
205            starting_index,
206            length,
207            type_name,
208            variable_name,
209        };
210        Ok(type_hint)
211    }
212}
213
214/// A Triton VM instruction. See the
215/// [Instruction Set Architecture](https://triton-vm.org/spec/isa.html)
216/// for more details.
217///
218/// The type parameter `Dest` describes the type of addresses (absolute or labels).
219#[derive(
220    Debug,
221    Copy,
222    Clone,
223    Eq,
224    PartialEq,
225    Hash,
226    EnumCount,
227    EnumIter,
228    Serialize,
229    Deserialize,
230    GetSize,
231    Arbitrary,
232)]
233pub enum AnInstruction<Dest: PartialEq + Default> {
234    // OpStack manipulation
235    Pop(NumberOfWords),
236    Push(BFieldElement),
237    Divine(NumberOfWords),
238    Pick(OpStackElement),
239    Place(OpStackElement),
240    Dup(OpStackElement),
241    Swap(OpStackElement),
242
243    // Control flow
244    Halt,
245    Nop,
246    Skiz,
247    Call(Dest),
248    Return,
249    Recurse,
250    RecurseOrReturn,
251    Assert,
252
253    // Memory access
254    ReadMem(NumberOfWords),
255    WriteMem(NumberOfWords),
256
257    // Hashing-related
258    Hash,
259    AssertVector,
260    SpongeInit,
261    SpongeAbsorb,
262    SpongeAbsorbMem,
263    SpongeSqueeze,
264
265    // Base field arithmetic on stack
266    Add,
267    AddI(BFieldElement),
268    Mul,
269    Invert,
270    Eq,
271
272    // Bitwise arithmetic on stack
273    Split,
274    Lt,
275    And,
276    Xor,
277    Log2Floor,
278    Pow,
279    DivMod,
280    PopCount,
281
282    // Extension field arithmetic on stack
283    XxAdd,
284    XxMul,
285    XInvert,
286    XbMul,
287
288    // Read/write
289    ReadIo(NumberOfWords),
290    WriteIo(NumberOfWords),
291
292    // Many-in-One
293    MerkleStep,
294    MerkleStepMem,
295    XxDotStep,
296    XbDotStep,
297}
298
299impl<Dest: PartialEq + Default> AnInstruction<Dest> {
300    /// Assign a unique positive integer to each `Instruction`.
301    pub const fn opcode(&self) -> u32 {
302        match self {
303            AnInstruction::Pop(_) => 3,
304            AnInstruction::Push(_) => 1,
305            AnInstruction::Divine(_) => 9,
306            AnInstruction::Pick(_) => 17,
307            AnInstruction::Place(_) => 25,
308            AnInstruction::Dup(_) => 33,
309            AnInstruction::Swap(_) => 41,
310            AnInstruction::Halt => 0,
311            AnInstruction::Nop => 8,
312            AnInstruction::Skiz => 2,
313            AnInstruction::Call(_) => 49,
314            AnInstruction::Return => 16,
315            AnInstruction::Recurse => 24,
316            AnInstruction::RecurseOrReturn => 32,
317            AnInstruction::Assert => 10,
318            AnInstruction::ReadMem(_) => 57,
319            AnInstruction::WriteMem(_) => 11,
320            AnInstruction::Hash => 18,
321            AnInstruction::AssertVector => 26,
322            AnInstruction::SpongeInit => 40,
323            AnInstruction::SpongeAbsorb => 34,
324            AnInstruction::SpongeAbsorbMem => 48,
325            AnInstruction::SpongeSqueeze => 56,
326            AnInstruction::Add => 42,
327            AnInstruction::AddI(_) => 65,
328            AnInstruction::Mul => 50,
329            AnInstruction::Invert => 64,
330            AnInstruction::Eq => 58,
331            AnInstruction::Split => 4,
332            AnInstruction::Lt => 6,
333            AnInstruction::And => 14,
334            AnInstruction::Xor => 22,
335            AnInstruction::Log2Floor => 12,
336            AnInstruction::Pow => 30,
337            AnInstruction::DivMod => 20,
338            AnInstruction::PopCount => 28,
339            AnInstruction::XxAdd => 66,
340            AnInstruction::XxMul => 74,
341            AnInstruction::XInvert => 72,
342            AnInstruction::XbMul => 82,
343            AnInstruction::ReadIo(_) => 73,
344            AnInstruction::WriteIo(_) => 19,
345            AnInstruction::MerkleStep => 36,
346            AnInstruction::MerkleStepMem => 44,
347            AnInstruction::XxDotStep => 80,
348            AnInstruction::XbDotStep => 88,
349        }
350    }
351
352    pub const fn name(&self) -> &'static str {
353        match self {
354            AnInstruction::Pop(_) => "pop",
355            AnInstruction::Push(_) => "push",
356            AnInstruction::Divine(_) => "divine",
357            AnInstruction::Pick(_) => "pick",
358            AnInstruction::Place(_) => "place",
359            AnInstruction::Dup(_) => "dup",
360            AnInstruction::Swap(_) => "swap",
361            AnInstruction::Halt => "halt",
362            AnInstruction::Nop => "nop",
363            AnInstruction::Skiz => "skiz",
364            AnInstruction::Call(_) => "call",
365            AnInstruction::Return => "return",
366            AnInstruction::Recurse => "recurse",
367            AnInstruction::RecurseOrReturn => "recurse_or_return",
368            AnInstruction::Assert => "assert",
369            AnInstruction::ReadMem(_) => "read_mem",
370            AnInstruction::WriteMem(_) => "write_mem",
371            AnInstruction::Hash => "hash",
372            AnInstruction::AssertVector => "assert_vector",
373            AnInstruction::SpongeInit => "sponge_init",
374            AnInstruction::SpongeAbsorb => "sponge_absorb",
375            AnInstruction::SpongeAbsorbMem => "sponge_absorb_mem",
376            AnInstruction::SpongeSqueeze => "sponge_squeeze",
377            AnInstruction::Add => "add",
378            AnInstruction::AddI(_) => "addi",
379            AnInstruction::Mul => "mul",
380            AnInstruction::Invert => "invert",
381            AnInstruction::Eq => "eq",
382            AnInstruction::Split => "split",
383            AnInstruction::Lt => "lt",
384            AnInstruction::And => "and",
385            AnInstruction::Xor => "xor",
386            AnInstruction::Log2Floor => "log_2_floor",
387            AnInstruction::Pow => "pow",
388            AnInstruction::DivMod => "div_mod",
389            AnInstruction::PopCount => "pop_count",
390            AnInstruction::XxAdd => "xx_add",
391            AnInstruction::XxMul => "xx_mul",
392            AnInstruction::XInvert => "x_invert",
393            AnInstruction::XbMul => "xb_mul",
394            AnInstruction::ReadIo(_) => "read_io",
395            AnInstruction::WriteIo(_) => "write_io",
396            AnInstruction::MerkleStep => "merkle_step",
397            AnInstruction::MerkleStepMem => "merkle_step_mem",
398            AnInstruction::XxDotStep => "xx_dot_step",
399            AnInstruction::XbDotStep => "xb_dot_step",
400        }
401    }
402
403    pub const fn opcode_b(&self) -> BFieldElement {
404        BFieldElement::new(self.opcode() as u64)
405    }
406
407    /// Number of words required to represent the instruction.
408    pub fn size(&self) -> usize {
409        match self {
410            AnInstruction::Pop(_) | AnInstruction::Push(_) => 2,
411            AnInstruction::Divine(_) => 2,
412            AnInstruction::Pick(_) | AnInstruction::Place(_) => 2,
413            AnInstruction::Dup(_) | AnInstruction::Swap(_) => 2,
414            AnInstruction::Call(_) => 2,
415            AnInstruction::ReadMem(_) | AnInstruction::WriteMem(_) => 2,
416            AnInstruction::AddI(_) => 2,
417            AnInstruction::ReadIo(_) | AnInstruction::WriteIo(_) => 2,
418            _ => 1,
419        }
420    }
421
422    /// Get the i'th instruction bit
423    pub fn ib(&self, arg: InstructionBit) -> BFieldElement {
424        bfe!((self.opcode() >> usize::from(arg)) & 1)
425    }
426
427    pub fn map_call_address<F, NewDest>(&self, f: F) -> AnInstruction<NewDest>
428    where
429        F: FnOnce(&Dest) -> NewDest,
430        NewDest: PartialEq + Default,
431    {
432        match self {
433            AnInstruction::Pop(x) => AnInstruction::Pop(*x),
434            AnInstruction::Push(x) => AnInstruction::Push(*x),
435            AnInstruction::Divine(x) => AnInstruction::Divine(*x),
436            AnInstruction::Pick(x) => AnInstruction::Pick(*x),
437            AnInstruction::Place(x) => AnInstruction::Place(*x),
438            AnInstruction::Dup(x) => AnInstruction::Dup(*x),
439            AnInstruction::Swap(x) => AnInstruction::Swap(*x),
440            AnInstruction::Halt => AnInstruction::Halt,
441            AnInstruction::Nop => AnInstruction::Nop,
442            AnInstruction::Skiz => AnInstruction::Skiz,
443            AnInstruction::Call(label) => AnInstruction::Call(f(label)),
444            AnInstruction::Return => AnInstruction::Return,
445            AnInstruction::Recurse => AnInstruction::Recurse,
446            AnInstruction::RecurseOrReturn => AnInstruction::RecurseOrReturn,
447            AnInstruction::Assert => AnInstruction::Assert,
448            AnInstruction::ReadMem(x) => AnInstruction::ReadMem(*x),
449            AnInstruction::WriteMem(x) => AnInstruction::WriteMem(*x),
450            AnInstruction::Hash => AnInstruction::Hash,
451            AnInstruction::AssertVector => AnInstruction::AssertVector,
452            AnInstruction::SpongeInit => AnInstruction::SpongeInit,
453            AnInstruction::SpongeAbsorb => AnInstruction::SpongeAbsorb,
454            AnInstruction::SpongeAbsorbMem => AnInstruction::SpongeAbsorbMem,
455            AnInstruction::SpongeSqueeze => AnInstruction::SpongeSqueeze,
456            AnInstruction::Add => AnInstruction::Add,
457            AnInstruction::AddI(x) => AnInstruction::AddI(*x),
458            AnInstruction::Mul => AnInstruction::Mul,
459            AnInstruction::Invert => AnInstruction::Invert,
460            AnInstruction::Eq => AnInstruction::Eq,
461            AnInstruction::Split => AnInstruction::Split,
462            AnInstruction::Lt => AnInstruction::Lt,
463            AnInstruction::And => AnInstruction::And,
464            AnInstruction::Xor => AnInstruction::Xor,
465            AnInstruction::Log2Floor => AnInstruction::Log2Floor,
466            AnInstruction::Pow => AnInstruction::Pow,
467            AnInstruction::DivMod => AnInstruction::DivMod,
468            AnInstruction::PopCount => AnInstruction::PopCount,
469            AnInstruction::XxAdd => AnInstruction::XxAdd,
470            AnInstruction::XxMul => AnInstruction::XxMul,
471            AnInstruction::XInvert => AnInstruction::XInvert,
472            AnInstruction::XbMul => AnInstruction::XbMul,
473            AnInstruction::ReadIo(x) => AnInstruction::ReadIo(*x),
474            AnInstruction::WriteIo(x) => AnInstruction::WriteIo(*x),
475            AnInstruction::MerkleStep => AnInstruction::MerkleStep,
476            AnInstruction::MerkleStepMem => AnInstruction::MerkleStepMem,
477            AnInstruction::XxDotStep => AnInstruction::XxDotStep,
478            AnInstruction::XbDotStep => AnInstruction::XbDotStep,
479        }
480    }
481
482    pub const fn op_stack_size_influence(&self) -> i32 {
483        match self {
484            AnInstruction::Pop(n) => -(n.num_words() as i32),
485            AnInstruction::Push(_) => 1,
486            AnInstruction::Divine(n) => n.num_words() as i32,
487            AnInstruction::Pick(_) => 0,
488            AnInstruction::Place(_) => 0,
489            AnInstruction::Dup(_) => 1,
490            AnInstruction::Swap(_) => 0,
491            AnInstruction::Halt => 0,
492            AnInstruction::Nop => 0,
493            AnInstruction::Skiz => -1,
494            AnInstruction::Call(_) => 0,
495            AnInstruction::Return => 0,
496            AnInstruction::Recurse => 0,
497            AnInstruction::RecurseOrReturn => 0,
498            AnInstruction::Assert => -1,
499            AnInstruction::ReadMem(n) => n.num_words() as i32,
500            AnInstruction::WriteMem(n) => -(n.num_words() as i32),
501            AnInstruction::Hash => -5,
502            AnInstruction::AssertVector => -5,
503            AnInstruction::SpongeInit => 0,
504            AnInstruction::SpongeAbsorb => -10,
505            AnInstruction::SpongeAbsorbMem => 0,
506            AnInstruction::SpongeSqueeze => 10,
507            AnInstruction::Add => -1,
508            AnInstruction::AddI(_) => 0,
509            AnInstruction::Mul => -1,
510            AnInstruction::Invert => 0,
511            AnInstruction::Eq => -1,
512            AnInstruction::Split => 1,
513            AnInstruction::Lt => -1,
514            AnInstruction::And => -1,
515            AnInstruction::Xor => -1,
516            AnInstruction::Log2Floor => 0,
517            AnInstruction::Pow => -1,
518            AnInstruction::DivMod => 0,
519            AnInstruction::PopCount => 0,
520            AnInstruction::XxAdd => -3,
521            AnInstruction::XxMul => -3,
522            AnInstruction::XInvert => 0,
523            AnInstruction::XbMul => -1,
524            AnInstruction::ReadIo(n) => n.num_words() as i32,
525            AnInstruction::WriteIo(n) => -(n.num_words() as i32),
526            AnInstruction::MerkleStep => 0,
527            AnInstruction::MerkleStepMem => 0,
528            AnInstruction::XxDotStep => 0,
529            AnInstruction::XbDotStep => 0,
530        }
531    }
532
533    /// Indicates whether the instruction operates on base field elements that are also u32s.
534    pub fn is_u32_instruction(&self) -> bool {
535        matches!(
536            self,
537            AnInstruction::Split
538                | AnInstruction::Lt
539                | AnInstruction::And
540                | AnInstruction::Xor
541                | AnInstruction::Log2Floor
542                | AnInstruction::Pow
543                | AnInstruction::DivMod
544                | AnInstruction::PopCount
545                | AnInstruction::MerkleStep
546                | AnInstruction::MerkleStepMem
547        )
548    }
549}
550
551impl<Dest: Display + PartialEq + Default> Display for AnInstruction<Dest> {
552    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
553        write!(f, "{}", self.name())?;
554        match self {
555            AnInstruction::Push(arg) => write!(f, " {arg}"),
556            AnInstruction::Pick(arg) => write!(f, " {arg}"),
557            AnInstruction::Place(arg) => write!(f, " {arg}"),
558            AnInstruction::Pop(arg) => write!(f, " {arg}"),
559            AnInstruction::Divine(arg) => write!(f, " {arg}"),
560            AnInstruction::Dup(arg) => write!(f, " {arg}"),
561            AnInstruction::Swap(arg) => write!(f, " {arg}"),
562            AnInstruction::Call(arg) => write!(f, " {arg}"),
563            AnInstruction::ReadMem(arg) => write!(f, " {arg}"),
564            AnInstruction::WriteMem(arg) => write!(f, " {arg}"),
565            AnInstruction::AddI(arg) => write!(f, " {arg}"),
566            AnInstruction::ReadIo(arg) => write!(f, " {arg}"),
567            AnInstruction::WriteIo(arg) => write!(f, " {arg}"),
568            _ => Ok(()),
569        }
570    }
571}
572
573impl Instruction {
574    /// Get the argument of the instruction, if it has one.
575    pub fn arg(&self) -> Option<BFieldElement> {
576        match self {
577            AnInstruction::Push(arg) => Some(*arg),
578            AnInstruction::Call(arg) => Some(*arg),
579            AnInstruction::Pop(arg) => Some(arg.into()),
580            AnInstruction::Divine(arg) => Some(arg.into()),
581            AnInstruction::Pick(arg) => Some(arg.into()),
582            AnInstruction::Place(arg) => Some(arg.into()),
583            AnInstruction::Dup(arg) => Some(arg.into()),
584            AnInstruction::Swap(arg) => Some(arg.into()),
585            AnInstruction::ReadMem(arg) => Some(arg.into()),
586            AnInstruction::WriteMem(arg) => Some(arg.into()),
587            AnInstruction::AddI(arg) => Some(*arg),
588            AnInstruction::ReadIo(arg) => Some(arg.into()),
589            AnInstruction::WriteIo(arg) => Some(arg.into()),
590            _ => None,
591        }
592    }
593
594    /// Change the argument of the instruction, if it has one. Returns an `Err` if the instruction
595    /// does not have an argument or if the argument is out of range.
596    pub fn change_arg(self, new_arg: BFieldElement) -> Result<Self> {
597        let illegal_argument_error = || InstructionError::IllegalArgument(self, new_arg);
598        let num_words = new_arg.try_into().map_err(|_| illegal_argument_error());
599        let op_stack_element = new_arg.try_into().map_err(|_| illegal_argument_error());
600
601        let new_instruction = match self {
602            AnInstruction::Pop(_) => AnInstruction::Pop(num_words?),
603            AnInstruction::Push(_) => AnInstruction::Push(new_arg),
604            AnInstruction::Divine(_) => AnInstruction::Divine(num_words?),
605            AnInstruction::Pick(_) => AnInstruction::Pick(op_stack_element?),
606            AnInstruction::Place(_) => AnInstruction::Place(op_stack_element?),
607            AnInstruction::Dup(_) => AnInstruction::Dup(op_stack_element?),
608            AnInstruction::Swap(_) => AnInstruction::Swap(op_stack_element?),
609            AnInstruction::Call(_) => AnInstruction::Call(new_arg),
610            AnInstruction::ReadMem(_) => AnInstruction::ReadMem(num_words?),
611            AnInstruction::WriteMem(_) => AnInstruction::WriteMem(num_words?),
612            AnInstruction::AddI(_) => AnInstruction::AddI(new_arg),
613            AnInstruction::ReadIo(_) => AnInstruction::ReadIo(num_words?),
614            AnInstruction::WriteIo(_) => AnInstruction::WriteIo(num_words?),
615            _ => return Err(illegal_argument_error()),
616        };
617
618        Ok(new_instruction)
619    }
620}
621
622impl TryFrom<u32> for Instruction {
623    type Error = InstructionError;
624
625    fn try_from(opcode: u32) -> Result<Self> {
626        OPCODE_TO_INSTRUCTION_MAP
627            .get(&opcode)
628            .copied()
629            .ok_or(InstructionError::InvalidOpcode(opcode))
630    }
631}
632
633impl TryFrom<u64> for Instruction {
634    type Error = InstructionError;
635
636    fn try_from(opcode: u64) -> Result<Self> {
637        let opcode = u32::try_from(opcode)?;
638        opcode.try_into()
639    }
640}
641
642impl TryFrom<usize> for Instruction {
643    type Error = InstructionError;
644
645    fn try_from(opcode: usize) -> Result<Self> {
646        let opcode = u32::try_from(opcode)?;
647        opcode.try_into()
648    }
649}
650
651impl TryFrom<BFieldElement> for Instruction {
652    type Error = InstructionError;
653
654    fn try_from(opcode: BFieldElement) -> Result<Self> {
655        let opcode = u32::try_from(opcode)?;
656        opcode.try_into()
657    }
658}
659
660/// Indicators for all the possible bits in an [`Instruction`].
661#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, EnumCount, EnumIter)]
662pub enum InstructionBit {
663    #[default]
664    IB0,
665    IB1,
666    IB2,
667    IB3,
668    IB4,
669    IB5,
670    IB6,
671}
672
673impl Display for InstructionBit {
674    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
675        let bit_index = usize::from(*self);
676        write!(f, "{bit_index}")
677    }
678}
679
680impl From<InstructionBit> for usize {
681    fn from(instruction_bit: InstructionBit) -> Self {
682        match instruction_bit {
683            InstructionBit::IB0 => 0,
684            InstructionBit::IB1 => 1,
685            InstructionBit::IB2 => 2,
686            InstructionBit::IB3 => 3,
687            InstructionBit::IB4 => 4,
688            InstructionBit::IB5 => 5,
689            InstructionBit::IB6 => 6,
690        }
691    }
692}
693
694impl TryFrom<usize> for InstructionBit {
695    type Error = String;
696
697    fn try_from(bit_index: usize) -> result::Result<Self, Self::Error> {
698        match bit_index {
699            0 => Ok(InstructionBit::IB0),
700            1 => Ok(InstructionBit::IB1),
701            2 => Ok(InstructionBit::IB2),
702            3 => Ok(InstructionBit::IB3),
703            4 => Ok(InstructionBit::IB4),
704            5 => Ok(InstructionBit::IB5),
705            6 => Ok(InstructionBit::IB6),
706            _ => Err(format!(
707                "Index {bit_index} is out of range for `InstructionBit`."
708            )),
709        }
710    }
711}
712
713impl<'a> Arbitrary<'a> for LabelledInstruction {
714    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
715        let instruction = match u.choose_index(LabelledInstruction::COUNT)? {
716            0 => u.arbitrary::<AnInstruction<String>>()?,
717            1 => return Ok(Self::Label(u.arbitrary::<InstructionLabel>()?.into())),
718            2 => return Ok(Self::Breakpoint),
719            3 => return Ok(Self::TypeHint(u.arbitrary()?)),
720            4 => return Ok(Self::AssertionContext(u.arbitrary()?)),
721            _ => unreachable!(),
722        };
723        let legal_label = String::from(u.arbitrary::<InstructionLabel>()?);
724        let instruction = instruction.map_call_address(|_| legal_label.clone());
725
726        Ok(Self::Instruction(instruction))
727    }
728}
729
730#[derive(Debug, Clone, Eq, PartialEq, Hash)]
731struct InstructionLabel(String);
732
733impl From<InstructionLabel> for String {
734    fn from(label: InstructionLabel) -> Self {
735        label.0
736    }
737}
738
739impl<'a> Arbitrary<'a> for InstructionLabel {
740    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
741        let legal_start_characters = ('a'..='z').chain('A'..='Z').chain('_'..='_');
742        let legal_characters = legal_start_characters
743            .clone()
744            .chain('0'..='9')
745            .chain('-'..='-')
746            .collect_vec();
747
748        let mut label = u.choose(&legal_start_characters.collect_vec())?.to_string();
749        for _ in 0..u.arbitrary_len::<char>()? {
750            label.push(*u.choose(&legal_characters)?);
751        }
752        while ALL_INSTRUCTION_NAMES.contains(&label.as_str()) {
753            label.push(*u.choose(&legal_characters)?);
754        }
755        Ok(Self(label))
756    }
757}
758
759#[derive(Debug, Clone, Eq, PartialEq, Hash)]
760struct TypeHintVariableName(String);
761
762impl From<TypeHintVariableName> for String {
763    fn from(label: TypeHintVariableName) -> Self {
764        label.0
765    }
766}
767
768impl<'a> Arbitrary<'a> for TypeHintVariableName {
769    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
770        let legal_start_characters = 'a'..='z';
771        let legal_characters = legal_start_characters
772            .clone()
773            .chain('0'..='9')
774            .chain('_'..='_')
775            .collect_vec();
776
777        let mut variable_name = u.choose(&legal_start_characters.collect_vec())?.to_string();
778        for _ in 0..u.arbitrary_len::<char>()? {
779            variable_name.push(*u.choose(&legal_characters)?);
780        }
781        Ok(Self(variable_name))
782    }
783}
784
785#[derive(Debug, Clone, Eq, PartialEq, Hash)]
786struct TypeHintTypeName(String);
787
788impl From<TypeHintTypeName> for String {
789    fn from(label: TypeHintTypeName) -> Self {
790        label.0
791    }
792}
793
794impl<'a> Arbitrary<'a> for TypeHintTypeName {
795    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
796        let legal_start_characters = ('a'..='z').chain('A'..='Z');
797        let legal_characters = legal_start_characters
798            .clone()
799            .chain('0'..='9')
800            .collect_vec();
801
802        let mut type_name = u.choose(&legal_start_characters.collect_vec())?.to_string();
803        for _ in 0..u.arbitrary_len::<char>()? {
804            type_name.push(*u.choose(&legal_characters)?);
805        }
806        Ok(Self(type_name))
807    }
808}
809
810#[non_exhaustive]
811#[derive(Debug, Clone, Eq, PartialEq, Error)]
812pub enum InstructionError {
813    #[error("opcode {0} is invalid")]
814    InvalidOpcode(u32),
815
816    #[error("opcode is out of range: {0}")]
817    OutOfRangeOpcode(#[from] TryFromIntError),
818
819    #[error("invalid argument {1} for instruction `{0}`")]
820    IllegalArgument(Instruction, BFieldElement),
821
822    #[error("instruction pointer points outside of program")]
823    InstructionPointerOverflow,
824
825    #[error("jump stack is empty")]
826    JumpStackIsEmpty,
827
828    #[error("assertion failed: {0}")]
829    AssertionFailed(AssertionError),
830
831    #[error("vector assertion failed because stack[{0}] != stack[{r}]: {1}", r = .0 + Digest::LEN)]
832    VectorAssertionFailed(usize, AssertionError),
833
834    #[error("0 does not have a multiplicative inverse")]
835    InverseOfZero,
836
837    #[error("division by 0 is impossible")]
838    DivisionByZero,
839
840    #[error("the Sponge state must be initialized before it can be used")]
841    SpongeNotInitialized,
842
843    #[error("the logarithm of 0 does not exist")]
844    LogarithmOfZero,
845
846    #[error("public input buffer is empty after {0} reads")]
847    EmptyPublicInput(usize),
848
849    #[error("secret input buffer is empty after {0} reads")]
850    EmptySecretInput(usize),
851
852    #[error("no more secret digests available")]
853    EmptySecretDigestInput,
854
855    #[error("Triton VM has halted and cannot execute any further instructions")]
856    MachineHalted,
857
858    #[error(transparent)]
859    OpStackError(#[from] OpStackError),
860}
861
862/// An error giving additional context to any failed assertion.
863#[non_exhaustive]
864#[derive(Debug, Clone, Eq, PartialEq, Error)]
865pub struct AssertionError {
866    /// The [element](BFieldElement) expected by the assertion.
867    pub expected: BFieldElement,
868
869    /// The actual [element](BFieldElement) encountered when executing the assertion.
870    pub actual: BFieldElement,
871
872    /// A user-defined error ID. Only has user-defined, no inherent, semantics.
873    pub id: Option<i128>,
874    //
875    // /// A user-defined error message supplying context to the failed assertion.
876    // pub message: Option<String>,
877}
878
879impl Display for AssertionError {
880    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
881        if let Some(id) = self.id {
882            write!(f, "[{id}] ")?;
883        }
884        write!(f, "expected {}, got {}", self.expected, self.actual)
885    }
886}
887
888impl AssertionError {
889    pub fn new(expected: impl Into<BFieldElement>, actual: impl Into<BFieldElement>) -> Self {
890        Self {
891            expected: expected.into(),
892            actual: actual.into(),
893            id: None,
894        }
895    }
896
897    #[must_use]
898    pub fn with_context(mut self, context: AssertionContext) -> Self {
899        match context {
900            AssertionContext::ID(id) => self.id = Some(id),
901        };
902        self
903    }
904}
905
906#[cfg(test)]
907pub mod tests {
908    use std::collections::HashMap;
909
910    use assert2::assert;
911    use itertools::Itertools;
912    use num_traits::One;
913    use num_traits::Zero;
914    use rand::Rng;
915    use strum::EnumCount;
916    use strum::IntoEnumIterator;
917    use strum::VariantNames;
918    use twenty_first::prelude::*;
919
920    use crate::triton_asm;
921    use crate::triton_program;
922
923    use super::*;
924
925    #[derive(Debug, Copy, Clone, EnumCount, EnumIter, VariantNames)]
926    pub enum InstructionBucket {
927        HasArg,
928        ShrinksStack,
929        IsU32,
930    }
931
932    impl InstructionBucket {
933        pub fn contains(self, instruction: Instruction) -> bool {
934            match self {
935                InstructionBucket::HasArg => instruction.arg().is_some(),
936                InstructionBucket::ShrinksStack => instruction.op_stack_size_influence() < 0,
937                InstructionBucket::IsU32 => instruction.is_u32_instruction(),
938            }
939        }
940
941        pub fn flag(self) -> u32 {
942            match self {
943                InstructionBucket::HasArg => 1,
944                InstructionBucket::ShrinksStack => 1 << 1,
945                InstructionBucket::IsU32 => 1 << 2,
946            }
947        }
948    }
949
950    impl Instruction {
951        pub fn flag_set(self) -> u32 {
952            InstructionBucket::iter()
953                .map(|bucket| u32::from(bucket.contains(self)) * bucket.flag())
954                .fold(0, |acc, bit_flag| acc | bit_flag)
955        }
956
957        fn computed_opcode(self) -> u32 {
958            let mut index_within_flag_set = 0;
959            for other_instruction in Instruction::iter() {
960                if other_instruction == self {
961                    break;
962                }
963                if other_instruction.flag_set() == self.flag_set() {
964                    index_within_flag_set += 1;
965                }
966            }
967
968            index_within_flag_set * 2_u32.pow(InstructionBucket::COUNT as u32) + self.flag_set()
969        }
970    }
971
972    #[test]
973    fn computed_and_actual_opcodes_are_identical() {
974        for instruction in Instruction::iter() {
975            let opcode = instruction.computed_opcode();
976            let name = instruction.name();
977            println!("{opcode: >3} {name}");
978        }
979
980        for instruction in Instruction::iter() {
981            let expected_opcode = instruction.computed_opcode();
982            let opcode = instruction.opcode();
983            assert!(expected_opcode == opcode, "{instruction}");
984        }
985    }
986
987    #[test]
988    fn opcodes_are_unique() {
989        let mut opcodes_to_instruction_map = HashMap::new();
990        for instruction in Instruction::iter() {
991            let opcode = instruction.opcode();
992            let maybe_entry = opcodes_to_instruction_map.insert(opcode, instruction);
993            if let Some(other_instruction) = maybe_entry {
994                panic!("{other_instruction} and {instruction} both have opcode {opcode}.");
995            }
996        }
997    }
998
999    #[test]
1000    fn number_of_instruction_bits_is_correct() {
1001        let all_opcodes = Instruction::iter().map(|instruction| instruction.opcode());
1002        let highest_opcode = all_opcodes.max().unwrap();
1003        let num_required_bits_for_highest_opcode = highest_opcode.ilog2() + 1;
1004        assert!(InstructionBit::COUNT == num_required_bits_for_highest_opcode as usize);
1005    }
1006
1007    #[test]
1008    fn parse_push_pop() {
1009        let program = triton_program!(push 1 push 1 add pop 2);
1010        let instructions = program.into_iter().collect_vec();
1011        let expected = vec![
1012            Instruction::Push(bfe!(1)),
1013            Instruction::Push(bfe!(1)),
1014            Instruction::Add,
1015            Instruction::Pop(NumberOfWords::N2),
1016        ];
1017
1018        assert!(expected == instructions);
1019    }
1020
1021    #[test]
1022    #[should_panic(expected = "Duplicate label: foo")]
1023    fn fail_on_duplicate_labels() {
1024        triton_program!(
1025            push 2
1026            call foo
1027            bar: push 2
1028            foo: push 3
1029            foo: push 4
1030            halt
1031        );
1032    }
1033
1034    #[test]
1035    fn ib_registers_are_binary() {
1036        for instruction in ALL_INSTRUCTIONS {
1037            for instruction_bit in InstructionBit::iter() {
1038                let ib_value = instruction.ib(instruction_bit);
1039                assert!(ib_value.is_zero() ^ ib_value.is_one());
1040            }
1041        }
1042    }
1043
1044    #[test]
1045    fn instruction_to_opcode_to_instruction_is_consistent() {
1046        for instr in ALL_INSTRUCTIONS {
1047            assert!(instr == instr.opcode().try_into().unwrap());
1048        }
1049    }
1050
1051    /// While the correct _number_ of instructions (respectively instruction names)
1052    /// is guaranteed at compile time, this test ensures the absence of repetitions.
1053    #[test]
1054    fn list_of_all_instructions_contains_unique_instructions() {
1055        assert!(ALL_INSTRUCTIONS.into_iter().all_unique());
1056        assert!(ALL_INSTRUCTION_NAMES.into_iter().all_unique());
1057    }
1058
1059    #[test]
1060    fn convert_various_types_to_instructions() {
1061        let _push = Instruction::try_from(1_usize).unwrap();
1062        let _dup = Instruction::try_from(9_u64).unwrap();
1063        let _swap = Instruction::try_from(17_u32).unwrap();
1064        let _pop = Instruction::try_from(3_usize).unwrap();
1065    }
1066
1067    #[test]
1068    fn change_arguments_of_various_instructions() {
1069        assert!(Instruction::Push(bfe!(0)).change_arg(bfe!(7)).is_ok());
1070        assert!(Instruction::Dup(OpStackElement::ST0)
1071            .change_arg(bfe!(1024))
1072            .is_err());
1073        assert!(Instruction::Swap(OpStackElement::ST0)
1074            .change_arg(bfe!(1337))
1075            .is_err());
1076        assert!(Instruction::Swap(OpStackElement::ST0)
1077            .change_arg(bfe!(0))
1078            .is_ok());
1079        assert!(Instruction::Swap(OpStackElement::ST0)
1080            .change_arg(bfe!(1))
1081            .is_ok());
1082        assert!(Instruction::Pop(NumberOfWords::N4)
1083            .change_arg(bfe!(0))
1084            .is_err());
1085        assert!(Instruction::Pop(NumberOfWords::N1)
1086            .change_arg(bfe!(2))
1087            .is_ok());
1088        assert!(Instruction::Nop.change_arg(bfe!(7)).is_err());
1089    }
1090
1091    #[test]
1092    fn print_various_instructions() {
1093        println!("instruction_push: {:?}", Instruction::Push(bfe!(7)));
1094        println!("instruction_assert: {}", Instruction::Assert);
1095        println!("instruction_invert: {:?}", Instruction::Invert);
1096        println!(
1097            "instruction_dup: {}",
1098            Instruction::Dup(OpStackElement::ST14)
1099        );
1100    }
1101
1102    #[test]
1103    fn instruction_size_is_consistent_with_having_arguments() {
1104        for instruction in Instruction::iter() {
1105            match instruction.arg() {
1106                Some(_) => assert!(2 == instruction.size()),
1107                None => assert!(1 == instruction.size()),
1108            }
1109        }
1110    }
1111
1112    #[test]
1113    fn opcodes_are_consistent_with_argument_indication_bit() {
1114        let argument_indicator_bit_mask = 1;
1115        for instruction in Instruction::iter() {
1116            let opcode = instruction.opcode();
1117            println!("Testing instruction {instruction} with opcode {opcode}.");
1118            let has_arg = instruction.arg().is_some();
1119            assert!(has_arg == (opcode & argument_indicator_bit_mask != 0));
1120        }
1121    }
1122
1123    #[test]
1124    fn opcodes_are_consistent_with_shrink_stack_indication_bit() {
1125        let shrink_stack_indicator_bit_mask = 2;
1126        for instruction in Instruction::iter() {
1127            let opcode = instruction.opcode();
1128            println!("Testing instruction {instruction} with opcode {opcode}.");
1129            let shrinks_stack = instruction.op_stack_size_influence() < 0;
1130            assert!(shrinks_stack == (opcode & shrink_stack_indicator_bit_mask != 0));
1131        }
1132    }
1133
1134    #[test]
1135    fn opcodes_are_consistent_with_u32_indication_bit() {
1136        let u32_indicator_bit_mask = 4;
1137        for instruction in Instruction::iter() {
1138            let opcode = instruction.opcode();
1139            println!("Testing instruction {instruction} with opcode {opcode}.");
1140            assert!(instruction.is_u32_instruction() == (opcode & u32_indicator_bit_mask != 0));
1141        }
1142    }
1143
1144    #[test]
1145    fn instruction_bits_are_consistent() {
1146        for instruction_bit in InstructionBit::iter() {
1147            println!("Testing instruction bit {instruction_bit}.");
1148            let bit_index = usize::from(instruction_bit);
1149            let recovered_instruction_bit = InstructionBit::try_from(bit_index).unwrap();
1150            assert!(instruction_bit == recovered_instruction_bit);
1151        }
1152    }
1153
1154    #[test]
1155    fn instruction_bit_conversion_fails_for_invalid_bit_index() {
1156        let invalid_bit_index = rand::rng().random_range(InstructionBit::COUNT..=usize::MAX);
1157        let maybe_instruction_bit = InstructionBit::try_from(invalid_bit_index);
1158        assert!(maybe_instruction_bit.is_err());
1159    }
1160
1161    #[test]
1162    fn stringify_some_instructions() {
1163        let instructions = triton_asm!(push 3 invert push 2 mul push 1 add write_io 1 halt);
1164        let code = instructions.iter().join("\n");
1165        println!("{code}");
1166    }
1167
1168    #[test]
1169    fn labelled_instructions_act_on_op_stack_as_indicated() {
1170        for instruction in ALL_INSTRUCTIONS {
1171            let labelled_instruction = instruction.map_call_address(|_| "dummy_label".to_string());
1172            let labelled_instruction = LabelledInstruction::Instruction(labelled_instruction);
1173
1174            assert!(
1175                instruction.op_stack_size_influence()
1176                    == labelled_instruction.op_stack_size_influence()
1177            );
1178        }
1179    }
1180
1181    #[test]
1182    fn labels_indicate_no_change_to_op_stack() {
1183        let labelled_instruction = LabelledInstruction::Label("dummy_label".to_string());
1184        assert!(0 == labelled_instruction.op_stack_size_influence());
1185    }
1186
1187    #[test]
1188    fn can_change_arg() {
1189        for instr in ALL_INSTRUCTIONS {
1190            if let Some(arg) = instr.arg() {
1191                let new_instr = instr.change_arg(arg + bfe!(1)).unwrap();
1192                assert_eq!(instr.opcode(), new_instr.opcode());
1193                assert_ne!(instr, new_instr);
1194            } else {
1195                assert!(instr.change_arg(bfe!(0)).is_err())
1196            }
1197        }
1198    }
1199}
triton_isa/instruction.rs

triton_isa/
instruction.rs
