tasm_lib/memory/
memcpy.rs

1use triton_vm::prelude::*;
2
3use crate::prelude::*;
4use crate::structure::tasm_object::DEFAULT_MAX_DYN_FIELD_SIZE;
5
6#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, Hash)]
7pub struct MemCpy; // TODO: add field `static_length : Option<usize>` to avoid loop
8
9impl MemCpy {
10    pub const EXCEEDS_MAX_COPY_SIZE_ERROR_ID: i128 = 60;
11}
12
13impl BasicSnippet for MemCpy {
14    fn inputs(&self) -> Vec<(DataType, String)> {
15        vec![
16            (DataType::VoidPointer, "read_source".to_string()),
17            (DataType::VoidPointer, "write_dest".to_string()),
18            (DataType::U32, "num_words".to_string()),
19        ]
20    }
21
22    fn outputs(&self) -> Vec<(DataType, String)> {
23        vec![]
24    }
25
26    fn entrypoint(&self) -> String {
27        "tasmlib_memory_memcpy".to_string()
28    }
29
30    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
31        let entrypoint = self.entrypoint();
32        let copy_5_words_loop_label = format!("{entrypoint}_loop_copy_5_words");
33        let copy_single_words_loop_label = format!("{entrypoint}_loop_copy_single_words");
34        triton_asm!(
35        // BEFORE: _ read_source write_dest num_words
36        // AFTER:  _
37        {entrypoint}:
38            /* Cap size of memcpy operation */
39            push {DEFAULT_MAX_DYN_FIELD_SIZE}
40            dup 1
41            lt
42            // _ read_source write_dest (num_words < MAX)
43
44            assert error_id {Self::EXCEEDS_MAX_COPY_SIZE_ERROR_ID}
45            // _ read_source write_dest
46
47            pick 2
48            addi 4
49            place 2
50            // _ (read_source + 4) write_dest num_words
51
52            call {copy_5_words_loop_label}
53            // _ (read_source + 4) write_dest remaining_words
54
55            pick 2
56            addi -4
57            place 2
58            call {copy_single_words_loop_label}
59
60            pop 3
61
62            return
63
64        // INVARIANT:  _ (read_source + 4) write_dest remaining_words
65        {copy_5_words_loop_label}:
66            // termination condition
67            push 5
68            dup 1
69            lt
70            // _ (read_source + 4) write_dest remaining_words (5 > remaining_words)
71
72            skiz return
73            // _ (read_source + 4) write_dest remaining_words
74
75            // read
76            pick 2      // _ write_dest remaining_words (read_source + 4)
77            read_mem 5  // _ write_dest remaining_words [val4 val3 val2 val1 val0] (read_source - 1)
78            addi 10     // _ write_dest remaining_words [val4 val3 val2 val1 val0] (read_source + 9)
79            place 7     // _ (read_source + 9) write_dest remaining_words [val4 val3 val2 val1 val0]
80
81            // write
82            pick 6      // _ (read_source + 9) remaining_words [val4 val3 val2 val1 val0] write_dest
83            write_mem 5 // _ (read_source + 9) remaining_words (write_dest + 5)
84            place 1     // _ (read_source + 9) (write_dest + 5) remaining_words
85
86            addi -5     // _ (read_source + 9) (write_dest + 5) (remaining_words-5)
87            recurse
88
89        // BEFORE: _ read_source       write_dest       n
90        // AFTER:  _ (read_source + n) (write_dest + n) 0
91        {copy_single_words_loop_label}:
92            dup 0 push 0 eq
93            skiz return
94
95            pick 2
96            read_mem 1
97            addi 2
98            place 3
99
100            pick 2
101            write_mem 1
102            place 1
103
104            addi -1
105            recurse
106        )
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113    use crate::test_prelude::*;
114
115    impl Function for MemCpy {
116        fn rust_shadow(
117            &self,
118            stack: &mut Vec<BFieldElement>,
119            memory: &mut HashMap<BFieldElement, BFieldElement>,
120        ) {
121            let len = pop_encodable(stack);
122            let write_dest = stack.pop().unwrap();
123            let read_source = stack.pop().unwrap();
124            assert!(len < DEFAULT_MAX_DYN_FIELD_SIZE);
125
126            for i in 0..len {
127                let offset = bfe!(i);
128                let maybe_element = memory.get(&(read_source + offset));
129                let element = maybe_element.copied().unwrap_or_default();
130                memory.insert(write_dest + offset, element);
131            }
132        }
133
134        fn pseudorandom_initial_state(
135            &self,
136            seed: [u8; 32],
137            bench_case: Option<BenchmarkCase>,
138        ) -> FunctionInitialState {
139            let mut rng = StdRng::from_seed(seed);
140            let len = match bench_case {
141                Some(BenchmarkCase::CommonCase) => 17,
142                Some(BenchmarkCase::WorstCase) => 1000,
143                None => rng.random_range(11..=200),
144            };
145            let read_source: BFieldElement = rng.random();
146            let write_dest: BFieldElement = rng.random();
147
148            let mut stack = self.init_stack_for_isolated_run();
149            stack.extend(bfe_vec![read_source, write_dest, len]);
150
151            let memory = (0..len)
152                .map(|i| (read_source + bfe!(i), rng.random()))
153                .collect();
154
155            FunctionInitialState { stack, memory }
156        }
157    }
158
159    #[test]
160    fn rust_shadow() {
161        ShadowedFunction::new(MemCpy).test();
162    }
163
164    #[proptest]
165    fn exceeding_max_size_crashes_vm(#[strategy(DEFAULT_MAX_DYN_FIELD_SIZE..)] len: u32) {
166        // actually filling memory with `len` random elements is a waste of time
167        let mut stack = MemCpy.init_stack_for_isolated_run();
168        stack.extend(bfe_vec![0, 0, len]);
169        let initial_state = InitVmState::with_stack(stack);
170
171        test_assertion_failure(
172            &ShadowedFunction::new(MemCpy),
173            initial_state,
174            &[MemCpy::EXCEEDS_MAX_COPY_SIZE_ERROR_ID],
175        );
176    }
177}
178
179#[cfg(test)]
180mod benches {
181    use super::*;
182    use crate::test_prelude::*;
183
184    #[test]
185    fn benchmark() {
186        ShadowedFunction::new(MemCpy).bench();
187    }
188}
tasm_lib/memory/memcpy.rs

tasm_lib/memory/
memcpy.rs
