//! uuid256.zig — reference implementation of README.md (UUID256, random layout) in Zig 0.16.  Std only.
//!
//!   zig run -OReleaseFast uuid256.zig                  # self-tests + exact duplicate check over 100,000,000 ids
//!   zig run -OReleaseFast uuid256.zig -- -n 5000000 -i 3   # 5e6 ids with 3 planted duplicates (proves detection)
//!   zig run uuid256.zig -- -g [count]                  # just print one (or count) new ids, nothing else
//!   (zig run builds into the global cache; nothing is written into this directory)
//!
//!   const id  = Uuid256.generate(io);                  // §5.1: 32 bytes from the Io CSPRNG, ver=4 / var=10 applied
//!   const txt = id.toCanonical();                      // §3.1: [68]u8 "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"
//!   const b   = try Uuid256.parse(txt[0..], true);     // §6: strict; parse(s, false) is lenient; error.{Length,Hyphen,Char,Version}
//!   Uuid256 formats with "{f}" as canonical text.
//!
//! Bulk check: all randomness from io.random (§5.2 — CSPRNG seeded from OS entropy) into one []u8, §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.

const std = @import("std");
const Io = std.Io;

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

pub const Uuid256 = struct {
    pub const size = 32; // bytes
    pub const text_length = 68; // 64 hex + 4 hyphens
    pub const version_number: u8 = 4;

    /// Big-endian: bytes[0] is the most significant byte.
    bytes: [size]u8,

    pub const nil: Uuid256 = .{ .bytes = [_]u8{0x00} ** size }; // §8
    pub const max: Uuid256 = .{ .bytes = [_]u8{0xff} ** size };

    pub const ParseError = error{ Length, Hyphen, Char, Version };

    /// §4 — force version nibble (byte 12) and variant bits (byte 16), in place.  Takes a pointer to
    /// exactly 32 bytes so a short buffer is a compile error rather than an unchecked write in ReleaseFast.
    pub fn setVersionAndVariant(b: *[size]u8) void {
        b[12] = (b[12] & 0x0F) | (version_number << 4); // hex digit 24 = '4'
        b[16] = (b[16] & 0x3F) | 0x80; // hex digit 32 in [89ab]
    }

    /// §5.1 — a new id from the CSPRNG behind `io` (seeded from OS entropy).
    pub fn generate(io: Io) Uuid256 {
        var u: Uuid256 = undefined;
        io.random(&u.bytes);
        setVersionAndVariant(&u.bytes);
        return u;
    }

    /// From a 32-byte big-endian encoding (no ver/var validation; see isStrict).
    pub fn fromBytes(b: *const [size]u8) Uuid256 {
        return .{ .bytes = b.* };
    }

    pub fn version(u: Uuid256) u8 {
        return u.bytes[12] >> 4;
    }
    pub fn variant(u: Uuid256) u8 {
        return u.bytes[16] >> 6;
    }
    /// §6 — ver == 4 && var == 10.
    pub fn isStrict(u: Uuid256) bool {
        return u.version() == version_number and u.variant() == 0b10;
    }

    /// §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars.
    pub fn toCanonical(u: Uuid256) [text_length]u8 {
        const hex = "0123456789abcdef";
        var out: [text_length]u8 = undefined;
        var o: usize = 0;
        for (u.bytes, 0..) |b, i| {
            out[o] = hex[b >> 4];
            out[o + 1] = hex[b & 0x0F];
            o += 2;
            if (i == 7 or i == 11 or i == 15 or i == 19) { // after hex digits 16, 24, 32, 40
                out[o] = '-';
                o += 1;
            }
        }
        return out;
    }
    /// The 64-hex-digit compact form (input-only per §3.2 rule 4).
    pub fn toCompact(u: Uuid256) [64]u8 {
        return std.fmt.bytesToHex(u.bytes, .lower);
    }

    /// §6 — canonical (68) or compact (64) form, any case; strict checks ver/var.
    pub fn parse(s: []const u8, strict: bool) ParseError!Uuid256 {
        const hyphenated = switch (s.len) {
            text_length => blk: {
                if (s[16] != '-' or s[25] != '-' or s[34] != '-' or s[43] != '-') return error.Hyphen;
                break :blk true;
            },
            64 => false,
            else => return error.Length,
        };
        var u: Uuid256 = .{ .bytes = undefined };
        var nib: u2 = 0;
        var bi: usize = 0;
        var cur: u8 = 0;
        for (s, 0..) |c, i| {
            if (hyphenated and (i == 16 or i == 25 or i == 34 or i == 43)) continue;
            const v: u8 = switch (c) {
                '0'...'9' => c - '0',
                'a'...'f' => c - 'a' + 10,
                'A'...'F' => c - 'A' + 10,
                else => return error.Char,
            };
            cur = (cur << 4) | v;
            nib += 1;
            if (nib == 2) {
                u.bytes[bi] = cur;
                bi += 1;
                nib = 0;
                cur = 0;
            }
        }
        if (strict and !u.isStrict()) return error.Version;
        return u;
    }

    pub fn eql(a: Uuid256, b: Uuid256) bool {
        return std.mem.eql(u8, &a.bytes, &b.bytes);
    }
    /// Numeric == big-endian byte order == canonical-text order (§7.1).
    pub fn order(a: Uuid256, b: Uuid256) std.math.Order {
        return std.mem.order(u8, &a.bytes, &b.bytes);
    }
    /// `{f}` formatting → canonical text.
    pub fn format(u: Uuid256, w: *Io.Writer) Io.Writer.Error!void {
        try w.writeAll(&u.toCanonical());
    }
};

