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::*;
22 #[cfg(not(integer128))]
23 use crate::d2s_intrinsics::*;
24 
25 pub static DOUBLE_POW5_INV_SPLIT2: [(u64, u64); 13] = [
26     (1, 2305843009213693952),
27     (5955668970331000884, 1784059615882449851),
28     (8982663654677661702, 1380349269358112757),
29     (7286864317269821294, 2135987035920910082),
30     (7005857020398200553, 1652639921975621497),
31     (17965325103354776697, 1278668206209430417),
32     (8928596168509315048, 1978643211784836272),
33     (10075671573058298858, 1530901034580419511),
34     (597001226353042382, 1184477304306571148),
35     (1527430471115325346, 1832889850782397517),
36     (12533209867169019542, 1418129833677084982),
37     (5577825024675947042, 2194449627517475473),
38     (11006974540203867551, 1697873161311732311),
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(integer128)]
100 #[cfg_attr(feature = "no-panic", inline)]
compute_pow5(i: u32) -> (u64, u64)101 pub unsafe fn compute_pow5(i: u32) -> (u64, u64) {
102     let base = i / DOUBLE_POW5_TABLE.len() as u32;
103     let base2 = base * DOUBLE_POW5_TABLE.len() as u32;
104     let offset = i - base2;
105     debug_assert!(base < DOUBLE_POW5_SPLIT2.len() as u32);
106     let mul = *DOUBLE_POW5_SPLIT2.get_unchecked(base as usize);
107     if offset == 0 {
108         return mul;
109     }
110     debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32);
111     let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize);
112     let b0 = m as u128 * mul.0 as u128;
113     let b2 = m as u128 * mul.1 as u128;
114     let delta = pow5bits(i as i32) - pow5bits(base2 as i32);
115     debug_assert!(base < POW5_OFFSETS.len() as u32);
116     let shifted_sum = (b0 >> delta)
117         + (b2 << (64 - delta))
118         + ((*POW5_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u128;
119     (shifted_sum as u64, (shifted_sum >> 64) as u64)
120 }
121 
122 // Computes 5^-i in the form required by Ryū.
123 #[cfg(integer128)]
124 #[cfg_attr(feature = "no-panic", inline)]
compute_inv_pow5(i: u32) -> (u64, u64)125 pub unsafe fn compute_inv_pow5(i: u32) -> (u64, u64) {
126     let base = (i + DOUBLE_POW5_TABLE.len() as u32 - 1) / DOUBLE_POW5_TABLE.len() as u32;
127     let base2 = base * DOUBLE_POW5_TABLE.len() as u32;
128     let offset = base2 - i;
129     debug_assert!(base < DOUBLE_POW5_INV_SPLIT2.len() as u32);
130     let mul = *DOUBLE_POW5_INV_SPLIT2.get_unchecked(base as usize); // 1/5^base2
131     if offset == 0 {
132         return mul;
133     }
134     debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32);
135     let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize); // 5^offset
136     let b0 = m as u128 * (mul.0 - 1) as u128;
137     let b2 = m as u128 * mul.1 as u128; // 1/5^base2 * 5^offset = 1/5^(base2-offset) = 1/5^i
138     let delta = pow5bits(base2 as i32) - pow5bits(i as i32);
139     debug_assert!(base < POW5_INV_OFFSETS.len() as u32);
140     let shifted_sum = ((b0 >> delta) + (b2 << (64 - delta)))
141         + 1
142         + ((*POW5_INV_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u128;
143     (shifted_sum as u64, (shifted_sum >> 64) as u64)
144 }
145 
146 // Computes 5^i in the form required by Ryū, and stores it in the given pointer.
147 #[cfg(not(integer128))]
148 #[cfg_attr(feature = "no-panic", inline)]
compute_pow5(i: u32) -> (u64, u64)149 pub unsafe fn compute_pow5(i: u32) -> (u64, u64) {
150     let base = i / DOUBLE_POW5_TABLE.len() as u32;
151     let base2 = base * DOUBLE_POW5_TABLE.len() as u32;
152     let offset = i - base2;
153     debug_assert!(base < DOUBLE_POW5_SPLIT2.len() as u32);
154     let mul = *DOUBLE_POW5_SPLIT2.get_unchecked(base as usize);
155     if offset == 0 {
156         return mul;
157     }
158     debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32);
159     let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize);
160     let (low1, mut high1) = umul128(m, mul.1);
161     let (low0, high0) = umul128(m, mul.0);
162     let sum = high0 + low1;
163     if sum < high0 {
164         high1 += 1; // overflow into high1
165     }
166     // high1 | sum | low0
167     let delta = pow5bits(i as i32) - pow5bits(base2 as i32);
168     debug_assert!(base < POW5_OFFSETS.len() as u32);
169     (
170         shiftright128(low0, sum, delta as u32)
171             + ((*POW5_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u64,
172         shiftright128(sum, high1, delta as u32),
173     )
174 }
175 
176 // Computes 5^-i in the form required by Ryū, and stores it in the given pointer.
177 #[cfg(not(integer128))]
178 #[cfg_attr(feature = "no-panic", inline)]
compute_inv_pow5(i: u32) -> (u64, u64)179 pub unsafe fn compute_inv_pow5(i: u32) -> (u64, u64) {
180     let base = (i + DOUBLE_POW5_TABLE.len() as u32 - 1) / DOUBLE_POW5_TABLE.len() as u32;
181     let base2 = base * DOUBLE_POW5_TABLE.len() as u32;
182     let offset = base2 - i;
183     debug_assert!(base < DOUBLE_POW5_INV_SPLIT2.len() as u32);
184     let mul = *DOUBLE_POW5_INV_SPLIT2.get_unchecked(base as usize); // 1/5^base2
185     if offset == 0 {
186         return mul;
187     }
188     debug_assert!(offset < DOUBLE_POW5_TABLE.len() as u32);
189     let m = *DOUBLE_POW5_TABLE.get_unchecked(offset as usize);
190     let (low1, mut high1) = umul128(m, mul.1);
191     let (low0, high0) = umul128(m, mul.0 - 1);
192     let sum = high0 + low1;
193     if sum < high0 {
194         high1 += 1; // overflow into high1
195     }
196     // high1 | sum | low0
197     let delta = pow5bits(base2 as i32) - pow5bits(i as i32);
198     debug_assert!(base < POW5_INV_OFFSETS.len() as u32);
199     (
200         shiftright128(low0, sum, delta as u32)
201             + 1
202             + ((*POW5_INV_OFFSETS.get_unchecked((i / 16) as usize) >> ((i % 16) << 1)) & 3) as u64,
203         shiftright128(sum, high1, delta as u32),
204     )
205 }
206