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 | #[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 | |
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 | #[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 | } |
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 | #[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 | |
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 | /// |
56 | /// # Safety |
57 | /// |
58 | /// `digit` must return an ASCII character. |
59 | #[doc (hidden)] |
60 | unsafe 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)] |
120 | struct Binary; |
121 | |
122 | /// An octal (base 8) radix |
123 | #[derive (Clone, PartialEq)] |
124 | struct Octal; |
125 | |
126 | /// A hexadecimal (base 16) radix, formatted with lower-case characters |
127 | #[derive (Clone, PartialEq)] |
128 | struct LowerHex; |
129 | |
130 | /// A hexadecimal (base 16) radix, formatted with upper-case characters |
131 | #[derive (Clone, PartialEq)] |
132 | struct UpperHex; |
133 | |
134 | macro_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 | |
149 | radix! { Binary, 2, "0b" , x @ 0 ..= 1 => b'0' + x } |
150 | radix! { Octal, 8, "0o" , x @ 0 ..= 7 => b'0' + x } |
151 | radix! { LowerHex, 16, "0x" , x @ 0 ..= 9 => b'0' + x, x @ 10 ..= 15 => b'a' + (x - 10) } |
152 | radix! { UpperHex, 16, "0x" , x @ 0 ..= 9 => b'0' + x, x @ 10 ..= 15 => b'A' + (x - 10) } |
153 | |
154 | macro_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 | |
165 | macro_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 | } |
178 | integer! { isize, usize } |
179 | integer! { i8, u8 } |
180 | integer! { i16, u16 } |
181 | integer! { i32, u32 } |
182 | integer! { i64, u64 } |
183 | integer! { i128, u128 } |
184 | macro_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 | } |
201 | debug! { |
202 | i8 i16 i32 i64 i128 isize |
203 | u8 u16 u32 u64 u128 usize |
204 | } |
205 | |
206 | // 2 digit decimal look up table |
207 | static DEC_DIGITS_LUT: &[u8; 200] = b"0001020304050607080910111213141516171819\ |
208 | 2021222324252627282930313233343536373839\ |
209 | 4041424344454647484950515253545556575859\ |
210 | 6061626364656667686970717273747576777879\ |
211 | 8081828384858687888990919293949596979899" ; |
212 | |
213 | macro_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 | |
297 | macro_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" ))] |
469 | mod 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" )))] |
482 | mod 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 | } |
489 | impl_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`. |
492 | fn 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" )] |
579 | impl 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" )] |
586 | impl 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. |
603 | fn 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 | /// |
662 | fn 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 ] |
678 | fn 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 | |