#!/usr/bin/env julia
# uuid256.jl — reference implementation of README.md (UUID256, random layout) in Julia 1.9+.  Stdlib only.
#
#   julia uuid256.jl                    # self-tests + exact duplicate check over 10,000,000 ids
#   julia uuid256.jl -n 2000000 -i 3    # 2e6 ids with 3 planted duplicates (proves detection)
#   julia uuid256.jl -g [count]         # just print one (or count) new ids, nothing else
#
#   include("uuid256.jl"); using .Uuid256
#   id  = Uuid256.generate()            # Vector{UInt8}(32), §5.1: RandomDevice (OS CSPRNG), ver=4 / var=10 applied
#   txt = Uuid256.to_canonical(id)      # §3.1: "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"
#   b   = Uuid256.parse(txt)            # §6: strict; parse(txt; strict=false) lenient; throws Uuid256.ParseError(kind, msg)
#
# Bulk check: one RandomDevice read for all ids, §4 applied to each, 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.

module Uuid256
using Random: RandomDevice

const SIZE = 32
const TEXT_LEN = 68                                   # 64 hex + 4 hyphens
const VERSION = 0x4
const HYPHENS = (17, 26, 35, 44)                      # 1-based offsets in canonical text
const STRICT_RE = r"^[0-9a-f]{16}-[0-9a-f]{8}-4[0-9a-f]{7}-[89ab][0-9a-f]{7}-[0-9a-f]{24}\z"   # \z, not $: PCRE $ also matches before a final newline
const NIL = zeros(UInt8, SIZE)                        # §8
const MAX = fill(0xff, SIZE)
const RNG = RandomDevice()                            # §5.2 — OS CSPRNG

struct ParseError <: Exception
    kind::Symbol                                      # :length | :hyphen | :char | :version
    msg::String
end
Base.showerror(io::IO, e::ParseError) = print(io, "uuid256: ", e.msg)

"§4 — force version nibble (byte 13, 1-based) and variant bits (byte 17), in place from offset `off` (0-based)."
@inline function set_ver_var!(b::AbstractVector{UInt8}, off::Int=0)
    @inbounds b[off + 13] = (b[off + 13] & 0x0F) | (VERSION << 4)   # hex digit 24 = '4'
    @inbounds b[off + 17] = (b[off + 17] & 0x3F) | 0x80             # hex digit 32 in [89ab]
    b
end

"§5.1 — one id straight from the OS CSPRNG (32 bytes, big-endian: byte 1 most significant)."
generate() = set_ver_var!(rand(RNG, UInt8, SIZE))

"§6 — ver == 4 && var == 10."
is_strict(b::AbstractVector{UInt8}) = length(b) == SIZE && (b[13] >> 4) == VERSION && (b[17] >> 6) == 0b10

"§3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars."
function to_canonical(b::AbstractVector{UInt8})
    length(b) == SIZE || throw(ArgumentError("UUID256 is exactly 32 bytes"))
    h = bytes2hex(b)                                  # 64 lowercase hex digits
    string(h[1:16], '-', h[17:24], '-', h[25:32], '-', h[33:40], '-', h[41:64])
end

"§6 — parse canonical (68) or compact (64) form, any case."
function parse(s::AbstractString; strict::Bool=true)
    t = lowercase(String(s))
    cu = codeunits(t)                                 # index by byte, never by char: t[17] would throw on multibyte input
    if length(cu) == TEXT_LEN
        all(i -> cu[i] == UInt8('-'), HYPHENS) || throw(ParseError(:hyphen, "hyphen at wrong position"))
        t = replace(t, "-" => "")
    elseif length(cu) != 64
        throw(ParseError(:length, "wrong length $(length(cu))"))
    end
    occursin(r"^[0-9a-f]{64}\z", t) || throw(ParseError(:char, "invalid character"))
    b = hex2bytes(t)
    strict && !is_strict(b) && throw(ParseError(:version, "unsupported version/variant"))
    b
end
end # module

using .Uuid256
using Printf

