#!/usr/bin/env dotnet
#:property Optimize=true
#:property Nullable=enable
// uuid256.cs — reference implementation of README.md (UUID256, random layout) for .NET.
//
//   Run (needs .NET 10 SDK, file-based app, no project file):
//       dotnet run uuid256.cs                      # self-tests + exact duplicate check over 100,000,000 ids
//       dotnet run uuid256.cs -- -n 5000000 -i 3   # 5e6 ids with 3 planted duplicates (proves detection)
//       dotnet run uuid256.cs -- -g [count]        # just print one (or count) new ids, nothing else
//   Or as a library: copy the `Uuid256` struct below into any .NET 8+ project.
//
//   Uuid256 id  = Uuid256.NewUuid256();            // §5.1: 32 bytes from RandomNumberGenerator, ver=4/var=10
//   string txt  = id.ToString();                   // §3.1: 16-8-8-8-24, lowercase, 68 chars
//   Uuid256 b   = Uuid256.Parse(txt);              // §6: strict (ver/var checked); Parse(txt, strict:false) lenient
//   id.TryWriteBytes(span32) / Uuid256.FromBytes(span32) — big-endian, byte 0 = most significant.
//
// Bulk check: all randomness from RandomNumberGenerator.Fill (§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.

using System;
using System.Buffers.Binary;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Security.Cryptography;

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

