// uuid256.cpp — reference implementation of README.md (UUID256, random layout) in C++20.  Standard library only.
//
//   Build & run (any C++20 compiler; nothing is written into this directory if you build elsewhere):
//       c++ -std=c++20 -O3 -o /tmp/uuid256-cpp uuid256.cpp && /tmp/uuid256-cpp
//       /tmp/uuid256-cpp -n 5000000 -i 3     # 5e6 ids with 3 planted duplicates (proves detection)
//       /tmp/uuid256-cpp -g [count]          # just print one (or count) new ids, nothing else
//   Library use: copy the `uuid256` class (and os_random) into a header.
//
//       uuid256 id  = uuid256::generate();       // §5.1: 32 bytes from the OS CSPRNG, ver=4 / var=10 applied
//       std::string s = id.to_string();          // §3.1: 16-8-8-8-24, lowercase, 68 chars
//       auto r = uuid256::parse(s);              // §6: std::expected-like result: r.ok() ? r.value : r.error (strict)
//       auto l = uuid256::parse(s, /*strict=*/false);
//
// Bulk check: all randomness from the OS CSPRNG into one std::vector<uint8_t>, §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.

#include <algorithm>
#include <array>
#include <cctype>
#include <charconv>
#include <chrono>
#include <cmath>
#include <compare>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <optional>
#include <string>
#include <string_view>
#include <vector>

#if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__)
#  include <cstdlib>              // arc4random_buf
#  define UUID256_ARC4RANDOM 1
#elif defined(__linux__)
#  include <sys/random.h>         // getrandom
#  include <cerrno>
#  define UUID256_GETRANDOM 1
#else
#  include <fstream>              // /dev/urandom fallback
#endif

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

/// §5.2 — fill `n` bytes from the OS cryptographically secure random source.
inline void os_random(void* buf, std::size_t n) {
#if defined(UUID256_ARC4RANDOM)
    arc4random_buf(buf, n);
#elif defined(UUID256_GETRANDOM)
    auto* p = static_cast<unsigned char*>(buf);
    while (n) {
        ssize_t r = getrandom(p, n, 0);
        if (r < 0) { if (errno == EINTR) continue; std::perror("getrandom"); std::abort(); }
        p += r; n -= static_cast<std::size_t>(r);
    }
#else
    std::ifstream f("/dev/urandom", std::ios::binary);
    if (!f.read(static_cast<char*>(buf), static_cast<std::streamsize>(n))) { std::perror("/dev/urandom"); std::abort(); }
#endif
}

class uuid256 {
public:
    static constexpr std::size_t size = 32;          // bytes
    static constexpr std::size_t text_length = 68;   // 64 hex + 4 hyphens
    static constexpr int version_number = 4;

    enum class parse_error { none, length, hyphen, character, version };
    struct parse_result;                                                  // defined after the class (needs a complete uuid256)

    constexpr uuid256() = default;                                       // nil (§8)
    explicit constexpr uuid256(const std::array<std::uint8_t, size>& b) : bytes_(b) {}

    static constexpr uuid256 nil() { return uuid256{}; }
    static constexpr uuid256 max() { std::array<std::uint8_t, size> a{}; a.fill(0xFF); return uuid256{a}; }

    /// §4 — force version nibble (byte 12) and variant bits (byte 16) in a raw 32-byte buffer.
    static constexpr void set_version_and_variant(std::uint8_t* b) noexcept {
        b[12] = static_cast<std::uint8_t>((b[12] & 0x0F) | (version_number << 4));   // hex digit 24 = '4'
        b[16] = static_cast<std::uint8_t>((b[16] & 0x3F) | 0x80);                    // hex digit 32 in [89ab]
    }

    /// §5.1 — a new id straight from the OS CSPRNG.
    static uuid256 generate() {
        uuid256 u;
        os_random(u.bytes_.data(), size);
        set_version_and_variant(u.bytes_.data());
        return u;
    }

    /// Big-endian 32-byte encoding (no ver/var validation; see is_strict()).
    static uuid256 from_bytes(const std::uint8_t* p) { uuid256 u; std::memcpy(u.bytes_.data(), p, size); return u; }
    const std::array<std::uint8_t, size>& bytes() const noexcept { return bytes_; }
    const std::uint8_t* data() const noexcept { return bytes_.data(); }

    int version() const noexcept { return bytes_[12] >> 4; }
    int variant() const noexcept { return bytes_[16] >> 6; }
    /// §6 — ver == 4 && var == 10.
    bool is_strict() const noexcept { return version() == version_number && variant() == 0b10; }

