dashu_int/fmt/
power_two.rs

1//! Format in a power-of-two radix.
2
3use super::{digit_writer::DigitWriter, InRadixWriter, PreparedForFormatting};
4use crate::{
5    arch::word::{DoubleWord, Word},
6    math,
7    primitive::{shrink_dword, DWORD_BITS_USIZE, WORD_BITS, WORD_BITS_USIZE},
8    radix::{self, Digit},
9    repr::TypedReprRef::*,
10};
11use core::fmt::{self, Formatter};
12
13impl InRadixWriter<'_> {
14    /// Radix must be a power of 2.
15    pub fn fmt_power_two(&self, f: &mut Formatter) -> fmt::Result {
16        debug_assert!(radix::is_radix_valid(self.radix) && self.radix.is_power_of_two());
17
18        match self.magnitude {
19            RefSmall(dword) => {
20                if let Some(word) = shrink_dword(dword) {
21                    let mut prepared = PreparedWord::new(word, self.radix);
22                    self.format_prepared(f, &mut prepared)
23                } else {
24                    let mut prepared = PreparedDword::new(dword, self.radix);
25                    self.format_prepared(f, &mut prepared)
26                }
27            }
28            RefLarge(words) => {
29                let mut prepared = PreparedLarge::new(words, self.radix);
30                self.format_prepared(f, &mut prepared)
31            }
32        }
33    }
34}
35
36/// A `Word` prepared for formatting.
37struct PreparedWord {
38    word: Word,
39    log_radix: u32,
40    width: usize,
41}
42
43impl PreparedWord {
44    /// Prepare a `Word` for formatting.
45    fn new(word: Word, radix: Digit) -> PreparedWord {
46        debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());
47        let log_radix = radix.trailing_zeros();
48        let width = math::ceil_div(math::bit_len(word), log_radix).max(1) as usize;
49
50        PreparedWord {
51            word,
52            log_radix,
53            width,
54        }
55    }
56}
57
58impl PreparedForFormatting for PreparedWord {
59    fn width(&self) -> usize {
60        self.width
61    }
62
63    fn write(&mut self, digit_writer: &mut DigitWriter) -> fmt::Result {
64        let mask: Word = math::ones_word(self.log_radix);
65        let mut digits = [0; WORD_BITS_USIZE];
66        for idx in 0..self.width {
67            let digit = ((self.word >> (idx as u32 * self.log_radix)) & mask) as u8;
68            digits[self.width - 1 - idx] = digit;
69        }
70        digit_writer.write(&digits[..self.width])
71    }
72}
73
74/// A large number prepared for formatting.
75struct PreparedDword {
76    dword: DoubleWord,
77    log_radix: u32,
78    width: usize,
79}
80
81impl PreparedDword {
82    /// Prepare a `DoubleWord` for formatting.
83    fn new(dword: DoubleWord, radix: Digit) -> PreparedDword {
84        debug_assert!(dword > Word::MAX as DoubleWord);
85        debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());
86        let log_radix = radix.trailing_zeros();
87        let width = math::ceil_div(math::bit_len(dword), log_radix).max(1) as usize;
88
89        PreparedDword {
90            dword,
91            log_radix,
92            width,
93        }
94    }
95}
96
97impl PreparedForFormatting for PreparedDword {
98    fn width(&self) -> usize {
99        self.width
100    }
101
102    fn write(&mut self, digit_writer: &mut DigitWriter) -> fmt::Result {
103        let mask: DoubleWord = math::ones_dword(self.log_radix);
104        let mut digits = [0; DWORD_BITS_USIZE];
105        for idx in 0..self.width {
106            let digit = ((self.dword >> (idx as u32 * self.log_radix)) & mask) as u8;
107            digits[self.width - 1 - idx] = digit;
108        }
109        digit_writer.write(&digits[..self.width])
110    }
111}
112
113/// A large number prepared for formatting.
114struct PreparedLarge<'a> {
115    words: &'a [Word],
116    log_radix: u32,
117    width: usize,
118}
119
120impl PreparedLarge<'_> {
121    /// Prepare a large number for formatting.
122    fn new(words: &[Word], radix: Digit) -> PreparedLarge {
123        debug_assert!(radix::is_radix_valid(radix) && radix.is_power_of_two());
124        let log_radix = radix.trailing_zeros();
125
126        // No overflow because words.len() * WORD_BITS <= usize::MAX for
127        // words.len() <= Buffer::MAX_CAPACITY.
128        let width = math::ceil_div(
129            words.len() * WORD_BITS_USIZE - words.last().unwrap().leading_zeros() as usize,
130            log_radix as usize,
131        )
132        .max(1);
133
134        PreparedLarge {
135            words,
136            log_radix,
137            width,
138        }
139    }
140}
141
142impl PreparedForFormatting for PreparedLarge<'_> {
143    fn width(&self) -> usize {
144        self.width
145    }
146
147    fn write(&mut self, digit_writer: &mut DigitWriter) -> fmt::Result {
148        let mask: Word = math::ones_word(self.log_radix);
149
150        let mut it = self.words.iter().rev();
151        let mut word = it.next().unwrap();
152        let mut bits = (self.width * self.log_radix as usize
153            - (self.words.len() - 1) * WORD_BITS_USIZE) as u32;
154
155        loop {
156            let digit;
157            if bits < self.log_radix {
158                match it.next() {
159                    Some(w) => {
160                        let extra_bits = self.log_radix - bits;
161                        bits = WORD_BITS - extra_bits;
162                        digit = ((word << extra_bits | w >> bits) & mask) as u8;
163                        word = w;
164                    }
165                    None => break,
166                }
167            } else {
168                bits -= self.log_radix;
169                digit = ((word >> bits) & mask) as u8;
170            }
171            digit_writer.write(&[digit])?;
172        }
173        debug_assert_eq!(bits, 0);
174        Ok(())
175    }
176}
dashu_int/fmt/power_two.rs

dashu_int/fmt/
power_two.rs
