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
21use crate::common::*;
22#[cfg(not(feature = "small"))]
23pub use crate::d2s_full_table::*;
24use crate::d2s_intrinsics::*;
25#[cfg(feature = "small")]
26pub use crate::d2s_small_table::*;
27use core::mem::MaybeUninit;
28
29pub const DOUBLE_MANTISSA_BITS: u32 = 52;
30pub const DOUBLE_EXPONENT_BITS: u32 = 11;
31pub const DOUBLE_BIAS: i32 = 1023;
32pub const DOUBLE_POW5_INV_BITCOUNT: i32 = 125;
33pub const DOUBLE_POW5_BITCOUNT: i32 = 125;
34
35#[cfg_attr(feature = "no-panic", inline)]
36pub 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.
81pub 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)]
89pub 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