    /// §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars.
    std::string to_string() const {
        static constexpr char hex[] = "0123456789abcdef";
        std::string out(text_length, '-');
        std::size_t o = 0;
        for (std::size_t i = 0; i < size; ++i) {
            out[o++] = hex[bytes_[i] >> 4];
            out[o++] = hex[bytes_[i] & 0x0F];
            if (i == 7 || i == 11 || i == 15 || i == 19) ++o;              // hyphen after hex digits 16, 24, 32, 40
        }
        return out;
    }
    /// The 64-hex-digit compact form (input-only per §3.2 rule 4).
    std::string to_compact() const { std::string s = to_string(); std::erase(s, '-'); return s; }

    /// §6 — canonical (68) or compact (64) form, any case; strict checks ver/var.
    static parse_result parse(std::string_view s, bool strict = true) noexcept;

    // Equality / ordering: numeric == big-endian byte order == canonical-text order (§7.1)
    friend bool operator==(const uuid256&, const uuid256&) = default;
    friend std::strong_ordering operator<=>(const uuid256& a, const uuid256& b) noexcept {
        int c = std::memcmp(a.bytes_.data(), b.bytes_.data(), size);
        return c < 0 ? std::strong_ordering::less : c > 0 ? std::strong_ordering::greater : std::strong_ordering::equal;
    }

private:
    static constexpr int hexval(char c) noexcept {
        return (c >= '0' && c <= '9') ? c - '0' : (c >= 'a' && c <= 'f') ? c - 'a' + 10 : (c >= 'A' && c <= 'F') ? c - 'A' + 10 : -1;
    }
    std::array<std::uint8_t, size> bytes_{};
};

struct uuid256::parse_result {
    uuid256 value{};
    parse_error error = parse_error::none;
    bool ok() const noexcept { return error == parse_error::none; }
    explicit operator bool() const noexcept { return ok(); }
};

inline uuid256::parse_result uuid256::parse(std::string_view s, bool strict) noexcept {
    parse_result r;
    bool hyphenated;
    if (s.size() == text_length) {
        if (s[16] != '-' || s[25] != '-' || s[34] != '-' || s[43] != '-') { r.error = parse_error::hyphen; return r; }
        hyphenated = true;
    } else if (s.size() == 64) hyphenated = false;
    else { r.error = parse_error::length; return r; }
    int nib = 0, cur = 0; std::size_t bi = 0;
    for (std::size_t i = 0; i < s.size(); ++i) {
        if (hyphenated && (i == 16 || i == 25 || i == 34 || i == 43)) continue;
        int v = hexval(s[i]);
        if (v < 0) { r.error = parse_error::character; r.value = uuid256{}; return r; }   // never hand back partial bytes
        cur = (cur << 4) | v;
        if (++nib == 2) { r.value.bytes_[bi++] = static_cast<std::uint8_t>(cur); nib = 0; cur = 0; }
    }
    if (strict && !r.value.is_strict()) { r.error = parse_error::version; r.value = uuid256{}; return r; }
    return r;
}

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

static std::array<std::uint8_t, 32> unhex32(std::string_view h) {
    std::array<std::uint8_t, 32> out{};
    for (std::size_t i = 0; i < 32; ++i) { unsigned v = 0; std::from_chars(h.data() + 2 * i, h.data() + 2 * i + 2, v, 16); out[i] = static_cast<std::uint8_t>(v); }
    return out;
}
static std::string upper(std::string s) { for (auto& c : s) c = static_cast<char>(std::toupper(static_cast<unsigned char>(c))); return s; }

