// uuid256.go — reference implementation of README.md (UUID256, random layout) in Go.  Standard library only.
//
//	Run (Go 1.21+, no module file needed — go run compiles to a temp dir, nothing left behind):
//	    go run uuid256.go                    # self-tests + exact duplicate check over 100,000,000 ids
//	    go run uuid256.go -n 5000000 -i 3    # 5e6 ids with 3 planted duplicates (proves detection)
//	    go run uuid256.go -g [count]         # just print one (or count) new ids, nothing else
//	Library use: copy the UUID type and its methods into a package of your own.
//
//	id  := uuid256.New()                     // §5.1: 32 bytes from crypto/rand, ver=4 / var=10 applied
//	txt := id.String()                       // §3.1: "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"
//	id2, err := uuid256.Parse(txt)           // §6: strict (ver/var checked); ParseLenient accepts any ver/var
//	UUID implements fmt.Stringer, encoding.TextMarshaler/TextUnmarshaler (so it JSON-encodes as canonical text).
//
// Bulk check: all randomness from crypto/rand (§5.2 — OS CSPRNG) into one []byte, §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.
package main

import (
	"bytes"
	"crypto/rand"
	"encoding/hex"
	"errors"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
	"time"
)

// ============================================================================
//  Spec §3–§6: the UUID type
// ============================================================================

const (
	Size       = 32 // bytes
	TextLength = 68 // 64 hex + 4 hyphens
	Version    = 4
)

// UUID is a 256-bit random unique identifier (README.md spec), stored big-endian: [0] is the most significant byte.
type UUID [Size]byte

var (
	Nil = UUID{} // §8
	Max = UUID{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}

	ErrLength  = errors.New("uuid256: wrong length (want 68 canonical or 64 compact)")
	ErrHyphen  = errors.New("uuid256: hyphen at wrong position")
	ErrChar    = errors.New("uuid256: invalid character")
	ErrVersion = errors.New("uuid256: unsupported version/variant")
)

// SetVersionAndVariant applies §4 to a raw 32-byte buffer: version nibble (byte 12), variant bits (byte 16).
func SetVersionAndVariant(b []byte) {
	b[12] = (b[12] & 0x0F) | (Version << 4) // hex digit 24 = '4'
	b[16] = (b[16] & 0x3F) | 0x80           // hex digit 32 in [89ab]
}

// New returns a fresh id straight from the OS CSPRNG (§5.1). Panics only if the OS random source fails.
func New() UUID {
	var u UUID
	if _, err := rand.Read(u[:]); err != nil {
		panic("uuid256: crypto/rand failed: " + err.Error())
	}
	SetVersionAndVariant(u[:])
	return u
}

// FromBytes copies a 32-byte big-endian encoding (no ver/var validation; see IsStrict).
func FromBytes(b []byte) (UUID, error) {
	var u UUID
	if len(b) != Size {
		return u, ErrLength
	}
	copy(u[:], b)
	return u, nil
}

// Bytes returns the 32-byte big-endian encoding.
func (u UUID) Bytes() []byte { b := make([]byte, Size); copy(b, u[:]); return b }

// VersionField is the version nibble (byte 12 high nibble): 4 for this spec.
func (u UUID) VersionField() int { return int(u[12] >> 4) }

// VariantField is the variant (byte 16 top two bits): 0b10 for this spec.
func (u UUID) VariantField() int { return int(u[16] >> 6) }

// IsStrict reports ver == 4 && var == 10 (§6).
func (u UUID) IsStrict() bool { return u.VersionField() == Version && u.VariantField() == 0b10 }

// String is the canonical text form (§3.1): 16-8-8-8-24, lowercase, 68 characters.
func (u UUID) String() string {
	const hexdigits = "0123456789abcdef"
	var out [TextLength]byte
	o := 0
	for i, b := range u {
		out[o] = hexdigits[b>>4]
		out[o+1] = hexdigits[b&0x0F]
		o += 2
		if i == 7 || i == 11 || i == 15 || i == 19 { // hyphen after hex digits 16, 24, 32, 40
			out[o] = '-'
			o++
		}
	}
	return string(out[:])
}