/// <summary>A 256-bit random unique identifier (README.md spec). Immutable value type, 32 bytes.</summary>
public readonly struct Uuid256 : IEquatable<Uuid256>, IComparable<Uuid256>
{
    public const int Size = 32;          // bytes
    public const int TextLength = 68;    // 64 hex + 4 hyphens
    public const int VersionNumber = 4;

    // Four big-endian 64-bit words: A = bytes 0..7 (text group 1), B = 8..15 (group 2 + first half of 3), ...
    private readonly ulong _a, _b, _c, _d;

    private Uuid256(ulong a, ulong b, ulong c, ulong d) { _a = a; _b = b; _c = c; _d = d; }

    public static readonly Uuid256 Nil = default;                                              // §8
    public static readonly Uuid256 Max = new(ulong.MaxValue, ulong.MaxValue, ulong.MaxValue, ulong.MaxValue);

    /// <summary>§4 — force version nibble (byte 12) and variant bits (byte 16) in a raw 32-byte buffer.</summary>
    public static void SetVersionAndVariant(Span<byte> b)
    {
        b[12] = (byte)((b[12] & 0x0F) | (VersionNumber << 4));   // hex digit 24 = '4'
        b[16] = (byte)((b[16] & 0x3F) | 0x80);                   // hex digit 32 in [89ab]
    }

    /// <summary>§5.1 — a new id straight from the OS CSPRNG.</summary>
    public static Uuid256 NewUuid256()
    {
        Span<byte> b = stackalloc byte[Size];
        RandomNumberGenerator.Fill(b);
        SetVersionAndVariant(b);
        return FromBytes(b);
    }

    /// <summary>Big-endian 32-byte encoding → value (no validation; use IsStrict to check ver/var).</summary>
    public static Uuid256 FromBytes(ReadOnlySpan<byte> b)
    {
        if (b.Length != Size) throw new ArgumentException("UUID256 is exactly 32 bytes", nameof(b));
        return new Uuid256(BinaryPrimitives.ReadUInt64BigEndian(b), BinaryPrimitives.ReadUInt64BigEndian(b[8..]),
                           BinaryPrimitives.ReadUInt64BigEndian(b[16..]), BinaryPrimitives.ReadUInt64BigEndian(b[24..]));
    }

    public bool TryWriteBytes(Span<byte> dst)
    {
        if (dst.Length < Size) return false;
        BinaryPrimitives.WriteUInt64BigEndian(dst, _a); BinaryPrimitives.WriteUInt64BigEndian(dst[8..], _b);
        BinaryPrimitives.WriteUInt64BigEndian(dst[16..], _c); BinaryPrimitives.WriteUInt64BigEndian(dst[24..], _d);
        return true;
    }
    public byte[] ToByteArray() { var r = new byte[Size]; TryWriteBytes(r); return r; }

    /// <summary>Version nibble (byte 12 high nibble); 4 for this spec.</summary>
    public int Version => (int)((_b >> 28) & 0xF);
    /// <summary>Variant bits (byte 16 top two bits); 0b10 for this spec.</summary>
    public int Variant => (int)(_c >> 62);
    /// <summary>§6 — ver == 4 &amp;&amp; var == 10.</summary>
    public bool IsStrict => Version == VersionNumber && Variant == 0b10;

    /// <summary>§3.1 — canonical text: 16-8-8-8-24, lowercase.</summary>
    public override string ToString()
    {
        return string.Create(TextLength, this, static (span, v) =>
        {
            Span<byte> b = stackalloc byte[Size];
            v.TryWriteBytes(b);
            ReadOnlySpan<char> hex = "0123456789abcdef";
            int o = 0;
            for (int i = 0; i < Size; i++)
            {
                span[o++] = hex[b[i] >> 4];
                span[o++] = hex[b[i] & 0xF];
                if (i == 7 || i == 11 || i == 15 || i == 19) span[o++] = '-';   // after hex digits 16, 24, 32, 40
            }
        });
    }

    public enum ParseError { None, Length, Hyphen, Char, Version }

    /// <summary>§6 — canonical (68) or compact (64) form, any case.</summary>
    public static bool TryParse(ReadOnlySpan<char> s, bool strict, out Uuid256 value, out ParseError error)
    {
        value = default; error = ParseError.None;
        bool hyphenated;
        if (s.Length == TextLength)
        {
            if (s[16] != '-' || s[25] != '-' || s[34] != '-' || s[43] != '-') { error = ParseError.Hyphen; return false; }
            hyphenated = true;
        }
        else if (s.Length == 64) hyphenated = false;
        else { error = ParseError.Length; return false; }

        Span<byte> b = stackalloc byte[Size];
        int nib = 0, bi = 0, cur = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (hyphenated && (i == 16 || i == 25 || i == 34 || i == 43)) continue;
            int v = HexVal(s[i]);
            if (v < 0) { error = ParseError.Char; return false; }
            cur = (cur << 4) | v;
            if (++nib == 2) { b[bi++] = (byte)cur; nib = 0; cur = 0; }
        }
        var r = FromBytes(b);
        if (strict && !r.IsStrict) { error = ParseError.Version; return false; }
        value = r; return true;
    }
    public static bool TryParse(ReadOnlySpan<char> s, out Uuid256 value) => TryParse(s, strict: true, out value, out _);
    public static Uuid256 Parse(ReadOnlySpan<char> s, bool strict = true)
        => TryParse(s, strict, out var v, out var e) ? v : throw new FormatException($"invalid UUID256 ({e})");
    private static int HexVal(char c) => c switch { >= '0' and <= '9' => c - '0', >= 'a' and <= 'f' => c - 'a' + 10, >= 'A' and <= 'F' => c - 'A' + 10, _ => -1 };

    // Equality / ordering: numeric = big-endian byte order = canonical-text order (§7.1)
    public bool Equals(Uuid256 o) => _a == o._a && _b == o._b && _c == o._c && _d == o._d;
    public override bool Equals(object? obj) => obj is Uuid256 o && Equals(o);
    public override int GetHashCode() => HashCode.Combine(_a, _b, _c, _d);
    public int CompareTo(Uuid256 o)
    {
        int c = _a.CompareTo(o._a); if (c != 0) return c;
        c = _b.CompareTo(o._b); if (c != 0) return c;
        c = _c.CompareTo(o._c); if (c != 0) return c;
        return _d.CompareTo(o._d);
    }
    public static bool operator ==(Uuid256 x, Uuid256 y) => x.Equals(y);
    public static bool operator !=(Uuid256 x, Uuid256 y) => !x.Equals(y);
}

// ============================================================================
//  Program: self-tests + bulk exact duplicate check
// ============================================================================

