"""Compile and compare the four executable implementations.""" from collections import Counter from concurrent.futures import ThreadPoolExecutor from hashlib import sha256 from pathlib import Path from shutil import which from struct import pack from subprocess import run from tempfile import TemporaryDirectory import platform import sys ROOT = Path(__file__).resolve().parent Q = 339949771344778 S = 10**15 STEPS = 23 DOMAIN = 32768 PACKET_BYTES = 6 TRACE_FORMAT = f"<{STEPS + 1}H" RECORD_BYTES = PACKET_BYTES + 2 * (STEPS + 1) def call(command, *, check=True): return run(command, cwd=ROOT, capture_output=True, check=check, timeout=90) def require(condition, message): if not condition: raise RuntimeError(message) def reference_corpus(): """Enumerate fibers and derive the rank by counting earlier preimages.""" image = [Q * d // S for d in range(DOMAIN)] rank = [] counts = Counter() for y in image: rank.append(counts[y]) counts[y] += 1 require(max(counts.values()) == 3, "unexpected maximum fiber size") records = bytearray() for d in range(DOMAIN): word = 0 trace = [d] for i in range(STEPS): word += rank[d] * 4**i d = image[d] trace.append(d) require(d == 0, "reference terminal is nonzero") records.extend(word.to_bytes(PACKET_BYTES, "little")) records.extend(pack(TRACE_FORMAT, *trace)) two_candidates = next(d for d, y in enumerate(image) if counts[y] == 2) return bytes(records), two_candidates def packet_at(corpus, seed): start = RECORD_BYTES * seed return corpus[start : start + PACKET_BYTES] def expected_trace(seed): states = [seed] for _ in range(STEPS): states.append(Q * states[-1] // S) return (" ".join(map(str, states)) + "\n").encode("ascii") def compile_programs(build): javac = [which("javac")] if which("javac") else [ "java", "-m", "jdk.compiler/com.sun.tools.javac.Main" ] call([*javac, "-Xlint:all", "-d", build, "Omega.java"]) rust_executable = str(Path(build) / "omega-rust") call([ "rustc", "--edition=2021", "-D", "warnings", "-C", "overflow-checks=yes", "-O", "omega.rs", "-o", rust_executable ]) return { "Java": ["java", "-Xmx256m", "-cp", build, "Omega"], "Python": [sys.executable, "omega.py"], "Rust": [rust_executable], "Julia": ["julia", "--startup-file=no", "--history-file=no", "omega.jl"], } def check_program(name, command, reference, fixtures, invalid): coefficient = call([*command, "constants"]) require(coefficient.stdout == f"{Q}\n".encode(), f"{name}: coefficient mismatch") batch = call([*command, "batch"]) require(batch.stdout == reference, f"{name}: packet or recovered-state bytes mismatch") require(not batch.stderr, f"{name}: unexpected batch diagnostics") for seed, packet in fixtures.items(): encoded = call([*command, "encode", str(seed)]) require(encoded.stdout.strip() == packet.hex().encode(), f"{name}: encode {seed}") decoded = call([*command, "decode", packet.hex()]) require(decoded.stdout == expected_trace(seed), f"{name}: decode {seed}") for kind, packet in invalid.items(): result = call([*command, "decode", packet.hex()], check=False) require(result.returncode != 0 and not result.stdout, f"{name}: accepted {kind}") return ( f"{name}: derived Q={Q}, {DOMAIN} histories recovered, " f"{len(fixtures)} wire fixtures matched, {len(invalid)} malformed packets rejected" ) def main(): corpus, two_candidates = reference_corpus() fixtures = {seed: packet_at(corpus, seed) for seed in (0, 398, 399, 400, DOMAIN - 1)} require(fixtures[399].hex() == "090600000000", "unexpected 399 fixture") sample = fixtures[399] two_packet = packet_at(corpus, two_candidates) invalid = { "short packet": sample[:-1], "nonzero padding": sample[:-1] + bytes([sample[-1] | 0x40]), "reserved rank 3": bytes([sample[0] | 3]) + sample[1:], "rank 2 in a two-element fiber": bytes([(two_packet[0] & ~3) | 2]) + two_packet[1:], } print(f"Python {platform.python_version()}") for executable in ("java", "rustc", "julia"): print(call([executable, "--version"]).stdout.decode().splitlines()[0]) with TemporaryDirectory(prefix="omega-verify-") as build: programs = compile_programs(build) with ThreadPoolExecutor(max_workers=len(programs)) as pool: checks = [ pool.submit(check_program, name, command, corpus, fixtures, invalid) for name, command in programs.items() ] for check in checks: print(check.result()) print(f"Transitions per implementation: {DOMAIN * STEPS}") packets = b"".join(packet_at(corpus, seed) for seed in range(DOMAIN)) print(f"Identical packet corpus: {len(packets)} bytes") print(f"Packet corpus SHA-256: {sha256(packets).hexdigest()}") print(f"Identical packet and recovered-state corpus: {len(corpus)} bytes") print(f"Recovered states per implementation: {DOMAIN * (STEPS + 1)}") print(f"Packet and recovered-state corpus SHA-256: {sha256(corpus).hexdigest()}") print(f"399 packet: {fixtures[399].hex()}") print(f"399 decoded: {expected_trace(399).decode().strip()}") print("PASS") if __name__ == "__main__": try: main() except Exception as error: if getattr(error, "stderr", None): sys.stderr.buffer.write(error.stderr) sys.exit(str(error))