ethnum/
fmt.rs

1//! Module with common integer formatting logic for implementing the standard
2//! library `core::fmt` traits.
3//!
4//! Most of these implementations were ported from the Rust standard library's
5//! implementation for primitive integer types:
6//! <https://doc.rust-lang.org/src/core/fmt/num.rs.html>
7
8use crate::uint::U256;
9use core::{fmt, mem::MaybeUninit, ptr, slice, str};
10
11pub(crate) trait GenericRadix: Sized {
12    const BASE: u8;
13    const PREFIX: &'static str;
14    fn digit(x: u8) -> u8;
15    fn fmt_u256(&self, mut x: U256, is_nonnegative: bool, f: &mut fmt::Formatter) -> fmt::Result {
16        // The radix can be as low as 2, so we need a buffer of at least 256
17        // characters for a base 2 number.
18        let zero = U256::ZERO;
19        let mut buf = [MaybeUninit::<u8>::uninit(); 256];
20        let mut curr = buf.len();
21        let base = U256::from(Self::BASE);
22        // Accumulate each digit of the number from the least significant
23        // to the most significant figure.
24        for byte in buf.iter_mut().rev() {
25            let n = x % base; // Get the current place value.
26            x /= base; // Deaccumulate the number.
27            byte.write(Self::digit(n.as_u8())); // Store the digit in the buffer.
28            curr -= 1;
29            if x == zero {
30                // No more digits left to accumulate.
31                break;
32            };
33        }
34        let buf = &buf[curr..];
35        // SAFETY: The only chars in `buf` are created by `Self::digit` which are assumed to be
36        // valid UTF-8
37        let buf = unsafe {
38            str::from_utf8_unchecked(slice::from_raw_parts(
39                &buf[0] as *const _ as *const u8,
40                buf.len(),
41            ))
42        };
43        f.pad_integral(is_nonnegative, Self::PREFIX, buf)
44    }
45}
46
47/// A binary (base 2) radix
48#[derive(Clone, PartialEq)]
49pub(crate) struct Binary;
50
51/// An octal (base 8) radix
52#[derive(Clone, PartialEq)]
53pub(crate) struct Octal;
54
55/// A hexadecimal (base 16) radix, formatted with lower-case characters
56#[derive(Clone, PartialEq)]
57pub(crate) struct LowerHex;
58
59/// A hexadecimal (base 16) radix, formatted with upper-case characters
60#[derive(Clone, PartialEq)]
61pub(crate) struct UpperHex;
62
63macro_rules! radix {
64    ($T:ident, $base:expr, $prefix:expr, $($x:pat => $conv:expr),+) => {
65        impl GenericRadix for $T {
66            const BASE: u8 = $base;
67            const PREFIX: &'static str = $prefix;
68            fn digit(x: u8) -> u8 {
69                match x {
70                    $($x => $conv,)+
71                    x => panic!("number not in the range 0..={}: {}", Self::BASE - 1, x),
72                }
73            }
74        }
75    }
76}
77
78radix! { Binary,    2, "0b", x @  0 ..=  1 => b'0' + x }
79radix! { Octal,     8, "0o", x @  0 ..=  7 => b'0' + x }
80radix! { LowerHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'a' + (x - 10) }
81radix! { UpperHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'A' + (x - 10) }
82
83const DEC_DIGITS_LUT: &[u8; 200] = b"\
84    0001020304050607080910111213141516171819\
85    2021222324252627282930313233343536373839\
86    4041424344454647484950515253545556575859\
87    6061626364656667686970717273747576777879\
88    8081828384858687888990919293949596979899";
89
90pub(crate) fn fmt_u256(mut n: U256, is_nonnegative: bool, f: &mut fmt::Formatter) -> fmt::Result {
91    // 2^256 is about 1*10^78, so 79 gives an extra byte of space
92    let mut buf = [MaybeUninit::<u8>::uninit(); 79];
93    let mut curr = buf.len() as isize;
94    let buf_ptr = &mut buf[0] as *mut _ as *mut u8;
95    let lut_ptr = DEC_DIGITS_LUT.as_ptr();
96
97    // SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
98    // can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
99    // that it's OK to copy into `buf_ptr`, notice that at the beginning
100    // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
101    // each step this is kept the same as `n` is divided. Since `n` is always
102    // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
103    // is safe to access.
104    unsafe {
105        // eagerly decode 4 characters at a time
106        while n >= 10000 {
107            let (q, r) = n.div_rem(U256::new(10000));
108            n = q;
109            let rem = r.as_isize();
110
111            let d1 = (rem / 100) << 1;
112            let d2 = (rem % 100) << 1;
113            curr -= 4;
114
115            // We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
116            // otherwise `curr < 0`. But then `n` was originally at least `10000^10`
117            // which is `10^40 > 2^128 > n`.
118            ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
119            ptr::copy_nonoverlapping(lut_ptr.offset(d2), buf_ptr.offset(curr + 2), 2);
120        }
121
122        // if we reach here numbers are <= 9999, so at most 4 chars long
123        let mut n = n.as_isize(); // possibly reduce 64bit math
124
125        // decode 2 more chars, if > 2 chars
126        if n >= 100 {
127            let d1 = (n % 100) << 1;
128            n /= 100;
129            curr -= 2;
130            ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
131        }
132
133        // decode last 1 or 2 chars
134        if n < 10 {
135            curr -= 1;
136            *buf_ptr.offset(curr) = (n as u8) + b'0';
137        } else {
138            let d1 = n << 1;
139            curr -= 2;
140            ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
141        }
142    }
143
144    // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
145    // UTF-8 since `DEC_DIGITS_LUT` is
146    let buf_slice = unsafe {
147        str::from_utf8_unchecked(slice::from_raw_parts(
148            buf_ptr.offset(curr),
149            buf.len() - curr as usize,
150        ))
151    };
152    f.pad_integral(is_nonnegative, "", buf_slice)
153}
ethnum/fmt.rs

ethnum/
fmt.rs
