// uuid256.kt — reference implementation of README.md (UUID256, random layout) in Kotlin/JVM.  Stdlib + JDK only.
//
//   Build & run (kotlinc needs a JDK; macOS/Homebrew: export JAVA_HOME=/opt/homebrew/opt/openjdk/libexec/openjdk.jdk/Contents/Home):
//       kotlinc uuid256.kt -include-runtime -d /tmp/uuid256.jar && java -Xmx6g -jar /tmp/uuid256.jar
//       java -jar /tmp/uuid256.jar -n 5000000 -i 3     # 5e6 ids with 3 planted duplicates (proves detection)
//       java -jar /tmp/uuid256.jar -g [count]          # just print one (or count) new ids, nothing else
//   Library use: copy the Uuid256 class into your module.
//
//       val id  = Uuid256.random()                    // §5.1: 32 bytes from SecureRandom, ver=4 / var=10 applied
//       val txt = id.toString()                       // §3.1: 16-8-8-8-24, lowercase, 68 chars
//       val b   = Uuid256.parse(txt)                  // §6: strict; parse(txt, strict = false) is lenient; throws Uuid256.ParseException
//
// Bulk check: all randomness from SecureRandom (§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.

import java.security.SecureRandom
import kotlin.math.ln
import kotlin.math.max
import kotlin.math.min
import kotlin.math.pow
import kotlin.system.exitProcess

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

/** A 256-bit random unique identifier (README.md spec). Immutable; wraps a defensively copied 32-byte array. */
class Uuid256 private constructor(private val b: ByteArray) : Comparable<Uuid256> {

    enum class ErrorKind { LENGTH, HYPHEN, CHAR, VERSION }
    class ParseException(val kind: ErrorKind, message: String) : IllegalArgumentException(message)

    companion object {
        const val SIZE = 32            // bytes
        const val TEXT_LENGTH = 68     // 64 hex + 4 hyphens
        const val VERSION = 4
        private val RNG = SecureRandom()                                              // §5.2
        private const val HEX = "0123456789abcdef"

        val NIL = Uuid256(ByteArray(SIZE))                                             // §8
        val MAX = Uuid256(ByteArray(SIZE) { 0xFF.toByte() })

        /** §4 — force version nibble (byte 12) and variant bits (byte 16) in a raw buffer. */
        fun setVersionAndVariant(buf: ByteArray, off: Int = 0) {
            buf[off + 12] = ((buf[off + 12].toInt() and 0x0F) or (VERSION shl 4)).toByte()   // hex digit 24 = '4'
            buf[off + 16] = ((buf[off + 16].toInt() and 0x3F) or 0x80).toByte()             // hex digit 32 in [89ab]
        }

        /** §5.1 — a new id straight from the OS CSPRNG. */
        fun random(): Uuid256 {
            val buf = ByteArray(SIZE)
            RNG.nextBytes(buf)
            setVersionAndVariant(buf)
            return Uuid256(buf)
        }

        /** From a 32-byte big-endian encoding (copied; no ver/var validation — see isStrict). */
        fun fromBytes(buf: ByteArray, off: Int = 0): Uuid256 {
            require(off >= 0 && buf.size - off >= SIZE) { "UUID256 is exactly 32 bytes" }
            return Uuid256(buf.copyOfRange(off, off + SIZE))
        }

        /** §6 — canonical (68) or compact (64) form, any case; strict checks ver/var. */
        fun parse(s: CharSequence, strict: Boolean = true): Uuid256 {
            val hyphenated = when (s.length) {
                TEXT_LENGTH -> {
                    if (s[16] != '-' || s[25] != '-' || s[34] != '-' || s[43] != '-') throw ParseException(ErrorKind.HYPHEN, "hyphen at wrong position")
                    true
                }
                64 -> false
                else -> throw ParseException(ErrorKind.LENGTH, "wrong length ${s.length}")
            }
            val out = ByteArray(SIZE)
            var nib = 0; var bi = 0; var cur = 0
            for (i in s.indices) {
                if (hyphenated && (i == 16 || i == 25 || i == 34 || i == 43)) continue
                val v = when (val c = s[i]) {
                    in '0'..'9' -> c - '0'
                    in 'a'..'f' -> c - 'a' + 10
                    in 'A'..'F' -> c - 'A' + 10
                    else -> throw ParseException(ErrorKind.CHAR, "invalid character at $i")
                }
                cur = (cur shl 4) or v
                if (++nib == 2) { out[bi++] = cur.toByte(); nib = 0; cur = 0 }
            }
            val r = Uuid256(out)
            if (strict && !r.isStrict) throw ParseException(ErrorKind.VERSION, "unsupported version/variant")
            return r
        }
        fun parseOrNull(s: CharSequence, strict: Boolean = true): Uuid256? = try { parse(s, strict) } catch (e: ParseException) { null }
    }

