Changed dec2flt to use the Eisel-Lemire algorithm.

Implementation is based off fast-float-rust, with a few notable changes.

- Some unsafe methods have been removed.
- Safe methods with inherently unsafe functionality have been removed.
- All unsafe functionality is documented and provably safe.
- Extensive documentation has been added for simpler maintenance.
- Inline annotations on internal routines has been removed.
- Fixed Python errors in src/etc/test-float-parse/runtests.py.
- Updated test-float-parse to be a library, to avoid missing rand dependency.
- Added regression tests for #31109 and #31407 in core tests.
- Added regression tests for #31109 and #31407 in ui tests.
- Use the existing slice primitive to simplify shared dec2flt methods
- Remove Miri ignores from dec2flt, due to faster parsing times.

- resolves #85198
- resolves #85214
- resolves #85234
- fixes #31407
- fixes #31109
- fixes #53015
- resolves #68396
- closes https://github.com/aldanor/fast-float-rust/issues/15

19 files changed, 136 insertions, 198 deletions

diff --git a/src/etc/dec2flt_table.py b/src/etc/dec2flt_table.py
index ad2292e8571..aa5188d96c3 100755..100644
--- a/src/etc/dec2flt_table.py
+++ b/src/etc/dec2flt_table.py
@@ -1,141 +1,110 @@
 #!/usr/bin/env python3
 
 """
-Generate powers of ten using William Clinger's ``AlgorithmM`` for use in
+Generate powers of five using Daniel Lemire's ``Eisel-Lemire algorithm`` for use in
 decimal to floating point conversions.
 
 Specifically, computes and outputs (as Rust code) a table of 10^e for some
-range of exponents e. The output is one array of 64 bit significands and
-another array of corresponding base two exponents. The approximations are
-normalized and rounded perfectly, i.e., within 0.5 ULP of the true value.
+range of exponents e. The output is one array of 128 bit significands.
+The base two exponents can be inferred using a logarithmic slope
+of the decimal exponent. The approximations are normalized and rounded perfectly,
+i.e., within 0.5 ULP of the true value.
 
-The representation ([u64], [i16]) instead of the more natural [(u64, i16)]
-is used because (u64, i16) has a ton of padding which would make the table
-even larger, and it's already uncomfortably large (6 KiB).
+Adapted from Daniel Lemire's fast_float ``table_generation.py``,
+available here: <https://github.com/fastfloat/fast_float/blob/main/script/table_generation.py>.
 """
 from __future__ import print_function
-from math import ceil, log
+from math import ceil, floor, log, log2
 from fractions import Fraction
-from collections import namedtuple
-
-
-N = 64  # Size of the significand field in bits
-MIN_SIG = 2 ** (N - 1)
-MAX_SIG = (2 ** N) - 1
-
-# Hand-rolled fp representation without arithmetic or any other operations.
-# The significand is normalized and always N bit, but the exponent is
-# unrestricted in range.
-Fp = namedtuple('Fp', 'sig exp')
-
-
-def algorithm_m(f, e):
-    assert f > 0
-    if e < 0:
-        u = f
-        v = 10 ** abs(e)
-    else:
-        u = f * 10 ** e
-        v = 1
-    k = 0
-    x = u // v
-    while True:
-        if x < MIN_SIG:
-            u <<= 1
-            k -= 1
-        elif x >= MAX_SIG:
-            v <<= 1
-            k += 1
-        else:
-            break
-        x = u // v
-    return ratio_to_float(u, v, k)
-
-
-def ratio_to_float(u, v, k):
-    q, r = divmod(u, v)
-    v_r = v - r
-    z = Fp(q, k)
-    if r < v_r:
-        return z
-    elif r > v_r:
-        return next_float(z)
-    elif q % 2 == 0:
-        return z
-    else:
-        return next_float(z)
-
-
-def next_float(z):
-    if z.sig == MAX_SIG:
-        return Fp(MIN_SIG, z.exp + 1)
-    else:
-        return Fp(z.sig + 1, z.exp)
-
-
-def error(f, e, z):
-    decimal = f * Fraction(10) ** e
-    binary = z.sig * Fraction(2) ** z.exp
-    abs_err = abs(decimal - binary)
-    # The unit in the last place has value z.exp
-    ulp_err = abs_err / Fraction(2) ** z.exp
-    return float(ulp_err)
-
+from collections import deque
 
 HEADER = """
-//! Tables of approximations of powers of ten.
+//! Pre-computed tables powers-of-5 for extended-precision representations.
+//!
+//! These tables enable fast scaling of the significant digits
+//! of a float to the decimal exponent, with minimal rounding
+//! errors, in a 128 or 192-bit representation.
+//!
 //! DO NOT MODIFY: Generated by `src/etc/dec2flt_table.py`
 """
 
