#!/usr/bin/env swift
// uuid256.swift — reference implementation of README.md (UUID256, random layout) in Swift 5.9+.  No packages.
//
//   Run:
//       swift uuid256.swift -g 3                        # immediate mode: fine for self-tests / printing ids
//       swiftc -O -o /tmp/uuid256-swift uuid256.swift && /tmp/uuid256-swift        # optimized: for the 1e8 bulk check
//       /tmp/uuid256-swift -n 5000000 -i 3              # 5e6 ids with 3 planted duplicates (proves detection)
//   Library use: copy the `UUID256` struct into your module.
//
//       let id  = UUID256.generate()                    // §5.1: 32 bytes from the OS CSPRNG, ver=4 / var=10 applied
//       let txt = id.description                        // §3.1: 16-8-8-8-24, lowercase, 68 chars
//       let b   = try UUID256.parse(txt)                // §6: strict; parse(txt, strict: false) is lenient; throws UUID256.ParseError
//       UUID256 is Hashable, Comparable (byte order == text order), Codable (as canonical text), LosslessStringConvertible.
//
// Bulk check: all randomness from the OS CSPRNG into one [UInt8], §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.

#if canImport(Darwin)
import Darwin
#elseif canImport(Glibc)
import Glibc
#endif
import Foundation

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

/// §5.2 — fill a buffer from the OS cryptographically secure random source.
@inline(__always)
func osRandom(_ p: UnsafeMutableRawBufferPointer) {
    #if canImport(Darwin)
    arc4random_buf(p.baseAddress, p.count)
    #elseif canImport(Glibc)
    var off = 0
    while off < p.count {
        let r = getrandom(p.baseAddress! + off, p.count - off, 0)
        if r < 0 { if errno == EINTR { continue }; perror("getrandom"); exit(1) }
        off += r
    }
    #else
    #error("no OS random source")
    #endif
}

public struct UUID256: Hashable, Comparable, CustomStringConvertible, LosslessStringConvertible, Codable {
    public static let size = 32            // bytes
    public static let textLength = 68      // 64 hex + 4 hyphens
    public static let versionNumber: UInt8 = 4

    /// Big-endian encoding: bytes[0] is the most significant byte.
    public let bytes: [UInt8]

    public enum ParseError: Error, Equatable { case length, hyphen, character, version }

    public static let null = UUID256(unchecked: [UInt8](repeating: 0x00, count: 32))    // §8 ("nil" is a keyword)
    public static let max  = UUID256(unchecked: [UInt8](repeating: 0xFF, count: 32))

    private init(unchecked b: [UInt8]) { bytes = b }

    /// From a 32-byte big-endian encoding (no ver/var validation; see `isStrict`).
    public init?(bytes b: [UInt8]) {
        guard b.count == UUID256.size else { return nil }
        bytes = b
    }

    /// §4 — force version nibble (byte 12) and variant bits (byte 16).
    @inline(__always)
    public static func setVersionAndVariant(_ b: UnsafeMutablePointer<UInt8>) {
        b[12] = (b[12] & 0x0F) | (versionNumber << 4)     // hex digit 24 = '4'
        b[16] = (b[16] & 0x3F) | 0x80                     // hex digit 32 in [89ab]
    }

    /// §5.1 — a new id straight from the OS CSPRNG.
    public static func generate() -> UUID256 {
        var b = [UInt8](repeating: 0, count: size)
        b.withUnsafeMutableBufferPointer { p in
            osRandom(UnsafeMutableRawBufferPointer(p))
            setVersionAndVariant(p.baseAddress!)
        }
        return UUID256(unchecked: b)
    }

    public var version: Int { Int(bytes[12] >> 4) }
    public var variant: Int { Int(bytes[16] >> 6) }
    /// §6 — ver == 4 && var == 10.
    public var isStrict: Bool { version == Int(UUID256.versionNumber) && variant == 0b10 }