static int self_test() {
    int fails = 0;
    const std::pair<const char*, const char*> vectors[] = {
        {"000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"},
        {"fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"},
    };
    int i = 0;
    for (auto [raw, expected] : vectors) {
        auto b = unhex32(raw);
        uuid256::set_version_and_variant(b.data());
        uuid256 id{b};
        std::string txt = id.to_string();
        auto p1 = uuid256::parse(txt), p2 = uuid256::parse(upper(txt));
        auto lenient = uuid256::parse(raw, false), strict = uuid256::parse(raw);
        bool ok = txt == expected && id.is_strict() && p1 && p1.value == id && p2 && p2.value == id
               && lenient && !lenient.value.is_strict()                          // raw compact: lenient ok (ver != 4)
               && strict.error == uuid256::parse_error::version                 // strict rejects
               && id.bytes() == b && id.to_compact() == [&]{ std::string c = txt; std::erase(c, '-'); return c; }();
        std::printf("  spec §11 vector %d: %s  %s\n", ++i, ok ? "PASS" : "FAIL", txt.c_str());
        fails += !ok;
    }
    {
        std::string nil = uuid256::nil().to_string();
        bool ok = uuid256::parse("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f").error == uuid256::parse_error::hyphen
               && uuid256::parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1").error == uuid256::parse_error::length
               && uuid256::parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g").error == uuid256::parse_error::character
               && uuid256::parse(nil).error == uuid256::parse_error::version
               && uuid256::parse(nil, false) && uuid256::parse(nil, false).value == uuid256::nil()
               && uuid256::nil() < uuid256::max()
               && uuid256::max().to_string() == std::string(16, 'f') + "-" + std::string(8, 'f') + "-" + std::string(8, 'f') + "-" + std::string(8, 'f') + "-" + std::string(24, 'f');
        std::printf("  parser rules (§3.2/§6):  %s\n", ok ? "PASS" : "FAIL");
        fails += !ok;
    }
    for (int k = 0; k < 3; ++k) {
        uuid256 id = uuid256::generate();
        std::string txt = id.to_string();
        // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
        auto p = uuid256::parse(txt);
        bool ok = id.is_strict() && txt.size() == 68 && txt[26] == '4' && std::string_view("89ab").find(txt[35]) != std::string_view::npos && p && p.value == id;
        std::printf("  generate(): %s  %s\n", txt.c_str(), ok ? "ok" : "BAD");
        fails += !ok;
    }
    return fails;
}

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

struct dup { std::size_t i, j; uuid256 id; };

static std::vector<dup> find_duplicates(const std::vector<std::uint8_t>& buf, std::size_t n) {
    constexpr std::size_t NB = 1u << 24;                                     // bucket = top 24 bits (bytes 0..2)
    std::vector<std::uint32_t> start(NB + 1, 0);
    const std::uint8_t* d = buf.data();
    auto bucket = [d](std::size_t i) { const std::uint8_t* p = d + i * 32; return (std::size_t(p[0]) << 16) | (std::size_t(p[1]) << 8) | p[2]; };
    for (std::size_t i = 0; i < n; ++i) ++start[bucket(i) + 1];
    for (std::size_t b = 0; b < NB; ++b) start[b + 1] += start[b];         // exclusive prefix sums
    std::vector<std::uint32_t> cursor(start);
    std::vector<std::uint32_t> order(n);
    for (std::size_t i = 0; i < n; ++i) order[cursor[bucket(i)]++] = static_cast<std::uint32_t>(i);
    std::vector<dup> dups;
    for (std::size_t b = 0; b < NB; ++b) {
        std::uint32_t lo = start[b], hi = start[b + 1];
        if (hi - lo < 2) continue;
        for (std::uint32_t x = lo; x < hi; ++x)
            for (std::uint32_t y = x + 1; y < hi; ++y) {                    // buckets are tiny (n / 16M)
                std::size_t i = order[x], j = order[y];
                if (std::memcmp(d + i * 32, d + j * 32, 32) == 0)
                    dups.push_back({std::min(i, j), std::max(i, j), uuid256::from_bytes(d + i * 32)});
            }
    }
    return dups;
}

static std::string commas(unsigned long long v) {
    std::string s = std::to_string(v), out;
    for (std::size_t i = 0; i < s.size(); ++i) { if (i && (s.size() - i) % 3 == 0) out += ','; out += s[i]; }
    return out;
}

/// Checked decimal parse for command-line numbers (atoi/atoll accept junk and overflow silently).
static bool parse_num(std::string_view a, unsigned long long& out) {
    auto [p, ec] = std::from_chars(a.data(), a.data() + a.size(), out, 10);
    return ec == std::errc() && p == a.data() + a.size() && !a.empty();
}

