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 parameters(&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 return_values(&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        ) -> Result<(), RustShadowError> {
121            let len = pop_encodable(stack)?;
122            let write_dest = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
123            let read_source = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
124            if len >= DEFAULT_MAX_DYN_FIELD_SIZE {
125                return Err(RustShadowError::Other);
126            }
127
128            for i in 0..len {
129                let offset = bfe!(i);
130                let maybe_element = memory.get(&(read_source + offset));
131                let element = maybe_element.copied().unwrap_or_default();
132                memory.insert(write_dest + offset, element);
133            }
134            Ok(())
135        }
136
137        fn pseudorandom_initial_state(
138            &self,
139            seed: [u8; 32],
140            bench_case: Option<BenchmarkCase>,
141        ) -> FunctionInitialState {
142            let mut rng = StdRng::from_seed(seed);
143            let len = match bench_case {
144                Some(BenchmarkCase::CommonCase) => 17,
145                Some(BenchmarkCase::WorstCase) => 1000,
146                None => rng.random_range(11..=200),
147            };
148            let read_source: BFieldElement = rng.random();
149            let write_dest: BFieldElement = rng.random();
150
151            let mut stack = self.init_stack_for_isolated_run();
152            stack.extend(bfe_vec![read_source, write_dest, len]);
153
154            let memory = (0..len)
155                .map(|i| (read_source + bfe!(i), rng.random()))
156                .collect();
157
158            FunctionInitialState { stack, memory }
159        }
160    }
161
162    #[macro_rules_attr::apply(test)]
163    fn rust_shadow() {
164        ShadowedFunction::new(MemCpy).test();
165    }
166
167    #[macro_rules_attr::apply(proptest)]
168    fn exceeding_max_size_crashes_vm(#[strategy(DEFAULT_MAX_DYN_FIELD_SIZE..)] len: u32) {
169        // actually filling memory with `len` random elements is a waste of time
170        let mut stack = MemCpy.init_stack_for_isolated_run();
171        stack.extend(bfe_vec![0, 0, len]);
172        let initial_state = InitVmState::with_stack(stack);
173
174        test_assertion_failure(
175            &ShadowedFunction::new(MemCpy),
176            initial_state,
177            &[MemCpy::EXCEEDS_MAX_COPY_SIZE_ERROR_ID],
178        );
179    }
180}
181
182#[cfg(test)]
183mod benches {
184    use super::*;
185    use crate::test_prelude::*;
186
187    #[macro_rules_attr::apply(test)]
188    fn benchmark() {
189        ShadowedFunction::new(MemCpy).bench();
190    }
191}
tasm_lib/memory/memcpy.rs

tasm_lib/memory/
memcpy.rs
