zkaluvm/gfa/
exec.rs

1// AluVM ISA extension for Galois fields
2//
3// SPDX-License-Identifier: Apache-2.0
4//
5// Designed in 2024-2025 by Dr Maxim Orlovsky <orlovsky@ubideco.org>
6// Written in 2024-2025 by Dr Maxim Orlovsky <orlovsky@ubideco.org>
7//
8// Copyright (C) 2024-2025 Laboratories for Ubiquitous Deterministic Computing (UBIDECO),
9//                         Institute for Distributed and Cognitive Systems (InDCS), Switzerland.
10// Copyright (C) 2024-2025 Dr Maxim Orlovsky.
11// All rights under the above copyrights are reserved.
12//
13// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
14// in compliance with the License. You may obtain a copy of the License at
15//
16//        http://www.apache.org/licenses/LICENSE-2.0
17//
18// Unless required by applicable law or agreed to in writing, software distributed under the License
19// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
20// or implied. See the License for the specific language governing permissions and limitations under
21// the License.
22
23use alloc::collections::BTreeSet;
24
25use aluvm::isa::{ExecStep, GotoTarget, Instruction};
26use aluvm::regs::Status;
27use aluvm::{Core, CoreExt, Site, SiteId, Supercore};
28use amplify::num::u256;
29
30use super::{FieldInstr, Instr, ISA_GFA256};
31use crate::{fe256, GfaCore, RegE};
32
33impl<Id: SiteId> Instruction<Id> for FieldInstr {
34    const ISA_EXT: &'static [&'static str] = &[ISA_GFA256];
35    type Core = GfaCore;
36    type Context<'ctx> = ();
37
38    fn is_goto_target(&self) -> bool { false }
39
40    fn local_goto_pos(&mut self) -> GotoTarget { GotoTarget::None }
41
42    fn remote_goto_pos(&mut self) -> Option<&mut Site<Id>> { None }
43
44    fn src_regs(&self) -> BTreeSet<RegE> {
45        match *self {
46            FieldInstr::Clr { dst: _ }
47            | FieldInstr::PutD { dst: _, data: _ }
48            | FieldInstr::PutZ { dst: _ }
49            | FieldInstr::PutV { dst: _, val: _ } => none!(),
50
51            FieldInstr::Eq { src1, src2 } => bset![src1, src2],
52
53            FieldInstr::Test { src }
54            | FieldInstr::Fits { src, bits: _ }
55            | FieldInstr::Mov { dst: _, src }
56            | FieldInstr::Neg { dst: _, src } => bset![src],
57
58            FieldInstr::Add { dst_src, src } | FieldInstr::Mul { dst_src, src } => bset![src, dst_src],
59        }
60    }
61
62    fn dst_regs(&self) -> BTreeSet<RegE> {
63        match *self {
64            FieldInstr::Clr { dst }
65            | FieldInstr::PutD { dst, data: _ }
66            | FieldInstr::PutZ { dst }
67            | FieldInstr::PutV { dst, val: _ }
68            | FieldInstr::Mov { dst, src: _ } => bset![dst],
69
70            FieldInstr::Eq { src1: _, src2: _ }
71            | FieldInstr::Test { src: _ }
72            | FieldInstr::Fits { src: _, bits: _ } => none!(),
73
74            FieldInstr::Neg { dst, src: _ }
75            | FieldInstr::Add { dst_src: dst, src: _ }
76            | FieldInstr::Mul { dst_src: dst, src: _ } => bset![dst],
77        }
78    }
79
80    fn op_data_bytes(&self) -> u16 {
81        match self {
82            FieldInstr::PutV { dst: _, val: _ } | FieldInstr::Fits { src: _, bits: _ } => 1,
83
84            FieldInstr::Test { src: _ }
85            | FieldInstr::Clr { dst: _ }
86            | FieldInstr::PutD { dst: _, data: _ }
87            | FieldInstr::PutZ { dst: _ }
88            | FieldInstr::Mov { dst: _, src: _ }
89            | FieldInstr::Eq { src1: _, src2: _ }
90            | FieldInstr::Neg { dst: _, src: _ }
91            | FieldInstr::Add { dst_src: _, src: _ }
92            | FieldInstr::Mul { dst_src: _, src: _ } => 0,
93        }
94    }
95
96    fn ext_data_bytes(&self) -> u16 {
97        match self {
98            FieldInstr::PutD { dst: _, data: _ } => 32,
99
100            FieldInstr::Test { src: _ }
101            | FieldInstr::Clr { dst: _ }
102            | FieldInstr::PutZ { dst: _ }
103            | FieldInstr::PutV { dst: _, val: _ }
104            | FieldInstr::Fits { src: _, bits: _ }
105            | FieldInstr::Mov { dst: _, src: _ }
106            | FieldInstr::Eq { src1: _, src2: _ }
107            | FieldInstr::Neg { dst: _, src: _ }
108            | FieldInstr::Add { dst_src: _, src: _ }
109            | FieldInstr::Mul { dst_src: _, src: _ } => 0,
110        }
111    }
112
113    fn complexity(&self) -> u64 {
114        let base = Instruction::<Id>::base_complexity(self);
115        match self {
116            FieldInstr::Test { src: _ }
117            | FieldInstr::Clr { dst: _ }
118            | FieldInstr::PutZ { dst: _ }
119            | FieldInstr::PutV { dst: _, val: _ }
120            | FieldInstr::PutD { dst: _, data: _ }
121            | FieldInstr::Mov { dst: _, src: _ }
122            | FieldInstr::Eq { src1: _, src2: _ } => base,
123
124            FieldInstr::Fits { src: _, bits: _ }
125            | FieldInstr::Neg { dst: _, src: _ }
126            | FieldInstr::Add { dst_src: _, src: _ }
127            | FieldInstr::Mul { dst_src: _, src: _ } => {
128                // Double the default complexity since each instruction performs two operations.
129                base * 2
130            }
131        }
132    }
133
134    fn exec(&self, _: Site<Id>, core: &mut Core<Id, GfaCore>, _: &Self::Context<'_>) -> ExecStep<Site<Id>> {
135        let res = match *self {
136            FieldInstr::Test { src } => {
137                let res = core.cx.test(src);
138                core.set_co(res);
139                Status::Ok
140            }
141            FieldInstr::Clr { dst } => {
142                core.cx.clr(dst);
143                Status::Ok
144            }
145            FieldInstr::PutD { dst, data } => {
146                core.cx.set(dst, data);
147                Status::Ok
148            }
149            FieldInstr::PutZ { dst } => {
150                core.cx.set(dst, fe256::ZERO);
151                Status::Ok
152            }
153            FieldInstr::PutV { dst, val } => {
154                let val = val
155                    .to_fe256()
156                    .unwrap_or_else(|| (core.cx.fq() - u256::ONE).into());
157                core.cx.set(dst, val);
158                Status::Ok
159            }
160            FieldInstr::Mov { dst, src } => {
161                core.cx.mov(dst, src);
162                Status::Ok
163            }
164            FieldInstr::Eq { src1, src2 } => {
165                let res = core.cx.eqv(src1, src2);
166                core.set_co(res);
167                Status::Ok
168            }
169
170            FieldInstr::Fits { src, bits } => match core.cx.fits(src, bits) {
171                None => Status::Fail,
172                Some(true) => {
173                    core.set_co(Status::Ok);
174                    Status::Ok
175                }
176                Some(false) => {
177                    core.set_co(Status::Fail);
178                    Status::Ok
179                }
180            },
181            FieldInstr::Neg { dst, src } => core.cx.neg_mod(dst, src),
182            FieldInstr::Add { dst_src, src } => core.cx.add_mod(dst_src, src),
183            FieldInstr::Mul { dst_src, src } => core.cx.mul_mod(dst_src, src),
184        };
185        if res == Status::Ok {
186            ExecStep::Next
187        } else {
188            ExecStep::Fail
189        }
190    }
191}
192
193impl<Id: SiteId> Instruction<Id> for Instr<Id> {
194    const ISA_EXT: &'static [&'static str] = &[ISA_GFA256];
195    type Core = GfaCore;
196    type Context<'ctx> = ();
197
198    fn is_goto_target(&self) -> bool {
199        match self {
200            Instr::Ctrl(ctrl) => ctrl.is_goto_target(),
201            Instr::Gfa(instr) => Instruction::<Id>::is_goto_target(instr),
202            Instr::Reserved(reserved) => Instruction::<Id>::is_goto_target(reserved),
203        }
204    }
205
206    fn local_goto_pos(&mut self) -> GotoTarget {
207        match self {
208            Instr::Ctrl(ctrl) => ctrl.local_goto_pos(),
209            Instr::Gfa(instr) => Instruction::<Id>::local_goto_pos(instr),
210            Instr::Reserved(reserved) => Instruction::<Id>::local_goto_pos(reserved),
211        }
212    }
213
214    fn remote_goto_pos(&mut self) -> Option<&mut Site<Id>> {
215        match self {
216            Instr::Ctrl(ctrl) => ctrl.remote_goto_pos(),
217            Instr::Gfa(instr) => Instruction::<Id>::remote_goto_pos(instr),
218            Instr::Reserved(reserved) => Instruction::<Id>::remote_goto_pos(reserved),
219        }
220    }
221
222    fn src_regs(&self) -> BTreeSet<<Self::Core as CoreExt>::Reg> {
223        match self {
224            Instr::Ctrl(_) => none!(),
225            Instr::Gfa(instr) => Instruction::<Id>::src_regs(instr),
226            Instr::Reserved(_) => none!(),
227        }
228    }
229
230    fn dst_regs(&self) -> BTreeSet<<Self::Core as CoreExt>::Reg> {
231        match self {
232            Instr::Ctrl(_) => none!(),
233            Instr::Gfa(instr) => Instruction::<Id>::dst_regs(instr),
234            Instr::Reserved(_) => none!(),
235        }
236    }
237
238    fn op_data_bytes(&self) -> u16 {
239        match self {
240            Instr::Ctrl(instr) => instr.op_data_bytes(),
241            Instr::Gfa(instr) => Instruction::<Id>::op_data_bytes(instr),
242            Instr::Reserved(_) => none!(),
243        }
244    }
245
246    fn ext_data_bytes(&self) -> u16 {
247        match self {
248            Instr::Ctrl(instr) => instr.ext_data_bytes(),
249            Instr::Gfa(instr) => Instruction::<Id>::ext_data_bytes(instr),
250            Instr::Reserved(_) => none!(),
251        }
252    }
253
254    fn complexity(&self) -> u64 {
255        match self {
256            Instr::Ctrl(instr) => instr.complexity(),
257            Instr::Gfa(instr) => Instruction::<Id>::complexity(instr),
258            Instr::Reserved(instr) => Instruction::<Id>::complexity(instr),
259        }
260    }
261
262    fn exec(&self, site: Site<Id>, core: &mut Core<Id, Self::Core>, context: &Self::Context<'_>) -> ExecStep<Site<Id>> {
263        match self {
264            Instr::Ctrl(instr) => {
265                let mut subcore = core.subcore();
266                let step = instr.exec(site, &mut subcore, context);
267                core.merge_subcore(subcore);
268                step
269            }
270            Instr::Gfa(instr) => instr.exec(site, core, context),
271            Instr::Reserved(instr) => {
272                let mut subcore = core.subcore();
273                let step = instr.exec(site, &mut subcore, context);
274                core.merge_subcore(subcore);
275                step
276            }
277        }
278    }
279}
280
281#[cfg(test)]
282mod test {
283    #![cfg_attr(coverage_nightly, coverage(off))]
284
285    use aluvm::LibId;
286
287    use super::*;
288    use crate::gfa::{Bits, ConstVal};
289
290    #[test]
291    fn test() {
292        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Test { src: RegE::E1 });
293        assert_eq!(instr.is_goto_target(), false);
294        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
295        assert_eq!(instr.remote_goto_pos(), None);
296        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
297        assert_eq!(instr.src_regs(), bset![RegE::E1]);
298        assert_eq!(instr.dst_regs(), none!());
299        assert_eq!(instr.src_reg_bytes(), 32);
300        assert_eq!(instr.dst_reg_bytes(), 0);
301        assert_eq!(instr.op_data_bytes(), 0);
302        assert_eq!(instr.ext_data_bytes(), 0);
303        assert_eq!(instr.base_complexity(), 256000);
304        assert_eq!(instr.complexity(), instr.base_complexity());
305    }
306
307    #[test]
308    fn clr() {
309        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Clr { dst: RegE::E1 });
310        assert_eq!(instr.is_goto_target(), false);
311        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
312        assert_eq!(instr.remote_goto_pos(), None);
313        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
314        assert_eq!(instr.src_regs(), none!());
315        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
316        assert_eq!(instr.src_reg_bytes(), 0);
317        assert_eq!(instr.dst_reg_bytes(), 32);
318        assert_eq!(instr.op_data_bytes(), 0);
319        assert_eq!(instr.ext_data_bytes(), 0);
320        assert_eq!(instr.base_complexity(), 256000);
321        assert_eq!(instr.complexity(), instr.base_complexity());
322    }
323
324    #[test]
325    fn putd() {
326        let mut instr = Instr::<LibId>::Gfa(FieldInstr::PutD {
327            dst: RegE::E1,
328            data: fe256::ZERO,
329        });
330        assert_eq!(instr.is_goto_target(), false);
331        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
332        assert_eq!(instr.remote_goto_pos(), None);
333        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
334        assert_eq!(instr.src_regs(), none!());
335        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
336        assert_eq!(instr.src_reg_bytes(), 0);
337        assert_eq!(instr.dst_reg_bytes(), 32);
338        assert_eq!(instr.op_data_bytes(), 0);
339        assert_eq!(instr.ext_data_bytes(), 32);
340        assert_eq!(instr.base_complexity(), 768000);
341        assert_eq!(instr.complexity(), instr.base_complexity());
342    }
343
344    #[test]
345    fn putz() {
346        let mut instr = Instr::<LibId>::Gfa(FieldInstr::PutZ { dst: RegE::E1 });
347        assert_eq!(instr.is_goto_target(), false);
348        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
349        assert_eq!(instr.remote_goto_pos(), None);
350        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
351        assert_eq!(instr.src_regs(), none!());
352        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
353        assert_eq!(instr.src_reg_bytes(), 0);
354        assert_eq!(instr.dst_reg_bytes(), 32);
355        assert_eq!(instr.op_data_bytes(), 0);
356        assert_eq!(instr.ext_data_bytes(), 0);
357        assert_eq!(instr.base_complexity(), 256000);
358        assert_eq!(instr.complexity(), instr.base_complexity());
359    }
360
361    #[test]
362    fn putv() {
363        let mut instr = Instr::<LibId>::Gfa(FieldInstr::PutV {
364            dst: RegE::E1,
365            val: ConstVal::ValFeMAX,
366        });
367        assert_eq!(instr.is_goto_target(), false);
368        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
369        assert_eq!(instr.remote_goto_pos(), None);
370        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
371        assert_eq!(instr.src_regs(), none!());
372        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
373        assert_eq!(instr.src_reg_bytes(), 0);
374        assert_eq!(instr.dst_reg_bytes(), 32);
375        assert_eq!(instr.op_data_bytes(), 1);
376        assert_eq!(instr.ext_data_bytes(), 0);
377        assert_eq!(instr.base_complexity(), 264000);
378        assert_eq!(instr.complexity(), instr.base_complexity());
379    }
380
381    #[test]
382    fn fits() {
383        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Fits {
384            src: RegE::E1,
385            bits: Bits::Bits8,
386        });
387        assert_eq!(instr.is_goto_target(), false);
388        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
389        assert_eq!(instr.remote_goto_pos(), None);
390        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
391        assert_eq!(instr.src_regs(), bset![RegE::E1]);
392        assert_eq!(instr.dst_regs(), none!());
393        assert_eq!(instr.src_reg_bytes(), 32);
394        assert_eq!(instr.dst_reg_bytes(), 0);
395        assert_eq!(instr.op_data_bytes(), 1);
396        assert_eq!(instr.ext_data_bytes(), 0);
397        assert_eq!(instr.base_complexity(), 264000);
398        assert_eq!(instr.complexity(), instr.base_complexity() * 2);
399    }
400
401    #[test]
402    fn mov() {
403        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Mov {
404            dst: RegE::E1,
405            src: RegE::EA,
406        });
407        assert_eq!(instr.is_goto_target(), false);
408        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
409        assert_eq!(instr.remote_goto_pos(), None);
410        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
411        assert_eq!(instr.src_regs(), bset![RegE::EA]);
412        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
413        assert_eq!(instr.src_reg_bytes(), 32);
414        assert_eq!(instr.dst_reg_bytes(), 32);
415        assert_eq!(instr.op_data_bytes(), 0);
416        assert_eq!(instr.ext_data_bytes(), 0);
417        assert_eq!(instr.base_complexity(), 512000);
418        assert_eq!(instr.complexity(), instr.base_complexity());
419    }
420
421    #[test]
422    fn eq() {
423        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Eq {
424            src1: RegE::E1,
425            src2: RegE::EA,
426        });
427        assert_eq!(instr.is_goto_target(), false);
428        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
429        assert_eq!(instr.remote_goto_pos(), None);
430        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
431        assert_eq!(instr.src_regs(), bset![RegE::E1, RegE::EA]);
432        assert_eq!(instr.dst_regs(), none!());
433        assert_eq!(instr.src_reg_bytes(), 64);
434        assert_eq!(instr.dst_reg_bytes(), 0);
435        assert_eq!(instr.op_data_bytes(), 0);
436        assert_eq!(instr.ext_data_bytes(), 0);
437        assert_eq!(instr.base_complexity(), 512000);
438        assert_eq!(instr.complexity(), instr.base_complexity());
439    }
440
441    #[test]
442    fn neg() {
443        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Neg {
444            dst: RegE::E1,
445            src: RegE::EA,
446        });
447        assert_eq!(instr.is_goto_target(), false);
448        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
449        assert_eq!(instr.remote_goto_pos(), None);
450        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
451        assert_eq!(instr.src_regs(), bset![RegE::EA]);
452        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
453        assert_eq!(instr.src_reg_bytes(), 32);
454        assert_eq!(instr.dst_reg_bytes(), 32);
455        assert_eq!(instr.op_data_bytes(), 0);
456        assert_eq!(instr.ext_data_bytes(), 0);
457        assert_eq!(instr.base_complexity(), 512000);
458        assert_eq!(instr.complexity(), instr.base_complexity() * 2);
459    }
460
461    #[test]
462    fn add() {
463        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Add {
464            dst_src: RegE::E1,
465            src: RegE::EA,
466        });
467        assert_eq!(instr.is_goto_target(), false);
468        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
469        assert_eq!(instr.remote_goto_pos(), None);
470        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
471        assert_eq!(instr.src_regs(), bset![RegE::EA, RegE::E1]);
472        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
473        assert_eq!(instr.src_reg_bytes(), 64);
474        assert_eq!(instr.dst_reg_bytes(), 32);
475        assert_eq!(instr.op_data_bytes(), 0);
476        assert_eq!(instr.ext_data_bytes(), 0);
477        assert_eq!(instr.base_complexity(), 768000);
478        assert_eq!(instr.complexity(), instr.base_complexity() * 2);
479    }
480
481    #[test]
482    fn mul() {
483        let mut instr = Instr::<LibId>::Gfa(FieldInstr::Mul {
484            dst_src: RegE::E1,
485            src: RegE::EA,
486        });
487        assert_eq!(instr.is_goto_target(), false);
488        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
489        assert_eq!(instr.remote_goto_pos(), None);
490        assert_eq!(instr.regs(), instr.src_regs().union(&instr.dst_regs()).copied().collect());
491        assert_eq!(instr.src_regs(), bset![RegE::EA, RegE::E1]);
492        assert_eq!(instr.dst_regs(), bset![RegE::E1]);
493        assert_eq!(instr.src_reg_bytes(), 64);
494        assert_eq!(instr.dst_reg_bytes(), 32);
495        assert_eq!(instr.op_data_bytes(), 0);
496        assert_eq!(instr.ext_data_bytes(), 0);
497        assert_eq!(instr.base_complexity(), 768000);
498        assert_eq!(instr.complexity(), instr.base_complexity() * 2);
499    }
500
501    #[test]
502    fn reserved() {
503        let mut instr = Instr::<LibId>::Reserved(default!());
504        assert_eq!(instr.is_goto_target(), false);
505        assert_eq!(instr.local_goto_pos(), GotoTarget::None);
506        assert_eq!(instr.remote_goto_pos(), None);
507        assert_eq!(instr.regs(), none!());
508        assert_eq!(instr.src_regs(), none!());
509        assert_eq!(instr.dst_regs(), none!());
510        assert_eq!(instr.src_reg_bytes(), 0);
511        assert_eq!(instr.dst_reg_bytes(), 0);
512        assert_eq!(instr.op_data_bytes(), 0);
513        assert_eq!(instr.ext_data_bytes(), 0);
514        assert_eq!(instr.base_complexity(), 0);
515        assert_eq!(instr.complexity(), u64::MAX);
516    }
517}
zkaluvm/gfa/exec.rs

zkaluvm/gfa/
exec.rs
