lexical_write_float/
radix.rs

1//! Adaptation of the V8 ftoa algorithm with a custom radix.
2//!
3//! This algorithm is adapted from the V8 codebase,
4//! and may be found [here](https://github.com/v8/v8).
5//!
6//! # Unsupported Features
7//!
8//! This does not support a few features from the format packed struct,
9//! most notably, it will never write numbers in scientific notation.
10//! Scientific notation must be disabled.
11
12#![cfg(feature = "radix")]
13#![doc(hidden)]
14
15use lexical_util::algorithm::{copy_to_dst, ltrim_char_count, rtrim_char_count};
16use lexical_util::constants::{FormattedSize, BUFFER_SIZE};
17use lexical_util::digit::{char_to_digit_const, digit_to_char_const};
18use lexical_util::format::NumberFormat;
19use lexical_util::num::Float;
20use lexical_write_integer::write::WriteInteger;
21
22use crate::options::{Options, RoundMode};
23use crate::shared;
24
25// ALGORITHM
26// ---------
27
28/// Naive float-to-string algorithm for generic radixes.
29///
30/// This assumes the float is:
31///     1). Non-special (NaN or Infinite).
32///     2). Non-negative.
33///
34/// # Panics
35///
36/// Panics if exponent notation is used.
37#[allow(clippy::collapsible_if)] // reason="conditions are different logical concepts"
38pub fn write_float<F: Float, const FORMAT: u128>(
39    float: F,
40    bytes: &mut [u8],
41    options: &Options,
42) -> usize
43where
44    <F as Float>::Unsigned: WriteInteger + FormattedSize,
45{
46    // PRECONDITIONS
47
48    // Assert no special cases remain, no negative numbers, and a valid format.
49    let format = NumberFormat::<{ FORMAT }> {};
50    assert!(format.is_valid());
51    debug_assert!(!float.is_special());
52    debug_assert!(float >= F::ZERO);
53    debug_assert!(F::BITS <= 64);
54
55    // Validate our options: we don't support different exponent bases here.
56    debug_assert!(format.mantissa_radix() == format.exponent_base());
57
58    // Temporary buffer for the result. We start with the decimal point in the
59    // middle and write to the left for the integer part and to the right for the
60    // fractional part. 1024 characters for the exponent and 52 for the mantissa
61    // either way, with additional space for sign, decimal point and string
62    // termination should be sufficient.
63    const SIZE: usize = 2200;
64    let mut buffer = [0u8; SIZE];
65    let initial_cursor: usize = SIZE / 2;
66    let mut integer_cursor = initial_cursor;
67    let mut fraction_cursor = initial_cursor;
68    let base = F::as_cast(format.radix());
69
70    // Split the float into an integer part and a fractional part.
71    let mut integer = float.floor();
72    let mut fraction = float - integer;
73
74    // We only compute fractional digits up to the input double's precision.
75    // This fails if the value is at f64::MAX. IF we take the next positive,
76    // we'll get literal infinite. We don't care about NaN comparisons, since
77    // the float **must** be finite, so do this.
78    let mut delta = if float.to_bits() == F::MAX.to_bits() {
79        F::as_cast(0.5) * (float - float.prev_positive())
80    } else {
81        F::as_cast(0.5) * (float.next_positive() - float)
82    };
83    delta = F::ZERO.next_positive().max_finite(delta);
84    debug_assert!(delta > F::ZERO);
85
86    // Write our fraction digits.
87    // Won't panic since we have 1100 digits, which is enough for any float f64 or
88    // smaller.
89    if fraction > delta {
90        loop {
91            // Shift up by one digit.
92            fraction *= base;
93            delta *= base;
94            // Write digit.
95            let digit = fraction.as_u32();
96            let c = digit_to_char_const(digit, format.radix());
97            buffer[fraction_cursor] = c;
98            fraction_cursor += 1;
99            // Calculate remainder.
100            fraction -= F::as_cast(digit);
101            // Round to even.
102            if fraction > F::as_cast(0.5) || (fraction == F::as_cast(0.5) && (digit & 1) != 0) {
103                if fraction + delta > F::ONE {
104                    // We need to back trace already written digits in case of carry-over.
105                    loop {
106                        fraction_cursor -= 1;
107                        if fraction_cursor == initial_cursor - 1 {
108                            // Carry over to the integer part.
109                            integer += F::ONE;
110                            break;
111                        }
112                        // Reconstruct digit.
113                        let c = buffer[fraction_cursor];
114                        if let Some(digit) = char_to_digit_const(c, format.radix()) {
115                            let idx = digit + 1;
116                            let c = digit_to_char_const(idx, format.radix());
117                            buffer[fraction_cursor] = c;
118                            fraction_cursor += 1;
119                            break;
120                        }
121                    }
122                    break;
123                }
124            }
125
126            if delta >= fraction {
127                break;
128            }
129        }
130    }
131
132    // Compute integer digits. Fill unrepresented digits with zero.
133    // Won't panic we have 1100 digits, which is enough for any float f64 or
134    // smaller. We do this first, so we can do extended precision control later.
135    while (integer / base).exponent() > 0 {
136        integer /= base;
137        integer_cursor -= 1;
138        buffer[integer_cursor] = b'0';
139    }
140
141    loop {
142        let remainder = integer % base;
143        integer_cursor -= 1;
144        let idx = remainder.as_u32();
145        let c = digit_to_char_const(idx, format.radix());
146        buffer[integer_cursor] = c;
147        integer = (integer - remainder) / base;
148
149        if integer <= F::ZERO {
150            break;
151        }
152    }
153
154    // Get our exponent.
155    // We can't use a naive float log algorithm, since rounding issues can
156    // cause major issues. For example, `12157665459056928801f64` is `3^40`,
157    // but glibc gives us `(f.ln() / 3.0.ln())` of `39.999`, while Android, and
158    // MUSL libm, and openlibm give us `40.0`, the correct answer. This of
159    // course means we have off-by-1 errors, so the correct way is to trim
160    // leading zeros, and then calculate the exponent as the offset.
161    let digits = &buffer[integer_cursor..fraction_cursor];
162    let zero_count = ltrim_char_count(digits, b'0');
163    let sci_exp: i32 = initial_cursor as i32 - integer_cursor as i32 - zero_count as i32 - 1;
164    write_float!(
165        float,
166        FORMAT,
167        sci_exp,
168        options,
169        write_float_scientific,
170        write_float_nonscientific,
171        write_float_nonscientific,
172        bytes => bytes,
173        args => sci_exp, &mut buffer, initial_cursor,
174                integer_cursor, fraction_cursor, options,
175    )
176}
177
178/// Write float to string in scientific notation.
179///
180/// # Preconditions
181///
182/// The mantissa must be truncated and rounded, prior to calling this,
183/// based on the number of maximum digits. In addition, `exponent_base`
184/// and `mantissa_radix` in `FORMAT` must be identical.
185#[cfg_attr(not(feature = "compact"), inline(always))]
186pub fn write_float_scientific<const FORMAT: u128>(
187    bytes: &mut [u8],
188    sci_exp: i32,
189    buffer: &mut [u8],
190    initial_cursor: usize,
191    integer_cursor: usize,
192    fraction_cursor: usize,
193    options: &Options,
194) -> usize {
195    // PRECONDITIONS
196    debug_assert!(bytes.len() >= BUFFER_SIZE);
197
198    // Config options.
199    let format = NumberFormat::<{ FORMAT }> {};
200    assert!(format.is_valid());
201    let decimal_point = options.decimal_point();
202
203    // Round and truncate the number of significant digits.
204    let start: usize = if sci_exp <= 0 {
205        ((initial_cursor as i32) - sci_exp - 1) as usize
206    } else {
207        integer_cursor
208    };
209    let end = fraction_cursor.min(start + MAX_DIGIT_LENGTH + 1);
210    let (mut digit_count, carried) =
211        truncate_and_round(buffer, start, end, format.radix(), options);
212    let digits = &buffer[start..start + digit_count];
213    // If we carried, just adjust the exponent since we will always have a
214    // `digit_count == 1`. This means we don't have to worry about any other
215    // digits.
216    let sci_exp = sci_exp + carried as i32;
217
218    // Non-exponent portion.
219    // Get as many digits as possible, up to `MAX_DIGIT_LENGTH+1`
220    // since we are ignoring the digit for the first digit,
221    // or the number of written digits.
222    bytes[0] = digits[0];
223    bytes[1] = decimal_point;
224    let src = &digits[1..digit_count];
225    let dst = &mut bytes[2..digit_count + 1];
226    copy_to_dst(dst, src);
227    let zeros = rtrim_char_count(&bytes[2..digit_count + 1], b'0');
228    digit_count -= zeros;
229    // Extra 1 since we have the decimal point.
230    let mut cursor = digit_count + 1;
231
232    // Determine if we need to add more trailing zeros.
233    let exact_count = shared::min_exact_digits(digit_count, options);
234
235    // Write any trailing digits to the output.
236    // Won't panic since bytes cannot be empty.
237    if !format.no_exponent_without_fraction() && cursor == 2 && options.trim_floats() {
238        // Need to trim floats from trailing zeros, and we have only a decimal.
239        cursor -= 1;
240    } else if exact_count < 2 {
241        // Need to have at least 1 digit, the trailing `.0`.
242        bytes[cursor] = b'0';
243        cursor += 1;
244    } else if exact_count > digit_count {
245        // NOTE: Neither `exact_count >= digit_count >= 2`.
246        // We need to write `exact_count - (cursor - 1)` digits, since
247        // cursor includes the decimal point.
248        let digits_end = exact_count + 1;
249        bytes[cursor..digits_end].fill(b'0');
250        cursor = digits_end;
251    }
252
253    // Now, write our scientific notation.
254    shared::write_exponent::<FORMAT>(bytes, &mut cursor, sci_exp, options.exponent());
255
256    cursor
257}
258
259/// Write float to string without scientific notation.
260#[cfg_attr(not(feature = "compact"), inline(always))]
261pub fn write_float_nonscientific<const FORMAT: u128>(
262    bytes: &mut [u8],
263    _: i32,
264    buffer: &mut [u8],
265    initial_cursor: usize,
266    integer_cursor: usize,
267    fraction_cursor: usize,
268    options: &Options,
269) -> usize {
270    // PRECONDITIONS
271    debug_assert!(bytes.len() >= BUFFER_SIZE);
272
273    // Config options.
274    let format = NumberFormat::<{ FORMAT }> {};
275    assert!(format.is_valid());
276    let decimal_point = options.decimal_point();
277
278    // Round and truncate the number of significant digits.
279    let mut start = integer_cursor;
280    let end = fraction_cursor.min(start + MAX_DIGIT_LENGTH + 1);
281    let (mut digit_count, carried) =
282        truncate_and_round(buffer, start, end, format.radix(), options);
283
284    // Adjust the buffer if we carried.
285    // Note that we can **only** carry if it overflowed through the integer
286    // component, since we always write at least 1 integer digit.
287    if carried {
288        debug_assert!(digit_count == 1);
289        start -= 1;
290        buffer[start] = b'1';
291    }
292
293    let digits = &buffer[start..start + digit_count];
294
295    // Write the integer component.
296    let integer_length = initial_cursor - start;
297    let integer_count = digit_count.min(integer_length);
298    let src = &digits[..integer_count];
299    let dst = &mut bytes[..integer_count];
300    copy_to_dst(dst, src);
301    if integer_count < integer_length {
302        // We have more leading digits than digits we wrote: can write
303        // any additional digits, and then just write the remaining zeros.
304        bytes[integer_count..integer_length].fill(b'0');
305    }
306    let mut cursor = integer_length;
307    bytes[cursor] = decimal_point;
308    cursor += 1;
309
310    // Write the fraction component.
311    // We've only consumed `integer_count` digits, since this input
312    // may have been truncated.
313    // Won't panic since `integer_count < digits.len()` since `digit_count <
314    // digits.len()`.
315    let digits = &digits[integer_count..];
316    let fraction_count = digit_count.saturating_sub(integer_length);
317    if fraction_count > 0 {
318        // Need to write additional fraction digits.
319        let src = &digits[..fraction_count];
320        let end = cursor + fraction_count;
321        let dst = &mut bytes[cursor..end];
322        copy_to_dst(dst, src);
323        let zeros = rtrim_char_count(&bytes[cursor..end], b'0');
324        cursor += fraction_count - zeros;
325    } else if options.trim_floats() {
326        // Remove the decimal point, went too far.
327        cursor -= 1;
328    } else {
329        bytes[cursor] = b'0';
330        cursor += 1;
331        digit_count += 1;
332    }
333
334    // Determine if we need to add more trailing zeros.
335    let exact_count = shared::min_exact_digits(digit_count, options);
336
337    // Write any trailing digits to the output.
338    // Won't panic since bytes cannot be empty.
339    if (fraction_count > 0 || !options.trim_floats()) && exact_count > digit_count {
340        // NOTE: Neither `exact_count >= digit_count >= 2`.
341        // We need to write `exact_count - (cursor - 1)` digits, since
342        // cursor includes the decimal point.
343        let digits_end = cursor + exact_count - digit_count;
344        bytes[cursor..digits_end].fill(b'0');
345        cursor = digits_end;
346    }
347
348    cursor
349}
350
351// Store the first digit and up to `BUFFER_SIZE - 20` digits
352// that occur from left-to-right in the decimal representation.
353// For example, for the number 123.45, store the first digit `1`
354// and `2345` as the remaining values. Then, decide on-the-fly
355// if we need scientific or regular formatting.
356//
357//   BUFFER_SIZE
358// - 1      # first digit
359// - 1      # period
360// - 1      # +/- sign
361// - 2      # e and +/- sign
362// - 9      # max exp is 308, in radix2 is 9
363// - 1      # null terminator
364// = 15 characters of formatting required
365// Just pad it a bit, we don't want memory corruption.
366const MAX_NONDIGIT_LENGTH: usize = 25;
367const MAX_DIGIT_LENGTH: usize = BUFFER_SIZE - MAX_NONDIGIT_LENGTH;
368
369/// Round mantissa to the nearest value, returning only the number
370/// of significant digits. Returns the number of digits of the mantissa,
371/// and if the rounding did a full carry.
372#[cfg_attr(not(feature = "compact"), inline(always))]
373#[allow(clippy::comparison_chain)] // reason="conditions are different logical concepts"
374pub fn truncate_and_round(
375    buffer: &mut [u8],
376    start: usize,
377    end: usize,
378    radix: u32,
379    options: &Options,
380) -> (usize, bool) {
381    debug_assert!(end >= start);
382    debug_assert!(end <= buffer.len());
383
384    // Get the number of max digits, and then calculate if we need to round.
385    let digit_count = end - start;
386    let max_digits = if let Some(digits) = options.max_significant_digits() {
387        digits.get()
388    } else {
389        return (digit_count, false);
390    };
391
392    if max_digits >= digit_count {
393        return (digit_count, false);
394    }
395    if options.round_mode() == RoundMode::Truncate {
396        // Don't round input, just shorten number of digits emitted.
397        return (max_digits, false);
398    }
399
400    // Need to add the number of leading zeros to the digits `digit_count`.
401    let max_digits = {
402        let digits = &mut buffer[start..start + max_digits];
403        max_digits + ltrim_char_count(digits, b'0')
404    };
405
406    // We need to round-nearest, tie-even, so we need to handle
407    // the truncation **here**. If the representation is above
408    // halfway at all, we need to round up, even if 1 bit.
409    let last = buffer[start + max_digits - 1];
410    let first = buffer[start + max_digits];
411    let halfway = digit_to_char_const(radix / 2, radix);
412    let rem = radix % 2;
413    if first < halfway {
414        // Just truncate, going to round-down anyway.
415        (max_digits, false)
416    } else if first > halfway {
417        // Round-up always.
418        let digits = &mut buffer[start..start + max_digits];
419        shared::round_up(digits, max_digits, radix)
420    } else if rem == 0 {
421        // Even radix, our halfway point `$c00000.....`.
422        let truncated = &buffer[start + max_digits + 1..end];
423        if truncated.iter().all(|&x| x == b'0') && last & 1 == 0 {
424            // At an exact halfway point, and even, round-down.
425            (max_digits, false)
426        } else {
427            // Above halfway or at halfway and even, round-up
428            let digits = &mut buffer[start..start + max_digits];
429            shared::round_up(digits, max_digits, radix)
430        }
431    } else {
432        // Odd radix, our halfway point is `$c$c$c$c$c$c....`. Cannot halfway points.
433        let truncated = &buffer[start + max_digits + 1..end];
434        for &c in truncated.iter() {
435            if c < halfway {
436                return (max_digits, false);
437            } else if c > halfway {
438                // Above halfway
439                let digits = &mut buffer[start..start + max_digits];
440                return shared::round_up(digits, max_digits, radix);
441            }
442        }
443        (max_digits, false)
444    }
445}