fork/rust
git clone https://git.julia.blue/fork/rust
f3e1a954d2e
1.41.1
1#!/usr/bin/env python2.7 2 3""" 4Testing dec2flt 5=============== 6These are *really* extensive tests. Expect them to run for hours. Due to the 7nature of the problem (the input is a string of arbitrary length), exhaustive 8testing is not really possible. Instead, there are exhaustive tests for some 9classes of inputs for which that is feasible and a bunch of deterministic and 10random non-exhaustive tests for covering everything else. 11 12The actual tests (generating decimal strings and feeding them to dec2flt) is 13performed by a set of stand-along rust programs. This script compiles, runs, 14and supervises them. The programs report the strings they generate and the 15floating point numbers they converted those strings to, and this script 16checks that the results are correct. 17 18You can run specific tests rather than all of them by giving their names 19(without .rs extension) as command line parameters. 20 21Verification 22------------ 23The tricky part is not generating those inputs but verifying the outputs. 24Comparing with the result of Python's float() does not cut it because 25(and this is apparently undocumented) although Python includes a version of 26Martin Gay's code including the decimal-to-float part, it doesn't actually use 27it for float() (only for round()) instead relying on the system scanf() which 28is not necessarily completely accurate. 29 30Instead, we take the input and compute the true value with bignum arithmetic 31(as a fraction, using the ``fractions`` module). 32 33Given an input string and the corresponding float computed via Rust, simply 34decode the float into f * 2^k (for integers f, k) and the ULP. 35We can now easily compute the error and check if it is within 0.5 ULP as it 36should be. Zero and infinites are handled similarly: 37 38- If the approximation is 0.0, the exact value should be *less or equal* 39 half the smallest denormal float: the smallest denormal floating point 40 number has an odd mantissa (00...001) and thus half of that is rounded 41 to 00...00, i.e., zero. 42- If the approximation is Inf, the exact value should be *greater or equal* 43 to the largest finite float + 0.5 ULP: the largest finite float has an odd 44 mantissa (11...11), so that plus half an ULP is rounded up to the nearest 45 even number, which overflows. 46 47Implementation details 48---------------------- 49This directory contains a set of single-file Rust programs that perform 50tests with a particular class of inputs. Each is compiled and run without 51parameters, outputs (f64, f32, decimal) pairs to verify externally, and 52in any case either exits gracefully or with a panic. 53 54If a test binary writes *anything at all* to stderr or exits with an 55exit code that's not 0, the test fails. 56The output on stdout is treated as (f64, f32, decimal) record, encoded thusly: 57 58- First, the bits of the f64 encoded as an ASCII hex string. 59- Second, the bits of the f32 encoded as an ASCII hex string. 60- Then the corresponding string input, in ASCII 61- The record is terminated with a newline. 62 63Incomplete records are an error. Not-a-Number bit patterns are invalid too. 64 65The tests run serially but the validation for a single test is parallelized 66with ``multiprocessing``. Each test is launched as a subprocess. 67One thread supervises it: Accepts and enqueues records to validate, observe 68stderr, and waits for the process to exit. A set of worker processes perform 69the validation work for the outputs enqueued there. Another thread listens 70for progress updates from the workers. 71 72Known issues 73------------ 74Some errors (e.g., NaN outputs) aren't handled very gracefully. 75Also, if there is an exception or the process is interrupted (at least on 76Windows) the worker processes are leaked and stick around forever. 77They're only a few megabytes each, but still, this script should not be run 78if you aren't prepared to manually kill a lot of orphaned processes. 79""" 80from __future__ import print_function 81import sys 82import os.path 83import time 84import struct 85from fractions import Fraction 86from collections import namedtuple 87from subprocess import Popen, check_call, PIPE 88from glob import glob 89import multiprocessing 90import threading 91import ctypes 92import binascii 93 94try: # Python 3 95 import queue as Queue 96except ImportError: # Python 2 97 import Queue 98 99NUM_WORKERS = 2 100UPDATE_EVERY_N = 50000 101INF = namedtuple('INF', '')() 102NEG_INF = namedtuple('NEG_INF', '')() 103ZERO = namedtuple('ZERO', '')() 104MAILBOX = None # The queue for reporting errors to the main process. 105STDOUT_LOCK = threading.Lock() 106test_name = None 107child_processes = [] 108exit_status = 0 109 110def msg(*args): 111 with STDOUT_LOCK: 112 print("[" + test_name + "]", *args) 113 sys.stdout.flush() 114 115 116def write_errors(): 117 global exit_status 118 f = open("errors.txt", 'w') 119 have_seen_error = False 120 while True: 121 args = MAILBOX.get() 122 if args is None: 123 f.close() 124 break 125 print(*args, file=f) 126 f.flush() 127 if not have_seen_error: 128 have_seen_error = True 129 msg("Something is broken:", *args) 130 msg("Future errors logged to errors.txt") 131 exit_status = 101 132 133 134def rustc(test): 135 rs = test + '.rs' 136 exe = test + '.exe' # hopefully this makes it work on *nix 137 print("compiling", test) 138 sys.stdout.flush() 139 check_call(['rustc', rs, '-o', exe]) 140 141 142def run(test): 143 global test_name 144 test_name = test 145 146 t0 = time.clock() 147 msg("setting up supervisor") 148 exe = test + '.exe' 149 proc = Popen(exe, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE) 150 done = multiprocessing.Value(ctypes.c_bool) 151 queue = multiprocessing.Queue(maxsize=5)#(maxsize=1024) 152 workers = [] 153 for n in range(NUM_WORKERS): 154 worker = multiprocessing.Process(name='Worker-' + str(n + 1), 155 target=init_worker, 156 args=[test, MAILBOX, queue, done]) 157 workers.append(worker) 158 child_processes.append(worker) 159 for worker in workers: 160 worker.start() 161 msg("running test") 162 interact(proc, queue) 163 with done.get_lock(): 164 done.value = True 165 for worker in workers: 166 worker.join() 167 msg("python is done") 168 assert queue.empty(), "did not validate everything" 169 dt = time.clock() - t0 170 msg("took", round(dt, 3), "seconds") 171 172 173def interact(proc, queue): 174 n = 0 175 while proc.poll() is None: 176 line = proc.stdout.readline() 177 if not line: 178 continue 179 assert line.endswith('\n'), "incomplete line: " + repr(line) 180 queue.put(line) 181 n += 1 182 if n % UPDATE_EVERY_N == 0: 183 msg("got", str(n // 1000) + "k", "records") 184 msg("rust is done. exit code:", proc.returncode) 185 rest, stderr = proc.communicate() 186 if stderr: 187 msg("rust stderr output:", stderr) 188 for line in rest.split('\n'): 189 if not line: 190 continue 191 queue.put(line) 192 193 194def main(): 195 global MAILBOX 196 tests = [os.path.splitext(f)[0] for f in glob('*.rs') 197 if not f.startswith('_')] 198 whitelist = sys.argv[1:] 199 if whitelist: 200 tests = [test for test in tests if test in whitelist] 201 if not tests: 202 print("Error: No tests to run") 203 sys.exit(1) 204 # Compile first for quicker feedback 205 for test in tests: 206 rustc(test) 207 # Set up mailbox once for all tests 208 MAILBOX = multiprocessing.Queue() 209 mailman = threading.Thread(target=write_errors) 210 mailman.daemon = True 211 mailman.start() 212 for test in tests: 213 if whitelist and test not in whitelist: 214 continue 215 run(test) 216 MAILBOX.put(None) 217 mailman.join() 218 219 220# ---- Worker thread code ---- 221 222 223POW2 = { e: Fraction(2) ** e for e in range(-1100, 1100) } 224HALF_ULP = { e: (Fraction(2) ** e)/2 for e in range(-1100, 1100) } 225DONE_FLAG = None 226 227 228def send_error_to_supervisor(*args): 229 MAILBOX.put(args) 230 231 232def init_worker(test, mailbox, queue, done): 233 global test_name, MAILBOX, DONE_FLAG 234 test_name = test 235 MAILBOX = mailbox 236 DONE_FLAG = done 237 do_work(queue) 238 239 240def is_done(): 241 with DONE_FLAG.get_lock(): 242 return DONE_FLAG.value 243 244 245def do_work(queue): 246 while True: 247 try: 248 line = queue.get(timeout=0.01) 249 except Queue.Empty: 250 if queue.empty() and is_done(): 251 return 252 else: 253 continue 254 bin64, bin32, text = line.rstrip().split() 255 validate(bin64, bin32, text) 256 257 258def decode_binary64(x): 259 """ 260 Turn a IEEE 754 binary64 into (mantissa, exponent), except 0.0 and 261 infinity (positive and negative), which return ZERO, INF, and NEG_INF 262 respectively. 263 """ 264 x = binascii.unhexlify(x) 265 assert len(x) == 8, repr(x) 266 [bits] = struct.unpack(b'>Q', x) 267 if bits == 0: 268 return ZERO 269 exponent = (bits >> 52) & 0x7FF 270 negative = bits >> 63 271 low_bits = bits & 0xFFFFFFFFFFFFF 272 if exponent == 0: 273 mantissa = low_bits 274 exponent += 1 275 if mantissa == 0: 276 return ZERO 277 elif exponent == 0x7FF: 278 assert low_bits == 0, "NaN" 279 if negative: 280 return NEG_INF 281 else: 282 return INF 283 else: 284 mantissa = low_bits | (1 << 52) 285 exponent -= 1023 + 52 286 if negative: 287 mantissa = -mantissa 288 return (mantissa, exponent) 289 290 291def decode_binary32(x): 292 """ 293 Turn a IEEE 754 binary32 into (mantissa, exponent), except 0.0 and 294 infinity (positive and negative), which return ZERO, INF, and NEG_INF 295 respectively. 296 """ 297 x = binascii.unhexlify(x) 298 assert len(x) == 4, repr(x) 299 [bits] = struct.unpack(b'>I', x) 300 if bits == 0: 301 return ZERO 302 exponent = (bits >> 23) & 0xFF 303 negative = bits >> 31 304 low_bits = bits & 0x7FFFFF 305 if exponent == 0: 306 mantissa = low_bits 307 exponent += 1 308 if mantissa == 0: 309 return ZERO 310 elif exponent == 0xFF: 311 if negative: 312 return NEG_INF 313 else: 314 return INF 315 else: 316 mantissa = low_bits | (1 << 23) 317 exponent -= 127 + 23 318 if negative: 319 mantissa = -mantissa 320 return (mantissa, exponent) 321 322 323MIN_SUBNORMAL_DOUBLE = Fraction(2) ** -1074 324MIN_SUBNORMAL_SINGLE = Fraction(2) ** -149 # XXX unsure 325MAX_DOUBLE = (2 - Fraction(2) ** -52) * (2 ** 1023) 326MAX_SINGLE = (2 - Fraction(2) ** -23) * (2 ** 127) 327MAX_ULP_DOUBLE = 1023 - 52 328MAX_ULP_SINGLE = 127 - 23 329DOUBLE_ZERO_CUTOFF = MIN_SUBNORMAL_DOUBLE / 2 330DOUBLE_INF_CUTOFF = MAX_DOUBLE + 2 ** (MAX_ULP_DOUBLE - 1) 331SINGLE_ZERO_CUTOFF = MIN_SUBNORMAL_SINGLE / 2 332SINGLE_INF_CUTOFF = MAX_SINGLE + 2 ** (MAX_ULP_SINGLE - 1) 333 334def validate(bin64, bin32, text): 335 double = decode_binary64(bin64) 336 single = decode_binary32(bin32) 337 real = Fraction(text) 338 339 if double is ZERO: 340 if real > DOUBLE_ZERO_CUTOFF: 341 record_special_error(text, "f64 zero") 342 elif double is INF: 343 if real < DOUBLE_INF_CUTOFF: 344 record_special_error(text, "f64 inf") 345 elif double is NEG_INF: 346 if -real < DOUBLE_INF_CUTOFF: 347 record_special_error(text, "f64 -inf") 348 elif len(double) == 2: 349 sig, k = double 350 validate_normal(text, real, sig, k, "f64") 351 else: 352 assert 0, "didn't handle binary64" 353 if single is ZERO: 354 if real > SINGLE_ZERO_CUTOFF: 355 record_special_error(text, "f32 zero") 356 elif single is INF: 357 if real < SINGLE_INF_CUTOFF: 358 record_special_error(text, "f32 inf") 359 elif single is NEG_INF: 360 if -real < SINGLE_INF_CUTOFF: 361 record_special_error(text, "f32 -inf") 362 elif len(single) == 2: 363 sig, k = single 364 validate_normal(text, real, sig, k, "f32") 365 else: 366 assert 0, "didn't handle binary32" 367 368def record_special_error(text, descr): 369 send_error_to_supervisor(text.strip(), "wrongly rounded to", descr) 370 371 372def validate_normal(text, real, sig, k, kind): 373 approx = sig * POW2[k] 374 error = abs(approx - real) 375 if error > HALF_ULP[k]: 376 record_normal_error(text, error, k, kind) 377 378 379def record_normal_error(text, error, k, kind): 380 one_ulp = HALF_ULP[k + 1] 381 assert one_ulp == 2 * HALF_ULP[k] 382 relative_error = error / one_ulp 383 text = text.strip() 384 try: 385 err_repr = float(relative_error) 386 except ValueError: 387 err_repr = str(err_repr).replace('/', ' / ') 388 send_error_to_supervisor(err_repr, "ULP error on", text, "(" + kind + ")") 389 390 391if __name__ == '__main__': 392 main()