Source code
Revision control
Copy as Markdown
Other Tools
use crate::lexical::math::{Limb, Math};
use std::cmp;
#[derive(Clone, Default)]
struct Bigint {
data: Vec<Limb>,
}
impl Math for Bigint {
fn data(&self) -> &Vec<Limb> {
&self.data
}
fn data_mut(&mut self) -> &mut Vec<Limb> {
&mut self.data
}
}
#[cfg(limb_width_32)]
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> {
x.iter().cloned().collect()
}
#[cfg(limb_width_64)]
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> {
let mut v = Vec::<Limb>::default();
for xi in x.chunks(2) {
match xi.len() {
1 => v.push(xi[0] as u64),
2 => v.push(((xi[1] as u64) << 32) | (xi[0] as u64)),
_ => unreachable!(),
}
}
v
}
#[test]
fn compare_test() {
// Simple
let x = Bigint {
data: from_u32(&[1]),
};
let y = Bigint {
data: from_u32(&[2]),
};
assert_eq!(x.compare(&y), cmp::Ordering::Less);
assert_eq!(x.compare(&x), cmp::Ordering::Equal);
assert_eq!(y.compare(&x), cmp::Ordering::Greater);
// Check asymmetric
let x = Bigint {
data: from_u32(&[5, 1]),
};
let y = Bigint {
data: from_u32(&[2]),
};
assert_eq!(x.compare(&y), cmp::Ordering::Greater);
assert_eq!(x.compare(&x), cmp::Ordering::Equal);
assert_eq!(y.compare(&x), cmp::Ordering::Less);
// Check when we use reverse ordering properly.
let x = Bigint {
data: from_u32(&[5, 1, 9]),
};
let y = Bigint {
data: from_u32(&[6, 2, 8]),
};
assert_eq!(x.compare(&y), cmp::Ordering::Greater);
assert_eq!(x.compare(&x), cmp::Ordering::Equal);
assert_eq!(y.compare(&x), cmp::Ordering::Less);
// Complex scenario, check it properly uses reverse ordering.
let x = Bigint {
data: from_u32(&[0, 1, 9]),
};
let y = Bigint {
data: from_u32(&[4294967295, 0, 9]),
};
assert_eq!(x.compare(&y), cmp::Ordering::Greater);
assert_eq!(x.compare(&x), cmp::Ordering::Equal);
assert_eq!(y.compare(&x), cmp::Ordering::Less);
}
#[test]
fn hi64_test() {
assert_eq!(Bigint::from_u64(0xA).hi64(), (0xA000000000000000, false));
assert_eq!(Bigint::from_u64(0xAB).hi64(), (0xAB00000000000000, false));
assert_eq!(
Bigint::from_u64(0xAB00000000).hi64(),
(0xAB00000000000000, false)
);
assert_eq!(
Bigint::from_u64(0xA23456789A).hi64(),
(0xA23456789A000000, false)
);
}
#[test]
fn bit_length_test() {
let x = Bigint {
data: from_u32(&[0, 0, 0, 1]),
};
assert_eq!(x.bit_length(), 97);
let x = Bigint {
data: from_u32(&[0, 0, 0, 3]),
};
assert_eq!(x.bit_length(), 98);
let x = Bigint {
data: from_u32(&[1 << 31]),
};
assert_eq!(x.bit_length(), 32);
}
#[test]
fn iadd_small_test() {
// Overflow check (single)
// This should set all the internal data values to 0, the top
// value to (1<<31), and the bottom value to (4>>1).
// This is because the max_value + 1 leads to all 0s, we set the
// topmost bit to 1.
let mut x = Bigint {
data: from_u32(&[4294967295]),
};
x.iadd_small(5);
assert_eq!(x.data, from_u32(&[4, 1]));
// No overflow, single value
let mut x = Bigint {
data: from_u32(&[5]),
};
x.iadd_small(7);
assert_eq!(x.data, from_u32(&[12]));
// Single carry, internal overflow
let mut x = Bigint::from_u64(0x80000000FFFFFFFF);
x.iadd_small(7);
assert_eq!(x.data, from_u32(&[6, 0x80000001]));
// Double carry, overflow
let mut x = Bigint::from_u64(0xFFFFFFFFFFFFFFFF);
x.iadd_small(7);
assert_eq!(x.data, from_u32(&[6, 0, 1]));
}
#[test]
fn imul_small_test() {
// No overflow check, 1-int.
let mut x = Bigint {
data: from_u32(&[5]),
};
x.imul_small(7);
assert_eq!(x.data, from_u32(&[35]));
// No overflow check, 2-ints.
let mut x = Bigint::from_u64(0x4000000040000);
x.imul_small(5);
assert_eq!(x.data, from_u32(&[0x00140000, 0x140000]));
// Overflow, 1 carry.
let mut x = Bigint {
data: from_u32(&[0x33333334]),
};
x.imul_small(5);
assert_eq!(x.data, from_u32(&[4, 1]));
// Overflow, 1 carry, internal.
let mut x = Bigint::from_u64(0x133333334);
x.imul_small(5);
assert_eq!(x.data, from_u32(&[4, 6]));
// Overflow, 2 carries.
let mut x = Bigint::from_u64(0x3333333333333334);
x.imul_small(5);
assert_eq!(x.data, from_u32(&[4, 0, 1]));
}
#[test]
fn shl_test() {
// Pattern generated via `''.join(["1" +"0"*i for i in range(20)])`
let mut big = Bigint {
data: from_u32(&[0xD2210408]),
};
big.ishl(5);
assert_eq!(big.data, from_u32(&[0x44208100, 0x1A]));
big.ishl(32);
assert_eq!(big.data, from_u32(&[0, 0x44208100, 0x1A]));
big.ishl(27);
assert_eq!(big.data, from_u32(&[0, 0, 0xD2210408]));
// 96-bits of previous pattern
let mut big = Bigint {
data: from_u32(&[0x20020010, 0x8040100, 0xD2210408]),
};
big.ishl(5);
assert_eq!(big.data, from_u32(&[0x400200, 0x802004, 0x44208101, 0x1A]));
big.ishl(32);
assert_eq!(
big.data,
from_u32(&[0, 0x400200, 0x802004, 0x44208101, 0x1A])
);
big.ishl(27);
assert_eq!(
big.data,
from_u32(&[0, 0, 0x20020010, 0x8040100, 0xD2210408])
);
}