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

tasm_lib/traits/
read_only_algorithm.rs
