diff --git a/Cargo.lock b/Cargo.lock index cacd4b32cc9..4e7080e1075 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -888,6 +888,38 @@ dependencies = [ "uuid", ] +[[package]] +name = "f128" +version = "0.2.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0b7d29530784c8b9e49eccb10c95abc69ac72e9e7eb29cb2649b13e08f766d2c" +dependencies = [ + "f128_input", + "f128_internal", + "libc", + "num-traits", +] + +[[package]] +name = "f128_input" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "18a821a6f74745607a8c99c932a8f513e6e7d6ee63725ec95511edf4a94510bb" +dependencies = [ + "f128_internal", +] + +[[package]] +name = "f128_internal" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9708a33de3cda4e6636670c1af561635fe249cb817dda1a14ec18fe9dda0a99d" +dependencies = [ + "cc", + "libc", + "num-traits", +] + [[package]] name = "fastrand" version = "2.0.1" @@ -3137,6 +3169,7 @@ version = "0.0.27" dependencies = [ "bigdecimal", "clap", + "f128", "num-bigint", "num-traits", "uucore", diff --git a/Cargo.toml b/Cargo.toml index 3219d50b268..0a7f609bfc6 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -285,6 +285,7 @@ crossterm = ">=0.27.0" ctrlc = { version = "3.4.4", features = ["termination"] } dns-lookup = { version = "2.0.4" } exacl = "0.12.0" +f128 = "0.2.9" # remove once support lands in stdlib https://github.com/rust-lang/rust/issues/116909#issuecomment-1969554030 file_diff = "1.0.0" filetime = "0.2.23" fnv = "1.0.7" diff --git a/src/uu/seq/Cargo.toml b/src/uu/seq/Cargo.toml index cdb514439f5..f9ed26b5f92 100644 --- a/src/uu/seq/Cargo.toml +++ b/src/uu/seq/Cargo.toml @@ -20,6 +20,7 @@ path = "src/seq.rs" [dependencies] bigdecimal = { workspace = true } clap = { workspace = true } +f128 = { workspace = true, optional = true } num-bigint = { workspace = true } num-traits = { workspace = true } uucore = { workspace = true, features = ["format", "quoting-style"] } diff --git a/src/uu/seq/src/extendedbigdecimal.rs b/src/uu/seq/src/extendedbigdecimal.rs index 4f9a0415218..369ee11a13d 100644 --- a/src/uu/seq/src/extendedbigdecimal.rs +++ b/src/uu/seq/src/extendedbigdecimal.rs @@ -22,7 +22,7 @@ //! ``` use std::cmp::Ordering; use std::fmt::Display; -use std::ops::Add; +use std::ops::{Add, Neg}; use bigdecimal::BigDecimal; use num_traits::Zero; @@ -76,6 +76,157 @@ impl ExtendedBigDecimal { pub fn one() -> Self { Self::BigDecimal(1.into()) } + + pub fn from_f128(value: f128) -> Self { + // this code is adapted from num_bigint::BigDecimal::from_f64, but without the fast path for + // subnormal f128s and all in one function + + let (neg, pow, frac) = match value.classify() { + std::num::FpCategory::Nan => return ExtendedBigDecimal::Nan, + std::num::FpCategory::Infinite => { + return if value.is_sign_negative() { + ExtendedBigDecimal::MinusInfinity + } else { + ExtendedBigDecimal::Infinity + }; + } + std::num::FpCategory::Zero => { + return if value.is_sign_negative() { + ExtendedBigDecimal::MinusZero + } else { + ExtendedBigDecimal::zero() + }; + } + std::num::FpCategory::Subnormal | std::num::FpCategory::Normal => { + /// f128::MANTISSA_DIGITS is 113 (because of the leading 1 in normal floats, but it + /// actually only has 112-bits) + const MANTISSA_BITS: u32 = f128::MANTISSA_DIGITS - 1; + /// The value of the leading one + const MANTISSA_LEADING_ONE: u128 = 1 << MANTISSA_BITS; + /// A mask that is all ones for the matissa bits + const MANTISSA_MASK: u128 = MANTISSA_LEADING_ONE - 1; + /// 15-bit exponent + const EXPONENT_MASK: u128 = (1 << 15) - 1; + + let bits = value.to_bits(); + + // extract mantissa (mask out the rest of the bits and add the leading one) + let frac = (bits & MANTISSA_MASK) + + if value.is_normal() { + MANTISSA_LEADING_ONE + } else { + 0 + }; + + // extract exponent (remove mantissa then mask out the rest of the bits (sign bit)) + let exp = (bits >> MANTISSA_BITS) & EXPONENT_MASK; + + // convert exponent to a power of two (subtract bias and size of mantissa) + let pow = exp as i64 - 16383 - i64::from(MANTISSA_BITS); + + (value.is_sign_negative(), pow, frac) + } + }; + let (frac, scale) = match pow.cmp(&0) { + Ordering::Less => { + let trailing_zeros = std::cmp::min(frac.trailing_zeros(), -pow as u32); + + // Reduce fraction by removing common factors + let reduced_frac = frac >> trailing_zeros; + let reduced_pow = pow + trailing_zeros as i64; + + // We need to scale up by 5^reduced_pow as `scale` is 10^scale instead of 2^scale + // (and 10^scale = 5^scale * 2^scale) + ( + reduced_frac * num_bigint::BigUint::from(5u8).pow(-reduced_pow as u32), + // scale is positive if the power is negative, so flip the sign + -reduced_pow, + ) + } + Ordering::Equal => (num_bigint::BigUint::from(frac), 0), + Ordering::Greater => (frac * num_bigint::BigUint::from(2u32).pow(pow as u32), 0), + }; + + ExtendedBigDecimal::BigDecimal(BigDecimal::new( + num_bigint::BigInt::from_biguint( + if neg { + num_bigint::Sign::Minus + } else { + num_bigint::Sign::Plus + }, + frac, + ), + scale, + )) + } + + pub fn to_f128(&self) -> f128 { + match self { + ExtendedBigDecimal::Infinity => f128::INFINITY, + ExtendedBigDecimal::MinusInfinity => f128::NEG_INFINITY, + ExtendedBigDecimal::MinusZero => -0.0f128, + ExtendedBigDecimal::Nan => f128::NAN, + // Adapted from ::to_f64 + ExtendedBigDecimal::BigDecimal(n) => { + // Descruture BigDecimal + let (n, e) = n.as_bigint_and_exponent(); + let bits = n.bits(); + let (sign, digits) = n.to_u64_digits(); + + // Extract most significant digits (we truncate the rest as they don't affect the + // conversion to f128): + // + // digits are stores in reverse order (e.g. 1u128 << 64 = [0, 1]) + let (mantissa, exponent) = match digits[..] { + // Last two digits + [.., a, b] => { + let m = (u128::from(b) << 64) + u128::from(a); + + // Strip mantissa digits from the exponent: + // + // Assume mantissa = 0b0...0110000 truncated rest + // ^...^^^^^^^ (size = u128::BITS) + // ^...^^^ mantissa + // ^^^^ (size = mantissa.trailing_zeros()) + // ^^^^ ^^^^^...^^^^^^ exponent + // ^...^^^^^^^ ^^^^^...^^^^^^ (size = bits) + // u128::BITS - mantissa.trailing_zeros() = bits(mantissa) + // bits - bits(mantissa) = exponenet + let e = bits - u64::from(u128::BITS - m.trailing_zeros()); + // FIXME: something is wrong here + (m >> m.trailing_zeros(), e) + } + // Single digit + // FIXME: something is wrong here + [a] => ( + u128::from(a) >> a.trailing_zeros(), + a.trailing_zeros().into(), + ), + // Zero (fast path) + [] => return 0.0, + }; + + // Convert to f128 + let val = if exponent > f128::MAX_EXP as u64 { + f128::INFINITY + } else { + // matissa * 2^exponent * 10^(-e) + // ^^^^^^^ big decimal exponent + // ^^^^^^^^^^^^^^^^^^^^ big uint to f128 + (mantissa as f128) + * f128::powi(2.0, exponent as i32) + * f128::powi(10.0, e.neg() as i32) + }; + + // Set sign + if matches!(sign, num_bigint::Sign::Minus) { + -val + } else { + val + } + } + } + } } impl Display for ExtendedBigDecimal { diff --git a/src/uu/seq/src/seq.rs b/src/uu/seq/src/seq.rs index 96ae83ba0a6..ed875b2be24 100644 --- a/src/uu/seq/src/seq.rs +++ b/src/uu/seq/src/seq.rs @@ -1,9 +1,12 @@ +#![feature(f128)] + // This file is part of the uutils coreutils package. // // For the full copyright and license information, please view the LICENSE // file that was distributed with this source code. // spell-checker:ignore (ToDO) extendedbigdecimal numberparse use std::io::{stdout, ErrorKind, Write}; +use std::str::FromStr; use clap::{crate_version, Arg, ArgAction, Command}; use num_traits::{ToPrimitive, Zero}; @@ -31,6 +34,7 @@ const OPT_SEPARATOR: &str = "separator"; const OPT_TERMINATOR: &str = "terminator"; const OPT_EQUAL_WIDTH: &str = "equal-width"; const OPT_FORMAT: &str = "format"; +const OPT_BIGDECIMAL: &str = "bigdecimal"; const ARG_NUMBERS: &str = "numbers"; @@ -39,6 +43,7 @@ struct SeqOptions<'a> { separator: String, terminator: String, equal_width: bool, + bigdecimal: bool, format: Option<&'a str>, } @@ -71,38 +76,37 @@ pub fn uumain(args: impl uucore::Args) -> UResult<()> { .unwrap_or("\n") .to_string(), equal_width: matches.get_flag(OPT_EQUAL_WIDTH), + bigdecimal: matches.get_flag(OPT_BIGDECIMAL), format: matches.get_one::(OPT_FORMAT).map(|s| s.as_str()), }; - let first = if numbers.len() > 1 { - match numbers[0].parse() { - Ok(num) => num, - Err(e) => return Err(SeqError::ParseError(numbers[0].to_string(), e).into()), - } - } else { - PreciseNumber::one() - }; - let increment = if numbers.len() > 2 { - match numbers[1].parse() { - Ok(num) => num, - Err(e) => return Err(SeqError::ParseError(numbers[1].to_string(), e).into()), - } - } else { - PreciseNumber::one() + let to_precise_number = + |n| PreciseNumber::from_str(n).map_err(|err| SeqError::ParseError(n.to_string(), err)); + + let (first, increment, last) = match numbers[..] { + [last] => ( + PreciseNumber::one(), + PreciseNumber::one(), + to_precise_number(last)?, + ), + [first, last] => ( + to_precise_number(first)?, + PreciseNumber::one(), + to_precise_number(last)?, + ), + [first, increment, last] => ( + to_precise_number(first)?, + to_precise_number(increment)?, + to_precise_number(last)?, + ), + // We are guaranteed that `numbers.len()` is greater than zero and at most three because of + // the argument specification in `uu_app()`. + _ => unreachable!(), }; + if increment.is_zero() { - return Err(SeqError::ZeroIncrement(numbers[1].to_string()).into()); + return Err(SeqError::ZeroIncrement(numbers[1].clone()).into()); } - let last: PreciseNumber = { - // We are guaranteed that `numbers.len()` is greater than zero - // and at most three because of the argument specification in - // `uu_app()`. - let n: usize = numbers.len(); - match numbers[n - 1].parse() { - Ok(num) => num, - Err(e) => return Err(SeqError::ParseError(numbers[n - 1].to_string(), e).into()), - } - }; let padding = first .num_integral_digits @@ -119,15 +123,38 @@ pub fn uumain(args: impl uucore::Args) -> UResult<()> { } None => None, }; - let result = print_seq( - (first.number, increment.number, last.number), - largest_dec, - &options.separator, - &options.terminator, - options.equal_width, - padding, - &format, - ); + + let result = if options.bigdecimal { + print_seq( + (first.number, increment.number, last.number), + largest_dec, + &options.separator, + &options.terminator, + options.equal_width, + padding, + &format, + ) + } else { + // TODO: remove once f128::from_str() is available + let first = first.number.to_f128(); + let increment = increment.number.to_f128(); + let last = last.number.to_f128(); + + if increment == 0.0 { + return Err(SeqError::ZeroIncrement(numbers[1].clone()).into()); + } + + print_seq_128( + (first, increment, last), + largest_dec, + &options.separator, + &options.terminator, + options.equal_width, + padding, + &format, + ) + }; + match result { Ok(_) => Ok(()), Err(err) if err.kind() == ErrorKind::BrokenPipe => Ok(()), @@ -173,6 +200,12 @@ pub fn uu_app() -> Command { .action(ArgAction::Append) .num_args(1..=3), ) + .arg( + Arg::new(OPT_BIGDECIMAL) + .long(OPT_BIGDECIMAL) + .help("use bigdecimal instead of f128 (breaks GNU compatibility but is more accurate)") + .action(ArgAction::SetTrue) + ) } fn done_printing(next: &T, increment: &T, last: &T) -> bool { @@ -258,3 +291,60 @@ fn print_seq( stdout.flush()?; Ok(()) } + +/// f128 based code path +fn print_seq_128( + (first, increment, last): (f128, f128, f128), + largest_dec: usize, + separator: &str, + terminator: &str, + pad: bool, + padding: usize, + format: &Option>, +) -> std::io::Result<()> { + let stdout = stdout(); + let mut stdout = stdout.lock(); + let mut value = first; + let padding = if pad { + padding + if largest_dec > 0 { largest_dec + 1 } else { 0 } + } else { + 0 + }; + let mut is_first_iteration = true; + // inlined done_printing as f128 does not implement Zero + while !(increment >= 0.0 && value > last) || (increment < 0.0 && value < last) { + if !is_first_iteration { + write!(stdout, "{separator}")?; + } + // If there was an argument `-f FORMAT`, then use that format + // template instead of the default formatting strategy. + // + // TODO The `printf()` method takes a string as its second + // parameter but we have an `ExtendedBigDecimal`. In order to + // satisfy the signature of the function, we convert the + // `ExtendedBigDecimal` into a string. The `printf()` + // logic will subsequently parse that string into something + // similar to an `ExtendedBigDecimal` again before rendering + // it as a string and ultimately writing to `stdout`. We + // shouldn't have to do so much converting back and forth via + // strings. + match &format { + Some(f) => { + f.fmt(&mut stdout, value as f64)?; + } + None => write!( + &mut stdout, + "{:>0padding$.largest_dec$}", + // TODO: remove once impl Display for f128 is added + ExtendedBigDecimal::from_f128(value) + )?, + } + value += increment; + is_first_iteration = false; + } + if !is_first_iteration { + write!(stdout, "{terminator}")?; + } + stdout.flush()?; + Ok(()) +} diff --git a/tests/by-util/test_seq.rs b/tests/by-util/test_seq.rs index a8bd1fb8359..902ae3fe93b 100644 --- a/tests/by-util/test_seq.rs +++ b/tests/by-util/test_seq.rs @@ -827,3 +827,21 @@ fn test_invalid_format() { .no_stdout() .stderr_contains("format '%g%g' has too many % directives"); } + +// Requires f128 code +//#[test] +//fn test_rejects_not_f128() { +// new_ucmd!() +// .args(&["12e4931", "12e4931"]) +// .fails() +// .no_stdout() +// .stderr_contains("invalid argument"); +//} + +#[test] +fn test_accepts_f128() { + new_ucmd!() + .args(&["11e4931", "11e4931"]) + .succeeds() + .stdout_only("11e+4931\n"); +}