static class Program
{
    static int SelfTest()
    {
        int fails = 0;
        var vectors = new[] {
            ("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"),
            ("fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"),
        };
        for (int i = 0; i < vectors.Length; i++)
        {
            var (raw, expected) = vectors[i];
            byte[] b = Convert.FromHexString(raw);
            Uuid256.SetVersionAndVariant(b);
            var id = Uuid256.FromBytes(b);
            string txt = id.ToString();
            bool ok = txt == expected && id.IsStrict
                   && Uuid256.Parse(txt) == id && Uuid256.Parse(txt.ToUpperInvariant()) == id
                   && Uuid256.TryParse(raw, strict: false, out var lenient, out _) && !lenient.IsStrict     // raw compact: lenient ok
                   && !Uuid256.TryParse(raw, strict: true, out _, out var e) && e == Uuid256.ParseError.Version   // strict rejects (ver != 4)
                   && id.ToByteArray().AsSpan().SequenceEqual(b);
            Console.WriteLine($"  spec §11 vector {i + 1}: {(ok ? "PASS" : "FAIL")}  {txt}");
            if (!ok) fails++;
        }
        {
            string nil = Uuid256.Nil.ToString();
            bool ok = !Uuid256.TryParse("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f", true, out _, out var e1) && e1 == Uuid256.ParseError.Hyphen
                   && !Uuid256.TryParse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1", true, out _, out var e2) && e2 == Uuid256.ParseError.Length
                   && !Uuid256.TryParse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g", true, out _, out var e3) && e3 == Uuid256.ParseError.Char
                   && !Uuid256.TryParse(nil, true, out _, out var e4) && e4 == Uuid256.ParseError.Version
                   && Uuid256.TryParse(nil, false, out var n2, out _) && n2 == Uuid256.Nil
                   && Uuid256.Max.ToString() == new string('f', 16) + "-" + new string('f', 8) + "-" + new string('f', 8) + "-" + new string('f', 8) + "-" + new string('f', 24)
                   && Uuid256.Nil.CompareTo(Uuid256.Max) < 0;
            Console.WriteLine($"  parser rules (§3.2/§6):  {(ok ? "PASS" : "FAIL")}");
            if (!ok) fails++;
        }
        for (int i = 0; i < 3; i++)
        {
            var id = Uuid256.NewUuid256(); string txt = id.ToString();
            // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
            bool ok = id.IsStrict && txt.Length == 68 && txt[26] == '4' && "89ab".Contains(txt[35]) && Uuid256.Parse(txt) == id;
            Console.WriteLine($"  NewUuid256(): {txt}  {(ok ? "ok" : "BAD")}");
            if (!ok) fails++;
        }
        return fails;
    }

    // ---- bulk storage: ids in 512 MB chunks (byte[] is limited to ~2 GB) --------------------------
    const int ChunkBits = 24;                       // 2^24 ids × 32 B = 512 MB per chunk
    const int ChunkIds = 1 << ChunkBits, ChunkMask = ChunkIds - 1;

    static byte[][] BulkGenerate(long n)
    {
        int chunks = (int)((n + ChunkIds - 1) / ChunkIds);
        var store = new byte[chunks][];
        for (int c = 0; c < chunks; c++)
        {
            long idsHere = Math.Min(ChunkIds, n - (long)c * ChunkIds);
            var buf = new byte[idsHere * Uuid256.Size];
            RandomNumberGenerator.Fill(buf);                             // §5.2
            for (int p = 0; p < buf.Length; p += Uuid256.Size) Uuid256.SetVersionAndVariant(buf.AsSpan(p, Uuid256.Size));   // §4
            store[c] = buf;
        }
        return store;
    }
    static Span<byte> Id(byte[][] store, long i) => store[(int)(i >> ChunkBits)].AsSpan((int)(i & ChunkMask) * Uuid256.Size, Uuid256.Size);