    /// §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars.
    public var description: String {
        let hex: [UInt8] = Array("0123456789abcdef".utf8)
        var out = [UInt8](repeating: UInt8(ascii: "-"), count: UUID256.textLength)
        var o = 0
        for i in 0..<UUID256.size {
            out[o] = hex[Int(bytes[i] >> 4)]
            out[o + 1] = hex[Int(bytes[i] & 0x0F)]
            o += 2
            if i == 7 || i == 11 || i == 15 || i == 19 { o += 1 }   // hyphen after hex digits 16, 24, 32, 40
        }
        return String(decoding: out, as: UTF8.self)
    }
    /// The 64-hex-digit compact form (input-only per §3.2 rule 4).
    public var compact: String { description.filter { $0 != "-" } }

    /// §6 — canonical (68) or compact (64) form, any case; strict checks ver/var.
    public static func parse(_ s: String, strict: Bool = true) throws -> UUID256 {
        let u = Array(s.utf8)
        let hyphenated: Bool
        switch u.count {
        case textLength:
            let dash = UInt8(ascii: "-")
            guard u[16] == dash, u[25] == dash, u[34] == dash, u[43] == dash else { throw ParseError.hyphen }
            hyphenated = true
        case 64: hyphenated = false
        default: throw ParseError.length
        }
        var out = [UInt8](repeating: 0, count: size)
        var nib = 0, bi = 0, cur = 0
        for i in 0..<u.count {
            if hyphenated && (i == 16 || i == 25 || i == 34 || i == 43) { continue }
            let c = u[i]
            let v: Int
            switch c {
            case 0x30...0x39: v = Int(c) - 0x30           // 0-9
            case 0x61...0x66: v = Int(c) - 0x61 + 10      // a-f
            case 0x41...0x46: v = Int(c) - 0x41 + 10      // A-F
            default: throw ParseError.character
            }
            cur = (cur << 4) | v
            nib += 1
            if nib == 2 { out[bi] = UInt8(cur); bi += 1; nib = 0; cur = 0 }
        }
        let r = UUID256(unchecked: out)
        if strict && !r.isStrict { throw ParseError.version }
        return r
    }

    /// LosslessStringConvertible — strict parse, nil on failure.
    public init?(_ description: String) {
        guard let v = try? UUID256.parse(description) else { return nil }
        self = v
    }

    // Ordering: numeric == big-endian byte order == canonical-text order (§7.1)
    public static func < (a: UUID256, b: UUID256) -> Bool { a.bytes.lexicographicallyPrecedes(b.bytes) }

    // Codable as canonical text (JSON string), strict on decode
    public init(from decoder: Decoder) throws {
        let s = try decoder.singleValueContainer().decode(String.self)
        self = try UUID256.parse(s)
    }
    public func encode(to encoder: Encoder) throws {
        var c = encoder.singleValueContainer()
        try c.encode(description)
    }
}

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

func unhex(_ h: String) -> [UInt8] {
    let u = Array(h.utf8)
    return stride(from: 0, to: u.count, by: 2).map { UInt8(String(decoding: u[$0..<$0 + 2], as: UTF8.self), radix: 16)! }
}

