ff-derive-arcium-fork 0.13.2

Procedural macro library used to build custom prime field implementations (Arcium fork)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! Fixed-exponent variable-base exponentiation using addition chains.

use addchain::{build_addition_chain, Step};
use num_bigint::BigUint;
use quote::quote;
use syn::Ident;

/// Returns t{n} as an ident.
fn get_temp(n: usize) -> Ident {
    Ident::new(&format!("t{}", n), proc_macro2::Span::call_site())
}

pub(crate) fn generate(
    base: &proc_macro2::TokenStream,
    exponent: BigUint,
) -> proc_macro2::TokenStream {
    let steps = build_addition_chain(exponent);
    // last_usage[i] indicates the last usage of the i-th temporary variable.
    let last_usage = steps
        .iter()
        .enumerate()
        .fold(Vec::new(), |mut acc, (n, step)| {
            acc.push(n);
            match step {
                Step::Double { index } => acc[*index] = n,
                Step::Add { left, right } => {
                    acc[*left] = n;
                    acc[*right] = n;
                }
            }
            acc
        });
    // drops is the ordered sequence of possible drops of the temporary variable
    // the first component is the variable to drop, the second is when to drop it
    let drops: Vec<(usize, usize)> = {
        let mut drops: Vec<(usize, usize)> = last_usage.into_iter().enumerate().collect();
        drops.sort_by_key(|(_i, last_usage)| *last_usage);
        drops
    };

    let mut gen = proc_macro2::TokenStream::new();

    // contains all idents that can be reused
    let mut free_idents: Vec<Ident> = Vec::new();
    // the number of variables that have been used so far.
    let mut n_vars = 0usize;
    // give code for using a free variable, and the corresponding ident
    fn get_free_variable(
        v: &mut Vec<Ident>,
        n_vars: &mut usize,
    ) -> (proc_macro2::TokenStream, Ident) {
        if let Some(last) = v.pop() {
            (quote! { #last }, last)
        } else {
            let ident = get_temp(*n_vars);
            *n_vars += 1;
            (quote! { let mut #ident }, ident)
        }
    }

    // First entry in chain is one, i.e. the base.
    let (start_code, start) = get_free_variable(&mut free_idents, &mut n_vars);
    gen.extend(quote! {
        #start_code = *#base; // the asterisk makes it work
    });

    let mut tmps = vec![start];
    // current location in drops
    let mut drop_index = 0usize;
    for (i, step) in steps.into_iter().enumerate() {
        // allow reuse of everything that will be dropped in this instruction
        while drop_index < drops.len() && drops[drop_index].1 <= i {
            free_idents.push(tmps[drops[drop_index].0].clone());
            drop_index += 1;
        }
        let (out_code, out) = get_free_variable(&mut free_idents, &mut n_vars);

        gen.extend(match step {
            Step::Double { index } => {
                let val = &tmps[index];
                quote! {
                    #out_code = #val.square();
                }
            }
            Step::Add { left, right } => {
                let left = &tmps[left];
                let right = &tmps[right];
                if left.to_string() == out.to_string() {
                    quote! {
                        #left *= #right;
                    }
                } else if right.to_string() == out.to_string() {
                    quote! {
                        #right *= #left;
                    }
                } else {
                    quote! {
                        #out_code = #left * #right;
                    }
                }
            }
        });

        tmps.push(out);
    }

    let end = tmps.last().expect("have last");
    gen.extend(quote! {
        #end
    });

    gen
}