benchmark.py

#!/usr/bin/env python3
"""
NONOCRYPT Benchmark Suite

Measures performance across grid sizes for:
  1. Key generation (image → clues)
  2. Puzzle solving (clues → image, NP-hard)
  3. Encryption (solve + symmetric encrypt)
  4. Decryption (symmetric only, no solving)
  5. Difficulty analysis (propagation vs backtracking)
"""

import time
import sys
import statistics
from nonogram import (
    compute_clues, solve, random_image, difficulty_score,
    verify_solution, propagate,
)
from nonocrypt import keygen_from_image, keygen_random, encrypt, decrypt


def timed(fn, *args, **kwargs):
    """Run fn and return (result, elapsed_seconds)."""
    t0 = time.perf_counter()
    result = fn(*args, **kwargs)
    return result, time.perf_counter() - t0


def benchmark_clue_computation(sizes, trials=10):
    """Benchmark: image → clues (the forward/easy direction)."""
    print("\n" + "=" * 70)
    print("  BENCHMARK 1: Clue Computation  (image -> clues, O(n^2))")
    print("=" * 70)
    print(f"  {'Size':>6s}  {'Cells':>6s}  {'Mean (us)':>10s}  {'Stdev':>10s}  {'Throughput':>12s}")
    print(f"  {'-'*6}  {'-'*6}  {'-'*10}  {'-'*10}  {'-'*12}")

    for n in sizes:
        times = []
        for _ in range(trials):
            img = random_image(n)
            _, elapsed = timed(compute_clues, img)
            times.append(elapsed * 1e6)  # microseconds
        mean = statistics.mean(times)
        std = statistics.stdev(times) if len(times) > 1 else 0
        cells = n * n
        throughput = cells / (mean / 1e6) if mean > 0 else 0
        print(f"  {n:>4d}x{n:<1d}  {cells:>6d}  {mean:>10.1f}  {std:>10.1f}  {throughput:>9.0f} c/s")


def benchmark_solving(sizes, trials=3):
    """Benchmark: clues → image (the hard/NP direction)."""
    print("\n" + "=" * 70)
    print("  BENCHMARK 2: Puzzle Solving  (clues -> image, NP-complete)")
    print("=" * 70)
    print(f"  {'Size':>6s}  {'Cells':>6s}  {'Mean (ms)':>10s}  {'Min':>10s}  "
          f"{'Max':>10s}  {'Solved':>7s}  {'Backtracks':>10s}")
    print(f"  {'-'*6}  {'-'*6}  {'-'*10}  {'-'*10}  "
          f"{'-'*10}  {'-'*7}  {'-'*10}")

    for n in sizes:
        times = []
        solved_count = 0
        total_bt = 0
        for trial in range(trials):
            img = random_image(n, seed=trial * 1000 + n)
            rc, cc = compute_clues(img)
            t0 = time.perf_counter()
            solution = solve(rc, cc, timeout_sec=60)
            elapsed = (time.perf_counter() - t0) * 1000  # ms
            times.append(elapsed)
            if solution is not None:
                solved_count += 1

        mean = statistics.mean(times)
        mn = min(times)
        mx = max(times)
        print(f"  {n:>4d}x{n:<1d}  {n*n:>6d}  {mean:>10.2f}  {mn:>10.2f}  "
              f"{mx:>10.2f}  {solved_count:>4d}/{trials:<1d}  {'--':>10s}")


def benchmark_encrypt_decrypt(sizes, trials=3):
    """Benchmark: full encrypt (solve + symmetric) and decrypt."""
    print("\n" + "=" * 70)
    print("  BENCHMARK 3: Encrypt/Decrypt Timing")
    print("=" * 70)
    print(f"  {'Size':>6s}  {'Encrypt (ms)':>12s}  {'Decrypt (us)':>12s}  "
          f"{'Ratio':>8s}  {'CT Size':>8s}")
    print(f"  {'-'*6}  {'-'*12}  {'-'*12}  "
          f"{'-'*8}  {'-'*8}")

    message = b"The quick brown fox jumps over the lazy dog. " * 3

    for n in sizes:
        enc_times = []
        dec_times = []
        ct_sizes = []
        for trial in range(trials):
            # Use keygen_random which ensures unique solutions
            pk, sk = keygen_random(n, ensure_unique=True, min_difficulty=0)

            # Encrypt (includes puzzle solving)
            try:
                t0 = time.perf_counter()
                ct, solved, _ = encrypt(pk, message, timeout_sec=60)
                enc_ms = (time.perf_counter() - t0) * 1000
            except RuntimeError:
                continue  # Skip multi-solution puzzles

            # Decrypt (no solving)
            t0 = time.perf_counter()
            recovered = decrypt(sk, ct)
            dec_us = (time.perf_counter() - t0) * 1e6

            if recovered != message:
                continue

            enc_times.append(enc_ms)
            dec_times.append(dec_us)
            ct_sizes.append(len(ct.serialize()))

        if enc_times:
            enc_mean = statistics.mean(enc_times)
            dec_mean = statistics.mean(dec_times)
            ct_mean = statistics.mean(ct_sizes)
            ratio = enc_mean * 1000 / dec_mean if dec_mean > 0 else 0
            print(f"  {n:>4d}x{n:<1d}  {enc_mean:>12.2f}  {dec_mean:>12.1f}  "
                  f"{ratio:>7.0f}x  {ct_mean:>7.0f}B")


