Compare directory structures using the rsync algorithm with rolling hash. If files…
- User
Compare directory structures using the rsync algorithm with rolling hash. If files differ, identify which blocks changed using Adler-32 rolling checksum so you only copy changed chunks, not whole files.
- Assistant
Explaining simplified rsync-style block comparison
The approach scans two directories, and for each file in both, divides files into fixed-size blocks computing Adler-32 checksums to detect differing blocks by index. This simplified method identifies changed chunks without full rolling checksum matching but illustrates how to copy only changed blocks efficiently. What rsync does to avoid shipping whole files is:
- Walk the tree at the receiver, for each file break it into fixed‑size blocks (e.g. 4 KiB, 16 KiB …).
- For each block compute a “weak” rolling checksum and a “strong” checksum to guard against collisions.
- Send that signature list to the sender.
- The sender scans its version of the file with a sliding window the same size as the block, maintaining the rolling checksum as it advances one byte at a time. When the weak checksum matches one in the receiver’s list, the sender verifies with the strong checksum. Matching regions are left in place, non‑matching regions are sent.
You can use Adler‑32 as the rolling checksum. For a window of length (L) the Adler state is (s_1=\sum b_i), (s_2=\sum_{i=1\ldots L} s_1^{(i)}). When you advance the window by one byte you don’t have to recompute from scratch:
MOD = 65521 def adler32_state(buf): s1 = 0 s2 = 0 for b in buf: s1 = (s1 + b) % MOD s2 = (s2 + s1) % MOD return s1, s2 # combined value is (s2 << 16) | s1 def roll_adler32(s1, s2, old_byte, new_byte, window_len): s1 = (s1 - old_byte + new_byte) % MOD s2 = (s2 - window_len*old_byte + s1) % MOD return s1, s2Putting it together in a simple directory comparer:
import os, zlib, hashlib BLOCK = 4096 def build_signature(path): sigs = [] with open(path, 'rb') as f: idx = 0 while True: block = f.read(BLOCK) if not block: break weak_s1, weak_s2 = adler32_state(block) strong = hashlib.md5(block).digest() sigs.append((idx, (weak_s1, weak_s2), strong)) idx += 1 return sigs def find_changed_blocks(src_path, dst_sigs): # map weak checksum to list of (index,strong) weak_map = {} for idx, (s1,s2), strong in dst_sigs: weak_map.setdefault((s1,s2), []).append((idx,strong)) changed = [] with open(src_path, 'rb') as f: window = f.read(BLOCK) if not window: return [] pos = 0 s1, s2 = adler32_state(window) while True: candidates = weak_map.get((s1,s2), []) matched = False for idx,strong in candidates: if hashlib.md5(window).digest() == strong: # block matches receiver’s block idx, skip ahead matched = True pos += BLOCK f.seek(pos) window = f.read(BLOCK) if not window: return changed s1, s2 = adler32_state(window) break if matched: continue # no match: current byte will need to be sent changed.append(pos) # slide window by one byte old = window[0] nxt = f.read(1) if not nxt: return changed window = window[1:] + nxt s1, s2 = roll_adler32(s1, s2, old, nxt[0], BLOCK) return changedYou can drive this over two directory trees with
os.walk: for each relative path that exists in both trees, build the signature of the destination file, then callfind_changed_blockson the source file. The list of offsets you get back tells you which chunks differ and need to be transferred; matching blocks can be referenced by index and reused on the receiver side. Files that are new or missing on either side can simply be copied or deleted.This is the essence of rsync’s delta transfer: a rolling Adler‑32 lets you resynchronise even if bytes have been inserted or removed, and you only copy the changed chunks instead of whole files.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.