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