tasm_lib/traits/
read_only_algorithm.rs

1use std::collections::HashMap;
2use std::collections::VecDeque;
3
4use rand::prelude::*;
5use triton_vm::prelude::*;
6
7use super::basic_snippet::BasicSnippet;
8use super::rust_shadow::RustShadow;
9use crate::linker::execute_bench;
10use crate::prelude::Tip5;
11use crate::snippet_bencher::write_benchmarks;
12use crate::snippet_bencher::BenchmarkCase;
13use crate::snippet_bencher::NamedBenchmarkResult;
14use crate::test_helpers::test_rust_equivalence_given_complete_state;
15use crate::InitVmState;
16
17/// An ReadOnlyAlgorithm can read memory and take ND_input.
18///
19/// An ReadOnlyAlgorithm is a piece of tasm code that can read memory and read
20/// from non-determinism.
21///
22/// See also: [closure], [function], [procedure], [accessor], [mem_preserver],
23///           [algorithm]
24///
25/// [closure]: crate::traits::closure::Closure
26/// [function]: crate::traits::function::Function
27/// [procedure]: crate::traits::procedure::Procedure
28/// [accessor]: crate::traits::accessor::Accessor
29/// [mem_preserver]: crate::traits::mem_preserver::MemPreserver
30/// [algorithm]: crate::traits::algorithm::Algorithm
31pub trait ReadOnlyAlgorithm: BasicSnippet {
32    fn rust_shadow(
33        &self,
34        stack: &mut Vec<BFieldElement>,
35        memory: &HashMap<BFieldElement, BFieldElement>,
36        nd_tokens: VecDeque<BFieldElement>,
37        nd_digests: VecDeque<Digest>,
38    );
39
40    fn pseudorandom_initial_state(
41        &self,
42        seed: [u8; 32],
43        bench_case: Option<BenchmarkCase>,
44    ) -> ReadOnlyAlgorithmInitialState;
45
46    fn corner_case_initial_states(&self) -> Vec<ReadOnlyAlgorithmInitialState> {
47        vec![]
48    }
49}
50
51#[derive(Debug, Clone, Default)]
52pub struct ReadOnlyAlgorithmInitialState {
53    pub stack: Vec<BFieldElement>,
54    pub nondeterminism: NonDeterminism,
55}
56
57impl From<ReadOnlyAlgorithmInitialState> for InitVmState {
58    fn from(value: ReadOnlyAlgorithmInitialState) -> Self {
59        Self {
60            stack: value.stack,
61            nondeterminism: value.nondeterminism,
62            ..Default::default()
63        }
64    }
65}
66
67pub struct ShadowedReadOnlyAlgorithm<T: ReadOnlyAlgorithm> {
68    algorithm: T,
69}
70
71impl<T: ReadOnlyAlgorithm> ShadowedReadOnlyAlgorithm<T> {
72    pub fn new(algorithm: T) -> Self {
73        Self { algorithm }
74    }
75}
76
77impl<T> RustShadow for ShadowedReadOnlyAlgorithm<T>
78where
79    T: ReadOnlyAlgorithm,
80{
81    fn inner(&self) -> &dyn BasicSnippet {
82        &self.algorithm
83    }
84
85    fn rust_shadow_wrapper(
86        &self,
87        _stdin: &[BFieldElement],
88        nondeterminism: &NonDeterminism,
89        stack: &mut Vec<BFieldElement>,
90        memory: &mut HashMap<BFieldElement, BFieldElement>,
91        _sponge: &mut Option<Tip5>,
92    ) -> Vec<BFieldElement> {
93        self.algorithm.rust_shadow(
94            stack,
95            memory,
96            nondeterminism.individual_tokens.to_owned().into(),
97            nondeterminism.digests.to_owned().into(),
98        );
99        vec![]
100    }
101
102    fn test(&self) {
103        for corner_case in self.algorithm.corner_case_initial_states() {
104            let stdin = vec![];
105            test_rust_equivalence_given_complete_state(
106                self,
107                &corner_case.stack,
108                &stdin,
109                &corner_case.nondeterminism,
110                &None,
111                None,
112            );
113        }
114
115        let num_states = 10;
116        let mut rng = StdRng::from_seed(rand::random());
117        for _ in 0..num_states {
118            let ReadOnlyAlgorithmInitialState {
119                stack,
120                nondeterminism,
121            } = self
122                .algorithm
123                .pseudorandom_initial_state(rng.random(), None);
124
125            let stdin = vec![];
126            test_rust_equivalence_given_complete_state(
127                self,
128                &stack,
129                &stdin,
130                &nondeterminism,
131                &None,
132                None,
133            );
134        }
135    }
136
137    fn bench(&self) {
138        let mut rng = StdRng::from_seed(
139            hex::decode("73a24b6b8b32e4d7d563a4d9a85f476573a24b6b8b32e4d7d563a4d9a85f4765")
140                .unwrap()
141                .try_into()
142                .unwrap(),
143        );
144        let mut benchmarks = Vec::with_capacity(2);
145
146        for bench_case in [BenchmarkCase::CommonCase, BenchmarkCase::WorstCase] {
147            let ReadOnlyAlgorithmInitialState {
148                stack,
149                nondeterminism,
150            } = self
151                .algorithm
152                .pseudorandom_initial_state(rng.random(), Some(bench_case));
153            let program = self.algorithm.link_for_isolated_run();
154            let benchmark = execute_bench(&program, &stack, vec![], nondeterminism, None);
155            let benchmark = NamedBenchmarkResult {
156                name: self.algorithm.entrypoint(),
157                benchmark_result: benchmark,
158                case: bench_case,
159            };
160            benchmarks.push(benchmark);
161        }
162
163        write_benchmarks(benchmarks);
164    }
165}
tasm_lib/traits/read_only_algorithm.rs

tasm_lib/traits/
read_only_algorithm.rs
