json_cursor/
number.rs

1//! Numbers: their grammar, read eight digits at a time, and the values they hold exactly.
2
3use crate::scan::word;
4use crate::{Error, ErrorKind};
5
6/// A number as the cursor read it.
7///
8/// [`text`](Self::text) is the number exactly as written. [`as_i64`](Self::as_i64) and
9/// [`as_f64`](Self::as_f64) give its value exactly, from the digits the cursor read while it
10/// checked the number's grammar, so most numbers need no second pass over their text.
11#[derive(Clone, Copy)]
12pub struct Number<'a> {
13    /// The input, and where the number lies in it: sliced only when the text is asked for.
14    input: &'a str,
15    start: usize,
16    end: usize,
17    negative: bool,
18    /// The digits with the point taken out: exact when `exact`, with at most 19 of them.
19    digits: u64,
20    exact: bool,
21    /// The power of ten the digits are scaled by: the exponent, less the digits after the point.
22    scale: i64,
23    /// Written with digits only: no point, no exponent.
24    integer: bool,
25}
26
27/// What a number's digits say, gathered as they are read.
28#[derive(Clone, Copy, Default)]
29pub(crate) struct Parts {
30    negative: bool,
31    digits: u64,
32    count: usize,
33    scale: i64,
34    integer: bool,
35}
36
37/// The largest integer a double holds exactly, along with every integer below it.
38const EXACT: u64 = 1 << 53;
39
40/// Powers of ten a double holds exactly.
41const POW10: [f64; 23] = [
42    1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20,
43    1e21, 1e22,
44];
45
46/// Powers of ten a `u64` holds.
47const POW10_U64: [u64; 20] = [
48    1,
49    10,
50    100,
51    1_000,
52    10_000,
53    100_000,
54    1_000_000,
55    10_000_000,
56    100_000_000,
57    1_000_000_000,
58    10_000_000_000,
59    100_000_000_000,
60    1_000_000_000_000,
61    10_000_000_000_000,
62    100_000_000_000_000,
63    1_000_000_000_000_000,
64    10_000_000_000_000_000,
65    100_000_000_000_000_000,
66    1_000_000_000_000_000_000,
67    10_000_000_000_000_000_000,
68];
69
70impl<'a> Number<'a> {
71    #[inline]
72    pub(crate) fn new(input: &'a str, start: usize, end: usize, p: Parts) -> Self {
73        Number {
74            input,
75            start,
76            end,
77            negative: p.negative,
78            digits: p.digits,
79            exact: p.count <= 19,
80            scale: p.scale,
81            integer: p.integer,
82        }
83    }
84
85    /// The number exactly as written: `12.50` stays `12.50`, and a 30-digit integer keeps every digit.
86    #[inline]
87    pub fn text(&self) -> &'a str {
88        // both ends are ASCII bytes, so char boundaries: the slice always exists
89        self.input.get(self.start..self.end).unwrap_or_default()
90    }
91
92    /// Whether it is written with digits only, with no point and no exponent: `7` is, `7.0` and
93    /// `7e0` are not.
94    #[inline]
95    pub fn is_integer(&self) -> bool {
96        self.integer
97    }
98
99    /// The number as an `i64`, exactly, when it is a whole number that fits, however it is written:
100    /// `7`, `7.0`, `700e-2` and `1e3` all are, and `-0` is `0`. `1.5` and `9223372036854775808`
101    /// are `None`. No float is used on the way: a fraction is never cut, nor a digit rounded.
102    #[inline]
103    pub fn as_i64(&self) -> Option<i64> {
104        if !self.exact {
105            return whole_from_text(self.text());
106        }
107        let digits = self.digits;
108        let magnitude = if digits == 0 {
109            0
110        } else if self.scale >= 0 {
111            digits.checked_mul(*POW10_U64.get(self.scale as usize)?)?
112        } else {
113            // a whole number when the digits after the point are all zeros
114            let p = *POW10_U64.get(self.scale.unsigned_abs() as usize)?;
115            if digits % p != 0 {
116                return None;
117            }
118            digits / p
119        };
120        signed(self.negative, magnitude)
121    }
122
123    /// The nearest `f64`, correctly rounded, exactly as Rust's own parser gives it: `1e400` is
124    /// infinite, and `-0` is negative zero.
125    ///
126    /// Most numbers take one multiplication or division, with no second pass. Digits that fit 2^53
127    /// and a power of ten up to 10^22 are both exact in a double, so one rounding gives the nearest
128    /// (Clinger's fast path). A larger power still qualifies when part of it moves into the digits
129    /// and they still fit, as `123e30` is `123000000 × 10^22`. The rest go through `str::parse`.
130    #[inline]
131    pub fn as_f64(&self) -> f64 {
132        if self.exact {
133            let digits = self.digits;
134            let fast = if digits > EXACT {
135                None
136            } else if (-22..=0).contains(&self.scale) {
137                Some(digits as f64 / POW10[self.scale.unsigned_abs() as usize])
138            } else if (0..=22).contains(&self.scale) {
139                Some(digits as f64 * POW10[self.scale as usize])
140            } else if (23..=22 + 15).contains(&self.scale) {
141                digits
142                    .checked_mul(POW10_U64[self.scale as usize - 22])
143                    .filter(|&m| m <= EXACT)
144                    .map(|m| m as f64 * 1e22)
145            } else {
146                None
147            };
148            if let Some(v) = fast {
149                return if self.negative { -v } else { v };
150            }
151        }
152        parse(self.text())
153    }
154}
155
156/// Two numbers are equal when they are written the same.
157impl PartialEq for Number<'_> {
158    fn eq(&self, other: &Self) -> bool {
159        self.text() == other.text()
160    }
161}
162
163impl Eq for Number<'_> {}
164
165impl core::fmt::Debug for Number<'_> {
166    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
167        f.debug_tuple("Number").field(&self.text()).finish()
168    }
169}
170
171/// A number past the fast paths, through Rust's own parser, which takes JSON's grammar: kept out
172/// of line, so the fast paths stay small where they are inlined.
173#[cold]
174#[inline(never)]
175fn parse(text: &str) -> f64 {
176    text.parse().unwrap_or(f64::NAN)
177}
178
179/// A magnitude with its sign, when it fits an `i64`, down to `i64::MIN`.
180#[inline]
181fn signed(negative: bool, magnitude: u64) -> Option<i64> {
182    if negative {
183        (magnitude <= 1 << 63).then(|| 0u64.wrapping_sub(magnitude) as i64)
184    } else {
185        i64::try_from(magnitude).ok()
186    }
187}
188
189/// The exact whole value of a number written with more than 19 digits, such as
190/// `1000000000000000000000e-3`: zeros at either end of its digits count only for the scale.
191#[cold]
192#[inline(never)]
193fn whole_from_text(text: &str) -> Option<i64> {
194    let b = text.as_bytes();
195    let negative = b.first() == Some(&b'-');
196    let body = &b[usize::from(negative)..];
197    let (mantissa, exponent) = match body.iter().position(|&c| c == b'e' || c == b'E') {
198        Some(e) => (&body[..e], &body[e + 1..]),
199        None => (body, &b""[..]),
200    };
201    let exponent = match exponent {
202        [b'-', d @ ..] => -saturating_digits(d),
203        [b'+', d @ ..] | d => saturating_digits(d),
204    };
205    let (int, frac) = match mantissa.iter().position(|&c| c == b'.') {
206        Some(p) => (&mantissa[..p], &mantissa[p + 1..]),
207        None => (mantissa, &b""[..]),
208    };
209    let digit = |i: usize| if i < int.len() { int[i] } else { frac[i - int.len()] };
210    let len = int.len() + frac.len();
211    let Some(first) = (0..len).find(|&i| digit(i) != b'0') else {
212        return Some(0);
213    };
214    let last = (0..len).rev().find(|&i| digit(i) != b'0')?;
215    if last - first >= 19 {
216        return None;
217    }
218    // the power of ten of the last digit that is not a zero
219    let scale = exponent
220        .saturating_sub(frac.len() as i64)
221        .saturating_add((len - 1 - last) as i64);
222    let mut magnitude: u64 = 0;
223    for i in first..=last {
224        magnitude = magnitude * 10 + u64::from(digit(i) - b'0');
225    }
226    signed(
227        negative,
228        // a negative scale leaves a fraction, so no whole value
229        magnitude.checked_mul(*POW10_U64.get(usize::try_from(scale).ok()?)?)?,
230    )
231}
232
233fn saturating_digits(d: &[u8]) -> i64 {
234    d.iter()
235        .fold(0i64, |v, &c| v.saturating_mul(10).saturating_add(i64::from(c - b'0')))
236}
237
238/// At a number's first byte, `-` or a digit, at `at`: reads it, checking its grammar, and gives
239/// the offset after it. With `VALUE`, also its parts, gathered from the digits as they are read.
240#[inline(always)]
241pub(crate) fn read<const VALUE: bool>(bytes: &[u8], start: usize) -> Result<(usize, Parts), Error> {
242    let bad = Error::new(ErrorKind::Number, start);
243    let mut p = Parts {
244        integer: true,
245        ..Parts::default()
246    };
247    let mut at = start;
248    if bytes.get(at) == Some(&b'-') {
249        p.negative = true;
250        at += 1;
251    }
252    match bytes.get(at) {
253        Some(b'0') => {
254            at += 1;
255            p.count = 1;
256        }
257        Some(b'1'..=b'9') => {
258            let end = digits::<VALUE>(bytes, at, &mut p.digits);
259            p.count = end - at;
260            at = end;
261        }
262        _ => return Err(bad),
263    }
264    let mut fraction = 0;
265    if bytes.get(at) == Some(&b'.') {
266        at += 1;
267        let end = digits::<VALUE>(bytes, at, &mut p.digits);
268        fraction = end - at;
269        if fraction == 0 {
270            return Err(bad);
271        }
272        at = end;
273        p.count += fraction;
274        p.integer = false;
275    }
276    let mut exponent: i64 = 0;
277    if let Some(b'e' | b'E') = bytes.get(at) {
278        at += 1;
279        p.integer = false;
280        let down = match bytes.get(at) {
281            Some(b'-') => {
282                at += 1;
283                true
284            }
285            Some(b'+') => {
286                at += 1;
287                false
288            }
289            _ => false,
290        };
291        let from = at;
292        while let Some(&d @ b'0'..=b'9') = bytes.get(at) {
293            if VALUE {
294                exponent = exponent.saturating_mul(10).saturating_add(i64::from(d - b'0'));
295            }
296            at += 1;
297        }
298        if at == from {
299            return Err(bad);
300        }
301        if down {
302            exponent = -exponent;
303        }
304    }
305    p.scale = exponent.saturating_sub(fraction as i64);
306    // a number ends where its grammar does: in `01` it is `0`, and the next read refuses the `1`
307    Ok((at, p))
308}
309
310const ZEROS: u64 = 0x3030_3030_3030_3030;
311
312/// From `at`, the run of ASCII digits: its end, and with `VALUE`, the digits added onto `value`,
313/// exact while it holds at most 19. Eight at a time while all eight are digits; with no value to
314/// gather, a word's leading digits are counted at once.
315#[inline(always)]
316fn digits<const VALUE: bool>(bytes: &[u8], mut at: usize, value: &mut u64) -> usize {
317    while let Some(w) = bytes.get(at..at + 8) {
318        let word = word(w);
319        let n = leading_digits(word);
320        if n < 8 {
321            if !VALUE {
322                return at + n;
323            }
324            break;
325        }
326        if VALUE {
327            *value = value.wrapping_mul(100_000_000).wrapping_add(eight_digits(word));
328        }
329        at += 8;
330    }
331    // fewer than eight: a short run is cheaper a digit at a time than through the word
332    while let Some(&d @ b'0'..=b'9') = bytes.get(at) {
333        if VALUE {
334            *value = value.wrapping_mul(10).wrapping_add(u64::from(d - b'0'));
335        }
336        at += 1;
337    }
338    at
339}
340
341/// How many of `word`'s bytes, from its lowest, are ASCII digits: 0 to 8.
342#[inline(always)]
343fn leading_digits(word: u64) -> usize {
344    // a digit's high nibble is 3, and stays 3 when 6 is added; a carry into the next byte comes only
345    // from a byte that is not a digit, so the count up to the first such byte is exact
346    const HIGH_NIBBLES: u64 = 0xF0F0_F0F0_F0F0_F0F0;
347    let off = ((word & HIGH_NIBBLES) ^ ZEROS) | ((word.wrapping_add(0x0606_0606_0606_0606) & HIGH_NIBBLES) ^ ZEROS);
348    (off.trailing_zeros() / 8) as usize
349}
350
351/// Eight ASCII digits, the first in the lowest byte, as their value: three multiplications, after
352/// fast_float and simdjson.
353#[inline(always)]
354fn eight_digits(word: u64) -> u64 {
355    const MASK: u64 = 0x0000_00FF_0000_00FF;
356    const MUL1: u64 = 100 + (1_000_000 << 32);
357    const MUL2: u64 = 1 + (10_000 << 32);
358    let v = word - ZEROS;
359    // each pair of digits as one value below 100, in the even bytes
360    let v = v * 10 + (v >> 8);
361    (v & MASK)
362        .wrapping_mul(MUL1)
363        .wrapping_add(((v >> 16) & MASK).wrapping_mul(MUL2))
364        >> 32
365}
366
367#[cfg(test)]
368mod tests {
369    use super::{eight_digits, leading_digits};
370    use crate::scan::word;
371    use crate::testing::Rng;
372
373    /// Bytes next to the digits, and those whose add carries into the next byte.
374    const OTHERS: [u8; 12] = [b'/', b':', b'.', b'e', b'-', b' ', b'"', 0x00, 0x2f, 0x3a, 0xfa, 0xff];
375
376    #[test]
377    fn leading_digits_counts_to_the_first_byte_that_is_not_one() {
378        let mut rng = Rng(0x853C_49E6_748F_EA9B);
379        for n in 0..=8 {
380            for &other in &OTHERS {
381                for _ in 0..200 {
382                    let mut b = [0u8; 8];
383                    for (i, byte) in b.iter_mut().enumerate() {
384                        let r = rng.next();
385                        *byte = if i < n {
386                            b'0' + (r % 10) as u8
387                        } else if i == n {
388                            other
389                        } else {
390                            // anything after the first non-digit, digits included
391                            (r >> 8) as u8
392                        };
393                    }
394                    assert_eq!(leading_digits(word(&b)), n, "{b:?}");
395                }
396            }
397        }
398    }
399
400    #[test]
401    fn eight_digits_read_in_a_word_have_their_value() {
402        let mut rng = Rng(0x2545_F491_4F6C_DD1D);
403        for _ in 0..100_000 {
404            let r = rng.next();
405            let mut b = [0u8; 8];
406            let mut value = 0u64;
407            for (i, byte) in b.iter_mut().enumerate() {
408                let d = ((r >> (i * 4)) % 10) as u8;
409                *byte = b'0' + d;
410                value = value * 10 + u64::from(d);
411            }
412            assert_eq!(eight_digits(word(&b)), value, "{b:?}");
413        }
414        assert_eq!(eight_digits(word(b"99999999")), 99_999_999);
415        assert_eq!(eight_digits(word(b"00000000")), 0);
416    }
417}
json_cursor/number.rs

json_cursor/
number.rs