// Compact is the 64-hex-digit input-only form (§3.2 rule 4).
func (u UUID) Compact() string { return hex.EncodeToString(u[:]) }

// Compare orders numerically == big-endian byte order == canonical-text order (§7.1).
func (u UUID) Compare(v UUID) int { return bytes.Compare(u[:], v[:]) }

// Parse accepts the canonical (68) or compact (64) form in any case and requires ver == 4 / var == 10 (§6).
func Parse(s string) (UUID, error) { return parse(s, true) }

// ParseLenient is Parse without the version/variant check (transports Nil/Max and future layouts).
func ParseLenient(s string) (UUID, error) { return parse(s, false) }

// MustParse is Parse that panics on error (for constants and tests).
func MustParse(s string) UUID {
	u, err := Parse(s)
	if err != nil {
		panic(err)
	}
	return u
}

func parse(s string, strict bool) (UUID, error) {
	var u UUID
	hyphenated := false
	switch len(s) {
	case TextLength:
		if s[16] != '-' || s[25] != '-' || s[34] != '-' || s[43] != '-' {
			return u, ErrHyphen
		}
		hyphenated = true
	case 64:
	default:
		return u, ErrLength
	}
	nib, bi, cur := 0, 0, 0
	for i := 0; i < len(s); i++ {
		if hyphenated && (i == 16 || i == 25 || i == 34 || i == 43) {
			continue
		}
		var v int
		switch c := s[i]; {
		case c >= '0' && c <= '9':
			v = int(c - '0')
		case c >= 'a' && c <= 'f':
			v = int(c-'a') + 10
		case c >= 'A' && c <= 'F':
			v = int(c-'A') + 10
		default:
			return UUID{}, ErrChar
		}
		cur = cur<<4 | v
		nib++
		if nib == 2 {
			u[bi] = byte(cur)
			bi, nib, cur = bi+1, 0, 0
		}
	}
	if strict && !u.IsStrict() {
		return UUID{}, ErrVersion
	}
	return u, nil
}

// MarshalText / UnmarshalText make UUID a JSON string, a text map key, etc. (encoding.TextMarshaler).
func (u UUID) MarshalText() ([]byte, error) { return []byte(u.String()), nil }
func (u *UUID) UnmarshalText(text []byte) error {
	v, err := Parse(string(text))
	if err != nil {
		return err
	}
	*u = v
	return nil
}

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

func selfTest() int {
	fails := 0
	vectors := []struct{ raw, expected string }{
		{"000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"},
		{"fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"},
	}
	for i, v := range vectors {
		raw, _ := hex.DecodeString(v.raw)
		SetVersionAndVariant(raw)
		u, _ := FromBytes(raw)
		txt := u.String()
		p1, e1 := Parse(txt)
		p2, e2 := Parse(strings.ToUpper(txt))
		_, e3 := ParseLenient(v.raw) // raw compact: lenient ok
		_, e4 := Parse(v.raw)        // strict rejects (ver != 4)
		var rt UUID
		e5 := rt.UnmarshalText([]byte(txt))
		ok := txt == v.expected && u.IsStrict() && e1 == nil && p1 == u && e2 == nil && p2 == u &&
			e3 == nil && errors.Is(e4, ErrVersion) && e5 == nil && rt == u && bytes.Equal(u.Bytes(), raw)
		status := "PASS"
		if !ok {
			status = "FAIL"
			fails++
		}
		fmt.Printf("  spec §11 vector %d: %s  %s\n", i+1, status, txt)
	}
	{
		nilTxt := Nil.String()
		_, eH := Parse("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f")
		_, eL := Parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1")
		_, eC := Parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g")
		_, eV := Parse(nilTxt)
		n2, eN := ParseLenient(nilTxt)
		ok := errors.Is(eH, ErrHyphen) && errors.Is(eL, ErrLength) && errors.Is(eC, ErrChar) && errors.Is(eV, ErrVersion) &&
			eN == nil && n2 == Nil && Nil.Compare(Max) < 0 &&
			Max.String() == strings.Repeat("f", 16)+"-"+strings.Repeat("f", 8)+"-"+strings.Repeat("f", 8)+"-"+strings.Repeat("f", 8)+"-"+strings.Repeat("f", 24)
		status := "PASS"
		if !ok {
			status = "FAIL"
			fails++
		}
		fmt.Printf("  parser rules (§3.2/§6):  %s\n", status)
	}
	for i := 0; i < 3; i++ {
		u := New()
		txt := u.String()
		// string offsets: hex digit 24 → char 26 (after 2 hyphens), hex digit 32 → char 35 (after 3 hyphens)
		p, err := Parse(txt)
		ok := u.IsStrict() && len(txt) == 68 && txt[26] == '4' && strings.ContainsRune("89ab", rune(txt[35])) && err == nil && p == u
		status := "ok"
		if !ok {
			status = "BAD"
			fails++
		}
		fmt.Printf("  New(): %s  %s\n", txt, status)
	}
	return fails
}

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

