fountain_qr_reading.md

Fountain QR Reading

Completely untested with actual qrcodes: based on fact that python's set.symmetric_difference is analogous to XOR.

This is an exploration of extrapolating more XOR-mixed frames than have been received while reading a fountain qrcode.

ie: If we get 2 frames with parts [0, 1, 3, 5] and [3, 5, 7, 9], then we also have [0, 1, 7, 9]

Working off of Keith's gist here I've made the assumption that part 8 was known as frame 0. I've also skipped frames that I assume are duplicates when Keith's log doesn't hint that new information was received.

from functools import reduce

def xor(*list_of_bytes):
    def _xor(a, b):
        assert type(a) == type(b) == bytes and len(a) == len(b)
        return bytes(i^j for i,j in zip(a,b))
    return bytes(reduce(_xor, list_of_bytes))

source = [(x.encode() + b' '*10)[:10] for x in [
    "zero",
    "one",
    "two",
    "three",
    "four",
    "five",
    "six",
    "seven",
    "eight",
    "nine",
    "ten",
    "eleven",
    "twelve",
    "thirteen",
    "fourteen"
]]

frames = [set(x) for x in [
    [8,],
    [0, 4, 6, 14],
    [2, 3, 4, 5, 6, 9, 10, 11, 12, 13],
    [0, 1, 2, 3, 5, 6, 7, 9, 10, 12, 13, 14],
    [1, 3, 6],
    [2, 3, 5, 11, 13],
    [0, 3, 5, 10, 11, 12, 13],
    [0, 5, 10, 11, 12, 13],
    [0, 1, 13],
    [12, 14],
    [1, 10, 12, 13],
    [1, 7, 9, 10, 12],
    [7, 10, 11, 13, 14],
    [0, 7, 10],
    [4, 9, 13, 14],
    [4, 7, 10, 12],
    [1, 7, 10, 11, 12],
    [4, 9, 11, 12],
    [1, 4],
    [6, 11, 14],
    [6, 12],
    [13, 14],
    [5, 13],
]]

print("Source:\n", source)

parts = {}
mixed = {}


loops = 0
for i, frame in enumerate(frames):
    loops += 1
    frame_data = xor(*[source[x] for x in frame])
    print(f"\nnew_frame #{i}: {frame} = {frame_data}")

    known_parts = frame.intersection(set(parts.keys()))
    if (known_parts):
        if known_parts == set(parts.keys()):
            continue
        frame = frame.difference(known_parts)
        frame_data = xor(*([frame_data] + [parts[x] for x in known_parts]))

    for mix, mix_data in [(x, y) for x,y in mixed.items()]:
        loops += 1
        if not frame.intersection(mix):
            continue
        diff = frame.symmetric_difference(mix)
        diff_data = xor(frame_data, mix_data)
        if len(diff) == 1:
            part = diff.pop()
            if part not in parts:
                parts[part] = diff_data
                for old in [x for x in mixed]:
                    loops += 1
                    if part in old:
                        new = set(old).symmetric_difference(set([part]))
                        new_data = xor(diff_data, mixed[old])
                        mixed[tuple(sorted(new))] = new_data
                        del mixed[old]
        else:
            mixed[tuple(sorted(diff))] = diff_data

    if len(frame) == 1:
        parts[frame.pop()] = frame_data
    else:
        mixed[tuple(sorted(frame))] = frame_data

    print(f"parts: {sorted(parts)}\nlen(mixed): {len(mixed)}\nloops: {loops}")
    if len(parts) == len(source):
        print("\nDecoded:\n", [parts[x] for x in sorted(parts)])
        break

As you can see, the len(mixed) grows exponentially at first, then gets trimmed as parts are found: key is a tuple of sorted parts, value here is only 10 XORed bytes.

Source:
 [b'zero      ', b'one       ', b'two       ', b'three     ', b'four      ', b'five      ', b'six       ', b'seven     ', b'eight     ', b'nine      ', b'ten       ', b'eleven    ', b'twelve    ', b'thirteen  ', b'fourteen  ']

new_frame #0: {8} = b'eight     '
parts: [8]
len(mixed): 0
loops: 1

new_frame #1: {0, 4, 6, 14} = b'\t\x0c\nOTEEN\x00\x00'
parts: [8]
len(mixed): 1
loops: 2

new_frame #2: {2, 3, 4, 5, 6, 9, 10, 11, 12, 13} = b'\x0c\x0f\x0f_\x02NEN\x00\x00'
parts: [8]
len(mixed): 3
loops: 4

new_frame #3: {0, 1, 2, 3, 5, 6, 7, 9, 10, 12, 13, 14} = b'\x0f\r\x0b\x03]E\x00\x00\x00\x00'
parts: [8]
len(mixed): 7
loops: 8

new_frame #4: {1, 3, 6} = b'hooee     '
parts: [8]
len(mixed): 15
loops: 16

new_frame #5: {2, 3, 5, 11, 13} = b'wrg$t+en  '
parts: [8]
len(mixed): 30
loops: 32

new_frame #6: {0, 3, 5, 10, 11, 12, 13} = b'yrq\'"nen  '
parts: [8]
len(mixed): 61
loops: 63

new_frame #7: {0, 5, 10, 11, 12, 13} = b'\r\x1a\x03BGNEN\x00\x00'
parts: [3, 8]
len(mixed): 61
loops: 243

new_frame #8: {0, 1, 13} = b'ac~=teen  '
parts: [3, 8]
len(mixed): 117
loops: 305

new_frame #9: {12, 14} = b'\x12\x18\x10\x1e\x02\x00EN\x00\x00'
parts: [3, 8]
len(mixed): 205
loops: 423

new_frame #10: {1, 10, 12, 13} = b'\x1b\x14\x07\x1e\x02\x00EN\x00\x00'
parts: [2, 3, 8]
len(mixed): 284
loops: 911

new_frame #11: {1, 7, 9, 10, 12} = b'rpvl8e    '
parts: [2, 3, 8]
len(mixed): 562
loops: 1196

new_frame #12: {7, 10, 11, 13, 14} = b'pka3+n    '
parts: [1, 2, 3, 6, 8]
len(mixed): 606
loops: 3093

new_frame #13: {0, 10, 7} = b'}ej*n     '
parts: [0, 1, 2, 3, 6, 8, 13]
len(mixed): 807
loops: 5093

new_frame #14: {9, 4, 13, 14} = b'\x1a\x01\x07\x17\x00\x00\x00\x00\x00\x00'
parts: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
len(mixed): 599
loops: 9561

Decoded:
 [b'zero      ', b'one       ', b'two       ', b'three     ', b'four      ', b'five      ', b'six       ', b'seven     ', b'eight     ', b'nine      ', b'ten       ', b'eleven    ', b'twelve    ', b'thirteen  ', b'fourteen  ']

jdlcdl/fountain_qr_reading.md

Fountain QR Reading