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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

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

use crate::{
    arch::word::Word,
    buffer::Buffer,
    error::ParseError,
    mul,
    radix::{self, Digit},
    ubig::UBig,
};
use alloc::vec;

/// Parse in chunks of CHUNK_LEN * digits_per_word.
const CHUNK_LEN: usize = 256;

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

    if bytes.len() <= radix_info.digits_per_word {
        let word = parse_word(bytes, radix)?;
        Ok(UBig::from_word(word))
    } else if bytes.len() <= CHUNK_LEN * radix_info.digits_per_word {
        parse_chunk(bytes, radix)
    } else {
        parse_large(bytes, radix)
    }
}

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

    let mut word: Word = 0;
    for byte in src.iter() {
        let digit = radix::digit_from_utf8_byte(*byte, radix).ok_or(ParseError::InvalidDigit)?;
        word = word * (radix as Word) + (digit as Word);
    }
    Ok(word)
}

/// Parse an unsigned string to [UBig].
///
/// The length of input is limited to `CHUNK_LEN * digits_per_word`.
fn parse_chunk(bytes: &[u8], radix: Digit) -> Result<UBig, ParseError> {
    debug_assert!(radix::is_radix_valid(radix) && !radix.is_power_of_two());
    let radix_info = radix::radix_info(radix);
    debug_assert!(bytes.len() <= CHUNK_LEN * radix_info.digits_per_word);

    let groups = bytes.rchunks(radix_info.digits_per_word);
    let mut buffer = Buffer::allocate(groups.len());
    for group in groups.rev() {
        let next = parse_word(group, radix)?;
        let carry = mul::mul_word_in_place_with_carry(&mut buffer, radix_info.range_per_word, next);
        if carry != 0 {
            buffer.push(carry);
        }
    }
    Ok(buffer.into())
}

/// Parse an unsigned string to [UBig].
///
/// This result will usually not fit in CHUNK_LEN words.
fn parse_large(bytes: &[u8], radix: Digit) -> Result<UBig, ParseError> {
    debug_assert!(radix::is_radix_valid(radix) && !radix.is_power_of_two());
    let radix_info = radix::radix_info(radix);
    let chunk_bytes = CHUNK_LEN * radix_info.digits_per_word;
    assert!(bytes.len() > chunk_bytes);

    // Calculate radix^(CHUNK_LEN<<i).
    let mut radix_powers = vec![UBig::from_word(radix_info.range_per_word).pow(CHUNK_LEN)];

    // while (chunk_bytes << radix_powers.len()) < bytes.len()
    // To avoid overflow:
    while chunk_bytes <= (bytes.len() - 1) >> radix_powers.len() {
        let prev = radix_powers.last().unwrap();
        let new = prev * prev;
        radix_powers.push(new);
    }

    parse_large_divide_conquer(bytes, radix, chunk_bytes, &radix_powers)
}

/// Convert an unsigned string to [UBig].
///
/// `radix_powers` contains radix^n for n = chunk digits << i
fn parse_large_divide_conquer(
    bytes: &[u8],
    radix: Digit,
    chunk_bytes: usize,
    radix_powers: &[UBig],
) -> Result<UBig, ParseError> {
    debug_assert!(bytes.len() <= chunk_bytes << radix_powers.len());

    match radix_powers.split_last() {
        None => parse_chunk(bytes, radix),
        Some((radix_power, radix_powers)) => {
            let bytes_lo_len = chunk_bytes << radix_powers.len();
            if bytes.len() <= bytes_lo_len {
                parse_large_divide_conquer(bytes, radix, chunk_bytes, radix_powers)
            } else {
                let (bytes_hi, bytes_lo) = bytes.split_at(bytes.len() - bytes_lo_len);
                let res_hi =
                    parse_large_divide_conquer(bytes_hi, radix, chunk_bytes, radix_powers)?;
                let res_lo =
                    parse_large_divide_conquer(bytes_lo, radix, chunk_bytes, radix_powers)?;
                Ok(res_hi * radix_power + res_lo)
            }
        }
    }
}