    /** The 32-byte big-endian encoding (a copy). */
    fun toBytes(): ByteArray = b.copyOf()
    val version: Int get() = (b[12].toInt() and 0xFF) shr 4
    val variant: Int get() = (b[16].toInt() and 0xFF) shr 6
    /** §6 — ver == 4 && var == 10. */
    val isStrict: Boolean get() = version == VERSION && variant == 0b10

    /** §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars. */
    override fun toString(): String {
        val sb = StringBuilder(TEXT_LENGTH)
        for (i in 0 until SIZE) {
            val v = b[i].toInt() and 0xFF
            sb.append(HEX[v shr 4]).append(HEX[v and 0x0F])
            if (i == 7 || i == 11 || i == 15 || i == 19) sb.append('-')          // after hex digits 16, 24, 32, 40
        }
        return sb.toString()
    }
    /** The 64-hex-digit compact form (input-only per §3.2 rule 4). */
    fun toCompact(): String = toString().replace("-", "")

    override fun equals(other: Any?): Boolean = other is Uuid256 && b.contentEquals(other.b)
    override fun hashCode(): Int = b.contentHashCode()
    /** Numeric == big-endian byte order == canonical-text order (§7.1). */
    override fun compareTo(other: Uuid256): Int {
        for (i in 0 until SIZE) {
            val d = (b[i].toInt() and 0xFF) - (other.b[i].toInt() and 0xFF)
            if (d != 0) return d
        }
        return 0
    }
}

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

private fun String.hexToBytes(): ByteArray = ByteArray(length / 2) { substring(2 * it, 2 * it + 2).toInt(16).toByte() }
private fun kindOf(s: String, strict: Boolean = true): Uuid256.ErrorKind? = try { Uuid256.parse(s, strict); null } catch (e: Uuid256.ParseException) { e.kind }

fun selfTest(): Int {
    var fails = 0
    val vectors = listOf(
        "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f" to "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f",
        "fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0" to "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0",
    )
    vectors.forEachIndexed { i, (raw, expected) ->
        val bytes = raw.hexToBytes().also { Uuid256.setVersionAndVariant(it) }
        val id = Uuid256.fromBytes(bytes)
        val txt = id.toString()
        val ok = txt == expected && id.isStrict &&
            Uuid256.parse(txt) == id && Uuid256.parse(txt.uppercase()) == id &&
            kindOf(raw, strict = false) == null && kindOf(raw) == Uuid256.ErrorKind.VERSION &&   // raw compact: lenient ok, strict rejects
            id.toBytes().contentEquals(bytes) && id.toCompact() == txt.replace("-", "")
        println("  spec §11 vector ${i + 1}: ${if (ok) "PASS" else "FAIL"}  $txt")
        if (!ok) fails++
    }
    run {
        val nil = Uuid256.NIL.toString()
        val ok = kindOf("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f") == Uuid256.ErrorKind.HYPHEN &&
            kindOf("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1") == Uuid256.ErrorKind.LENGTH &&
            kindOf("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g") == Uuid256.ErrorKind.CHAR &&
            kindOf(nil) == Uuid256.ErrorKind.VERSION && kindOf(nil, strict = false) == null &&
            Uuid256.parse(nil, strict = false) == Uuid256.NIL && Uuid256.parseOrNull(nil) == null &&
            Uuid256.NIL < Uuid256.MAX &&
            Uuid256.MAX.toString() == "f".repeat(16) + "-" + "f".repeat(8) + "-" + "f".repeat(8) + "-" + "f".repeat(8) + "-" + "f".repeat(24)
        println("  parser rules (§3.2/§6):  ${if (ok) "PASS" else "FAIL"}")
        if (!ok) fails++
    }
    repeat(3) {
        val id = Uuid256.random()
        val txt = id.toString()
        // string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
        val ok = id.isStrict && txt.length == 68 && txt[26] == '4' && txt[35] in "89ab" && Uuid256.parse(txt) == id
        println("  random(): $txt  ${if (ok) "ok" else "BAD"}")
        if (!ok) fails++
    }
    return fails
}

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

