#!/usr/bin/env lua
-- uuid256.lua — reference implementation of README.md (UUID256, random layout) in Lua 5.3+ (stdlib only).
--
--   lua uuid256.lua                    -- self-tests + exact duplicate check over 1,000,000 ids
--   lua uuid256.lua -n 200000 -i 3     -- 2e5 ids with 3 planted duplicates (proves detection)
--   lua uuid256.lua -g [count]         -- just print one (or count) new ids, nothing else
--
--   local Uuid256 = require("uuid256")             -- (module use: nothing runs; returns the table)
--   local id  = Uuid256.generate()                  -- 32-byte string, §5.1: /dev/urandom (OS CSPRNG), ver=4 / var=10 applied
--   local txt = Uuid256.to_canonical(id)            -- §3.1: "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"
--   local b, err = Uuid256.parse(txt)               -- §6: strict → bytes or nil, "length"|"hyphen"|"char"|"version"; parse(txt, false) lenient
--
-- Randomness (§5.2): /dev/urandom — math.random is not a CSPRNG and MUST NOT be used.
-- Bulk check: one urandom read for all ids, §4 applied to each, then a table keyed by the 32-byte ids (exact).

local Uuid256 = {}
Uuid256.SIZE = 32
Uuid256.TEXT_LEN = 68
Uuid256.VERSION = 4
Uuid256.STRICT_PATTERN = "^" .. ("%x"):rep(16) .. "%-" .. ("%x"):rep(8) .. "%-4" .. ("%x"):rep(7) .. "%-[89ab]" .. ("%x"):rep(7) .. "%-" .. ("%x"):rep(24) .. "$"
Uuid256.NIL = ("\0"):rep(32)              -- §8
Uuid256.MAX = ("\255"):rep(32)