# ---------------------------------------------------------------------------
# Self-tests (spec §11 vectors, §3.2/§6 parser rules, live generation)
# ---------------------------------------------------------------------------
kindof(s; strict=true) = try Uuid256.parse(s; strict=strict); :ok catch e; e isa Uuid256.ParseError ? e.kind : rethrow() end

function self_test()
    fails = 0
    vectors = [
        ("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"),
        ("fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"),
    ]
    for (i, (raw, expected)) in enumerate(vectors)
        b = Uuid256.set_ver_var!(hex2bytes(raw))
        txt = Uuid256.to_canonical(b)
        ok = txt == expected && Uuid256.is_strict(b) && Uuid256.parse(txt) == b && Uuid256.parse(uppercase(txt)) == b &&
             occursin(Uuid256.STRICT_RE, txt) && kindof(raw; strict=false) == :ok && kindof(raw) == :version   # raw compact: lenient ok, strict rejects
        println("  spec §11 vector $i: $(ok ? "PASS" : "FAIL")  $txt")
        ok || (fails += 1)
    end
    nil_txt = Uuid256.to_canonical(Uuid256.NIL)
    ok = kindof("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f") == :hyphen &&
         kindof("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1") == :length &&
         kindof("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g") == :char &&
         kindof(nil_txt) == :version && kindof(nil_txt; strict=false) == :ok && Uuid256.parse(nil_txt; strict=false) == Uuid256.NIL &&
         Uuid256.to_canonical(Uuid256.MAX) == join(["f"^16, "f"^8, "f"^8, "f"^8, "f"^24], "-") && Uuid256.NIL < Uuid256.MAX
    println("  parser rules (§3.2/§6):  $(ok ? "PASS" : "FAIL")")
    ok || (fails += 1)
    for _ in 1:3
        b = Uuid256.generate(); txt = Uuid256.to_canonical(b)
        ok = Uuid256.is_strict(b) && occursin(Uuid256.STRICT_RE, txt) && Uuid256.parse(txt) == b
        println("  generate(): $txt  $(ok ? "ok" : "BAD")")
        ok || (fails += 1)
    end
    fails
end

# ---------------------------------------------------------------------------
# Bulk exact duplicate check
# ---------------------------------------------------------------------------
function bulk_generate(n::Int)
    buf = rand(Uuid256.RNG, UInt8, n * 32)                          # §5.2, one call
    @inbounds for i in 0:n-1
        Uuid256.set_ver_var!(buf, i * 32)                            # §4
    end
    buf
end

@inline bucket(buf, i) = (Int(buf[i*32+1]) << 16) | (Int(buf[i*32+2]) << 8) | Int(buf[i*32+3])   # top 24 bits

function find_duplicates(buf::Vector{UInt8}, n::Int)
    NB = 1 << 24
    start = zeros(UInt32, NB + 1)
    @inbounds for i in 0:n-1; start[bucket(buf, i) + 2] += 1; end
    @inbounds for b in 1:NB; start[b + 1] += start[b]; end            # exclusive prefix sums (start[b+1] = first index of bucket b)
    cursor = copy(start)
    order = Vector{UInt32}(undef, n)
    @inbounds for i in 0:n-1
        b = bucket(buf, i) + 1
        order[cursor[b] + 1] = i; cursor[b] += 1
    end
    dups = Tuple{Int,Int,Vector{UInt8}}[]
    @inbounds for b in 1:NB
        lo, hi = Int(start[b]), Int(start[b + 1])
        hi - lo < 2 && continue
        for x in lo+1:hi, y in x+1:hi                                  # buckets are tiny (n / 16M)
            i, j = Int(order[x]), Int(order[y])
            vi = view(buf, i*32+1:i*32+32); vj = view(buf, j*32+1:j*32+32)
            vi == vj && push!(dups, (min(i, j), max(i, j), collect(vi)))
        end
    end
    dups
end

commas(v::Integer) = replace(string(v), r"(?<=\d)(?=(\d{3})+$)" => ",")

