Back
+30 XP
Concept

Binary Diff & Patch Generator

Transmitting an entire 100MB updated binary over metered mobile networks wastes bandwidth when only a few bytes changed. A binary diff identifies matching byte blocks to issue COPY instructions and INSERT commands for novel bytes, yielding tiny patch updates.

python
# Patch operation types:
# ("COPY", source_offset, length)
# ("INSERT", literal_bytes)

# Binary Diff & Patch Generator When your mobile app or firmware updates from version 1.0 to 1.1, 98% of the binary executable is identical. Transmitting the full 50 MB firmware binary over cellular towers costs money and burns battery. 📦⚡ **Delta Compression (Binary Diffing)** calculates differences: - **`("COPY", src_offset, length)`**: Directs the patcher to copy `length` bytes from the client’s existing original file at `src_offset`. - **`("INSERT", new_bytes)`**: Directs the patcher to insert newly modified or introduced bytes. Applying the tiny patch sequence transforms the old binary into the new binary bit-for-bit. ```python # Applying a patch stream: for op, *args in patch: if op == "COPY": offset, length = args output.extend(old_data[offset : offset + length]) elif op == "INSERT": data, = args output.extend(data) ``` ## Pop Quiz Why do delta-compression patch formats use `COPY` instructions referencing the original file? - [ ] They reuse existing unmodified data blocks already resident on the client disk, avoiding retransmission over the wire. - [ ] They decrypt proprietary compression algorithms via hardware DMA controllers. - [ ] They bypass operating system write permissions on immutable executable binaries. - [ ] Because modern network routers only forward diff packets containing COPY opcodes. ## Real-World Challenge Implement: 1. `create_binary_patch(old_bytes: bytes, new_bytes: bytes) -> list[tuple]`: Scans for matching chunks of length $\ge 4$ to generate `("COPY", old_pos, length)` and `("INSERT", byte_slice)` operations. 2. `apply_binary_patch(old_bytes: bytes, patch: list[tuple]) -> bytes`: Reconstructs the target byte sequence from the original bytes and patch operations. <details> <summary>Solution</summary> ```python def create_binary_patch(old_bytes: bytes, new_bytes: bytes) -> list[tuple]: patch = [] i = 0 new_len = len(new_bytes) while i < new_len: # Search for longest matching block in old_bytes best_match_pos = -1 best_match_len = 0 max_search_len = min(32, new_len - i) for match_len in range(max_search_len, 3, -1): sub = new_bytes[i : i + match_len] pos = old_bytes.find(sub) if pos != -1: best_match_pos = pos best_match_len = match_len break if best_match_len >= 4: patch.append(("COPY", best_match_pos, best_match_len)) i += best_match_len else: patch.append(("INSERT", bytes([new_bytes[i]]))) i += 1 return patch def apply_binary_patch(old_bytes: bytes, patch: list[tuple]) -> bytes: output = bytearray() for op, *args in patch: if op == "COPY": pos, length = args output.extend(old_bytes[pos : pos + length]) elif op == "INSERT": data, = args output.extend(data) else: raise ValueError(f"Unknown patch op: {op}") return bytes(output) # Verification old_payload = b"INIT_FIRMWARE_CORE_V1_CONFIG_ACTIVE_SYSTEM_READY" new_payload = b"INIT_FIRMWARE_CORE_V2_CONFIG_ACTIVE_DEBUG_READY" patch_instructions = create_binary_patch(old_payload, new_payload) reconstructed = apply_binary_patch(old_payload, patch_instructions) assert reconstructed == new_payload assert any(op[0] == "COPY" for op in patch_instructions) ``` </details>