ic-ec 0.3.1

X25519, Ed25519, and elliptic-curve arithmetic for IronCrypto
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

//! `safegcd`'s packed divsteps as x86-64 assembly: the same steps on the
//! same packed words, each decision a conditional move.
//!
//! In Rust each step's decisions are masks, and a mask costs a chain of
//! instructions -- the parity, its negation, an `and` -- between `g` and
//! the sum it selects; measured, a step took about eight cycles, the length
//! of that chain, and so did the packed form, whose words are fewer but
//! whose chain is the same. Here both candidate sums are formed while the
//! decisions are made, and `cmov` picks: `g`'s chain is a sum, two moves
//! and a shift, about four cycles. A `cmov` reads its flags and both
//! operands whatever they hold, so nothing branches and nothing is indexed
//! by data.
//!
//! The step counts are the rounds `safegcd` runs: 19 and 5 of Bernstein and
//! Yang's divsteps, 19 and 2 of the half-delta ones. Its tests hold every
//! batch, through these, to the divsteps step by step.

use core::arch::asm;

/// One of Bernstein and Yang's divsteps on the packed `f` and `g`, `delta`
/// in `d`: where `delta > 0` and `g` is odd, `(1 - delta, g, (g - f) / 2)`;
/// otherwise `(1 + delta, f, (g + (g mod 2) f) / 2)`.
macro_rules! by_step {
    () => {
        concat!(
            // The candidates: g + f, g - f; 1 - delta, 1 + delta.
            "lea {t}, [{g} + {f}]\n",
            "mov {s}, {g}\n",
            "sub {s}, {f}\n",
            "mov {a:e}, 1\n",
            "sub {a}, {d}\n",
            "lea {e}, [{d} + 1]\n",
            "mov {c}, {f}\n",
            "mov {b}, {e}\n",
            // delta > 0: the difference, f becomes g, 1 - delta.
            "test {d}, {d}\n",
            "cmovg {t}, {s}\n",
            "cmovg {c}, {g}\n",
            "cmovg {b}, {a}\n",
            // g even: g alone, f stays, 1 + delta.
            "test {g:e}, 1\n",
            "cmovz {t}, {g}\n",
            "cmovz {c}, {f}\n",
            "cmovz {b}, {e}\n",
            "sar {t}, 1\n",
            "mov {f}, {c}\n",
            "mov {g}, {t}\n",
            "mov {d}, {b}\n",
        )
    };
}

/// One half-delta divstep on the packed `f` and `g`, `zeta` in `d`: where
/// `zeta < 0` and `g` is odd, `(-zeta - 2, g, (g - f) / 2)`; otherwise
/// `(zeta - 1, f, (g + (g mod 2) f) / 2)`.
macro_rules! hd_step {
    () => {
        concat!(
            // The candidates: g + f, g - f; -zeta - 2, zeta - 1.
            "lea {t}, [{g} + {f}]\n",
            "mov {s}, {g}\n",
            "sub {s}, {f}\n",
            "mov {a}, {d}\n",
            "not {a}\n",
            "lea {a}, [{a} - 1]\n",
            "lea {e}, [{d} - 1]\n",
            "mov {c}, {f}\n",
            "mov {b}, {e}\n",
            // zeta < 0: the difference, f becomes g, -zeta - 2.
            "test {d}, {d}\n",
            "cmovs {t}, {s}\n",
            "cmovs {c}, {g}\n",
            "cmovs {b}, {a}\n",
            // g even: g alone, f stays, zeta - 1.
            "test {g:e}, 1\n",
            "cmovz {t}, {g}\n",
            "cmovz {c}, {f}\n",
            "cmovz {b}, {e}\n",
            "sar {t}, 1\n",
            "mov {f}, {c}\n",
            "mov {g}, {t}\n",
            "mov {d}, {b}\n",
        )
    };
}

/// Runs of a step, written out.
macro_rules! x2 {
    ($s:ident) => {
        concat!($s!(), $s!())
    };
}
macro_rules! x4 {
    ($s:ident) => {
        concat!(x2!($s), x2!($s))
    };
}
macro_rules! x16 {
    ($s:ident) => {
        concat!(x4!($s), x4!($s), x4!($s), x4!($s))
    };
}

/// A function running `$steps` of one kind on `(d, f, g)`.
macro_rules! runner {
    ($name:ident, $doc:literal, $($body:tt)*) => {
        #[doc = $doc]
        #[inline(always)]
        pub(super) fn $name(d: &mut i64, f: &mut i64, g: &mut i64) {
            // SAFETY: the block reads and writes only the registers it
            // declares, touches no memory and no stack, and needs nothing
            // beyond the x86-64 baseline (`cmov`).
            unsafe {
                asm!(
                    ".p2align 6",
                    $($body)*,
                    d = inout(reg) *d,
                    f = inout(reg) *f,
                    g = inout(reg) *g,
                    t = out(reg) _,
                    s = out(reg) _,
                    a = out(reg) _,
                    e = out(reg) _,
                    c = out(reg) _,
                    b = out(reg) _,
                    options(pure, nomem, nostack),
                );
            }
        }
    };
}

runner!(
    by_19,
    "Nineteen divsteps.",
    x16!(by_step),
    x2!(by_step),
    by_step!()
);
runner!(by_5, "Five divsteps.", x4!(by_step), by_step!());
runner!(
    hd_19,
    "Nineteen half-delta divsteps.",
    x16!(hd_step),
    x2!(hd_step),
    hd_step!()
);
runner!(hd_2, "Two half-delta divsteps.", x2!(hd_step));