// ============================================================================
//  Self-tests (spec §11 vectors, §3.2/§6 parser rules, live generation)
// ============================================================================

fn unhex32(h: []const u8) [32]u8 {
    var out: [32]u8 = undefined;
    _ = std.fmt.hexToBytes(&out, h) catch unreachable;
    return out;
}

fn parseErr(s: []const u8, strict: bool) ?Uuid256.ParseError {
    _ = Uuid256.parse(s, strict) catch |e| return e;
    return null;
}
fn failsWith(s: []const u8, strict: bool, expected: Uuid256.ParseError) bool {
    return if (parseErr(s, strict)) |e| e == expected else false;
}

fn selfTest(io: Io, out: *Io.Writer) !u32 {
    var fails: u32 = 0;
    const vectors = [_][2][]const u8{
        .{ "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f" },
        .{ "fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0" },
    };
    for (vectors, 0..) |v, i| {
        var b = unhex32(v[0]);
        Uuid256.setVersionAndVariant(&b);
        const id = Uuid256.fromBytes(&b);
        const txt = id.toCanonical();
        var upper: [68]u8 = undefined;
        _ = std.ascii.upperString(&upper, &txt);
        const p1 = Uuid256.parse(&txt, true) catch Uuid256.nil;
        const p2 = Uuid256.parse(&upper, true) catch Uuid256.nil;
        const lenient = Uuid256.parse(v[0], false) catch Uuid256.nil; // raw compact: lenient ok (ver != 4)
        var compact_expect: [64]u8 = undefined;
        _ = std.mem.replace(u8, &txt, "-", "", &compact_expect);
        const ok = std.mem.eql(u8, &txt, v[1]) and id.isStrict() and p1.eql(id) and p2.eql(id) and
            !lenient.isStrict() and failsWith(v[0], true, error.Version) and // strict rejects
            std.mem.eql(u8, &id.toCompact(), &compact_expect);
        try out.print("  spec §11 vector {d}: {s}  {s}\n", .{ i + 1, if (ok) "PASS" else "FAIL", txt });
        if (!ok) fails += 1;
    }
    {
        const nil_txt = Uuid256.nil.toCanonical();
        const max_txt = Uuid256.max.toCanonical();
        const ok = failsWith("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f", true, error.Hyphen) and
            failsWith("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1", true, error.Length) and
            failsWith("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g", true, error.Char) and
            failsWith(&nil_txt, true, error.Version) and parseErr(&nil_txt, false) == null and
            (Uuid256.parse(&nil_txt, false) catch Uuid256.max).eql(Uuid256.nil) and
            Uuid256.nil.order(Uuid256.max) == .lt and
            std.mem.eql(u8, &max_txt, "ffffffffffffffff-ffffffff-ffffffff-ffffffff-ffffffffffffffffffffffff");
        try out.print("  parser rules (§3.2/§6):  {s}\n", .{if (ok) "PASS" else "FAIL"});
        if (!ok) fails += 1;
    }
    for (0..3) |_| {
        const id = Uuid256.generate(io);
        const txt = id.toCanonical();
        // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
        const p = Uuid256.parse(&txt, true) catch Uuid256.nil;
        const ok = id.isStrict() and txt[26] == '4' and std.mem.indexOfScalar(u8, "89ab", txt[35]) != null and p.eql(id);
        try out.print("  generate(): {f}  {s}\n", .{ id, if (ok) "ok" else "BAD" });
        if (!ok) fails += 1;
    }
    return fails;
}

// ============================================================================
//  Bulk exact duplicate check
// ============================================================================

const Dup = struct { i: usize, j: usize, id: Uuid256 };