    static List<(long i, long j, Uuid256 id)> FindDuplicates(byte[][] store, long n)
    {
        const int BB = 24; const int NB = 1 << BB;                     // bucket = top 24 bits (bytes 0..2, all random)
        var start = new int[NB + 1];
        for (long i = 0; i < n; i++) { var s = Id(store, i); start[((s[0] << 16) | (s[1] << 8) | s[2]) + 1]++; }
        for (int b = 0; b < NB; b++) start[b + 1] += start[b];         // exclusive prefix sums
        var cursor = (int[])start.Clone();
        var order = new int[n];                                        // n ≤ int.MaxValue for this harness
        for (long i = 0; i < n; i++) { var s = Id(store, i); order[cursor[(s[0] << 16) | (s[1] << 8) | s[2]]++] = (int)i; }
        var dups = new List<(long, long, Uuid256)>();
        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)
                {
                    long i = order[x], j = order[y];
                    if (Id(store, i).SequenceEqual(Id(store, j)))
                        dups.Add((Math.Min(i, j), Math.Max(i, j), Uuid256.FromBytes(Id(store, i))));
                }
        }
        return dups;
    }

    static int Main(string[] args)
    {
        long n = 100_000_000; int planted = 0;
        if (args.Length >= 2 && (args[0] == "-p" || args[0] == "-P"))                     // parse mode: -p strict, -P lenient
        {
            if (Uuid256.TryParse(args[1], strict: args[0] == "-p", out var pv, out var pe)) { Console.WriteLine("ok " + Convert.ToHexString(pv.ToByteArray()).ToLowerInvariant()); return 0; }
            Console.WriteLine("error " + pe.ToString().ToLowerInvariant()); return 1;
        }
        for (int i = 0; i < args.Length; i++)
        {
            if (args[i] == "-g")                                            // just print ids: -g [count]
            {
                long count = i + 1 < args.Length && long.TryParse(args[i + 1], NumberStyles.None, CultureInfo.InvariantCulture, out var c) ? c : 1;
                for (long k = 0; k < count; k++) Console.WriteLine(Uuid256.NewUuid256());
                return 0;
            }
            if (args[i] == "-n" && i + 1 < args.Length && long.TryParse(args[i + 1], NumberStyles.None, CultureInfo.InvariantCulture, out var nv)) { n = nv; i++; }
            else if (args[i] == "-i" && i + 1 < args.Length && int.TryParse(args[i + 1], NumberStyles.None, CultureInfo.InvariantCulture, out var iv)) { planted = iv; i++; }
            else { Console.WriteLine("usage: dotnet run uuid256.cs -- [-g [count]] [-n count] [-i planted_dups] | -p|-P <text>"); return 2; }
        }
        if (n < 2 || n > int.MaxValue || planted < 0 || planted > n / 2) { Console.WriteLine("-n must be 2..2147483647 and -i at most n/2"); return 2; }
        string F(long v) => v.ToString("N0", CultureInfo.InvariantCulture);

        Console.WriteLine("UUID256 reference implementation (C# / .NET) — README.md (256-bit random, 16-8-8-8-24 text)\n");
        Console.WriteLine("Self-tests:");
        if (SelfTest() > 0) { Console.WriteLine("  self-test FAILED — aborting"); return 1; }

        var sw = Stopwatch.StartNew(); const int K = 1_000_000;
        for (int i = 0; i < K; i++) Uuid256.NewUuid256();
        double perCall = sw.Elapsed.TotalSeconds / K;
        Console.WriteLine($"\nNewUuid256() per-call cost: {perCall * 1e6:F2} µs → {1 / perCall / 1e6:F2} M ids/s single-threaded " +
                          $"(1e9 ids would take ~{1e9 * perCall / 60:F0} min just to generate)");

        Console.WriteLine($"\nBulk exact duplicate check: n={F(n)} ids, planted duplicates={planted}, RAM ~{n * 36 / 1e9:F1} GB");
        sw.Restart();
        var store = BulkGenerate(n);
        var tGen = sw.Elapsed;
        // 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).
        long plantStep = planted > 0 ? (n / 2) / planted : 0;
        for (int k = 0; k < planted; k++)
        {
            long src = plantStep * k, dst = n - 1 - src;
            Id(store, src).CopyTo(Id(store, dst));
            Console.WriteLine($"  planted: id[{F(dst)}] := id[{F(src)}]");
        }
        long bad = 0;
        for (long i = 0; i < n; i++) { var s = Id(store, i); if ((s[12] >> 4) != Uuid256.VersionNumber || (s[16] >> 6) != 0b10) bad++; }
        var dups = FindDuplicates(store, n);
        var tAll = sw.Elapsed;
        foreach (var (i, j, id) in dups) Console.WriteLine($"  DUPLICATE  id[{F(i)}] == id[{F(j)}]  {id}");
        long rtOk = 0, step = Math.Max(1, n / 1000);
        for (long i = 0; i < n; i += step) { var id = Uuid256.FromBytes(Id(store, i)); if (Uuid256.Parse(id.ToString()) == id) rtOk++; }

        Console.WriteLine("\n==== RESULT ====");
        Console.WriteLine($"ids generated:                   {F(n)}   (RandomNumberGenerator.Fill + §4 in {tGen.TotalSeconds:F1}s; bucket-sort+compare in {(tAll - tGen).TotalSeconds:F1}s)");
        Console.WriteLine($"version/variant violations:      {F(bad)}");
        Console.WriteLine($"text round-trips (sampled):      {F(rtOk)} ok");
        Console.WriteLine($"FULL 256-bit DUPLICATES:         {F(dups.Count)}" + (planted > 0 ? $"   (planted: {planted} — {(dups.Count == planted ? "all detected" : "COUNT MISMATCH")})" : ""));
        if (dups.Count == 0) Console.WriteLine($"  → no duplicates among {F(n)} ids");
        double log2p = 2 * Math.Log2(n) - 251;
        Console.WriteLine($"expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^{log2p:F1} ≈ {Math.Pow(2, log2p):E1}");
        return dups.Count == planted ? 0 : 1;
    }
}