compare_deltas.py

#!/usr/bin/env python3
"""Compare successive-version delta creation and chained reconstruction."""
import argparse
import hashlib
import json
import itertools
import platform
import random
import shutil
import statistics
import subprocess
import tempfile
import time
from pathlib import Path

SEED = 20261028
ROOT = Path(__file__).resolve().parent
TOOLS = ('xdelta3', 'rdiff', 'bsdiff', 'zstd')


def sha_file(path):
    h = hashlib.sha256()
    with path.open('rb') as f:
        for block in iter(lambda: f.read(1024 * 1024), b''):
            h.update(block)
    return h.hexdigest()


def command(args):
    start = time.perf_counter_ns()
    result = subprocess.run([str(arg) for arg in args], stdout=subprocess.PIPE,
                            stderr=subprocess.PIPE, timeout=120)
    elapsed = (time.perf_counter_ns() - start) / 1e6
    if result.returncode:
        raise RuntimeError(f'Command failed ({result.returncode}): {args!r}\n'
                           f'{result.stderr.decode(errors="replace")}')
    return elapsed


def stats(values):
    ordered = sorted(values)
    return {'sum_ms': sum(values), 'median_ms': statistics.median(values),
            'min_ms': ordered[0], 'max_ms': ordered[-1],
            'p95_ms': ordered[min(len(ordered) - 1, int(len(ordered) * .95))],
            'samples_ms': values}


