use tc_bigint::{Limb, Word};
use tc_zeroize::Zeroize;
use crate::limb::{
add_masked, borrow_out, halve_masked, is_one, reduce_once, select_assign, sub_masked,
};
pub(crate) fn binary_inverse<S>(value: &[Limb], modulus: &[Limb], zero: &S) -> Option<S>
where
S: AsRef<[Limb]> + AsMut<[Limb]> + Clone,
{
let start = |limbs: &[Limb]| {
let mut started = zero.clone();
started.as_mut().copy_from_slice(limbs);
started
};
let one = |mut limbs: S| {
limbs.as_mut()[0] = Limb::new(1);
limbs
};
let (mut u, mut v) = (start(value), start(modulus));
let (mut a, mut b) = (one(zero.clone()), zero.clone());
let (mut c, mut d) = (zero.clone(), one(zero.clone()));
let (mut first, mut second) = (zero.clone(), zero.clone());
for _ in 0..2 * modulus.len() as u32 * Word::BITS {
let both_odd = (low_bit(u.as_ref()) & low_bit(v.as_ref())).wrapping_neg();
let v_below_u = borrow_out(v.as_ref(), u.as_ref()).wrapping_neg();
first.as_mut().copy_from_slice(v.as_ref());
sub_masked(first.as_mut(), u.as_ref(), Word::MAX);
select_assign(v.as_mut(), first.as_ref(), both_odd & !v_below_u);
first.as_mut().copy_from_slice(u.as_ref());
sub_masked(first.as_mut(), v.as_ref(), Word::MAX);
select_assign(u.as_mut(), first.as_ref(), both_odd & v_below_u);
first.as_mut().copy_from_slice(a.as_ref());
let carry = add_masked(first.as_mut(), c.as_ref(), Word::MAX);
second.as_mut().copy_from_slice(first.as_ref());
let below = sub_masked(second.as_mut(), modulus, Word::MAX);
let reduce = (carry | (below ^ 1)).wrapping_neg();
select_assign(first.as_mut(), second.as_ref(), reduce);
select_assign(a.as_mut(), first.as_ref(), both_odd & v_below_u);
select_assign(c.as_mut(), first.as_ref(), both_odd & !v_below_u);
first.as_mut().copy_from_slice(b.as_ref());
add_masked(first.as_mut(), d.as_ref(), Word::MAX);
second.as_mut().copy_from_slice(first.as_ref());
sub_masked(second.as_mut(), value, Word::MAX);
select_assign(first.as_mut(), second.as_ref(), reduce);
select_assign(b.as_mut(), first.as_ref(), both_odd & v_below_u);
select_assign(d.as_mut(), first.as_ref(), both_odd & !v_below_u);
halve_with(&mut u, &mut a, &mut b, value, modulus);
halve_with(&mut v, &mut c, &mut d, value, modulus);
}
reduce_once(a.as_mut(), 0, modulus);
let either_odd = low_bit(value) | low_bit(modulus);
let invertible = either_odd & (is_one(u.as_ref()) | is_one(modulus));
for working in [
&mut u,
&mut v,
&mut b,
&mut c,
&mut d,
&mut first,
&mut second,
] {
working.as_mut().zeroize();
}
if invertible == 1 {
Some(a)
} else {
a.as_mut().zeroize();
None
}
}
fn halve_with<S>(x: &mut S, p: &mut S, q: &mut S, value: &[Limb], modulus: &[Limb])
where
S: AsRef<[Limb]> + AsMut<[Limb]>,
{
let even = (low_bit(x.as_ref()) ^ 1).wrapping_neg();
halve_masked(x.as_mut(), 0, even);
let odd = (low_bit(p.as_ref()) | low_bit(q.as_ref())).wrapping_neg();
let p_carry = add_masked(p.as_mut(), modulus, odd & even);
let q_carry = add_masked(q.as_mut(), value, odd & even);
halve_masked(p.as_mut(), p_carry, even);
halve_masked(q.as_mut(), q_carry, even);
}
fn low_bit(value: &[Limb]) -> Word {
value.first().map_or(0, |limb| limb.to_word() & 1)
}