Quines

[resilar]

Implement a feature to calculate CRC quines. For example:

$ printf "\xcc\x4f\xbb\x6a" | ./crchack -
cc4fbb6a
$ printf "\xff\xff\xff\xff" | ./crchack -
ffffffff
$ printf 'foo\x81\xc8\x73\xa7bar' | ./crchack -
81c873a7
$ printf 'foo\xe0\x2d\x7a\x0bbar' | ./crchack -
e02d7a0b

sagemath proof of concept:

def binvec(x, w=32): return vector(GF(2), x.digits(2, padto=w))

def crc32(msg):
    crc = 0xffffffff
    for c in msg.encode() if isinstance(msg, str) else msg:
        crc ^^= c & 0xff
        for _ in range(8):
            crc = (crc >> 1) ^^ 0xedb88320 if crc & 1 else crc >> 1
    return crc ^^ 0xffffffff

def h(x): return crc32(int(x).to_bytes(4, 'big'))
h0 = h(0) # crc32(b'\x00\x00\x00\x00')
diff = [h0 ^^ h(2^x) for x in range(32)]
A = matrix(GF(2), 32, [x.digits(2, padto=32) for x in diff]).transpose()

# Find a quine
sol = (A - identity_matrix(GF(2), 32)).solve_right(binvec(h0, 32))
quine = Integer(sol.list(), base=2)
print(hex(quine), quine == h(quine))
# 0xcc4fbb6a True

# Calculate all quines
def quines(h, w=32):
    def gf2vec(x): return vector(GF(2), x.digits(2, padto=w))
    h0 = h(0)
    diff = [h0 ^^ h(2^x) for x in range(w)]
    A = matrix(GF(2), w, [x.digits(2, padto=w) for x in diff]).transpose()
    Id = identity_matrix(GF(2), w)
    try: sol = (A - Id).solve_right(gf2vec(h0))
    except: return # No solutions
    for kernel in (A - Id).right_kernel():
        yield Integer((sol + kernel).list(), base=2)

def h(x, prefix=b'', suffix=b''):
    return crc32(prefix + int(x).to_bytes(4, 'big') + suffix)
for quine in quines(h, 32): print(hex(quine), quine == h(quine))
# 0xcc4fbb6a True
# 0xffffffff True

H = lambda x: h(x, b'foo', b'bar')
for quine in quines(H, 32):
    print(hex(quine), quine == H(quine))
# 0x81c873a7 True
# 0xe02d7a0b True

[resilar]

Note that a quine does not necessarily exist for a specific input and CRC function. However, some standardized CRC functions have an unique quine for every input (for other CRC functions, some inputs have multiple valid quines while other inputs have none). CRC functions that have unique quine for any input message include the following:

CRC-3/GSM -w3 -p3 -x7
CRC-3/ROHC -w3 -p3 -i7 -rR
CRC-4/G-704 -w4 -p3 -rR
CRC-4/INTERLAKEN -w4 -p3 -if -xf
CRC-5/EPC-C1G2 -w5 -p09 -i09
CRC-5/USB -w5 -p05 -i1f -rR -x1f
CRC-6/CDMA2000-A -w6 -p27 -i3f
CRC-6/G-704 -w6 -p03 -rR
CRC-7/MMC -w7 -p09
CRC-8/DARC -w8 -p39 -rR
CRC-8/GSM-A -w8 -p1d
CRC-8/HITAG -w8 -p1d -iff
CRC-8/I-CODE -w8 -p1d -ifd
CRC-8/MIFARE-MAD -w8 -p1d -ic7
CRC-8/SAE-J1850 -w8 -p1d -iff -xff
CRC-8/TECH-3250 -w8 -p1d -iff -rR
CRC-12/GSM -w12 -pd31 -xfff
CRC-15/MPT1327 -w15 -p6815 -x0001
CRC-16/CDMA2000 -w16 -pc867 -iffff
CRC-16/LJ1200 -w16 -p6f63
CRC-16/M17 -w16 -p5935 -iffff
CRC-16/OPENSAFETY-A -w16 -p5935
CRC-16/OPENSAFETY-B -w16 -p755b
CRC-16/PROFIBUS -w16 -p1dcf -iffff -xffff
CRC-16/T10-DIF -w16 -p8bb7
CRC-32/BZIP2 -w32 -p04c11db7 -iffffffff -xffffffff
CRC-32/CKSUM -w32 -p04c11db7 -xffffffff
CRC-32/MPEG-2 -w32 -p04c11db7 -iffffffff
CRC-32/XFER -w32 -p000000af

The listed CRC function names and parameters have been taken from the file check.sh

---

Yes. In principle, we could define a file format that includes a self-referential CRC checksum (that is calculated over the entire file) in its header. This would unironically simplify parsing of such file format.