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