in math/src/field/f128/mod.rs [448:541]
fn inv(x: u128) -> u128 {
if x == 0 {
return 0;
};
// initialize v, a, u, and d variables
let mut v = M;
let (mut a0, mut a1, mut a2) = (0, 0, 0);
let (mut u0, mut u1, mut u2) = if x & 1 == 1 {
// u = x
(x as u64, (x >> 64) as u64, 0)
} else {
// u = x + m
add_192x192(x as u64, (x >> 64) as u64, 0, M as u64, (M >> 64) as u64, 0)
};
// d = m - 1
let (mut d0, mut d1, mut d2) = ((M as u64) - 1, (M >> 64) as u64, 0);
// compute the inverse
while v != 1 {
while u2 > 0 || ((u0 as u128) + ((u1 as u128) << 64)) > v {
// u > v
// u = u - v
let (t0, t1, t2) = sub_192x192(u0, u1, u2, v as u64, (v >> 64) as u64, 0);
u0 = t0;
u1 = t1;
u2 = t2;
// d = d + a
let (t0, t1, t2) = add_192x192(d0, d1, d2, a0, a1, a2);
d0 = t0;
d1 = t1;
d2 = t2;
while u0 & 1 == 0 {
if d0 & 1 == 1 {
// d = d + m
let (t0, t1, t2) = add_192x192(d0, d1, d2, M as u64, (M >> 64) as u64, 0);
d0 = t0;
d1 = t1;
d2 = t2;
}
// u = u >> 1
u0 = (u0 >> 1) | ((u1 & 1) << 63);
u1 = (u1 >> 1) | ((u2 & 1) << 63);
u2 >>= 1;
// d = d >> 1
d0 = (d0 >> 1) | ((d1 & 1) << 63);
d1 = (d1 >> 1) | ((d2 & 1) << 63);
d2 >>= 1;
}
}
// v = v - u (u is less than v at this point)
v -= (u0 as u128) + ((u1 as u128) << 64);
// a = a + d
let (t0, t1, t2) = add_192x192(a0, a1, a2, d0, d1, d2);
a0 = t0;
a1 = t1;
a2 = t2;
while v & 1 == 0 {
if a0 & 1 == 1 {
// a = a + m
let (t0, t1, t2) = add_192x192(a0, a1, a2, M as u64, (M >> 64) as u64, 0);
a0 = t0;
a1 = t1;
a2 = t2;
}
v >>= 1;
// a = a >> 1
a0 = (a0 >> 1) | ((a1 & 1) << 63);
a1 = (a1 >> 1) | ((a2 & 1) << 63);
a2 >>= 1;
}
}
// a = a mod m
let mut a = (a0 as u128) + ((a1 as u128) << 64);
while a2 > 0 || a >= M {
let (t0, t1, t2) = sub_192x192(a0, a1, a2, M as u64, (M >> 64) as u64, 0);
a0 = t0;
a1 = t1;
a2 = t2;
a = (a0 as u128) + ((a1 as u128) << 64);
}
a
}