+STATIC_WARNING = """
+// Use static to avoid long compile times: Rust compiler errors
+// can have the entire table compiled multiple times, and then
+// emit code multiple times, even if it's stripped out in
+// the final binary.
+"""
 
 def main():
+    min_exp = minimum_exponent(10)
+    max_exp = maximum_exponent(10)
+    bias = -minimum_exponent(5)
+
     print(HEADER.strip())
     print()
-    print_proper_powers()
-    print()
-    print_short_powers(32, 24)
+    print('pub const SMALLEST_POWER_OF_FIVE: i32 = {};'.format(min_exp))
+    print('pub const LARGEST_POWER_OF_FIVE: i32 = {};'.format(max_exp))
+    print('pub const N_POWERS_OF_FIVE: usize = ', end='')
+    print('(LARGEST_POWER_OF_FIVE - SMALLEST_POWER_OF_FIVE + 1) as usize;')
     print()
-    print_short_powers(64, 53)
+    print_proper_powers(min_exp, max_exp, bias)
+
+
+def minimum_exponent(base):
+    return ceil(log(5e-324, base) - log(0xFFFFFFFFFFFFFFFF, base))
+
 
+def maximum_exponent(base):
+    return floor(log(1.7976931348623157e+308, base))
 
-def print_proper_powers():
-    MIN_E = -305
-    MAX_E = 305
-    e_range = range(MIN_E, MAX_E+1)
+
+def print_proper_powers(min_exp, max_exp, bias):
+    powers = deque()
+
+    # Add negative exponents.
+    # 2^(2b)/(5^−q) with b=64 + int(math.ceil(log2(5^−q)))
     powers = []
