nanvm_lib/vm/bigint/
mod.rs

1mod add;
2mod bitand;
3mod bitor;
4mod bitxor;
5mod cmp;
6mod debug;
7mod default;
8mod display;
9mod div;
10mod from;
11mod index;
12mod mul;
13mod neg;
14mod partial_eq;
15mod pow;
16mod radix;
17mod rem;
18mod shl;
19mod shr;
20mod sub;
21#[cfg(test)]
22mod test_util;
23mod to_f64;
24
25use core::{cmp::Ordering, iter::once};
26
27use crate::{
28    common::{div_mod::DivMod, iter::Iter, sized_index::SizedIndex, uint::Uint},
29    sign::Sign,
30    vm::{Any, IContainer, IVm, error},
31};
32
33/// The largest word count a `<<` or a `*` may grow a `BigInt` to — `2^14`
34/// words (`2^20` bits, 128 KiB) — matching
35/// [`fjs/types/bigint/module.f.mjs`](../../../../../fjs/types/bigint/module.f.mjs)'s
36/// own `maxLength` (`0x10_0000n` bits) exactly, divided down from bits to
37/// 64-bit words. `maxLength` is itself the *smallest* `BigInt` size limit
38/// across the engines FunctionalScript targets — V8's own limit is `2^30`
39/// bits, far larger, but Bun's and Safari's are tighter, and `maxLength` is
40/// already chosen to fit under all of them (see that file's own comment on
41/// `mask`, keyed to the same constant). `nanvm-lib` follows the tightest
42/// bound already established for the language rather than picking a
43/// second, V8-only one of its own.
44///
45/// This is *not* the same limit as `BigInt`'s internal `u32` word index
46/// (~4 billion words, ~34 GiB): that ceiling only protects the container's
47/// own indexing, not the process. An allocation anywhere near it can abort
48/// the process outright — `Vec`'s allocator failure is not a catchable
49/// panic — from a shift count an attacker can spell in one `u64` word, or from
50/// operands whose product is that long, well before any guard based on the
51/// index limit alone would reject it. That is
52/// exactly the crash-instead-of-refuse this checks against.
53const MAX_WORDS: u64 = 1 << 14;
54
55/// [`BigInt::abs_sub_vec`]'s precondition, broken.
56const RHS_GREATER: &str = "abs_sub_vec: rhs is greater than self";
57
58/// A non-negative shift amount, decoded once for `<<` (`shl.rs`) and `>>`
59/// (`shr.rs`) by [`BigInt::shift_amount`]. Each operation picks its own
60/// result for the two degenerate cases; only `Words` reaches a shift loop.
61enum ShiftAmount {
62    /// `self` is `0n`, or the amount is `0n`: the result is `self`.
63    Noop,
64    /// The amount does not fit one word (`>= 2^64`).
65    TooWide,
66    /// The amount as whole words and the bits left over (`< 64`).
67    Words(u64, u64),
68}
69
70// The word layer: magnitude arithmetic over plain little-endian words (least
71// significant first). It is the single owner of these algorithms; the
72// `BigInt`-level methods below only convert their operands and delegate, so
73// [`abs_divmod_vec`](BigInt::abs_divmod_vec) can run its inner loop on words
74// without rebuilding a `BigInt` on every bit.
75
76/// Drops `words`' leading (most-significant) zero words, so a magnitude is
77/// normalized: zero becomes empty.
78fn trim(words: &mut Vec<u64>) {
79    while words.last() == Some(&0) {
80        words.pop();
81    }
82}
83
84/// Compares two magnitudes with no leading (most-significant) zero words: the
85/// longer one (more significant words) is greater; at equal length, the first
86/// differing word from the most-significant end decides.
87fn cmp_words<T: SizedIndex<usize, Output = u64> + ?Sized>(a: &T, b: &T) -> Ordering {
88    a.length().cmp(&b.length()).then_with(|| {
89        let words = (0..a.length()).rev();
90        words.clone().map(|i| a[i]).cmp(words.map(|i| b[i]))
91    })
92}
93
94/// `a -= b` word by word, in place, with `b` read as zero past its end: the
95/// one borrow loop behind both [`sub_words_assign`] and
96/// [`abs_sub_vec`](BigInt::abs_sub_vec). Returns the borrow out of `a`'s most
97/// significant word: `true` iff `b > a` (when `b` is no longer than `a`), in
98/// which case `a` holds the difference wrapped modulo `2^(64 * a.len())`.
99/// Words of `b` beyond `a`'s length are not read, so the caller rules out a
100/// longer `b` itself.
101fn sub_words_borrow(a: &mut [u64], b: impl IntoIterator<Item = u64>) -> bool {
102    let mut b = b.into_iter();
103    let mut borrow = false;
104    for word in a.iter_mut() {
105        let (diff, under_b) = word.overflowing_sub(b.next().unwrap_or(0));
106        let (diff, under_borrow) = diff.overflowing_sub(borrow as u64);
107        *word = diff;
108        borrow = under_b || under_borrow;
109    }
110    borrow
111}
112
113/// `a -= b`, in place, trimming any leading zero words the subtraction
114/// produces so `a` stays normalized.
115///
116/// Precondition: `cmp_words(a, b)` is not `Ordering::Less`.
117fn sub_words_assign(a: &mut Vec<u64>, b: &[u64]) {
118    sub_words_borrow(a, b.iter().copied());
119    trim(a);
120}
121
122/// `words += 1`, in place: the carry ripples up until a word does not
123/// overflow, and becomes a new most-significant word if every word did.
124fn add_one(words: &mut Vec<u64>) {
125    for word in words.iter_mut() {
126        let (sum, overflow) = word.overflowing_add(1);
127        *word = sum;
128        if !overflow {
129            return;
130        }
131    }
132    words.push(1);
133}
134
135/// `words -= 1`, in place: the borrow ripples up until a word does not
136/// underflow. The length never changes, and no trim is made; an all-zero
137/// `words` wraps to all ones (callers pass a nonzero magnitude).
138fn sub_one(words: &mut [u64]) {
139    for word in words.iter_mut() {
140        let (diff, underflow) = word.overflowing_sub(1);
141        *word = diff;
142        if !underflow {
143            return;
144        }
145    }
146}
147
148/// The positive magnitude a negative `bitwise_op` result's two's-complement
149/// word pattern decodes to: flip every bit, then add one — the standard
150/// two's-complement negation, over words instead of a single machine
151/// integer. The `+ 1` can carry a new word into existence (`!x` all-ones
152/// becomes all-zeros, and `+ 1` then carries out past the last word), which
153/// [`add_one`] does.
154fn magnitude_from_twos_complement(mut words: Vec<u64>) -> Vec<u64> {
155    for word in words.iter_mut() {
156        *word = !*word;
157    }
158    add_one(&mut words);
159    trim(&mut words);
160    words
161}
162
163/// ```
164/// use nanvm_lib::{vm::{BigInt, IVm}, naive::Naive};
165/// fn bigint_test<A: IVm>() {
166///     let a: BigInt<A> = 12345678901234567890u64.into();
167///     let b: BigInt<A> = (-1234567890123456789i64).into();
168/// }
169///
170/// bigint_test::<Naive>();
171/// ```
172#[derive(Clone)]
173pub struct BigInt<A: IVm>(A::InternalBigInt);
174
175impl<A: IVm> BigInt<A> {
176    /// `self`, or the `RangeError` of a `BigInt` longer than `MAX_WORDS`
177    /// words: the check `+`, `-` and `*` make of their results (`<<` checks
178    /// its width before it allocates).
179    pub(crate) fn within_limit(self) -> Result<Self, Any<A>> {
180        if u64::from(self.length()) > MAX_WORDS {
181            return Err(error::bigint_too_large());
182        }
183        Ok(self)
184    }
185
186    /// `self * rhs` where the caller's operands are bounded by construction
187    /// to a product far under `MAX_WORDS`, as the exact arithmetic of a
188    /// `binary64` is (a 53-bit mantissa, a power of two, a power of ten of at
189    /// most a few hundred digits): the product cannot throw.
190    pub(crate) fn mul_bounded(self, rhs: Self) -> Self {
191        (self * rhs).expect("a binary64's exact arithmetic is far under BigInt's size limit")
192    }
193
194    /// `self + rhs` where the caller's operands are bounded by construction,
195    /// as for `mul_bounded`: the sum cannot throw.
196    pub(crate) fn add_bounded(self, rhs: Self) -> Self {
197        (self + rhs).expect("a binary64's exact arithmetic is far under BigInt's size limit")
198    }
199
200    /// `pub(crate)`, not private: `BooleanCoercion` (`vm/boolean_coercion.rs`)
201    /// uses this to test `0n` without constructing and comparing against a
202    /// throwaway `BigInt::default()`.
203    pub(crate) fn is_zero(&self) -> bool {
204        self.0.items().is_empty()
205    }
206
207    fn sign(&self) -> Sign {
208        *self.0.header()
209    }
210
211    /// The function doesn't normalize the bigint.
212    fn unchecked_new(sign: Sign, items: impl IntoIterator<Item = u64>) -> Self {
213        Self(A::InternalBigInt::new_ok(sign, items))
214    }
215
216    /// Note: this function accepts an iterator in least-significant-word-first order,
217    /// i.e. the first item is the least significant word!
218    pub fn normalize_new(sign: Sign, items: impl IntoIterator<Item = u64>) -> Self {
219        let mut vec: Vec<u64> = items.into_iter().collect();
220        // TODO: Don't allocate vector for the normalization.
221        trim(&mut vec);
222        if vec.is_empty() {
223            Self::default()
224        } else {
225            Self::unchecked_new(sign, vec)
226        }
227    }
228
229    /// Decodes `rhs`, a non-negative shift amount, against `self`.
230    fn shift_amount(&self, rhs: &Self) -> ShiftAmount {
231        if self.length() == 0 {
232            return ShiftAmount::Noop;
233        }
234        match rhs.length() {
235            0 => ShiftAmount::Noop,
236            1 => {
237                let (word_shift, bit_shift) = rhs[0].div_mod(64);
238                ShiftAmount::Words(word_shift, bit_shift)
239            }
240            _ => ShiftAmount::TooWide,
241        }
242    }
243
244    fn new_one(sign: Sign, value: u64) -> Self {
245        Self::unchecked_new(sign, once(value))
246    }
247
248    /// `self + (rhs with its sign replaced by rhs_sign)`.
249    ///
250    /// The single signed dispatch shared by `Add` and `Sub` (`a - b = a + (-b)`).
251    /// The effective sign is threaded as a parameter instead of negating `rhs`
252    /// via `Neg`, because `Neg` rebuilds the container (copying every word) —
253    /// don't "simplify" `sub` back to `self + (-rhs)`.
254    fn add_signed(self, rhs: Self, rhs_sign: Sign) -> Self {
255        let lhs_sign = self.sign();
256        let (sign, vec) = if lhs_sign == rhs_sign {
257            (lhs_sign, self.abs_add_vec(rhs))
258        } else {
259            // Signs differ: the result takes the sign of the larger magnitude.
260            match self.clone().abs_cmp_vec(rhs.clone()) {
261                Ordering::Equal => return Self::default(),
262                Ordering::Greater => (lhs_sign, self.abs_sub_vec(rhs)),
263                Ordering::Less => (rhs_sign, rhs.abs_sub_vec(self)),
264            }
265        };
266        Self::unchecked_new(sign, vec)
267    }
268
269    /// Truncating division: `(self / rhs, self % rhs)`.
270    ///
271    /// The single owner of the protocol `Div` and `Rem` project from: the
272    /// zero-divisor guard, the magnitude division, and both sign rules. The
273    /// quotient truncates toward zero, so it is negative iff exactly one
274    /// operand is; the remainder's sign follows the dividend. Both match
275    /// Rust's own integer `/` and `%`. Only the zero divisor is special: JS
276    /// throws instead of the `NaN` a `Number` operation would give.
277    pub fn div_mod(self, rhs: Self) -> Result<(Self, Self), Any<A>> {
278        if rhs.is_zero() {
279            return Err(error::division_by_zero());
280        }
281        let lhs_sign = self.sign();
282        let quotient_sign = lhs_sign * rhs.sign();
283        let (quotient, remainder) = self.abs_divmod_vec(rhs);
284        Ok((
285            Self::normalize_new(quotient_sign, quotient),
286            Self::normalize_new(lhs_sign, remainder),
287        ))
288    }
289
290    fn add_to_vec(mut vec: Vec<u64>, index: u32, add: u128) -> Vec<u64> {
291        // TODO: replace recursion with loop.
292        let sum = vec[index as usize] as u128 + add;
293        vec[index as usize] = sum as u64;
294        let carry = sum >> 64;
295        if carry > 0 {
296            vec = Self::add_to_vec(vec, index + 1, carry);
297        }
298        vec
299    }
300
301    /// Panics if this BigInt is not normalized, i.e. if it has leading
302    /// (most-significant) zero words.
303    fn assert_normalized(&self) {
304        assert_slice_normalized(self.0.items());
305    }
306
307    /// Panics unless both `self` and `rhs` are normalized: the shared
308    /// precondition of the two-operand magnitude helpers.
309    fn assert_normalized_with(&self, rhs: &Self) {
310        self.assert_normalized();
311        rhs.assert_normalized();
312    }
313
314    /// Compare absolute values by looking at the most-significant words first.
315    ///
316    /// Precondition: both `self` and `rhs` must be normalized, i.e. they must
317    /// not contain leading (most-significant) zero words.
318    fn abs_cmp_vec(self, rhs: Self) -> Ordering {
319        self.assert_normalized_with(&rhs);
320        cmp_words(self.0.items(), rhs.0.items())
321    }
322
323    fn abs_add_vec(self, rhs: Self) -> Vec<u64> {
324        self.assert_normalized_with(&rhs);
325
326        let mut carry: u128 = 0;
327        let mut out: Vec<u64> = self
328            .index_iter()
329            .zip_longest(rhs.index_iter())
330            .map(|(a, b)| {
331                let sum = a.unwrap_or_default() as u128 + b.unwrap_or_default() as u128 + carry;
332                carry = sum >> 64;
333                sum as u64
334            })
335            .collect();
336
337        if carry > 0 {
338            out.push(carry as u64);
339        }
340
341        // Postcondition: result must be normalized.
342        assert_slice_normalized(out.as_slice());
343        out
344    }
345
346    /// `|self| - |rhs|`, normalized.
347    ///
348    /// Precondition: both operands are normalized, and `|rhs| <= |self|`;
349    /// panics with [`RHS_GREATER`] otherwise.
350    fn abs_sub_vec(self, rhs: Self) -> Vec<u64> {
351        self.assert_normalized_with(&rhs);
352
353        // Normalized, a longer `rhs` is a greater one; `sub_words_borrow`
354        // would not read its extra words.
355        if rhs.length() > self.length() {
356            panic!("{RHS_GREATER}");
357        }
358        let mut out: Vec<u64> = self.index_iter().collect();
359        if sub_words_borrow(&mut out, rhs.index_iter()) {
360            panic!("{RHS_GREATER}");
361        }
362        trim(&mut out);
363        out
364    }
365
366    /// `(|self| / |rhs|, |self| % |rhs|)`, via schoolbook binary long
367    /// division: one bit of the dividend at a time, shifted into a running
368    /// remainder that is reduced by the divisor whenever it grows large
369    /// enough, recording a quotient bit each time it is.
370    ///
371    /// Precondition: both operands are normalized, and `rhs` is non-zero.
372    fn abs_divmod_vec(self, rhs: Self) -> (Vec<u64>, Vec<u64>) {
373        self.assert_normalized_with(&rhs);
374
375        let denom: Vec<u64> = rhs.index_iter().collect();
376        let numer: Vec<u64> = self.index_iter().collect();
377
378        let mut quotient: Vec<u64> = vec![0; numer.len()];
379        let mut remainder: Vec<u64> = Vec::new();
380        for bit in (0..numer.len() as u32 * 64).rev() {
381            let numer_bit = (numer[(bit / 64) as usize] >> (bit % 64)) & 1;
382
383            let mut carry = numer_bit;
384            for word in remainder.iter_mut() {
385                let next_carry = *word >> 63;
386                *word = (*word << 1) | carry;
387                carry = next_carry;
388            }
389            if carry != 0 {
390                remainder.push(carry);
391            }
392
393            if cmp_words(remainder.as_slice(), denom.as_slice()) != Ordering::Less {
394                sub_words_assign(&mut remainder, &denom);
395                quotient[(bit / 64) as usize] |= 1u64 << (bit % 64);
396            }
397        }
398
399        trim(&mut quotient);
400        (quotient, remainder)
401    }
402
403    /// This BigInt's infinite-precision two's-complement bit pattern, sliced
404    /// to `len` words (the caller passes the larger of the two operand
405    /// lengths, so no significant bit is cut off). Non-negative: the
406    /// magnitude, zero-padded. Negative: `NOT(|self| - 1)` — the standard
407    /// two's-complement encoding, chosen (over flip-then-subtract) because
408    /// the sign bit implicitly repeats forever above the magnitude, and
409    /// subtracting first keeps that repetition free instead of needing it
410    /// threaded through the padding words too.
411    fn twos_complement_words(self, len: u32) -> Vec<u64> {
412        let sign = self.sign();
413        let mut words: Vec<u64> = self.index_iter().collect();
414        words.resize(len as usize, 0);
415        if sign == Sign::Negative {
416            sub_one(&mut words);
417            for word in words.iter_mut() {
418                *word = !*word;
419            }
420        }
421        words
422    }
423
424    /// Shared `&`/`|`/`^` dispatch (ECMA-262's `BigInt::bitwiseOp`): decode
425    /// both operands to same-length two's-complement word patterns, apply
426    /// `word_op` word-by-word, then decode the outcome — `result_negative`
427    /// gives the result's sign from whether each operand was negative (AND:
428    /// both; OR: either; XOR: exactly one), and a negative outcome's word
429    /// pattern is turned back into a magnitude via
430    /// [`magnitude_from_twos_complement`].
431    fn bitwise_op(
432        self,
433        rhs: Self,
434        word_op: impl Fn(u64, u64) -> u64,
435        result_negative: impl Fn(bool, bool) -> bool,
436    ) -> Self {
437        let self_negative = self.sign() == Sign::Negative;
438        let rhs_negative = rhs.sign() == Sign::Negative;
439        let len = self.length().max(rhs.length());
440        let a = self.twos_complement_words(len);
441        let b = rhs.twos_complement_words(len);
442        let out: Vec<u64> = a
443            .iter()
444            .zip(b.iter())
445            .map(|(&x, &y)| word_op(x, y))
446            .collect();
447        if result_negative(self_negative, rhs_negative) {
448            Self::normalize_new(Sign::Negative, magnitude_from_twos_complement(out))
449        } else {
450            Self::normalize_new(Sign::Positive, out)
451        }
452    }
453}
454
455/// Panics if the slice is not normalized, i.e. if it has leading
456/// (most-significant) zero words.
457fn assert_slice_normalized<I: Uint, T: SizedIndex<I, Output = u64> + ?Sized>(v: &T) {
458    if let Some(&last) = v.last()
459        && last == 0
460    {
461        panic!("BigInt is not normalized (has leading zero words)");
462    }
463}
464
465#[cfg(test)]
466mod tests {
467    use super::{
468        add_one, cmp_words, sub_one, sub_words_assign, sub_words_borrow,
469        test_util::{T, int, pos},
470        trim,
471    };
472    use core::cmp::Ordering;
473
474    // Tests for the word layer
475
476    #[test]
477    fn test_trim() {
478        for (words, trimmed) in [
479            ([].to_vec(), [].to_vec()),
480            ([0].to_vec(), [].to_vec()),
481            ([0, 0].to_vec(), [].to_vec()),
482            ([1, 0, 0].to_vec(), [1].to_vec()),
483            ([0, 1].to_vec(), [0, 1].to_vec()),
484            ([0, 1, 0].to_vec(), [0, 1].to_vec()),
485        ] {
486            let mut words: Vec<u64> = words;
487            trim(&mut words);
488            assert_eq!(words, trimmed);
489        }
490    }
491
492    #[test]
493    fn test_cmp_words() {
494        let cmp = |a: &[u64], b: &[u64]| cmp_words(a, b);
495        assert_eq!(cmp(&[], &[]), Ordering::Equal);
496        assert_eq!(cmp(&[], &[1]), Ordering::Less);
497        assert_eq!(cmp(&[u64::MAX], &[0, 1]), Ordering::Less);
498        assert_eq!(cmp(&[5, 10], &[20, 9]), Ordering::Greater);
499        assert_eq!(cmp(&[20, 9], &[5, 10]), Ordering::Less);
500        assert_eq!(cmp(&[2, 7], &[1, 7]), Ordering::Greater);
501        assert_eq!(cmp(&[1, 7], &[1, 7]), Ordering::Equal);
502    }
503
504    #[test]
505    fn test_sub_words_borrow() {
506        // No borrow, and a shorter `b` read as zero past its end.
507        let mut a = [300u64, 2];
508        assert!(!sub_words_borrow(&mut a, [100u64]));
509        assert_eq!(a, [200, 2]);
510        // A borrow that ripples through a zero word.
511        let mut a = [0u64, 0, 1];
512        assert!(!sub_words_borrow(&mut a, [1u64]));
513        assert_eq!(a, [u64::MAX, u64::MAX, 0]);
514        // `b > a`: the borrow comes out, and `a` wraps.
515        let mut a = [1u64];
516        assert!(sub_words_borrow(&mut a, [2u64]));
517        assert_eq!(a, [u64::MAX]);
518        // A borrow plus a word subtraction in the same word.
519        let mut a = [0u64, 5];
520        assert!(!sub_words_borrow(&mut a, [1u64, 4]));
521        assert_eq!(a, [u64::MAX, 0]);
522    }
523
524    #[test]
525    fn test_sub_words_assign_trims() {
526        let mut a = [0u64, 5].to_vec();
527        sub_words_assign(&mut a, &[1, 4]);
528        assert_eq!(a, [u64::MAX]);
529        let mut a = [7u64, 3].to_vec();
530        sub_words_assign(&mut a, &[7, 3]);
531        assert_eq!(a, []);
532    }
533
534    #[test]
535    fn test_add_one() {
536        for (words, sum) in [
537            ([].to_vec(), [1].to_vec()),
538            ([41].to_vec(), [42].to_vec()),
539            ([u64::MAX, 3].to_vec(), [0, 4].to_vec()),
540            ([u64::MAX, u64::MAX].to_vec(), [0, 0, 1].to_vec()),
541        ] {
542            let mut words: Vec<u64> = words;
543            add_one(&mut words);
544            assert_eq!(words, sum);
545        }
546    }
547
548    #[test]
549    fn test_sub_one() {
550        let mut words = [42u64];
551        sub_one(&mut words);
552        assert_eq!(words, [41]);
553        // The borrow ripples, and the length stays: no trim.
554        let mut words = [0u64, 0, 1];
555        sub_one(&mut words);
556        assert_eq!(words, [u64::MAX, u64::MAX, 0]);
557        let mut words = [0u64, 4];
558        sub_one(&mut words);
559        assert_eq!(words, [u64::MAX, 3]);
560    }
561
562    #[test]
563    fn test_abs_cmp_vec_equal_numbers() {
564        let a: T = 12_345u64.into();
565        let b: T = 12_345u64.into();
566        assert_eq!(a.abs_cmp_vec(b), Ordering::Equal);
567    }
568
569    #[test]
570    fn test_abs_cmp_vec_equal_zero() {
571        let a: T = 0u64.into();
572        let b: T = 0u64.into();
573        assert_eq!(a.abs_cmp_vec(b), Ordering::Equal);
574    }
575
576    #[test]
577    fn test_abs_cmp_vec_simple_different_lengths() {
578        let one_digit = pos([100u64]);
579        let two_digits = pos([100u64, 1u64]);
580        assert_eq!(
581            two_digits.clone().abs_cmp_vec(one_digit.clone()),
582            Ordering::Greater
583        );
584        assert_eq!(one_digit.abs_cmp_vec(two_digits), Ordering::Less);
585    }
586
587    #[test]
588    fn test_abs_cmp_vec_same_length_first_greater() {
589        let a: T = 12_346u64.into();
590        let b: T = 12_345u64.into();
591        assert_eq!(a.abs_cmp_vec(b), Ordering::Greater);
592    }
593
594    #[test]
595    fn test_abs_cmp_vec_same_length_first_less() {
596        let a: T = 12_344u64.into();
597        let b: T = 12_345u64.into();
598        assert_eq!(a.abs_cmp_vec(b), Ordering::Less);
599    }
600
601    #[test]
602    fn test_abs_cmp_vec_most_significant_digit_differs() {
603        let a: T = 0x8000_0000_0000_0000u64.into();
604        let b: T = 0x7FFF_FFFF_FFFF_FFFFu64.into();
605        assert_eq!(a.abs_cmp_vec(b), Ordering::Greater);
606    }
607
608    #[test]
609    fn test_abs_cmp_vec_least_significant_digit_differs() {
610        let a: T = 0x1000_0000_0000_0001u64.into();
611        let b: T = 0x1000_0000_0000_0000u64.into();
612        assert_eq!(a.abs_cmp_vec(b), Ordering::Greater);
613    }
614
615    #[test]
616    fn test_abs_cmp_vec_zero_vs_nonzero() {
617        let a: T = 0u64.into();
618        let b: T = 1u64.into();
619        assert_eq!(a.abs_cmp_vec(b), Ordering::Less);
620
621        let a: T = 1u64.into();
622        let b: T = 0u64.into();
623        assert_eq!(a.abs_cmp_vec(b), Ordering::Greater);
624    }
625
626    #[test]
627    fn test_abs_cmp_vec_simple_large_numbers() {
628        // Test with large u64 numbers instead of multi-digit
629        let large1: T = 0xFFFF_FFFF_FFFF_FFFFu64.into();
630        let large2: T = 0xFFFF_FFFF_FFFF_FFFEu64.into();
631
632        assert_eq!(
633            large1.clone().abs_cmp_vec(large2.clone()),
634            Ordering::Greater
635        );
636        assert_eq!(large2.clone().abs_cmp_vec(large1.clone()), Ordering::Less);
637        assert_eq!(large1.clone().abs_cmp_vec(large1.clone()), Ordering::Equal);
638    }
639
640    #[test]
641    fn test_abs_cmp_vec_simple_equal() {
642        let large1: T = 0x1234_5678_9ABC_DEF0u64.into();
643        let large2: T = 0x1234_5678_9ABC_DEF0u64.into();
644
645        assert_eq!(large1.abs_cmp_vec(large2), Ordering::Equal);
646    }
647
648    #[test]
649    fn test_abs_cmp_vec_simple_digit_difference() {
650        // Test simple cases where we know the expected result
651        let large1: T = 0x8000_0000_0000_0000u64.into();
652        let large2: T = 0x7FFF_FFFF_FFFF_FFFFu64.into();
653
654        assert_eq!(large1.abs_cmp_vec(large2), Ordering::Greater);
655    }
656
657    #[test]
658    fn test_abs_cmp_vec_two_digits_higher_word_dominates() {
659        // Test where self's lower word < rhs lower word, but self's higher word > rhs higher word
660        // self = [5, 10] represents 10 * 2^64 + 5
661        // rhs = [20, 9] represents 9 * 2^64 + 20
662        // Since higher word is more significant, self should be greater despite lower word being smaller
663        let self_val = pos([5u64, 10u64]);
664        let rhs_val = pos([20u64, 9u64]);
665
666        assert_eq!(self_val.abs_cmp_vec(rhs_val), Ordering::Greater);
667    }
668
669    #[test]
670    fn test_div_mod_pairs_quotient_and_remainder() {
671        for (a, b, q, r) in [
672            (10, 3, 3, 1),
673            (-10, 3, -3, -1),
674            (10, -3, -3, 1),
675            (-10, -3, 3, -1),
676            // `div_mod` picks each result's sign before it knows the
677            // magnitude; a zero result must still come out positive.
678            (-1, 2, 0, -1),
679            (1, -2, 0, 1),
680            (-4, 2, -2, 0),
681            (4, -2, -2, 0),
682        ] {
683            let (quotient, remainder) = int(a).div_mod(int(b)).unwrap();
684            // `==` ignores the sign of a zero, so the sign is pinned apart.
685            assert_eq!(quotient.sign(), int(q).sign());
686            assert_eq!(remainder.sign(), int(r).sign());
687            assert_eq!(quotient, int(q));
688            assert_eq!(remainder, int(r));
689        }
690    }
691
692    #[test]
693    fn test_div_mod_zero_divisor_throws() {
694        let a: T = 5u64.into();
695        assert!(a.div_mod(T::default()).is_err());
696    }
697
698    // Tests for abs_add_vec
699
700    #[test]
701    fn test_abs_add_vec_basic() {
702        let a: T = 123u64.into();
703        let b: T = 456u64.into();
704        let result = a.abs_add_vec(b);
705        let expected = pos(result);
706        let expected_value: T = 579u64.into();
707        assert_eq!(expected.abs_cmp_vec(expected_value), Ordering::Equal);
708    }
709
710    #[test]
711    fn test_abs_add_vec_zero() {
712        let a: T = 42u64.into();
713        let b: T = 0u64.into();
714        let result = a.clone().abs_add_vec(b);
715        let result_bigint = pos(result);
716        assert_eq!(result_bigint.abs_cmp_vec(a), Ordering::Equal);
717
718        let c: T = 0u64.into();
719        let d: T = 17u64.into();
720        let result2 = c.abs_add_vec(d.clone());
721        let result2_bigint = pos(result2);
722        assert_eq!(result2_bigint.abs_cmp_vec(d), Ordering::Equal);
723    }
724
725    #[test]
726    fn test_abs_add_vec_carry() {
727        let a: T = u64::MAX.into();
728        let b: T = 1u64.into();
729        let result = a.abs_add_vec(b);
730
731        // u64::MAX + 1 should produce [0, 1] (carry to next digit)
732        assert_eq!(result.len(), 2);
733        assert_eq!(result[0], 0u64);
734        assert_eq!(result[1], 1u64);
735    }
736
737    #[test]
738    fn test_abs_add_vec_different_lengths() {
739        let small = pos([100u64]);
740        let large = pos([200u64, 1u64]);
741
742        let result1 = small.clone().abs_add_vec(large.clone());
743        let result2 = large.abs_add_vec(small);
744
745        // Addition should be commutative
746        assert_eq!(result1.len(), result2.len());
747        for (a, b) in result1.iter().zip(result2.iter()) {
748            assert_eq!(a, b);
749        }
750
751        // Result should be [300, 1]
752        assert_eq!(result1[0], 300u64);
753        assert_eq!(result1[1], 1u64);
754    }
755
756    #[test]
757    fn test_abs_add_vec_multiple_carries() {
758        let a = pos([u64::MAX, u64::MAX]);
759        let b: T = 1u64.into();
760
761        let result = a.abs_add_vec(b);
762
763        // [u64::MAX, u64::MAX] + 1 should produce [0, 0, 1]
764        assert_eq!(result.len(), 3);
765        assert_eq!(result[0], 0u64);
766        assert_eq!(result[1], 0u64);
767        assert_eq!(result[2], 1u64);
768    }
769
770    #[test]
771    fn test_abs_add_vec_same_large_numbers() {
772        let large: T = 0x7FFF_FFFF_FFFF_FFFFu64.into();
773        let result = large.clone().abs_add_vec(large);
774        let result_bigint = pos(result);
775
776        let expected: T = 0xFFFF_FFFF_FFFF_FFFEu64.into();
777        assert_eq!(result_bigint.abs_cmp_vec(expected), Ordering::Equal);
778    }
779
780    #[test]
781    fn test_abs_add_vec_no_carry() {
782        let a: T = 1_000u64.into();
783        let b: T = 2_000u64.into();
784        let result = a.abs_add_vec(b);
785
786        assert_eq!(result.len(), 1);
787        assert_eq!(result[0], 3_000u64);
788    }
789
790    #[test]
791    fn test_abs_add_vec_both_zero() {
792        let a: T = 0u64.into();
793        let b: T = 0u64.into();
794        let result = a.abs_add_vec(b);
795
796        // Zero might be represented as empty vector in this implementation
797        assert!(result.is_empty() || (result.len() == 1 && result[0] == 0u64));
798    }
799
800    // Tests for abs_sub_vec
801
802    #[test]
803    fn test_abs_sub_vec_basic() {
804        let a: T = 456u64.into();
805        let b: T = 123u64.into();
806        let result = a.abs_sub_vec(b);
807        let result_bigint = pos(result);
808        let expected: T = 333u64.into();
809        assert_eq!(result_bigint.abs_cmp_vec(expected), Ordering::Equal);
810    }
811
812    #[test]
813    fn test_abs_sub_vec_same_numbers() {
814        let a: T = 12_345u64.into();
815        let result = a.clone().abs_sub_vec(a);
816
817        // Result should be zero (empty vec or [0])
818        assert!(result.is_empty() || (result.len() == 1 && result[0] == 0u64));
819    }
820
821    #[test]
822    fn test_abs_sub_vec_subtract_zero() {
823        let a: T = 42u64.into();
824        let b: T = 0u64.into();
825        let result = a.clone().abs_sub_vec(b);
826        let result_bigint = pos(result);
827        assert_eq!(result_bigint.abs_cmp_vec(a), Ordering::Equal);
828    }
829
830    #[test]
831    fn test_abs_sub_vec_with_borrow() {
832        let a: T = 1_000u64.into();
833        let b: T = 1u64.into();
834        let result = a.abs_sub_vec(b);
835
836        assert_eq!(result.len(), 1);
837        assert_eq!(result[0], 999u64);
838    }
839
840    #[test]
841    fn test_abs_sub_vec_different_lengths() {
842        let large = pos([300u64, 2u64]);
843        let small = pos([100u64]);
844
845        let result = large.abs_sub_vec(small);
846
847        // [300, 2] - [100] should be [200, 2]
848        assert_eq!(result.len(), 2);
849        assert_eq!(result[0], 200u64);
850        assert_eq!(result[1], 2u64);
851    }
852
853    #[test]
854    fn test_abs_sub_vec_borrow_propagation() {
855        let a = pos([0u64, 1u64]); // 2^64
856        let b: T = 1u64.into();
857
858        let result = a.abs_sub_vec(b);
859
860        // 2^64 - 1 should be u64::MAX
861        assert_eq!(result.len(), 1);
862        assert_eq!(result[0], u64::MAX);
863    }
864
865    #[test]
866    fn test_abs_sub_vec_leading_zero_trim() {
867        let a = pos([100u64, 1u64]);
868        let b = pos([100u64, 1u64]);
869
870        let result = a.abs_sub_vec(b);
871
872        // Should trim leading zeros and result in empty or [0]
873        assert!(result.is_empty() || (result.len() == 1 && result[0] == 0u64));
874    }
875
876    #[test]
877    fn test_abs_sub_vec_large_numbers() {
878        let a: T = u64::MAX.into();
879        let b: T = (u64::MAX - 1_000u64).into();
880        let result = a.abs_sub_vec(b);
881
882        assert_eq!(result.len(), 1);
883        assert_eq!(result[0], 1_000u64);
884    }
885
886    #[test]
887    fn test_abs_sub_vec_no_borrow() {
888        let a: T = 5_000u64.into();
889        let b: T = 2_000u64.into();
890        let result = a.abs_sub_vec(b);
891
892        assert_eq!(result.len(), 1);
893        assert_eq!(result[0], 3_000u64);
894    }
895
896    #[test]
897    #[should_panic(expected = "abs_sub_vec: rhs is greater than self")]
898    fn test_abs_sub_vec_panic_rhs_greater() {
899        let a: T = 100u64.into();
900        let b: T = 200u64.into();
901        let _ = a.abs_sub_vec(b); // Should panic
902    }
903
904    #[test]
905    #[should_panic(expected = "abs_sub_vec: rhs is greater than self")]
906    fn test_abs_sub_vec_panic_different_lengths() {
907        let small = pos([100u64]);
908        let large = pos([100u64, 1u64]);
909        let _ = small.abs_sub_vec(large); // Should panic - small < large
910    }
911}
nanvm_lib/vm/bigint/mod.rs

nanvm_lib/vm/bigint/
mod.rs