func bulkGenerate(n int) []byte {
	buf := make([]byte, n*Size)
	if _, err := rand.Read(buf); err != nil { // §5.2 — crypto/rand fills any length
		panic(err)
	}
	for p := 0; p < len(buf); p += Size { // §4 on every id
		SetVersionAndVariant(buf[p : p+Size])
	}
	return buf
}

type dup struct {
	i, j int
	id   UUID
}

func findDuplicates(buf []byte, n int) []dup {
	const NB = 1 << 24 // bucket = top 24 bits (bytes 0..2, all random)
	start := make([]uint32, NB+1)
	for i, p := 0, 0; i < n; i, p = i+1, p+Size {
		start[(int(buf[p])<<16|int(buf[p+1])<<8|int(buf[p+2]))+1]++
	}
	for b := 0; b < NB; b++ { // exclusive prefix sums → bucket starts
		start[b+1] += start[b]
	}
	cursor := make([]uint32, NB+1)
	copy(cursor, start)
	order := make([]uint32, n)
	for i, p := 0, 0; i < n; i, p = i+1, p+Size {
		b := int(buf[p])<<16 | int(buf[p+1])<<8 | int(buf[p+2])
		order[cursor[b]] = uint32(i)
		cursor[b]++
	}
	var dups []dup
	for b := 0; b < NB; b++ {
		lo, hi := start[b], start[b+1]
		if hi-lo < 2 {
			continue
		}
		for x := lo; x < hi; x++ {
			for y := x + 1; y < hi; y++ { // buckets are tiny (n / 16M)
				i, j := int(order[x]), int(order[y])
				if bytes.Equal(buf[i*Size:i*Size+Size], buf[j*Size:j*Size+Size]) {
					var u UUID
					copy(u[:], buf[i*Size:])
					dups = append(dups, dup{min(i, j), max(i, j), u})
				}
			}
		}
	}
	return dups
}

func commas(v int64) string {
	s := strconv.FormatInt(v, 10)
	var sb strings.Builder
	for i, c := range s {
		if i > 0 && (len(s)-i)%3 == 0 {
			sb.WriteByte(',')
		}
		sb.WriteRune(c)
	}
	return sb.String()
}

