import itertools import hashlib import json from pathlib import Path import unittest import zlib from experiment import ( POLYNOMIALS, crc32c, flip, generator_positions, joint_results, multiply, pattern_polynomial, payloads, reflected_crc, remainder, results, toy_distances, ) class CRCExperimentTests(unittest.TestCase): def test_published_iscsi_vectors(self): # RFC 7143 A.4 gives wire bytes, little-endian relative to these integers. vectors = [ (bytes(32), "aa36918a"), (bytes([255]) * 32, "43aba862"), (bytes(range(32)), "4e79dd46"), (bytes(range(31, -1, -1)), "5cdb3f11"), (bytes.fromhex( "01c00000 00000000 00000000 00000000 14000000 00000400 " "00000014 00000018 28000000 00000000 02000000 00000000" ), "563a96d9"), ] for data, wire in vectors: self.assertEqual(crc32c(data).to_bytes(4, "little").hex(), wire) def test_crc32_against_independent_zlib(self): for size in [0, 1, 4, 32, 257, 4096]: data = bytes((i * 37 + 11) % 256 for i in range(size)) self.assertEqual(reflected_crc(data, POLYNOMIALS["crc32"]), zlib.crc32(data)) self.assertEqual(zlib.crc32(b"123456789"), 0xcbf43926) def test_construction_and_cross_detection(self): rows = results() self.assertEqual(len(rows), 30) for row in rows: self.assertFalse(row["detected"][row["generator"]]) other = "crc32c" if row["generator"] == "crc32" else "crc32" self.assertTrue(row["detected"][other]) self.assertNotEqual(row["originalSha256"], row["mutatedSha256"]) self.assertEqual(row["changedBits"], 15 if row["generator"] == "crc32" else 18) positions = row["positionsLsbFirst"] self.assertEqual(max(positions) - min(positions) + 1, 33) self.assertEqual(pattern_polynomial(positions), POLYNOMIALS[row["generator"]]) def test_divisibility_independent_of_crc_engine(self): for generator in POLYNOMIALS.values(): for shift in [0, 1, 32, 300, 4096]: self.assertEqual(remainder(generator << shift, generator), 0) other = next(g for g in POLYNOMIALS.values() if g != generator) self.assertNotEqual(remainder(other, generator), 0) def test_all_short_bursts_algebraically(self): # Exhaustive only through span 12, at four selected algebraic shifts. for width in range(1, 13): interiors = range(1 if width == 1 else 1 << (width - 2)) for middle in interiors: pattern = 1 if width == 1 else (1 << (width - 1)) | (middle << 1) | 1 for shift in [0, 1, 31, 32736]: for generator in POLYNOMIALS.values(): self.assertNotEqual(remainder(pattern << shift, generator), 0) def test_single_flip_and_32_bit_span_controls(self): for data in payloads().values(): for positions in [[0], [32767], [0, 31], list(range(32)), [32736, 32767]]: changed = flip(data, positions) self.assertNotEqual(zlib.crc32(data), zlib.crc32(changed)) self.assertNotEqual(crc32c(data), crc32c(changed)) def test_odd_weight_factor_and_finite_controls(self): self.assertEqual(remainder(POLYNOMIALS["crc32c"], 0b11), 0) self.assertNotEqual(remainder(POLYNOMIALS["crc32"], 0b11), 0) for weight in [1, 3, 5]: for positions in itertools.combinations(range(12), weight): self.assertNotEqual(remainder(pattern_polynomial(positions), POLYNOMIALS["crc32c"]), 0) def test_joint_pattern_independent_convolution(self): left, right = POLYNOMIALS.values() coefficients = {} for i in range(left.bit_length()): for j in range(right.bit_length()): if (left >> i) & (right >> j) & 1: coefficients[i + j] = coefficients.get(i + j, 0) ^ 1 expected = sum(bit << power for power, bit in coefficients.items()) self.assertEqual(expected, 0x11a6ec5c893b4ed77) self.assertEqual(multiply(left, right), expected) self.assertEqual(multiply(right, left), expected) self.assertNotEqual(left * right, expected) for generator in POLYNOMIALS.values(): self.assertEqual(remainder(expected, generator), 0) rows = joint_results() self.assertEqual(len(rows), 15) for row in rows: self.assertEqual(row["changedBits"], 36) self.assertEqual(row["burstSpanBits"], 65) self.assertEqual(row["before"], row["after"]) self.assertEqual(row["detected"], {"crc32": False, "crc32c": False}) self.assertNotEqual(row["originalSha256"], row["mutatedSha256"]) self.assertEqual(pattern_polynomial(row["positionsLsbFirst"]), expected) self.assertEqual(max(rows[-1]["positionsLsbFirst"]), 32767) def test_multiplication_boundaries(self): self.assertEqual(multiply(0, POLYNOMIALS["crc32"]), 0) self.assertEqual(multiply(POLYNOMIALS["crc32c"], 1), POLYNOMIALS["crc32c"]) for operands in [(-1, 1), (1, -1)]: with self.assertRaises(ValueError): multiply(*operands) def test_exact_small_code_distances(self): for row in toy_distances(): width = row["codewordBits"] # Independently enumerate error masks, not encoded input words. undetected = [error for error in range(1, 1 << width) if remainder(error, 0x13) == 0] self.assertEqual(len(undetected), row["nonzeroCodewordsChecked"]) self.assertEqual(min(error.bit_count() for error in undetected), row["minimumDistance"]) self.assertEqual(row["minimumDistance"], 2 if width == 16 else 3) def test_published_results_and_source_hashes(self): root = Path(__file__).parent saved = json.loads((root / "results.json").read_text()) self.assertEqual(saved["rows"], results()) self.assertEqual(saved["jointDetection"]["rows"], joint_results()) self.assertEqual(saved["jointDetection"]["fullErrorPolynomialHex"], "11a6ec5c893b4ed77") self.assertEqual(saved["toyDistance"]["rows"], toy_distances()) for filename, expected in saved["sourceHashes"].items(): self.assertEqual(hashlib.sha256((root / filename).read_bytes()).hexdigest(), expected) def test_boundary_and_input_validation(self): self.assertEqual(max(generator_positions(POLYNOMIALS["crc32"], 32735)), 32767) for positions in [[-1], [32768], [0, 0]]: with self.assertRaises(ValueError): flip(bytes(4096), positions) if __name__ == "__main__": unittest.main()