core/fmt/
num.rs

1//! Integer and floating-point number formatting
2
3use crate::mem::MaybeUninit;
4use crate::num::fmt as numfmt;
5use crate::ops::{Div, Rem, Sub};
6use crate::{fmt, ptr, slice, str};
7
8#[doc(hidden)]
9trait DisplayInt:
10    PartialEq + PartialOrd + Div<Output = Self> + Rem<Output = Self> + Sub<Output = Self> + Copy
11{
12    fn zero() -> Self;
13    fn from_u8(u: u8) -> Self;
14    fn to_u8(&self) -> u8;
15    #[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
16    fn to_u32(&self) -> u32;
17    fn to_u64(&self) -> u64;
18    fn to_u128(&self) -> u128;
19}
20
21macro_rules! impl_int {
22    ($($t:ident)*) => (
23        $(impl DisplayInt for $t {
24            fn zero() -> Self { 0 }
25            fn from_u8(u: u8) -> Self { u as Self }
26            fn to_u8(&self) -> u8 { *self as u8 }
27            #[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
28            fn to_u32(&self) -> u32 { *self as u32 }
29            fn to_u64(&self) -> u64 { *self as u64 }
30            fn to_u128(&self) -> u128 { *self as u128 }
31        })*
32    )
33}
34
35impl_int! {
36    i8 i16 i32 i64 i128 isize
37    u8 u16 u32 u64 u128 usize
38}
39
40/// A type that represents a specific radix
41///
42/// # Safety
43///
44/// `digit` must return an ASCII character.
45#[doc(hidden)]
46unsafe trait GenericRadix: Sized {
47    /// The number of digits.
48    const BASE: u8;
49
50    /// A radix-specific prefix string.
51    const PREFIX: &'static str;
52
53    /// Converts an integer to corresponding radix digit.
54    fn digit(x: u8) -> u8;
55
56    /// Format an integer using the radix using a formatter.
57    fn fmt_int<T: DisplayInt>(&self, mut x: T, f: &mut fmt::Formatter<'_>) -> fmt::Result {
58        // The radix can be as low as 2, so we need a buffer of at least 128
59        // characters for a base 2 number.
60        let zero = T::zero();
61        let is_nonnegative = x >= zero;
62        let mut buf = [MaybeUninit::<u8>::uninit(); 128];
63        let mut curr = buf.len();
64        let base = T::from_u8(Self::BASE);
65        if is_nonnegative {
66            // Accumulate each digit of the number from the least significant
67            // to the most significant figure.
68            loop {
69                let n = x % base; // Get the current place value.
70                x = x / base; // Deaccumulate the number.
71                curr -= 1;
72                buf[curr].write(Self::digit(n.to_u8())); // Store the digit in the buffer.
73                if x == zero {
74                    // No more digits left to accumulate.
75                    break;
76                };
77            }
78        } else {
79            // Do the same as above, but accounting for two's complement.
80            loop {
81                let n = zero - (x % base); // Get the current place value.
82                x = x / base; // Deaccumulate the number.
83                curr -= 1;
84                buf[curr].write(Self::digit(n.to_u8())); // Store the digit in the buffer.
85                if x == zero {
86                    // No more digits left to accumulate.
87                    break;
88                };
89            }
90        }
91        // SAFETY: `curr` is initialized to `buf.len()` and is only decremented, so it can't overflow. It is
92        // decremented exactly once for each digit. Since u128 is the widest fixed width integer format supported,
93        // the maximum number of digits (bits) is 128 for base-2, so `curr` won't underflow as well.
94        let buf = unsafe { buf.get_unchecked(curr..) };
95        // SAFETY: The only chars in `buf` are created by `Self::digit` which are assumed to be
96        // valid UTF-8
97        let buf = unsafe {
98            str::from_utf8_unchecked(slice::from_raw_parts(
99                MaybeUninit::slice_as_ptr(buf),
100                buf.len(),
101            ))
102        };
103        f.pad_integral(is_nonnegative, Self::PREFIX, buf)
104    }
105}
106
107/// A binary (base 2) radix
108#[derive(Clone, PartialEq)]
109struct Binary;
110
111/// An octal (base 8) radix
112#[derive(Clone, PartialEq)]
113struct Octal;
114
115/// A hexadecimal (base 16) radix, formatted with lower-case characters
116#[derive(Clone, PartialEq)]
117struct LowerHex;
118
119/// A hexadecimal (base 16) radix, formatted with upper-case characters
120#[derive(Clone, PartialEq)]
121struct UpperHex;
122
123macro_rules! radix {
124    ($T:ident, $base:expr, $prefix:expr, $($x:pat => $conv:expr),+) => {
125        unsafe impl GenericRadix for $T {
126            const BASE: u8 = $base;
127            const PREFIX: &'static str = $prefix;
128            fn digit(x: u8) -> u8 {
129                match x {
130                    $($x => $conv,)+
131                    x => panic!("number not in the range 0..={}: {}", Self::BASE - 1, x),
132                }
133            }
134        }
135    }
136}
137
138radix! { Binary,    2, "0b", x @  0 ..=  1 => b'0' + x }
139radix! { Octal,     8, "0o", x @  0 ..=  7 => b'0' + x }
140radix! { LowerHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'a' + (x - 10) }
141radix! { UpperHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'A' + (x - 10) }
142
143macro_rules! int_base {
144    (fmt::$Trait:ident for $T:ident as $U:ident -> $Radix:ident) => {
145        #[stable(feature = "rust1", since = "1.0.0")]
146        impl fmt::$Trait for $T {
147            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
148                $Radix.fmt_int(*self as $U, f)
149            }
150        }
151    };
152}
153
154macro_rules! integer {
155    ($Int:ident, $Uint:ident) => {
156        int_base! { fmt::Binary   for $Int as $Uint  -> Binary }
157        int_base! { fmt::Octal    for $Int as $Uint  -> Octal }
158        int_base! { fmt::LowerHex for $Int as $Uint  -> LowerHex }
159        int_base! { fmt::UpperHex for $Int as $Uint  -> UpperHex }
160
161        int_base! { fmt::Binary   for $Uint as $Uint -> Binary }
162        int_base! { fmt::Octal    for $Uint as $Uint -> Octal }
163        int_base! { fmt::LowerHex for $Uint as $Uint -> LowerHex }
164        int_base! { fmt::UpperHex for $Uint as $Uint -> UpperHex }
165    };
166}
167integer! { isize, usize }
168integer! { i8, u8 }
169integer! { i16, u16 }
170integer! { i32, u32 }
171integer! { i64, u64 }
172integer! { i128, u128 }
173
174macro_rules! impl_Debug {
175    ($($T:ident)*) => {
176        $(
177            #[stable(feature = "rust1", since = "1.0.0")]
178            impl fmt::Debug for $T {
179                #[inline]
180                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
181                    if f.debug_lower_hex() {
182                        fmt::LowerHex::fmt(self, f)
183                    } else if f.debug_upper_hex() {
184                        fmt::UpperHex::fmt(self, f)
185                    } else {
186                        fmt::Display::fmt(self, f)
187                    }
188                }
189            }
190        )*
191    };
192}
193
194// 2 digit decimal look up table
195static DEC_DIGITS_LUT: &[u8; 200] = b"\
196      0001020304050607080910111213141516171819\
197      2021222324252627282930313233343536373839\
198      4041424344454647484950515253545556575859\
199      6061626364656667686970717273747576777879\
200      8081828384858687888990919293949596979899";
201
202macro_rules! impl_Display {
203    ($($signed:ident, $unsigned:ident,)* ; as $u:ident via $conv_fn:ident named $gen_name:ident) => {
204
205        $(
206        #[stable(feature = "rust1", since = "1.0.0")]
207        impl fmt::Display for $unsigned {
208            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
209                #[cfg(not(feature = "optimize_for_size"))]
210                {
211                    const MAX_DEC_N: usize = $unsigned::MAX.ilog10() as usize + 1;
212                    // Buffer decimals for $unsigned with right alignment.
213                    let mut buf = [MaybeUninit::<u8>::uninit(); MAX_DEC_N];
214
215                    f.pad_integral(true, "", self._fmt(&mut buf))
216                }
217                #[cfg(feature = "optimize_for_size")]
218                {
219                    $gen_name(self.$conv_fn(), true, f)
220                }
221            }
222        }
223
224        #[stable(feature = "rust1", since = "1.0.0")]
225        impl fmt::Display for $signed {
226            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
227                #[cfg(not(feature = "optimize_for_size"))]
228                {
229                    const MAX_DEC_N: usize = $unsigned::MAX.ilog10() as usize + 1;
230                    // Buffer decimals for $unsigned with right alignment.
231                    let mut buf = [MaybeUninit::<u8>::uninit(); MAX_DEC_N];
232
233                    f.pad_integral(*self >= 0, "", self.unsigned_abs()._fmt(&mut buf))
234                }
235                #[cfg(feature = "optimize_for_size")]
236                {
237                    return $gen_name(self.unsigned_abs().$conv_fn(), *self >= 0, f);
238                }
239            }
240        }
241
242        #[cfg(not(feature = "optimize_for_size"))]
243        impl $unsigned {
244            #[doc(hidden)]
245            #[unstable(
246                feature = "fmt_internals",
247                reason = "specialized method meant to only be used by `SpecToString` implementation",
248                issue = "none"
249            )]
250            pub fn _fmt<'a>(self, buf: &'a mut [MaybeUninit::<u8>]) -> &'a str {
251                // Count the number of bytes in buf that are not initialized.
252                let mut offset = buf.len();
253                // Consume the least-significant decimals from a working copy.
254                let mut remain = self;
255
256                // Format per four digits from the lookup table.
257                // Four digits need a 16-bit $unsigned or wider.
258                while size_of::<Self>() > 1 && remain > 999.try_into().expect("branch is not hit for types that cannot fit 999 (u8)") {
259                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
260                    // and the while condition ensures at least 4 more decimals.
261                    unsafe { core::hint::assert_unchecked(offset >= 4) }
262                    // SAFETY: The offset counts down from its initial buf.len()
263                    // without underflow due to the previous precondition.
264                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
265                    offset -= 4;
266
267                    // pull two pairs
268                    let scale: Self = 1_00_00.try_into().expect("branch is not hit for types that cannot fit 1E4 (u8)");
269                    let quad = remain % scale;
270                    remain /= scale;
271                    let pair1 = (quad / 100) as usize;
272                    let pair2 = (quad % 100) as usize;
273                    buf[offset + 0].write(DEC_DIGITS_LUT[pair1 * 2 + 0]);
274                    buf[offset + 1].write(DEC_DIGITS_LUT[pair1 * 2 + 1]);
275                    buf[offset + 2].write(DEC_DIGITS_LUT[pair2 * 2 + 0]);
276                    buf[offset + 3].write(DEC_DIGITS_LUT[pair2 * 2 + 1]);
277                }
278
279                // Format per two digits from the lookup table.
280                if remain > 9 {
281                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
282                    // and the if condition ensures at least 2 more decimals.
283                    unsafe { core::hint::assert_unchecked(offset >= 2) }
284                    // SAFETY: The offset counts down from its initial buf.len()
285                    // without underflow due to the previous precondition.
286                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
287                    offset -= 2;
288
289                    let pair = (remain % 100) as usize;
290                    remain /= 100;
291                    buf[offset + 0].write(DEC_DIGITS_LUT[pair * 2 + 0]);
292                    buf[offset + 1].write(DEC_DIGITS_LUT[pair * 2 + 1]);
293                }
294
295                // Format the last remaining digit, if any.
296                if remain != 0 || self == 0 {
297                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
298                    // and the if condition ensures (at least) 1 more decimals.
299                    unsafe { core::hint::assert_unchecked(offset >= 1) }
300                    // SAFETY: The offset counts down from its initial buf.len()
301                    // without underflow due to the previous precondition.
302                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
303                    offset -= 1;
304
305                    // Either the compiler sees that remain < 10, or it prevents
306                    // a boundary check up next.
307                    let last = (remain & 15) as usize;
308                    buf[offset].write(DEC_DIGITS_LUT[last * 2 + 1]);
309                    // not used: remain = 0;
310                }
311
312                // SAFETY: All buf content since offset is set.
313                let written = unsafe { buf.get_unchecked(offset..) };
314                // SAFETY: Writes use ASCII from the lookup table exclusively.
315                unsafe {
316                    str::from_utf8_unchecked(slice::from_raw_parts(
317                          MaybeUninit::slice_as_ptr(written),
318                          written.len(),
319                    ))
320                }
321            }
322        })*
323
324        #[cfg(feature = "optimize_for_size")]
325        fn $gen_name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
326            const MAX_DEC_N: usize = $u::MAX.ilog10() as usize + 1;
327            let mut buf = [MaybeUninit::<u8>::uninit(); MAX_DEC_N];
328            let mut curr = MAX_DEC_N;
329            let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
330
331            // SAFETY: To show that it's OK to copy into `buf_ptr`, notice that at the beginning
332            // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
333            // each step this is kept the same as `n` is divided. Since `n` is always
334            // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
335            // is safe to access.
336            unsafe {
337                loop {
338                    curr -= 1;
339                    buf_ptr.add(curr).write((n % 10) as u8 + b'0');
340                    n /= 10;
341
342                    if n == 0 {
343                        break;
344                    }
345                }
346            }
347
348            // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid UTF-8
349            let buf_slice = unsafe {
350                str::from_utf8_unchecked(
351                    slice::from_raw_parts(buf_ptr.add(curr), buf.len() - curr))
352            };
353            f.pad_integral(is_nonnegative, "", buf_slice)
354        }
355    };
356}
357
358macro_rules! impl_Exp {
359    ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
360        fn $name(
361            mut n: $u,
362            is_nonnegative: bool,
363            upper: bool,
364            f: &mut fmt::Formatter<'_>
365        ) -> fmt::Result {
366            let (mut n, mut exponent, trailing_zeros, added_precision) = {
367                let mut exponent = 0;
368                // count and remove trailing decimal zeroes
369                while n % 10 == 0 && n >= 10 {
370                    n /= 10;
371                    exponent += 1;
372                }
373                let (added_precision, subtracted_precision) = match f.precision() {
374                    Some(fmt_prec) => {
375                        // number of decimal digits minus 1
376                        let mut tmp = n;
377                        let mut prec = 0;
378                        while tmp >= 10 {
379                            tmp /= 10;
380                            prec += 1;
381                        }
382                        (fmt_prec.saturating_sub(prec), prec.saturating_sub(fmt_prec))
383                    }
384                    None => (0, 0)
385                };
386                for _ in 1..subtracted_precision {
387                    n /= 10;
388                    exponent += 1;
389                }
390                if subtracted_precision != 0 {
391                    let rem = n % 10;
392                    n /= 10;
393                    exponent += 1;
394                    // round up last digit, round to even on a tie
395                    if rem > 5 || (rem == 5 && (n % 2 != 0 || subtracted_precision > 1 )) {
396                        n += 1;
397                        // if the digit is rounded to the next power
398                        // instead adjust the exponent
399                        if n.ilog10() > (n - 1).ilog10() {
400                            n /= 10;
401                            exponent += 1;
402                        }
403                    }
404                }
405                (n, exponent, exponent, added_precision)
406            };
407
408            // Since `curr` always decreases by the number of digits copied, this means
409            // that `curr >= 0`.
410            let mut buf = [MaybeUninit::<u8>::uninit(); 40];
411            let mut curr = buf.len(); //index for buf
412            let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
413            let lut_ptr = DEC_DIGITS_LUT.as_ptr();
414
415            // decode 2 chars at a time
416            while n >= 100 {
417                let d1 = ((n % 100) as usize) << 1;
418                curr -= 2;
419                // SAFETY: `d1 <= 198`, so we can copy from `lut_ptr[d1..d1 + 2]` since
420                // `DEC_DIGITS_LUT` has a length of 200.
421                unsafe {
422                    ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
423                }
424                n /= 100;
425                exponent += 2;
426            }
427            // n is <= 99, so at most 2 chars long
428            let mut n = n as isize; // possibly reduce 64bit math
429            // decode second-to-last character
430            if n >= 10 {
431                curr -= 1;
432                // SAFETY: Safe since `40 > curr >= 0` (see comment)
433                unsafe {
434                    *buf_ptr.add(curr) = (n as u8 % 10_u8) + b'0';
435                }
436                n /= 10;
437                exponent += 1;
438            }
439            // add decimal point iff >1 mantissa digit will be printed
440            if exponent != trailing_zeros || added_precision != 0 {
441                curr -= 1;
442                // SAFETY: Safe since `40 > curr >= 0`
443                unsafe {
444                    *buf_ptr.add(curr) = b'.';
445                }
446            }
447
448            // SAFETY: Safe since `40 > curr >= 0`
449            let buf_slice = unsafe {
450                // decode last character
451                curr -= 1;
452                *buf_ptr.add(curr) = (n as u8) + b'0';
453
454                let len = buf.len() - curr as usize;
455                slice::from_raw_parts(buf_ptr.add(curr), len)
456            };
457
458            // stores 'e' (or 'E') and the up to 2-digit exponent
459            let mut exp_buf = [MaybeUninit::<u8>::uninit(); 3];
460            let exp_ptr = MaybeUninit::slice_as_mut_ptr(&mut exp_buf);
461            // SAFETY: In either case, `exp_buf` is written within bounds and `exp_ptr[..len]`
462            // is contained within `exp_buf` since `len <= 3`.
463            let exp_slice = unsafe {
464                *exp_ptr.add(0) = if upper { b'E' } else { b'e' };
465                let len = if exponent < 10 {
466                    *exp_ptr.add(1) = (exponent as u8) + b'0';
467                    2
468                } else {
469                    let off = exponent << 1;
470                    ptr::copy_nonoverlapping(lut_ptr.add(off), exp_ptr.add(1), 2);
471                    3
472                };
473                slice::from_raw_parts(exp_ptr, len)
474            };
475
476            let parts = &[
477                numfmt::Part::Copy(buf_slice),
478                numfmt::Part::Zero(added_precision),
479                numfmt::Part::Copy(exp_slice),
480            ];
481            let sign = if !is_nonnegative {
482                "-"
483            } else if f.sign_plus() {
484                "+"
485            } else {
486                ""
487            };
488            let formatted = numfmt::Formatted { sign, parts };
489            // SAFETY: `buf_slice` and `exp_slice` contain only ASCII characters.
490            unsafe { f.pad_formatted_parts(&formatted) }
491        }
492
493        $(
494            #[stable(feature = "integer_exp_format", since = "1.42.0")]
495            impl fmt::LowerExp for $t {
496                #[allow(unused_comparisons)]
497                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
498                    let is_nonnegative = *self >= 0;
499                    let n = if is_nonnegative {
500                        self.$conv_fn()
501                    } else {
502                        // convert the negative num to positive by summing 1 to its 2s complement
503                        (!self.$conv_fn()).wrapping_add(1)
504                    };
505                    $name(n, is_nonnegative, false, f)
506                }
507            })*
508        $(
509            #[stable(feature = "integer_exp_format", since = "1.42.0")]
510            impl fmt::UpperExp for $t {
511                #[allow(unused_comparisons)]
512                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
513                    let is_nonnegative = *self >= 0;
514                    let n = if is_nonnegative {
515                        self.$conv_fn()
516                    } else {
517                        // convert the negative num to positive by summing 1 to its 2s complement
518                        (!self.$conv_fn()).wrapping_add(1)
519                    };
520                    $name(n, is_nonnegative, true, f)
521                }
522            })*
523    };
524}
525
526impl_Debug! {
527    i8 i16 i32 i64 i128 isize
528    u8 u16 u32 u64 u128 usize
529}
530
531// Include wasm32 in here since it doesn't reflect the native pointer size, and
532// often cares strongly about getting a smaller code size.
533#[cfg(any(target_pointer_width = "64", target_arch = "wasm32"))]
534mod imp {
535    use super::*;
536    impl_Display!(
537        i8, u8,
538        i16, u16,
539        i32, u32,
540        i64, u64,
541        isize, usize,
542        ; as u64 via to_u64 named fmt_u64
543    );
544    impl_Exp!(
545        i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
546            as u64 via to_u64 named exp_u64
547    );
548}
549
550#[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
551mod imp {
552    use super::*;
553    impl_Display!(
554        i8, u8,
555        i16, u16,
556        i32, u32,
557        isize, usize,
558        ; as u32 via to_u32 named fmt_u32);
559    impl_Display!(
560        i64, u64,
561        ; as u64 via to_u64 named fmt_u64);
562
563    impl_Exp!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32);
564    impl_Exp!(i64, u64 as u64 via to_u64 named exp_u64);
565}
566impl_Exp!(i128, u128 as u128 via to_u128 named exp_u128);
567
568const U128_MAX_DEC_N: usize = u128::MAX.ilog10() as usize + 1;
569
570#[stable(feature = "rust1", since = "1.0.0")]
571impl fmt::Display for u128 {
572    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
573        let mut buf = [MaybeUninit::<u8>::uninit(); U128_MAX_DEC_N];
574
575        f.pad_integral(true, "", self._fmt(&mut buf))
576    }
577}
578
579#[stable(feature = "rust1", since = "1.0.0")]
580impl fmt::Display for i128 {
581    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
582        // This is not a typo, we use the maximum number of digits of `u128`, hence why we use
583        // `U128_MAX_DEC_N`.
584        let mut buf = [MaybeUninit::<u8>::uninit(); U128_MAX_DEC_N];
585
586        let is_nonnegative = *self >= 0;
587        f.pad_integral(is_nonnegative, "", self.unsigned_abs()._fmt(&mut buf))
588    }
589}
590
591impl u128 {
592    /// Format optimized for u128. Computation of 128 bits is limited by proccessing
593    /// in batches of 16 decimals at a time.
594    #[doc(hidden)]
595    #[unstable(
596        feature = "fmt_internals",
597        reason = "specialized method meant to only be used by `SpecToString` implementation",
598        issue = "none"
599    )]
600    pub fn _fmt<'a>(self, buf: &'a mut [MaybeUninit<u8>]) -> &'a str {
601        // Optimize common-case zero, which would also need special treatment due to
602        // its "leading" zero.
603        if self == 0 {
604            return "0";
605        }
606
607        // Take the 16 least-significant decimals.
608        let (quot_1e16, mod_1e16) = div_rem_1e16(self);
609        let (mut remain, mut offset) = if quot_1e16 == 0 {
610            (mod_1e16, U128_MAX_DEC_N)
611        } else {
612            // Write digits at buf[23..39].
613            enc_16lsd::<{ U128_MAX_DEC_N - 16 }>(buf, mod_1e16);
614
615            // Take another 16 decimals.
616            let (quot2, mod2) = div_rem_1e16(quot_1e16);
617            if quot2 == 0 {
618                (mod2, U128_MAX_DEC_N - 16)
619            } else {
620                // Write digits at buf[7..23].
621                enc_16lsd::<{ U128_MAX_DEC_N - 32 }>(buf, mod2);
622                // Quot2 has at most 7 decimals remaining after two 1e16 divisions.
623                (quot2 as u64, U128_MAX_DEC_N - 32)
624            }
625        };
626
627        // Format per four digits from the lookup table.
628        while remain > 999 {
629            // SAFETY: All of the decimals fit in buf due to U128_MAX_DEC_N
630            // and the while condition ensures at least 4 more decimals.
631            unsafe { core::hint::assert_unchecked(offset >= 4) }
632            // SAFETY: The offset counts down from its initial buf.len()
633            // without underflow due to the previous precondition.
634            unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
635            offset -= 4;
636
637            // pull two pairs
638            let quad = remain % 1_00_00;
639            remain /= 1_00_00;
640            let pair1 = (quad / 100) as usize;
641            let pair2 = (quad % 100) as usize;
642            buf[offset + 0].write(DEC_DIGITS_LUT[pair1 * 2 + 0]);
643            buf[offset + 1].write(DEC_DIGITS_LUT[pair1 * 2 + 1]);
644            buf[offset + 2].write(DEC_DIGITS_LUT[pair2 * 2 + 0]);
645            buf[offset + 3].write(DEC_DIGITS_LUT[pair2 * 2 + 1]);
646        }
647
648        // Format per two digits from the lookup table.
649        if remain > 9 {
650            // SAFETY: All of the decimals fit in buf due to U128_MAX_DEC_N
651            // and the if condition ensures at least 2 more decimals.
652            unsafe { core::hint::assert_unchecked(offset >= 2) }
653            // SAFETY: The offset counts down from its initial buf.len()
654            // without underflow due to the previous precondition.
655            unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
656            offset -= 2;
657
658            let pair = (remain % 100) as usize;
659            remain /= 100;
660            buf[offset + 0].write(DEC_DIGITS_LUT[pair * 2 + 0]);
661            buf[offset + 1].write(DEC_DIGITS_LUT[pair * 2 + 1]);
662        }
663
664        // Format the last remaining digit, if any.
665        if remain != 0 {
666            // SAFETY: All of the decimals fit in buf due to U128_MAX_DEC_N
667            // and the if condition ensures (at least) 1 more decimals.
668            unsafe { core::hint::assert_unchecked(offset >= 1) }
669            // SAFETY: The offset counts down from its initial buf.len()
670            // without underflow due to the previous precondition.
671            unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
672            offset -= 1;
673
674            // Either the compiler sees that remain < 10, or it prevents
675            // a boundary check up next.
676            let last = (remain & 15) as usize;
677            buf[offset].write(DEC_DIGITS_LUT[last * 2 + 1]);
678            // not used: remain = 0;
679        }
680
681        // SAFETY: All buf content since offset is set.
682        let written = unsafe { buf.get_unchecked(offset..) };
683        // SAFETY: Writes use ASCII from the lookup table exclusively.
684        unsafe {
685            str::from_utf8_unchecked(slice::from_raw_parts(
686                MaybeUninit::slice_as_ptr(written),
687                written.len(),
688            ))
689        }
690    }
691}
692
693/// Encodes the 16 least-significant decimals of n into `buf[OFFSET .. OFFSET +
694/// 16 ]`.
695fn enc_16lsd<const OFFSET: usize>(buf: &mut [MaybeUninit<u8>], n: u64) {
696    // Consume the least-significant decimals from a working copy.
697    let mut remain = n;
698
699    // Format per four digits from the lookup table.
700    for quad_index in (0..4).rev() {
701        // pull two pairs
702        let quad = remain % 1_00_00;
703        remain /= 1_00_00;
704        let pair1 = (quad / 100) as usize;
705        let pair2 = (quad % 100) as usize;
706        buf[quad_index * 4 + OFFSET + 0].write(DEC_DIGITS_LUT[pair1 * 2 + 0]);
707        buf[quad_index * 4 + OFFSET + 1].write(DEC_DIGITS_LUT[pair1 * 2 + 1]);
708        buf[quad_index * 4 + OFFSET + 2].write(DEC_DIGITS_LUT[pair2 * 2 + 0]);
709        buf[quad_index * 4 + OFFSET + 3].write(DEC_DIGITS_LUT[pair2 * 2 + 1]);
710    }
711}
712
713/// Euclidean division plus remainder with constant 1E16 basically consumes 16
714/// decimals from n.
715///
716/// The integer division algorithm is based on the following paper:
717///
718///   T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
719///   in Proc. of the SIGPLAN94 Conference on Programming Language Design and
720///   Implementation, 1994, pp. 61–72
721///
722#[inline]
723fn div_rem_1e16(n: u128) -> (u128, u64) {
724    const D: u128 = 1_0000_0000_0000_0000;
725    // The check inlines well with the caller flow.
726    if n < D {
727        return (0, n as u64);
728    }
729
730    // These constant values are computed with the CHOOSE_MULTIPLIER procedure
731    // from the Granlund & Montgomery paper, using N=128, prec=128 and d=1E16.
732    const M_HIGH: u128 = 76624777043294442917917351357515459181;
733    const SH_POST: u8 = 51;
734
735    let quot = n.widening_mul(M_HIGH).1 >> SH_POST;
736    let rem = n - quot * D;
737    (quot, rem as u64)
738}
core/fmt/num.rs

core/fmt/
num.rs
