library/core/src/fmt/num.rs

   1 //! Integer and floating-point number formatting
   2
   3 use crate::fmt;
   4 use crate::mem::MaybeUninit;
   5 use crate::num::fmt as numfmt;
   6 use crate::ops::{Div, Rem, Sub};
   7 use crate::ptr;
   8 use crate::slice;
   9 use crate::str;
  10
  11 #[doc(hidden)]
  12 trait DisplayInt:
  13     PartialEq + PartialOrd + Div<Output = Self> + Rem<Output = Self> + Sub<Output = Self> + Copy
  14 {
  15     fn zero() -> Self;
  16     fn from_u8(u: u8) -> Self;
  17     fn to_u8(&self) -> u8;
  18     fn to_u16(&self) -> u16;
  19     fn to_u32(&self) -> u32;
  20     fn to_u64(&self) -> u64;
  21     fn to_u128(&self) -> u128;
  22 }
  23
  24 macro_rules! impl_int {
  25     ($($t:ident)*) => (
  26       $(impl DisplayInt for $t {
  27           fn zero() -> Self { 0 }
  28           fn from_u8(u: u8) -> Self { u as Self }
  29           fn to_u8(&self) -> u8 { *self as u8 }
  30           fn to_u16(&self) -> u16 { *self as u16 }
  31           fn to_u32(&self) -> u32 { *self as u32 }
  32           fn to_u64(&self) -> u64 { *self as u64 }
  33           fn to_u128(&self) -> u128 { *self as u128 }
  34       })*
  35     )
  36 }
  37 macro_rules! impl_uint {
  38     ($($t:ident)*) => (
  39       $(impl DisplayInt for $t {
  40           fn zero() -> Self { 0 }
  41           fn from_u8(u: u8) -> Self { u as Self }
  42           fn to_u8(&self) -> u8 { *self as u8 }
  43           fn to_u16(&self) -> u16 { *self as u16 }
  44           fn to_u32(&self) -> u32 { *self as u32 }
  45           fn to_u64(&self) -> u64 { *self as u64 }
  46           fn to_u128(&self) -> u128 { *self as u128 }
  47       })*
  48     )
  49 }
  50
  51 impl_int! { i8 i16 i32 i64 i128 isize }
  52 impl_uint! { u8 u16 u32 u64 u128 usize }
  53
  54 /// A type that represents a specific radix
  55 #[doc(hidden)]
  56 trait GenericRadix: Sized {
  57     /// The number of digits.
  58     const BASE: u8;
  59
  60     /// A radix-specific prefix string.
  61     const PREFIX: &'static str;
  62
  63     /// Converts an integer to corresponding radix digit.
  64     fn digit(x: u8) -> u8;
  65
  66     /// Format an integer using the radix using a formatter.
  67     fn fmt_int<T: DisplayInt>(&self, mut x: T, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  68         // The radix can be as low as 2, so we need a buffer of at least 128
  69         // characters for a base 2 number.
  70         let zero = T::zero();
  71         let is_nonnegative = x >= zero;
  72         let mut buf = [MaybeUninit::<u8>::uninit(); 128];
  73         let mut curr = buf.len();
  74         let base = T::from_u8(Self::BASE);
  75         if is_nonnegative {
  76             // Accumulate each digit of the number from the least significant
  77             // to the most significant figure.
  78             for byte in buf.iter_mut().rev() {
  79                 let n = x % base; // Get the current place value.
  80                 x = x / base; // Deaccumulate the number.
  81                 byte.write(Self::digit(n.to_u8())); // Store the digit in the buffer.
  82                 curr -= 1;
  83                 if x == zero {
  84                     // No more digits left to accumulate.
  85                     break;
  86                 };
  87             }
  88         } else {
  89             // Do the same as above, but accounting for two's complement.
  90             for byte in buf.iter_mut().rev() {
  91                 let n = zero - (x % base); // Get the current place value.
  92                 x = x / base; // Deaccumulate the number.
  93                 byte.write(Self::digit(n.to_u8())); // Store the digit in the buffer.
  94                 curr -= 1;
  95                 if x == zero {
  96                     // No more digits left to accumulate.
  97                     break;
  98                 };
  99             }
 100         }
 101         let buf = &buf[curr..];
 102         // SAFETY: The only chars in `buf` are created by `Self::digit` which are assumed to be
 103         // valid UTF-8
 104         let buf = unsafe {
 105             str::from_utf8_unchecked(slice::from_raw_parts(
 106                 MaybeUninit::slice_as_ptr(buf),
 107                 buf.len(),
 108             ))
 109         };
 110         f.pad_integral(is_nonnegative, Self::PREFIX, buf)
 111     }
 112 }
 113
 114 /// A binary (base 2) radix
 115 #[derive(Clone, PartialEq)]
 116 struct Binary;
 117
 118 /// An octal (base 8) radix
 119 #[derive(Clone, PartialEq)]
 120 struct Octal;
 121
 122 /// A hexadecimal (base 16) radix, formatted with lower-case characters
 123 #[derive(Clone, PartialEq)]
 124 struct LowerHex;
 125
 126 /// A hexadecimal (base 16) radix, formatted with upper-case characters
 127 #[derive(Clone, PartialEq)]
 128 struct UpperHex;
 129
 130 macro_rules! radix {
 131     ($T:ident, $base:expr, $prefix:expr, $($x:pat => $conv:expr),+) => {
 132         impl GenericRadix for $T {
 133             const BASE: u8 = $base;
 134             const PREFIX: &'static str = $prefix;
 135             fn digit(x: u8) -> u8 {
 136                 match x {
 137                     $($x => $conv,)+
 138                     x => panic!("number not in the range 0..={}: {}", Self::BASE - 1, x),
 139                 }
 140             }
 141         }
 142     }
 143 }
 144
 145 radix! { Binary,    2, "0b", x @  0 ..=  1 => b'0' + x }
 146 radix! { Octal,     8, "0o", x @  0 ..=  7 => b'0' + x }
 147 radix! { LowerHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'a' + (x - 10) }
 148 radix! { UpperHex, 16, "0x", x @  0 ..=  9 => b'0' + x, x @ 10 ..= 15 => b'A' + (x - 10) }
 149
 150 macro_rules! int_base {
 151     (fmt::$Trait:ident for $T:ident as $U:ident -> $Radix:ident) => {
 152         #[stable(feature = "rust1", since = "1.0.0")]
 153         impl fmt::$Trait for $T {
 154             fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 155                 $Radix.fmt_int(*self as $U, f)
 156             }
 157         }
 158     };
 159 }
 160
 161 macro_rules! integer {
 162     ($Int:ident, $Uint:ident) => {
 163         int_base! { fmt::Binary   for $Int as $Uint  -> Binary }
 164         int_base! { fmt::Octal    for $Int as $Uint  -> Octal }
 165         int_base! { fmt::LowerHex for $Int as $Uint  -> LowerHex }
 166         int_base! { fmt::UpperHex for $Int as $Uint  -> UpperHex }
 167
 168         int_base! { fmt::Binary   for $Uint as $Uint -> Binary }
 169         int_base! { fmt::Octal    for $Uint as $Uint -> Octal }
 170         int_base! { fmt::LowerHex for $Uint as $Uint -> LowerHex }
 171         int_base! { fmt::UpperHex for $Uint as $Uint -> UpperHex }
 172     };
 173 }
 174 integer! { isize, usize }
 175 integer! { i8, u8 }
 176 integer! { i16, u16 }
 177 integer! { i32, u32 }
 178 integer! { i64, u64 }
 179 integer! { i128, u128 }
 180 macro_rules! debug {
 181     ($($T:ident)*) => {$(
 182         #[stable(feature = "rust1", since = "1.0.0")]
 183         impl fmt::Debug for $T {
 184             #[inline]
 185             fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 186                 if f.debug_lower_hex() {
 187                     fmt::LowerHex::fmt(self, f)
 188                 } else if f.debug_upper_hex() {
 189                     fmt::UpperHex::fmt(self, f)
 190                 } else {
 191                     fmt::Display::fmt(self, f)
 192                 }
 193             }
 194         }
 195     )*};
 196 }
 197 debug! {
 198   i8 i16 i32 i64 i128 isize
 199   u8 u16 u32 u64 u128 usize
 200 }
 201
 202 // 2 digit decimal look up table
 203 static DEC_DIGITS_LUT: &[u8; 200] = b"0001020304050607080910111213141516171819\
 204       2021222324252627282930313233343536373839\
 205       4041424344454647484950515253545556575859\
 206       6061626364656667686970717273747576777879\
 207       8081828384858687888990919293949596979899";
 208
 209 macro_rules! impl_Display {
 210     ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
 211         fn $name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 212             // 2^128 is about 3*10^38, so 39 gives an extra byte of space
 213             let mut buf = [MaybeUninit::<u8>::uninit(); 39];
 214             let mut curr = buf.len();
 215             let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
 216             let lut_ptr = DEC_DIGITS_LUT.as_ptr();
 217
 218             // SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
 219             // can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
 220             // that it's OK to copy into `buf_ptr`, notice that at the beginning
 221             // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
 222             // each step this is kept the same as `n` is divided. Since `n` is always
 223             // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
 224             // is safe to access.
 225             unsafe {
 226                 // need at least 16 bits for the 4-characters-at-a-time to work.
 227                 assert!(crate::mem::size_of::<$u>() >= 2);
 228
 229                 // eagerly decode 4 characters at a time
 230                 while n >= 10000 {
 231                     let rem = (n % 10000) as usize;
 232                     n /= 10000;
 233
 234                     let d1 = (rem / 100) << 1;
 235                     let d2 = (rem % 100) << 1;
 236                     curr -= 4;
 237
 238                     // We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
 239                     // otherwise `curr < 0`. But then `n` was originally at least `10000^10`
 240                     // which is `10^40 > 2^128 > n`.
 241                     ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
 242                     ptr::copy_nonoverlapping(lut_ptr.add(d2), buf_ptr.add(curr + 2), 2);
 243                 }
 244
 245                 // if we reach here numbers are <= 9999, so at most 4 chars long
 246                 let mut n = n as usize; // possibly reduce 64bit math
 247
 248                 // decode 2 more chars, if > 2 chars
 249                 if n >= 100 {
 250                     let d1 = (n % 100) << 1;
 251                     n /= 100;
 252                     curr -= 2;
 253                     ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
 254                 }
 255
 256                 // decode last 1 or 2 chars
 257                 if n < 10 {
 258                     curr -= 1;
 259                     *buf_ptr.add(curr) = (n as u8) + b'0';
 260                 } else {
 261                     let d1 = n << 1;
 262                     curr -= 2;
 263                     ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
 264                 }
 265             }
 266
 267             // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
 268             // UTF-8 since `DEC_DIGITS_LUT` is
 269             let buf_slice = unsafe {
 270                 str::from_utf8_unchecked(
 271                     slice::from_raw_parts(buf_ptr.add(curr), buf.len() - curr))
 272             };
 273             f.pad_integral(is_nonnegative, "", buf_slice)
 274         }
 275
 276         $(#[stable(feature = "rust1", since = "1.0.0")]
 277         impl fmt::Display for $t {
 278             #[allow(unused_comparisons)]
 279             fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 280                 let is_nonnegative = *self >= 0;
 281                 let n = if is_nonnegative {
 282                     self.$conv_fn()
 283                 } else {
 284                     // convert the negative num to positive by summing 1 to it's 2 complement
 285                     (!self.$conv_fn()).wrapping_add(1)
 286                 };
 287                 $name(n, is_nonnegative, f)
 288             }
 289         })*
 290     };
 291 }
 292
 293 macro_rules! impl_Exp {
 294     ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
 295         fn $name(
 296             mut n: $u,
 297             is_nonnegative: bool,
 298             upper: bool,
 299             f: &mut fmt::Formatter<'_>
 300         ) -> fmt::Result {
 301             let (mut n, mut exponent, trailing_zeros, added_precision) = {
 302                 let mut exponent = 0;
 303                 // count and remove trailing decimal zeroes
 304                 while n % 10 == 0 && n >= 10 {
 305                     n /= 10;
 306                     exponent += 1;
 307                 }
 308
 309                 let (added_precision, subtracted_precision) = match f.precision() {
 310                     Some(fmt_prec) => {
 311                         // number of decimal digits minus 1
 312                         let mut tmp = n;
 313                         let mut prec = 0;
 314                         while tmp >= 10 {
 315                             tmp /= 10;
 316                             prec += 1;
 317                         }
 318                         (fmt_prec.saturating_sub(prec), prec.saturating_sub(fmt_prec))
 319                     }
 320                     None => (0, 0)
 321                 };
 322                 for _ in 1..subtracted_precision {
 323                     n /= 10;
 324                     exponent += 1;
 325                 }
 326                 if subtracted_precision != 0 {
 327                     let rem = n % 10;
 328                     n /= 10;
 329                     exponent += 1;
 330                     // round up last digit
 331                     if rem >= 5 {
 332                         n += 1;
 333                     }
 334                 }
 335                 (n, exponent, exponent, added_precision)
 336             };
 337
 338             // 39 digits (worst case u128) + . = 40
 339             // Since `curr` always decreases by the number of digits copied, this means
 340             // that `curr >= 0`.
 341             let mut buf = [MaybeUninit::<u8>::uninit(); 40];
 342             let mut curr = buf.len(); //index for buf
 343             let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
 344             let lut_ptr = DEC_DIGITS_LUT.as_ptr();
 345
 346             // decode 2 chars at a time
 347             while n >= 100 {
 348                 let d1 = ((n % 100) as usize) << 1;
 349                 curr -= 2;
 350                 // SAFETY: `d1 <= 198`, so we can copy from `lut_ptr[d1..d1 + 2]` since
 351                 // `DEC_DIGITS_LUT` has a length of 200.
 352                 unsafe {
 353                     ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
 354                 }
 355                 n /= 100;
 356                 exponent += 2;
 357             }
 358             // n is <= 99, so at most 2 chars long
 359             let mut n = n as isize; // possibly reduce 64bit math
 360             // decode second-to-last character
 361             if n >= 10 {
 362                 curr -= 1;
 363                 // SAFETY: Safe since `40 > curr >= 0` (see comment)
 364                 unsafe {
 365                     *buf_ptr.add(curr) = (n as u8 % 10_u8) + b'0';
 366                 }
 367                 n /= 10;
 368                 exponent += 1;
 369             }
 370             // add decimal point iff >1 mantissa digit will be printed
 371             if exponent != trailing_zeros || added_precision != 0 {
 372                 curr -= 1;
 373                 // SAFETY: Safe since `40 > curr >= 0`
 374                 unsafe {
 375                     *buf_ptr.add(curr) = b'.';
 376                 }
 377             }
 378
 379             // SAFETY: Safe since `40 > curr >= 0`
 380             let buf_slice = unsafe {
 381                 // decode last character
 382                 curr -= 1;
 383                 *buf_ptr.add(curr) = (n as u8) + b'0';
 384
 385                 let len = buf.len() - curr as usize;
 386                 slice::from_raw_parts(buf_ptr.add(curr), len)
 387             };
 388
 389             // stores 'e' (or 'E') and the up to 2-digit exponent
 390             let mut exp_buf = [MaybeUninit::<u8>::uninit(); 3];
 391             let exp_ptr = MaybeUninit::slice_as_mut_ptr(&mut exp_buf);
 392             // SAFETY: In either case, `exp_buf` is written within bounds and `exp_ptr[..len]`
 393             // is contained within `exp_buf` since `len <= 3`.
 394             let exp_slice = unsafe {
 395                 *exp_ptr.add(0) = if upper { b'E' } else { b'e' };
 396                 let len = if exponent < 10 {
 397                     *exp_ptr.add(1) = (exponent as u8) + b'0';
 398                     2
 399                 } else {
 400                     let off = exponent << 1;
 401                     ptr::copy_nonoverlapping(lut_ptr.add(off), exp_ptr.add(1), 2);
 402                     3
 403                 };
 404                 slice::from_raw_parts(exp_ptr, len)
 405             };
 406
 407             let parts = &[
 408                 numfmt::Part::Copy(buf_slice),
 409                 numfmt::Part::Zero(added_precision),
 410                 numfmt::Part::Copy(exp_slice)
 411             ];
 412             let sign = if !is_nonnegative {
 413                 "-"
 414             } else if f.sign_plus() {
 415                 "+"
 416             } else {
 417                 ""
 418             };
 419             let formatted = numfmt::Formatted{sign, parts};
 420             f.pad_formatted_parts(&formatted)
 421         }
 422
 423         $(
 424             #[stable(feature = "integer_exp_format", since = "1.42.0")]
 425             impl fmt::LowerExp for $t {
 426                 #[allow(unused_comparisons)]
 427                 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 428                     let is_nonnegative = *self >= 0;
 429                     let n = if is_nonnegative {
 430                         self.$conv_fn()
 431                     } else {
 432                         // convert the negative num to positive by summing 1 to it's 2 complement
 433                         (!self.$conv_fn()).wrapping_add(1)
 434                     };
 435                     $name(n, is_nonnegative, false, f)
 436                 }
 437             })*
 438         $(
 439             #[stable(feature = "integer_exp_format", since = "1.42.0")]
 440             impl fmt::UpperExp for $t {
 441                 #[allow(unused_comparisons)]
 442                 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 443                     let is_nonnegative = *self >= 0;
 444                     let n = if is_nonnegative {
 445                         self.$conv_fn()
 446                     } else {
 447                         // convert the negative num to positive by summing 1 to it's 2 complement
 448                         (!self.$conv_fn()).wrapping_add(1)
 449                     };
 450                     $name(n, is_nonnegative, true, f)
 451                 }
 452             })*
 453     };
 454 }
 455
 456 // Include wasm32 in here since it doesn't reflect the native pointer size, and
 457 // often cares strongly about getting a smaller code size.
 458 #[cfg(any(target_pointer_width = "64", target_arch = "wasm32"))]
 459 mod imp {
 460     use super::*;
 461     impl_Display!(
 462         i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
 463             as u64 via to_u64 named fmt_u64
 464     );
 465     impl_Exp!(
 466         i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
 467             as u64 via to_u64 named exp_u64
 468     );
 469 }
 470
 471 #[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
 472 mod imp {
 473     use super::*;
 474     impl_Display!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named fmt_u32);
 475     impl_Display!(i64, u64 as u64 via to_u64 named fmt_u64);
 476     impl_Exp!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32);
 477     impl_Exp!(i64, u64 as u64 via to_u64 named exp_u64);
 478 }
 479 impl_Exp!(i128, u128 as u128 via to_u128 named exp_u128);
 480
 481 /// Helper function for writing a u64 into `buf` going from last to first, with `curr`.
 482 fn parse_u64_into<const N: usize>(mut n: u64, buf: &mut [MaybeUninit<u8>; N], curr: &mut usize) {
 483     let buf_ptr = MaybeUninit::slice_as_mut_ptr(buf);
 484     let lut_ptr = DEC_DIGITS_LUT.as_ptr();
 485     assert!(*curr > 19);
 486
 487     // SAFETY:
 488     // Writes at most 19 characters into the buffer. Guaranteed that any ptr into LUT is at most
 489     // 198, so will never OOB. There is a check above that there are at least 19 characters
 490     // remaining.
 491     unsafe {
 492         if n >= 1e16 as u64 {
 493             let to_parse = n % 1e16 as u64;
 494             n /= 1e16 as u64;
 495
 496             // Some of these are nops but it looks more elegant this way.
 497             let d1 = ((to_parse / 1e14 as u64) % 100) << 1;
 498             let d2 = ((to_parse / 1e12 as u64) % 100) << 1;
 499             let d3 = ((to_parse / 1e10 as u64) % 100) << 1;
 500             let d4 = ((to_parse / 1e8 as u64) % 100) << 1;
 501             let d5 = ((to_parse / 1e6 as u64) % 100) << 1;
 502             let d6 = ((to_parse / 1e4 as u64) % 100) << 1;
 503             let d7 = ((to_parse / 1e2 as u64) % 100) << 1;
 504             let d8 = ((to_parse / 1e0 as u64) % 100) << 1;
 505
 506             *curr -= 16;
 507
 508             ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
 509             ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
 510             ptr::copy_nonoverlapping(lut_ptr.add(d3 as usize), buf_ptr.add(*curr + 4), 2);
 511             ptr::copy_nonoverlapping(lut_ptr.add(d4 as usize), buf_ptr.add(*curr + 6), 2);
 512             ptr::copy_nonoverlapping(lut_ptr.add(d5 as usize), buf_ptr.add(*curr + 8), 2);
 513             ptr::copy_nonoverlapping(lut_ptr.add(d6 as usize), buf_ptr.add(*curr + 10), 2);
 514             ptr::copy_nonoverlapping(lut_ptr.add(d7 as usize), buf_ptr.add(*curr + 12), 2);
 515             ptr::copy_nonoverlapping(lut_ptr.add(d8 as usize), buf_ptr.add(*curr + 14), 2);
 516         }
 517         if n >= 1e8 as u64 {
 518             let to_parse = n % 1e8 as u64;
 519             n /= 1e8 as u64;
 520
 521             // Some of these are nops but it looks more elegant this way.
 522             let d1 = ((to_parse / 1e6 as u64) % 100) << 1;
 523             let d2 = ((to_parse / 1e4 as u64) % 100) << 1;
 524             let d3 = ((to_parse / 1e2 as u64) % 100) << 1;
 525             let d4 = ((to_parse / 1e0 as u64) % 100) << 1;
 526             *curr -= 8;
 527
 528             ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
 529             ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
 530             ptr::copy_nonoverlapping(lut_ptr.add(d3 as usize), buf_ptr.add(*curr + 4), 2);
 531             ptr::copy_nonoverlapping(lut_ptr.add(d4 as usize), buf_ptr.add(*curr + 6), 2);
 532         }
 533         // `n` < 1e8 < (1 << 32)
 534         let mut n = n as u32;
 535         if n >= 1e4 as u32 {
 536             let to_parse = n % 1e4 as u32;
 537             n /= 1e4 as u32;
 538
 539             let d1 = (to_parse / 100) << 1;
 540             let d2 = (to_parse % 100) << 1;
 541             *curr -= 4;
 542
 543             ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr + 0), 2);
 544             ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(*curr + 2), 2);
 545         }
 546
 547         // `n` < 1e4 < (1 << 16)
 548         let mut n = n as u16;
 549         if n >= 100 {
 550             let d1 = (n % 100) << 1;
 551             n /= 100;
 552             *curr -= 2;
 553             ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr), 2);
 554         }
 555
 556         // decode last 1 or 2 chars
 557         if n < 10 {
 558             *curr -= 1;
 559             *buf_ptr.add(*curr) = (n as u8) + b'0';
 560         } else {
 561             let d1 = n << 1;
 562             *curr -= 2;
 563             ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(*curr), 2);
 564         }
 565     }
 566 }
 567
 568 #[stable(feature = "rust1", since = "1.0.0")]
 569 impl fmt::Display for u128 {
 570     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 571         fmt_u128(*self, true, f)
 572     }
 573 }
 574
 575 #[stable(feature = "rust1", since = "1.0.0")]
 576 impl fmt::Display for i128 {
 577     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 578         let is_nonnegative = *self >= 0;
 579         let n = if is_nonnegative {
 580             self.to_u128()
 581         } else {
 582             // convert the negative num to positive by summing 1 to it's 2 complement
 583             (!self.to_u128()).wrapping_add(1)
 584         };
 585         fmt_u128(n, is_nonnegative, f)
 586     }
 587 }
 588
 589 /// Specialized optimization for u128. Instead of taking two items at a time, it splits
 590 /// into at most 2 u64s, and then chunks by 10e16, 10e8, 10e4, 10e2, and then 10e1.
 591 /// It also has to handle 1 last item, as 10^40 > 2^128 > 10^39, whereas
 592 /// 10^20 > 2^64 > 10^19.
 593 fn fmt_u128(n: u128, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 594     // 2^128 is about 3*10^38, so 39 gives an extra byte of space
 595     let mut buf = [MaybeUninit::<u8>::uninit(); 39];
 596     let mut curr = buf.len();
 597
 598     let (n, rem) = udiv_1e19(n);
 599     parse_u64_into(rem, &mut buf, &mut curr);
 600
 601     if n != 0 {
 602         // 0 pad up to point
 603         let target = buf.len() - 19;
 604         // SAFETY: Guaranteed that we wrote at most 19 bytes, and there must be space
 605         // remaining since it has length 39
 606         unsafe {
 607             ptr::write_bytes(
 608                 MaybeUninit::slice_as_mut_ptr(&mut buf).add(target),
 609                 b'0',
 610                 curr - target,
 611             );
 612         }
 613         curr = target;
 614
 615         let (n, rem) = udiv_1e19(n);
 616         parse_u64_into(rem, &mut buf, &mut curr);
 617         // Should this following branch be annotated with unlikely?
 618         if n != 0 {
 619             let target = buf.len() - 38;
 620             // The raw `buf_ptr` pointer is only valid until `buf` is used the next time,
 621             // buf `buf` is not used in this scope so we are good.
 622             let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
 623             // SAFETY: At this point we wrote at most 38 bytes, pad up to that point,
 624             // There can only be at most 1 digit remaining.
 625             unsafe {
 626                 ptr::write_bytes(buf_ptr.add(target), b'0', curr - target);
 627                 curr = target - 1;
 628                 *buf_ptr.add(curr) = (n as u8) + b'0';
 629             }
 630         }
 631     }
 632
 633     // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
 634     // UTF-8 since `DEC_DIGITS_LUT` is
 635     let buf_slice = unsafe {
 636         str::from_utf8_unchecked(slice::from_raw_parts(
 637             MaybeUninit::slice_as_mut_ptr(&mut buf).add(curr),
 638             buf.len() - curr,
 639         ))
 640     };
 641     f.pad_integral(is_nonnegative, "", buf_slice)
 642 }
 643
 644 /// Partition of `n` into n > 1e19 and rem <= 1e19
 645 ///
 646 /// Integer division algorithm is based on the following paper:
 647 ///
 648 ///   T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
 649 ///   in Proc. of the SIGPLAN94 Conference on Programming Language Design and
 650 ///   Implementation, 1994, pp. 61–72
 651 ///
 652 fn udiv_1e19(n: u128) -> (u128, u64) {
 653     const DIV: u64 = 1e19 as u64;
 654     const FACTOR: u128 = 156927543384667019095894735580191660403;
 655
 656     let quot = if n < 1 << 83 {
 657         ((n >> 19) as u64 / (DIV >> 19)) as u128
 658     } else {
 659         u128_mulhi(n, FACTOR) >> 62
 660     };
 661
 662     let rem = (n - quot * DIV as u128) as u64;
 663     (quot, rem)
 664 }
 665
 666 /// Multiply unsigned 128 bit integers, return upper 128 bits of the result
 667 #[inline]
 668 fn u128_mulhi(x: u128, y: u128) -> u128 {
 669     let x_lo = x as u64;
 670     let x_hi = (x >> 64) as u64;
 671     let y_lo = y as u64;
 672     let y_hi = (y >> 64) as u64;
 673
 674     // handle possibility of overflow
 675     let carry = (x_lo as u128 * y_lo as u128) >> 64;
 676     let m = x_lo as u128 * y_hi as u128 + carry;
 677     let high1 = m >> 64;
 678
 679     let m_lo = m as u64;
 680     let high2 = (x_hi as u128 * y_lo as u128 + m_lo as u128) >> 64;
 681
 682     x_hi as u128 * y_hi as u128 + high1 + high2
 683 }