int main(int argc, char** argv) {
    std::size_t n = 100'000'000; int planted = 0;
    unsigned long long v = 0;
    if (argc >= 3 && (std::string_view(argv[1]) == "-p" || std::string_view(argv[1]) == "-P")) {   // parse mode: -p strict, -P lenient
        auto r = uuid256::parse(argv[2], std::string_view(argv[1]) == "-p");
        static const char* kinds[] = {"ok", "length", "hyphen", "char", "version"};
        if (r) { std::printf("ok %s\n", r.value.to_compact().c_str()); return 0; }
        std::printf("error %s\n", kinds[static_cast<int>(r.error)]); return 1;
    }
    for (int i = 1; i < argc; ++i) {
        std::string_view a = argv[i];
        if (a == "-g") {                                                     // just print ids: -g [count]
            unsigned long long count = 1;
            if (i + 1 < argc && parse_num(argv[i + 1], v)) count = v;               // -g N: exactly N (0 allowed); junk → 1
            for (unsigned long long k = 0; k < count; ++k) std::puts(uuid256::generate().to_string().c_str());
            return 0;
        }
        if (a == "-n" && i + 1 < argc && parse_num(argv[++i], v) && v <= 0xFFFFFFFFull) n = static_cast<std::size_t>(v);
        else if (a == "-i" && i + 1 < argc && parse_num(argv[++i], v) && v <= 0x7FFFFFFFull) planted = static_cast<int>(v);
        else { std::puts("usage: uuid256-cpp [-g [count]] [-n count(2..4294967295)] [-i planted_dups]"); return 2; }
    }
    if (n < 2 || n > 0xFFFFFFFFull || planted < 0 || static_cast<std::size_t>(planted) > n / 2) { std::puts("-n must be 2..4294967295 and -i at most n/2"); return 2; }

    std::puts("UUID256 reference implementation (C++20) — README.md (256-bit random, 16-8-8-8-24 text)\n");
    std::puts("Self-tests:");
    if (self_test()) { std::puts("  self-test FAILED — aborting"); return 1; }

    using clock = std::chrono::steady_clock;
    constexpr int K = 1'000'000;
    auto t0 = clock::now();
    for (int i = 0; i < K; ++i) { volatile auto id = uuid256::generate(); (void)id; }
    double per_call = std::chrono::duration<double>(clock::now() - t0).count() / K;
    std::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);

    std::printf("\nBulk exact duplicate check: n=%s ids, planted duplicates=%d, RAM ~%.1f GB\n", commas(n).c_str(), planted, n * 36.0 / 1e9);
    t0 = clock::now();
    std::vector<std::uint8_t> buf;
    try { buf.resize(n * 32); } catch (const std::bad_alloc&) { std::printf("out of memory: %zu ids need %.1f GB\n", n, n * 36.0 / 1e9); return 1; }
    os_random(buf.data(), buf.size());                                        // §5.2
    for (std::size_t p = 0; p < buf.size(); p += 32) uuid256::set_version_and_variant(buf.data() + p);   // §4
    auto t_gen = clock::now();
    // 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 std::size_t plant_step = planted ? (n / 2) / std::size_t(planted) : 0;
    for (int k = 0; k < planted; ++k) {
        std::size_t src = plant_step * std::size_t(k), dst = n - 1 - src;
        std::memcpy(buf.data() + dst * 32, buf.data() + src * 32, 32);
        std::printf("  planted: id[%s] := id[%s]\n", commas(dst).c_str(), commas(src).c_str());
    }
    std::size_t bad = 0;
    for (std::size_t p = 0; p < buf.size(); p += 32) if ((buf[p + 12] >> 4) != uuid256::version_number || (buf[p + 16] >> 6) != 0b10) ++bad;
    auto dups = find_duplicates(buf, n);
    auto t_all = clock::now();
    for (const auto& d : dups) std::printf("  DUPLICATE  id[%s] == id[%s]  %s\n", commas(d.i).c_str(), commas(d.j).c_str(), d.id.to_string().c_str());
    std::size_t rt_ok = 0, step = std::max<std::size_t>(1, n / 1000);
    for (std::size_t i = 0; i < n; i += step) { auto id = uuid256::from_bytes(buf.data() + i * 32); auto p = uuid256::parse(id.to_string()); if (p && p.value == id) ++rt_ok; }

    std::puts("\n==== RESULT ====");
    std::printf("ids generated:                   %s   (OS CSPRNG + §4 in %.1fs; bucket-sort+compare in %.1fs)\n", commas(n).c_str(),
                std::chrono::duration<double>(t_gen - t0).count(), std::chrono::duration<double>(t_all - t_gen).count());
    std::printf("version/variant violations:      %s\n", commas(bad).c_str());
    std::printf("text round-trips (sampled):      %s ok\n", commas(rt_ok).c_str());
    std::printf("FULL 256-bit DUPLICATES:         %s%s\n", commas(dups.size()).c_str(),
                planted ? (std::string("   (planted: ") + std::to_string(planted) + " — " + (dups.size() == std::size_t(planted) ? "all detected" : "COUNT MISMATCH") + ")").c_str() : "");
    if (dups.empty()) std::printf("  → no duplicates among %s ids\n", commas(n).c_str());
    double log2p = 2 * std::log2(double(n)) - 251;
    std::printf("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e\n", log2p, std::pow(2.0, log2p));
    return dups.size() == std::size_t(planted) ? 0 : 1;
}