use core::fmt;
use core::ops::Deref;
use crate::consts::{ONE_RAW, POW10};
use crate::error::{BufferTooSmall, ParseError};
use crate::kernel::mul::{D, div2by1};
use crate::round::{Round, decide, round_away};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Parsed {
pub(crate) negative: bool,
pub(crate) magnitude: u128,
pub(crate) dropped: Dropped,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Dropped {
Nothing,
BelowHalf,
Half,
AboveHalf,
}
impl Dropped {
const fn new(first: u8, sticky: bool) -> Self {
match (first, sticky) {
(0, false) => Dropped::Nothing,
(0..=4, _) => Dropped::BelowHalf,
(5, false) => Dropped::Half,
_ => Dropped::AboveHalf,
}
}
}
pub(crate) const fn parse(
b: &[u8],
start: usize,
end: usize,
round: Option<Round>,
) -> Result<Parsed, ParseError> {
let mut i = start;
let mut negative = false;
if i < end && (b[i] == b'-' || b[i] == b'+') {
negative = b[i] == b'-';
i += 1;
}
let int_start = i;
let (int_end, int_value) = scan_digits(b, i, end);
i = int_end;
let mut frac_start = i;
let mut frac_end = i;
let mut frac_value = 0;
if i < end && b[i] == b'.' {
frac_start = i + 1;
(frac_end, frac_value) = scan_digits(b, frac_start, end);
i = frac_end;
}
if i != end || (int_end == int_start && frac_end == frac_start) {
return Err(ParseError::Invalid);
}
let mut magnitude = if int_end - int_start <= 19 {
int_value as u128 * ONE_RAW
} else {
let mut s = int_start;
while s < int_end && b[s] == b'0' {
s += 1;
}
let int_len = int_end - s;
if int_len <= 19 {
digits_to_u64(b, s, int_len) as u128 * ONE_RAW
} else if int_len == 20 {
let whole =
(b[s] - b'0') as u128 * ONE_RAW + digits_to_u64(b, s + 1, 19) as u128;
match whole.checked_mul(ONE_RAW) {
Some(v) => v,
None => return Err(ParseError::OutOfRange),
}
} else {
return Err(ParseError::OutOfRange);
}
};
let frac_len = frac_end - frac_start;
if frac_len > 19 {
frac_value = digits_to_u64(b, frac_start, 19);
}
let kept = if frac_len < 19 { frac_len } else { 19 };
let frac = frac_value as u128 * POW10_U64[19 - kept] as u128;
magnitude = match magnitude.checked_add(frac) {
Some(v) => v,
None => return Err(ParseError::OutOfRange),
};
if frac_len <= 19 {
return Ok(Parsed {
negative,
magnitude,
dropped: Dropped::Nothing,
});
}
let first_extra = b[frac_start + 19] - b'0';
let mut sticky = false;
let mut j = frac_start + 20;
while j < frac_end {
sticky |= b[j] != b'0';
j += 1;
}
round_extra(negative, magnitude, first_extra, sticky, round)
}
const fn round_extra(
negative: bool,
magnitude: u128,
first_extra: u8,
sticky: bool,
round: Option<Round>,
) -> Result<Parsed, ParseError> {
let dropped = Dropped::new(first_extra, sticky);
let Some(mode) = round else {
return Ok(Parsed {
negative,
magnitude,
dropped,
});
};
let away = decide(
mode,
negative,
magnitude & 1 == 1,
matches!(dropped, Dropped::AboveHalf),
matches!(dropped, Dropped::Half),
!matches!(dropped, Dropped::Nothing),
);
let magnitude = if away {
match magnitude.checked_add(1) {
Some(v) => v,
None => return Err(ParseError::OutOfRange),
}
} else {
magnitude
};
Ok(Parsed {
negative,
magnitude,
dropped: Dropped::Nothing,
})
}
#[inline(always)]
const fn load8(b: &[u8], i: usize) -> u64 {
u64::from_le_bytes([
b[i],
b[i + 1],
b[i + 2],
b[i + 3],
b[i + 4],
b[i + 5],
b[i + 6],
b[i + 7],
])
}
#[inline(always)]
const fn non_digits(chunk: u64) -> u64 {
let t = chunk ^ 0x3030_3030_3030_3030;
(t.wrapping_add(0x7676_7676_7676_7676) | t) & 0x8080_8080_8080_8080
}
#[inline(always)]
const fn eight_digits(chunk: u64) -> u64 {
let v = chunk.wrapping_sub(0x3030_3030_3030_3030); let v = (v.wrapping_mul(10).wrapping_add(v >> 8)) & 0x00FF_00FF_00FF_00FF;
let v = (v.wrapping_mul(100).wrapping_add(v >> 16)) & 0x0000_FFFF_0000_FFFF;
(v.wrapping_mul(10_000).wrapping_add(v >> 32)) & 0xFFFF_FFFF
}
#[inline(always)]
const fn scan_digits(b: &[u8], mut i: usize, end: usize) -> (usize, u64) {
let mut value = 0u64;
while i + 8 <= end {
let chunk = load8(b, i);
let flags = non_digits(chunk);
if flags != 0 {
break;
}
value = value
.wrapping_mul(100_000_000)
.wrapping_add(eight_digits(chunk));
i += 8;
}
while i < end {
let d = b[i].wrapping_sub(b'0');
if d > 9 {
break;
}
value = value.wrapping_mul(10).wrapping_add(d as u64);
i += 1;
}
(i, value)
}
#[inline(always)]
const fn digits_to_u64(b: &[u8], s: usize, len: usize) -> u64 {
let end = s + len;
let mut acc = 0u64;
let mut i = s;
while i + 8 <= end {
acc = acc * 100_000_000 + eight_digits(load8(b, i));
i += 8;
}
while i < end {
acc = acc * 10 + (b[i] - b'0') as u64;
i += 1;
}
acc
}
pub(crate) const fn parse_scalar(
b: &[u8],
start: usize,
end: usize,
underscores: bool,
round: Option<Round>,
) -> Result<Parsed, ParseError> {
let mut i = start;
let mut negative = false;
if i < end && (b[i] == b'-' || b[i] == b'+') {
negative = b[i] == b'-';
i += 1;
}
let mut int: u128 = 0;
let mut overflow = false;
let mut digits = 0usize;
while i < end {
let c = b[i];
if c.is_ascii_digit() {
match int.checked_mul(10) {
Some(v) => match v.checked_add((c - b'0') as u128) {
Some(v) => int = v,
None => overflow = true,
},
None => overflow = true,
}
digits += 1;
} else if !(c == b'_' && underscores) {
break;
}
i += 1;
}
let mut frac: u128 = 0;
let mut frac_len = 0usize;
let mut extra_digits = 0usize;
let mut first_extra: u8 = 0;
let mut sticky = false;
if i < end && b[i] == b'.' {
i += 1;
while i < end {
let c = b[i];
if c.is_ascii_digit() {
let d = c - b'0';
if frac_len < 19 {
frac = frac * 10 + d as u128;
frac_len += 1;
} else {
if extra_digits == 0 {
first_extra = d;
} else if d != 0 {
sticky = true;
}
extra_digits += 1;
}
digits += 1;
} else if !(c == b'_' && underscores) {
break;
}
i += 1;
}
}
if i != end || digits == 0 {
return Err(ParseError::Invalid);
}
if overflow {
return Err(ParseError::OutOfRange);
}
let mut magnitude = match int.checked_mul(ONE_RAW) {
Some(v) => v,
None => return Err(ParseError::OutOfRange),
};
magnitude = match magnitude.checked_add(frac * POW10[19 - frac_len]) {
Some(v) => v,
None => return Err(ParseError::OutOfRange),
};
round_extra(negative, magnitude, first_extra, sticky, round)
}
pub(crate) const fn parse_literal(s: &str) -> Result<Parsed, &'static str> {
let b = s.as_bytes();
let end = b.len();
let mut i = 0;
let mut negative = false;
if i < end && b[i] == b'-' {
negative = true;
i += 1;
while i < end && b[i] == b' ' {
i += 1;
}
}
if i < end && b[i] == b'"' {
if negative {
return Err("put the minus sign inside the string, e.g. dec!(\"-1.5\")");
}
if end - i < 2 || b[end - 1] != b'"' {
return Err("invalid string literal");
}
return match parse_scalar(b, i + 1, end - 1, false, None) {
Ok(v) => Ok(v),
Err(e) => Err(e.as_str()),
};
}
let mut j = i;
while j < end {
let c = b[j];
if c == b'e' || c == b'E' {
return Err("exponents are not supported: write the number out in full");
}
if c.is_ascii_alphabetic() {
return Err(
"only plain decimal literals are allowed (no suffix such as f64, no \
hex, octal or binary)",
);
}
j += 1;
}
match parse_scalar(b, i, end, true, None) {
Ok(Parsed { negative: true, .. }) => Err(ParseError::Invalid.as_str()),
Ok(p) => Ok(Parsed { negative, ..p }),
Err(e) => Err(e.as_str()),
}
}
const DIGIT_PAIRS: [u8; 200] = {
let mut t = [0u8; 200];
let mut i = 0;
while i < 100 {
t[2 * i] = b'0' + (i / 10) as u8;
t[2 * i + 1] = b'0' + (i % 10) as u8;
i += 1;
}
t
};
const POW10_U64: [u64; 20] = {
let mut t = [1u64; 20];
let mut k = 1;
while k < 20 {
t[k] = t[k - 1] * 10;
k += 1;
}
t
};
#[inline(always)]
pub(crate) fn split(m: u128) -> (u128, u64) {
let hi = (m >> 64) as u64;
let lo = m as u64;
let (top, hi) = if hi >= D { (1u128, hi - D) } else { (0, hi) };
let (q, r) = div2by1(hi, lo);
((top << 64) | q as u128, r)
}
#[inline(always)]
const fn digits8(n: u64) -> u64 {
let x = (n / 10_000) | ((n % 10_000) << 32);
let q = ((x * 5243) >> 19) & 0x0000_007F_0000_007F;
let x = q | ((x - q * 100) << 16);
let q = ((x * 103) >> 10) & 0x000F_000F_000F_000F;
q | ((x - q * 10) << 8)
}
const ZEROS: u64 = 0x3030_3030_3030_3030;
#[inline(always)]
fn write_u64(buf: &mut [u8], pos: usize, v: u64) -> usize {
if v < 100_000_000 {
let n = v.checked_ilog10().map_or(1, |l| l as usize + 1);
let x = (digits8(v) + ZEROS) >> (8 * (8 - n));
buf[pos..pos + 8].copy_from_slice(&x.to_le_bytes());
pos + n
} else {
let pos = write_u64(buf, pos, v / 100_000_000);
let x = digits8(v % 100_000_000) + ZEROS;
buf[pos..pos + 8].copy_from_slice(&x.to_le_bytes());
pos + 8
}
}
#[inline(always)]
fn write_frac19(buf: &mut [u8], pos: usize, frac: u64) -> usize {
let a = frac / 10_000_000_000_000_000;
let rest = frac % 10_000_000_000_000_000;
let (b, c) = (rest / 100_000_000, rest % 100_000_000);
let (xb, xc) = (digits8(b), digits8(c));
let pair = (a % 100) as usize * 2;
buf[pos] = b'0' + (a / 100) as u8;
buf[pos + 1] = DIGIT_PAIRS[pair];
buf[pos + 2] = DIGIT_PAIRS[pair + 1];
buf[pos + 3..pos + 11].copy_from_slice(&(xb + ZEROS).to_le_bytes());
buf[pos + 11..pos + 19].copy_from_slice(&(xc + ZEROS).to_le_bytes());
if xc != 0 {
xc.leading_zeros() as usize / 8
} else if xb != 0 {
8 + xb.leading_zeros() as usize / 8
} else {
16 + a.is_multiple_of(10) as usize + a.is_multiple_of(100) as usize
}
}
#[inline(always)]
fn write_fixed(buf: &mut [u8], pos: usize, v: u64, width: usize) {
if width <= 8 {
let x = (digits8(v) + ZEROS) >> (8 * (8 - width));
buf[pos..pos + 8].copy_from_slice(&x.to_le_bytes());
} else {
write_fixed(buf, pos, v / 100_000_000, width - 8);
let x = digits8(v % 100_000_000) + ZEROS;
buf[pos + width - 8..pos + width].copy_from_slice(&x.to_le_bytes());
}
}
#[inline(always)]
fn write_whole(buf: &mut [u8], pos: usize, int: u128) -> usize {
if let Ok(v) = u64::try_from(int) {
write_u64(buf, pos, v)
} else {
buf[pos] = b'0' + (int / ONE_RAW) as u8;
write_frac19(buf, pos + 1, (int % ONE_RAW) as u64);
pos + 20
}
}
pub(crate) type Scratch = [u8; 49];
#[inline(always)]
fn copy_out(buf: &[u8], out: &mut [u8]) -> Result<usize, BufferTooSmall> {
let dest = out.get_mut(..buf.len()).ok_or(BufferTooSmall)?;
dest.copy_from_slice(buf);
Ok(buf.len())
}
#[inline]
pub(crate) fn write_shortest(
negative: bool,
magnitude: u128,
out: &mut [u8],
) -> Result<usize, BufferTooSmall> {
let mut buf: Scratch = [0; 49];
let len = shortest(negative, magnitude, &mut buf);
copy_out(&buf[..len], out)
}
#[inline(always)]
pub(crate) fn shortest(
negative: bool,
magnitude: u128,
buf: &mut Scratch,
) -> usize {
let (int, frac) = split(magnitude);
let mut len = 0;
if negative && magnitude != 0 {
buf[0] = b'-';
len = 1;
}
len = write_whole(buf, len, int);
if frac != 0 {
buf[len] = b'.';
let trailing = write_frac19(buf, len + 1, frac);
len += 20 - trailing;
}
len
}
pub(crate) fn write_places(
negative: bool,
magnitude: u128,
places: u32,
mode: Round,
out: &mut [u8],
) -> Result<usize, BufferTooSmall> {
let (mut int, frac) = split(magnitude);
let places = places as usize;
if places >= 19 {
let mut buf: Scratch = [0; 49];
let mut len = 0;
if negative && magnitude != 0 {
buf[0] = b'-';
len = 1;
}
len = write_whole(&mut buf, len, int);
buf[len] = b'.';
write_frac19(&mut buf, len + 1, frac);
len += 20;
let total = len + (places - 19);
let dest = out.get_mut(..total).ok_or(BufferTooSmall)?;
dest[..len].copy_from_slice(&buf[..len]);
dest[len..].fill(b'0');
return Ok(total);
}
let step = POW10_U64[19 - places];
let mut kept = frac / step;
let dropped = frac % step;
let odd = if places == 0 {
int & 1 == 1
} else {
kept & 1 == 1
};
if round_away(mode, negative, odd, dropped as u128, step as u128) {
kept += 1;
if kept == POW10_U64[places] {
kept = 0;
int += 1;
}
}
let mut buf: Scratch = [0; 49];
let mut len = 0;
if negative && (int != 0 || kept != 0) {
buf[0] = b'-';
len = 1;
}
len = write_whole(&mut buf, len, int);
if places > 0 {
buf[len] = b'.';
write_fixed(&mut buf, len + 1, kept, places);
len += 1 + places;
}
copy_out(&buf[..len], out)
}
#[derive(Clone, Copy)]
pub struct AsciiBuf {
buf: Scratch,
len: u8,
}
impl AsciiBuf {
#[inline]
pub(crate) fn new(negative: bool, magnitude: u128) -> Self {
let mut buf: Scratch = [0; 49];
let len = shortest(negative, magnitude, &mut buf) as u8;
Self { buf, len }
}
#[must_use]
#[inline]
#[allow(unsafe_code)] pub fn as_str(&self) -> &str {
let bytes = self.as_bytes();
debug_assert!(bytes.is_ascii(), "AsciiBuf holds non-ASCII bytes");
unsafe { core::str::from_utf8_unchecked(bytes) }
}
#[must_use]
pub fn as_bytes(&self) -> &[u8] {
&self.buf[..self.len as usize]
}
}
impl Deref for AsciiBuf {
type Target = str;
fn deref(&self) -> &str {
self.as_str()
}
}
impl fmt::Display for AsciiBuf {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.pad(self.as_str())
}
}
impl fmt::Debug for AsciiBuf {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(self.as_str(), f)
}
}
pub(crate) fn display(
negative: bool,
magnitude: u128,
f: &mut fmt::Formatter<'_>,
) -> fmt::Result {
let mut buf = [0u8; 141];
let len = match f.precision() {
None => write_shortest(negative, magnitude, &mut buf),
Some(p) if p <= 100 => {
write_places(negative, magnitude, p as u32, Round::HalfEven, &mut buf)
}
Some(p) => {
let len =
write_places(negative, magnitude, 19, Round::HalfEven, &mut buf)
.expect("fits");
f.write_str(core::str::from_utf8(&buf[..len]).expect("ASCII"))?;
for _ in 19..p {
f.write_str("0")?;
}
return Ok(());
}
}
.expect("buffer fits");
let text = core::str::from_utf8(&buf[..len]).expect("ASCII");
let (non_negative, digits) = match text.strip_prefix('-') {
Some(rest) => (false, rest),
None => (true, text),
};
f.pad_integral(non_negative, "", digits)
}
#[cfg(test)]
mod tests {
use std::vec::Vec;
use std::{format, vec};
use proptest::prelude::*;
use super::*;
#[test]
fn digits8_and_eight_digits_agree_with_std() {
let step = if cfg!(miri) {
999_983
} else if cfg!(debug_assertions) {
997
} else {
1
};
let mut n = 0u64;
while n < 100_000_000 {
let ascii = (digits8(n) + ZEROS).to_le_bytes();
assert_eq!(&ascii, format!("{n:08}").as_bytes(), "digits8({n})");
assert_eq!(eight_digits(u64::from_le_bytes(ascii)), n);
n += step;
}
let last = 99_999_999u64;
assert_eq!(eight_digits(digits8(last) + ZEROS), last);
}
#[test]
fn non_digits_flags_the_first_non_digit_at_every_position() {
for pos in 0..8 {
for byte in 0..=255u8 {
let mut chunk = *b"55555555";
chunk[pos] = byte;
let flags = non_digits(u64::from_le_bytes(chunk));
if byte.is_ascii_digit() {
assert_eq!(flags, 0, "byte {byte:#x} at {pos}");
} else {
assert_eq!(
flags.trailing_zeros() / 8,
pos as u32,
"byte {byte:#x} at {pos}"
);
}
}
}
}
#[test]
fn scan_digits_stops_at_every_position() {
for len in 1..=24 {
for pos in 0..len {
for bad in [b'/', b':', b' ', b'.', b'_', 0x00, 0x80, 0xFA, 0xFF] {
let mut text = Vec::from(&b"123456789012345678901234"[..len]);
text[pos] = bad;
let (end, _) = scan_digits(&text, 0, len);
assert_eq!(end, pos, "len {len}, {bad:#x} at {pos}");
}
}
}
}
fn text_bytes() -> impl Strategy<Value = Vec<u8>> {
let byte = prop_oneof![
8 => b'0'..=b'9',
2 => Just(b'.'),
1 => Just(b'-'),
1 => Just(b'+'),
1 => prop::sample::select(vec![b'/', b':', b' ', b'e', b'_', 0, 0x80, 0xFA, 0xFF]),
];
prop::collection::vec(byte, 0..48)
}
proptest! {
#![proptest_config(ProptestConfig {
cases: if cfg!(miri) { 8 } else { 20_000 },
failure_persistence: None,
..ProptestConfig::default()
})]
#[test]
fn fast_parse_matches_scalar(text in text_bytes()) {
let n = text.len();
for round in [None, Some(Round::HalfEven), Some(Round::Floor)] {
prop_assert_eq!(
parse(&text, 0, n, round),
parse_scalar(&text, 0, n, false, round)
);
}
}
#[test]
fn fast_parse_matches_scalar_on_long_digit_runs(
int in "[0-9]{0,40}",
frac in proptest::option::of("[0-9]{0,40}"),
neg in any::<bool>(),
) {
let text = format!(
"{}{}{}",
if neg { "-" } else { "" },
int,
frac.map(|f| format!(".{f}")).unwrap_or_default()
);
let b = text.as_bytes();
for round in [None, Some(Round::HalfEven), Some(Round::Ceiling)] {
prop_assert_eq!(
parse(b, 0, b.len(), round),
parse_scalar(b, 0, b.len(), false, round)
);
}
}
}
}