package unit;
import java.util.HashSet;

/**
 * openssh-0001 / openssh-0002: CWE-407 O(N²) dedup via match_list inside loop
 *
 * Models kex_assemble_server_sig_algs() and kex_names_cat():
 *   SLOW: dedup by scanning a growing comma-separated string (match_list pattern)
 *   FAST: dedup using a HashSet with O(1) contains
 *
 * No JUnit — compile and run standalone.
 */
public class OpenSshSigAlgsTest {

    // -----------------------------------------------------------------------
    // SLOW: mirrors C kex_assemble_server_sig_algs / kex_names_cat dedup
    //   For each new alg, scan the entire accumulated string for a match.
    //   Returns op count (triangular sum proxy).
    // -----------------------------------------------------------------------
    static long slowDedup(String[] algs) {
        String accumulated = "";
        long ops = 0;
        for (String alg : algs) {
            // match_list scan: split accumulated on comma, strcmp each token
            if (!accumulated.isEmpty()) {
                String[] tokens = accumulated.split(",");
                for (String t : tokens) {
                    ops++;
                    if (t.equals(alg)) {
                        // duplicate — skip
                        alg = null;
                        break;
                    }
                }
            }
            if (alg != null) {
                accumulated = accumulated.isEmpty() ? alg : accumulated + "," + alg;
            }
        }
        return ops;
    }

    // -----------------------------------------------------------------------
    // FAST: HashSet O(1) contains — the fix
    // -----------------------------------------------------------------------
    static long fastDedup(String[] algs) {
        HashSet<String> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();
        long ops = 0;
        for (String alg : algs) {
            ops++;
            if (!seen.contains(alg)) {
                seen.add(alg);
                if (result.length() > 0) result.append(',');
                result.append(alg);
            }
        }
        return ops;
    }

    // -----------------------------------------------------------------------
    // Helper: generate N unique algorithm name strings
    // -----------------------------------------------------------------------
    static String[] makeAlgs(int n) {
        String[] algs = new String[n];
        for (int i = 0; i < n; i++) {
            algs[i] = "alg-" + i;
        }
        return algs;
    }

    public static void main(String[] args) {
        int tests = 0, passed = 0;

        // --- correctness tests ---
        int[] correctnessSizes = {1, 5, 10, 20};
        for (int n : correctnessSizes) {
            tests++;
            String[] algs = makeAlgs(n);
            long slowOps = slowDedup(algs);
            long fastOps = fastDedup(algs);
            // Both should produce same logical result; fast ops == n (one per alg)
            if (fastOps == n) {
                passed++;
                System.out.println("PASS correctness n=" + n
                    + " slow_ops=" + slowOps + " fast_ops=" + fastOps);
            } else {
                System.out.println("FAIL correctness n=" + n
                    + " expected fast_ops=" + n + " got=" + fastOps);
            }
        }

        // --- dedup correctness: all-duplicate input ---
        {
            tests++;
            int n = 20;
            String[] algs = new String[n];
            for (int i = 0; i < n; i++) algs[i] = "same-alg";
            long slowOps = slowDedup(algs);
            long fastOps = fastDedup(algs);
            // fast: n ops; slow: 0+1+1+...+1 = n-1 (first hit terminates each scan)
            // key check: fast == n, slow >= n-1
            if (fastOps == n && slowOps >= n - 1) {
                passed++;
                System.out.println("PASS dedup-all-same n=" + n
                    + " slow_ops=" + slowOps + " fast_ops=" + fastOps);
            } else {
                System.out.println("FAIL dedup-all-same n=" + n
                    + " slow_ops=" + slowOps + " fast_ops=" + fastOps);
            }
        }

        // --- speedup benchmark ---
        int[] benchSizes = {100, 200, 500, 1000};
        for (int n : benchSizes) {
            tests++;
            String[] algs = makeAlgs(n);

            long slowOps = slowDedup(algs);
            long fastOps = fastDedup(algs);

            // triangular: slow = 0+1+2+...+(n-1) = n*(n-1)/2
            long expected_slow = (long) n * (n - 1) / 2;

            double ratio = (double) slowOps / fastOps;

            // Require ratio >= 5x at n=500
            boolean ok = (n < 500) ? (ratio >= 2.0) : (ratio >= 5.0);
            if (ok) {
                passed++;
                System.out.printf("PASS speedup n=%d slow_ops=%d fast_ops=%d ratio=%.1fx%n",
                    n, slowOps, fastOps, ratio);
            } else {
                System.out.printf("FAIL speedup n=%d slow_ops=%d fast_ops=%d ratio=%.1fx (need >=5x at n>=500)%n",
                    n, slowOps, fastOps, ratio);
            }
        }

        System.out.println("\n" + passed + "/" + tests + " PASS");
        if (passed != tests) System.exit(1);
    }
}