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                    self._fmt(true, f)
212                }
213                #[cfg(feature = "optimize_for_size")]
214                {
215                    $gen_name(self.$conv_fn(), true, f)
216                }
217            }
218        }
219
220        #[stable(feature = "rust1", since = "1.0.0")]
221        impl fmt::Display for $signed {
222            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
223                #[cfg(not(feature = "optimize_for_size"))]
224                {
225                    return self.unsigned_abs()._fmt(*self >= 0, f);
226                }
227                #[cfg(feature = "optimize_for_size")]
228                {
229                    return $gen_name(self.unsigned_abs().$conv_fn(), *self >= 0, f);
230                }
231            }
232        }
233
234        #[cfg(not(feature = "optimize_for_size"))]
235        impl $unsigned {
236            fn _fmt(self, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
237                const MAX_DEC_N: usize = $unsigned::MAX.ilog(10) as usize + 1;
238                // Buffer decimals for $unsigned with right alignment.
239                let mut buf = [MaybeUninit::<u8>::uninit(); MAX_DEC_N];
240                // Count the number of bytes in buf that are not initialized.
241                let mut offset = buf.len();
242                // Consume the least-significant decimals from a working copy.
243                let mut remain = self;
244
245                // Format per four digits from the lookup table.
246                // Four digits need a 16-bit $unsigned or wider.
247                while size_of::<Self>() > 1 && remain > 999.try_into().expect("branch is not hit for types that cannot fit 999 (u8)") {
248                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
249                    // and the while condition ensures at least 4 more decimals.
250                    unsafe { core::hint::assert_unchecked(offset >= 4) }
251                    // SAFETY: The offset counts down from its initial buf.len()
252                    // without underflow due to the previous precondition.
253                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
254                    offset -= 4;
255
256                    // pull two pairs
257                    let scale: Self = 1_00_00.try_into().expect("branch is not hit for types that cannot fit 1E4 (u8)");
258                    let quad = remain % scale;
259                    remain /= scale;
260                    let pair1 = (quad / 100) as usize;
261                    let pair2 = (quad % 100) as usize;
262                    buf[offset + 0].write(DEC_DIGITS_LUT[pair1 * 2 + 0]);
263                    buf[offset + 1].write(DEC_DIGITS_LUT[pair1 * 2 + 1]);
264                    buf[offset + 2].write(DEC_DIGITS_LUT[pair2 * 2 + 0]);
265                    buf[offset + 3].write(DEC_DIGITS_LUT[pair2 * 2 + 1]);
266                }
267
268                // Format per two digits from the lookup table.
269                if remain > 9 {
270                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
271                    // and the while condition ensures at least 2 more decimals.
272                    unsafe { core::hint::assert_unchecked(offset >= 2) }
273                    // SAFETY: The offset counts down from its initial buf.len()
274                    // without underflow due to the previous precondition.
275                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
276                    offset -= 2;
277
278                    let pair = (remain % 100) as usize;
279                    remain /= 100;
280                    buf[offset + 0].write(DEC_DIGITS_LUT[pair * 2 + 0]);
281                    buf[offset + 1].write(DEC_DIGITS_LUT[pair * 2 + 1]);
282                }
283
284                // Format the last remaining digit, if any.
285                if remain != 0 || self == 0 {
286                    // SAFETY: All of the decimals fit in buf due to MAX_DEC_N
287                    // and the if condition ensures (at least) 1 more decimals.
288                    unsafe { core::hint::assert_unchecked(offset >= 1) }
289                    // SAFETY: The offset counts down from its initial buf.len()
290                    // without underflow due to the previous precondition.
291                    unsafe { core::hint::assert_unchecked(offset <= buf.len()) }
292                    offset -= 1;
293
294                    // Either the compiler sees that remain < 10, or it prevents
295                    // a boundary check up next.
296                    let last = (remain & 15) as usize;
297                    buf[offset].write(DEC_DIGITS_LUT[last * 2 + 1]);
298                    // not used: remain = 0;
299                }
300
301                // SAFETY: All buf content since offset is set.
302                let written = unsafe { buf.get_unchecked(offset..) };
303                // SAFETY: Writes use ASCII from the lookup table exclusively.
304                let as_str = unsafe {
305                    str::from_utf8_unchecked(slice::from_raw_parts(
306                          MaybeUninit::slice_as_ptr(written),
307                          written.len(),
308                    ))
309                };
310                f.pad_integral(is_nonnegative, "", as_str)
311            }
312        })*
313
314        #[cfg(feature = "optimize_for_size")]
315        fn $gen_name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316            const MAX_DEC_N: usize = $u::MAX.ilog(10) as usize + 1;
317            let mut buf = [MaybeUninit::<u8>::uninit(); MAX_DEC_N];
318            let mut curr = MAX_DEC_N;
319            let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
320
321            // SAFETY: To show that it's OK to copy into `buf_ptr`, notice that at the beginning
322            // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
323            // each step this is kept the same as `n` is divided. Since `n` is always
324            // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
325            // is safe to access.
326            unsafe {
327                loop {
328                    curr -= 1;
329                    buf_ptr.add(curr).write((n % 10) as u8 + b'0');
330                    n /= 10;
331
332                    if n == 0 {
333                        break;
334                    }
335                }
336            }
337
338            // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid UTF-8
339            let buf_slice = unsafe {
340                str::from_utf8_unchecked(
341                    slice::from_raw_parts(buf_ptr.add(curr), buf.len() - curr))
342            };
343            f.pad_integral(is_nonnegative, "", buf_slice)
344        }
345    };
346}
347
348macro_rules! impl_Exp {
349    ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
350        fn $name(
351            mut n: $u,
352            is_nonnegative: bool,
353            upper: bool,
354            f: &mut fmt::Formatter<'_>
355        ) -> fmt::Result {
356            let (mut n, mut exponent, trailing_zeros, added_precision) = {
357                let mut exponent = 0;
358                // count and remove trailing decimal zeroes
359                while n % 10 == 0 && n >= 10 {
360                    n /= 10;
361                    exponent += 1;
362                }
363                let (added_precision, subtracted_precision) = match f.precision() {
364                    Some(fmt_prec) => {
365                        // number of decimal digits minus 1
366                        let mut tmp = n;
367                        let mut prec = 0;
368                        while tmp >= 10 {
369                            tmp /= 10;
370                            prec += 1;
371                        }
372                        (fmt_prec.saturating_sub(prec), prec.saturating_sub(fmt_prec))
373                    }
374                    None => (0, 0)
375                };
376                for _ in 1..subtracted_precision {
377                    n /= 10;
378                    exponent += 1;
379                }
380                if subtracted_precision != 0 {
381                    let rem = n % 10;
382                    n /= 10;
383                    exponent += 1;
384                    // round up last digit, round to even on a tie
385                    if rem > 5 || (rem == 5 && (n % 2 != 0 || subtracted_precision > 1 )) {
386                        n += 1;
387                        // if the digit is rounded to the next power
388                        // instead adjust the exponent
389                        if n.ilog10() > (n - 1).ilog10() {
390                            n /= 10;
391                            exponent += 1;
392                        }
393                    }
394                }
395                (n, exponent, exponent, added_precision)
396            };
397
398            // Since `curr` always decreases by the number of digits copied, this means
399            // that `curr >= 0`.
400            let mut buf = [MaybeUninit::<u8>::uninit(); 40];
401            let mut curr = buf.len(); //index for buf
402            let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
403            let lut_ptr = DEC_DIGITS_LUT.as_ptr();
404
405            // decode 2 chars at a time
406            while n >= 100 {
407                let d1 = ((n % 100) as usize) << 1;
408                curr -= 2;
409                // SAFETY: `d1 <= 198`, so we can copy from `lut_ptr[d1..d1 + 2]` since
410                // `DEC_DIGITS_LUT` has a length of 200.
411                unsafe {
412                    ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
413                }
414                n /= 100;
415                exponent += 2;
416            }
417            // n is <= 99, so at most 2 chars long
418            let mut n = n as isize; // possibly reduce 64bit math
419            // decode second-to-last character
420            if n >= 10 {
421                curr -= 1;
422                // SAFETY: Safe since `40 > curr >= 0` (see comment)
423                unsafe {
424                    *buf_ptr.add(curr) = (n as u8 % 10_u8) + b'0';
425                }
426                n /= 10;
427                exponent += 1;
428            }
429            // add decimal point iff >1 mantissa digit will be printed
430            if exponent != trailing_zeros || added_precision != 0 {
431                curr -= 1;
432                // SAFETY: Safe since `40 > curr >= 0`
433                unsafe {
434                    *buf_ptr.add(curr) = b'.';
435                }
436            }
437
438            // SAFETY: Safe since `40 > curr >= 0`
439            let buf_slice = unsafe {
440                // decode last character
441                curr -= 1;
442                *buf_ptr.add(curr) = (n as u8) + b'0';
443
444                let len = buf.len() - curr as usize;
445                slice::from_raw_parts(buf_ptr.add(curr), len)
446            };
447
448            // stores 'e' (or 'E') and the up to 2-digit exponent
449            let mut exp_buf = [MaybeUninit::<u8>::uninit(); 3];
450            let exp_ptr = MaybeUninit::slice_as_mut_ptr(&mut exp_buf);
451            // SAFETY: In either case, `exp_buf` is written within bounds and `exp_ptr[..len]`
452            // is contained within `exp_buf` since `len <= 3`.
453            let exp_slice = unsafe {
454                *exp_ptr.add(0) = if upper { b'E' } else { b'e' };
455                let len = if exponent < 10 {
456                    *exp_ptr.add(1) = (exponent as u8) + b'0';
457                    2
458                } else {
459                    let off = exponent << 1;
460                    ptr::copy_nonoverlapping(lut_ptr.add(off), exp_ptr.add(1), 2);
461                    3
462                };
463                slice::from_raw_parts(exp_ptr, len)
464            };
465
466            let parts = &[
467                numfmt::Part::Copy(buf_slice),
468                numfmt::Part::Zero(added_precision),
469                numfmt::Part::Copy(exp_slice),
470            ];
471            let sign = if !is_nonnegative {
472                "-"
473            } else if f.sign_plus() {
474                "+"
475            } else {
476                ""
477            };
478            let formatted = numfmt::Formatted { sign, parts };
479            // SAFETY: `buf_slice` and `exp_slice` contain only ASCII characters.
480            unsafe { f.pad_formatted_parts(&formatted) }
481        }
482
483        $(
484            #[stable(feature = "integer_exp_format", since = "1.42.0")]
485            impl fmt::LowerExp for $t {
486                #[allow(unused_comparisons)]
487                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
488                    let is_nonnegative = *self >= 0;
489                    let n = if is_nonnegative {
490                        self.$conv_fn()
491                    } else {
492                        // convert the negative num to positive by summing 1 to its 2s complement
493                        (!self.$conv_fn()).wrapping_add(1)
494                    };
495                    $name(n, is_nonnegative, false, f)
496                }
497            })*
498        $(
499            #[stable(feature = "integer_exp_format", since = "1.42.0")]
500            impl fmt::UpperExp for $t {
501                #[allow(unused_comparisons)]
502                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
503                    let is_nonnegative = *self >= 0;
504                    let n = if is_nonnegative {
505                        self.$conv_fn()
506                    } else {
507                        // convert the negative num to positive by summing 1 to its 2s complement
508                        (!self.$conv_fn()).wrapping_add(1)
509                    };
510                    $name(n, is_nonnegative, true, f)
511                }
512            })*
513    };
514}
515
516impl_Debug! {
517    i8 i16 i32 i64 i128 isize
518    u8 u16 u32 u64 u128 usize
519}
520
521// Include wasm32 in here since it doesn't reflect the native pointer size, and
522// often cares strongly about getting a smaller code size.
523#[cfg(any(target_pointer_width = "64", target_arch = "wasm32"))]
524mod imp {
525    use super::*;
526    impl_Display!(
527        i8, u8,
528        i16, u16,
529        i32, u32,
530        i64, u64,
531        isize, usize,
532        ; as u64 via to_u64 named fmt_u64
533    );
534    impl_Exp!(
535        i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
536            as u64 via to_u64 named exp_u64
537    );
538}
539
540#[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
541mod imp {
542    use super::*;
543    impl_Display!(
544        i8, u8,
545        i16, u16,
546        i32, u32,
547        isize, usize,
548        ; as u32 via to_u32 named fmt_u32);
549    impl_Display!(
550        i64, u64,
551        ; as u64 via to_u64 named fmt_u64);
552
553    impl_Exp!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32);
554    impl_Exp!(i64, u64 as u64 via to_u64 named exp_u64);
555}
556impl_Exp!(i128, u128 as u128 via to_u128 named exp_u128);
557
558/// Helper function for writing a u64 into `buf` going from last to first, with `curr`.
559fn parse_u64_into<const N: usize>(mut n: u64, buf: &mut [MaybeUninit<u8>; N], curr: &mut usize) {
560    let buf_ptr = MaybeUninit::slice_as_mut_ptr(buf);
561    let lut_ptr = DEC_DIGITS_LUT.as_ptr();
562    assert!(*curr > 19);
563
564    // SAFETY:
565    // Writes at most 19 characters into the buffer. Guaranteed that any ptr into LUT is at most
566    // 198, so will never OOB. There is a check above that there are at least 19 characters
567    // remaining.
568    unsafe {
569        if n >= 1e16 as u64 {
570            let to_parse = n % 1e16 as u64;
571            n /= 1e16 as u64;
572
573            // Some of these are nops but it looks more elegant this way.
574            let d1 = ((to_parse / 1e14 as u64) % 100) << 1;
575            let d2 = ((to_parse / 1e12 as u64) % 100) << 1;
576            let d3 = ((to_parse / 1e10 as u64) % 100) << 1;
577            let d4 = ((to_parse / 1e8 as u64) % 100) << 1;
578            let d5 = ((to_parse / 1e6 as u64) % 100) << 1;
579            let d6 = ((to_parse / 1e4 as u64) % 100) << 1;
580            let d7 = ((to_parse / 1e2 as u64) % 100) << 1;
581            let d8 = ((to_parse / 1e0 as u64) % 100) << 1;
582
583            *curr -= 16;
584
585            ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
586            ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
587            ptr::copy_nonoverlapping(lut_ptr.add(d3 as usize), buf_ptr.add(*curr + 4), 2);
588            ptr::copy_nonoverlapping(lut_ptr.add(d4 as usize), buf_ptr.add(*curr + 6), 2);
589            ptr::copy_nonoverlapping(lut_ptr.add(d5 as usize), buf_ptr.add(*curr + 8), 2);
590            ptr::copy_nonoverlapping(lut_ptr.add(d6 as usize), buf_ptr.add(*curr + 10), 2);
591            ptr::copy_nonoverlapping(lut_ptr.add(d7 as usize), buf_ptr.add(*curr + 12), 2);
592            ptr::copy_nonoverlapping(lut_ptr.add(d8 as usize), buf_ptr.add(*curr + 14), 2);
593        }
594        if n >= 1e8 as u64 {
595            let to_parse = n % 1e8 as u64;
596            n /= 1e8 as u64;
597
598            // Some of these are nops but it looks more elegant this way.
599            let d1 = ((to_parse / 1e6 as u64) % 100) << 1;
600            let d2 = ((to_parse / 1e4 as u64) % 100) << 1;
601            let d3 = ((to_parse / 1e2 as u64) % 100) << 1;
602            let d4 = ((to_parse / 1e0 as u64) % 100) << 1;
603            *curr -= 8;
604
605            ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
606            ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
607            ptr::copy_nonoverlapping(lut_ptr.add(d3 as usize), buf_ptr.add(*curr + 4), 2);
608            ptr::copy_nonoverlapping(lut_ptr.add(d4 as usize), buf_ptr.add(*curr + 6), 2);
609        }
610        // `n` < 1e8 < (1 << 32)
611        let mut n = n as u32;
612        if n >= 1e4 as u32 {
613            let to_parse = n % 1e4 as u32;
614            n /= 1e4 as u32;
615
616            let d1 = (to_parse / 100) << 1;
617            let d2 = (to_parse % 100) << 1;
618            *curr -= 4;
619
620            ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
621            ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
622        }
623
624        // `n` < 1e4 < (1 << 16)
625        let mut n = n as u16;
626        if n >= 100 {
627            let d1 = (n % 100) << 1;
628            n /= 100;
629            *curr -= 2;
630            ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr), 2);
631        }
632
633        // decode last 1 or 2 chars
634        if n < 10 {
635            *curr -= 1;
636            *buf_ptr.add(*curr) = (n as u8) + b'0';
637        } else {
638            let d1 = n << 1;
639            *curr -= 2;
640            ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr), 2);
641        }
642    }
643}
644
645#[stable(feature = "rust1", since = "1.0.0")]
646impl fmt::Display for u128 {
647    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
648        fmt_u128(*self, true, f)
649    }
650}
651
652#[stable(feature = "rust1", since = "1.0.0")]
653impl fmt::Display for i128 {
654    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
655        let is_nonnegative = *self >= 0;
656        let n = if is_nonnegative {
657            self.to_u128()
658        } else {
659            // convert the negative num to positive by summing 1 to its 2s complement
660            (!self.to_u128()).wrapping_add(1)
661        };
662        fmt_u128(n, is_nonnegative, f)
663    }
664}
665
666/// Specialized optimization for u128. Instead of taking two items at a time, it splits
667/// into at most 2 u64s, and then chunks by 10e16, 10e8, 10e4, 10e2, and then 10e1.
668/// It also has to handle 1 last item, as 10^40 > 2^128 > 10^39, whereas
669/// 10^20 > 2^64 > 10^19.
670fn fmt_u128(n: u128, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
671    // 2^128 is about 3*10^38, so 39 gives an extra byte of space
672    let mut buf = [MaybeUninit::<u8>::uninit(); 39];
673    let mut curr = buf.len();
674
675    let (n, rem) = udiv_1e19(n);
676    parse_u64_into(rem, &mut buf, &mut curr);
677
678    if n != 0 {
679        // 0 pad up to point
680        let target = buf.len() - 19;
681        // SAFETY: Guaranteed that we wrote at most 19 bytes, and there must be space
682        // remaining since it has length 39
683        unsafe {
684            ptr::write_bytes(
685                MaybeUninit::slice_as_mut_ptr(&mut buf).add(target),
686                b'0',
687                curr - target,
688            );
689        }
690        curr = target;
691
692        let (n, rem) = udiv_1e19(n);
693        parse_u64_into(rem, &mut buf, &mut curr);
694        // Should this following branch be annotated with unlikely?
695        if n != 0 {
696            let target = buf.len() - 38;
697            // The raw `buf_ptr` pointer is only valid until `buf` is used the next time,
698            // buf `buf` is not used in this scope so we are good.
699            let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
700            // SAFETY: At this point we wrote at most 38 bytes, pad up to that point,
701            // There can only be at most 1 digit remaining.
702            unsafe {
703                ptr::write_bytes(buf_ptr.add(target), b'0', curr - target);
704                curr = target - 1;
705                *buf_ptr.add(curr) = (n as u8) + b'0';
706            }
707        }
708    }
709
710    // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
711    // UTF-8 since `DEC_DIGITS_LUT` is
712    let buf_slice = unsafe {
713        str::from_utf8_unchecked(slice::from_raw_parts(
714            MaybeUninit::slice_as_mut_ptr(&mut buf).add(curr),
715            buf.len() - curr,
716        ))
717    };
718    f.pad_integral(is_nonnegative, "", buf_slice)
719}
720
721/// Partition of `n` into n > 1e19 and rem <= 1e19
722///
723/// Integer division algorithm is based on the following paper:
724///
725///   T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
726///   in Proc. of the SIGPLAN94 Conference on Programming Language Design and
727///   Implementation, 1994, pp. 61–72
728///
729fn udiv_1e19(n: u128) -> (u128, u64) {
730    const DIV: u64 = 1e19 as u64;
731    const FACTOR: u128 = 156927543384667019095894735580191660403;
732
733    let quot = if n < 1 << 83 {
734        ((n >> 19) as u64 / (DIV >> 19)) as u128
735    } else {
736        n.widening_mul(FACTOR).1 >> 62
737    };
738
739    let rem = (n - quot * DIV as u128) as u64;
740    (quot, rem)
741}