1 //! Integer and floating-point number formatting
4 use crate::mem
::MaybeUninit
;
5 use crate::num
::fmt
as numfmt
;
6 use crate::ops
::{Div, Rem, Sub}
;
13 PartialEq
+ PartialOrd
+ Div
<Output
= Self> + Rem
<Output
= Self> + Sub
<Output
= Self> + Copy
16 fn from_u8(u
: u8) -> Self;
17 fn to_u8(&self) -> u8;
18 fn to_u16(&self) -> u16;
19 fn to_u32(&self) -> u32;
20 fn to_u64(&self) -> u64;
21 fn to_u128(&self) -> u128
;
24 macro_rules
! impl_int
{
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 }
37 macro_rules
! impl_uint
{
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 }
51 impl_int
! { i8 i16 i32 i64 i128 isize }
52 impl_uint
! { u8 u16 u32 u64 u128 usize }
54 /// A type that represents a specific radix
56 trait GenericRadix
: Sized
{
57 /// The number of digits.
60 /// A radix-specific prefix string.
61 const PREFIX
: &'
static str;
63 /// Converts an integer to corresponding radix digit.
64 fn digit(x
: u8) -> u8;
66 /// Format an integer using the radix using a formatter.
67 fn fmt_int
<T
: DisplayInt
>(&self, mut x
: T
, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
68 // The radix can be as low as 2, so we need a buffer of at least 128
69 // characters for a base 2 number.
71 let is_nonnegative
= x
>= zero
;
72 let mut buf
= [MaybeUninit
::<u8>::uninit(); 128];
73 let mut curr
= buf
.len();
74 let base
= T
::from_u8(Self::BASE
);
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() {
79 let n
= x
% base
; // Get the current place value.
80 x
= x
/ base
; // Deaccumulate the number.
81 byte
.write(Self::digit(n
.to_u8())); // Store the digit in the buffer.
84 // No more digits left to accumulate.
89 // Do the same as above, but accounting for two's complement.
90 for byte
in buf
.iter_mut().rev() {
91 let n
= zero
- (x
% base
); // Get the current place value.
92 x
= x
/ base
; // Deaccumulate the number.
93 byte
.write(Self::digit(n
.to_u8())); // Store the digit in the buffer.
96 // No more digits left to accumulate.
101 let buf
= &buf
[curr
..];
102 // SAFETY: The only chars in `buf` are created by `Self::digit` which are assumed to be
105 str::from_utf8_unchecked(slice
::from_raw_parts(
106 MaybeUninit
::slice_as_ptr(buf
),
110 f
.pad_integral(is_nonnegative
, Self::PREFIX
, buf
)
114 /// A binary (base 2) radix
115 #[derive(Clone, PartialEq)]
118 /// An octal (base 8) radix
119 #[derive(Clone, PartialEq)]
122 /// A hexadecimal (base 16) radix, formatted with lower-case characters
123 #[derive(Clone, PartialEq)]
126 /// A hexadecimal (base 16) radix, formatted with upper-case characters
127 #[derive(Clone, PartialEq)]
131 ($T
:ident
, $base
:expr
, $prefix
:expr
, $
($x
:pat
=> $conv
:expr
),+) => {
132 impl GenericRadix
for $T
{
133 const BASE
: u8 = $base
;
134 const PREFIX
: &'
static str = $prefix
;
135 fn digit(x
: u8) -> u8 {
138 x
=> panic
!("number not in the range 0..={}: {}", Self::BASE
- 1, x
),
145 radix
! { Binary, 2, "0b", x @ 0 ..= 1 => b'0' + x }
146 radix
! { Octal, 8, "0o", x @ 0 ..= 7 => b'0' + x }
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) }
150 macro_rules
! int_base
{
151 (fmt
::$Trait
:ident
for $T
:ident
as $U
:ident
-> $Radix
:ident
) => {
152 #[stable(feature = "rust1", since = "1.0.0")]
153 impl fmt
::$Trait
for $T
{
154 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
155 $Radix
.fmt_int(*self as $U
, f
)
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 }
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 }
174 integer
! { isize, usize }
176 integer
! { i16, u16 }
177 integer
! { i32, u32 }
178 integer
! { i64, u64 }
179 integer
! { i128, u128 }
181 ($
($T
:ident
)*) => {$
(
182 #[stable(feature = "rust1", since = "1.0.0")]
183 impl fmt
::Debug
for $T
{
185 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
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
)
191 fmt
::Display
::fmt(self, f
)
198 i8 i16 i32 i64 i128
isize
199 u8 u16 u32 u64 u128
usize
202 // 2 digit decimal look up table
203 static DEC_DIGITS_LUT
: &[u8; 200] = b
"0001020304050607080910111213141516171819\
204 2021222324252627282930313233343536373839\
205 4041424344454647484950515253545556575859\
206 6061626364656667686970717273747576777879\
207 8081828384858687888990919293949596979899";
209 macro_rules
! impl_Display
{
210 ($
($t
:ident
),* as $u
:ident via $conv_fn
:ident named $name
:ident
) => {
211 fn $
name(mut n
: $u
, is_nonnegative
: bool
, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
212 // 2^128 is about 3*10^38, so 39 gives an extra byte of space
213 let mut buf
= [MaybeUninit
::<u8>::uninit(); 39];
214 let mut curr
= buf
.len() as isize;
215 let buf_ptr
= MaybeUninit
::slice_as_mut_ptr(&mut buf
);
216 let lut_ptr
= DEC_DIGITS_LUT
.as_ptr();
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.
226 // need at least 16 bits for the 4-characters-at-a-time to work.
227 assert
!(crate::mem
::size_of
::<$u
>() >= 2);
229 // eagerly decode 4 characters at a time
231 let rem
= (n
% 10000) as isize;
234 let d1
= (rem
/ 100) << 1;
235 let d2
= (rem
% 100) << 1;
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`.
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);
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
248 // decode 2 more chars, if > 2 chars
250 let d1
= (n
% 100) << 1;
253 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
), buf_ptr
.offset(curr
), 2);
256 // decode last 1 or 2 chars
259 *buf_ptr
.offset(curr
) = (n
as u8) + b'
0'
;
263 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
), buf_ptr
.offset(curr
), 2);
267 // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
268 // UTF-8 since `DEC_DIGITS_LUT` is
269 let buf_slice
= unsafe {
270 str::from_utf8_unchecked(
271 slice
::from_raw_parts(buf_ptr
.offset(curr
), buf
.len() - curr
as usize))
273 f
.pad_integral(is_nonnegative
, "", buf_slice
)
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
{
284 // convert the negative num to positive by summing 1 to it's 2 complement
285 (!self.$
conv_fn()).wrapping_add(1)
287 $
name(n
, is_nonnegative
, f
)
293 macro_rules
! impl_Exp
{
294 ($
($t
:ident
),* as $u
:ident via $conv_fn
:ident named $name
:ident
) => {
297 is_nonnegative
: bool
,
299 f
: &mut fmt
::Formatter
<'_
>
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 {
309 let (added_precision
, subtracted_precision
) = match f
.precision() {
311 // number of decimal digits minus 1
318 (fmt_prec
.saturating_sub(prec
), prec
.saturating_sub(fmt_prec
))
322 for _
in 1..subtracted_precision
{
326 if subtracted_precision
!= 0 {
330 // round up last digit
335 (n
, exponent
, exponent
, added_precision
)
338 // 39 digits (worst case u128) + . = 40
339 // Since `curr` always decreases by the number of digits copied, this means
341 let mut buf
= [MaybeUninit
::<u8>::uninit(); 40];
342 let mut curr
= buf
.len() as isize; //index for buf
343 let buf_ptr
= MaybeUninit
::slice_as_mut_ptr(&mut buf
);
344 let lut_ptr
= DEC_DIGITS_LUT
.as_ptr();
346 // decode 2 chars at a time
348 let d1
= ((n
% 100) as isize) << 1;
350 // SAFETY: `d1 <= 198`, so we can copy from `lut_ptr[d1..d1 + 2]` since
351 // `DEC_DIGITS_LUT` has a length of 200.
353 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
), buf_ptr
.offset(curr
), 2);
358 // n is <= 99, so at most 2 chars long
359 let mut n
= n
as isize; // possibly reduce 64bit math
360 // decode second-to-last character
363 // SAFETY: Safe since `40 > curr >= 0` (see comment)
365 *buf_ptr
.offset(curr
) = (n
as u8 % 10_u8) + b'
0'
;
370 // add decimal point iff >1 mantissa digit will be printed
371 if exponent
!= trailing_zeros
|| added_precision
!= 0 {
373 // SAFETY: Safe since `40 > curr >= 0`
375 *buf_ptr
.offset(curr
) = b'
.'
;
379 // SAFETY: Safe since `40 > curr >= 0`
380 let buf_slice
= unsafe {
381 // decode last character
383 *buf_ptr
.offset(curr
) = (n
as u8) + b'
0'
;
385 let len
= buf
.len() - curr
as usize;
386 slice
::from_raw_parts(buf_ptr
.offset(curr
), len
)
389 // stores 'e' (or 'E') and the up to 2-digit exponent
390 let mut exp_buf
= [MaybeUninit
::<u8>::uninit(); 3];
391 let exp_ptr
= MaybeUninit
::slice_as_mut_ptr(&mut exp_buf
);
392 // SAFETY: In either case, `exp_buf` is written within bounds and `exp_ptr[..len]`
393 // is contained within `exp_buf` since `len <= 3`.
394 let exp_slice
= unsafe {
395 *exp_ptr
.offset(0) = if upper {b'E'}
else {b'e'}
;
396 let len
= if exponent
< 10 {
397 *exp_ptr
.offset(1) = (exponent
as u8) + b'
0'
;
400 let off
= exponent
<< 1;
401 ptr
::copy_nonoverlapping(lut_ptr
.offset(off
), exp_ptr
.offset(1), 2);
404 slice
::from_raw_parts(exp_ptr
, len
)
408 numfmt
::Part
::Copy(buf_slice
),
409 numfmt
::Part
::Zero(added_precision
),
410 numfmt
::Part
::Copy(exp_slice
)
412 let sign
= if !is_nonnegative
{
414 } else if f
.sign_plus() {
419 let formatted
= numfmt
::Formatted{sign, parts}
;
420 f
.pad_formatted_parts(&formatted
)
424 #[stable(feature = "integer_exp_format", since = "1.42.0")]
425 impl fmt
::LowerExp
for $t
{
426 #[allow(unused_comparisons)]
427 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
428 let is_nonnegative
= *self >= 0;
429 let n
= if is_nonnegative
{
432 // convert the negative num to positive by summing 1 to it's 2 complement
433 (!self.$
conv_fn()).wrapping_add(1)
435 $
name(n
, is_nonnegative
, false, f
)
439 #[stable(feature = "integer_exp_format", since = "1.42.0")]
440 impl fmt
::UpperExp
for $t
{
441 #[allow(unused_comparisons)]
442 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
443 let is_nonnegative
= *self >= 0;
444 let n
= if is_nonnegative
{
447 // convert the negative num to positive by summing 1 to it's 2 complement
448 (!self.$
conv_fn()).wrapping_add(1)
450 $
name(n
, is_nonnegative
, true, f
)
456 // Include wasm32 in here since it doesn't reflect the native pointer size, and
457 // often cares strongly about getting a smaller code size.
458 #[cfg(any(target_pointer_width = "64", target_arch = "wasm32"))]
462 i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
463 as u64 via to_u64 named fmt_u64
466 i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
467 as u64 via to_u64 named exp_u64
471 #[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
474 impl_Display
!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named fmt_u32
);
475 impl_Display
!(i64, u64 as u64 via to_u64 named fmt_u64
);
476 impl_Exp
!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32
);
477 impl_Exp
!(i64, u64 as u64 via to_u64 named exp_u64
);
479 impl_Exp
!(i128
, u128
as u128 via to_u128 named exp_u128
);
481 /// Helper function for writing a u64 into `buf` going from last to first, with `curr`.
482 fn parse_u64_into
<const N
: usize>(mut n
: u64, buf
: &mut [MaybeUninit
<u8>; N
], curr
: &mut isize) {
483 let buf_ptr
= MaybeUninit
::slice_as_mut_ptr(buf
);
484 let lut_ptr
= DEC_DIGITS_LUT
.as_ptr();
488 // Writes at most 19 characters into the buffer. Guaranteed that any ptr into LUT is at most
489 // 198, so will never OOB. There is a check above that there are at least 19 characters
492 if n
>= 1e16
as u64 {
493 let to_parse
= n
% 1e16
as u64;
496 // Some of these are nops but it looks more elegant this way.
497 let d1
= ((to_parse
/ 1e14
as u64) % 100) << 1;
498 let d2
= ((to_parse
/ 1e12
as u64) % 100) << 1;
499 let d3
= ((to_parse
/ 1e10
as u64) % 100) << 1;
500 let d4
= ((to_parse
/ 1e8
as u64) % 100) << 1;
501 let d5
= ((to_parse
/ 1e6
as u64) % 100) << 1;
502 let d6
= ((to_parse
/ 1e4
as u64) % 100) << 1;
503 let d7
= ((to_parse
/ 1e2
as u64) % 100) << 1;
504 let d8
= ((to_parse
/ 1e0
as u64) % 100) << 1;
508 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
as isize), buf_ptr
.offset(*curr
+ 0), 2);
509 ptr
::copy_nonoverlapping(lut_ptr
.offset(d2
as isize), buf_ptr
.offset(*curr
+ 2), 2);
510 ptr
::copy_nonoverlapping(lut_ptr
.offset(d3
as isize), buf_ptr
.offset(*curr
+ 4), 2);
511 ptr
::copy_nonoverlapping(lut_ptr
.offset(d4
as isize), buf_ptr
.offset(*curr
+ 6), 2);
512 ptr
::copy_nonoverlapping(lut_ptr
.offset(d5
as isize), buf_ptr
.offset(*curr
+ 8), 2);
513 ptr
::copy_nonoverlapping(lut_ptr
.offset(d6
as isize), buf_ptr
.offset(*curr
+ 10), 2);
514 ptr
::copy_nonoverlapping(lut_ptr
.offset(d7
as isize), buf_ptr
.offset(*curr
+ 12), 2);
515 ptr
::copy_nonoverlapping(lut_ptr
.offset(d8
as isize), buf_ptr
.offset(*curr
+ 14), 2);
518 let to_parse
= n
% 1e8
as u64;
521 // Some of these are nops but it looks more elegant this way.
522 let d1
= ((to_parse
/ 1e6
as u64) % 100) << 1;
523 let d2
= ((to_parse
/ 1e4
as u64) % 100) << 1;
524 let d3
= ((to_parse
/ 1e2
as u64) % 100) << 1;
525 let d4
= ((to_parse
/ 1e0
as u64) % 100) << 1;
528 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
as isize), buf_ptr
.offset(*curr
+ 0), 2);
529 ptr
::copy_nonoverlapping(lut_ptr
.offset(d2
as isize), buf_ptr
.offset(*curr
+ 2), 2);
530 ptr
::copy_nonoverlapping(lut_ptr
.offset(d3
as isize), buf_ptr
.offset(*curr
+ 4), 2);
531 ptr
::copy_nonoverlapping(lut_ptr
.offset(d4
as isize), buf_ptr
.offset(*curr
+ 6), 2);
533 // `n` < 1e8 < (1 << 32)
534 let mut n
= n
as u32;
536 let to_parse
= n
% 1e4
as u32;
539 let d1
= (to_parse
/ 100) << 1;
540 let d2
= (to_parse
% 100) << 1;
543 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
as isize), buf_ptr
.offset(*curr
+ 0), 2);
544 ptr
::copy_nonoverlapping(lut_ptr
.offset(d2
as isize), buf_ptr
.offset(*curr
+ 2), 2);
547 // `n` < 1e4 < (1 << 16)
548 let mut n
= n
as u16;
550 let d1
= (n
% 100) << 1;
553 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
as isize), buf_ptr
.offset(*curr
), 2);
556 // decode last 1 or 2 chars
559 *buf_ptr
.offset(*curr
) = (n
as u8) + b'
0'
;
563 ptr
::copy_nonoverlapping(lut_ptr
.offset(d1
as isize), buf_ptr
.offset(*curr
), 2);
568 #[stable(feature = "rust1", since = "1.0.0")]
569 impl fmt
::Display
for u128
{
570 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
571 fmt_u128(*self, true, f
)
575 #[stable(feature = "rust1", since = "1.0.0")]
576 impl fmt
::Display
for i128
{
577 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
578 let is_nonnegative
= *self >= 0;
579 let n
= if is_nonnegative
{
582 // convert the negative num to positive by summing 1 to it's 2 complement
583 (!self.to_u128()).wrapping_add(1)
585 fmt_u128(n
, is_nonnegative
, f
)
589 /// Specialized optimization for u128. Instead of taking two items at a time, it splits
590 /// into at most 2 u64s, and then chunks by 10e16, 10e8, 10e4, 10e2, and then 10e1.
591 /// It also has to handle 1 last item, as 10^40 > 2^128 > 10^39, whereas
592 /// 10^20 > 2^64 > 10^19.
593 fn fmt_u128(n
: u128
, is_nonnegative
: bool
, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
594 // 2^128 is about 3*10^38, so 39 gives an extra byte of space
595 let mut buf
= [MaybeUninit
::<u8>::uninit(); 39];
596 let mut curr
= buf
.len() as isize;
598 let (n
, rem
) = udiv_1e19(n
);
599 parse_u64_into(rem
, &mut buf
, &mut curr
);
603 let target
= (buf
.len() - 19) as isize;
604 // SAFETY: Guaranteed that we wrote at most 19 bytes, and there must be space
605 // remaining since it has length 39
608 MaybeUninit
::slice_as_mut_ptr(&mut buf
).offset(target
),
610 (curr
- target
) as usize,
615 let (n
, rem
) = udiv_1e19(n
);
616 parse_u64_into(rem
, &mut buf
, &mut curr
);
617 // Should this following branch be annotated with unlikely?
619 let target
= (buf
.len() - 38) as isize;
620 // The raw `buf_ptr` pointer is only valid until `buf` is used the next time,
621 // buf `buf` is not used in this scope so we are good.
622 let buf_ptr
= MaybeUninit
::slice_as_mut_ptr(&mut buf
);
623 // SAFETY: At this point we wrote at most 38 bytes, pad up to that point,
624 // There can only be at most 1 digit remaining.
626 ptr
::write_bytes(buf_ptr
.offset(target
), b'
0'
, (curr
- target
) as usize);
628 *buf_ptr
.offset(curr
) = (n
as u8) + b'
0'
;
633 // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
634 // UTF-8 since `DEC_DIGITS_LUT` is
635 let buf_slice
= unsafe {
636 str::from_utf8_unchecked(slice
::from_raw_parts(
637 MaybeUninit
::slice_as_mut_ptr(&mut buf
).offset(curr
),
638 buf
.len() - curr
as usize,
641 f
.pad_integral(is_nonnegative
, "", buf_slice
)
644 /// Partition of `n` into n > 1e19 and rem <= 1e19
646 /// Integer division algorithm is based on the following paper:
648 /// T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
649 /// in Proc. of the SIGPLAN94 Conference on Programming Language Design and
650 /// Implementation, 1994, pp. 61–72
652 fn udiv_1e19(n
: u128
) -> (u128
, u64) {
653 const DIV
: u64 = 1e19
as u64;
654 const FACTOR
: u128
= 156927543384667019095894735580191660403;
656 let quot
= if n
< 1 << 83 {
657 ((n
>> 19) as u64 / (DIV
>> 19)) as u128
659 u128_mulhi(n
, FACTOR
) >> 62
662 let rem
= (n
- quot
* DIV
as u128
) as u64;
666 /// Multiply unsigned 128 bit integers, return upper 128 bits of the result
668 fn u128_mulhi(x
: u128
, y
: u128
) -> u128
{
670 let x_hi
= (x
>> 64) as u64;
672 let y_hi
= (y
>> 64) as u64;
674 // handle possibility of overflow
675 let carry
= (x_lo
as u128
* y_lo
as u128
) >> 64;
676 let m
= x_lo
as u128
* y_hi
as u128
+ carry
;
680 let high2
= (x_hi
as u128
* y_lo
as u128
+ m_lo
as u128
) >> 64;
682 x_hi
as u128
* y_hi
as u128
+ high1
+ high2