use super::div_limb::{div_rem_limb_with_reciprocal, Reciprocal};
use crate::{CtChoice, Limb, NonZero, Uint, Word, Wrapping};
use core::ops::{Div, DivAssign, Rem, RemAssign};
use subtle::CtOption;
impl<const LIMBS: usize> Uint<LIMBS> {
#[inline(always)]
pub const fn ct_div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
div_rem_limb_with_reciprocal(self, reciprocal)
}
#[inline(always)]
pub fn div_rem_limb_with_reciprocal(
&self,
reciprocal: &CtOption<Reciprocal>,
) -> CtOption<(Self, Limb)> {
reciprocal.map(|r| div_rem_limb_with_reciprocal(self, &r))
}
#[inline(always)]
pub(crate) const fn ct_div_rem_limb(&self, rhs: Limb) -> (Self, Limb, CtChoice) {
let (reciprocal, is_some) = Reciprocal::ct_new(rhs);
let (quo, rem) = div_rem_limb_with_reciprocal(self, &reciprocal);
(quo, rem, is_some)
}
#[inline(always)]
pub fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
let (quo, rem, _is_some) = self.ct_div_rem_limb(*rhs);
(quo, rem)
}
pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, CtChoice) {
let mb = rhs.bits_vartime();
let mut bd = Self::BITS - mb;
let mut rem = *self;
let mut quo = Self::ZERO;
let mut c = rhs.shl_vartime(bd);
loop {
let (mut r, borrow) = rem.sbb(&c, Limb::ZERO);
rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
r = quo.bitor(&Self::ONE);
quo = Self::ct_select(&r, &quo, CtChoice::from_mask(borrow.0));
if bd == 0 {
break;
}
bd -= 1;
c = c.shr_vartime(1);
quo = quo.shl_vartime(1);
}
let is_some = Limb(mb as Word).ct_is_nonzero();
quo = Self::ct_select(&Self::ZERO, &quo, is_some);
(quo, rem, is_some)
}
pub const fn const_rem(&self, rhs: &Self) -> (Self, CtChoice) {
let mb = rhs.bits_vartime();
let mut bd = Self::BITS - mb;
let mut rem = *self;
let mut c = rhs.shl_vartime(bd);
loop {
let (r, borrow) = rem.sbb(&c, Limb::ZERO);
rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
if bd == 0 {
break;
}
bd -= 1;
c = c.shr_vartime(1);
}
let is_some = Limb(mb as Word).ct_is_nonzero();
(rem, is_some)
}
pub const fn const_rem_wide(lower_upper: (Self, Self), rhs: &Self) -> (Self, CtChoice) {
let mb = rhs.bits_vartime();
let mut bd = (2 * Self::BITS) - mb;
let (mut lower, mut upper) = lower_upper;
let mut c = Self::shl_vartime_wide((*rhs, Uint::ZERO), bd);
loop {
let (lower_sub, borrow) = lower.sbb(&c.0, Limb::ZERO);
let (upper_sub, borrow) = upper.sbb(&c.1, borrow);
lower = Self::ct_select(&lower_sub, &lower, CtChoice::from_mask(borrow.0));
upper = Self::ct_select(&upper_sub, &upper, CtChoice::from_mask(borrow.0));
if bd == 0 {
break;
}
bd -= 1;
c = Self::shr_vartime_wide(c, 1);
}
let is_some = Limb(mb as Word).ct_is_nonzero();
(lower, is_some)
}
pub const fn rem2k(&self, k: usize) -> Self {
let highest = (LIMBS - 1) as u32;
let index = k as u32 / (Limb::BITS as u32);
let le = Limb::ct_le(Limb::from_u32(index), Limb::from_u32(highest));
let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize;
let base = k % Limb::BITS;
let mask = (1 << base) - 1;
let mut out = *self;
let outmask = Limb(out.limbs[word].0 & mask);
out.limbs[word] = Limb::ct_select(out.limbs[word], outmask, le);
let mut i = word + 1;
while i < LIMBS {
out.limbs[i] = Limb::ZERO;
i += 1;
}
out
}
pub fn div_rem(&self, rhs: &NonZero<Self>) -> (Self, Self) {
let (q, r, _c) = self.ct_div_rem(rhs);
(q, r)
}
pub fn rem(&self, rhs: &NonZero<Self>) -> Self {
let (r, _c) = self.const_rem(rhs);
r
}
pub const fn wrapping_div(&self, rhs: &Self) -> Self {
let (q, _, c) = self.ct_div_rem(rhs);
assert!(c.is_true_vartime(), "divide by zero");
q
}
pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
NonZero::new(*rhs).map(|rhs| {
let (q, _r) = self.div_rem(&rhs);
q
})
}
pub const fn wrapping_rem(&self, rhs: &Self) -> Self {
let (r, c) = self.const_rem(rhs);
assert!(c.is_true_vartime(), "modulo zero");
r
}
pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
}
}
impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
*self / *rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Limb>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
self / *rhs
}
}
impl<const LIMBS: usize> Div<NonZero<Limb>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: NonZero<Limb>) -> Self::Output {
*self / rhs
}
}
impl<const LIMBS: usize> Div<NonZero<Limb>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: NonZero<Limb>) -> Self::Output {
let (q, _, _) = self.ct_div_rem_limb(*rhs);
q
}
}
impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Uint<LIMBS> {
fn div_assign(&mut self, rhs: &NonZero<Limb>) {
*self /= *rhs;
}
}
impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Uint<LIMBS> {
fn div_assign(&mut self, rhs: NonZero<Limb>) {
*self = *self / rhs;
}
}
impl<const LIMBS: usize> Div<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: NonZero<Limb>) -> Self::Output {
Wrapping(self.0 / rhs)
}
}
impl<const LIMBS: usize> Div<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: NonZero<Limb>) -> Self::Output {
*self / rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
*self / *rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
self / *rhs
}
}
impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
fn div_assign(&mut self, rhs: &NonZero<Limb>) {
*self = Wrapping(self.0 / rhs)
}
}
impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
fn div_assign(&mut self, rhs: NonZero<Limb>) {
*self /= &rhs;
}
}
impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Uint<LIMBS> {
type Output = Limb;
fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
*self % *rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Uint<LIMBS> {
type Output = Limb;
fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
self % *rhs
}
}
impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Uint<LIMBS> {
type Output = Limb;
fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
*self % rhs
}
}
impl<const LIMBS: usize> Rem<NonZero<Limb>> for Uint<LIMBS> {
type Output = Limb;
fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
let (_, r, _) = self.ct_div_rem_limb(*rhs);
r
}
}
impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Uint<LIMBS> {
fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
*self = (*self % rhs).into();
}
}
impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Uint<LIMBS> {
fn rem_assign(&mut self, rhs: NonZero<Limb>) {
*self %= &rhs;
}
}
impl<const LIMBS: usize> Rem<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Limb>;
fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
Wrapping(self.0 % rhs)
}
}
impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Limb>;
fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
*self % rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Limb>;
fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
*self % *rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Limb>;
fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
self % *rhs
}
}
impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
fn rem_assign(&mut self, rhs: NonZero<Limb>) {
*self %= &rhs;
}
}
impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
*self = Wrapping((self.0 % rhs).into())
}
}
impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
*self / *rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
self / *rhs
}
}
impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
*self / rhs
}
}
impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
let (q, _) = self.div_rem(&rhs);
q
}
}
impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
*self /= *rhs
}
}
impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
*self = *self / rhs;
}
}
impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
Wrapping(self.0 / rhs)
}
}
impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
*self / rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
*self / *rhs
}
}
impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
self / *rhs
}
}
impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
*self = Wrapping(self.0 / rhs);
}
}
impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
*self /= &rhs;
}
}
impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
*self % *rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
self % *rhs
}
}
impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
*self % rhs
}
}
impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
type Output = Uint<LIMBS>;
fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
Self::rem(&self, &rhs)
}
}
impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
*self %= *rhs
}
}
impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
*self = *self % rhs;
}
}
impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
Wrapping(self.0 % rhs)
}
}
impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
*self % rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
*self % *rhs
}
}
impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
type Output = Wrapping<Uint<LIMBS>>;
fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
self % *rhs
}
}
impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
*self %= &rhs;
}
}
impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
*self = Wrapping(self.0 % rhs)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{limb::HI_BIT, Limb, U256};
#[cfg(feature = "rand")]
use {
crate::{CheckedMul, Random},
rand_chacha::ChaChaRng,
rand_core::RngCore,
rand_core::SeedableRng,
};
#[test]
fn div_word() {
for (n, d, e, ee) in &[
(200u64, 2u64, 100u64, 0),
(100u64, 25u64, 4u64, 0),
(100u64, 10u64, 10u64, 0),
(1024u64, 8u64, 128u64, 0),
(27u64, 13u64, 2u64, 1u64),
(26u64, 13u64, 2u64, 0u64),
(14u64, 13u64, 1u64, 1u64),
(13u64, 13u64, 1u64, 0u64),
(12u64, 13u64, 0u64, 12u64),
(1u64, 13u64, 0u64, 1u64),
] {
let lhs = U256::from(*n);
let rhs = U256::from(*d);
let (q, r, is_some) = lhs.ct_div_rem(&rhs);
assert!(is_some.is_true_vartime());
assert_eq!(U256::from(*e), q);
assert_eq!(U256::from(*ee), r);
}
}
#[cfg(feature = "rand")]
#[test]
fn div() {
let mut rng = ChaChaRng::from_seed([7u8; 32]);
for _ in 0..25 {
let num = U256::random(&mut rng).shr_vartime(128);
let den = U256::random(&mut rng).shr_vartime(128);
let n = num.checked_mul(&den);
if n.is_some().into() {
let (q, _, is_some) = n.unwrap().ct_div_rem(&den);
assert!(is_some.is_true_vartime());
assert_eq!(q, num);
}
}
}
#[test]
fn div_max() {
let mut a = U256::ZERO;
let mut b = U256::ZERO;
b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
let q = a.wrapping_div(&b);
assert_eq!(q, Uint::ZERO);
a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
let q = a.wrapping_div(&b);
assert_eq!(q, Uint::ZERO);
}
#[test]
fn div_zero() {
let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO);
assert!(!is_some.is_true_vartime());
assert_eq!(q, U256::ZERO);
assert_eq!(r, U256::ONE);
}
#[test]
fn div_one() {
let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE);
assert!(is_some.is_true_vartime());
assert_eq!(q, U256::from(10u8));
assert_eq!(r, U256::ZERO);
}
#[test]
fn reduce_one() {
let (r, is_some) = U256::from(10u8).const_rem(&U256::ONE);
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::ZERO);
}
#[test]
fn reduce_zero() {
let u = U256::from(10u8);
let (r, is_some) = u.const_rem(&U256::ZERO);
assert!(!is_some.is_true_vartime());
assert_eq!(r, u);
}
#[test]
fn reduce_tests() {
let (r, is_some) = U256::from(10u8).const_rem(&U256::from(2u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::ZERO);
let (r, is_some) = U256::from(10u8).const_rem(&U256::from(3u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::ONE);
let (r, is_some) = U256::from(10u8).const_rem(&U256::from(7u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::from(3u8));
}
#[test]
fn reduce_tests_wide_zero_padded() {
let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(2u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::ZERO);
let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(3u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::ONE);
let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(7u8));
assert!(is_some.is_true_vartime());
assert_eq!(r, U256::from(3u8));
}
#[test]
fn reduce_max() {
let mut a = U256::ZERO;
let mut b = U256::ZERO;
b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
let r = a.wrapping_rem(&b);
assert_eq!(r, Uint::ZERO);
a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
let r = a.wrapping_rem(&b);
assert_eq!(r, a);
}
#[cfg(feature = "rand")]
#[test]
fn rem2krand() {
let mut rng = ChaChaRng::from_seed([7u8; 32]);
for _ in 0..25 {
let num = U256::random(&mut rng);
let k = (rng.next_u32() % 256) as usize;
let den = U256::ONE.shl_vartime(k);
let a = num.rem2k(k);
let e = num.wrapping_rem(&den);
assert_eq!(a, e);
}
}
#[allow(clippy::op_ref)]
#[test]
fn rem_trait() {
let a = U256::from(10u64);
let b = NonZero::new(U256::from(3u64)).unwrap();
let c = U256::from(1u64);
assert_eq!(a % b, c);
assert_eq!(a % &b, c);
assert_eq!(&a % b, c);
assert_eq!(&a % &b, c);
}
}