def positive(value):
    result = int(value)
    if result <= 0:
        raise argparse.ArgumentTypeError('must be positive')
    return result


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('--versions', type=positive, default=100,
                        help='number of versions including the initial base (default: 100)')
    parser.add_argument('--runs', type=positive, default=3)
    parser.add_argument('--sizes', type=positive, nargs='+', default=[4096, 131072],
                        help='initial file sizes in bytes (at least 32)')
    parser.add_argument('--workloads', nargs='+', choices=('binary', 'text'),
                        default=['binary', 'text'])
    args = parser.parse_args()
    if args.versions < 2 or any(size < 32 for size in args.sizes):
        parser.error('--versions must be at least 2 and each --sizes value at least 32')
    if len(set(args.sizes)) != len(args.sizes):
        parser.error('--sizes values must be distinct')
    if len(set(args.workloads)) != len(args.workloads):
        parser.error('--workloads values must be distinct')
    names = ('xdelta3', 'rdiff', 'bsdiff', 'bspatch', 'zstd')
    paths = {name: shutil.which(name) for name in names}
    missing = [name for name, path in paths.items() if path is None]
    if missing:
        parser.error('missing executables: ' + ', '.join(missing))
    binaries = {name: str(Path(path).resolve()) for name, path in paths.items()}
    directory = Path(tempfile.mkdtemp(prefix='compare-deltas-', dir=ROOT))
    report = {
        'seed': SEED, 'platform': platform.platform(), 'versions': args.versions,
        'runs': args.runs, 'sizes': args.sizes, 'workloads': args.workloads, 'directory': str(directory),
        'script_sha256': sha_file(Path(__file__)),
        'binaries': {name: {'path': path, 'sha256': sha_file(Path(path))}
                     for name, path in binaries.items()},
        'protocol': ('Identical deterministic cumulative versions per workload, size and trial. '
                     'Seed 20261028 + initial size. Binary begins as random bytes; text begins '
                     'as lowercase hex of random bytes, wrapped every 64 characters and '
                     'truncated to initial size. Each revision replaces three random 16-byte '
                     'windows and appends one byte. Text replacements avoid newlines and use '
                     'hexadecimal characters. Fresh outputs each trial. '
                     'Creation uses each original predecessor; reconstruction follows each '
                     'tool\'s own reconstructed chain from the common initial base. SHA-256 '
                     'verification after every reconstruction is outside timed intervals. '
                     'Tool order rotates per version and trial. Times are CLI wall time including '
                     'process startup and output capture; rdiff creation includes separate '
                     'signature and delta commands. Filesystem cache is warm; fixture generation, '
                     'file sizes, hashing and cleanup are not timed.'),
        'limitations': ('Synthetic binary and hexadecimal text edits; no CPU pinning or background-load isolation. '
                        'CLI startup matters especially for small files. Defaults and compression '
                        'settings differ; rdiff requires a temporary signature. Storage totals '
                        'count the uncompressed initial base plus successive delta files, not '
                        'filesystem overhead or metadata. Reconstruction applies every delta '
                        'sequentially; no random-access checkpoints or recovery tests.'),
        'cases': {}, 'completed': False,
    }

    def save():
        (directory / 'results.json').write_text(json.dumps(report, indent=2) + '\n')

    save()
    for workload, size in itertools.product(args.workloads, args.sizes):
        case = {'workload': workload, 'initial_bytes': size, 'fixture_sha256': [], 'trials': []}
        report['cases'][f'{workload}-{size}'] = case
        for trial in range(args.runs):
            with tempfile.TemporaryDirectory(prefix='work-', dir=directory) as work:
                work = Path(work)
                rng = random.Random(SEED + size)
                if workload == 'binary':
                    data = bytearray(rng.randbytes(size))
                else:
                    raw = rng.randbytes(size).hex()
                    data = bytearray(('\n'.join(raw[i:i + 64] for i in range(0, len(raw), 64)))[:size], 'ascii')
                base = work / 'version-0'
                base.write_bytes(data)
                hashes = [sha_file(base)]
                previous = base
                rebuilt = {name: base for name in TOOLS}
                tools = {name: {'encode_ms': [], 'decode_ms': [], 'delta_bytes': [],
                                'signature_ms': [], 'signature_bytes': []} for name in TOOLS}
                for version in range(1, args.versions):
                    for _ in range(3):
                        at = rng.randrange(len(data) - 16)
                        if workload == 'text':
                            while b'\n' in data[at:at + 16]:
                                at = rng.randrange(len(data) - 16)
                            data[at:at + 16] = rng.randbytes(8).hex().encode('ascii')
                        else:
                            data[at:at + 16] = rng.randbytes(16)
                    data += (rng.randbytes(1).hex()[:1].encode('ascii')
                             if workload == 'text' else rng.randbytes(1))
                    current = work / f'version-{version}'
                    current.write_bytes(data)
                    expected = sha_file(current)
                    hashes.append(expected)
                    shift = (version - 1 + trial) % len(TOOLS)
                    order = TOOLS[shift:] + TOOLS[:shift]
                    for name in order:
                        delta = work / f'{name}.delta'
                        output = work / f'{name}-rebuild-{version}'
                        row = tools[name]
                        if name == 'xdelta3':
                            enc = command([binaries[name], '-e', '-s', previous, current, delta])
                            dec_args = [binaries[name], '-d', '-s', rebuilt[name], delta, output]
                        elif name == 'rdiff':
                            signature = work / 'rdiff.signature'
                            sig_ms = command([binaries[name], 'signature', previous, signature])
                            row['signature_ms'].append(sig_ms)
                            row['signature_bytes'].append(signature.stat().st_size)
                            enc = sig_ms + command([binaries[name], 'delta', signature, current, delta])
                            dec_args = [binaries[name], 'patch', rebuilt[name], delta, output]
                        elif name == 'bsdiff':
                            enc = command([binaries[name], previous, current, delta])
                            dec_args = [binaries['bspatch'], rebuilt[name], output, delta]
                        else:
                            enc = command([binaries[name], '-q', f'--patch-from={previous}', current, '-o', delta])
                            dec_args = [binaries[name], '-q', '-d', f'--patch-from={rebuilt[name]}', delta, '-o', output]
                        row['encode_ms'].append(enc)
                        row['delta_bytes'].append(delta.stat().st_size)
                        row['decode_ms'].append(command(dec_args))
                        actual = sha_file(output)
                        if actual != expected:
                            raise RuntimeError(f'{name} version {version}: SHA-256 {actual} != {expected}')
                        if rebuilt[name] != base:
                            rebuilt[name].unlink()
                        rebuilt[name] = output
                        delta.unlink()
                        if name == 'rdiff':
                            signature.unlink()
                    if previous != base:
                        previous.unlink()
                    previous = current
                if not case['fixture_sha256']:
                    case['fixture_sha256'] = hashes
                elif hashes != case['fixture_sha256']:
                    raise RuntimeError('fixtures differ between trials')
                summary = {}
                for name, row in tools.items():
                    delta_total = sum(row['delta_bytes'])
                    summary[name] = {
                        'encode': stats(row['encode_ms']), 'decode': stats(row['decode_ms']),
                        'delta_bytes': row['delta_bytes'], 'delta_bytes_total': delta_total,
                        'base_bytes': size, 'base_plus_deltas_bytes': size + delta_total,
                        'verified_reconstructions': len(row['decode_ms']),
                    }
                    if name == 'rdiff':
                        summary[name]['signature'] = stats(row['signature_ms'])
                        summary[name]['signature_bytes'] = row['signature_bytes']
                case['trials'].append({'trial': trial, 'tools': summary})
                save()
                print(f'{workload}, {size} bytes, trial {trial + 1}: ' + ', '.join(
                    f'{name} {summary[name]["delta_bytes_total"]} delta bytes' for name in TOOLS), flush=True)
    for name, path in binaries.items():
        if sha_file(Path(path)) != report['binaries'][name]['sha256']:
            raise RuntimeError(f'executable changed during benchmark: {name}')
    report['completed'] = True
    save()
    print('Results:', directory / 'results.json', flush=True)


if __name__ == '__main__':
    main()