// uuid256.java — reference implementation of README.md (UUID256, random layout) in Java.  JDK 17+, no deps.
//
//   Run in source-file mode (no compile step, no artifacts):
//       java uuid256.java                        # self-tests + exact duplicate check over 100,000,000 ids
//       java -Xmx6g uuid256.java -n 100000000    # (give the JVM heap room for the default 1e8: ~3.7 GB live)
//       java uuid256.java -n 5000000 -i 3        # 5e6 ids with 3 planted duplicates (proves detection)
//       java uuid256.java -g [count]             # just print one (or count) new ids, nothing else
//   (macOS/Homebrew keg-only JDK: /opt/homebrew/opt/openjdk/bin/java uuid256.java …)
//   Library use: copy the Uuid256 class into your project (rename the file to Uuid256.java).
//
//       Uuid256 id  = Uuid256.randomUuid256();   // §5.1: 32 bytes from SecureRandom, ver=4 / var=10 applied
//       String  txt = id.toString();             // §3.1: 16-8-8-8-24, lowercase, 68 chars
//       Uuid256 b   = Uuid256.parse(txt);        // §6: strict; parse(txt, false) is lenient. Throws Uuid256.FormatException
//
// Bulk check: all randomness from SecureRandom (§5.2 — OS CSPRNG) into 512 MB chunks, §4 applied to
// every id, then an O(n) counting sort on the top 24 random bits groups ids into 16M buckets and every
// pair inside a bucket is compared over all 32 bytes.  Exact.  RAM ≈ 36 B per id.

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HexFormat;
import java.util.List;
import java.util.Locale;

// ============================================================================
//  Spec §3–§6: the Uuid256 value class
// ============================================================================

/** A 256-bit random unique identifier (README.md spec). Immutable; 32 bytes as four big-endian longs. */
public final class Uuid256 implements Comparable<Uuid256> {
    public static final int SIZE = 32;          // bytes
    public static final int TEXT_LENGTH = 68;   // 64 hex + 4 hyphens
    public static final int VERSION = 4;

    public static final Uuid256 NIL = new Uuid256(0, 0, 0, 0);                                   // §8
    public static final Uuid256 MAX = new Uuid256(-1L, -1L, -1L, -1L);

    private static final SecureRandom RNG = new SecureRandom();                                  // §5.2
    private static final char[] HEX = "0123456789abcdef".toCharArray();

    private final long a, b, c, d;   // a = bytes 0..7 (text group 1), b = 8..15, c = 16..23, d = 24..31

    private Uuid256(long a, long b, long c, long d) { this.a = a; this.b = b; this.c = c; this.d = d; }

    /** §4 — force version nibble (byte 12) and variant bits (byte 16) in a raw 32-byte buffer. */
    public static void setVersionAndVariant(byte[] buf, int off) {
        buf[off + 12] = (byte) ((buf[off + 12] & 0x0F) | (VERSION << 4));   // hex digit 24 = '4'
        buf[off + 16] = (byte) ((buf[off + 16] & 0x3F) | 0x80);             // hex digit 32 in [89ab]
    }

    /** §5.1 — a new id straight from the OS CSPRNG. */
    public static Uuid256 randomUuid256() {
        byte[] buf = new byte[SIZE];
        RNG.nextBytes(buf);
        setVersionAndVariant(buf, 0);
        return fromBytes(buf, 0);
    }

    /** Big-endian 32-byte encoding → value (no ver/var validation; see {@link #isStrict()}). */
    public static Uuid256 fromBytes(byte[] buf, int off) {
        if (off < 0 || buf.length - off < SIZE) throw new IllegalArgumentException("UUID256 is exactly 32 bytes");
        return new Uuid256(be64(buf, off), be64(buf, off + 8), be64(buf, off + 16), be64(buf, off + 24));
    }
    public static Uuid256 fromBytes(byte[] buf) {
        if (buf.length != SIZE) throw new IllegalArgumentException("UUID256 is exactly 32 bytes");
        return fromBytes(buf, 0);
    }
    private static long be64(byte[] p, int o) {
        long v = 0;
        for (int i = 0; i < 8; i++) v = (v << 8) | (p[o + i] & 0xFF);
        return v;
    }
    private static void putBe64(byte[] p, int o, long v) { for (int i = 7; i >= 0; i--) { p[o + i] = (byte) v; v >>>= 8; } }

    /** The 32-byte big-endian encoding. */
    public byte[] toBytes() {
        byte[] r = new byte[SIZE];
        putBe64(r, 0, a); putBe64(r, 8, b); putBe64(r, 16, c); putBe64(r, 24, d);
        return r;
    }

