1mod stackvec;
2
3use core::cmp;
4use minimal_lexical::bigint;
5use stackvec::{vec_from_u32, VecType};
6
7// u64::MAX and Limb::MAX for older Rustc versions.
8const U64_MAX: u64 = 0xffff_ffff_ffff_ffff;
9// LIMB_MAX
10#[cfg(all(target_pointer_width = "64", not(target_arch = "sparc")))]
11const LIMB_MAX: u64 = U64_MAX;
12#[cfg(not(all(target_pointer_width = "64", not(target_arch = "sparc"))))]
13const LIMB_MAX: u32 = 0xffff_ffff;
14
15#[test]
16fn 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]
56fn 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]
64fn 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]
92fn 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]
131fn 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]
137fn 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]
144fn 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]
169fn 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]
202fn 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]
235fn 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]
273fn 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]
305fn 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]
335fn 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]
347fn 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]
355fn 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]
367fn 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