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(feature = "small" ))] |
23 | pub use crate::d2s_full_table::*; |
24 | use crate::d2s_intrinsics::*; |
25 | #[cfg (feature = "small" )] |
26 | pub use crate::d2s_small_table::*; |
27 | use core::mem::MaybeUninit; |
28 | |
29 | pub const DOUBLE_MANTISSA_BITS: u32 = 52; |
30 | pub const DOUBLE_EXPONENT_BITS: u32 = 11; |
31 | pub const DOUBLE_BIAS: i32 = 1023; |
32 | pub const DOUBLE_POW5_INV_BITCOUNT: i32 = 125; |
33 | pub const DOUBLE_POW5_BITCOUNT: i32 = 125; |
34 | |
35 | #[cfg_attr (feature = "no-panic" , inline)] |
36 | pub fn decimal_length17(v: u64) -> u32 { |
37 | // This is slightly faster than a loop. |
38 | // The average output length is 16.38 digits, so we check high-to-low. |
39 | // Function precondition: v is not an 18, 19, or 20-digit number. |
40 | // (17 digits are sufficient for round-tripping.) |
41 | debug_assert!(v < 100000000000000000); |
42 | |
43 | if v >= 10000000000000000 { |
44 | 17 |
45 | } else if v >= 1000000000000000 { |
46 | 16 |
47 | } else if v >= 100000000000000 { |
48 | 15 |
49 | } else if v >= 10000000000000 { |
50 | 14 |
51 | } else if v >= 1000000000000 { |
52 | 13 |
53 | } else if v >= 100000000000 { |
54 | 12 |
55 | } else if v >= 10000000000 { |
56 | 11 |
57 | } else if v >= 1000000000 { |
58 | 10 |
59 | } else if v >= 100000000 { |
60 | 9 |
61 | } else if v >= 10000000 { |
62 | 8 |
63 | } else if v >= 1000000 { |
64 | 7 |
65 | } else if v >= 100000 { |
66 | 6 |
67 | } else if v >= 10000 { |
68 | 5 |
69 | } else if v >= 1000 { |
70 | 4 |
71 | } else if v >= 100 { |
72 | 3 |
73 | } else if v >= 10 { |
74 | 2 |
75 | } else { |
76 | 1 |
77 | } |
78 | } |
79 | |
80 | // A floating decimal representing m * 10^e. |
81 | pub struct FloatingDecimal64 { |
82 | pub mantissa: u64, |
83 | // Decimal exponent's range is -324 to 308 |
84 | // inclusive, and can fit in i16 if needed. |
85 | pub exponent: i32, |
86 | } |
87 | |
88 | #[cfg_attr (feature = "no-panic" , inline)] |
89 | pub fn d2d(ieee_mantissa: u64, ieee_exponent: u32) -> FloatingDecimal64 { |
90 | let (e2, m2) = if ieee_exponent == 0 { |
91 | ( |
92 | // We subtract 2 so that the bounds computation has 2 additional bits. |
93 | 1 - DOUBLE_BIAS - DOUBLE_MANTISSA_BITS as i32 - 2, |
94 | ieee_mantissa, |
95 | ) |
96 | } else { |
97 | ( |
98 | ieee_exponent as i32 - DOUBLE_BIAS - DOUBLE_MANTISSA_BITS as i32 - 2, |
99 | (1u64 << DOUBLE_MANTISSA_BITS) | ieee_mantissa, |
100 | ) |
101 | }; |
102 | let even = (m2 & 1) == 0; |
103 | let accept_bounds = even; |
104 | |
105 | // Step 2: Determine the interval of valid decimal representations. |
106 | let mv = 4 * m2; |
107 | // Implicit bool -> int conversion. True is 1, false is 0. |
108 | let mm_shift = (ieee_mantissa != 0 || ieee_exponent <= 1) as u32; |
109 | // We would compute mp and mm like this: |
110 | // uint64_t mp = 4 * m2 + 2; |
111 | // uint64_t mm = mv - 1 - mm_shift; |
112 | |
113 | // Step 3: Convert to a decimal power base using 128-bit arithmetic. |
114 | let mut vr: u64; |
115 | let mut vp: u64; |
116 | let mut vm: u64; |
117 | let mut vp_uninit: MaybeUninit<u64> = MaybeUninit::uninit(); |
118 | let mut vm_uninit: MaybeUninit<u64> = MaybeUninit::uninit(); |
119 | let e10: i32; |
120 | let mut vm_is_trailing_zeros = false; |
121 | let mut vr_is_trailing_zeros = false; |
122 | if e2 >= 0 { |
123 | // I tried special-casing q == 0, but there was no effect on performance. |
124 | // This expression is slightly faster than max(0, log10_pow2(e2) - 1). |
125 | let q = log10_pow2(e2) - (e2 > 3) as u32; |
126 | e10 = q as i32; |
127 | let k = DOUBLE_POW5_INV_BITCOUNT + pow5bits(q as i32) - 1; |
128 | let i = -e2 + q as i32 + k; |
129 | vr = unsafe { |
130 | mul_shift_all_64( |
131 | m2, |
132 | #[cfg (feature = "small" )] |
133 | &compute_inv_pow5(q), |
134 | #[cfg (not(feature = "small" ))] |
135 | { |
136 | debug_assert!(q < DOUBLE_POW5_INV_SPLIT.len() as u32); |
137 | DOUBLE_POW5_INV_SPLIT.get_unchecked(q as usize) |
138 | }, |
139 | i as u32, |
140 | vp_uninit.as_mut_ptr(), |
141 | vm_uninit.as_mut_ptr(), |
142 | mm_shift, |
143 | ) |
144 | }; |
145 | vp = unsafe { vp_uninit.assume_init() }; |
146 | vm = unsafe { vm_uninit.assume_init() }; |
147 | if q <= 21 { |
148 | // This should use q <= 22, but I think 21 is also safe. Smaller values |
149 | // may still be safe, but it's more difficult to reason about them. |
150 | // Only one of mp, mv, and mm can be a multiple of 5, if any. |
151 | let mv_mod5 = (mv as u32).wrapping_sub(5u32.wrapping_mul(div5(mv) as u32)); |
152 | if mv_mod5 == 0 { |
153 | vr_is_trailing_zeros = multiple_of_power_of_5(mv, q); |
154 | } else if accept_bounds { |
155 | // Same as min(e2 + (~mm & 1), pow5_factor(mm)) >= q |
156 | // <=> e2 + (~mm & 1) >= q && pow5_factor(mm) >= q |
157 | // <=> true && pow5_factor(mm) >= q, since e2 >= q. |
158 | vm_is_trailing_zeros = multiple_of_power_of_5(mv - 1 - mm_shift as u64, q); |
159 | } else { |
160 | // Same as min(e2 + 1, pow5_factor(mp)) >= q. |
161 | vp -= multiple_of_power_of_5(mv + 2, q) as u64; |
162 | } |
163 | } |
164 | } else { |
165 | // This expression is slightly faster than max(0, log10_pow5(-e2) - 1). |
166 | let q = log10_pow5(-e2) - (-e2 > 1) as u32; |
167 | e10 = q as i32 + e2; |
168 | let i = -e2 - q as i32; |
169 | let k = pow5bits(i) - DOUBLE_POW5_BITCOUNT; |
170 | let j = q as i32 - k; |
171 | vr = unsafe { |
172 | mul_shift_all_64( |
173 | m2, |
174 | #[cfg (feature = "small" )] |
175 | &compute_pow5(i as u32), |
176 | #[cfg (not(feature = "small" ))] |
177 | { |
178 | debug_assert!(i < DOUBLE_POW5_SPLIT.len() as i32); |
179 | DOUBLE_POW5_SPLIT.get_unchecked(i as usize) |
180 | }, |
181 | j as u32, |
182 | vp_uninit.as_mut_ptr(), |
183 | vm_uninit.as_mut_ptr(), |
184 | mm_shift, |
185 | ) |
186 | }; |
187 | vp = unsafe { vp_uninit.assume_init() }; |
188 | vm = unsafe { vm_uninit.assume_init() }; |
189 | if q <= 1 { |
190 | // {vr,vp,vm} is trailing zeros if {mv,mp,mm} has at least q trailing 0 bits. |
191 | // mv = 4 * m2, so it always has at least two trailing 0 bits. |
192 | vr_is_trailing_zeros = true; |
193 | if accept_bounds { |
194 | // mm = mv - 1 - mm_shift, so it has 1 trailing 0 bit iff mm_shift == 1. |
195 | vm_is_trailing_zeros = mm_shift == 1; |
196 | } else { |
197 | // mp = mv + 2, so it always has at least one trailing 0 bit. |
198 | vp -= 1; |
199 | } |
200 | } else if q < 63 { |
201 | // TODO(ulfjack): Use a tighter bound here. |
202 | // We want to know if the full product has at least q trailing zeros. |
203 | // We need to compute min(p2(mv), p5(mv) - e2) >= q |
204 | // <=> p2(mv) >= q && p5(mv) - e2 >= q |
205 | // <=> p2(mv) >= q (because -e2 >= q) |
206 | vr_is_trailing_zeros = multiple_of_power_of_2(mv, q); |
207 | } |
208 | } |
209 | |
210 | // Step 4: Find the shortest decimal representation in the interval of valid representations. |
211 | let mut removed = 0i32; |
212 | let mut last_removed_digit = 0u8; |
213 | // On average, we remove ~2 digits. |
214 | let output = if vm_is_trailing_zeros || vr_is_trailing_zeros { |
215 | // General case, which happens rarely (~0.7%). |
216 | loop { |
217 | let vp_div10 = div10(vp); |
218 | let vm_div10 = div10(vm); |
219 | if vp_div10 <= vm_div10 { |
220 | break; |
221 | } |
222 | let vm_mod10 = (vm as u32).wrapping_sub(10u32.wrapping_mul(vm_div10 as u32)); |
223 | let vr_div10 = div10(vr); |
224 | let vr_mod10 = (vr as u32).wrapping_sub(10u32.wrapping_mul(vr_div10 as u32)); |
225 | vm_is_trailing_zeros &= vm_mod10 == 0; |
226 | vr_is_trailing_zeros &= last_removed_digit == 0; |
227 | last_removed_digit = vr_mod10 as u8; |
228 | vr = vr_div10; |
229 | vp = vp_div10; |
230 | vm = vm_div10; |
231 | removed += 1; |
232 | } |
233 | if vm_is_trailing_zeros { |
234 | loop { |
235 | let vm_div10 = div10(vm); |
236 | let vm_mod10 = (vm as u32).wrapping_sub(10u32.wrapping_mul(vm_div10 as u32)); |
237 | if vm_mod10 != 0 { |
238 | break; |
239 | } |
240 | let vp_div10 = div10(vp); |
241 | let vr_div10 = div10(vr); |
242 | let vr_mod10 = (vr as u32).wrapping_sub(10u32.wrapping_mul(vr_div10 as u32)); |
243 | vr_is_trailing_zeros &= last_removed_digit == 0; |
244 | last_removed_digit = vr_mod10 as u8; |
245 | vr = vr_div10; |
246 | vp = vp_div10; |
247 | vm = vm_div10; |
248 | removed += 1; |
249 | } |
250 | } |
251 | if vr_is_trailing_zeros && last_removed_digit == 5 && vr % 2 == 0 { |
252 | // Round even if the exact number is .....50..0. |
253 | last_removed_digit = 4; |
254 | } |
255 | // We need to take vr + 1 if vr is outside bounds or we need to round up. |
256 | vr + ((vr == vm && (!accept_bounds || !vm_is_trailing_zeros)) || last_removed_digit >= 5) |
257 | as u64 |
258 | } else { |
259 | // Specialized for the common case (~99.3%). Percentages below are relative to this. |
260 | let mut round_up = false; |
261 | let vp_div100 = div100(vp); |
262 | let vm_div100 = div100(vm); |
263 | // Optimization: remove two digits at a time (~86.2%). |
264 | if vp_div100 > vm_div100 { |
265 | let vr_div100 = div100(vr); |
266 | let vr_mod100 = (vr as u32).wrapping_sub(100u32.wrapping_mul(vr_div100 as u32)); |
267 | round_up = vr_mod100 >= 50; |
268 | vr = vr_div100; |
269 | vp = vp_div100; |
270 | vm = vm_div100; |
271 | removed += 2; |
272 | } |
273 | // Loop iterations below (approximately), without optimization above: |
274 | // 0: 0.03%, 1: 13.8%, 2: 70.6%, 3: 14.0%, 4: 1.40%, 5: 0.14%, 6+: 0.02% |
275 | // Loop iterations below (approximately), with optimization above: |
276 | // 0: 70.6%, 1: 27.8%, 2: 1.40%, 3: 0.14%, 4+: 0.02% |
277 | loop { |
278 | let vp_div10 = div10(vp); |
279 | let vm_div10 = div10(vm); |
280 | if vp_div10 <= vm_div10 { |
281 | break; |
282 | } |
283 | let vr_div10 = div10(vr); |
284 | let vr_mod10 = (vr as u32).wrapping_sub(10u32.wrapping_mul(vr_div10 as u32)); |
285 | round_up = vr_mod10 >= 5; |
286 | vr = vr_div10; |
287 | vp = vp_div10; |
288 | vm = vm_div10; |
289 | removed += 1; |
290 | } |
291 | // We need to take vr + 1 if vr is outside bounds or we need to round up. |
292 | vr + (vr == vm || round_up) as u64 |
293 | }; |
294 | let exp = e10 + removed; |
295 | |
296 | FloatingDecimal64 { |
297 | exponent: exp, |
298 | mantissa: output, |
299 | } |
300 | } |
301 | |