-- §5.2 — n bytes from the OS CSPRNG
function Uuid256.os_random(n)
  local f = assert(io.open("/dev/urandom", "rb"), "uuid256: cannot open /dev/urandom")
  local s = f:read(n); f:close()
  assert(s and #s == n, "uuid256: short read from /dev/urandom")
  return s
end

-- §4 — force version nibble (byte 13, 1-based) and variant bits (byte 17); returns a new 32-byte string
function Uuid256.set_ver_var(b)
  return b:sub(1, 12) .. string.char((b:byte(13) & 0x0F) | (Uuid256.VERSION << 4))   -- hex digit 24 = '4'
      .. b:sub(14, 16) .. string.char((b:byte(17) & 0x3F) | 0x80)                    -- hex digit 32 in [89ab]
      .. b:sub(18, 32)
end

-- §5.1 — a new id (32-byte string, big-endian: byte 1 most significant)
function Uuid256.generate() return Uuid256.set_ver_var(Uuid256.os_random(32)) end

-- §6 — ver == 4 && var == 10
function Uuid256.is_strict(b)
  return #b == 32 and (b:byte(13) >> 4) == Uuid256.VERSION and (b:byte(17) >> 6) == 2
end

-- §3.1 — canonical text: 16-8-8-8-24, lowercase, 68 chars
function Uuid256.to_canonical(b)
  assert(#b == 32, "uuid256: value must be exactly 32 bytes")
  local h = b:gsub(".", function(c) return ("%02x"):format(c:byte()) end)
  return h:sub(1, 16) .. "-" .. h:sub(17, 24) .. "-" .. h:sub(25, 32) .. "-" .. h:sub(33, 40) .. "-" .. h:sub(41, 64)
end
function Uuid256.to_compact(b) return (b:gsub(".", function(c) return ("%02x"):format(c:byte()) end)) end

-- §6 — parse canonical (68) or compact (64), any case → 32-byte string, or nil + error kind
function Uuid256.parse(s, strict)
  if strict == nil then strict = true end
  local t = s:lower()
  if #t == Uuid256.TEXT_LEN then
    if t:sub(17, 17) ~= "-" or t:sub(26, 26) ~= "-" or t:sub(35, 35) ~= "-" or t:sub(44, 44) ~= "-" then return nil, "hyphen" end
    t = t:gsub("%-", "")
  elseif #t ~= 64 then
    return nil, "length"
  end
  if not t:match("^" .. ("%x"):rep(64) .. "$") then return nil, "char" end
  local b = t:gsub("..", function(hh) return string.char(tonumber(hh, 16)) end)
  if strict and not Uuid256.is_strict(b) then return nil, "version" end
  return b
end

if ... == "uuid256" then return Uuid256 end     -- required as a module: expose the API and stop

-- ---------------------------------------------------------------------------
-- Self-tests (spec §11 vectors, §3.2/§6 parser rules, live generation)
-- ---------------------------------------------------------------------------
local function kind_of(s, strict) local b, e = Uuid256.parse(s, strict); return b and "ok" or e end
local function commas(n) local s = tostring(n); local r; repeat s, r = s:gsub("^(%-?%d+)(%d%d%d)", "%1,%2") until r == 0; return s end

local function self_test()
  local fails = 0
  local vectors = {
    { "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f" },
    { "fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0" },
  }
  for i, v in ipairs(vectors) do
    local raw, expected = v[1], v[2]
    local b = Uuid256.set_ver_var((Uuid256.parse(raw, false)))
    local txt = Uuid256.to_canonical(b)
    local ok = txt == expected and Uuid256.is_strict(b) and Uuid256.parse(txt) == b and Uuid256.parse(txt:upper()) == b
      and txt:match(Uuid256.STRICT_PATTERN) ~= nil and kind_of(raw, false) == "ok" and kind_of(raw) == "version"   -- raw compact: lenient ok, strict rejects
      and Uuid256.to_compact(b) == txt:gsub("%-", "")
    print(("  spec §11 vector %d: %s  %s"):format(i, ok and "PASS" or "FAIL", txt))
    if not ok then fails = fails + 1 end
  end
  local nil_txt = Uuid256.to_canonical(Uuid256.NIL)
  local ok = kind_of("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f") == "hyphen"
    and kind_of("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1") == "length"
    and kind_of("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g") == "char"
    and kind_of(nil_txt) == "version" and kind_of(nil_txt, false) == "ok" and Uuid256.parse(nil_txt, false) == Uuid256.NIL
    and Uuid256.to_canonical(Uuid256.MAX) == table.concat({ ("f"):rep(16), ("f"):rep(8), ("f"):rep(8), ("f"):rep(8), ("f"):rep(24) }, "-")
    and Uuid256.NIL < Uuid256.MAX
  print(("  parser rules (§3.2/§6):  %s"):format(ok and "PASS" or "FAIL"))
  if not ok then fails = fails + 1 end
  for _ = 1, 3 do
    local b = Uuid256.generate(); local txt = Uuid256.to_canonical(b)
    local ok2 = Uuid256.is_strict(b) and txt:match(Uuid256.STRICT_PATTERN) ~= nil and Uuid256.parse(txt) == b
    print(("  generate(): %s  %s"):format(txt, ok2 and "ok" or "BAD"))
    if not ok2 then fails = fails + 1 end
  end
  return fails
end

-- ---------------------------------------------------------------------------
-- Bulk exact duplicate check
-- ---------------------------------------------------------------------------
local function main(args)
  local n, planted = 1000000, 0
  if #args >= 2 and (args[1] == "-p" or args[1] == "-P") then                -- parse mode: -p strict, -P lenient
    local b, e = Uuid256.parse(args[2], args[1] == "-p")
    if b then print("ok " .. Uuid256.to_compact(b)); return 0 end
    print("error " .. e); return 1
  end
  local i = 1
  while i <= #args do
    local a = args[i]
    if a == "-g" then                                                          -- just print ids: -g [count]
      local c = tonumber(args[i + 1] or "") or 1; if c < 0 then c = 1 end            -- -g N: exactly N (0 allowed); junk → 1
      for _ = 1, c do print(Uuid256.to_canonical(Uuid256.generate())) end
      return 0
    elseif a == "-n" and args[i + 1] then i = i + 1; n = tonumber(args[i])
    elseif a == "-i" and args[i + 1] then i = i + 1; planted = tonumber(args[i])
    else print("usage: lua uuid256.lua [-g [count]] [-n count] [-i planted_dups]"); return 2 end
    i = i + 1
  end
  if not n or n < 2 or not planted or planted < 0 or planted > n // 2 then print("-n must be >= 2 and -i at most n/2"); return 2 end

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

  local K = 20000
  local t0 = os.clock()
  for _ = 1, K do Uuid256.generate() end
  local per_call = (os.clock() - t0) / K
  print(("\ngenerate() per-call cost: %.2f µs → %.3f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate; opening /dev/urandom per call dominates)")
        :format(per_call * 1e6, 1 / per_call / 1e6, 1e9 * per_call / 60))

  print(("\nBulk exact duplicate check: n=%s ids, planted duplicates=%d"):format(commas(n), planted))
  t0 = os.clock()
  local raw = Uuid256.os_random(n * 32)                                       -- §5.2, one read
  local ids = {}
  for k = 0, n - 1 do ids[k] = Uuid256.set_ver_var(raw:sub(k * 32 + 1, k * 32 + 32)) end   -- §4 on every id
  local t1 = os.clock()
  for kk = 0, planted - 1 do                                                   -- id[dst] := id[src]
    local src = kk * ((n // 2) // planted); local dst = n - 1 - src           -- stride: distinct pairs for every k < planted <= n/2
    ids[dst] = ids[src]
    print(("  planted: id[%s] := id[%s]"):format(commas(dst), commas(src)))
  end
  local bad, seen, dups = 0, {}, {}
  for k = 0, n - 1 do
    local id = ids[k]
    if not Uuid256.is_strict(id) then bad = bad + 1 end
    local first = seen[id]
    if first then dups[#dups + 1] = { first, k, id } else seen[id] = k end     -- exact: string keys
  end
  local t2 = os.clock()
  for _, d in ipairs(dups) do print(("  DUPLICATE  id[%s] == id[%s]  %s"):format(commas(d[1]), commas(d[2]), Uuid256.to_canonical(d[3]))) end
  local step = math.max(1, n // 1000); local rt_ok = 0
  for k = 0, n - 1, step do if Uuid256.parse(Uuid256.to_canonical(ids[k])) == ids[k] then rt_ok = rt_ok + 1 end end

  print("\n==== RESULT ====")
  print(("ids generated:                   %s   (/dev/urandom + §4 in %.1fs; table dedup in %.1fs)"):format(commas(n), t1 - t0, t2 - t1))
  print(("version/variant violations:      %s"):format(commas(bad)))
  print(("text round-trips (sampled):      %s ok"):format(commas(rt_ok)))
  print(("FULL 256-bit DUPLICATES:         %s%s"):format(commas(#dups),
        planted > 0 and ("   (planted: %d — %s)"):format(planted, #dups == planted and "all detected" or "COUNT MISMATCH") or ""))
  if #dups == 0 then print(("  → no duplicates among %s ids"):format(commas(n))) end
  local log2p = 2 * math.log(n, 2) - 251
  print(("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e"):format(log2p, 2 ^ log2p))
  return #dups == planted and 0 or 1
end

os.exit(main(arg))