    /** Version nibble (byte 12 high nibble); 4 for this spec. */
    public int version() { return (int) ((b >>> 28) & 0xF); }
    /** Variant bits (byte 16 top two bits); 0b10 for this spec. */
    public int variant() { return (int) (c >>> 62); }
    /** §6 — ver == 4 && var == 10. */
    public boolean isStrict() { return version() == VERSION && variant() == 0b10; }

    /** §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars. */
    @Override public String toString() {
        byte[] bytes = toBytes();
        char[] out = new char[TEXT_LENGTH];
        int o = 0;
        for (int i = 0; i < SIZE; i++) {
            out[o++] = HEX[(bytes[i] >> 4) & 0xF];
            out[o++] = HEX[bytes[i] & 0xF];
            if (i == 7 || i == 11 || i == 15 || i == 19) out[o++] = '-';   // after hex digits 16, 24, 32, 40
        }
        return new String(out);
    }
    /** The 64-hex-digit compact form (input-only per §3.2 rule 4). */
    public String toCompact() { return HexFormat.of().formatHex(toBytes()); }

    public enum ErrorKind { LENGTH, HYPHEN, CHAR, VERSION }
    public static final class FormatException extends IllegalArgumentException {
        public final ErrorKind kind;
        FormatException(ErrorKind kind, String msg) { super(msg); this.kind = kind; }
    }

    /** §6 — strict parse of canonical (68) or compact (64) form, any case. */
    public static Uuid256 parse(CharSequence s) { return parse(s, true); }
    /** §6 — parse; {@code strict=false} skips the version/variant check (Nil/Max, future layouts). */
    public static Uuid256 parse(CharSequence s, boolean strict) {
        int len = s.length();
        boolean hyphenated;
        if (len == TEXT_LENGTH) {
            if (s.charAt(16) != '-' || s.charAt(25) != '-' || s.charAt(34) != '-' || s.charAt(43) != '-')
                throw new FormatException(ErrorKind.HYPHEN, "hyphen at wrong position");
            hyphenated = true;
        } else if (len == 64) hyphenated = false;
        else throw new FormatException(ErrorKind.LENGTH, "wrong length: " + len);
        byte[] buf = new byte[SIZE];
        int nib = 0, bi = 0, cur = 0;
        for (int i = 0; i < len; i++) {
            if (hyphenated && (i == 16 || i == 25 || i == 34 || i == 43)) continue;
            int v = Character.digit(s.charAt(i), 16);
            if (v < 0 || s.charAt(i) > 0x7F) throw new FormatException(ErrorKind.CHAR, "invalid character at " + i);
            cur = (cur << 4) | v;
            if (++nib == 2) { buf[bi++] = (byte) cur; nib = 0; cur = 0; }
        }
        Uuid256 r = fromBytes(buf, 0);
        if (strict && !r.isStrict()) throw new FormatException(ErrorKind.VERSION, "unsupported version/variant");
        return r;
    }

    // Equality / ordering: numeric == big-endian byte order == canonical-text order (§7.1)
    @Override public boolean equals(Object o) { return o instanceof Uuid256 u && a == u.a && b == u.b && c == u.c && d == u.d; }
    @Override public int hashCode() { return Long.hashCode(a ^ b * 31 ^ c * 961 ^ d * 29791); }
    @Override public int compareTo(Uuid256 o) {
        int r = Long.compareUnsigned(a, o.a); if (r != 0) return r;
        r = Long.compareUnsigned(b, o.b); if (r != 0) return r;
        r = Long.compareUnsigned(c, o.c); if (r != 0) return r;
        return Long.compareUnsigned(d, o.d);
    }