func main() {
	n, planted := 100_000_000, 0
	args := os.Args[1:]
	if len(args) >= 2 && (args[0] == "-p" || args[0] == "-P") { // parse mode: -p strict, -P lenient
		u, err := parse(args[1], args[0] == "-p")
		if err == nil {
			fmt.Println("ok", u.Compact())
			return
		}
		kind := map[error]string{ErrLength: "length", ErrHyphen: "hyphen", ErrChar: "char", ErrVersion: "version"}[err]
		fmt.Println("error", kind)
		os.Exit(1)
	}
	for i := 0; i < len(args); i++ {
		switch {
		case args[i] == "-g": // just print ids: -g [count]
			count := 1
			if i+1 < len(args) {
				if c, err := strconv.Atoi(args[i+1]); err == nil && c >= 0 { // -g N: exactly N (0 allowed); junk → 1
					count = c
				}
			}
			for k := 0; k < count; k++ {
				fmt.Println(New())
			}
			return
		case args[i] == "-n" && i+1 < len(args):
			i++
			n, _ = strconv.Atoi(args[i])
		case args[i] == "-i" && i+1 < len(args):
			i++
			planted, _ = strconv.Atoi(args[i])
		default:
			fmt.Println("usage: go run uuid256.go [-g [count]] [-n count] [-i planted_dups]")
			os.Exit(2)
		}
	}
	if n < 2 || n > math.MaxUint32 || planted < 0 || planted > n/2 { // bucket counters and indices are uint32
		fmt.Println("-n must be 2..4294967295 and -i at most n/2")
		os.Exit(2)
	}
	fmt.Println("UUID256 reference implementation (Go) — README.md (256-bit random, 16-8-8-8-24 text)")
	fmt.Println()
	fmt.Println("Self-tests:")
	if selfTest() > 0 {
		fmt.Println("  self-test FAILED — aborting")
		os.Exit(1)
	}

	const K = 1_000_000
	t0 := time.Now()
	for i := 0; i < K; i++ {
		_ = New()
	}
	perCall := time.Since(t0).Seconds() / K
	fmt.Printf("\nNew() per-call cost: %.2f µs → %.2f M ids/s single-threaded (1e9 ids would take ~%.0f min just to generate)\n",
		perCall*1e6, 1/perCall/1e6, 1e9*perCall/60)

	fmt.Printf("\nBulk exact duplicate check: n=%s ids, planted duplicates=%d, RAM ~%.1f GB\n", commas(int64(n)), planted, float64(n)*36/1e9)
	t0 = time.Now()
	buf := bulkGenerate(n)
	tGen := time.Since(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).
	plantStep := 0
	if planted > 0 {
		plantStep = (n / 2) / planted
	}
	for k := 0; k < planted; k++ {
		src, dst := plantStep*k, n-1-plantStep*k
		copy(buf[dst*Size:dst*Size+Size], buf[src*Size:src*Size+Size])
		fmt.Printf("  planted: id[%s] := id[%s]\n", commas(int64(dst)), commas(int64(src)))
	}
	bad := 0
	for p := 0; p < len(buf); p += Size {
		if buf[p+12]>>4 != Version || buf[p+16]>>6 != 0b10 {
			bad++
		}
	}
	dups := findDuplicates(buf, n)
	tAll := time.Since(t0)
	for _, d := range dups {
		fmt.Printf("  DUPLICATE  id[%s] == id[%s]  %s\n", commas(int64(d.i)), commas(int64(d.j)), d.id)
	}
	rtOK, step := 0, max(1, n/1000)
	for i := 0; i < n; i += step {
		var u UUID
		copy(u[:], buf[i*Size:])
		if p, err := Parse(u.String()); err == nil && p == u {
			rtOK++
		}
	}

	fmt.Println("\n==== RESULT ====")
	fmt.Printf("ids generated:                   %s   (crypto/rand + §4 in %.1fs; bucket-sort+compare in %.1fs)\n", commas(int64(n)), tGen.Seconds(), (tAll - tGen).Seconds())
	fmt.Printf("version/variant violations:      %s\n", commas(int64(bad)))
	fmt.Printf("text round-trips (sampled):      %s ok\n", commas(int64(rtOK)))
	fmt.Printf("FULL 256-bit DUPLICATES:         %s", commas(int64(len(dups))))
	if planted > 0 {
		verdict := "all detected"
		if len(dups) != planted {
			verdict = "COUNT MISMATCH"
		}
		fmt.Printf("   (planted: %d — %s)", planted, verdict)
	}
	fmt.Println()
	if len(dups) == 0 {
		fmt.Printf("  → no duplicates among %s ids\n", commas(int64(n)))
	}
	log2p := 2*math.Log2(float64(n)) - 251
	fmt.Printf("expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e\n", log2p, math.Pow(2, log2p))
	if len(dups) != planted {
		os.Exit(1)
	}
}