/**
 * LibtiffDirDedupTest — MOAD-0001 model for libtiff-0001
 *
 * Models the O(D^2) duplicate-tag detection loop in TIFFReadDirectory /
 * TIFFReadCustomDirectory (libtiff/tif_dirread.c, bugzilla 1994 dedup block).
 *
 * A TIFF IFD can contain up to 65535 directory entries (dircount is uint16_t).
 * For each entry ma the original code scans all subsequent entries na looking
 * for a matching tdir_tag, producing O(D*(D-1)/2) comparisons.
 *
 * Fix: replace with a HashSet membership test — O(D) total.
 *
 * Severity: HIGH — a crafted adversarial TIFF with 65535 entries bearing
 * unique tags causes ~2 billion tag comparisons on each TIFFReadDirectory call.
 * At ~1 ns per comparison that is ~2 seconds per IFD open on modern hardware.
 * Multi-page TIFFs (each page is an IFD) multiply the impact linearly.
 */
import java.util.*;

public class LibtiffDirDedupTest {

    // --- O(D^2) original: nested loop duplicate detection ---
    static boolean[] markDuplicatesQuadratic(int[] tags) {
        boolean[] ignore = new boolean[tags.length];
        for (int ma = 0; ma < tags.length; ma++) {
            for (int na = ma + 1; na < tags.length; na++) {
                if (tags[ma] == tags[na]) {
                    ignore[na] = true;
                }
            }
        }
        return ignore;
    }

    // --- O(D) fixed: HashSet membership dedup ---
    static boolean[] markDuplicatesLinear(int[] tags) {
        boolean[] ignore = new boolean[tags.length];
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < tags.length; i++) {
            if (!seen.add(tags[i])) {
                ignore[i] = true;
            }
        }
        return ignore;
    }

    static int[] buildTags(int count, boolean withDups) {
        int[] tags = new int[count];
        // Fill with unique ascending tag IDs (TIFF spec: tags should be sorted)
        for (int i = 0; i < count; i++) {
            tags[i] = i;
        }
        if (withDups) {
            // Insert duplicates at regular intervals
            for (int i = count / 4; i < count; i += count / 4) {
                tags[i] = tags[i - 1];
            }
        }
        return tags;
    }

    static void assertResultsMatch(int[] tags) {
        boolean[] q = markDuplicatesQuadratic(tags);
        boolean[] l = markDuplicatesLinear(tags);
        for (int i = 0; i < tags.length; i++) {
            if (q[i] != l[i]) {
                throw new AssertionError(
                    "Mismatch at index " + i + ": quadratic=" + q[i] +
                    " linear=" + l[i] + " tag=" + tags[i]);
            }
        }
    }

    public static void main(String[] args) {
        // Correctness tests
        assertResultsMatch(new int[]{});
        assertResultsMatch(new int[]{1});
        assertResultsMatch(new int[]{1, 2, 3});
        assertResultsMatch(new int[]{1, 1, 2, 3, 3, 3, 4});
        assertResultsMatch(buildTags(64, true));
        assertResultsMatch(buildTags(256, true));
        assertResultsMatch(buildTags(1000, false));
        assertResultsMatch(buildTags(1000, true));
        System.out.println("PASS: correctness checks done");

        // Performance benchmark
        int[] sizes = {500, 1000, 2000, 4000, 8000};
        System.out.printf("%-8s  %-12s  %-12s  %-8s%n",
            "D", "quadratic(ms)", "linear(ms)", "ratio");
        for (int sz : sizes) {
            int[] tags = buildTags(sz, false);

            long t0 = System.nanoTime();
            for (int r = 0; r < 200; r++) markDuplicatesQuadratic(tags);
            long quadMs = (System.nanoTime() - t0) / 1_000_000;

            long t1 = System.nanoTime();
            for (int r = 0; r < 200; r++) markDuplicatesLinear(tags);
            long linMs = (System.nanoTime() - t1) / 1_000_000;

            double ratio = linMs > 0 ? (double) quadMs / linMs : Double.NaN;
            System.out.printf("%-8d  %-12d  %-12d  %-8.1f%n",
                sz, quadMs, linMs, ratio);
        }
    }
}