rust: const fn support

[tarcieri]

I've started work integrating the Rust output from fiat-crypto into the RustCrypto p384 crate.

One of the biggest hurdles I've encountered is that in our other elliptic curve crates we make extensive use of const fn to precompute constants at compile time. This isn't possible with the Rust output from fiat-crypto today as the generated functions aren't const fn.

While for the most part this could be relatively straightforward due to the arithmetic nature of these functions, there is one major impediment: the APIs all operate on an out: &mut ... parameter as opposed to returning a value, and this is not presently supported by const fn: rust-lang/rust#57349

It seems when this upstream blocker is addressed, it should be trivial to add const to the function signatures. Alternatively, the functions could return the outputs as opposed to writing them into an &mut output buffer.

[JasonGross]

Alternatively, the functions could return the outputs as opposed to writing them into an &mut output buffer.

What's the syntax for this in Rust? (Does this change the allocation behavior?). (There were some requests for this in the Go code, too, and it's been on my to-do list for a while.)

[tarcieri]

Here is a function from the p384 code as it exists today:

pub fn fiat_p384_set_one(out1: &mut fiat_p384_montgomery_domain_field_element) -> () {
  out1[0] = 0xffffffff00000001;
  out1[1] = 0xffffffff;
  out1[2] = (0x1 as u64);
  out1[3] = (0x0 as u64);
  out1[4] = (0x0 as u64);
  out1[5] = (0x0 as u64);
}

Here it is rewritten to return a value, which allows it to be const fn:

pub const fn fiat_p384_set_one() -> fiat_p384_montgomery_domain_field_element {
  let mut out1 = fiat_p384_montgomery_domain_field_element::default();
  out1[0] = 0xffffffff00000001;
  out1[1] = 0xffffffff;
  out1[2] = (0x1 as u64);
  out1[3] = (0x0 as u64);
  out1[4] = (0x0 as u64);
  out1[5] = (0x0 as u64);
  out1
}

...or more idiomatically:

pub const fn fiat_p384_set_one() -> fiat_p384_montgomery_domain_field_element {
    [
        0xffffffff00000001,
        0xffffffff,
        0x1,
        0x0,
        0x0,
        0x0,
    ]
}

[tarcieri]

Also note: the generated ASM for the const fn examples above should generally be the same, as LLVM is typically smart enough to elide the zero-initialization performed by fiat_p384_montgomery_domain_field_element::default() if the entire array is subsequently rewritten.

Does this change the allocation behavior?

If the function isn't inlined, then this introduces a copy of the return value, at least until placement by return lands.

However, if the function is inlined in my observations LLVM is generally smart enough to avoid that, which allows in-place mutation of a field element by optimizing away the array allocation entirely.

[tarcieri]

I wrote a tool to mechanically translate fiat-crypto's Rust output into const fn form:

https://github.com/RustCrypto/utils/tree/master/fiat-constify

It's a PoC which leaves some unused/dead code in the output, but that should be automatically removed by LLVM.

Benchmarking various P-384 operations (happens to be the crate I'm working on) shows what appears to be a ~5% performance regression in const fn form, but I should stress I haven't benchmarked particularly carefully and it could just be noise:

RustCrypto/elliptic-curves#589

Anyway, this is very useful for precomputing constants and things like basepoint tables at compile time using CTFE rather than some sort of two-stage build approach, and I'd love to see it at least optionally supported in a first-class manner.