def benchmark_difficulty_distribution(sizes, samples=20):
    """Analyze puzzle difficulty distribution across grid sizes."""
    print("\n" + "=" * 70)
    print("  BENCHMARK 4: Difficulty Distribution")
    print("=" * 70)
    print(f"  {'Size':>6s}  {'Mean Propagation %':>18s}  {'Need Backtrack %':>16s}  "
          f"{'Avg Undetermined':>16s}")
    print(f"  {'-'*6}  {'-'*18}  {'-'*16}  {'-'*16}")

    for n in sizes:
        prop_ratios = []
        needs_bt = 0
        undetermined = []
        for trial in range(samples):
            img = random_image(n, seed=trial * 10 + n)
            rc, cc = compute_clues(img)
            diff = difficulty_score(rc, cc)
            if diff.get("solvable", False):
                prop_ratios.append(diff["propagation_ratio"] * 100)
                if diff.get("needs_backtracking", False):
                    needs_bt += 1
                undetermined.append(diff.get("undetermined_cells", 0))

        if prop_ratios:
            mean_prop = statistics.mean(prop_ratios)
            bt_pct = 100.0 * needs_bt / samples
            mean_undet = statistics.mean(undetermined)
            print(f"  {n:>4d}x{n:<1d}  {mean_prop:>17.1f}%  {bt_pct:>15.1f}%  "
                  f"{mean_undet:>16.1f}")


def benchmark_message_sizes(n=12, sizes_kb=None):
    """Benchmark encrypt/decrypt with varying message sizes."""
    if sizes_kb is None:
        sizes_kb = [0.001, 0.01, 0.1, 1, 10]

    print("\n" + "=" * 70)
    print(f"  BENCHMARK 5: Message Size Scaling (grid={n}x{n})")
    print("=" * 70)
    print(f"  {'Msg Size':>10s}  {'Encrypt (ms)':>12s}  {'Decrypt (us)':>12s}  "
          f"{'CT Overhead':>12s}")
    print(f"  {'-'*10}  {'-'*12}  {'-'*12}  {'-'*12}")

    pk, sk = keygen_random(n, ensure_unique=True, min_difficulty=0)
    solved_image = sk.image  # Pre-solved

    for size_kb in sizes_kb:
        msg_len = max(1, int(size_kb * 1024))
        message = bytes(i % 256 for i in range(msg_len))

        # Encrypt with pre-solved image
        t0 = time.perf_counter()
        ct, _, _ = encrypt(pk, message, solved_image=solved_image)
        enc_ms = (time.perf_counter() - t0) * 1000

        # Decrypt
        t0 = time.perf_counter()
        recovered = decrypt(sk, ct)
        dec_us = (time.perf_counter() - t0) * 1e6

        ct_bytes = len(ct.serialize())
        overhead = ct_bytes - msg_len

        if msg_len < 1024:
            label = f"{msg_len}B"
        else:
            label = f"{msg_len/1024:.1f}KB"

        print(f"  {label:>10s}  {enc_ms:>12.3f}  {dec_us:>12.1f}  "
              f"{overhead:>11d}B")


def main():
    print(r"""
    ╔═══════════════════════════════════════════════════════════╗
    ║   NONOCRYPT Benchmark Suite                               ║
    ║   Post-Quantum Encryption via Nonogram NP-Hardness        ║
    ╚═══════════════════════════════════════════════════════════╝
    """)

    small = [5, 8, 10, 12, 15]
    medium = [5, 8, 10, 12, 15, 18, 20]
    large = [5, 10, 15, 20, 25]

    # Pick size set based on arg
    if len(sys.argv) > 1 and sys.argv[1] == "--full":
        solve_sizes = large
        print("  Mode: FULL (including larger grids, may take minutes)\n")
    else:
        solve_sizes = small
        print("  Mode: QUICK (use --full for larger grids)\n")

    benchmark_clue_computation(medium, trials=20)
    benchmark_solving(solve_sizes, trials=5)
    benchmark_encrypt_decrypt(small, trials=5)
    benchmark_difficulty_distribution(medium, samples=30)
    benchmark_message_sizes(n=10)

    print("\n" + "=" * 70)
    print("  Benchmark complete.")
    print("  Key insight: clue computation is O(n^2), solving is NP-hard.")
    print("  The asymmetry between encrypt (solve) and decrypt (instant)")
    print("  grows exponentially with grid size.")
    print("=" * 70 + "\n")


if __name__ == "__main__":
    main()