1 mod stackvec;
2
3 use core::cmp;
4 use minimal_lexical::bigint;
5 use stackvec::{vec_from_u32, VecType};
6
7 // u64::MAX and Limb::MAX for older Rustc versions.
8 const U64_MAX: u64 = 0xffff_ffff_ffff_ffff;
9 // LIMB_MAX
10 #[cfg(all(target_pointer_width = "64", not(target_arch = "sparc")))]
11 const LIMB_MAX: u64 = U64_MAX;
12 #[cfg(not(all(target_pointer_width = "64", not(target_arch = "sparc"))))]
13 const LIMB_MAX: u32 = 0xffff_ffff;
14
15 #[test]
simple_test()16 fn simple_test() {
17 // Test the simple properties of the stack vector.
18 let mut x = VecType::from_u64(1);
19 assert_eq!(x.len(), 1);
20 assert_eq!(x.is_empty(), false);
21 assert_eq!(x.capacity(), bigint::BIGINT_LIMBS);
22 x.try_push(5).unwrap();
23 assert_eq!(x.len(), 2);
24 assert_eq!(x.pop(), Some(5));
25 assert_eq!(x.len(), 1);
26 assert_eq!(&*x, &[1]);
27 x.try_extend(&[2, 3, 4]).unwrap();
28 assert_eq!(x.len(), 4);
29 assert_eq!(&*x, &[1, 2, 3, 4]);
30 x.try_resize(6, 0).unwrap();
31 assert_eq!(x.len(), 6);
32 assert_eq!(&*x, &[1, 2, 3, 4, 0, 0]);
33 x.try_resize(0, 0).unwrap();
34 assert_eq!(x.len(), 0);
35 assert_eq!(x.is_empty(), true);
36
37 let x = VecType::try_from(&[5, 1]).unwrap();
38 assert_eq!(x.len(), 2);
39 assert_eq!(x.is_empty(), false);
40 if bigint::LIMB_BITS == 32 {
41 assert_eq!(x.hi64(), (0x8000000280000000, false));
42 } else {
43 assert_eq!(x.hi64(), (0x8000000000000002, true));
44 }
45 let rview = bigint::rview(&x);
46 assert_eq!(x[0], 5);
47 assert_eq!(x[1], 1);
48 assert_eq!(rview[0], 1);
49 assert_eq!(rview[1], 5);
50 assert_eq!(x.len(), 2);
51
52 assert_eq!(VecType::from_u64(U64_MAX).hi64(), (U64_MAX, false));
53 }
54
55 #[test]
hi64_test()56 fn hi64_test() {
57 assert_eq!(VecType::from_u64(0xA).hi64(), (0xA000000000000000, false));
58 assert_eq!(VecType::from_u64(0xAB).hi64(), (0xAB00000000000000, false));
59 assert_eq!(VecType::from_u64(0xAB00000000).hi64(), (0xAB00000000000000, false));
60 assert_eq!(VecType::from_u64(0xA23456789A).hi64(), (0xA23456789A000000, false));
61 }
62
63 #[test]
cmp_test()64 fn cmp_test() {
65 // Simple
66 let x = VecType::from_u64(1);
67 let y = VecType::from_u64(2);
68 assert_eq!(x.partial_cmp(&x), Some(cmp::Ordering::Equal));
69 assert_eq!(x.cmp(&x), cmp::Ordering::Equal);
70 assert_eq!(x.cmp(&y), cmp::Ordering::Less);
71
72 // Check asymmetric
73 let x = VecType::try_from(&[5, 1]).unwrap();
74 let y = VecType::from_u64(2);
75 assert_eq!(x.cmp(&x), cmp::Ordering::Equal);
76 assert_eq!(x.cmp(&y), cmp::Ordering::Greater);
77
78 // Check when we use reverse ordering properly.
79 let x = VecType::try_from(&[5, 1, 9]).unwrap();
80 let y = VecType::try_from(&[6, 2, 8]).unwrap();
81 assert_eq!(x.cmp(&x), cmp::Ordering::Equal);
82 assert_eq!(x.cmp(&y), cmp::Ordering::Greater);
83
84 // Complex scenario, check it properly uses reverse ordering.
85 let x = VecType::try_from(&[0, 1, 9]).unwrap();
86 let y = VecType::try_from(&[4294967295, 0, 9]).unwrap();
87 assert_eq!(x.cmp(&x), cmp::Ordering::Equal);
88 assert_eq!(x.cmp(&y), cmp::Ordering::Greater);
89 }
90
91 #[test]
math_test()92 fn math_test() {
93 let mut x = VecType::try_from(&[0, 1, 9]).unwrap();
94 assert_eq!(x.is_normalized(), true);
95 x.try_push(0).unwrap();
96 assert_eq!(&*x, &[0, 1, 9, 0]);
97 assert_eq!(x.is_normalized(), false);
98 x.normalize();
99 assert_eq!(&*x, &[0, 1, 9]);
100 assert_eq!(x.is_normalized(), true);
101
102 x.add_small(1);
103 assert_eq!(&*x, &[1, 1, 9]);
104 x.add_small(LIMB_MAX);
105 assert_eq!(&*x, &[0, 2, 9]);
106
107 x.mul_small(3);
108 assert_eq!(&*x, &[0, 6, 27]);
109 x.mul_small(LIMB_MAX);
110 let expected: VecType = if bigint::LIMB_BITS == 32 {
111 vec_from_u32(&[0, 4294967290, 4294967274, 26])
112 } else {
113 vec_from_u32(&[0, 0, 4294967290, 4294967295, 4294967274, 4294967295, 26])
114 };
115 assert_eq!(&*x, &*expected);
116
117 let mut x = VecType::from_u64(0xFFFFFFFF);
118 let y = VecType::from_u64(5);
119 x *= &y;
120 let expected: VecType = vec_from_u32(&[0xFFFFFFFB, 0x4]);
121 assert_eq!(&*x, &*expected);
122
123 // Test with carry
124 let mut x = VecType::from_u64(1);
125 assert_eq!(&*x, &[1]);
126 x.add_small(LIMB_MAX);
127 assert_eq!(&*x, &[0, 1]);
128 }
129
130 #[test]
scalar_add_test()131 fn scalar_add_test() {
132 assert_eq!(bigint::scalar_add(5, 5), (10, false));
133 assert_eq!(bigint::scalar_add(LIMB_MAX, 1), (0, true));
134 }
135
136 #[test]
scalar_mul_test()137 fn scalar_mul_test() {
138 assert_eq!(bigint::scalar_mul(5, 5, 0), (25, 0));
139 assert_eq!(bigint::scalar_mul(5, 5, 1), (26, 0));
140 assert_eq!(bigint::scalar_mul(LIMB_MAX, 2, 0), (LIMB_MAX - 1, 1));
141 }
142
143 #[test]
small_add_test()144 fn small_add_test() {
145 let mut x = VecType::from_u64(4294967295);
146 bigint::small_add(&mut x, 5);
147 let expected: VecType = vec_from_u32(&[4, 1]);
148 assert_eq!(&*x, &*expected);
149
150 let mut x = VecType::from_u64(5);
151 bigint::small_add(&mut x, 7);
152 let expected = VecType::from_u64(12);
153 assert_eq!(&*x, &*expected);
154
155 // Single carry, internal overflow
156 let mut x = VecType::from_u64(0x80000000FFFFFFFF);
157 bigint::small_add(&mut x, 7);
158 let expected: VecType = vec_from_u32(&[6, 0x80000001]);
159 assert_eq!(&*x, &*expected);
160
161 // Double carry, overflow
162 let mut x = VecType::from_u64(0xFFFFFFFFFFFFFFFF);
163 bigint::small_add(&mut x, 7);
164 let expected: VecType = vec_from_u32(&[6, 0, 1]);
165 assert_eq!(&*x, &*expected);
166 }
167
168 #[test]
small_mul_test()169 fn small_mul_test() {
170 // No overflow check, 1-int.
171 let mut x = VecType::from_u64(5);
172 bigint::small_mul(&mut x, 7);
173 let expected = VecType::from_u64(35);
174 assert_eq!(&*x, &*expected);
175
176 // No overflow check, 2-ints.
177 let mut x = VecType::from_u64(0x4000000040000);
178 bigint::small_mul(&mut x, 5);
179 let expected: VecType = vec_from_u32(&[0x00140000, 0x140000]);
180 assert_eq!(&*x, &*expected);
181
182 // Overflow, 1 carry.
183 let mut x = VecType::from_u64(0x33333334);
184 bigint::small_mul(&mut x, 5);
185 let expected: VecType = vec_from_u32(&[4, 1]);
186 assert_eq!(&*x, &*expected);
187
188 // Overflow, 1 carry, internal.
189 let mut x = VecType::from_u64(0x133333334);
190 bigint::small_mul(&mut x, 5);
191 let expected: VecType = vec_from_u32(&[4, 6]);
192 assert_eq!(&*x, &*expected);
193
194 // Overflow, 2 carries.
195 let mut x = VecType::from_u64(0x3333333333333334);
196 bigint::small_mul(&mut x, 5);
197 let expected: VecType = vec_from_u32(&[4, 0, 1]);
198 assert_eq!(&*x, &*expected);
199 }
200
201 #[test]
pow_test()202 fn pow_test() {
203 let mut x = VecType::from_u64(1);
204 bigint::pow(&mut x, 2);
205 let expected = VecType::from_u64(25);
206 assert_eq!(&*x, &*expected);
207
208 let mut x = VecType::from_u64(1);
209 bigint::pow(&mut x, 15);
210 let expected: VecType = vec_from_u32(&[452807053, 7]);
211 assert_eq!(&*x, &*expected);
212
213 let mut x = VecType::from_u64(1);
214 bigint::pow(&mut x, 16);
215 let expected: VecType = vec_from_u32(&[2264035265, 35]);
216 assert_eq!(&*x, &*expected);
217
218 let mut x = VecType::from_u64(1);
219 bigint::pow(&mut x, 17);
220 let expected: VecType = vec_from_u32(&[2730241733, 177]);
221 assert_eq!(&*x, &*expected);
222
223 let mut x = VecType::from_u64(1);
224 bigint::pow(&mut x, 302);
225 let expected: VecType = vec_from_u32(&[
226 2443090281, 2149694430, 2297493928, 1584384001, 1279504719, 1930002239, 3312868939,
227 3735173465, 3523274756, 2025818732, 1641675015, 2431239749, 4292780461, 3719612855,
228 4174476133, 3296847770, 2677357556, 638848153, 2198928114, 3285049351, 2159526706,
229 626302612,
230 ]);
231 assert_eq!(&*x, &*expected);
232 }
233
234 #[test]
large_add_test()235 fn large_add_test() {
236 // Overflow, both single values
237 let mut x = VecType::from_u64(4294967295);
238 let y = VecType::from_u64(5);
239 bigint::large_add(&mut x, &y);
240 let expected: VecType = vec_from_u32(&[4, 1]);
241 assert_eq!(&*x, &*expected);
242
243 // No overflow, single value
244 let mut x = VecType::from_u64(5);
245 let y = VecType::from_u64(7);
246 bigint::large_add(&mut x, &y);
247 let expected = VecType::from_u64(12);
248 assert_eq!(&*x, &*expected);
249
250 // Single carry, internal overflow
251 let mut x = VecType::from_u64(0x80000000FFFFFFFF);
252 let y = VecType::from_u64(7);
253 bigint::large_add(&mut x, &y);
254 let expected: VecType = vec_from_u32(&[6, 0x80000001]);
255 assert_eq!(&*x, &*expected);
256
257 // 1st overflows, 2nd doesn't.
258 let mut x = VecType::from_u64(0x7FFFFFFFFFFFFFFF);
259 let y = VecType::from_u64(0x7FFFFFFFFFFFFFFF);
260 bigint::large_add(&mut x, &y);
261 let expected: VecType = vec_from_u32(&[0xFFFFFFFE, 0xFFFFFFFF]);
262 assert_eq!(&*x, &*expected);
263
264 // Both overflow.
265 let mut x = VecType::from_u64(0x8FFFFFFFFFFFFFFF);
266 let y = VecType::from_u64(0x7FFFFFFFFFFFFFFF);
267 bigint::large_add(&mut x, &y);
268 let expected: VecType = vec_from_u32(&[0xFFFFFFFE, 0x0FFFFFFF, 1]);
269 assert_eq!(&*x, &*expected);
270 }
271
272 #[test]
large_mul_test()273 fn large_mul_test() {
274 // Test by empty
275 let mut x = VecType::from_u64(0xFFFFFFFF);
276 let y = VecType::new();
277 bigint::large_mul(&mut x, &y);
278 let expected = VecType::new();
279 assert_eq!(&*x, &*expected);
280
281 // Simple case
282 let mut x = VecType::from_u64(0xFFFFFFFF);
283 let y = VecType::from_u64(5);
284 bigint::large_mul(&mut x, &y);
285 let expected: VecType = vec_from_u32(&[0xFFFFFFFB, 0x4]);
286 assert_eq!(&*x, &*expected);
287
288 // Large u32, but still just as easy.
289 let mut x = VecType::from_u64(0xFFFFFFFF);
290 let y = VecType::from_u64(0xFFFFFFFE);
291 bigint::large_mul(&mut x, &y);
292 let expected: VecType = vec_from_u32(&[0x2, 0xFFFFFFFD]);
293 assert_eq!(&*x, &*expected);
294
295 // Let's multiply two large values together.
296 let mut x: VecType = vec_from_u32(&[0xFFFFFFFE, 0x0FFFFFFF, 1]);
297 let y: VecType = vec_from_u32(&[0x99999999, 0x99999999, 0xCCCD9999, 0xCCCC]);
298 bigint::large_mul(&mut x, &y);
299 let expected: VecType =
300 vec_from_u32(&[0xCCCCCCCE, 0x5CCCCCCC, 0x9997FFFF, 0x33319999, 0x999A7333, 0xD999]);
301 assert_eq!(&*x, &*expected);
302 }
303
304 #[test]
very_large_mul_test()305 fn very_large_mul_test() {
306 // Test cases triggered to that would normally use `karatsuba_mul`.
307 // Karatsuba multiplication was ripped out, however, these are useful
308 // test cases.
309 let mut x: VecType = vec_from_u32(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]);
310 let y: VecType = vec_from_u32(&[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]);
311 bigint::large_mul(&mut x, &y);
312 let expected: VecType = vec_from_u32(&[
313 4, 13, 28, 50, 80, 119, 168, 228, 300, 385, 484, 598, 728, 875, 1040, 1224, 1340, 1435,
314 1508, 1558, 1584, 1585, 1560, 1508, 1428, 1319, 1180, 1010, 808, 573, 304,
315 ]);
316 assert_eq!(&*x, &*expected);
317
318 // Test cases triggered to that would normally use `karatsuba_uneven_mul`.
319 let mut x: VecType = vec_from_u32(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]);
320 let y: VecType = vec_from_u32(&[
321 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
322 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
323 ]);
324 bigint::large_mul(&mut x, &y);
325 let expected: VecType = vec_from_u32(&[
326 4, 13, 28, 50, 80, 119, 168, 228, 300, 385, 484, 598, 728, 875, 1040, 1224, 1360, 1496,
327 1632, 1768, 1904, 2040, 2176, 2312, 2448, 2584, 2720, 2856, 2992, 3128, 3264, 3400, 3536,
328 3672, 3770, 3829, 3848, 3826, 3762, 3655, 3504, 3308, 3066, 2777, 2440, 2054, 1618, 1131,
329 592,
330 ]);
331 assert_eq!(&*x, &*expected);
332 }
333
334 #[test]
bit_length_test()335 fn bit_length_test() {
336 let x: VecType = vec_from_u32(&[0, 0, 0, 1]);
337 assert_eq!(bigint::bit_length(&x), 97);
338
339 let x: VecType = vec_from_u32(&[0, 0, 0, 3]);
340 assert_eq!(bigint::bit_length(&x), 98);
341
342 let x = VecType::from_u64(1 << 31);
343 assert_eq!(bigint::bit_length(&x), 32);
344 }
345
346 #[test]
shl_bits_test()347 fn shl_bits_test() {
348 let mut x = VecType::from_u64(0xD2210408);
349 bigint::shl_bits(&mut x, 5);
350 let expected: VecType = vec_from_u32(&[0x44208100, 0x1A]);
351 assert_eq!(&*x, &*expected);
352 }
353
354 #[test]
shl_limbs_test()355 fn shl_limbs_test() {
356 let mut x = VecType::from_u64(0xD2210408);
357 bigint::shl_limbs(&mut x, 2);
358 let expected: VecType = if bigint::LIMB_BITS == 32 {
359 vec_from_u32(&[0, 0, 0xD2210408])
360 } else {
361 vec_from_u32(&[0, 0, 0, 0, 0xD2210408])
362 };
363 assert_eq!(&*x, &*expected);
364 }
365
366 #[test]
shl_test()367 fn shl_test() {
368 // Pattern generated via `''.join(["1" +"0"*i for i in range(20)])`
369 let mut x = VecType::from_u64(0xD2210408);
370 bigint::shl(&mut x, 5);
371 let expected: VecType = vec_from_u32(&[0x44208100, 0x1A]);
372 assert_eq!(&*x, &*expected);
373
374 bigint::shl(&mut x, 32);
375 let expected: VecType = vec_from_u32(&[0, 0x44208100, 0x1A]);
376 assert_eq!(&*x, &*expected);
377
378 bigint::shl(&mut x, 27);
379 let expected: VecType = vec_from_u32(&[0, 0, 0xD2210408]);
380 assert_eq!(&*x, &*expected);
381
382 // 96-bits of previous pattern
383 let mut x: VecType = vec_from_u32(&[0x20020010, 0x8040100, 0xD2210408]);
384 bigint::shl(&mut x, 5);
385 let expected: VecType = vec_from_u32(&[0x400200, 0x802004, 0x44208101, 0x1A]);
386 assert_eq!(&*x, &*expected);
387
388 bigint::shl(&mut x, 32);
389 let expected: VecType = vec_from_u32(&[0, 0x400200, 0x802004, 0x44208101, 0x1A]);
390 assert_eq!(&*x, &*expected);
391
392 bigint::shl(&mut x, 27);
393 let expected: VecType = vec_from_u32(&[0, 0, 0x20020010, 0x8040100, 0xD2210408]);
394 assert_eq!(&*x, &*expected);
395 }
396