| 1 |
// Adapted from https://github.com/Alexhuszagh/rust-lexical. |
| 2 |
|
| 3 |
use crate::lexical::math::{Limb, Math}; |
| 4 |
use std::cmp; |
| 5 |
|
| 6 |
#[derive(Clone, Default)] |
| 7 |
struct Bigint { |
| 8 |
data: Vec<Limb>, |
| 9 |
} |
| 10 |
|
| 11 |
impl Math for Bigint { |
| 12 |
fn data(&self) -> &Vec<Limb> { |
| 13 |
&self.data |
| 14 |
} |
| 15 |
|
| 16 |
fn data_mut(&mut self) -> &mut Vec<Limb> { |
| 17 |
&mut self.data |
| 18 |
} |
| 19 |
} |
| 20 |
|
| 21 |
#[cfg(limb_width_32)] |
| 22 |
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> { |
| 23 |
x.iter().cloned().collect() |
| 24 |
} |
| 25 |
|
| 26 |
#[cfg(limb_width_64)] |
| 27 |
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> { |
| 28 |
let mut v = Vec::<Limb>::default(); |
| 29 |
for xi in x.chunks(2) { |
| 30 |
match xi.len() { |
| 31 |
1 => v.push(xi[0] as u64), |
| 32 |
2 => v.push(((xi[1] as u64) << 32) | (xi[0] as u64)), |
| 33 |
_ => unreachable!(), |
| 34 |
} |
| 35 |
} |
| 36 |
|
| 37 |
v |
| 38 |
} |
| 39 |
|
| 40 |
#[test] |
| 41 |
fn compare_test() { |
| 42 |
// Simple |
| 43 |
let x = Bigint { |
| 44 |
data: from_u32(&[1]), |
| 45 |
}; |
| 46 |
let y = Bigint { |
| 47 |
data: from_u32(&[2]), |
| 48 |
}; |
| 49 |
assert_eq!(x.compare(&y), cmp::Ordering::Less); |
| 50 |
assert_eq!(x.compare(&x), cmp::Ordering::Equal); |
| 51 |
assert_eq!(y.compare(&x), cmp::Ordering::Greater); |
| 52 |
|
| 53 |
// Check asymmetric |
| 54 |
let x = Bigint { |
| 55 |
data: from_u32(&[5, 1]), |
| 56 |
}; |
| 57 |
let y = Bigint { |
| 58 |
data: from_u32(&[2]), |
| 59 |
}; |
| 60 |
assert_eq!(x.compare(&y), cmp::Ordering::Greater); |
| 61 |
assert_eq!(x.compare(&x), cmp::Ordering::Equal); |
| 62 |
assert_eq!(y.compare(&x), cmp::Ordering::Less); |
| 63 |
|
| 64 |
// Check when we use reverse ordering properly. |
| 65 |
let x = Bigint { |
| 66 |
data: from_u32(&[5, 1, 9]), |
| 67 |
}; |
| 68 |
let y = Bigint { |
| 69 |
data: from_u32(&[6, 2, 8]), |
| 70 |
}; |
| 71 |
assert_eq!(x.compare(&y), cmp::Ordering::Greater); |
| 72 |
assert_eq!(x.compare(&x), cmp::Ordering::Equal); |
| 73 |
assert_eq!(y.compare(&x), cmp::Ordering::Less); |
| 74 |
|
| 75 |
// Complex scenario, check it properly uses reverse ordering. |
| 76 |
let x = Bigint { |
| 77 |
data: from_u32(&[0, 1, 9]), |
| 78 |
}; |
| 79 |
let y = Bigint { |
| 80 |
data: from_u32(&[4294967295, 0, 9]), |
| 81 |
}; |
| 82 |
assert_eq!(x.compare(&y), cmp::Ordering::Greater); |
| 83 |
assert_eq!(x.compare(&x), cmp::Ordering::Equal); |
| 84 |
assert_eq!(y.compare(&x), cmp::Ordering::Less); |
| 85 |
} |
| 86 |
|
| 87 |
#[test] |
| 88 |
fn hi64_test() { |
| 89 |
assert_eq!(Bigint::from_u64(0xA).hi64(), (0xA000000000000000, false)); |
| 90 |
assert_eq!(Bigint::from_u64(0xAB).hi64(), (0xAB00000000000000, false)); |
| 91 |
assert_eq!( |
| 92 |
Bigint::from_u64(0xAB00000000).hi64(), |
| 93 |
(0xAB00000000000000, false) |
| 94 |
); |
| 95 |
assert_eq!( |
| 96 |
Bigint::from_u64(0xA23456789A).hi64(), |
| 97 |
(0xA23456789A000000, false) |
| 98 |
); |
| 99 |
} |
| 100 |
|
| 101 |
#[test] |
| 102 |
fn bit_length_test() { |
| 103 |
let x = Bigint { |
| 104 |
data: from_u32(&[0, 0, 0, 1]), |
| 105 |
}; |
| 106 |
assert_eq!(x.bit_length(), 97); |
| 107 |
|
| 108 |
let x = Bigint { |
| 109 |
data: from_u32(&[0, 0, 0, 3]), |
| 110 |
}; |
| 111 |
assert_eq!(x.bit_length(), 98); |
| 112 |
|
| 113 |
let x = Bigint { |
| 114 |
data: from_u32(&[1 << 31]), |
| 115 |
}; |
| 116 |
assert_eq!(x.bit_length(), 32); |
| 117 |
} |
| 118 |
|
| 119 |
#[test] |
| 120 |
fn iadd_small_test() { |
| 121 |
// Overflow check (single) |
| 122 |
// This should set all the internal data values to 0, the top |
| 123 |
// value to (1<<31), and the bottom value to (4>>1). |
| 124 |
// This is because the max_value + 1 leads to all 0s, we set the |
| 125 |
// topmost bit to 1. |
| 126 |
let mut x = Bigint { |
| 127 |
data: from_u32(&[4294967295]), |
| 128 |
}; |
| 129 |
x.iadd_small(5); |
| 130 |
assert_eq!(x.data, from_u32(&[4, 1])); |
| 131 |
|
| 132 |
// No overflow, single value |
| 133 |
let mut x = Bigint { |
| 134 |
data: from_u32(&[5]), |
| 135 |
}; |
| 136 |
x.iadd_small(7); |
| 137 |
assert_eq!(x.data, from_u32(&[12])); |
| 138 |
|
| 139 |
// Single carry, internal overflow |
| 140 |
let mut x = Bigint::from_u64(0x80000000FFFFFFFF); |
| 141 |
x.iadd_small(7); |
| 142 |
assert_eq!(x.data, from_u32(&[6, 0x80000001])); |
| 143 |
|
| 144 |
// Double carry, overflow |
| 145 |
let mut x = Bigint::from_u64(0xFFFFFFFFFFFFFFFF); |
| 146 |
x.iadd_small(7); |
| 147 |
assert_eq!(x.data, from_u32(&[6, 0, 1])); |
| 148 |
} |
| 149 |
|
| 150 |
#[test] |
| 151 |
fn imul_small_test() { |
| 152 |
// No overflow check, 1-int. |
| 153 |
let mut x = Bigint { |
| 154 |
data: from_u32(&[5]), |
| 155 |
}; |
| 156 |
x.imul_small(7); |
| 157 |
assert_eq!(x.data, from_u32(&[35])); |
| 158 |
|
| 159 |
// No overflow check, 2-ints. |
| 160 |
let mut x = Bigint::from_u64(0x4000000040000); |
| 161 |
x.imul_small(5); |
| 162 |
assert_eq!(x.data, from_u32(&[0x00140000, 0x140000])); |
| 163 |
|
| 164 |
// Overflow, 1 carry. |
| 165 |
let mut x = Bigint { |
| 166 |
data: from_u32(&[0x33333334]), |
| 167 |
}; |
| 168 |
x.imul_small(5); |
| 169 |
assert_eq!(x.data, from_u32(&[4, 1])); |
| 170 |
|
| 171 |
// Overflow, 1 carry, internal. |
| 172 |
let mut x = Bigint::from_u64(0x133333334); |
| 173 |
x.imul_small(5); |
| 174 |
assert_eq!(x.data, from_u32(&[4, 6])); |
| 175 |
|
| 176 |
// Overflow, 2 carries. |
| 177 |
let mut x = Bigint::from_u64(0x3333333333333334); |
| 178 |
x.imul_small(5); |
| 179 |
assert_eq!(x.data, from_u32(&[4, 0, 1])); |
| 180 |
} |
| 181 |
|
| 182 |
#[test] |
| 183 |
fn shl_test() { |
| 184 |
// Pattern generated via `''.join(["1" +"0"*i for i in range(20)])` |
| 185 |
let mut big = Bigint { |
| 186 |
data: from_u32(&[0xD2210408]), |
| 187 |
}; |
| 188 |
big.ishl(5); |
| 189 |
assert_eq!(big.data, from_u32(&[0x44208100, 0x1A])); |
| 190 |
big.ishl(32); |
| 191 |
assert_eq!(big.data, from_u32(&[0, 0x44208100, 0x1A])); |
| 192 |
big.ishl(27); |
| 193 |
assert_eq!(big.data, from_u32(&[0, 0, 0xD2210408])); |
| 194 |
|
| 195 |
// 96-bits of previous pattern |
| 196 |
let mut big = Bigint { |
| 197 |
data: from_u32(&[0x20020010, 0x8040100, 0xD2210408]), |
| 198 |
}; |
| 199 |
big.ishl(5); |
| 200 |
assert_eq!(big.data, from_u32(&[0x400200, 0x802004, 0x44208101, 0x1A])); |
| 201 |
big.ishl(32); |
| 202 |
assert_eq!( |
| 203 |
big.data, |
| 204 |
from_u32(&[0, 0x400200, 0x802004, 0x44208101, 0x1A]) |
| 205 |
); |
| 206 |
big.ishl(27); |
| 207 |
assert_eq!( |
| 208 |
big.data, |
| 209 |
from_u32(&[0, 0, 0x20020010, 0x8040100, 0xD2210408]) |
| 210 |
); |
| 211 |
} |