use std::intrinsics::assume;
use std::cmp::{self, Ordering};
use mem;
use ll;
use ll::limb::{self, Limb};
use super::{same_or_separate, overlap};
use ll::limb_ptr::{Limbs, LimbsMut};
pub unsafe fn divrem_1(mut qp: LimbsMut, qxn: i32,
xp: Limbs, mut xs: i32, d: Limb) -> Limb {
debug_assert!(qxn >= 0);
debug_assert!(xs >= 0);
debug_assert!(d != 0);
debug_assert!(same_or_separate(qp.offset(qxn as isize), xs, xp, xs));
assume(qxn >= 0);
assume(xs >= 0);
assume(d != 0);
let mut n = xs + qxn;
if n == 0 { return Limb(0); }
let qp_lo = qp;
qp = qp.offset((n - 1) as isize);
let mut r = Limb(0);
if d.high_bit_set() {
if xs != 0 {
r = *xp.offset((xs - 1) as isize);
let q = if r >= d { Limb(1) } else { Limb(0) };
*qp = q;
if qp > qp_lo {
qp = qp.offset(-1);
}
r = r - (d & -q);
xs -= 1;
}
let dinv = d.invert();
let mut i = xs - 1;
while i >= 0 {
let n0 = *xp.offset(i as isize);
let (q, rem) = limb::div_preinv(r, n0, d, dinv);
r = rem;
*qp = q;
if qp > qp_lo {
qp = qp.offset(-1);
}
i -= 1;
}
let mut i = qxn - 1;
while i >= 0 {
let (q, rem) = limb::div_preinv(r, Limb(0), d, dinv);
r = rem;
*qp = q;
if qp > qp_lo {
qp = qp.offset(-1);
}
i -= 1;
}
return r;
} else {
if xs != 0 {
let n1 = *xp.offset((xs - 1) as isize);
if n1 < d {
r = n1;
*qp = Limb(0);
if qp > qp_lo {
qp = qp.offset(-1);
}
n -= 1;
if n == 0 {
return r;
}
xs -= 1;
}
}
let cnt = d.leading_zeros() as usize;
let d = d << cnt;
r = r << cnt;
let dinv = d.invert();
if xs != 0 {
let mut n1 = *xp.offset((xs - 1) as isize);
r = r | (n1 >> (Limb::BITS - cnt));
let mut i = xs - 2;
while i >= 0 {
let n0 = *xp.offset(i as isize);
let nshift = (n1 << cnt) | (n0 >> (Limb::BITS - cnt));
let (q, rem) = limb::div_preinv(r, nshift, d, dinv);
r = rem;
*qp = q;
qp = qp.offset(-1);
n1 = n0;
i -= 1;
}
let (q, rem) = limb::div_preinv(r, n1 << cnt, d, dinv);
r = rem;
*qp = q;
if qp > qp_lo {
qp = qp.offset(-1);
}
}
let mut i = qxn - 1;
while i >= 0 {
let (q, rem) = limb::div_preinv(r, Limb(0), d, dinv);
r = rem;
*qp = q;
if qp > qp_lo {
qp = qp.offset(-1);
}
i -= 1;
}
return r >> cnt;
}
}
pub unsafe fn divrem_2(mut qp: LimbsMut, qxn: i32,
mut np: LimbsMut, ns: i32,
dp: Limbs) -> Limb {
debug_assert!(ns >= 2);
debug_assert!(qxn >= 0);
debug_assert!((*dp.offset(1)).high_bit_set());
debug_assert!(!overlap(qp, ns-2+qxn, np.as_const(), ns) || qp >= np.offset(2));
np = np.offset((ns - 2) as isize);
let d1 = *dp.offset(1);
let d0 = *dp.offset(0);
let mut r1 = *np.offset(1);
let mut r0 = *np.offset(0);
let mut most_significant_q_limb = 0;
if r1 >= d1 && (r1 > d1 || r0 >= d0) {
let (r_1, r_0) = ll::limb::sub_2(r1, r0, d1, d0);
r1 = r_1;
r0 = r_0;
most_significant_q_limb = 1;
}
let dinv = invert_pi(d1, d0);
qp = qp.offset(qxn as isize);
let mut i = ns - 2 - 1;
while i >= 0 {
let n0 = *np.offset(-1);
let (q, r_1, r_0) = divrem_3by2(r1, r0, n0, d1, d0, dinv);
np = np.offset(-1);
r1 = r_1;
r0 = r_0;
*qp.offset(i as isize) = q;
i -= 1;
}
if qxn != 0 {
qp = qp.offset(-qxn as isize);
let mut i = qxn - 1;
while i >= 0 {
let (q, r_1, r_0) = divrem_3by2(r1, r0, Limb(0), d1, d0, dinv);
r1 = r_1;
r0 = r_0;
*qp.offset(i as isize) = q;
i -= 1;
}
}
*np.offset(1) = r1;
*np = r0;
return Limb(most_significant_q_limb);
}
#[inline]
fn invert_pi(d1: Limb, d0: Limb) -> Limb {
let mut v = d1.invert();
let (mut p, cy) = (d1 * v).add_overflow(d0);
if cy {
v = v - 1;
let mask = if p >= d1 { Limb(!0) } else { Limb(0) };
p = p - d1;
v = v + mask;
p = p - (mask & d1);
}
let (t1, t0) = d0.mul_hilo(v);
p = p + t1;
if p < t1 {
v = v - 1;
if p >= d1 && (p > d1 || t0 >= d0) {
v = v - 1;
}
}
v
}
#[inline]
fn divrem_3by2(n2: Limb, n1: Limb, n0: Limb, d1: Limb, d0: Limb, dinv: Limb) -> (Limb, Limb, Limb) {
let (q, ql) = n2.mul_hilo(dinv);
let (q, ql) = ll::limb::add_2(q, ql, n2, n1);
let r1 = n1 - d1 * q;
let (r1, r0) = ll::limb::sub_2(r1, n0, d1, d0);
let (t1, t0) = d0.mul_hilo(q);
let (r1, r0) = ll::limb::sub_2(r1, r0, t1, t0);
let q = q + 1;
let mask = if r1 >= ql { Limb(!0) } else { Limb(0) };
let q = q + mask;
let (r1, r0) = ll::limb::add_2(r1, r0, mask & d1, mask & d0);
if r1 >= d1 && (r1 > d1 || r0 >= d0) {
let (r1, r0) = ll::limb::sub_2(r1, r0, d1, d0);
(q + 1, r1, r0)
} else {
(q, r1, r0)
}
}
pub unsafe fn divrem(mut qp: LimbsMut, mut rp: LimbsMut,
np: Limbs, ns: i32,
dp: Limbs, ds: i32) {
let max_result_size = cmp::max((ns - ds) + 1, 1);
debug_assert!(!overlap(qp, max_result_size, np, ns));
if ns < ds {
*qp = Limb(0);
ll::copy_incr(np, rp, ns);
return;
} else if ns == ds {
if let Ordering::Less = ll::cmp(np, dp, ns) {
*qp = Limb(0);
ll::copy_incr(np, rp, ns);
return;
}
}
match ds {
1 => {
let r = divrem_1(qp, 0, np, ns, *dp);
*rp = r;
}
2 => {
let mut tmp = mem::TmpAllocator::new();
let dh = *dp.offset((ds - 1) as isize);
let cnt = dh.leading_zeros() as usize;
if cnt == 0 {
let np_tmp = tmp.allocate((ns + 1) as usize);
ll::copy_incr(np, np_tmp, ns);
let qhl = divrem_2(qp, 0, np_tmp, ns, dp);
*qp.offset((ns - 2) as isize) = qhl;
*rp = *np_tmp;
*rp.offset(1) = *np_tmp.offset(1);
} else {
let dtmp = [*dp << cnt, (*dp.offset(1) << cnt) | *dp >> (Limb::BITS - cnt)];
let dp_tmp = Limbs::new(&dtmp[0], 0, dtmp.len() as i32);
let np_tmp = tmp.allocate((ns + 1) as usize);
let c = ll::shl(np_tmp, np, ns, cnt as u32);
*np_tmp.offset(ns as isize) = c;
let ns_tmp = ns + if c == 0 { 0 } else { 1 };
let qhl = divrem_2(qp, 0, np_tmp, ns_tmp, dp_tmp);
if c == 0 {
*qp.offset((ns - 2) as isize) = qhl;
}
*rp = (*np_tmp >> cnt) | (*np_tmp.offset(1) << Limb::BITS - cnt);
*rp.offset(1) = *np_tmp.offset(1) >> cnt;
}
return;
}
_ => {
let mut tmp = mem::TmpAllocator::new();
let dh = *dp.offset((ds - 1) as isize);
let cnt = dh.leading_zeros() as u32;
let dp_tmp;
let np_tmp;
let mut ns_tmp = ns;
if cnt == 0 {
dp_tmp = dp;
np_tmp = tmp.allocate(ns_tmp as usize);
ll::copy_incr(np, np_tmp, ns);
} else {
ns_tmp += 1;
np_tmp = tmp.allocate(ns_tmp as usize);
let c = ll::shl(np_tmp, np, ns, cnt);
if c > 0 {
*np_tmp.offset(ns as isize) = c;
} else {
ns_tmp -= 1;
}
let dtmp = tmp.allocate(ds as usize);
ll::shl(dtmp, dp, ds, cnt);
dp_tmp = dtmp.as_const();
}
let dinv = invert_pi(*dp_tmp.offset((ds - 1) as isize),
*dp_tmp.offset((ds - 2) as isize));
let qh = sb_div(qp, np_tmp, ns_tmp, dp_tmp, ds, dinv);
if qh > 0 {
*qp.offset((ns - ds) as isize) = qh;
}
if cnt == 0 {
ll::copy_incr(np_tmp.as_const(), rp, ds);
} else {
ll::shr(rp, np_tmp.as_const(), ds, cnt);
}
}
}
}
unsafe fn sb_div(qp: LimbsMut,
np: LimbsMut, ns: i32,
dp: Limbs, ds: i32,
dinv: Limb) -> Limb {
debug_assert!(ds > 2);
debug_assert!(ns >= ds);
debug_assert!((*dp.offset((ds - 1) as isize)).high_bit_set());
let mut np = np.offset(ns as isize);
let qh = if let Ordering::Less = ll::cmp(np.offset(-ds as isize).as_const(), dp, ds) {
Limb(0)
} else {
let np = np.offset(-ds as isize);
ll::sub_n(np, np.as_const(), dp, ds);
Limb(1)
};
let mut qp = qp.offset((ns - ds) as isize);
let ds = (ds - 2) as isize;
let d1 = *dp.offset(ds + 1);
let d0 = *dp.offset(ds + 0);
np = np.offset(-2);
let mut n2 = *np.offset(1);
let mut i = ns - (ds + 2) as i32;
while i > 0 {
np = np.offset(-1);
let n1 = *np.offset(1);
let n0 = *np;
let q = if n2 == d1 && n1 == d0 {
ll::submul_1(np.offset(-ds), dp, (ds + 2) as i32, Limb(!0));
n2 = *np.offset(1);
Limb(!0)
} else {
let (q, r1, mut r0) = divrem_3by2(n2, n1, n0, d1, d0, dinv);
let cy = ll::submul_1(np.offset(-ds), dp, ds as i32, q);
n2 = r1;
let cy1 = r0 < cy;
r0 = r0 - cy;
let cy = n2 < (cy1 as ll::limb::BaseInt);
if cy1 {
n2 = n2 - 1;
}
*np = r0;
if cy {
n2 = d1 + n2 + ll::add_n(np.offset(-ds), np.offset(-ds).as_const(), dp, (ds + 1) as i32);
q - 1
} else {
q
}
};
qp = qp.offset(-1);
*qp = q;
i -= 1;
}
*np.offset(1) = n2;
return qh;
}