fn findDuplicates(gpa: std.mem.Allocator, buf: []const u8, n: usize) ![]Dup {
    const NB: usize = 1 << 24; // bucket = top 24 bits (bytes 0..2)
    const start = try gpa.alloc(u32, NB + 1);
    defer gpa.free(start);
    @memset(start, 0);
    for (0..n) |i| {
        const p = buf[i * 32 ..];
        start[(@as(usize, p[0]) << 16 | @as(usize, p[1]) << 8 | p[2]) + 1] += 1;
    }
    for (0..NB) |b| start[b + 1] += start[b]; // exclusive prefix sums
    const cursor = try gpa.alloc(u32, NB + 1);
    defer gpa.free(cursor);
    @memcpy(cursor, start);
    const order = try gpa.alloc(u32, n);
    defer gpa.free(order);
    for (0..n) |i| {
        const p = buf[i * 32 ..];
        const b = @as(usize, p[0]) << 16 | @as(usize, p[1]) << 8 | p[2];
        order[cursor[b]] = @intCast(i);
        cursor[b] += 1;
    }
    var dups: std.ArrayList(Dup) = .empty;
    for (0..NB) |b| {
        const lo = start[b];
        const hi = start[b + 1];
        if (hi - lo < 2) continue;
        var x = lo;
        while (x < hi) : (x += 1) {
            var y = x + 1;
            while (y < hi) : (y += 1) { // buckets are tiny (n / 16M)
                const i: usize = order[x];
                const j: usize = order[y];
                if (std.mem.eql(u8, buf[i * 32 ..][0..32], buf[j * 32 ..][0..32])) {
                    try dups.append(gpa, .{ .i = @min(i, j), .j = @max(i, j), .id = Uuid256.fromBytes(buf[i * 32 ..][0..32]) });
                }
            }
        }
    }
    return dups.toOwnedSlice(gpa);
}

fn commas(v: u64, buf: *[32]u8) []const u8 {
    var tmp: [24]u8 = undefined;
    const digits = std.fmt.bufPrint(&tmp, "{d}", .{v}) catch unreachable;
    var o: usize = 0;
    for (digits, 0..) |c, i| {
        if (i > 0 and (digits.len - i) % 3 == 0) {
            buf[o] = ',';
            o += 1;
        }
        buf[o] = c;
        o += 1;
    }
    return buf[0..o];
}

fn secs(d: Io.Duration) f64 {
    return @as(f64, @floatFromInt(d.toNanoseconds())) / 1e9;
}

