ff_derive/
pow_fixed.rs

1//! Fixed-exponent variable-base exponentiation using addition chains.
2
3use addchain::{build_addition_chain, Step};
4use num_bigint::BigUint;
5use quote::quote;
6use syn::Ident;
7
8/// Returns t{n} as an ident.
9fn get_temp(n: usize) -> Ident {
10    Ident::new(&format!("t{}", n), proc_macro2::Span::call_site())
11}
12
13pub(crate) fn generate(
14    base: &proc_macro2::TokenStream,
15    exponent: BigUint,
16) -> proc_macro2::TokenStream {
17    let steps = build_addition_chain(exponent);
18
19    let mut gen = proc_macro2::TokenStream::new();
20
21    // First entry in chain is one, i.e. the base.
22    let start = get_temp(0);
23    gen.extend(quote! {
24        let #start = #base;
25    });
26
27    let mut tmps = vec![start];
28    for (i, step) in steps.into_iter().enumerate() {
29        let out = get_temp(i + 1);
30
31        gen.extend(match step {
32            Step::Double { index } => {
33                let val = &tmps[index];
34                quote! {
35                    let #out = #val.square();
36                }
37            }
38            Step::Add { left, right } => {
39                let left = &tmps[left];
40                let right = &tmps[right];
41                quote! {
42                    let #out = #left * #right;
43                }
44            }
45        });
46
47        tmps.push(out.clone());
48    }
49
50    let end = tmps.last().expect("have last");
51    gen.extend(quote! {
52        #end
53    });
54
55    gen
56}