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

triton_isa/
instruction.rs
