dashu_int/
radix.rs

1//! Information about radixes.
2
3use crate::{
4    arch::word::Word,
5    math::{max_exp_in_dword, max_exp_in_word},
6};
7use static_assertions::const_assert;
8
9type FastDivideSmall = num_modular::PreMulInv1by1<Word>;
10type FastDivideNormalized = num_modular::Normalized2by1Divisor<Word>;
11
12/// Digit and radix type, it's always u32.
13pub type Digit = u32;
14
15/// Minimum supported radix.
16pub const MIN_RADIX: Digit = 2;
17
18/// Maximum supported radix.
19pub const MAX_RADIX: Digit = 36;
20
21/// Is a radix in valid range?
22#[inline]
23pub const fn is_radix_valid(radix: Digit) -> bool {
24    MIN_RADIX <= radix && radix <= MAX_RADIX
25}
26
27const_assert!(b'a' > b'0' + 10 && b'A' > b'0' + 10);
28
29/// u8 representation is: how much digits >= 10 should be offset by in ASCII.
30#[derive(Clone, Copy, Eq, PartialEq)]
31#[repr(u8)]
32pub enum DigitCase {
33    NoLetters = 0,
34    Lower = b'a' - b'0' - 10,
35    Upper = b'A' - b'0' - 10,
36}
37
38/// Converts a byte (ASCII) representation of a digit to its value.
39///
40/// The radix has to be in range 2..36 (inclusive), and the digit will
41/// be parsed with insensitive case.
42#[inline]
43pub const fn digit_from_ascii_byte(byte: u8, radix: Digit) -> Option<Digit> {
44    assert!(is_radix_valid(radix));
45
46    let res = match byte {
47        c @ b'0'..=b'9' => (c - b'0') as Digit,
48        c @ b'a'..=b'z' => (c - b'a') as Digit + 10,
49        c @ b'A'..=b'Z' => (c - b'A') as Digit + 10,
50        _ => return None,
51    };
52    if res < radix {
53        Some(res)
54    } else {
55        None
56    }
57}
58
59/// Properties of a given radix.
60#[derive(Clone, Copy)]
61pub struct RadixInfo {
62    /// The number of digits that can always fit in a `Word`.
63    pub(crate) digits_per_word: usize,
64
65    /// Radix to the power of `max_digits`.
66    /// Only for non-power-of-2 radixes.
67    pub(crate) range_per_word: Word,
68
69    /// Faster division by `radix`.
70    pub(crate) fast_div_radix: FastDivideSmall,
71
72    /// Faster division by normalized range_per_word.
73    /// Only for non-power-of-2 radixes.
74    pub(crate) fast_div_range_per_word: FastDivideNormalized,
75}
76
77/// Radix info for base 10
78pub const RADIX10_INFO: RadixInfo = RadixInfo::for_radix(10);
79
80/// Maximum number of digits that a `Word` can ever have for any non-power-of-2 radix.
81pub const MAX_WORD_DIGITS_NON_POW_2: usize = max_exp_in_word(3).0 + 1;
82/// Maximum number of digits that a `DoubleWord` can ever have for any non-power-of-2 radix.
83pub const MAX_DWORD_DIGITS_NON_POW_2: usize = max_exp_in_dword(3).0 + 1;
84
85/// Get [RadixInfo] for a given radix.
86///
87/// This method is not specialized for power of two.
88#[inline]
89pub fn radix_info(radix: Digit) -> RadixInfo {
90    debug_assert!(is_radix_valid(radix));
91
92    match radix {
93        10 => RADIX10_INFO,
94        _ => RadixInfo::for_radix(radix),
95    }
96}
97
98impl RadixInfo {
99    const fn for_radix(radix: Digit) -> RadixInfo {
100        let (digits_per_word, range_per_word) = max_exp_in_word(radix as Word);
101        let shift = range_per_word.leading_zeros();
102        let fast_div_radix = FastDivideSmall::new(radix as Word);
103        let fast_div_range_per_word = FastDivideNormalized::new(range_per_word << shift);
104        RadixInfo {
105            digits_per_word,
106            range_per_word,
107            fast_div_radix,
108            fast_div_range_per_word,
109        }
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn test_digit_from_utf8_byte() {
119        assert_eq!(digit_from_ascii_byte(b'7', 10), Some(7));
120        assert_eq!(digit_from_ascii_byte(b'a', 16), Some(10));
121        assert_eq!(digit_from_ascii_byte(b'z', 36), Some(35));
122        assert_eq!(digit_from_ascii_byte(b'Z', 36), Some(35));
123        assert_eq!(digit_from_ascii_byte(b'?', 10), None);
124        assert_eq!(digit_from_ascii_byte(b'a', 10), None);
125        assert_eq!(digit_from_ascii_byte(b'z', 35), None);
126        assert_eq!(digit_from_ascii_byte(255, 35), None);
127    }
128}
dashu_int/radix.rs

dashu_int/
radix.rs
