"""Deterministic CRC error patterns, not a storage failure-rate experiment.""" import argparse import hashlib import json import platform import sys import zlib from datetime import datetime, timezone from pathlib import Path POLYNOMIALS = {"crc32": 0x104C11DB7, "crc32c": 0x11EDC6F41} SOURCES = [ "https://www.rfc-editor.org/rfc/rfc3385.html", "https://www.rfc-editor.org/rfc/rfc7143.html#appendix-A.4", "https://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf", "https://docs.python.org/3/library/zlib.html#zlib.crc32", ] def remainder(value, generator): if value < 0 or generator < 2: raise ValueError("nonnegative polynomial and positive-degree generator required") while value.bit_length() >= generator.bit_length(): value ^= generator << (value.bit_length() - generator.bit_length()) return value def multiply(left, right): """Carryless polynomial multiplication over GF(2), not integer multiplication.""" if left < 0 or right < 0: raise ValueError("nonnegative polynomials required") product = 0 while right: if right & 1: product ^= left left <<= 1 right >>= 1 return product def reflected_crc(data, generator): reflected = int(f"{generator & 0xffffffff:032b}"[::-1], 2) crc = 0xffffffff for byte in data: crc ^= byte for _ in range(8): crc = (crc >> 1) ^ (reflected if crc & 1 else 0) return crc ^ 0xffffffff def crc32c(data): return reflected_crc(data, POLYNOMIALS["crc32c"]) def generator_positions(generator, offset): # First polynomial coefficient enters the reflected CRC's LSB-first input. degree = generator.bit_length() - 1 return [offset + bit for bit in range(degree + 1) if generator & (1 << (degree - bit))] def flip(data, positions): if len(set(positions)) != len(positions): raise ValueError("duplicate bit positions") output = bytearray(data) for bit in positions: if not isinstance(bit, int) or not 0 <= bit < 8 * len(output): raise ValueError("bit position outside payload") output[bit // 8] ^= 1 << (bit % 8) return bytes(output) def pattern_polynomial(positions): if not positions: return 0 end = max(positions) return sum(1 << (end - position) for position in positions) def payloads(): return { "zero": bytes(4096), "ff": bytes([255]) * 4096, "ramp": bytes(range(256)) * 16, } def mutation_rows(generators, offsets): rows = [] for label, payload in payloads().items(): before = {"crc32": zlib.crc32(payload), "crc32c": crc32c(payload)} for name, generator in generators: for offset in offsets: positions = generator_positions(generator, offset) mutated = flip(payload, positions) after = {"crc32": zlib.crc32(mutated), "crc32c": crc32c(mutated)} rows.append({ "payload": label, "generator": name, "payloadBytes": len(payload), "startBit": offset, "changedBits": len(positions), "burstSpanBits": generator.bit_length(), "positionsLsbFirst": positions, "originalSha256": hashlib.sha256(payload).hexdigest(), "mutatedSha256": hashlib.sha256(mutated).hexdigest(), "before": {k: f"{v:08x}" for k, v in before.items()}, "after": {k: f"{v:08x}" for k, v in after.items()}, "detected": {k: before[k] != after[k] for k in before}, }) return rows def results(): return mutation_rows(POLYNOMIALS.items(), [0, 1, 7, 2048, 32735]) def joint_results(): product = multiply(POLYNOMIALS["crc32"], POLYNOMIALS["crc32c"]) return mutation_rows([("crc32-and-crc32c", product)], [0, 1, 7, 2048, 32703]) def toy_distances(): # Linear code: distance is the minimum weight of a nonzero codeword. generator = 0b10011 # x^4 + x + 1, full polynomial notation. rows = [] for data_bits in [4, 11, 12]: words = [] for data in range(1, 1 << data_bits): shifted = data << 4 word = shifted ^ remainder(shifted, generator) words.append(word) minimum = min(word.bit_count() for word in words) witness = next(word for word in words if word.bit_count() == minimum) rows.append({ "dataBits": data_bits, "checkBits": 4, "codewordBits": data_bits + 4, "nonzeroCodewordsChecked": len(words), "minimumDistance": minimum, "witnessBinary": f"{witness:0{data_bits + 4}b}", }) return rows def report(): here = Path(__file__).parent return { "schemaVersion": 1, "generatedAt": datetime.now(timezone.utc).isoformat(), "kind": "constructed-error-patterns", "method": "XOR a 33-bit generator-shaped pattern into three 4096-byte payloads at five offsets; recompute unchanged-length CRCs without changing stored reference values.", "bitConvention": "Bit 0 is the least-significant bit of byte 0; subsequent bits follow reflected CRC processing order.", "crcParameters": { "width": 32, "initialRegister": "ffffffff", "reflectInput": True, "reflectOutput": True, "xorOut": "ffffffff", "crc32FullPolynomial": "104c11db7", "crc32cFullPolynomial": "11edc6f41", "valueEncoding": "eight hexadecimal digits of the numerical return value, not wire bytes", }, "environment": {"python": platform.python_version(), "zlib": zlib.ZLIB_RUNTIME_VERSION}, "sourceHashes": {p: hashlib.sha256((here / p).read_bytes()).hexdigest() for p in ["experiment.py", "test_experiment.py"]}, "sources": SOURCES, "rows": results(), "jointDetection": { "fullErrorPolynomialHex": format(multiply(*POLYNOMIALS.values()), "x"), "method": "Carryless product of both generators; XOR its 65-bit pattern into the same payload families while preserving both reference CRCs.", "rows": joint_results(), }, "toyDistance": {"fullGeneratorHex": "13", "rows": toy_distances()}, "limits": [ "Designed counterexamples, not random faults, device measurements or a collision-rate estimate.", "No exhaustive Hamming-distance computation for either 32-bit polynomial.", "Unchanged message length, fixed covered bytes and an unchanged stored CRC reference.", "Burst span is measured in the declared processing-bit order, not inferred physical media adjacency.", "CRC32C implementation is a teaching implementation checked against published vectors, not a production library benchmark.", ], } if __name__ == "__main__": parser = argparse.ArgumentParser() parser.add_argument("--output", type=Path) args = parser.parse_args() output = json.dumps(report(), indent=2) + "\n" if args.output: args.output.write_text(output) else: sys.stdout.write(output)