summaryrefslogtreecommitdiffstats
path: root/library/core/src/fmt/num.rs
diff options
context:
space:
mode:
Diffstat (limited to 'library/core/src/fmt/num.rs')
-rw-r--r--library/core/src/fmt/num.rs683
1 files changed, 683 insertions, 0 deletions
diff --git a/library/core/src/fmt/num.rs b/library/core/src/fmt/num.rs
new file mode 100644
index 000000000..25789d37c
--- /dev/null
+++ b/library/core/src/fmt/num.rs
@@ -0,0 +1,683 @@
+//! Integer and floating-point number formatting
+
+use crate::fmt;
+use crate::mem::MaybeUninit;
+use crate::num::fmt as numfmt;
+use crate::ops::{Div, Rem, Sub};
+use crate::ptr;
+use crate::slice;
+use crate::str;
+
+#[doc(hidden)]
+trait DisplayInt:
+ PartialEq + PartialOrd + Div<Output = Self> + Rem<Output = Self> + Sub<Output = Self> + Copy
+{
+ fn zero() -> Self;
+ fn from_u8(u: u8) -> Self;
+ fn to_u8(&self) -> u8;
+ fn to_u16(&self) -> u16;
+ fn to_u32(&self) -> u32;
+ fn to_u64(&self) -> u64;
+ fn to_u128(&self) -> u128;
+}
+
+macro_rules! impl_int {
+ ($($t:ident)*) => (
+ $(impl DisplayInt for $t {
+ fn zero() -> Self { 0 }
+ fn from_u8(u: u8) -> Self { u as Self }
+ fn to_u8(&self) -> u8 { *self as u8 }
+ fn to_u16(&self) -> u16 { *self as u16 }
+ fn to_u32(&self) -> u32 { *self as u32 }
+ fn to_u64(&self) -> u64 { *self as u64 }
+ fn to_u128(&self) -> u128 { *self as u128 }
+ })*
+ )
+}
+macro_rules! impl_uint {
+ ($($t:ident)*) => (
+ $(impl DisplayInt for $t {
+ fn zero() -> Self { 0 }
+ fn from_u8(u: u8) -> Self { u as Self }
+ fn to_u8(&self) -> u8 { *self as u8 }
+ fn to_u16(&self) -> u16 { *self as u16 }
+ fn to_u32(&self) -> u32 { *self as u32 }
+ fn to_u64(&self) -> u64 { *self as u64 }
+ fn to_u128(&self) -> u128 { *self as u128 }
+ })*
+ )
+}
+
+impl_int! { i8 i16 i32 i64 i128 isize }
+impl_uint! { u8 u16 u32 u64 u128 usize }
+
+/// A type that represents a specific radix
+#[doc(hidden)]
+trait GenericRadix: Sized {
+ /// The number of digits.
+ const BASE: u8;
+
+ /// A radix-specific prefix string.
+ const PREFIX: &'static str;
+
+ /// Converts an integer to corresponding radix digit.
+ fn digit(x: u8) -> u8;
+
+ /// Format an integer using the radix using a formatter.
+ fn fmt_int<T: DisplayInt>(&self, mut x: T, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // The radix can be as low as 2, so we need a buffer of at least 128
+ // characters for a base 2 number.
+ let zero = T::zero();
+ let is_nonnegative = x >= zero;
+ let mut buf = [MaybeUninit::<u8>::uninit(); 128];
+ let mut curr = buf.len();
+ let base = T::from_u8(Self::BASE);
+ if is_nonnegative {
+ // Accumulate each digit of the number from the least significant
+ // to the most significant figure.
+ for byte in buf.iter_mut().rev() {
+ let n = x % base; // Get the current place value.
+ x = x / base; // Deaccumulate the number.
+ byte.write(Self::digit(n.to_u8())); // Store the digit in the buffer.
+ curr -= 1;
+ if x == zero {
+ // No more digits left to accumulate.
+ break;
+ };
+ }
+ } else {
+ // Do the same as above, but accounting for two's complement.
+ for byte in buf.iter_mut().rev() {
+ let n = zero - (x % base); // Get the current place value.
+ x = x / base; // Deaccumulate the number.
+ byte.write(Self::digit(n.to_u8())); // Store the digit in the buffer.
+ curr -= 1;
+ if x == zero {
+ // No more digits left to accumulate.
+ break;
+ };
+ }
+ }
+ let buf = &buf[curr..];
+ // SAFETY: The only chars in `buf` are created by `Self::digit` which are assumed to be
+ // valid UTF-8
+ let buf = unsafe {
+ str::from_utf8_unchecked(slice::from_raw_parts(
+ MaybeUninit::slice_as_ptr(buf),
+ buf.len(),
+ ))
+ };
+ f.pad_integral(is_nonnegative, Self::PREFIX, buf)
+ }
+}
+
+/// A binary (base 2) radix
+#[derive(Clone, PartialEq)]
+struct Binary;
+
+/// An octal (base 8) radix
+#[derive(Clone, PartialEq)]
+struct Octal;
+
+/// A hexadecimal (base 16) radix, formatted with lower-case characters
+#[derive(Clone, PartialEq)]
+struct LowerHex;
+
+/// A hexadecimal (base 16) radix, formatted with upper-case characters
+#[derive(Clone, PartialEq)]
+struct UpperHex;
+
+macro_rules! radix {
+ ($T:ident, $base:expr, $prefix:expr, $($x:pat => $conv:expr),+) => {
+ impl GenericRadix for $T {
+ const BASE: u8 = $base;
+ const PREFIX: &'static str = $prefix;
+ fn digit(x: u8) -> u8 {
+ match x {
+ $($x => $conv,)+
+ x => panic!("number not in the range 0..={}: {}", Self::BASE - 1, x),
+ }
+ }
+ }
+ }
+}
+
+radix! { Binary, 2, "0b", x @ 0 ..= 1 => b'0' + x }
+radix! { Octal, 8, "0o", x @ 0 ..= 7 => b'0' + x }
+radix! { LowerHex, 16, "0x", x @ 0 ..= 9 => b'0' + x, x @ 10 ..= 15 => b'a' + (x - 10) }
+radix! { UpperHex, 16, "0x", x @ 0 ..= 9 => b'0' + x, x @ 10 ..= 15 => b'A' + (x - 10) }
+
+macro_rules! int_base {
+ (fmt::$Trait:ident for $T:ident as $U:ident -> $Radix:ident) => {
+ #[stable(feature = "rust1", since = "1.0.0")]
+ impl fmt::$Trait for $T {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ $Radix.fmt_int(*self as $U, f)
+ }
+ }
+ };
+}
+
+macro_rules! integer {
+ ($Int:ident, $Uint:ident) => {
+ int_base! { fmt::Binary for $Int as $Uint -> Binary }
+ int_base! { fmt::Octal for $Int as $Uint -> Octal }
+ int_base! { fmt::LowerHex for $Int as $Uint -> LowerHex }
+ int_base! { fmt::UpperHex for $Int as $Uint -> UpperHex }
+
+ int_base! { fmt::Binary for $Uint as $Uint -> Binary }
+ int_base! { fmt::Octal for $Uint as $Uint -> Octal }
+ int_base! { fmt::LowerHex for $Uint as $Uint -> LowerHex }
+ int_base! { fmt::UpperHex for $Uint as $Uint -> UpperHex }
+ };
+}
+integer! { isize, usize }
+integer! { i8, u8 }
+integer! { i16, u16 }
+integer! { i32, u32 }
+integer! { i64, u64 }
+integer! { i128, u128 }
+macro_rules! debug {
+ ($($T:ident)*) => {$(
+ #[stable(feature = "rust1", since = "1.0.0")]
+ impl fmt::Debug for $T {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ if f.debug_lower_hex() {
+ fmt::LowerHex::fmt(self, f)
+ } else if f.debug_upper_hex() {
+ fmt::UpperHex::fmt(self, f)
+ } else {
+ fmt::Display::fmt(self, f)
+ }
+ }
+ }
+ )*};
+}
+debug! {
+ i8 i16 i32 i64 i128 isize
+ u8 u16 u32 u64 u128 usize
+}
+
+// 2 digit decimal look up table
+static DEC_DIGITS_LUT: &[u8; 200] = b"0001020304050607080910111213141516171819\
+ 2021222324252627282930313233343536373839\
+ 4041424344454647484950515253545556575859\
+ 6061626364656667686970717273747576777879\
+ 8081828384858687888990919293949596979899";
+
+macro_rules! impl_Display {
+ ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
+ fn $name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // 2^128 is about 3*10^38, so 39 gives an extra byte of space
+ let mut buf = [MaybeUninit::<u8>::uninit(); 39];
+ let mut curr = buf.len() as isize;
+ let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
+ let lut_ptr = DEC_DIGITS_LUT.as_ptr();
+
+ // SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
+ // can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
+ // that it's OK to copy into `buf_ptr`, notice that at the beginning
+ // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
+ // each step this is kept the same as `n` is divided. Since `n` is always
+ // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
+ // is safe to access.
+ unsafe {
+ // need at least 16 bits for the 4-characters-at-a-time to work.
+ assert!(crate::mem::size_of::<$u>() >= 2);
+
+ // eagerly decode 4 characters at a time
+ while n >= 10000 {
+ let rem = (n % 10000) as isize;
+ n /= 10000;
+
+ let d1 = (rem / 100) << 1;
+ let d2 = (rem % 100) << 1;
+ curr -= 4;
+
+ // We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
+ // otherwise `curr < 0`. But then `n` was originally at least `10000^10`
+ // which is `10^40 > 2^128 > n`.
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d2), buf_ptr.offset(curr + 2), 2);
+ }
+
+ // if we reach here numbers are <= 9999, so at most 4 chars long
+ let mut n = n as isize; // possibly reduce 64bit math
+
+ // decode 2 more chars, if > 2 chars
+ if n >= 100 {
+ let d1 = (n % 100) << 1;
+ n /= 100;
+ curr -= 2;
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
+ }
+
+ // decode last 1 or 2 chars
+ if n < 10 {
+ curr -= 1;
+ *buf_ptr.offset(curr) = (n as u8) + b'0';
+ } else {
+ let d1 = n << 1;
+ curr -= 2;
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
+ }
+ }
+
+ // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
+ // UTF-8 since `DEC_DIGITS_LUT` is
+ let buf_slice = unsafe {
+ str::from_utf8_unchecked(
+ slice::from_raw_parts(buf_ptr.offset(curr), buf.len() - curr as usize))
+ };
+ f.pad_integral(is_nonnegative, "", buf_slice)
+ }
+
+ $(#[stable(feature = "rust1", since = "1.0.0")]
+ impl fmt::Display for $t {
+ #[allow(unused_comparisons)]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let is_nonnegative = *self >= 0;
+ let n = if is_nonnegative {
+ self.$conv_fn()
+ } else {
+ // convert the negative num to positive by summing 1 to it's 2 complement
+ (!self.$conv_fn()).wrapping_add(1)
+ };
+ $name(n, is_nonnegative, f)
+ }
+ })*
+ };
+}
+
+macro_rules! impl_Exp {
+ ($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
+ fn $name(
+ mut n: $u,
+ is_nonnegative: bool,
+ upper: bool,
+ f: &mut fmt::Formatter<'_>
+ ) -> fmt::Result {
+ let (mut n, mut exponent, trailing_zeros, added_precision) = {
+ let mut exponent = 0;
+ // count and remove trailing decimal zeroes
+ while n % 10 == 0 && n >= 10 {
+ n /= 10;
+ exponent += 1;
+ }
+
+ let (added_precision, subtracted_precision) = match f.precision() {
+ Some(fmt_prec) => {
+ // number of decimal digits minus 1
+ let mut tmp = n;
+ let mut prec = 0;
+ while tmp >= 10 {
+ tmp /= 10;
+ prec += 1;
+ }
+ (fmt_prec.saturating_sub(prec), prec.saturating_sub(fmt_prec))
+ }
+ None => (0, 0)
+ };
+ for _ in 1..subtracted_precision {
+ n /= 10;
+ exponent += 1;
+ }
+ if subtracted_precision != 0 {
+ let rem = n % 10;
+ n /= 10;
+ exponent += 1;
+ // round up last digit
+ if rem >= 5 {
+ n += 1;
+ }
+ }
+ (n, exponent, exponent, added_precision)
+ };
+
+ // 39 digits (worst case u128) + . = 40
+ // Since `curr` always decreases by the number of digits copied, this means
+ // that `curr >= 0`.
+ let mut buf = [MaybeUninit::<u8>::uninit(); 40];
+ let mut curr = buf.len() as isize; //index for buf
+ let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
+ let lut_ptr = DEC_DIGITS_LUT.as_ptr();
+
+ // decode 2 chars at a time
+ while n >= 100 {
+ let d1 = ((n % 100) as isize) << 1;
+ curr -= 2;
+ // SAFETY: `d1 <= 198`, so we can copy from `lut_ptr[d1..d1 + 2]` since
+ // `DEC_DIGITS_LUT` has a length of 200.
+ unsafe {
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
+ }
+ n /= 100;
+ exponent += 2;
+ }
+ // n is <= 99, so at most 2 chars long
+ let mut n = n as isize; // possibly reduce 64bit math
+ // decode second-to-last character
+ if n >= 10 {
+ curr -= 1;
+ // SAFETY: Safe since `40 > curr >= 0` (see comment)
+ unsafe {
+ *buf_ptr.offset(curr) = (n as u8 % 10_u8) + b'0';
+ }
+ n /= 10;
+ exponent += 1;
+ }
+ // add decimal point iff >1 mantissa digit will be printed
+ if exponent != trailing_zeros || added_precision != 0 {
+ curr -= 1;
+ // SAFETY: Safe since `40 > curr >= 0`
+ unsafe {
+ *buf_ptr.offset(curr) = b'.';
+ }
+ }
+
+ // SAFETY: Safe since `40 > curr >= 0`
+ let buf_slice = unsafe {
+ // decode last character
+ curr -= 1;
+ *buf_ptr.offset(curr) = (n as u8) + b'0';
+
+ let len = buf.len() - curr as usize;
+ slice::from_raw_parts(buf_ptr.offset(curr), len)
+ };
+
+ // stores 'e' (or 'E') and the up to 2-digit exponent
+ let mut exp_buf = [MaybeUninit::<u8>::uninit(); 3];
+ let exp_ptr = MaybeUninit::slice_as_mut_ptr(&mut exp_buf);
+ // SAFETY: In either case, `exp_buf` is written within bounds and `exp_ptr[..len]`
+ // is contained within `exp_buf` since `len <= 3`.
+ let exp_slice = unsafe {
+ *exp_ptr.offset(0) = if upper { b'E' } else { b'e' };
+ let len = if exponent < 10 {
+ *exp_ptr.offset(1) = (exponent as u8) + b'0';
+ 2
+ } else {
+ let off = exponent << 1;
+ ptr::copy_nonoverlapping(lut_ptr.offset(off), exp_ptr.offset(1), 2);
+ 3
+ };
+ slice::from_raw_parts(exp_ptr, len)
+ };
+
+ let parts = &[
+ numfmt::Part::Copy(buf_slice),
+ numfmt::Part::Zero(added_precision),
+ numfmt::Part::Copy(exp_slice)
+ ];
+ let sign = if !is_nonnegative {
+ "-"
+ } else if f.sign_plus() {
+ "+"
+ } else {
+ ""
+ };
+ let formatted = numfmt::Formatted{sign, parts};
+ f.pad_formatted_parts(&formatted)
+ }
+
+ $(
+ #[stable(feature = "integer_exp_format", since = "1.42.0")]
+ impl fmt::LowerExp for $t {
+ #[allow(unused_comparisons)]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let is_nonnegative = *self >= 0;
+ let n = if is_nonnegative {
+ self.$conv_fn()
+ } else {
+ // convert the negative num to positive by summing 1 to it's 2 complement
+ (!self.$conv_fn()).wrapping_add(1)
+ };
+ $name(n, is_nonnegative, false, f)
+ }
+ })*
+ $(
+ #[stable(feature = "integer_exp_format", since = "1.42.0")]
+ impl fmt::UpperExp for $t {
+ #[allow(unused_comparisons)]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let is_nonnegative = *self >= 0;
+ let n = if is_nonnegative {
+ self.$conv_fn()
+ } else {
+ // convert the negative num to positive by summing 1 to it's 2 complement
+ (!self.$conv_fn()).wrapping_add(1)
+ };
+ $name(n, is_nonnegative, true, f)
+ }
+ })*
+ };
+}
+
+// Include wasm32 in here since it doesn't reflect the native pointer size, and
+// often cares strongly about getting a smaller code size.
+#[cfg(any(target_pointer_width = "64", target_arch = "wasm32"))]
+mod imp {
+ use super::*;
+ impl_Display!(
+ i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
+ as u64 via to_u64 named fmt_u64
+ );
+ impl_Exp!(
+ i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
+ as u64 via to_u64 named exp_u64
+ );
+}
+
+#[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
+mod imp {
+ use super::*;
+ impl_Display!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named fmt_u32);
+ impl_Display!(i64, u64 as u64 via to_u64 named fmt_u64);
+ impl_Exp!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32);
+ impl_Exp!(i64, u64 as u64 via to_u64 named exp_u64);
+}
+impl_Exp!(i128, u128 as u128 via to_u128 named exp_u128);
+
+/// Helper function for writing a u64 into `buf` going from last to first, with `curr`.
+fn parse_u64_into<const N: usize>(mut n: u64, buf: &mut [MaybeUninit<u8>; N], curr: &mut isize) {
+ let buf_ptr = MaybeUninit::slice_as_mut_ptr(buf);
+ let lut_ptr = DEC_DIGITS_LUT.as_ptr();
+ assert!(*curr > 19);
+
+ // SAFETY:
+ // Writes at most 19 characters into the buffer. Guaranteed that any ptr into LUT is at most
+ // 198, so will never OOB. There is a check above that there are at least 19 characters
+ // remaining.
+ unsafe {
+ if n >= 1e16 as u64 {
+ let to_parse = n % 1e16 as u64;
+ n /= 1e16 as u64;
+
+ // Some of these are nops but it looks more elegant this way.
+ let d1 = ((to_parse / 1e14 as u64) % 100) << 1;
+ let d2 = ((to_parse / 1e12 as u64) % 100) << 1;
+ let d3 = ((to_parse / 1e10 as u64) % 100) << 1;
+ let d4 = ((to_parse / 1e8 as u64) % 100) << 1;
+ let d5 = ((to_parse / 1e6 as u64) % 100) << 1;
+ let d6 = ((to_parse / 1e4 as u64) % 100) << 1;
+ let d7 = ((to_parse / 1e2 as u64) % 100) << 1;
+ let d8 = ((to_parse / 1e0 as u64) % 100) << 1;
+
+ *curr -= 16;
+
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1 as isize), buf_ptr.offset(*curr + 0), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d2 as isize), buf_ptr.offset(*curr + 2), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d3 as isize), buf_ptr.offset(*curr + 4), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d4 as isize), buf_ptr.offset(*curr + 6), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d5 as isize), buf_ptr.offset(*curr + 8), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d6 as isize), buf_ptr.offset(*curr + 10), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d7 as isize), buf_ptr.offset(*curr + 12), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d8 as isize), buf_ptr.offset(*curr + 14), 2);
+ }
+ if n >= 1e8 as u64 {
+ let to_parse = n % 1e8 as u64;
+ n /= 1e8 as u64;
+
+ // Some of these are nops but it looks more elegant this way.
+ let d1 = ((to_parse / 1e6 as u64) % 100) << 1;
+ let d2 = ((to_parse / 1e4 as u64) % 100) << 1;
+ let d3 = ((to_parse / 1e2 as u64) % 100) << 1;
+ let d4 = ((to_parse / 1e0 as u64) % 100) << 1;
+ *curr -= 8;
+
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1 as isize), buf_ptr.offset(*curr + 0), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d2 as isize), buf_ptr.offset(*curr + 2), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d3 as isize), buf_ptr.offset(*curr + 4), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d4 as isize), buf_ptr.offset(*curr + 6), 2);
+ }
+ // `n` < 1e8 < (1 << 32)
+ let mut n = n as u32;
+ if n >= 1e4 as u32 {
+ let to_parse = n % 1e4 as u32;
+ n /= 1e4 as u32;
+
+ let d1 = (to_parse / 100) << 1;
+ let d2 = (to_parse % 100) << 1;
+ *curr -= 4;
+
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1 as isize), buf_ptr.offset(*curr + 0), 2);
+ ptr::copy_nonoverlapping(lut_ptr.offset(d2 as isize), buf_ptr.offset(*curr + 2), 2);
+ }
+
+ // `n` < 1e4 < (1 << 16)
+ let mut n = n as u16;
+ if n >= 100 {
+ let d1 = (n % 100) << 1;
+ n /= 100;
+ *curr -= 2;
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1 as isize), buf_ptr.offset(*curr), 2);
+ }
+
+ // decode last 1 or 2 chars
+ if n < 10 {
+ *curr -= 1;
+ *buf_ptr.offset(*curr) = (n as u8) + b'0';
+ } else {
+ let d1 = n << 1;
+ *curr -= 2;
+ ptr::copy_nonoverlapping(lut_ptr.offset(d1 as isize), buf_ptr.offset(*curr), 2);
+ }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl fmt::Display for u128 {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt_u128(*self, true, f)
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl fmt::Display for i128 {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let is_nonnegative = *self >= 0;
+ let n = if is_nonnegative {
+ self.to_u128()
+ } else {
+ // convert the negative num to positive by summing 1 to it's 2 complement
+ (!self.to_u128()).wrapping_add(1)
+ };
+ fmt_u128(n, is_nonnegative, f)
+ }
+}
+
+/// Specialized optimization for u128. Instead of taking two items at a time, it splits
+/// into at most 2 u64s, and then chunks by 10e16, 10e8, 10e4, 10e2, and then 10e1.
+/// It also has to handle 1 last item, as 10^40 > 2^128 > 10^39, whereas
+/// 10^20 > 2^64 > 10^19.
+fn fmt_u128(n: u128, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // 2^128 is about 3*10^38, so 39 gives an extra byte of space
+ let mut buf = [MaybeUninit::<u8>::uninit(); 39];
+ let mut curr = buf.len() as isize;
+
+ let (n, rem) = udiv_1e19(n);
+ parse_u64_into(rem, &mut buf, &mut curr);
+
+ if n != 0 {
+ // 0 pad up to point
+ let target = (buf.len() - 19) as isize;
+ // SAFETY: Guaranteed that we wrote at most 19 bytes, and there must be space
+ // remaining since it has length 39
+ unsafe {
+ ptr::write_bytes(
+ MaybeUninit::slice_as_mut_ptr(&mut buf).offset(target),
+ b'0',
+ (curr - target) as usize,
+ );
+ }
+ curr = target;
+
+ let (n, rem) = udiv_1e19(n);
+ parse_u64_into(rem, &mut buf, &mut curr);
+ // Should this following branch be annotated with unlikely?
+ if n != 0 {
+ let target = (buf.len() - 38) as isize;
+ // The raw `buf_ptr` pointer is only valid until `buf` is used the next time,
+ // buf `buf` is not used in this scope so we are good.
+ let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
+ // SAFETY: At this point we wrote at most 38 bytes, pad up to that point,
+ // There can only be at most 1 digit remaining.
+ unsafe {
+ ptr::write_bytes(buf_ptr.offset(target), b'0', (curr - target) as usize);
+ curr = target - 1;
+ *buf_ptr.offset(curr) = (n as u8) + b'0';
+ }
+ }
+ }
+
+ // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
+ // UTF-8 since `DEC_DIGITS_LUT` is
+ let buf_slice = unsafe {
+ str::from_utf8_unchecked(slice::from_raw_parts(
+ MaybeUninit::slice_as_mut_ptr(&mut buf).offset(curr),
+ buf.len() - curr as usize,
+ ))
+ };
+ f.pad_integral(is_nonnegative, "", buf_slice)
+}
+
+/// Partition of `n` into n > 1e19 and rem <= 1e19
+///
+/// Integer division algorithm is based on the following paper:
+///
+/// T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
+/// in Proc. of the SIGPLAN94 Conference on Programming Language Design and
+/// Implementation, 1994, pp. 61–72
+///
+fn udiv_1e19(n: u128) -> (u128, u64) {
+ const DIV: u64 = 1e19 as u64;
+ const FACTOR: u128 = 156927543384667019095894735580191660403;
+
+ let quot = if n < 1 << 83 {
+ ((n >> 19) as u64 / (DIV >> 19)) as u128
+ } else {
+ u128_mulhi(n, FACTOR) >> 62
+ };
+
+ let rem = (n - quot * DIV as u128) as u64;
+ (quot, rem)
+}
+
+/// Multiply unsigned 128 bit integers, return upper 128 bits of the result
+#[inline]
+fn u128_mulhi(x: u128, y: u128) -> u128 {
+ let x_lo = x as u64;
+ let x_hi = (x >> 64) as u64;
+ let y_lo = y as u64;
+ let y_hi = (y >> 64) as u64;
+
+ // handle possibility of overflow
+ let carry = (x_lo as u128 * y_lo as u128) >> 64;
+ let m = x_lo as u128 * y_hi as u128 + carry;
+ let high1 = m >> 64;
+
+ let m_lo = m as u64;
+ let high2 = (x_hi as u128 * y_lo as u128 + m_lo as u128) >> 64;
+
+ x_hi as u128 * y_hi as u128 + high1 + high2
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-26 14:14:00 +0000