oxinum_int/native/
radix.rs

1//! Radix conversion (`to_radix`, `from_str_radix`) + `Display`/`Debug`/
2//! `LowerHex`/`UpperHex`/`Octal`/`Binary` for [`BigUint`] and [`BigInt`].
3//!
4//! For powers-of-2 radices (2, 4, 8, 16, 32) we use direct bit-walking via
5//! shifts. For all other radices in 2..=36, we use repeated division by
6//! `radix^k` where `k` is the largest power such that `radix^k` fits in `u64`.
7//!
8//! ## Alternate-form formatting
9//!
10//! All four traits (`LowerHex`, `UpperHex`, `Octal`, `Binary`) support the
11//! `{:#}` alternate form: the prefix `0x`, `0o`, or `0b` is emitted via
12//! `Formatter::pad_integral`, which also handles width, fill, and sign.
13
14use super::int::BigInt;
15use super::uint::BigUint;
16use crate::OxiNumError;
17use crate::OxiNumResult;
18use std::fmt;
19
20impl BigUint {
21    /// Format this value as a string in the given `radix` (2..=36).
22    ///
23    /// # Errors
24    ///
25    /// Returns [`OxiNumError::InvalidRadix`] if `radix < 2` or `radix > 36`.
26    ///
27    /// # Examples
28    ///
29    /// ```
30    /// use oxinum_int::native::BigUint;
31    /// let n = BigUint::from_u64(255);
32    /// assert_eq!(n.to_radix(16).unwrap(), "ff");
33    /// assert_eq!(n.to_radix(2).unwrap(), "11111111");
34    /// ```
35    pub fn to_radix(&self, radix: u32) -> OxiNumResult<String> {
36        if !(2..=36).contains(&radix) {
37            return Err(OxiNumError::InvalidRadix(radix));
38        }
39        if self.is_zero() {
40            return Ok("0".to_string());
41        }
42        if radix.is_power_of_two() {
43            return Ok(self.to_radix_pow2(radix));
44        }
45        Ok(self.to_radix_general(radix))
46    }
47
48    /// Parse a `BigUint` from `src` in the given `radix` (2..=36).
49    ///
50    /// Leading/trailing whitespace is rejected. Digits use lowercase or
51    /// uppercase letters (case-insensitive) for radices > 10.
52    ///
53    /// # Errors
54    ///
55    /// Returns [`OxiNumError::InvalidRadix`] if `radix < 2` or `radix > 36`,
56    /// or [`OxiNumError::Parse`] on invalid digits.
57    ///
58    /// # Examples
59    ///
60    /// ```
61    /// use oxinum_int::native::BigUint;
62    /// let n = BigUint::from_str_radix("ff", 16).unwrap();
63    /// assert_eq!(n, BigUint::from_u64(255));
64    /// ```
65    pub fn from_str_radix(src: &str, radix: u32) -> OxiNumResult<BigUint> {
66        if !(2..=36).contains(&radix) {
67            return Err(OxiNumError::InvalidRadix(radix));
68        }
69        if src.is_empty() {
70            return Err(OxiNumError::Parse("empty string".into()));
71        }
72        // Chunk by k = largest power so that radix^k fits in u64.
73        // (For pow-2 radices we still use this approach for simplicity.)
74        let (chunk_size, chunk_base) = chunk_for_radix(radix);
75        let bytes = src.as_bytes();
76        let total = bytes.len();
77        let chunk_base_big = BigUint::from_u64(chunk_base);
78        let mut idx = 0usize;
79        let first_chunk_len = if total % chunk_size == 0 {
80            chunk_size
81        } else {
82            total % chunk_size
83        };
84        // Process first (short) chunk:
85        let first_str = std::str::from_utf8(&bytes[idx..idx + first_chunk_len])
86            .map_err(|_| OxiNumError::Parse("invalid UTF-8".into()))?;
87        let first_val: u64 = u64::from_str_radix(first_str, radix)
88            .map_err(|e| OxiNumError::Parse(format!("{e}").into()))?;
89        let mut acc = BigUint::from_u64(first_val);
90        idx += first_chunk_len;
91        // Compute the per-chunk multiplier `radix^chunk_size` once.
92        while idx < total {
93            let chunk_str = std::str::from_utf8(&bytes[idx..idx + chunk_size])
94                .map_err(|_| OxiNumError::Parse("invalid UTF-8".into()))?;
95            let val: u64 = u64::from_str_radix(chunk_str, radix)
96                .map_err(|e| OxiNumError::Parse(format!("{e}").into()))?;
97            acc = &acc * &chunk_base_big;
98            acc = &acc + &BigUint::from_u64(val);
99            idx += chunk_size;
100        }
101        Ok(acc)
102    }
103
104    // --------------------------------------------------------------------
105    // Helpers
106    // --------------------------------------------------------------------
107
108    fn to_radix_pow2(&self, radix: u32) -> String {
109        // bits_per_digit = log2(radix).
110        let bits_per_digit = radix.trailing_zeros() as u64;
111        // We need the full binary representation, then group bits from LSB.
112        let total_bits = self.bit_length();
113        // Number of digits in the output:
114        let n_digits = total_bits.div_ceil(bits_per_digit) as usize;
115        let mut digits: Vec<u8> = Vec::with_capacity(n_digits);
116        let mask: u64 = (1u64 << bits_per_digit) - 1;
117        for i in 0..n_digits {
118            let bit_pos = (i as u64) * bits_per_digit;
119            let limb_idx = (bit_pos / 64) as usize;
120            let bit_in_limb = bit_pos % 64;
121            let mut val: u64 = (self.limbs[limb_idx] >> bit_in_limb) & mask;
122            // If the digit spans two limbs, fetch the bridging bits.
123            let bits_in_first = (64u64).saturating_sub(bit_in_limb);
124            if bits_in_first < bits_per_digit && limb_idx + 1 < self.limbs.len() {
125                let needed = bits_per_digit - bits_in_first;
126                let upper_mask = (1u64 << needed) - 1;
127                let extra = self.limbs[limb_idx + 1] & upper_mask;
128                val |= extra << bits_in_first;
129            }
130            digits.push(digit_to_char(val as u32));
131        }
132        // digits is LSB-first; reverse for MSB-first.
133        digits.reverse();
134        // Strip leading zero digits (we sized for ceil; the topmost might be 0).
135        while digits.first() == Some(&b'0') && digits.len() > 1 {
136            digits.remove(0);
137        }
138        String::from_utf8(digits).unwrap_or_else(|_| String::from("<radix-output-utf8-bug>"))
139    }
140
141    fn to_radix_general(&self, radix: u32) -> String {
142        let (chunk_size, chunk_base) = chunk_for_radix(radix);
143        let chunk_base_big = BigUint::from_u64(chunk_base);
144        let mut acc = self.clone();
145        // Accumulate raw chunk values (each < chunk_base).
146        let mut chunks: Vec<u64> = Vec::new();
147        while !acc.is_zero() {
148            let (q, r) = super::div::divrem(&acc, &chunk_base_big);
149            chunks.push(r.to_u64().unwrap_or(0));
150            acc = q;
151        }
152        // Build the string: most-significant chunk has no leading zeros;
153        // every subsequent chunk must be zero-padded to `chunk_size` digits.
154        let mut out = String::with_capacity(chunks.len() * chunk_size);
155        if let Some(&top) = chunks.last() {
156            // Top: no padding.
157            out.push_str(&format_in_radix(top, radix, 0));
158        }
159        for &c in chunks.iter().rev().skip(1) {
160            out.push_str(&format_in_radix(c, radix, chunk_size));
161        }
162        out
163    }
164}
165
166/// Largest `(k, radix^k)` such that `radix^k` fits in a `u64`.
167fn chunk_for_radix(radix: u32) -> (usize, u64) {
168    let r = radix as u64;
169    let mut k: usize = 1;
170    let mut acc: u64 = r;
171    loop {
172        match acc.checked_mul(r) {
173            Some(v) => {
174                acc = v;
175                k += 1;
176            }
177            None => return (k, acc),
178        }
179    }
180}
181
182/// Format `value` in `radix`, padding with leading zeros to width `min_width`.
183fn format_in_radix(value: u64, radix: u32, min_width: usize) -> String {
184    if value == 0 {
185        // Zero-padded zero of width `min_width` (could be 0 for top chunk).
186        return "0".repeat(min_width.max(1));
187    }
188    let mut digits: Vec<u8> = Vec::new();
189    let mut v = value;
190    while v != 0 {
191        digits.push(digit_to_char((v % radix as u64) as u32));
192        v /= radix as u64;
193    }
194    while digits.len() < min_width {
195        digits.push(b'0');
196    }
197    digits.reverse();
198    String::from_utf8(digits).unwrap_or_else(|_| "0".to_string())
199}
200
201fn digit_to_char(d: u32) -> u8 {
202    debug_assert!(d < 36);
203    match d {
204        0..=9 => b'0' + d as u8,
205        10..=35 => b'a' + (d - 10) as u8,
206        _ => b'?',
207    }
208}
209
210// ---------------------------------------------------------------------------
211// Display / Debug
212// ---------------------------------------------------------------------------
213
214impl fmt::Display for BigUint {
215    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
216        match self.to_radix(10) {
217            Ok(s) => f.write_str(&s),
218            Err(_) => f.write_str("<BigUint-radix-error>"),
219        }
220    }
221}
222
223impl fmt::Debug for BigUint {
224    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
225        // For debug, show decimal + limb count for diagnosability.
226        write!(f, "BigUint({})", self)?;
227        if !self.limbs.is_empty() {
228            write!(f, " [{}lm]", self.limbs.len())?;
229        }
230        Ok(())
231    }
232}
233
234// ---------------------------------------------------------------------------
235// LowerHex / UpperHex / Octal / Binary for BigUint
236// ---------------------------------------------------------------------------
237
238impl fmt::LowerHex for BigUint {
239    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
240        let digits = self.to_radix(16).map_err(|_| fmt::Error)?;
241        f.pad_integral(true, "0x", &digits)
242    }
243}
244
245impl fmt::UpperHex for BigUint {
246    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
247        let digits = self.to_radix(16).map_err(|_| fmt::Error)?;
248        // pad_integral with UpperHex prefix is still "0x" (std matches this).
249        f.pad_integral(true, "0x", &digits.to_ascii_uppercase())
250    }
251}
252
253impl fmt::Octal for BigUint {
254    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255        let digits = self.to_radix(8).map_err(|_| fmt::Error)?;
256        f.pad_integral(true, "0o", &digits)
257    }
258}
259
260impl fmt::Binary for BigUint {
261    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
262        let digits = self.to_radix(2).map_err(|_| fmt::Error)?;
263        f.pad_integral(true, "0b", &digits)
264    }
265}
266
267// ---------------------------------------------------------------------------
268// LowerHex / UpperHex / Octal / Binary for BigInt
269//
270// BigInt emits `sign + magnitude-in-radix`. The `pad_integral` flag
271// `is_nonnegative` drives the sign; the prefix is the same as for BigUint.
272// ---------------------------------------------------------------------------
273
274impl fmt::LowerHex for BigInt {
275    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
276        let digits = self.magnitude().to_radix(16).map_err(|_| fmt::Error)?;
277        f.pad_integral(!self.is_negative(), "0x", &digits)
278    }
279}
280
281impl fmt::UpperHex for BigInt {
282    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
283        let digits = self.magnitude().to_radix(16).map_err(|_| fmt::Error)?;
284        f.pad_integral(!self.is_negative(), "0x", &digits.to_ascii_uppercase())
285    }
286}
287
288impl fmt::Octal for BigInt {
289    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
290        let digits = self.magnitude().to_radix(8).map_err(|_| fmt::Error)?;
291        f.pad_integral(!self.is_negative(), "0o", &digits)
292    }
293}
294
295impl fmt::Binary for BigInt {
296    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
297        let digits = self.magnitude().to_radix(2).map_err(|_| fmt::Error)?;
298        f.pad_integral(!self.is_negative(), "0b", &digits)
299    }
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305
306    #[test]
307    fn to_radix_zero() {
308        assert_eq!(BigUint::zero().to_radix(10).expect("radix"), "0");
309        assert_eq!(BigUint::zero().to_radix(2).expect("radix"), "0");
310        assert_eq!(BigUint::zero().to_radix(16).expect("radix"), "0");
311    }
312
313    #[test]
314    fn to_radix_decimal_small() {
315        let n = BigUint::from_u64(12345);
316        assert_eq!(n.to_radix(10).expect("radix"), "12345");
317    }
318
319    #[test]
320    fn to_radix_hex() {
321        let n = BigUint::from_u64(0xDEAD_BEEF);
322        assert_eq!(n.to_radix(16).expect("radix"), "deadbeef");
323    }
324
325    #[test]
326    fn to_radix_binary() {
327        let n = BigUint::from_u64(0b1010_1100);
328        assert_eq!(n.to_radix(2).expect("radix"), "10101100");
329    }
330
331    #[test]
332    fn radix_invalid() {
333        assert!(BigUint::from_u64(10).to_radix(1).is_err());
334        assert!(BigUint::from_u64(10).to_radix(37).is_err());
335        assert!(BigUint::from_str_radix("123", 1).is_err());
336    }
337
338    #[test]
339    fn radix_roundtrip_many() {
340        let n = BigUint::from_le_limbs(&[0xDEAD_BEEF_CAFE_BABE, 0x1234_5678_9ABC_DEF0, 0x42]);
341        for r in [2, 8, 10, 16, 36, 7, 13] {
342            let s = n.to_radix(r).expect("to_radix");
343            let m = BigUint::from_str_radix(&s, r).expect("from_radix");
344            assert_eq!(m, n, "roundtrip failed at radix {r}");
345        }
346    }
347
348    #[test]
349    fn display_matches_decimal() {
350        let n = BigUint::from_u64(12_345_678_901_234_567_890u64);
351        assert_eq!(format!("{n}"), "12345678901234567890");
352    }
353}
oxinum_int/native/radix.rs

oxinum_int/native/
radix.rs
