import java.util.*;

/**
 * Unit test for Suricata CWE-407: SigFindSignatureBySidGid O(S) linear scan
 * called per threshold.conf line, giving O(T*S) total at startup.
 *
 * Defect: util-threshold-config.c calls SigFindSignatureBySidGid() for each
 * threshold config line. That function walks the entire sig_list linked list
 * O(S) per call. With T threshold lines: O(T * S).
 *
 * In production Suricata: S = 30,000-80,000 (ET rules), T = 100-5,000
 * threshold/suppress entries. At T=1000, S=30000: 30 million comparisons.
 *
 * Fix: Build a HashMap<(sid,gid), Signature> once before threshold parsing.
 * Lookup becomes O(1) per line. Total: O(S + T) instead of O(T * S).
 */
public class SuricataThresholdLookupTest {

    static class Signature {
        int sid;
        int gid;
        Signature(int sid, int gid) { this.sid = sid; this.gid = gid; }
    }

    // --- Defective: linear scan per lookup ---
    static int defectiveOps = 0;

    static Signature findSigLinear(List<Signature> sigList, int sid, int gid) {
        for (Signature s : sigList) {
            defectiveOps++;
            if (s.sid == sid && s.gid == gid)
                return s;
        }
        return null;
    }

    // --- Fixed: hash map lookup ---
    static int fixedOps = 0;

    static Map<Long, Signature> buildSigMap(List<Signature> sigList) {
        Map<Long, Signature> map = new HashMap<>();
        for (Signature s : sigList) {
            fixedOps++;
            long key = ((long) s.sid << 32) | (s.gid & 0xFFFFFFFFL);
            map.put(key, s);
        }
        return map;
    }

    static Signature findSigFixed(Map<Long, Signature> sigMap, int sid, int gid) {
        fixedOps++;
        long key = ((long) sid << 32) | (gid & 0xFFFFFFFFL);
        return sigMap.get(key);
    }

    public static void main(String[] args) {
        int S = 30000; // number of signatures (typical ET ruleset)
        int T = 1000;  // number of threshold config lines

        // Build signature list
        List<Signature> sigList = new ArrayList<>();
        for (int i = 0; i < S; i++)
            sigList.add(new Signature(i + 1, 1));

        // Threshold entries: lookup random sids
        int[] thresholdSids = new int[T];
        Random rng = new Random(42);
        for (int i = 0; i < T; i++)
            thresholdSids[i] = rng.nextInt(S) + 1;

        // Run defective version: linear scan per threshold line
        defectiveOps = 0;
        for (int sid : thresholdSids) {
            Signature found = findSigLinear(sigList, sid, 1);
            assert found != null : "Should find sid " + sid;
        }
        int defOps = defectiveOps;

        // Run fixed version: build hash map once, then O(1) lookups
        fixedOps = 0;
        Map<Long, Signature> sigMap = buildSigMap(sigList);
        for (int sid : thresholdSids) {
            Signature found = findSigFixed(sigMap, sid, 1);
            assert found != null : "Should find sid " + sid;
        }
        int fixOps = fixedOps;

        double ratio = (double) defOps / fixOps;

        System.out.println("=== Suricata suricata-0001: SigFindSignatureBySidGid O(T*S) ===");
        System.out.println("S (signatures):     " + S);
        System.out.println("T (threshold lines): " + T);
        System.out.println("Defective ops:       " + defOps);
        System.out.println("Fixed ops:           " + fixOps);
        System.out.printf("Ratio:               %.1fx%n", ratio);

        // Verify ratio shows quadratic vs linear improvement
        assert ratio > 100.0 : "Expected >100x ratio, got " + ratio;

        System.out.println("PASS");
    }
}