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 inputs(&self) -> Vec<(DataType, String)> {
13        vec![(DataType::VoidPointer, "*addr".to_owned())]
14    }
15
16    fn outputs(&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 crate::library::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    #[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    #[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        ) -> Vec<BFieldElement> {
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 mut squeezed = sponge.as_mut().unwrap().squeeze();
93            squeezed.reverse();
94            stack.extend(squeezed);
95
96            // Pop returned digest
97            let digest = pop_encodable::<Digest>(stack);
98
99            // Remove 5 more words:
100            for _ in 0..Digest::LEN {
101                stack.pop().unwrap();
102            }
103
104            // Remove pointer
105            let input_pointer_plus_size = stack.pop().unwrap();
106
107            // Put digest back on stack
108            stack.extend(digest.reversed().values().to_vec());
109
110            stack.push(input_pointer_plus_size);
111
112            // _ d4 d3 d2 d1 d0 *ret_addr
113
114            vec![]
115        }
116
117        fn pseudorandom_initial_state(
118            &self,
119            seed: [u8; 32],
120            _bench_case: Option<BenchmarkCase>,
121        ) -> ProcedureInitialState {
122            let mut rng = StdRng::from_seed(seed);
123            let memory_start: BFieldElement = rng.random();
124            let memory: HashMap<BFieldElement, BFieldElement> = (0..self.size)
125                .map(|i| (memory_start + BFieldElement::new(i as u64), rng.random()))
126                .collect();
127
128            let nondeterminism = NonDeterminism::default().with_ram(memory);
129            ProcedureInitialState {
130                stack: [self.init_stack_for_isolated_run(), vec![memory_start]].concat(),
131                nondeterminism,
132                public_input: vec![],
133                sponge: None,
134            }
135        }
136    }
137}
138
139#[cfg(test)]
140mod benches {
141    use super::*;
142    use crate::test_prelude::*;
143
144    // Picked to be the size of a main table row at time of writing
145    #[test]
146    fn hash_var_lenstatic_size_benchmark_356() {
147        ShadowedProcedure::new(HashStaticSize { size: 356 }).bench();
148    }
149
150    // Picked to be the size of a auxiliary table row at time of writing
151    #[test]
152    fn hash_var_lenstatic_size_benchmark_249() {
153        ShadowedProcedure::new(HashStaticSize { size: 249 }).bench();
154    }
155
156    // Picked to be the size of a quotient table row at time of writing
157    #[test]
158    fn hash_var_lenstatic_size_benchmark_12() {
159        ShadowedProcedure::new(HashStaticSize { size: 12 }).bench();
160    }
161
162    // Picked to compare with same size of benchmark for `hash_varlen` at time of writing
163    #[test]
164    fn hash_var_lenstatic_size_benchmark_1000() {
165        ShadowedProcedure::new(HashStaticSize { size: 1000 }).bench();
166    }
167}
tasm_lib/hashing/algebraic_hasher/hash_static_size.rs

tasm_lib/hashing/algebraic_hasher/
hash_static_size.rs