    // ============================================================================
    //  Self-tests (spec §11 vectors, §3.2/§6 parser rules, live generation)
    // ============================================================================
    static int selfTest() {
        int fails = 0;
        String[][] vectors = {
            {"000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"},
            {"fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"},
        };
        for (int i = 0; i < vectors.length; i++) {
            final String rawHex = vectors[i][0];
            byte[] raw = HexFormat.of().parseHex(rawHex);
            setVersionAndVariant(raw, 0);
            Uuid256 id = fromBytes(raw);
            String txt = id.toString();
            boolean ok = txt.equals(vectors[i][1]) && id.isStrict()
                    && parse(txt).equals(id) && parse(txt.toUpperCase(Locale.ROOT)).equals(id)
                    && !parse(vectors[i][0], false).isStrict()                       // raw compact: lenient ok (ver != 4)
                    && kindOf(() -> parse(rawHex)) == ErrorKind.VERSION                 // strict rejects
                    && Arrays.equals(id.toBytes(), raw) && id.toCompact().equals(HexFormat.of().formatHex(raw));
            System.out.printf("  spec §11 vector %d: %s  %s%n", i + 1, ok ? "PASS" : "FAIL", txt);
            if (!ok) fails++;
        }
        {
            String nil = NIL.toString();
            boolean ok = kindOf(() -> parse("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f")) == ErrorKind.HYPHEN
                    && kindOf(() -> parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1")) == ErrorKind.LENGTH
                    && kindOf(() -> parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g")) == ErrorKind.CHAR
                    && kindOf(() -> parse(nil)) == ErrorKind.VERSION
                    && parse(nil, false).equals(NIL) && NIL.compareTo(MAX) < 0
                    && MAX.toString().equals("f".repeat(16) + "-" + "f".repeat(8) + "-" + "f".repeat(8) + "-" + "f".repeat(8) + "-" + "f".repeat(24));
            System.out.printf("  parser rules (§3.2/§6):  %s%n", ok ? "PASS" : "FAIL");
            if (!ok) fails++;
        }
        for (int i = 0; i < 3; i++) {
            Uuid256 id = randomUuid256();
            String txt = id.toString();
            // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
            boolean ok = id.isStrict() && txt.length() == 68 && txt.charAt(26) == '4' && "89ab".indexOf(txt.charAt(35)) >= 0 && parse(txt).equals(id);
            System.out.printf("  randomUuid256(): %s  %s%n", txt, ok ? "ok" : "BAD");
            if (!ok) fails++;
        }
        return fails;
    }
    private static ErrorKind kindOf(Runnable r) {
        try { r.run(); return null; } catch (FormatException e) { return e.kind; }
    }

    // ============================================================================
    //  Bulk exact duplicate check
    // ============================================================================
    static final int CHUNK_BITS = 24, CHUNK_IDS = 1 << CHUNK_BITS, CHUNK_MASK = CHUNK_IDS - 1;   // 512 MB chunks

    static byte[][] bulkGenerate(int n) {
        int chunks = (n + CHUNK_IDS - 1) / CHUNK_IDS;
        byte[][] store = new byte[chunks][];
        for (int c = 0; c < chunks; c++) {
            int idsHere = Math.min(CHUNK_IDS, n - c * CHUNK_IDS);
            byte[] buf = new byte[idsHere * SIZE];
            RNG.nextBytes(buf);                                                        // §5.2
            for (int p = 0; p < buf.length; p += SIZE) setVersionAndVariant(buf, p);   // §4
            store[c] = buf;
        }
        return store;
    }
    record Dup(int i, int j, Uuid256 id) {}

    static List<Dup> findDuplicates(byte[][] store, int n) {
        final int NB = 1 << 24;                                                        // bucket = top 24 bits (bytes 0..2)
        int[] start = new int[NB + 1];
        for (int i = 0; i < n; i++) { byte[] s = store[i >>> CHUNK_BITS]; int p = (i & CHUNK_MASK) * SIZE;
            start[((s[p] & 0xFF) << 16 | (s[p + 1] & 0xFF) << 8 | (s[p + 2] & 0xFF)) + 1]++; }
        for (int b = 0; b < NB; b++) start[b + 1] += start[b];                         // exclusive prefix sums
        int[] cursor = start.clone();
        int[] order = new int[n];
        for (int i = 0; i < n; i++) { byte[] s = store[i >>> CHUNK_BITS]; int p = (i & CHUNK_MASK) * SIZE;
            order[cursor[(s[p] & 0xFF) << 16 | (s[p + 1] & 0xFF) << 8 | (s[p + 2] & 0xFF)]++] = i; }
        List<Dup> dups = new ArrayList<>();
        for (int b = 0; b < NB; b++) {
            int lo = start[b], hi = start[b + 1];
            if (hi - lo < 2) continue;
            for (int x = lo; x < hi; x++) for (int y = x + 1; y < hi; y++) {           // buckets are tiny (n / 16M)
                int i = order[x], j = order[y];
                byte[] si = store[i >>> CHUNK_BITS], sj = store[j >>> CHUNK_BITS];
                int pi = (i & CHUNK_MASK) * SIZE, pj = (j & CHUNK_MASK) * SIZE;
                if (Arrays.equals(si, pi, pi + SIZE, sj, pj, pj + SIZE))
                    dups.add(new Dup(Math.min(i, j), Math.max(i, j), fromBytes(si, pi)));
            }
        }
        return dups;
    }
    static String f(long v) { return String.format(Locale.US, "%,d", v); }
    static int parseArg(String s, String flag) {                                       // friendly rejection instead of a NumberFormatException trace
        try { return Integer.parseInt(s); } catch (NumberFormatException e) { System.out.println(flag + ": invalid number '" + s + "'"); System.exit(2); return 0; }
    }

    public static void main(String[] args) {
        if (args.length >= 2 && (args[0].equals("-p") || args[0].equals("-P"))) {          // parse mode: -p strict, -P lenient
            try { System.out.println("ok " + parse(args[1], args[0].equals("-p")).toCompact()); return; }
            catch (FormatException e) { System.out.println("error " + e.kind.name().toLowerCase(Locale.ROOT)); System.exit(1); }
        }
        int n = 100_000_000, planted = 0;
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("-g")) {                                                // just print ids: -g [count]
                int count = 1;
                if (i + 1 < args.length) try { count = Math.max(0, Integer.parseInt(args[i + 1])); } catch (NumberFormatException ignored) {}   // -g N: exactly N (0 allowed); junk → 1
                for (int k = 0; k < count; k++) System.out.println(randomUuid256());
                return;
            } else if (args[i].equals("-n") && i + 1 < args.length) n = parseArg(args[++i], "-n");
            else if (args[i].equals("-i") && i + 1 < args.length) planted = parseArg(args[++i], "-i");
            else { System.out.println("usage: java uuid256.java [-g [count]] [-n count] [-i planted_dups] | -p|-P <text>"); System.exit(2); }
        }
        if (n < 2 || planted < 0 || planted > n / 2) { System.out.println("-n must be >= 2 and -i at most n/2"); System.exit(2); }

        System.out.println("UUID256 reference implementation (Java) — README.md (256-bit random, 16-8-8-8-24 text)\n");
        System.out.println("Self-tests:");
        if (selfTest() > 0) { System.out.println("  self-test FAILED — aborting"); System.exit(1); }

        final int K = 1_000_000;
        long t0 = System.nanoTime();
        for (int i = 0; i < K; i++) randomUuid256();
        double perCall = (System.nanoTime() - t0) / 1e9 / K;
        System.out.printf(Locale.US, "%nrandomUuid256() per-call cost: %.2f µs → %.2f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate)%n",
                perCall * 1e6, 1 / perCall / 1e6, 1e9 * perCall / 60);

        System.out.printf(Locale.US, "%nBulk exact duplicate check: n=%s ids, planted duplicates=%d, RAM ~%.1f GB%n", f(n), planted, n * 36.0 / 1e9);
        t0 = System.nanoTime();
        byte[][] store = bulkGenerate(n);
        double tGen = (System.nanoTime() - t0) / 1e9;
        // planted duplicates: id[dst] := id[src] — sources evenly spaced over the lower half, each mirrored
        // into the upper half, so all 2K positions are distinct and no source is itself a target (K <= n/2).
        int plantStep = planted > 0 ? (n / 2) / planted : 0;
        for (int k = 0; k < planted; k++) {
            int src = plantStep * k, dst = n - 1 - src;
            System.arraycopy(store[src >>> CHUNK_BITS], (src & CHUNK_MASK) * SIZE, store[dst >>> CHUNK_BITS], (dst & CHUNK_MASK) * SIZE, SIZE);
            System.out.printf("  planted: id[%s] := id[%s]%n", f(dst), f(src));
        }
        long bad = 0;
        for (int i = 0; i < n; i++) { byte[] s = store[i >>> CHUNK_BITS]; int p = (i & CHUNK_MASK) * SIZE;
            if (((s[p + 12] & 0xFF) >> 4) != VERSION || ((s[p + 16] & 0xFF) >> 6) != 0b10) bad++; }
        List<Dup> dups = findDuplicates(store, n);
        double tAll = (System.nanoTime() - t0) / 1e9;
        for (Dup d : dups) System.out.printf("  DUPLICATE  id[%s] == id[%s]  %s%n", f(d.i()), f(d.j()), d.id());
        int rtOk = 0, step = Math.max(1, n / 1000);
        for (int i = 0; i < n; i += step) { Uuid256 id = fromBytes(store[i >>> CHUNK_BITS], (i & CHUNK_MASK) * SIZE); if (parse(id.toString()).equals(id)) rtOk++; }

        System.out.println("\n==== RESULT ====");
        System.out.printf(Locale.US, "ids generated:                   %s   (SecureRandom + §4 in %.1fs; bucket-sort+compare in %.1fs)%n", f(n), tGen, tAll - tGen);
        System.out.printf("version/variant violations:      %s%n", f(bad));
        System.out.printf("text round-trips (sampled):      %s ok%n", f(rtOk));
        System.out.printf("FULL 256-bit DUPLICATES:         %s%s%n", f(dups.size()),
                planted > 0 ? "   (planted: " + planted + " — " + (dups.size() == planted ? "all detected" : "COUNT MISMATCH") + ")" : "");
        if (dups.isEmpty()) System.out.printf("  → no duplicates among %s ids%n", f(n));
        double log2p = 2 * (Math.log(n) / Math.log(2)) - 251;
        System.out.printf(Locale.US, "expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e%n", log2p, Math.pow(2, log2p));
        System.exit(dups.size() == planted ? 0 : 1);
    }
}