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 {
data(&self) -> &Vec<Limb>12 fn data(&self) -> &Vec<Limb> {
13 &self.data
14 }
15
data_mut(&mut self) -> &mut Vec<Limb>16 fn data_mut(&mut self) -> &mut Vec<Limb> {
17 &mut self.data
18 }
19 }
20
21 #[cfg(limb_width_32)]
from_u32(x: &[u32]) -> Vec<Limb>22 pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> {
23 x.iter().cloned().collect()
24 }
25
26 #[cfg(limb_width_64)]
from_u32(x: &[u32]) -> Vec<Limb>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]
compare_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]
hi64_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]
bit_length_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]
iadd_small_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]
imul_small_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]
shl_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 }
212