dashu-int 0.6.0-rc.4

Arbitrary-precision integer math library for Rust, balancing ergonomics and efficiency. Provides UBig and IBig (unsigned and signed), with small values inlined on the stack. Efficient arithmetic, modular arithmetic, and number theory (pow, ilog, gcd, gcd_ext); two's-complement bit operations; parsing and formatting in base 2-36; optional serde, rand, num-traits, rkyv, and zeroize.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

//! Parse in a power-of-two radix.

use crate::{
    arch::word::Word,
    buffer::Buffer,
    primitive::{WORD_BITS, WORD_BITS_USIZE},
    radix::{self, Digit},
    repr::Repr,
    ubig::UBig,
};

use dashu_base::ParseError;

/// Parse an unsigned string to [UBig].
pub fn parse(src: &str, radix: Digit) -> Result<UBig, ParseError> {
    debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());

    let digits_per_word = (WORD_BITS / radix.trailing_zeros()) as usize;
    if src.len() <= digits_per_word {
        Ok(parse_word(src, radix)?.into())
    } else {
        parse_large(src, radix)
    }
}

/// Parse an unsigned string to `Word`.
///
/// The length of the string must be at most digits_per_word(radix).
fn parse_word(src: &str, radix: Digit) -> Result<Word, ParseError> {
    debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());
    debug_assert!(src.len() <= (WORD_BITS / radix.trailing_zeros()) as usize);

    let log_radix = radix.trailing_zeros();
    let mut word = 0;
    let mut bits = 0;
    for byte in src.as_bytes().iter().rev() {
        if *byte == b'_' {
            continue;
        }
        let digit = radix::digit_from_ascii_byte(*byte, radix).ok_or(ParseError::InvalidDigit)?;
        word |= (digit as Word) << bits;
        bits += log_radix;
    }
    Ok(word)
}

/// Parse an unsigned string to [UBig].
///
/// The result will usually not fit in a single word.
fn parse_large(src: &str, radix: Digit) -> Result<UBig, ParseError> {
    debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());

    let log_radix = radix.trailing_zeros();
    #[allow(clippy::redundant_closure)]
    let num_bits = src
        .len()
        .checked_mul(log_radix as usize)
        .expect("the number to be parsed is too large");
    let mut buffer = Buffer::allocate((num_bits - 1) / WORD_BITS_USIZE + 1);
    let mut bits = 0;
    let mut word = 0;
    for byte in src.as_bytes().iter().rev() {
        if *byte == b'_' {
            continue;
        }
        let digit = radix::digit_from_ascii_byte(*byte, radix).ok_or(ParseError::InvalidDigit)?;
        word |= (digit as Word) << bits;
        let new_bits = bits + log_radix;
        if new_bits >= WORD_BITS {
            buffer.push(word);
            word = (digit as Word) >> (WORD_BITS - bits);
            bits = new_bits - WORD_BITS;
        } else {
            bits = new_bits;
        }
    }
    if bits > 0 {
        buffer.push(word);
    }
    Ok(UBig(Repr::from_buffer(buffer)))
}