use std::cmp::Ordering;
use std::intrinsics::abort;
mod addsub;
mod bit;
mod div;
mod gcd;
mod mul;
pub mod base;
pub mod limb;
pub mod limb_ptr;
pub mod pow;
use self::limb::Limb;
use ll::limb_ptr::{Limbs, LimbsMut};
pub use self::addsub::{add, add_1, add_n, decr, incr, sub, sub_1, sub_n};
pub use self::bit::{
and_n, and_not_n, nand_n, nor_n, not, or_n, or_not_n, scan_0, scan_1, shl, shr,
twos_complement, xor_n,
};
pub use self::div::{divrem, divrem_1, divrem_2};
pub use self::gcd::gcd;
pub use self::mul::{addmul_1, mul, mul_1, sqr, submul_1};
#[inline(always)]
pub unsafe fn overlap(xp: LimbsMut, xs: i32, yp: Limbs, ys: i32) -> bool {
xp.offset(xs as isize).as_const() > yp && yp.offset(ys as isize) > xp.as_const()
}
#[inline(always)]
pub unsafe fn same_or_separate(xp: LimbsMut, xs: i32, yp: Limbs, ys: i32) -> bool {
xp.as_const() == yp || !overlap(xp, xs, yp, ys)
}
#[inline(always)]
pub unsafe fn same_or_incr(xp: LimbsMut, xs: i32, yp: Limbs, ys: i32) -> bool {
xp.as_const() <= yp || !overlap(xp, xs, yp, ys)
}
#[inline(always)]
pub unsafe fn same_or_decr(xp: LimbsMut, xs: i32, yp: Limbs, ys: i32) -> bool {
xp.as_const() >= yp || !overlap(xp, xs, yp, ys)
}
#[inline]
pub unsafe fn copy_incr(src: Limbs, dst: LimbsMut, n: i32) {
debug_assert!(same_or_incr(dst, n, src, n));
let mut i = 0;
while i < n {
*dst.offset(i as isize) = *src.offset(i as isize);
i += 1;
}
}
#[inline]
pub unsafe fn copy_decr(src: Limbs, dst: LimbsMut, mut n: i32) {
debug_assert!(same_or_decr(dst, n, src, n));
n -= 1;
while n >= 0 {
*dst.offset(n as isize) = *src.offset(n as isize);
n -= 1;
}
}
#[inline]
pub unsafe fn copy_rest(src: Limbs, dst: LimbsMut, n: i32, start: i32) {
copy_incr(
src.offset(start as isize),
dst.offset(start as isize),
n - start,
);
}
#[inline]
pub unsafe fn normalize(p: Limbs, mut n: i32) -> i32 {
debug_assert!(n >= 0);
while n > 0 && *p.offset((n - 1) as isize) == 0 {
n -= 1;
}
return n;
}
#[cold]
#[inline(never)]
pub fn divide_by_zero() -> ! {
if cfg!(debug_assertions) {
panic!("divide by zero")
} else {
abort();
}
}
pub unsafe fn is_zero(mut np: Limbs, mut nn: i32) -> bool {
while nn > 0 {
if *np != 0 {
return false;
}
np = np.offset(1);
nn -= 1;
}
return true;
}
pub unsafe fn zero(mut np: LimbsMut, mut nn: i32) {
while nn > 0 {
*np = Limb(0);
np = np.offset(1);
nn -= 1;
}
}
pub unsafe fn cmp(xp: Limbs, yp: Limbs, n: i32) -> Ordering {
let mut i = n - 1;
while i >= 0 {
let x = *xp.offset(i as isize);
let y = *yp.offset(i as isize);
if x != y {
return if x > y {
Ordering::Greater
} else {
Ordering::Less
};
}
i -= 1;
}
Ordering::Equal
}
#[doc(hidden)]
#[allow(unused_must_use)]
#[cold]
#[inline(never)]
pub unsafe fn dump(lbl: &str, mut p: Limbs, mut n: i32) {
use std::io::{self, Write};
let stdout = io::stdout();
let mut stdout = stdout.lock();
stdout.write_all(lbl.as_bytes());
write!(stdout, ": ({})", n);
stdout.write_all(b"[\n");
let mut i = 0;
while n > 0 {
write!(stdout, "0x{:0>2X}", (*p).0);
p = p.offset(1);
n -= 1;
if n != 0 {
stdout.write_all(b", ");
}
i += 1;
if (i % 8) == 0 {
stdout.write_all(b"\n");
}
}
stdout.write_all(b"]\n");
stdout.flush();
}
#[cfg(test)]
mod test {
use super::*;
use ll::limb::Limb;
use ll::limb_ptr::{Limbs, LimbsMut};
macro_rules! make_limbs {
(const $nm:ident, $($d:expr),*) => (
{
$nm = [$(Limb($d)),*];
let len = $nm.len() as i32;
let ptr = unsafe {Limbs::new($nm.as_ptr(), 0, len)};
(ptr, len)
}
);
(out $nm:ident, $len:expr) => (
{
$nm = [Limb(0);$len];
unsafe {LimbsMut::new($nm.as_mut_ptr(), 0, $len as i32)}
}
);
}
#[test]
fn test_add() {
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, 1);
let (bp, bsz) = make_limbs!(const b, 2);
let cp = make_limbs!(out c, 1);
unsafe {
assert_eq!(add(cp, ap, asz, bp, bsz), 0);
}
assert_eq!(c[0], 3);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !0);
let (bp, bsz) = make_limbs!(const b, 5);
let cp = make_limbs!(out c, 1);
unsafe {
assert_eq!(add(cp, ap, asz, bp, bsz), 1);
}
assert_eq!(c[0], 4);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !0, 0);
let (bp, bsz) = make_limbs!(const b, 5);
let cp = make_limbs!(out c, 2);
unsafe {
assert_eq!(add(cp, ap, asz, bp, bsz), 0);
}
assert_eq!(c, [4, 1]);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !0, !9);
let (bp, bsz) = make_limbs!(const b, 5, 10);
let cp = make_limbs!(out c, 2);
unsafe {
assert_eq!(add(cp, ap, asz, bp, bsz), 1);
}
assert_eq!(c, [4, 1]);
}
#[test]
fn test_add_self() {
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, !0, !9);
let bp = make_limbs!(out b, 2);
let bsz = 2;
b[0] = Limb(5);
b[1] = Limb(10);
unsafe {
assert_eq!(add(bp, ap, asz, bp.as_const(), bsz), 1);
}
assert_eq!(b, [4, 1]);
}
#[test]
fn test_sub() {
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, 2);
let (bp, bsz) = make_limbs!(const b, 1);
let cp = make_limbs!(out c, 1);
unsafe {
assert_eq!(sub(cp, ap, asz, bp, bsz), 0);
}
assert_eq!(c[0], 1);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, 0, 2);
let (bp, bsz) = make_limbs!(const b, 1);
let cp = make_limbs!(out c, 2);
unsafe {
assert_eq!(sub(cp, ap, asz, bp, bsz), 0);
}
assert_eq!(c, [!0, 1]);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, 0, 2);
let (bp, bsz) = make_limbs!(const b, 2, 1);
let cp = make_limbs!(out c, 2);
unsafe {
assert_eq!(sub(cp, ap, asz, bp, bsz), 0);
}
assert_eq!(c, [!1, 0]);
}
#[test]
fn test_sub_self() {
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 0, 2);
let bp = make_limbs!(out b, 2);
let bsz = 2;
b[0] = Limb(2);
b[1] = Limb(1);
unsafe {
assert_eq!(sub(bp, ap, asz, bp.as_const(), bsz), 0);
}
assert_eq!(b, [!1, 0]);
}
#[test]
fn test_mul_hilo() {
let r = Limb(10).mul_hilo(Limb(20));
assert_eq!((Limb(0), Limb(200)), r);
let r = Limb(!1).mul_hilo(Limb(2));
assert_eq!((Limb(1), Limb(!3)), r);
let r = Limb(2).mul_hilo(Limb(!1));
assert_eq!((Limb(1), Limb(!3)), r);
let r = Limb(!0).mul_hilo(Limb(!0));
assert_eq!((Limb(!1), Limb(1)), r);
}
#[test]
fn test_mul_1() {
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 10);
let bp = make_limbs!(out b, 1);
unsafe {
assert_eq!(mul_1(bp, ap, asz, Limb(20)), 0);
}
assert_eq!(b, [200]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, !1);
let bp = make_limbs!(out b, 1);
unsafe {
assert_eq!(mul_1(bp, ap, asz, Limb(2)), 1);
}
assert_eq!(b, [!3]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 10, 10);
let bp = make_limbs!(out b, 2);
unsafe {
assert_eq!(mul_1(bp, ap, asz, Limb(2)), 0);
}
assert_eq!(b, [20, 20]);
}
#[test]
fn test_mul() {
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, 2);
let (bp, bsz) = make_limbs!(const b, 2);
let cp = make_limbs!(out c, 2);
unsafe {
mul(cp, ap, asz, bp, bsz);
}
assert_eq!(c, [4, 0]);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !1);
let (bp, bsz) = make_limbs!(const b, 2);
let cp = make_limbs!(out c, 2);
unsafe {
mul(cp, ap, asz, bp, bsz);
}
assert_eq!(c, [!3, 1]);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !1, 1);
let (bp, bsz) = make_limbs!(const b, 4);
let cp = make_limbs!(out c, 3);
unsafe {
mul(cp, ap, asz, bp, bsz);
}
assert_eq!(c, [!7, 7, 0]);
let a;
let b;
let mut c;
let (ap, asz) = make_limbs!(const a, !1, 1);
let (bp, bsz) = make_limbs!(const b, 0, 1);
let cp = make_limbs!(out c, 4);
unsafe {
mul(cp, ap, asz, bp, bsz);
}
assert_eq!(c, [0, !1, 1, 0]);
}
#[test]
fn test_mul_large() {
let a;
let b;
let mut c;
let expected: [Limb; 73] = unsafe {
::std::mem::transmute((
Limb(1),
[Limb(0); 29],
[Limb(!0); 13],
Limb(!1),
[Limb(!0); 29],
))
};
a = [Limb(!0); 43];
b = [Limb(!0); 30];
c = [Limb(0); 73];
unsafe {
let ap = Limbs::new(&a[0], 0, a.len() as i32);
let bp = Limbs::new(&b[0], 0, b.len() as i32);
let cp = LimbsMut::new(&mut c[0], 0, c.len() as i32);
mul(cp, ap, 43, bp, 30);
}
let ep: &[Limb] = &expected;
let cp: &[Limb] = &c;
assert_eq!(cp, ep);
let a;
let b;
let mut c;
let expected: [Limb; 150] = unsafe {
::std::mem::transmute((
Limb(1),
[Limb(0); 25],
[Limb(!0); 98],
Limb(!1),
[Limb(!0); 25],
))
};
a = [Limb(!0); 124];
b = [Limb(!0); 26];
c = [Limb(0); 150];
unsafe {
let ap = Limbs::new(&a[0], 0, a.len() as i32);
let bp = Limbs::new(&b[0], 0, b.len() as i32);
let cp = LimbsMut::new(&mut c[0], 0, c.len() as i32);
mul(cp, ap, 124, bp, 26);
}
let ep: &[Limb] = &expected;
let cp: &[Limb] = &c;
assert_eq!(cp, ep);
}
#[test]
fn test_divrem_1() {
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 2);
let bp = make_limbs!(out b, 1);
unsafe {
assert_eq!(divrem_1(bp, 0, ap, asz, Limb(2)), 0);
}
assert_eq!(b, [1]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 7);
let bp = make_limbs!(out b, 1);
unsafe {
assert_eq!(divrem_1(bp, 0, ap, asz, Limb(1)), 0);
}
assert_eq!(b, [7]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 7);
let bp = make_limbs!(out b, 1);
unsafe {
assert_eq!(divrem_1(bp, 0, ap, asz, Limb(2)), 1);
}
assert_eq!(b, [3]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 0, 1);
let bp = make_limbs!(out b, 2);
unsafe {
assert_eq!(divrem_1(bp, 0, ap, asz, Limb(4)), 0);
}
assert_eq!(b, [1 << (Limb::BITS - 2), 0 as limb::BaseInt]);
let a;
let mut b;
let (ap, asz) = make_limbs!(const a, 5);
let bp = make_limbs!(out b, 2);
unsafe {
assert_eq!(divrem_1(bp, 1, ap, asz, Limb(2)), 0);
}
assert_eq!(b, [1 << (Limb::BITS - 1), 2 as limb::BaseInt]);
}
#[test]
fn test_divrem() {
let a;
let b;
let mut q;
let mut r;
let (ap, asz) = make_limbs!(const a, 4, 3, 4);
let (bp, bsz) = make_limbs!(const b, 1, !0);
let qp = make_limbs!(out q, 2);
let rp = make_limbs!(out r, 2);
unsafe {
divrem(qp, rp, ap, asz, bp, bsz);
}
assert_eq!(q, [4, 0]);
assert_eq!(r, [0, 7]);
let a;
let b;
let mut q;
let mut r;
let (ap, asz) = make_limbs!(const a, 0, 4, 3, 4, 2);
let (bp, bsz) = make_limbs!(const b, 0, !1);
let qp = make_limbs!(out q, 4);
let rp = make_limbs!(out r, 2);
unsafe {
divrem(qp, rp, ap, asz, bp, bsz);
}
assert_eq!(q, [19, 8, 2, 0]);
assert_eq!(r, [0, 42]);
let a;
let b;
let mut q;
let mut r;
let (ap, asz) = make_limbs!(const a, 8, 1, 3, 4, 1);
let (bp, bsz) = make_limbs!(const b, 0, 1);
let qp = make_limbs!(out q, 4);
let rp = make_limbs!(out r, 2);
unsafe {
divrem(qp, rp, ap, asz, bp, bsz);
}
assert_eq!(q, [1, 3, 4, 1]);
assert_eq!(r, [8, 0]);
{
let a;
let b;
let mut q;
let mut r;
let (ap, asz) = make_limbs!(const a, 1, 0, 0, 0, !0, !0, !0, !0, !1, !0, !0, !0);
let (bp, bsz) = make_limbs!(const b, !0, !0, !0, !0);
let qp = make_limbs!(out q, 9);
let rp = make_limbs!(out r, 4);
unsafe {
divrem(qp, rp, ap, asz, bp, bsz);
}
assert_eq!(q, [!0, !0, !0, !0, !0, !0, !0, !0, 0]);
assert_eq!(r, [0, 0, 0, 0]);
}
}
#[test]
fn test_bitscan() {
let a;
let (ap, asz) = make_limbs!(const a, 256);
let pos = unsafe { scan_1(ap, asz) };
assert_eq!(pos, 8);
let a;
let (ap, asz) = make_limbs!(const a, 0, 256);
let pos = unsafe { scan_1(ap, asz) };
assert_eq!(pos, Limb::BITS as u32 + 8);
let a;
let (ap, asz) = make_limbs!(const a, !256);
let pos = unsafe { scan_0(ap, asz) };
assert_eq!(pos, 8);
let a;
let (ap, asz) = make_limbs!(const a, !0, !256);
let pos = unsafe { scan_0(ap, asz) };
assert_eq!(pos, Limb::BITS as u32 + 8);
}
}