ULID Generator — Go source

// Package ulid is the Go twin of CosmoDev's src/lib/ulid.ts (dual source: the
// web lib is TypeScript, the CLI lib is Go — kept in lock-step). Pure +
// deterministic, never panics. The table-driven tests in ulid_test.go share
// vectors with src/lib/ulid.test.ts so the two implementations are held to the
// same contract.
//
// The TS lib wraps the `ulid` npm package. This Go twin HAND-ROLLS the ULID
// algorithm (stdlib only — no oklog/ulid, no external module). A ULID is 26
// Crockford-base32 chars: the first 10 encode a 48-bit millisecond timestamp
// (MSB-first) and the last 16 encode 80 bits of randomness. Crockford alphabet:
// "0123456789ABCDEFGHJKMNPQRSTVWXYZ" (excludes I, L, O, U).
//
// Time-encoding is the lock-step ANCHOR. Because 32^16 == 2^80 exactly,
// packing [6 time bytes | 10 random bytes] into a 16-byte big-endian integer
// and base32-encoding the whole 128-bit value reproduces the npm package's
// separate encodeTime(ts, 10) verbatim in the first 10 chars — so
// DecodeTime(Generate(ms)) == ms holds identically across Go and TS. The
// random tail is drawn from crypto/rand (the Go analogue of the TS default
// RNG) and varies call to call, exactly as in the TS default-RNG path.
package ulid

import (
	"crypto/rand"
	"fmt"
	"strings"
	"time"
)

// crockford is the Crockford base32 alphabet (excludes I, L, O, U).
const crockford = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"

// decodeMap maps an ASCII byte to its Crockford base32 value, or 0xFF if the
// byte is not a valid ULID character. Letters I, L, O, U are invalid (absent
// from the alphabet); lowercase letters are accepted and decode identically to
// their uppercase form — matching the `ulid` npm package's DECODING table, so a
// lowercase TS-produced ULID decodes the same way in Go.
var decodeMap [256]byte

func init() {
	for i := range decodeMap {
		decodeMap[i] = 0xFF
	}
	for i := 0; i < len(crockford); i++ {
		decodeMap[crockford[i]] = byte(i)
	}
	// Accept lowercase a-z where the uppercase equivalent is a valid symbol.
	// i/l/o/u stay 0xFF because I/L/O/U are not in the alphabet.
	for c := byte('a'); c <= 'z'; c++ {
		up := c - 'a' + 'A'
		if decodeMap[up] != 0xFF {
			decodeMap[c] = decodeMap[up]
		}
	}
}

// divBy32 divides the big-endian integer stored in b by 32, in place, and
// returns the remainder (0-31). It is long division in base 256: each byte is
// combined with the carry from the previous (more-significant) byte, the high
// 8 bits become the new byte and the low 5 bits become the next carry.
func divBy32(b []byte) byte {
	var rem byte
	for i := 0; i < len(b); i++ {
		cur := uint16(rem)<<8 | uint16(b[i])
		b[i] = byte(cur >> 5)
		rem = byte(cur & 0x1F)
	}
	return rem
}

// Generate returns a new ULID for the given millisecond timestamp. It is the Go
// twin of generateUlid() in src/lib/ulid.ts.
//
// The timestamp occupies the low 48 bits of ms and is written MSB-first into
// the first 6 bytes; the last 10 bytes are filled from crypto/rand. The whole
// 16-byte value is then base32-encoded into the canonical 26 chars.
//
// Generate returns a string only (no error) for parity with the TS default-RNG
// path. If crypto/rand.Read fails — which should not happen in practice — the
// random bytes stay zero: the ULID remains well-formed and its timestamp still
// round-trips, it is merely less random. Never panics. Callers should pass a
// non-negative ms-since-epoch; negative values encode the low 48 bits of the
// two's-complement representation (defined but not meaningful as a timestamp).
func Generate(ms int64) string {
	var b [16]byte
	u := uint64(ms)
	b[0] = byte(u >> 40)
	b[1] = byte(u >> 32)
	b[2] = byte(u >> 24)
	b[3] = byte(u >> 16)
	b[4] = byte(u >> 8)
	b[5] = byte(u)
	_, _ = rand.Read(b[6:16]) // best-effort; on failure b[6:16] stays zero

	// Repeatedly divide the 128-bit value by 32, collecting remainders LSB-first
	// into out[25] down to out[0]. 26 base32 digits cover 130 bits, so the most
	// significant digit captures the leftover top 3 bits (value 0-7).
	var out [26]byte
	for i := 25; i >= 0; i-- {
		out[i] = crockford[divBy32(b[:])]
	}
	return string(out[:])
}

// DecodeTime extracts the 48-bit millisecond timestamp encoded in the first 10
// chars of id. It is the Go twin of decodeUlidTime() in src/lib/ulid.ts.
//
// It returns an error if id is not exactly 26 chars long or contains a
// character outside the Crockford base32 alphabet (I, L, O, U are invalid), so
// it errors on the same inputs as the `ulid` npm package's decodeTime.
func DecodeTime(id string) (int64, error) {
	if len(id) != 26 {
		return 0, fmt.Errorf("ulid: malformed id: length %d, want 26", len(id))
	}
	var ts int64
	for i := 0; i < 10; i++ {
		v := decodeMap[id[i]]
		if v == 0xFF {
			return 0, fmt.Errorf("ulid: invalid character %q at position %d", rune(id[i]), i)
		}
		ts = ts*32 + int64(v)
	}
	return ts, nil
}

// Info is the Go twin of the UlidInfo interface in src/lib/ulid.ts: the
// structured breakdown of a pasted ULID. Error is set only when Valid is false.
type Info struct {
	Valid      bool
	Error      string
	TimePart   string // first 10 chars — the encoded timestamp
	Randomness string // last 16 chars — the random part
	Timestamp  int64  // decoded ms since epoch
	ISO        string // timestamp as ISO-8601 UTC with millisecond precision
}

// timeMax is the 48-bit ULID timestamp ceiling (281474976710655 ms, year 10889).
const timeMax = int64(1)<<48 - 1

// Inspect validates a pasted ULID and breaks out its structural parts. It is
// the Go twin of inspectUlid() in src/lib/ulid.ts, sharing its test vectors.
// Input is trimmed and uppercased before validation (matching the TS twin);
// error strings mirror the TS messages so both implementations are held to
// one contract. Never panics.
func Inspect(input string) Info {
	id := strings.ToUpper(strings.TrimSpace(input))
	if len(id) != 26 {
		return Info{Error: fmt.Sprintf("Length must be 26 characters, got %d", len(id))}
	}
	for i := 0; i < len(id); i++ {
		if decodeMap[id[i]] == 0xFF {
			return Info{Error: "Invalid character — ULIDs use Crockford base32 (no I, L, O, U)"}
		}
	}
	ts, err := DecodeTime(id)
	if err != nil || ts > timeMax {
		return Info{Error: "Time part overflows the 48-bit ULID timestamp ceiling"}
	}
	return Info{
		Valid:      true,
		TimePart:   id[:10],
		Randomness: id[10:],
		Timestamp:  ts,
		ISO:        time.UnixMilli(ts).UTC().Format("2006-01-02T15:04:05.000Z"),
	}
}