func selfTest() -> Int {
    var fails = 0
    let vectors = [
        ("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"),
        ("fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"),
    ]
    for (i, (raw, expected)) in vectors.enumerated() {
        var b = unhex(raw)
        b.withUnsafeMutableBufferPointer { UUID256.setVersionAndVariant($0.baseAddress!) }
        let id = UUID256(bytes: b)!
        let txt = id.description
        var strictErr: UUID256.ParseError? = nil
        do { _ = try UUID256.parse(raw) } catch let e as UUID256.ParseError { strictErr = e } catch {}
        let ok = txt == expected && id.isStrict
            && (try? UUID256.parse(txt)) == id && (try? UUID256.parse(txt.uppercased())) == id
            && (try? UUID256.parse(raw, strict: false))?.isStrict == false          // raw compact: lenient ok (ver != 4)
            && strictErr == .version                                              // strict rejects
            && UUID256(txt) == id && id.compact == txt.filter { $0 != "-" }
            && (try? JSONDecoder().decode([UUID256].self, from: JSONEncoder().encode([id]))) == [id]
        print("  spec §11 vector \(i + 1): \(ok ? "PASS" : "FAIL")  \(txt)")
        if !ok { fails += 1 }
    }
    do {
        func err(_ s: String, strict: Bool = true) -> UUID256.ParseError? {
            do { _ = try UUID256.parse(s, strict: strict); return nil } catch let e as UUID256.ParseError { return e } catch { return nil }
        }
        let nilTxt = UUID256.null.description
        let ok = err("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f") == .hyphen
            && err("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1") == .length
            && err("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g") == .character
            && err(nilTxt) == .version && err(nilTxt, strict: false) == nil
            && (try? UUID256.parse(nilTxt, strict: false)) == UUID256.null && UUID256.null < UUID256.max
            && UUID256.max.description == String(repeating: "f", count: 16) + "-" + String(repeating: "f", count: 8) + "-" + String(repeating: "f", count: 8) + "-" + String(repeating: "f", count: 8) + "-" + String(repeating: "f", count: 24)
        print("  parser rules (§3.2/§6):  \(ok ? "PASS" : "FAIL")")
        if !ok { fails += 1 }
    }
    for _ in 0..<3 {
        let id = UUID256.generate()
        let txt = id.description
        let u = Array(txt.utf8)
        // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
        let ok = id.isStrict && u.count == 68 && u[26] == UInt8(ascii: "4") && "89ab".utf8.contains(u[35]) && (try? UUID256.parse(txt)) == id
        print("  generate(): \(txt)  \(ok ? "ok" : "BAD")")
        if !ok { fails += 1 }
    }
    return fails
}

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

struct Dup { let i: Int; let j: Int; let id: UUID256 }

func findDuplicates(_ buf: UnsafeMutableBufferPointer<UInt8>, _ n: Int) -> [Dup] {
    let NB = 1 << 24                                                       // bucket = top 24 bits (bytes 0..2)
    var start = [UInt32](repeating: 0, count: NB + 1)
    let d = UnsafePointer(buf.baseAddress!)
    @inline(__always) func bucket(_ i: Int) -> Int { let p = d + i * 32; return Int(p[0]) << 16 | Int(p[1]) << 8 | Int(p[2]) }
    start.withUnsafeMutableBufferPointer { st in
        for i in 0..<n { st[bucket(i) + 1] += 1 }
        for b in 0..<NB { st[b + 1] += st[b] }                             // exclusive prefix sums
    }
    var cursor = start
    var order = [UInt32](repeating: 0, count: n)
    cursor.withUnsafeMutableBufferPointer { cu in
        order.withUnsafeMutableBufferPointer { od in
            for i in 0..<n { let b = bucket(i); od[Int(cu[b])] = UInt32(i); cu[b] += 1 }
        }
    }
    var dups: [Dup] = []
    order.withUnsafeBufferPointer { od in
        for b in 0..<NB {
            let lo = Int(start[b]), hi = Int(start[b + 1])
            if hi - lo < 2 { continue }
            for x in lo..<hi {
                for y in (x + 1)..<hi {                                     // buckets are tiny (n / 16M)
                    let i = Int(od[x]), j = Int(od[y])
                    if memcmp(d + i * 32, d + j * 32, 32) == 0 {
                        dups.append(Dup(i: min(i, j), j: max(i, j), id: UUID256(bytes: Array(UnsafeBufferPointer(start: d + i * 32, count: 32)))!))
                    }
                }
            }
        }
    }
    return dups
}

func commas(_ v: Int) -> String {
    let f = NumberFormatter(); f.numberStyle = .decimal; f.locale = Locale(identifier: "en_US")
    return f.string(from: NSNumber(value: v)) ?? String(v)
}

