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