Quelle  math.rs   Sprache: unbekannt

// Adapted from https://github.com/Alexhuszagh/rust-lexical.

use crate::lexical::math::{Limb, Math};
use std::cmp;

#[derive(Clone, Default)]
struct Bigint {
    data: Vec<Limb>,
}

impl Math for Bigint {
    fn data(&self) -> &Vec<Limb> {
        &self.data
    }

    fn data_mut(&mut self) -> &mut Vec<Limb> {
        &mut self.data
    }
}

#[cfg(limb_width_32)]
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> {
    x.iter().cloned().collect()
}

#[cfg(limb_width_64)]
pub(crate) fn from_u32(x: &[u32]) -> Vec<Limb> {
    let mut v = Vec::<Limb>::default();
    for xi in x.chunks(2) {
        match xi.len() {
            1 => v.push(xi[0] as u64),
            2 => v.push(((xi[1] as u64) << 32) | (xi[0] as u64)),
            _ => unreachable!(),
        }
    }

    v
}

#[test]
fn compare_test() {
    // Simple
    let x = Bigint {
        data: from_u32(&[1]),
    };
    let y = Bigint {
        data: from_u32(&[2]),
    };
    assert_eq!(x.compare(&y), cmp::Ordering::Less);
    assert_eq!(x.compare(&x), cmp::Ordering::Equal);
    assert_eq!(y.compare(&x), cmp::Ordering::Greater);

    // Check asymmetric
    let x = Bigint {
        data: from_u32(&[5, 1]),
    };
    let y = Bigint {
        data: from_u32(&[2]),
    };
    assert_eq!(x.compare(&y), cmp::Ordering::Greater);
    assert_eq!(x.compare(&x), cmp::Ordering::Equal);
    assert_eq!(y.compare(&x), cmp::Ordering::Less);

    // Check when we use reverse ordering properly.
    let x = Bigint {
        data: from_u32(&[5, 1, 9]),
    };
    let y = Bigint {
        data: from_u32(&[6, 2, 8]),
    };
    assert_eq!(x.compare(&y), cmp::Ordering::Greater);
    assert_eq!(x.compare(&x), cmp::Ordering::Equal);
    assert_eq!(y.compare(&x), cmp::Ordering::Less);

    // Complex scenario, check it properly uses reverse ordering.
    let x = Bigint {
        data: from_u32(&[0, 1, 9]),
    };
    let y = Bigint {
        data: from_u32(&[4294967295, 0, 9]),
    };
    assert_eq!(x.compare(&y), cmp::Ordering::Greater);
    assert_eq!(x.compare(&x), cmp::Ordering::Equal);
    assert_eq!(y.compare(&x), cmp::Ordering::Less);
}

#[test]
fn hi64_test() {
    assert_eq!(Bigint::from_u64(0xA).hi64(), (0xA000000000000000, false));
    assert_eq!(Bigint::from_u64(0xAB).hi64(), (0xAB00000000000000, false));
    assert_eq!(
        Bigint::from_u64(0xAB00000000).hi64(),
        (0xAB00000000000000, false)
    );
    assert_eq!(
        Bigint::from_u64(0xA23456789A).hi64(),
        (0xA23456789A000000, false)
    );
}

#[test]
fn bit_length_test() {
    let x = Bigint {
        data: from_u32(&[0, 0, 0, 1]),
    };
    assert_eq!(x.bit_length(), 97);

    let x = Bigint {
        data: from_u32(&[0, 0, 0, 3]),
    };
    assert_eq!(x.bit_length(), 98);

    let x = Bigint {
        data: from_u32(&[1 << 31]),
    };
    assert_eq!(x.bit_length(), 32);
}

#[test]
fn iadd_small_test() {
    // Overflow check (single)
    // This should set all the internal data values to 0, the top
    // value to (1<<31), and the bottom value to (4>>1).
    // This is because the max_value + 1 leads to all 0s, we set the
    // topmost bit to 1.
    let mut x = Bigint {
        data: from_u32(&[4294967295]),
    };
    x.iadd_small(5);
    assert_eq!(x.data, from_u32(&[4, 1]));

    // No overflow, single value
    let mut x = Bigint {
        data: from_u32(&[5]),
    };
    x.iadd_small(7);
    assert_eq!(x.data, from_u32(&[12]));

    // Single carry, internal overflow
    let mut x = Bigint::from_u64(0x80000000FFFFFFFF);
    x.iadd_small(7);
    assert_eq!(x.data, from_u32(&[6, 0x80000001]));

    // Double carry, overflow
    let mut x = Bigint::from_u64(0xFFFFFFFFFFFFFFFF);
    x.iadd_small(7);
    assert_eq!(x.data, from_u32(&[6, 0, 1]));
}

#[test]
fn imul_small_test() {
    // No overflow check, 1-int.
    let mut x = Bigint {
        data: from_u32(&[5]),
    };
    x.imul_small(7);
    assert_eq!(x.data, from_u32(&[35]));

    // No overflow check, 2-ints.
    let mut x = Bigint::from_u64(0x4000000040000);
    x.imul_small(5);
    assert_eq!(x.data, from_u32(&[0x00140000, 0x140000]));

    // Overflow, 1 carry.
    let mut x = Bigint {
        data: from_u32(&[0x33333334]),
    };
    x.imul_small(5);
    assert_eq!(x.data, from_u32(&[4, 1]));

    // Overflow, 1 carry, internal.
    let mut x = Bigint::from_u64(0x133333334);
    x.imul_small(5);
    assert_eq!(x.data, from_u32(&[4, 6]));

    // Overflow, 2 carries.
    let mut x = Bigint::from_u64(0x3333333333333334);
    x.imul_small(5);
    assert_eq!(x.data, from_u32(&[4, 0, 1]));
}

#[test]
fn shl_test() {
    // Pattern generated via `''.join(["1" +"0"*i for i in range(20)])`
    let mut big = Bigint {
        data: from_u32(&[0xD2210408]),
    };
    big.ishl(5);
    assert_eq!(big.data, from_u32(&[0x44208100, 0x1A]));
    big.ishl(32);
    assert_eq!(big.data, from_u32(&[0, 0x44208100, 0x1A]));
    big.ishl(27);
    assert_eq!(big.data, from_u32(&[0, 0, 0xD2210408]));

    // 96-bits of previous pattern
    let mut big = Bigint {
        data: from_u32(&[0x20020010, 0x8040100, 0xD2210408]),
    };
    big.ishl(5);
    assert_eq!(big.data, from_u32(&[0x400200, 0x802004, 0x44208101, 0x1A]));
    big.ishl(32);
    assert_eq!(
        big.data,
        from_u32(&[0, 0x400200, 0x802004, 0x44208101, 0x1A])
    );
    big.ishl(27);
    assert_eq!(
        big.data,
        from_u32(&[0, 0, 0x20020010, 0x8040100, 0xD2210408])
    );
}