private const val CHUNK_BITS = 24; private const val CHUNK_IDS = 1 shl CHUNK_BITS; private const val CHUNK_MASK = CHUNK_IDS - 1   // 512 MB chunks
private val RNG = SecureRandom()

fun bulkGenerate(n: Int): Array<ByteArray> = Array((n + CHUNK_IDS - 1) / CHUNK_IDS) { c ->
    val idsHere = min(CHUNK_IDS, n - c * CHUNK_IDS)
    ByteArray(idsHere * Uuid256.SIZE).also { buf ->
        RNG.nextBytes(buf)                                                            // §5.2
        var p = 0
        while (p < buf.size) { Uuid256.setVersionAndVariant(buf, p); p += Uuid256.SIZE }   // §4
    }
}
private fun Array<ByteArray>.chunk(i: Int) = this[i ushr CHUNK_BITS]
private fun off(i: Int) = (i and CHUNK_MASK) * Uuid256.SIZE

data class Dup(val i: Int, val j: Int, val id: Uuid256)

fun findDuplicates(store: Array<ByteArray>, n: Int): List<Dup> {
    val NB = 1 shl 24                                                                  // bucket = top 24 bits (bytes 0..2)
    val start = IntArray(NB + 1)
    fun bucket(i: Int): Int { val s = store.chunk(i); val p = off(i); return (s[p].toInt() and 0xFF shl 16) or (s[p + 1].toInt() and 0xFF shl 8) or (s[p + 2].toInt() and 0xFF) }
    for (i in 0 until n) start[bucket(i) + 1]++
    for (b in 0 until NB) start[b + 1] += start[b]                                     // exclusive prefix sums
    val cursor = start.copyOf()
    val order = IntArray(n)
    for (i in 0 until n) order[cursor[bucket(i)]++] = i
    val dups = ArrayList<Dup>()
    for (b in 0 until NB) {
        val lo = start[b]; val hi = start[b + 1]
        if (hi - lo < 2) continue
        for (x in lo until hi) for (y in x + 1 until hi) {                             // buckets are tiny (n / 16M)
            val i = order[x]; val j = order[y]
            val si = store.chunk(i); val sj = store.chunk(j); val pi = off(i); val pj = off(j)
            if (java.util.Arrays.equals(si, pi, pi + Uuid256.SIZE, sj, pj, pj + Uuid256.SIZE))
                dups += Dup(min(i, j), max(i, j), Uuid256.fromBytes(si, pi))
        }
    }
    return dups
}

private fun f(v: Long) = "%,d".format(java.util.Locale.US, v)

