| 1 |
// Translated from C to Rust. The original C code can be found at |
| 2 |
// https://github.com/ulfjack/ryu and carries the following license: |
| 3 |
// |
| 4 |
// Copyright 2018 Ulf Adams |
| 5 |
// |
| 6 |
// The contents of this file may be used under the terms of the Apache License, |
| 7 |
// Version 2.0. |
| 8 |
// |
| 9 |
// (See accompanying file LICENSE-Apache or copy at |
| 10 |
// http://www.apache.org/licenses/LICENSE-2.0) |
| 11 |
// |
| 12 |
// Alternatively, the contents of this file may be used under the terms of |
| 13 |
// the Boost Software License, Version 1.0. |
| 14 |
// (See accompanying file LICENSE-Boost or copy at |
| 15 |
// https://www.boost.org/LICENSE_1_0.txt) |
| 16 |
// |
| 17 |
// Unless required by applicable law or agreed to in writing, this software |
| 18 |
// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 19 |
// KIND, either express or implied. |
| 20 |
|
| 21 |
use crate::common::pow5bits; |
| 22 |
|
| 23 |
pub static DOUBLE_POW5_INV_SPLIT2: [(u64, u64); 15] = [ |
| 24 |
(1, 2305843009213693952), |
| 25 |
(5955668970331000884, 1784059615882449851), |
| 26 |
(8982663654677661702, 1380349269358112757), |
| 27 |
(7286864317269821294, 2135987035920910082), |
| 28 |
(7005857020398200553, 1652639921975621497), |
| 29 |
(17965325103354776697, 1278668206209430417), |
| 30 |
(8928596168509315048, 1978643211784836272), |
| 31 |
(10075671573058298858, 1530901034580419511), |
| 32 |
(597001226353042382, 1184477304306571148), |
| 33 |
(1527430471115325346, 1832889850782397517), |
| 34 |
(12533209867169019542, 1418129833677084982), |
| 35 |
(5577825024675947042, 2194449627517475473), |
| 36 |
(11006974540203867551, 1697873161311732311), |
| 37 |
(10313493231639821582, 1313665730009899186), |
| 38 |
(12701016819766672773, 2032799256770390445), |
| 39 |
]; |
| 40 |
|
| 41 |
pub static POW5_INV_OFFSETS: [u32; 19] = [ |
| 42 |
0x54544554, 0x04055545, 0x10041000, 0x00400414, 0x40010000, 0x41155555, 0x00000454, 0x00010044, |
| 43 |
0x40000000, 0x44000041, 0x50454450, 0x55550054, 0x51655554, 0x40004000, 0x01000001, 0x00010500, |
| 44 |
0x51515411, 0x05555554, 0x00000000, |
| 45 |
]; |
| 46 |
|
| 47 |
pub static DOUBLE_POW5_SPLIT2: [(u64, u64); 13] = [ |
| 48 |
(0, 1152921504606846976), |
| 49 |
(0, 1490116119384765625), |
| 50 |
(1032610780636961552, 1925929944387235853), |
| 51 |
(7910200175544436838, 1244603055572228341), |
| 52 |
(16941905809032713930, 1608611746708759036), |
| 53 |
(13024893955298202172, 2079081953128979843), |
| 54 |
(6607496772837067824, 1343575221513417750), |
| 55 |
(17332926989895652603, 1736530273035216783), |
| 56 |
(13037379183483547984, 2244412773384604712), |
| 57 |
(1605989338741628675, 1450417759929778918), |
| 58 |
(9630225068416591280, 1874621017369538693), |
| 59 |
(665883850346957067, 1211445438634777304), |
| 60 |
(14931890668723713708, 1565756531257009982), |
| 61 |
]; |
| 62 |
|
| 63 |
pub static POW5_OFFSETS: [u32; 21] = [ |
| 64 |
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x40000000, 0x59695995, 0x55545555, 0x56555515, |
| 65 |
0x41150504, 0x40555410, 0x44555145, 0x44504540, 0x45555550, 0x40004000, 0x96440440, 0x55565565, |
| 66 |
0x54454045, 0x40154151, 0x55559155, 0x51405555, 0x00000105, |
| 67 |
]; |
| 68 |
|
| 69 |
pub static DOUBLE_POW5_TABLE: [u64; 26] = [ |
| 70 |
1, |
| 71 |
5, |
| 72 |
25, |
| 73 |
125, |
| 74 |
625, |
| 75 |
3125, |
| 76 |
15625, |
| 77 |
78125, |
| 78 |
390625, |
| 79 |
1953125, |
| 80 |
9765625, |
| 81 |
48828125, |
| 82 |
244140625, |
| 83 |
1220703125, |
| 84 |
6103515625, |
| 85 |
30517578125, |
| 86 |
152587890625, |
| 87 |
762939453125, |
| 88 |
3814697265625, |
| 89 |
19073486328125, |
| 90 |
95367431640625, |
| 91 |
476837158203125, |
| 92 |
2384185791015625, |
| 93 |
11920928955078125, |
| 94 |
59604644775390625, |
| 95 |
298023223876953125, |
| 96 |
]; |
| 97 |
|
| 98 |
// Computes 5^i in the form required by Ryū. |
| 99 |
#[cfg_attr(feature = "no-panic", inline)] |
| 100 |
pub unsafe fn compute_pow5(i: u32) -> (u64, u64) { |
| 101 |
let base = i / DOUBLE_POW5_TABLE.len() as u32; |
| 102 |
let base2 = base * DOUBLE_POW5_TABLE.len() as u32; |
| 103 |
let offset = i - base2; |
| 104 |
debug_assert!(base < DOUBLE_POW5_SPLIT2.len() as u32); |
| 105 |
let mul = *DOUBLE_POW5_SPLIT2.get_unchecked(base as usize); |
| 106 |
if offset == 0 { |
| 107 |
return mul; |
| 108 |
} |
| 109 |
debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32); |
| 110 |
let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize); |
| 111 |
let b0 = m as u128 * mul.0 as u128; |
| 112 |
let b2 = m as u128 * mul.1 as u128; |
| 113 |
let delta = pow5bits(i as i32) - pow5bits(base2 as i32); |
| 114 |
debug_assert!(i / 16 < POW5_OFFSETS.len() as u32); |
| 115 |
let shifted_sum = (b0 >> delta) |
| 116 |
+ (b2 << (64 - delta)) |
| 117 |
+ ((*POW5_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u128; |
| 118 |
(shifted_sum as u64, (shifted_sum >> 64) as u64) |
| 119 |
} |
| 120 |
|
| 121 |
// Computes 5^-i in the form required by Ryū. |
| 122 |
#[cfg_attr(feature = "no-panic", inline)] |
| 123 |
pub unsafe fn compute_inv_pow5(i: u32) -> (u64, u64) { |
| 124 |
let base = (i + DOUBLE_POW5_TABLE.len() as u32 - 1) / DOUBLE_POW5_TABLE.len() as u32; |
| 125 |
let base2 = base * DOUBLE_POW5_TABLE.len() as u32; |
| 126 |
let offset = base2 - i; |
| 127 |
debug_assert!(base < DOUBLE_POW5_INV_SPLIT2.len() as u32); |
| 128 |
let mul = *DOUBLE_POW5_INV_SPLIT2.get_unchecked(base as usize); // 1/5^base2 |
| 129 |
if offset == 0 { |
| 130 |
return mul; |
| 131 |
} |
| 132 |
debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32); |
| 133 |
let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize); // 5^offset |
| 134 |
let b0 = m as u128 * (mul.0 - 1) as u128; |
| 135 |
let b2 = m as u128 * mul.1 as u128; // 1/5^base2 * 5^offset = 1/5^(base2-offset) = 1/5^i |
| 136 |
let delta = pow5bits(base2 as i32) - pow5bits(i as i32); |
| 137 |
debug_assert!(base < POW5_INV_OFFSETS.len() as u32); |
| 138 |
let shifted_sum = ((b0 >> delta) + (b2 << (64 - delta))) |
| 139 |
+ 1 |
| 140 |
+ ((*POW5_INV_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u128; |
| 141 |
(shifted_sum as u64, (shifted_sum >> 64) as u64) |
| 142 |
} |