logicaffeine_compile/semantics/
native_kernels.rs

1//! The standard library's native KERNELS — the `## To native` functions of `crypto.lg` (ML-KEM's NTT,
2//! sampling, and serialization; the high-level ML-KEM / ML-DSA primitives) — as ONE table every tier
3//! reads.
4//!
5//! A `## To native` declaration has an EMPTY body: the engine supplies the implementation. The compiled
6//! tier links `logicaffeine_system`'s kernel ([`NativeKernel::rust_path`]); the tree-walker calls
7//! [`NativeKernel::call`]; the VM lowers a kernel call to `CallBuiltin(NativeKernel)` whose first
8//! argument is the kernel's [`NativeKernel::code`], and the builtin runs the same [`NativeKernel::call`].
9//! So every tier runs the very same Rust function, and a kernel added here reaches all of them at once.
10//!
11//! [`NativeKernel::code`] is the kernel's POSITION in [`NativeKernel::ALL`] and travels in bytecode (and
12//! the binary wire format), so new kernels are APPENDED — `goldens/native_kernel_codes.txt` locks it.
13
14use crate::interpreter::{ListRepr, RuntimeValue};
15use logicaffeine_base::{Word16, WordVal};
16use logicaffeine_data::LogosSeq;
17use logicaffeine_system::{mldsa, mlkem, ntt};
18use std::cell::RefCell;
19use std::rc::Rc;
20
21/// One native kernel of the standard library.
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
23pub enum NativeKernel {
24    MlkemNtt,
25    MlkemBaseMulW16,
26    ToMontW16,
27    Cbd2W16,
28    CompressW16,
29    DecompressW16,
30    ByteEncodeW16,
31    ByteDecodeW16,
32    SampleAW16,
33    SampleMatrixW16,
34    MlkemNoiseBatch,
35    AddModQW16,
36    SubModQW16,
37    ZerosW16,
38    MlkemInvNtt,
39    MlkemBaseMul,
40    Cbd2,
41    Cbd3,
42    Compress,
43    Decompress,
44    ByteEncode,
45    ByteDecode,
46    SampleNtt,
47    SampleA,
48    ToMont,
49    MlkemKeypair,
50    MlkemEncapsKem,
51    MlkemDecapsKem,
52    MldsaKeypair,
53    MldsaSign,
54    MldsaVerify,
55}
56
57impl NativeKernel {
58    /// Every kernel, in code order. Append only.
59    pub const ALL: &'static [NativeKernel] = &[
60        NativeKernel::MlkemNtt,
61        NativeKernel::MlkemBaseMulW16,
62        NativeKernel::ToMontW16,
63        NativeKernel::Cbd2W16,
64        NativeKernel::CompressW16,
65        NativeKernel::DecompressW16,
66        NativeKernel::ByteEncodeW16,
67        NativeKernel::ByteDecodeW16,
68        NativeKernel::SampleAW16,
69        NativeKernel::SampleMatrixW16,
70        NativeKernel::MlkemNoiseBatch,
71        NativeKernel::AddModQW16,
72        NativeKernel::SubModQW16,
73        NativeKernel::ZerosW16,
74        NativeKernel::MlkemInvNtt,
75        NativeKernel::MlkemBaseMul,
76        NativeKernel::Cbd2,
77        NativeKernel::Cbd3,
78        NativeKernel::Compress,
79        NativeKernel::Decompress,
80        NativeKernel::ByteEncode,
81        NativeKernel::ByteDecode,
82        NativeKernel::SampleNtt,
83        NativeKernel::SampleA,
84        NativeKernel::ToMont,
85        NativeKernel::MlkemKeypair,
86        NativeKernel::MlkemEncapsKem,
87        NativeKernel::MlkemDecapsKem,
88        NativeKernel::MldsaKeypair,
89        NativeKernel::MldsaSign,
90        NativeKernel::MldsaVerify,
91    ];
92
93    /// The LOGOS name the standard library declares it under.
94    pub const fn name(self) -> &'static str {
95        match self {
96            NativeKernel::MlkemNtt => "mlkemNtt",
97            NativeKernel::MlkemBaseMulW16 => "mlkemBaseMulW16",
98            NativeKernel::ToMontW16 => "toMontW16",
99            NativeKernel::Cbd2W16 => "cbd2W16",
100            NativeKernel::CompressW16 => "compressW16",
101            NativeKernel::DecompressW16 => "decompressW16",
102            NativeKernel::ByteEncodeW16 => "byteEncodeW16",
103            NativeKernel::ByteDecodeW16 => "byteDecodeW16",
104            NativeKernel::SampleAW16 => "sampleAW16",
105            NativeKernel::SampleMatrixW16 => "sampleMatrixW16",
106            NativeKernel::MlkemNoiseBatch => "mlkemNoiseBatch",
107            NativeKernel::AddModQW16 => "addModQW16",
108            NativeKernel::SubModQW16 => "subModQW16",
109            NativeKernel::ZerosW16 => "zerosW16",
110            NativeKernel::MlkemInvNtt => "mlkemInvNtt",
111            NativeKernel::MlkemBaseMul => "mlkemBaseMul",
112            NativeKernel::Cbd2 => "cbd2",
113            NativeKernel::Cbd3 => "cbd3",
114            NativeKernel::Compress => "compress",
115            NativeKernel::Decompress => "decompress",
116            NativeKernel::ByteEncode => "byteEncode",
117            NativeKernel::ByteDecode => "byteDecode",
118            NativeKernel::SampleNtt => "sampleNtt",
119            NativeKernel::SampleA => "sampleA",
120            NativeKernel::ToMont => "toMont",
121            NativeKernel::MlkemKeypair => "mlkemKeypair",
122            NativeKernel::MlkemEncapsKem => "mlkemEncapsKem",
123            NativeKernel::MlkemDecapsKem => "mlkemDecapsKem",
124            NativeKernel::MldsaKeypair => "mldsaKeypair",
125            NativeKernel::MldsaSign => "mldsaSign",
126            NativeKernel::MldsaVerify => "mldsaVerify",
127        }
128    }
129
130    /// How many arguments the declaration takes.
131    pub const fn arity(self) -> usize {
132        match self {
133            NativeKernel::MlkemNtt
134            | NativeKernel::ToMontW16
135            | NativeKernel::Cbd2W16
136            | NativeKernel::SampleMatrixW16
137            | NativeKernel::ZerosW16
138            | NativeKernel::MlkemInvNtt
139            | NativeKernel::Cbd2
140            | NativeKernel::Cbd3
141            | NativeKernel::SampleNtt
142            | NativeKernel::ToMont
143            | NativeKernel::MldsaKeypair => 1,
144            NativeKernel::MlkemBaseMulW16
145            | NativeKernel::CompressW16
146            | NativeKernel::DecompressW16
147            | NativeKernel::ByteEncodeW16
148            | NativeKernel::ByteDecodeW16
149            | NativeKernel::AddModQW16
150            | NativeKernel::SubModQW16
151            | NativeKernel::MlkemBaseMul
152            | NativeKernel::Compress
153            | NativeKernel::Decompress
154            | NativeKernel::ByteEncode
155            | NativeKernel::ByteDecode
156            | NativeKernel::MlkemKeypair
157            | NativeKernel::MlkemEncapsKem
158            | NativeKernel::MlkemDecapsKem => 2,
159            NativeKernel::SampleAW16
160            | NativeKernel::MlkemNoiseBatch
161            | NativeKernel::SampleA
162            | NativeKernel::MldsaSign => 3,
163            NativeKernel::MldsaVerify => 4,
164        }
165    }
166
167    /// The `logicaffeine_system` `(module, function)` the compiled tier calls.
168    pub const fn rust_path(self) -> (&'static str, &'static str) {
169        match self {
170            NativeKernel::MlkemNtt => ("ntt", "mlkem_ntt"),
171            NativeKernel::MlkemBaseMulW16 => ("ntt", "mlkem_base_mul_w16_seq"),
172            NativeKernel::ToMontW16 => ("ntt", "mlkem_to_mont_w16_seq"),
173            NativeKernel::Cbd2W16 => ("ntt", "mlkem_cbd2_w16_from_int"),
174            NativeKernel::CompressW16 => ("ntt", "mlkem_compress_w16_seq"),
175            NativeKernel::DecompressW16 => ("ntt", "mlkem_decompress_w16_seq"),
176            NativeKernel::ByteEncodeW16 => ("ntt", "mlkem_byte_encode_w16_to_int"),
177            NativeKernel::ByteDecodeW16 => ("ntt", "mlkem_byte_decode_w16_from_int"),
178            NativeKernel::SampleAW16 => ("ntt", "mlkem_sample_a_w16_from_int"),
179            NativeKernel::SampleMatrixW16 => ("ntt", "mlkem_sample_matrix_w16_from_int"),
180            NativeKernel::MlkemNoiseBatch => ("mlkem", "mlkem_noise_batch_from_int"),
181            NativeKernel::AddModQW16 => ("ntt", "mlkem_add_mod_q_w16"),
182            NativeKernel::SubModQW16 => ("ntt", "mlkem_sub_mod_q_w16"),
183            NativeKernel::ZerosW16 => ("ntt", "mlkem_zeros_w16"),
184            NativeKernel::MlkemInvNtt => ("ntt", "mlkem_inv_ntt"),
185            NativeKernel::MlkemBaseMul => ("ntt", "mlkem_base_mul"),
186            NativeKernel::Cbd2 => ("ntt", "mlkem_cbd2"),
187            NativeKernel::Cbd3 => ("ntt", "mlkem_cbd3"),
188            NativeKernel::Compress => ("ntt", "mlkem_compress"),
189            NativeKernel::Decompress => ("ntt", "mlkem_decompress"),
190            NativeKernel::ByteEncode => ("ntt", "mlkem_byte_encode"),
191            NativeKernel::ByteDecode => ("ntt", "mlkem_byte_decode"),
192            NativeKernel::SampleNtt => ("ntt", "mlkem_sample_ntt"),
193            NativeKernel::SampleA => ("ntt", "mlkem_sample_a"),
194            NativeKernel::ToMont => ("ntt", "mlkem_to_mont"),
195            NativeKernel::MlkemKeypair => ("mlkem", "mlkem_keypair_seq"),
196            NativeKernel::MlkemEncapsKem => ("mlkem", "mlkem_encaps_seq"),
197            NativeKernel::MlkemDecapsKem => ("mlkem", "mlkem_decaps_seq"),
198            NativeKernel::MldsaKeypair => ("mldsa", "mldsa_keypair_seq"),
199            NativeKernel::MldsaSign => ("mldsa", "mldsa_sign_seq"),
200            NativeKernel::MldsaVerify => ("mldsa", "mldsa_verify_seq"),
201        }
202    }
203
204    /// The kernel's stable code — its position in [`Self::ALL`].
205    pub fn code(self) -> i64 {
206        Self::ALL
207            .iter()
208            .position(|&k| k == self)
209            .expect("every kernel is in ALL") as i64
210    }
211
212    /// The kernel with this code.
213    pub fn from_code(code: i64) -> Option<NativeKernel> {
214        usize::try_from(code)
215            .ok()
216            .and_then(|i| Self::ALL.get(i).copied())
217    }
218
219    /// The kernel declared under `name`, if any.
220    pub fn from_name(name: &str) -> Option<NativeKernel> {
221        Self::ALL.iter().copied().find(|k| k.name() == name)
222    }
223
224    /// Why a backend that cannot link the Rust kernels refuses a program that calls this one.
225    pub fn refusal(self, backend: &str) -> String {
226        format!(
227            "`{}` is a standard-library native kernel (crypto.lg) implemented in Rust — the {backend} \
228             backend cannot link it; run the program on the interpreter or the VM, or build it with the \
229             Rust tier (`largo build`)",
230            self.name()
231        )
232    }
233
234    /// Run the kernel on already-evaluated arguments.
235    pub fn call(self, args: &[RuntimeValue]) -> Result<RuntimeValue, String> {
236        if args.len() != self.arity() {
237            return Err(format!(
238                "{}() takes {} argument{}, got {}",
239                self.name(),
240                self.arity(),
241                if self.arity() == 1 { "" } else { "s" },
242                args.len()
243            ));
244        }
245        let name = self.name();
246        let int = |i: usize| int_arg(name, &args[i]);
247        let ints = |i: usize| int_seq(name, &args[i]);
248        let w16 = |i: usize| word16_seq(name, &args[i]);
249        let ran = match self {
250            NativeKernel::MlkemNtt => ntt::mlkem_ntt(&ints(0)?).map(from_ints),
251            NativeKernel::MlkemBaseMulW16 => {
252                ntt::mlkem_base_mul_w16_seq(&w16(0)?, &w16(1)?).map(from_w16)
253            }
254            NativeKernel::ToMontW16 => ntt::mlkem_to_mont_w16_seq(&w16(0)?).map(from_w16),
255            NativeKernel::Cbd2W16 => ntt::mlkem_cbd2_w16_from_int(&ints(0)?).map(from_w16),
256            NativeKernel::CompressW16 => {
257                ntt::mlkem_compress_w16_seq(&w16(0)?, int(1)?).map(from_w16)
258            }
259            NativeKernel::DecompressW16 => {
260                ntt::mlkem_decompress_w16_seq(&w16(0)?, int(1)?).map(from_w16)
261            }
262            NativeKernel::ByteEncodeW16 => {
263                ntt::mlkem_byte_encode_w16_to_int(&w16(0)?, int(1)?).map(from_ints)
264            }
265            NativeKernel::ByteDecodeW16 => {
266                ntt::mlkem_byte_decode_w16_from_int(&ints(0)?, int(1)?).map(from_w16)
267            }
268            NativeKernel::SampleAW16 => {
269                ntt::mlkem_sample_a_w16_from_int(&ints(0)?, int(1)?, int(2)?).map(from_w16)
270            }
271            NativeKernel::SampleMatrixW16 => {
272                ntt::mlkem_sample_matrix_w16_from_int(&ints(0)?).map(from_w16)
273            }
274            NativeKernel::MlkemNoiseBatch => {
275                mlkem::mlkem_noise_batch_from_int(&ints(0)?, int(1)?, int(2)?).map(from_w16)
276            }
277            NativeKernel::AddModQW16 => ntt::mlkem_add_mod_q_w16(&w16(0)?, &w16(1)?).map(from_w16),
278            NativeKernel::SubModQW16 => ntt::mlkem_sub_mod_q_w16(&w16(0)?, &w16(1)?).map(from_w16),
279            NativeKernel::ZerosW16 => ntt::mlkem_zeros_w16(int(0)?).map(from_w16),
280            NativeKernel::MlkemInvNtt => ntt::mlkem_inv_ntt(&ints(0)?).map(from_ints),
281            NativeKernel::MlkemBaseMul => ntt::mlkem_base_mul(&ints(0)?, &ints(1)?).map(from_ints),
282            NativeKernel::Cbd2 => ntt::mlkem_cbd2(&ints(0)?).map(from_ints),
283            NativeKernel::Cbd3 => ntt::mlkem_cbd3(&ints(0)?).map(from_ints),
284            NativeKernel::Compress => ntt::mlkem_compress(&ints(0)?, int(1)?).map(from_ints),
285            NativeKernel::Decompress => ntt::mlkem_decompress(&ints(0)?, int(1)?).map(from_ints),
286            NativeKernel::ByteEncode => ntt::mlkem_byte_encode(&ints(0)?, int(1)?).map(from_ints),
287            NativeKernel::ByteDecode => ntt::mlkem_byte_decode(&ints(0)?, int(1)?).map(from_ints),
288            NativeKernel::SampleNtt => ntt::mlkem_sample_ntt(&ints(0)?).map(from_ints),
289            NativeKernel::SampleA => {
290                ntt::mlkem_sample_a(&ints(0)?, int(1)?, int(2)?).map(from_ints)
291            }
292            NativeKernel::ToMont => ntt::mlkem_to_mont(&ints(0)?).map(from_ints),
293            NativeKernel::MlkemKeypair => {
294                mlkem::mlkem_keypair_seq(&ints(0)?, &ints(1)?).map(from_ints)
295            }
296            NativeKernel::MlkemEncapsKem => {
297                mlkem::mlkem_encaps_seq(&ints(0)?, &ints(1)?).map(from_ints)
298            }
299            NativeKernel::MlkemDecapsKem => {
300                mlkem::mlkem_decaps_seq(&ints(0)?, &ints(1)?).map(from_ints)
301            }
302            NativeKernel::MldsaKeypair => mldsa::mldsa_keypair_seq(&ints(0)?).map(from_ints),
303            NativeKernel::MldsaSign => {
304                mldsa::mldsa_sign_seq(&ints(0)?, &ints(1)?, &ints(2)?).map(from_ints)
305            }
306            NativeKernel::MldsaVerify => {
307                mldsa::mldsa_verify_seq(&ints(0)?, &ints(1)?, &ints(2)?, &ints(3)?)
308                    .map(RuntimeValue::Int)
309            }
310        };
311        ran.map_err(|why| self.failure(&why))
312    }
313
314    /// The report a refused call stops the program with, on every tier: the kernel's name, then why
315    /// its `logicaffeine_system` function refused the arguments. The compiled tier panics with the same
316    /// text (see the Rust backend's native-function emission).
317    pub fn failure(self, why: &str) -> String {
318        format!("{}(): {why}", self.name())
319    }
320}
321
322/// The refusal for a backend that lowers compiled bytecode but cannot link the Rust kernels: `Err` at
323/// the first kernel call that can RUN (named when its code is a constant, as the VM compiler emits
324/// it). A kernel in a function nothing reaches is code the loader spliced in and nothing calls, so it
325/// refuses nothing — [`crate::vm::reach`] is the same answer the backends lower by.
326pub fn refuse_kernel_calls(
327    program: &crate::vm::CompiledProgram,
328    interner: &crate::Interner,
329    backend: &str,
330) -> Result<(), String> {
331    refuse_kernel_calls_with(
332        program,
333        interner,
334        backend,
335        &crate::vm::reach::HostEntries::default(),
336    )
337}
338
339/// [`refuse_kernel_calls`], judging what the host's own `entries` reach as well as Main — the same
340/// roots a module built with those entries lowers.
341pub fn refuse_kernel_calls_with(
342    program: &crate::vm::CompiledProgram,
343    interner: &crate::Interner,
344    backend: &str,
345    entries: &crate::vm::reach::HostEntries,
346) -> Result<(), String> {
347    use crate::semantics::builtins::BuiltinId;
348    use crate::vm::{Constant, Op};
349    for (pc, op) in crate::vm::reach::running_ops_with(program, interner, entries) {
350        let Op::CallBuiltin {
351            builtin: BuiltinId::NativeKernel,
352            args_start,
353            ..
354        } = *op
355        else {
356            continue;
357        };
358        let kernel = program.code[..pc]
359            .iter()
360            .rev()
361            .find_map(|prior| match *prior {
362                Op::LoadConst { dst, idx } if dst == args_start => {
363                    match program.constants.get(idx as usize) {
364                        Some(Constant::Int(code)) => Some(NativeKernel::from_code(*code)),
365                        _ => Some(None),
366                    }
367                }
368                _ => None,
369            });
370        return Err(match kernel.flatten() {
371            Some(k) => k.refusal(backend),
372            None => format!(
373                "the program calls a standard-library native kernel (crypto.lg) implemented in Rust — the \
374                 {backend} backend cannot link it"
375            ),
376        });
377    }
378    Ok(())
379}
380
381fn int_arg(kernel: &str, v: &RuntimeValue) -> Result<i64, String> {
382    match v {
383        RuntimeValue::Int(n) => Ok(*n),
384        other => Err(format!(
385            "{kernel}() needs an Int here, got {}",
386            other.type_name()
387        )),
388    }
389}
390
391fn int_seq(kernel: &str, v: &RuntimeValue) -> Result<Vec<i64>, String> {
392    let RuntimeValue::List(items) = v else {
393        return Err(format!(
394            "{kernel}() needs a Seq of Int here, got {}",
395            v.type_name()
396        ));
397    };
398    items
399        .borrow()
400        .to_values()
401        .iter()
402        .enumerate()
403        .map(|(i, e)| match e {
404            RuntimeValue::Int(n) => Ok(*n),
405            other => Err(format!(
406                "{kernel}() needs a Seq of Int here; item {} is {}",
407                i + 1,
408                other.type_name()
409            )),
410        })
411        .collect()
412}
413
414fn word16_seq(kernel: &str, v: &RuntimeValue) -> Result<Vec<Word16>, String> {
415    let RuntimeValue::List(items) = v else {
416        return Err(format!(
417            "{kernel}() needs a Seq of Word16 here, got {}",
418            v.type_name()
419        ));
420    };
421    items
422        .borrow()
423        .to_values()
424        .iter()
425        .enumerate()
426        .map(|(i, e)| match e {
427            RuntimeValue::Word(WordVal::W16(w)) => Ok(*w),
428            other => Err(format!(
429                "{kernel}() needs a Seq of Word16 here; item {} is {}",
430                i + 1,
431                other.type_name()
432            )),
433        })
434        .collect()
435}
436
437fn from_ints(seq: LogosSeq<i64>) -> RuntimeValue {
438    RuntimeValue::List(Rc::new(RefCell::new(ListRepr::Ints(seq.to_vec()))))
439}
440
441fn from_w16(seq: LogosSeq<Word16>) -> RuntimeValue {
442    let values = seq
443        .to_vec()
444        .into_iter()
445        .map(|w| RuntimeValue::Word(WordVal::W16(w)))
446        .collect();
447    RuntimeValue::List(Rc::new(RefCell::new(ListRepr::Boxed(values))))
448}
449
450#[cfg(test)]
451#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/semantics/native_kernels/tests.rs"]
452mod tests;
logicaffeine_compile/semantics/native_kernels.rs

logicaffeine_compile/semantics/
native_kernels.rs