function main(args)
    n = 10_000_000; planted = 0
    if length(args) >= 2 && args[1] in ("-p", "-P")                          # parse mode: -p strict, -P lenient
        try
            println("ok ", bytes2hex(Uuid256.parse(args[2]; strict = args[1] == "-p")))
            return 0
        catch e
            e isa Uuid256.ParseError || rethrow()
            println("error ", e.kind); return 1
        end
    end
    i = 1
    while i <= length(args)
        a = args[i]
        if a == "-g"                                                     # just print ids: -g [count]
            c = i + 1 <= length(args) ? tryparse(Int, args[i + 1]) : nothing
            count = (c === nothing || c < 0) ? 1 : c                              # -g N: exactly N (0 allowed); junk → 1
            for _ in 1:count; println(Uuid256.to_canonical(Uuid256.generate())); end
            return 0
        elseif a == "-n" && i + 1 <= length(args); i += 1; n = Base.parse(Int, args[i])
        elseif a == "-i" && i + 1 <= length(args); i += 1; planted = Base.parse(Int, args[i])
        else println("usage: julia uuid256.jl [-g [count]] [-n count] [-i planted_dups]"); return 2 end
        i += 1
    end
    (n < 2 || planted < 0 || planted > n ÷ 2) && (println("-n must be >= 2 and -i at most n/2"); return 2)

    println("UUID256 reference implementation (Julia) — README.md (256-bit random, 16-8-8-8-24 text)\n")
    println("Self-tests:")
    self_test() > 0 && (println("  self-test FAILED — aborting"); return 1)

    K = 200_000
    t0 = time_ns(); for _ in 1:K; Uuid256.generate(); end
    per_call = (time_ns() - t0) / 1e9 / K
    @printf("\ngenerate() per-call cost: %.2f µs → %.2f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate)\n", per_call * 1e6, 1 / per_call / 1e6, 1e9 * per_call / 60)

    println("\nBulk exact duplicate check: n=$(commas(n)) ids, planted duplicates=$planted, RAM ~$(round(n * 36 / 1e9, digits=1)) GB")
    t0 = time_ns()
    buf = bulk_generate(n)
    t_gen = (time_ns() - t0) / 1e9
    for k in 0:planted-1                                                 # id[dst] := id[src]
        src = k * ((n ÷ 2) ÷ planted); dst = n - 1 - src                    # stride: distinct pairs for every k < planted <= n/2
        buf[dst*32+1:dst*32+32] = buf[src*32+1:src*32+32]
        println("  planted: id[$(commas(dst))] := id[$(commas(src))]")
    end
    bad = 0
    @inbounds for i in 0:n-1; ((buf[i*32+13] >> 4) != Uuid256.VERSION || (buf[i*32+17] >> 6) != 0b10) && (bad += 1); end
    dups = find_duplicates(buf, n)
    t_all = (time_ns() - t0) / 1e9
    for (i, j, b) in dups; println("  DUPLICATE  id[$(commas(i))] == id[$(commas(j))]  $(Uuid256.to_canonical(b))"); end
    step = max(1, n ÷ 1000); rt_ok = 0
    for i in 0:step:n-1
        id = buf[i*32+1:i*32+32]
        Uuid256.parse(Uuid256.to_canonical(id)) == id && (rt_ok += 1)
    end

    println("\n==== RESULT ====")
    @printf("ids generated:                   %s   (RandomDevice + §4 in %.1fs; bucket-sort+compare in %.1fs)\n", commas(n), t_gen, t_all - t_gen)
    println("version/variant violations:      $(commas(bad))")
    println("text round-trips (sampled):      $(commas(rt_ok)) ok")
    println("FULL 256-bit DUPLICATES:         $(commas(length(dups)))" * (planted > 0 ? "   (planted: $planted — $(length(dups) == planted ? "all detected" : "COUNT MISMATCH"))" : ""))
    isempty(dups) && println("  → no duplicates among $(commas(n)) ids")
    log2p = 2 * log2(n) - 251
    @printf("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e\n", log2p, 2.0^log2p)
    length(dups) == planted ? 0 : 1
end

if abspath(PROGRAM_FILE) == @__FILE__
    exit(main(ARGS))
end