fun main(args: Array<String>) {
    if (args.size >= 2 && (args[0] == "-p" || args[0] == "-P")) {                          // parse mode: -p strict, -P lenient
        try { println("ok " + Uuid256.parse(args[1], strict = args[0] == "-p").toCompact()); return }
        catch (e: Uuid256.ParseException) { println("error " + e.kind.name.lowercase()); exitProcess(1) }
    }
    var n = 100_000_000; var planted = 0
    var i = 0
    while (i < args.size) {
        when (args[i]) {
            "-g" -> {                                                                  // just print ids: -g [count]
                val count = args.getOrNull(i + 1)?.toIntOrNull()?.takeIf { it >= 0 } ?: 1   // -g N: exactly N (0 allowed); junk → 1
                repeat(count) { println(Uuid256.random()) }
                return
            }
            "-n", "-i" -> {
                val v = args.getOrNull(i + 1)?.toIntOrNull()
                if (v == null) { println("${args[i]}: invalid number '${args.getOrNull(i + 1) ?: ""}'"); exitProcess(2) }
                if (args[i] == "-n") n = v else planted = v
                i++
            }
            else -> { println("usage: java -jar uuid256.jar [-g [count]] [-n count] [-i planted_dups] | -p|-P <text>"); exitProcess(2) }
        }
        i++
    }
    if (n < 2 || planted < 0 || planted > n / 2) { println("-n must be >= 2 and -i at most n/2"); exitProcess(2) }

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

    val K = 1_000_000
    var t0 = System.nanoTime()
    repeat(K) { Uuid256.random() }
    val perCall = (System.nanoTime() - t0) / 1e9 / K
    println("\nrandom() per-call cost: %.2f µs → %.2f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate)".format(java.util.Locale.US, perCall * 1e6, 1 / perCall / 1e6, 1e9 * perCall / 60))

    println("\nBulk exact duplicate check: n=${f(n.toLong())} ids, planted duplicates=$planted, RAM ~%.1f GB".format(java.util.Locale.US, n * 36.0 / 1e9))
    t0 = System.nanoTime()
    val store = bulkGenerate(n)
    val tGen = (System.nanoTime() - t0) / 1e9
    // 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).
    val plantStep = if (planted > 0) (n / 2) / planted else 0
    for (k in 0 until planted) {
        val src = plantStep * k; val dst = n - 1 - src
        System.arraycopy(store.chunk(src), off(src), store.chunk(dst), off(dst), Uuid256.SIZE)
        println("  planted: id[${f(dst.toLong())}] := id[${f(src.toLong())}]")
    }
    var bad = 0L
    for (idx in 0 until n) { val s = store.chunk(idx); val p = off(idx); if ((s[p + 12].toInt() and 0xFF) shr 4 != Uuid256.VERSION || (s[p + 16].toInt() and 0xFF) shr 6 != 0b10) bad++ }
    val dups = findDuplicates(store, n)
    val tAll = (System.nanoTime() - t0) / 1e9
    for (d in dups) println("  DUPLICATE  id[${f(d.i.toLong())}] == id[${f(d.j.toLong())}]  ${d.id}")
    val step = max(1, n / 1000)
    var rtOk = 0
    var idx = 0
    while (idx < n) { val id = Uuid256.fromBytes(store.chunk(idx), off(idx)); if (Uuid256.parse(id.toString()) == id) rtOk++; idx += step }

    println("\n==== RESULT ====")
    println("ids generated:                   ${f(n.toLong())}   (SecureRandom + §4 in %.1fs; bucket-sort+compare in %.1fs)".format(java.util.Locale.US, tGen, tAll - tGen))
    println("version/variant violations:      ${f(bad)}")
    println("text round-trips (sampled):      ${f(rtOk.toLong())} ok")
    println("FULL 256-bit DUPLICATES:         ${f(dups.size.toLong())}" + if (planted > 0) "   (planted: $planted — ${if (dups.size == planted) "all detected" else "COUNT MISMATCH"})" else "")
    if (dups.isEmpty()) println("  → no duplicates among ${f(n.toLong())} ids")
    val log2p = 2 * (ln(n.toDouble()) / ln(2.0)) - 251
    println("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e".format(java.util.Locale.US, log2p, 2.0.pow(log2p)))
    exitProcess(if (dups.size == planted) 0 else 1)
}