func main() -> Int32 {
    var n = 100_000_000, planted = 0
    let args = Array(CommandLine.arguments.dropFirst())
    if args.count >= 2 && (args[0] == "-p" || args[0] == "-P") {                     // parse mode: -p strict, -P lenient
        do { let u = try UUID256.parse(args[1], strict: args[0] == "-p"); print("ok \(u.compact)"); return 0 }
        catch let e as UUID256.ParseError { print("error \(e == .character ? "char" : "\(e)")"); return 1 }
        catch { print("error unknown"); return 1 }
    }
    var k = 0
    while k < args.count {
        switch args[k] {
        case "-g":                                                          // just print ids: -g [count]
            var count = 1
            if k + 1 < args.count, let c = Int(args[k + 1]), c >= 0 { count = c }   // -g N: exactly N (0 allowed); junk → 1
            for _ in 0..<count { print(UUID256.generate()) }
            return 0
        case "-n" where k + 1 < args.count: k += 1; n = Int(args[k]) ?? 0
        case "-i" where k + 1 < args.count: k += 1; planted = Int(args[k]) ?? -1
        default: print("usage: uuid256-swift [-g [count]] [-n count] [-i planted_dups]"); return 2
        }
        k += 1
    }
    if n < 2 || n > Int(UInt32.max) || planted < 0 || planted > n / 2 {   // bucket counters and indices are UInt32
        print("-n must be 2..4294967295 and -i at most n/2"); return 2
    }

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

    let K = 1_000_000
    var t0 = Date()
    for _ in 0..<K { _ = UUID256.generate() }
    let perCall = Date().timeIntervalSince(t0) / Double(K)
    print(String(format: "\ngenerate() per-call cost: %.2f µs → %.2f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate)",
                 perCall * 1e6, 1 / perCall / 1e6, 1e9 * perCall / 60))

    print(String(format: "\nBulk exact duplicate check: n=%@ ids, planted duplicates=%d, RAM ~%.1f GB", commas(n), planted, Double(n) * 36 / 1e9))
    t0 = Date()
    let buf = UnsafeMutableBufferPointer<UInt8>.allocate(capacity: n * 32)
    defer { buf.deallocate() }
    osRandom(UnsafeMutableRawBufferPointer(buf))                            // §5.2
    let base = buf.baseAddress!
    for i in 0..<n { UUID256.setVersionAndVariant(base + i * 32) }         // §4
    let tGen = Date().timeIntervalSince(t0)
    // 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).
    let plantStep = planted > 0 ? (n / 2) / planted : 0
    for kk in 0..<planted {
        let src = plantStep * kk, dst = n - 1 - src
        (base + dst * 32).update(from: base + src * 32, count: 32)
        print("  planted: id[\(commas(dst))] := id[\(commas(src))]")
    }
    var bad = 0
    for i in 0..<n { let p = base + i * 32; if p[12] >> 4 != UUID256.versionNumber || p[16] >> 6 != 0b10 { bad += 1 } }
    let dups = findDuplicates(buf, n)
    let tAll = Date().timeIntervalSince(t0)
    for d in dups { print("  DUPLICATE  id[\(commas(d.i))] == id[\(commas(d.j))]  \(d.id)") }
    var rtOk = 0
    let step = Swift.max(1, n / 1000)
    for i in stride(from: 0, to: n, by: step) {
        let id = UUID256(bytes: Array(UnsafeBufferPointer(start: base + i * 32, count: 32)))!
        if (try? UUID256.parse(id.description)) == id { rtOk += 1 }
    }

    print("\n==== RESULT ====")
    print(String(format: "ids generated:                   %@   (OS CSPRNG + §4 in %.1fs; bucket-sort+compare in %.1fs)", commas(n), tGen, tAll - tGen))
    print("version/variant violations:      \(commas(bad))")
    print("text round-trips (sampled):      \(commas(rtOk)) ok")
    print("FULL 256-bit DUPLICATES:         \(commas(dups.count))" + (planted > 0 ? "   (planted: \(planted) — \(dups.count == planted ? "all detected" : "COUNT MISMATCH"))" : ""))
    if dups.isEmpty { print("  → no duplicates among \(commas(n)) ids") }
    let log2p = 2 * log2(Double(n)) - 251
    print(String(format: "expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e", log2p, pow(2.0, log2p)))
    return dups.count == planted ? 0 : 1
}

exit(main())