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