tasm_lib/hashing/algebraic_hasher/
hash_varlen.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::hashing::absorb_multiple::AbsorbMultiple;
6use crate::prelude::*;
7use crate::traits::basic_snippet::Reviewer;
8use crate::traits::basic_snippet::SignOffFingerprint;
9
10/// Calculate hash of a raw sequence of [`BFieldElement`]s.
11///
12/// ### Behavior
13///
14/// ```text
15/// BEFORE: _ *array [length: u32]
16/// AFTER:  _ [digest: Digest]
17/// ```
18///
19/// ### Preconditions
20///
21/// - all input arguments are properly [`BFieldCodec`] encoded
22///
23/// ### Postconditions
24///
25/// None.
26#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
27pub struct HashVarlen;
28
29impl BasicSnippet for HashVarlen {
30    fn parameters(&self) -> Vec<(DataType, String)> {
31        vec![
32            (DataType::VoidPointer, "*addr".to_owned()),
33            (DataType::U32, "length".to_owned()),
34        ]
35    }
36
37    fn return_values(&self) -> Vec<(DataType, String)> {
38        vec![(DataType::Digest, "digest".to_owned())]
39    }
40
41    fn entrypoint(&self) -> String {
42        "tasmlib_hashing_algebraic_hasher_hash_varlen".to_owned()
43    }
44
45    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
46        let absorb_subroutine = library.import(Box::new(AbsorbMultiple));
47
48        triton_asm!(
49            // BEFORE:      _ addr [len: u32]
50            // AFTER:       _ [digest: Digest]
51            {self.entrypoint()}:
52                sponge_init
53                call {absorb_subroutine}
54                sponge_squeeze  // _ d_9 d_8 d_7 d_6 d_5 [digest: Digest]
55                pick 9
56                pick 9
57                pick 9
58                pick 9
59                pick 9
60                pop 5           // _ [digest: Digest]
61                return
62        )
63    }
64
65    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
66        let mut sign_offs = HashMap::new();
67        sign_offs.insert(Reviewer("ferdinand"), 0x210c72ced00922c8.into());
68        sign_offs
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use std::collections::VecDeque;
75
76    use twenty_first::prelude::*;
77
78    use super::*;
79    use crate::empty_stack;
80    use crate::test_prelude::*;
81
82    impl MemPreserver for HashVarlen {
83        fn rust_shadow(
84            &self,
85            stack: &mut Vec<BFieldElement>,
86            memory: &HashMap<BFieldElement, BFieldElement>,
87            nd_tokens: VecDeque<BFieldElement>,
88            nd_digests: VecDeque<Digest>,
89            stdin: VecDeque<BFieldElement>,
90            sponge: &mut Option<Tip5>,
91        ) -> Result<Vec<BFieldElement>, RustShadowError> {
92            *sponge = Some(Tip5::init());
93            AbsorbMultiple.rust_shadow(stack, memory, nd_tokens, nd_digests, stdin, sponge)?;
94            let Some(sponge) = sponge.as_mut() else {
95                return Err(RustShadowError::SpongeUninitialized);
96            };
97            let [d0, d1, d2, d3, d4, ..] = sponge.squeeze();
98            push_encodable(stack, &Digest::new([d0, d1, d2, d3, d4]));
99
100            Ok(Vec::new())
101        }
102
103        fn pseudorandom_initial_state(
104            &self,
105            seed: [u8; 32],
106            bench_case: Option<BenchmarkCase>,
107        ) -> MemPreserverInitialState {
108            let mut rng = StdRng::from_seed(seed);
109            let length = match bench_case {
110                Some(BenchmarkCase::CommonCase) => 25,
111                Some(BenchmarkCase::WorstCase) => 1000,
112                None => rng.random_range(0..400),
113            };
114
115            let address = rng.random::<BFieldElement>();
116            let ram: HashMap<_, _> = (0..length)
117                .map(|i| (address + bfe!(i), rng.random()))
118                .collect();
119
120            MemPreserverInitialState {
121                stack: [empty_stack(), bfe_vec![address, length]].concat(),
122                nondeterminism: NonDeterminism::default().with_ram(ram),
123                ..MemPreserverInitialState::default()
124            }
125        }
126    }
127
128    #[macro_rules_attr::apply(test)]
129    fn test() {
130        ShadowedMemPreserver::new(HashVarlen).test();
131    }
132}
133
134#[cfg(test)]
135mod benches {
136    use super::*;
137    use crate::test_prelude::*;
138
139    #[macro_rules_attr::apply(test)]
140    fn benchmark() {
141        ShadowedMemPreserver::new(HashVarlen).bench();
142    }
143}
tasm_lib/hashing/algebraic_hasher/hash_varlen.rs

tasm_lib/hashing/algebraic_hasher/
hash_varlen.rs
