tasm_lib/hashing/algebraic_hasher/
hash_static_size.rs

1use triton_vm::prelude::*;
2
3use crate::hashing::absorb_multiple_static_size::AbsorbMultipleStaticSize;
4use crate::prelude::*;
5
6#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
7pub struct HashStaticSize {
8    pub size: usize,
9}
10
11impl BasicSnippet for HashStaticSize {
12    fn parameters(&self) -> Vec<(DataType, String)> {
13        vec![(DataType::VoidPointer, "*addr".to_owned())]
14    }
15
16    fn return_values(&self) -> Vec<(DataType, String)> {
17        vec![
18            (DataType::Digest, "digest".to_owned()),
19            (DataType::VoidPointer, "*addr + size".to_owned()),
20        ]
21    }
22
23    fn entrypoint(&self) -> String {
24        format!(
25            "tasmlib_hashing_algebraic_hasher_hash_static_size_{}",
26            self.size
27        )
28    }
29
30    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
31        let entrypoint = self.entrypoint();
32        let absorb_subroutine =
33            library.import(Box::new(AbsorbMultipleStaticSize { size: self.size }));
34
35        triton_asm!(
36            // BEFORE:      _ *addr
37            // AFTER:       _ (*addr + size) digest[4] digest[3] digest[2] digest[1] digest[0]
38            {entrypoint}:
39                sponge_init
40                call {absorb_subroutine}
41                sponge_squeeze  // _ *ret_addr d[9] d[8] d[7] d[6] d[5] d[4] d[3] d[2] d[1] d[0]
42                swap 6 pop 1
43                swap 6 pop 1
44                swap 6 pop 1
45                swap 6 pop 1
46                swap 6
47                swap 1 pop 1
48                // _ d[4] d[3] d[2] d[1] d[0] *ret_addr
49                return
50        )
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use twenty_first::prelude::*;
57
58    use super::*;
59    use crate::test_prelude::*;
60
61    #[macro_rules_attr::apply(test)]
62    fn hash_static_size_small_pbt() {
63        for size in 0..20 {
64            println!("Testing size {size}");
65            ShadowedProcedure::new(HashStaticSize { size }).test();
66        }
67    }
68
69    #[macro_rules_attr::apply(proptest(cases = 50))]
70    fn hash_static_size_pbt_pbt(#[strategy(arb())] size: u8) {
71        ShadowedProcedure::new(HashStaticSize {
72            size: size as usize,
73        })
74        .test();
75    }
76
77    impl Procedure for HashStaticSize {
78        fn rust_shadow(
79            &self,
80            stack: &mut Vec<BFieldElement>,
81            memory: &mut HashMap<BFieldElement, BFieldElement>,
82            nondeterminism: &NonDeterminism,
83            public_input: &[BFieldElement],
84            sponge: &mut Option<Tip5>,
85        ) -> Result<Vec<BFieldElement>, RustShadowError> {
86            *sponge = Some(Tip5::init());
87
88            let absorb_snippet = AbsorbMultipleStaticSize { size: self.size };
89            absorb_snippet.rust_shadow(stack, memory, nondeterminism, public_input, sponge)?;
90
91            // Sponge-squeeze
92            let Some(sponge) = sponge.as_mut() else {
93                return Err(RustShadowError::SpongeUninitialized);
94            };
95            let mut squeezed = sponge.squeeze();
96            squeezed.reverse();
97            stack.extend(squeezed);
98
99            // Pop returned digest
100            let digest = pop_encodable::<Digest>(stack)?;
101
102            // Remove 5 more words:
103            for _ in 0..Digest::LEN {
104                stack.pop().ok_or(RustShadowError::StackUnderflow)?;
105            }
106
107            // Remove pointer
108            let input_pointer_plus_size = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
109
110            // Put digest back on stack
111            stack.extend(digest.reversed().values().to_vec());
112
113            stack.push(input_pointer_plus_size);
114
115            // _ d4 d3 d2 d1 d0 *ret_addr
116
117            Ok(Vec::new())
118        }
119
120        fn pseudorandom_initial_state(
121            &self,
122            seed: [u8; 32],
123            _bench_case: Option<BenchmarkCase>,
124        ) -> ProcedureInitialState {
125            let mut rng = StdRng::from_seed(seed);
126            let memory_start: BFieldElement = rng.random();
127            let memory: HashMap<BFieldElement, BFieldElement> = (0..self.size)
128                .map(|i| (memory_start + BFieldElement::new(i as u64), rng.random()))
129                .collect();
130
131            let nondeterminism = NonDeterminism::default().with_ram(memory);
132            ProcedureInitialState {
133                stack: [self.init_stack_for_isolated_run(), vec![memory_start]].concat(),
134                nondeterminism,
135                public_input: vec![],
136                sponge: None,
137            }
138        }
139    }
140}
141
142#[cfg(test)]
143mod benches {
144    use super::*;
145    use crate::test_prelude::*;
146
147    // Picked to be the size of a main table row at time of writing
148    #[macro_rules_attr::apply(test)]
149    fn hash_var_lenstatic_size_benchmark_356() {
150        ShadowedProcedure::new(HashStaticSize { size: 356 }).bench();
151    }
152
153    // Picked to be the size of a auxiliary table row at time of writing
154    #[macro_rules_attr::apply(test)]
155    fn hash_var_lenstatic_size_benchmark_249() {
156        ShadowedProcedure::new(HashStaticSize { size: 249 }).bench();
157    }
158
159    // Picked to be the size of a quotient table row at time of writing
160    #[macro_rules_attr::apply(test)]
161    fn hash_var_lenstatic_size_benchmark_12() {
162        ShadowedProcedure::new(HashStaticSize { size: 12 }).bench();
163    }
164
165    // Picked to compare with same size of benchmark for `hash_varlen` at time of writing
166    #[macro_rules_attr::apply(test)]
167    fn hash_var_lenstatic_size_benchmark_1000() {
168        ShadowedProcedure::new(HashStaticSize { size: 1000 }).bench();
169    }
170}
tasm_lib/hashing/algebraic_hasher/hash_static_size.rs

tasm_lib/hashing/algebraic_hasher/
hash_static_size.rs