-    for e in e_range:
-        z = algorithm_m(1, e)
-        err = error(1, e, z)
-        assert err < 0.5
-        powers.append(z)
-    print("pub const MIN_E: i16 = {};".format(MIN_E))
-    print("pub const MAX_E: i16 = {};".format(MAX_E))
-    print()
-    print("#[rustfmt::skip]")
-    typ = "([u64; {0}], [i16; {0}])".format(len(powers))
-    print("pub static POWERS: ", typ, " = (", sep='')
-    print("    [")
-    for z in powers:
-        print("        0x{:x},".format(z.sig))
-    print("    ],")
-    print("    [")
-    for z in powers:
-        print("        {},".format(z.exp))
-    print("    ],")
-    print(");")
-
-
-def print_short_powers(num_bits, significand_size):
-    max_sig = 2**significand_size - 1
-    # The fast path bails out for exponents >= ceil(log5(max_sig))
-    max_e = int(ceil(log(max_sig, 5)))
-    e_range = range(max_e)
-    typ = "[f{}; {}]".format(num_bits, len(e_range))
-    print("#[rustfmt::skip]")
-    print("pub const F", num_bits, "_SHORT_POWERS: ", typ, " = [", sep='')
-    for e in e_range:
-        print("    1e{},".format(e))
-    print("];")
+    for q in range(min_exp, 0):
+        power5 = 5 ** -q
+        z = 0
+        while (1 << z) < power5:
+            z += 1
+        if q >= -27:
+            b = z + 127
+            c = 2 ** b // power5 + 1
+            powers.append((c, q))
+        else:
+            b = 2 * z + 2 * 64
+            c = 2 ** b // power5 + 1
+            # truncate
+            while c >= (1<<128):
+                c //= 2
+            powers.append((c, q))
+
+    # Add positive exponents
+    for q in range(0, max_exp + 1):
+        power5 = 5 ** q
+        # move the most significant bit in position
+        while power5 < (1<<127):
+            power5 *= 2
+        # *truncate*
+        while power5 >= (1<<128):
+            power5 //= 2
+        powers.append((power5, q))
+
+    # Print the powers.
+    print(STATIC_WARNING.strip())
+    print('#[rustfmt::skip]')
+    typ = '[(u64, u64); N_POWERS_OF_FIVE]'
+    print('pub static POWER_OF_FIVE_128: {} = ['.format(typ))
+    lo_mask = (1 << 64) - 1
+    for c, exp in powers:
+        hi = '0x{:x}'.format(c // (1 << 64))
+        lo = '0x{:x}'.format(c % (1 << 64))
+        value = '    ({}, {}), '.format(hi, lo)
+        comment = '// {}^{}'.format(5, exp)
+        print(value.ljust(46, ' ') + comment)
+    print('];')
 
 
 if __name__ == '__main__':
diff --git a/src/etc/test-float-parse/Cargo.toml b/src/etc/test-float-parse/Cargo.toml
new file mode 100644
index 00000000000..8226e815c2c
--- /dev/null
+++ b/src/etc/test-float-parse/Cargo.toml
@@ -0,0 +1,13 @@
+[package]
+name = "test-float-parse"
+version = "0.1.0"
+edition = "2018"
+publish = false
+
+[workspace]
+
+[dependencies]
+rand = "0.4"
+
+[lib]
+name = "test_float_parse"
diff --git a/src/etc/test-float-parse/runtests.py b/src/etc/test-float-parse/runtests.py
index 218552a4597..cf7279534dc 100644
--- a/src/etc/test-float-parse/runtests.py
+++ b/src/etc/test-float-parse/runtests.py
@@ -131,22 +131,20 @@ def write_errors():
             exit_status = 101
 
 
-def rustc(test):
-    rs = test + '.rs'
-    exe = test + '.exe'  # hopefully this makes it work on *nix
-    print("compiling", test)
+def cargo():
+    print("compiling tests")
     sys.stdout.flush()
-    check_call(['rustc', rs, '-o', exe])
+    check_call(['cargo', 'build', '--release'])
 
 
 def run(test):
     global test_name
     test_name = test
 
-    t0 = time.clock()
+    t0 = time.perf_counter()
     msg("setting up supervisor")
-    exe = test + '.exe'
-    proc = Popen(exe, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE)
+    command = ['cargo', 'run', '--bin', test, '--release']
+    proc = Popen(command, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE)
     done = multiprocessing.Value(ctypes.c_bool)
     queue = multiprocessing.Queue(maxsize=5)#(maxsize=1024)
     workers = []
@@ -166,7 +164,7 @@ def run(test):
         worker.join()
     msg("python is done")
     assert queue.empty(), "did not validate everything"
-    dt = time.clock() - t0
+    dt = time.perf_counter() - t0
     msg("took", round(dt, 3), "seconds")
 
 
@@ -176,7 +174,7 @@ def interact(proc, queue):
         line = proc.stdout.readline()
         if not line:
             continue
-        assert line.endswith('\n'), "incomplete line: " + repr(line)
+        assert line.endswith(b'\n'), "incomplete line: " + repr(line)
         queue.put(line)
         n += 1
         if n % UPDATE_EVERY_N == 0:
@@ -185,7 +183,7 @@ def interact(proc, queue):
     rest, stderr = proc.communicate()
     if stderr:
         msg("rust stderr output:", stderr)
-    for line in rest.split('\n'):
+    for line in rest.split(b'\n'):
         if not line:
             continue
         queue.put(line)
@@ -193,18 +191,19 @@ def interact(proc, queue):
 
 def main():
     global MAILBOX
-    all_tests = [os.path.splitext(f)[0] for f in glob('*.rs') if not f.startswith('_')]
+    files = glob('src/bin/*.rs')
+    basenames = [os.path.basename(i) for i in files]
+    all_tests = [os.path.splitext(f)[0] for f in basenames if not f.startswith('_')]
     args = sys.argv[1:]
     if args:
         tests = [test for test in all_tests if test in args]
-    else
+    else:
         tests = all_tests
     if not tests:
         print("Error: No tests to run")
         sys.exit(1)
     # Compile first for quicker feedback
-    for test in tests:
-        rustc(test)
+    cargo()
     # Set up mailbox once for all tests
     MAILBOX = multiprocessing.Queue()
     mailman = threading.Thread(target=write_errors)
@@ -251,7 +250,7 @@ def do_work(queue):
             else:
                 continue
         bin64, bin32, text = line.rstrip().split()
-        validate(bin64, bin32, text)
+        validate(bin64, bin32, text.decode('utf-8'))
 
 
 def decode_binary64(x):
@@ -331,7 +330,11 @@ SINGLE_ZERO_CUTOFF = MIN_SUBNORMAL_SINGLE / 2
 SINGLE_INF_CUTOFF = MAX_SINGLE + 2 ** (MAX_ULP_SINGLE - 1)
 
 def validate(bin64, bin32, text):
-    double = decode_binary64(bin64)
+    try:
+        double = decode_binary64(bin64)
+    except AssertionError:
+        print(bin64, bin32, text)
+        raise
     single = decode_binary32(bin32)
     real = Fraction(text)
 
diff --git a/src/etc/test-float-parse/few-ones.rs b/src/etc/test-float-parse/src/bin/few-ones.rs
index 2d82918aabb..6bb406a5947 100644
--- a/src/etc/test-float-parse/few-ones.rs
+++ b/src/etc/test-float-parse/src/bin/few-ones.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     let mut pow = vec![];
diff --git a/src/etc/test-float-parse/huge-pow10.rs b/src/etc/test-float-parse/src/bin/huge-pow10.rs
index 9a16d9c6028..722a24ffcd8 100644
--- a/src/etc/test-float-parse/huge-pow10.rs
+++ b/src/etc/test-float-parse/src/bin/huge-pow10.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     for e in 300..310 {
diff --git a/src/etc/test-float-parse/long-fractions.rs b/src/etc/test-float-parse/src/bin/long-fractions.rs
index 60cf85c4a60..c715bc1ac2b 100644
--- a/src/etc/test-float-parse/long-fractions.rs
+++ b/src/etc/test-float-parse/src/bin/long-fractions.rs
@@ -1,7 +1,5 @@
-mod _common;
-
-use _common::validate;
 use std::char;
+use test_float_parse::validate;
 
 fn main() {
     for n in 0..10 {
diff --git a/src/etc/test-float-parse/many-digits.rs b/src/etc/test-float-parse/src/bin/many-digits.rs
index 599986e20dd..ba166fd5607 100644
--- a/src/etc/test-float-parse/many-digits.rs
+++ b/src/etc/test-float-parse/src/bin/many-digits.rs
@@ -1,11 +1,9 @@
 extern crate rand;
 
-mod _common;
-
-use _common::{validate, SEED};
 use rand::distributions::{Range, Sample};
 use rand::{IsaacRng, Rng, SeedableRng};
 use std::char;
+use test_float_parse::{validate, SEED};
 
 fn main() {
     let mut rnd = IsaacRng::from_seed(&SEED);
diff --git a/src/etc/test-float-parse/rand-f64.rs b/src/etc/test-float-parse/src/bin/rand-f64.rs
index 39ad63945cd..6991e8be15e 100644
--- a/src/etc/test-float-parse/rand-f64.rs
+++ b/src/etc/test-float-parse/src/bin/rand-f64.rs
@@ -1,10 +1,8 @@
 extern crate rand;
 
-mod _common;
-
-use _common::{validate, SEED};
 use rand::{IsaacRng, Rng, SeedableRng};
 use std::mem::transmute;
+use test_float_parse::{validate, SEED};
 
 fn main() {
     let mut rnd = IsaacRng::from_seed(&SEED);
diff --git a/src/etc/test-float-parse/short-decimals.rs b/src/etc/test-float-parse/src/bin/short-decimals.rs
index 8b9b6f78ae3..49084eb35e8 100644
--- a/src/etc/test-float-parse/short-decimals.rs
+++ b/src/etc/test-float-parse/src/bin/short-decimals.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     // Skip e = 0 because small-u32 already does those.
diff --git a/src/etc/test-float-parse/subnorm.rs b/src/etc/test-float-parse/src/bin/subnorm.rs
index ba68d31e4ed..ac88747eacd 100644
--- a/src/etc/test-float-parse/subnorm.rs
+++ b/src/etc/test-float-parse/src/bin/subnorm.rs
@@ -1,7 +1,5 @@
-mod _common;
-
-use _common::validate;
 use std::mem::transmute;
+use test_float_parse::validate;
 
 fn main() {
     for bits in 0u32..(1 << 21) {
diff --git a/src/etc/test-float-parse/tiny-pow10.rs b/src/etc/test-float-parse/src/bin/tiny-pow10.rs
index 43fad5b49ee..fb6ba166380 100644
--- a/src/etc/test-float-parse/tiny-pow10.rs
+++ b/src/etc/test-float-parse/src/bin/tiny-pow10.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     for e in 301..327 {
diff --git a/src/etc/test-float-parse/u32-small.rs b/src/etc/test-float-parse/src/bin/u32-small.rs
index 3ae62425adf..5ec9d1eea5f 100644
--- a/src/etc/test-float-parse/u32-small.rs
+++ b/src/etc/test-float-parse/src/bin/u32-small.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     for i in 0..(1 << 19) {
diff --git a/src/etc/test-float-parse/u64-pow2.rs b/src/etc/test-float-parse/src/bin/u64-pow2.rs
index 7e67e2b1246..984e49200cd 100644
--- a/src/etc/test-float-parse/u64-pow2.rs
+++ b/src/etc/test-float-parse/src/bin/u64-pow2.rs
@@ -1,6 +1,4 @@
-mod _common;
-
-use _common::validate;
+use test_float_parse::validate;
 
 fn main() {
     for exp in 19..64 {
diff --git a/src/etc/test-float-parse/_common.rs b/src/etc/test-float-parse/src/lib.rs
index 9cbad5486b4..9cbad5486b4 100644
--- a/src/etc/test-float-parse/_common.rs
+++ b/src/etc/test-float-parse/src/lib.rs
diff --git a/src/test/ui/issues/issue-31109.rs b/src/test/ui/issues/issue-31109.rs
deleted file mode 100644
index 37c23905819..00000000000
--- a/src/test/ui/issues/issue-31109.rs
+++ /dev/null
@@ -1,6 +0,0 @@
-fn main() {
-    // FIXME(#31407) this error should go away, but in the meantime we test that it
-    // is accompanied by a somewhat useful error message.
-    let _: f64 = 1234567890123456789012345678901234567890e-340;
-    //~^ ERROR could not evaluate float literal (see issue #31407)
-}
diff --git a/src/test/ui/issues/issue-31109.stderr b/src/test/ui/issues/issue-31109.stderr
deleted file mode 100644
index d354f61a501..00000000000
--- a/src/test/ui/issues/issue-31109.stderr
+++ /dev/null
@@ -1,8 +0,0 @@
-error: could not evaluate float literal (see issue #31407)
-  --> $DIR/issue-31109.rs:4:18
-   |
-LL |     let _: f64 = 1234567890123456789012345678901234567890e-340;
-   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-error: aborting due to previous error
-
diff --git a/src/test/ui/parser/float-literals.rs b/src/test/ui/parser/float-literals.rs
new file mode 100644
index 00000000000..1e9319fd27d
--- /dev/null
+++ b/src/test/ui/parser/float-literals.rs
@@ -0,0 +1,9 @@
+// build-pass
+// ignore-tidy-linelength
+// Regression test for #31109 and #31407.
+
+pub fn main() {
+    let _: f64 = 0.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333;
+
+    let _: f64 = 1234567890123456789012345678901234567890e-340;
+}
diff --git a/src/test/ui/pattern/issue-68396-let-float-bug.rs b/src/test/ui/pattern/issue-68396-let-float-bug.rs
deleted file mode 100644
index afc599a4b22..00000000000
--- a/src/test/ui/pattern/issue-68396-let-float-bug.rs
+++ /dev/null
@@ -1,7 +0,0 @@
-fn main() {
-    let 1234567890123456789012345678901234567890e-340: f64 = 0.0;
-    //~^ ERROR could not evaluate float literal (see issue #31407)
-
-    fn param(1234567890123456789012345678901234567890e-340: f64) {}
-    //~^ ERROR could not evaluate float literal (see issue #31407)
-}
diff --git a/src/test/ui/pattern/issue-68396-let-float-bug.stderr b/src/test/ui/pattern/issue-68396-let-float-bug.stderr
deleted file mode 100644
index 618aa4b5021..00000000000
--- a/src/test/ui/pattern/issue-68396-let-float-bug.stderr
+++ /dev/null
@@ -1,15 +0,0 @@
-error[E0080]: could not evaluate float literal (see issue #31407)
-  --> $DIR/issue-68396-let-float-bug.rs:2:9
-   |
-LL |     let 1234567890123456789012345678901234567890e-340: f64 = 0.0;
-   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-error[E0080]: could not evaluate float literal (see issue #31407)
-  --> $DIR/issue-68396-let-float-bug.rs:5:14
-   |
-LL |     fn param(1234567890123456789012345678901234567890e-340: f64) {}
-   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-error: aborting due to 2 previous errors
-
-For more information about this error, try `rustc --explain E0080`.