pub fn main(init: std.process.Init) !void {
    const io = init.io;
    const arena = init.arena.allocator();
    const gpa = init.gpa;
    var stdout_buffer: [4096]u8 = undefined;
    var stdout_writer: Io.File.Writer = .init(.stdout(), io, &stdout_buffer);
    const out = &stdout_writer.interface;
    defer out.flush() catch {};

    const args = try init.minimal.args.toSlice(arena);
    if (args.len >= 3 and (std.mem.eql(u8, args[1], "-p") or std.mem.eql(u8, args[1], "-P"))) { // parse mode: -p strict, -P lenient
        if (Uuid256.parse(args[2], std.mem.eql(u8, args[1], "-p"))) |u| {
            try out.print("ok {s}\n", .{&u.toCompact()});
            try out.flush();
            return;
        } else |e| {
            try out.print("error {s}\n", .{switch (e) { error.Length => "length", error.Hyphen => "hyphen", error.Char => "char", error.Version => "version" }});
            try out.flush();
            std.process.exit(1);
        }
    }
    var n: usize = 100_000_000;
    var planted: usize = 0;
    var k: usize = 1;
    while (k < args.len) : (k += 1) {
        const a = args[k];
        if (std.mem.eql(u8, a, "-g")) { // just print ids: -g [count]
            var count: usize = 1;
            if (k + 1 < args.len) count = std.fmt.parseUnsigned(usize, args[k + 1], 10) catch 1; // -g N: exactly N (0 allowed); junk → 1
            for (0..count) |_| try out.print("{f}\n", .{Uuid256.generate(io)});
            return;
        } else if (std.mem.eql(u8, a, "-n") and k + 1 < args.len) {
            k += 1;
            n = std.fmt.parseUnsigned(usize, args[k], 10) catch {
                try out.print("-n: invalid number '{s}'\n", .{args[k]});
                try out.flush();
                std.process.exit(2);
            };
        } else if (std.mem.eql(u8, a, "-i") and k + 1 < args.len) {
            k += 1;
            planted = std.fmt.parseUnsigned(usize, args[k], 10) catch {
                try out.print("-i: invalid number '{s}'\n", .{args[k]});
                try out.flush();
                std.process.exit(2);
            };
        } else {
            try out.writeAll("usage: uuid256-zig [-g [count]] [-n count] [-i planted_dups]\n");
            try out.flush();
            std.process.exit(2);
        }
    }
    if (n < 2 or n > std.math.maxInt(u32) or planted > n / 2) {
        try out.writeAll("-n must be 2..4294967295 and -i at most n/2\n");
        try out.flush();
        std.process.exit(2);
    }
    var cb: [32]u8 = undefined;
    var cb2: [32]u8 = undefined;

    try out.writeAll("UUID256 reference implementation (Zig) — README.md (256-bit random, 16-8-8-8-24 text)\n\n");
    try out.writeAll("Self-tests:\n");
    if (try selfTest(io, out) > 0) {
        try out.writeAll("  self-test FAILED — aborting\n");
        try out.flush();
        std.process.exit(1);
    }

    const K: usize = 1_000_000;
    var t0 = Io.Clock.awake.now(io);
    var sink: u8 = 0;
    for (0..K) |_| sink ^= Uuid256.generate(io).bytes[31];
    std.mem.doNotOptimizeAway(sink);
    const per_call = secs(t0.durationTo(Io.Clock.awake.now(io))) / @as(f64, @floatFromInt(K));
    try out.print("\ngenerate() per-call cost: {d:.2} µs → {d:.2} M ids/s single-threaded (1e9 ids would take ~{d:.0} min just to generate)\n", .{ per_call * 1e6, 1 / per_call / 1e6, 1e9 * per_call / 60 });

    try out.print("\nBulk exact duplicate check: n={s} ids, planted duplicates={d}, RAM ~{d:.1} GB\n", .{ commas(n, &cb), planted, @as(f64, @floatFromInt(n)) * 36 / 1e9 });
    try out.flush();
    t0 = Io.Clock.awake.now(io);
    const buf = try gpa.alloc(u8, n * 32);
    defer gpa.free(buf);
    io.random(buf); // §5.2
    for (0..n) |i| Uuid256.setVersionAndVariant(buf[i * 32 ..][0..32]); // §4
    const t_gen = t0.durationTo(Io.Clock.awake.now(io));
    // 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).
    const plant_step: usize = if (planted > 0) (n / 2) / planted else 0;
    for (0..planted) |kk| {
        const src = plant_step * kk;
        const dst = n - 1 - src;
        @memcpy(buf[dst * 32 ..][0..32], buf[src * 32 ..][0..32]);
        try out.print("  planted: id[{s}] := id[{s}]\n", .{ commas(dst, &cb), commas(src, &cb2) });
    }
    var bad: usize = 0;
    for (0..n) |i| {
        const p = buf[i * 32 ..];
        if ((p[12] >> 4) != Uuid256.version_number or (p[16] >> 6) != 0b10) bad += 1;
    }
    const dups = try findDuplicates(gpa, buf, n);
    defer gpa.free(dups);
    const t_all = t0.durationTo(Io.Clock.awake.now(io));
    for (dups) |d| try out.print("  DUPLICATE  id[{s}] == id[{s}]  {f}\n", .{ commas(d.i, &cb), commas(d.j, &cb2), d.id });
    var rt_ok: usize = 0;
    const step = @max(1, n / 1000);
    var i: usize = 0;
    while (i < n) : (i += step) {
        const id = Uuid256.fromBytes(buf[i * 32 ..][0..32]);
        const p = Uuid256.parse(&id.toCanonical(), true) catch Uuid256.nil;
        if (p.eql(id)) rt_ok += 1;
    }

    try out.writeAll("\n==== RESULT ====\n");
    try out.print("ids generated:                   {s}   (io.random + §4 in {d:.1}s; bucket-sort+compare in {d:.1}s)\n", .{ commas(n, &cb), secs(t_gen), secs(t_all) - secs(t_gen) });
    try out.print("version/variant violations:      {s}\n", .{commas(bad, &cb)});
    try out.print("text round-trips (sampled):      {s} ok\n", .{commas(rt_ok, &cb)});
    try out.print("FULL 256-bit DUPLICATES:         {s}", .{commas(dups.len, &cb)});
    if (planted > 0) try out.print("   (planted: {d} — {s})", .{ planted, if (dups.len == planted) "all detected" else "COUNT MISMATCH" });
    try out.writeAll("\n");
    if (dups.len == 0) try out.print("  → no duplicates among {s} ids\n", .{commas(n, &cb)});
    const log2p = 2 * std.math.log2(@as(f64, @floatFromInt(n))) - 251;
    try out.print("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^{d:.1} ≈ {e:.1}\n", .{ log2p, std.math.pow(f64, 2, log2p) });
    try out.flush();
    if (dups.len != planted) std.process.exit(1);
}