nx_ulid.nx source

1// ulid.nx -- Universally Unique Lexicographically Sortable ID. 2// 3// Alizain Feerasta 2016 spec. Drop-in UUID replacement designed 4// for databases + sortable indexes: 5// - 128 bits, same width as UUID 6// - First 48 bits: unix_ms timestamp (big-endian); sorts 7// chronologically in a SQL ORDER BY or filesystem listing 8// - Last 80 bits: cryptographic randomness 9// - Encoded as 26 Crockford-32 characters (no hyphens) 10// 11// Examples: 12// 01ARZ3NDEKTSV4RRFFQ69G5FAV 13// 01H7TNAC9TZ42D8XGTVJBKRS7M 14// 15// Used by: modern databases (PostgreSQL ULID extension, MongoDB 16// BSON_ULID), distributed systems needing time-ordered IDs, 17// log correlation, event sourcing, request tracing. 18// 19// Composes rand.nx (80 bits of randomness) + crockford32.nx 20// (canonical encoding). Time source is a caller-supplied 21// unix_ms -- keeps the module pure/testable. 22// 23// Invariants: 24// U1 Output = 26 ASCII chars, uppercase Crockford-32. 25// U2 First 10 chars encode 48-bit timestamp; lex-sort and 26// timestamp-sort agree within 2^48ms (~8900 years). 27// U3 Same millisecond -> different IDs (random suffix 28// differs); no strict monotonic-within-ms ordering 29// guaranteed today (that's a future ULID_MONOTONIC variant). 30 31// nx_safety_envelope: 32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 33// sil_target: SIL1 34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 35// verdict: NOT_YET_EVALUATED 36 37import "nx_syscalls.nx" 38import "nx_rand.nx" 39import "nx_crockford32.nx" 40const ULID_MAGIC_1777000000000: i64 = 1777000000000 41const ULID_MAGIC_1777000001000: i64 = 1777000001000 42 43const ULID_LEN: i64 = 26 44const ULID_BYTES: i64 = 16 45 46// Build a 16-byte ULID value into `out`. Caller handles time. 47func ulid_bytes(unix_ms: i64, out: *u8) -> i64 { 48 // 48-bit big-endian timestamp into out[0..6]. 49 out[0] = (unix_ms >> 40) & 0xFF 50 out[1] = (unix_ms >> 32) & 0xFF 51 out[2] = (unix_ms >> 24) & 0xFF 52 out[3] = (unix_ms >> 16) & 0xFF 53 out[4] = (unix_ms >> 8) & 0xFF 54 out[5] = unix_ms & 0xFF 55 // 80 random bits into out[6..16]. 56 rand_bytes(out + 6, 10) 57 return 0 58} 59 60// Encode a 16-byte ULID as 26 Crockford-32 chars. Specialised 61// here (not via c32_encode) because ULID's 128 bits don't align 62// to base-32 group boundaries; the layout is: 63// time high: first 2 chars (10 high bits of timestamp) 64// -- wait, actually ULID packs 128 bits into 26 chars by 65// padding 2 zero bits at the top. We encode the bitstream 66// big-end-first, 5 bits at a time. 67func ulid_render(bytes: *u8, out: *u8) -> i64 { 68 // Pack 16 bytes big-endian into a 130-bit virtual stream (with 69 // 2 leading zero bits), emit 26 5-bit groups. We produce each 70 // group by extracting the appropriate slice of the input byte 71 // array. 72 // 73 // The canonical ULID spec has specific alignment: 74 // char 0 = top 3 bits of byte 0 (prefixed with 2 zeros -> top bit 0) 75 // char 1 = bottom 5 bits of byte 0, top 0 bits of byte 1 76 // ... 77 // To stay simple we do a shift register: build a 128-bit 78 // number from bytes, emit 26 chars from the TOP 130 bits 79 // (treating the buffer as having 2 leading zero bits). 80 // 81 // NishiLang i64 is 64-bit so we handle the 128-bit value as 82 // two halves (hi, lo) of 64 bits each. Shift operations on 83 // the pair extract 5 bits at a time from the top. 84 let hi_raw: *i64 = (sys_mmap(16)) as *i64 85 let lo_raw: *i64 = (sys_mmap(16)) as *i64 86 var hi: i64 = 0 87 var lo: i64 = 0 88 var i: i64 = 0 89 while i < 8 { 90 hi = (hi << 8) | bytes[i] 91 i = i + 1 92 } 93 while i < 16 { 94 lo = (lo << 8) | bytes[i] 95 i = i + 1 96 } 97 98 // 130-bit stream has the 128 bits of (hi, lo) starting at 99 // bit index 2 (top two bits are the padding zeros). Emit 100 // 26 groups of 5 bits, top-first. 101 // 102 // For each group g in 0..25: 103 // bit_top_pos = 130 - 5*(g+1) (from LSB side of the 130-bit value) 104 // 105 // Use a helper to extract 5 bits at a given LSB position. 106 var g: i64 = 0 107 while g < 26 { 108 let bit_pos: i64 = 125 - 5 * g // LSB of this 5-bit group 109 var v: i64 = 0 110 if bit_pos >= 64 { 111 // All 5 bits live in hi. 112 v = (hi >> (bit_pos - 64)) & 0x1F 113 } else { 114 if bit_pos + 5 <= 64 { 115 // All 5 bits live in lo. 116 v = (lo >> bit_pos) & 0x1F 117 } else { 118 // Straddles: low part from lo, high part from hi. 119 let lo_bits: i64 = 64 - bit_pos // how many from lo 120 let lo_mask: i64 = (1 << lo_bits) - 1 121 let lo_part: i64 = (lo >> bit_pos) & lo_mask 122 let hi_part: i64 = hi & ((1 << (5 - lo_bits)) - 1) 123 v = (hi_part << lo_bits) | lo_part 124 } 125 } 126 out[g] = c32_enc_char(v) 127 g = g + 1 128 } 129 *hi_raw = hi // discard-use so the vars don't get optimised to unused 130 *lo_raw = lo 131 return ULID_LEN 132} 133 134// Convenience: emit a fresh 26-char ULID at caller's time. 135func ulid_new(unix_ms: i64, out: *u8) -> i64 { 136 let tmp: *u8 = sys_mmap(ULID_BYTES) 137 ulid_bytes(unix_ms, tmp) 138 return ulid_render(tmp, out) 139} 140 141// Compile-only smoke. 142func main() -> i64 { 143 let out: *u8 = sys_mmap(64) 144 ulid_new(ULID_MAGIC_1777000000000, out) 145 // All 26 characters must be valid Crockford-32 (alnum minus 146 // I/L/O/U; encoder always upper-case). 147 var i: i64 = 0 148 while i < 26 { 149 let c: i64 = out[i] 150 var ok: i64 = 0 151 if c >= 0x30 { 152 if c <= 0x39 { ok = 1 } 153 } 154 if c >= 0x41 { 155 if c <= 0x5A { 156 if c != 0x49 { // 'I' 157 if c != 0x4C { // 'L' 158 if c != 0x4F { // 'O' 159 if c != 0x55 { // 'U' 160 ok = 1 161 } 162 } 163 } 164 } 165 } 166 } 167 if ok == 0 { return 1 } 168 i = i + 1 169 } 170 171 // Two ULIDs at the same timestamp should differ (random suffix). 172 let out2: *u8 = sys_mmap(64) 173 ulid_new(ULID_MAGIC_1777000000000, out2) 174 var diff: i64 = 0 175 i = 0 176 while i < 26 { 177 if out[i] != out2[i] { diff = 1; break } 178 i = i + 1 179 } 180 if diff != 1 { return 2 } 181 182 // Later timestamp should produce a lexicographically-greater 183 // prefix (first 10 chars). This is the whole reason ULID exists. 184 let out3: *u8 = sys_mmap(64) 185 ulid_new(ULID_MAGIC_1777000001000, out3) 186 // Compare first 10 chars. Can't be lower -- at minimum 187 // later timestamps give equal-or-greater prefix. 188 var worse: i64 = 0 189 i = 0 190 while i < 10 { 191 if out3[i] < out[i] { worse = 1; break } 192 if out3[i] > out[i] { break } 193 i = i + 1 194 } 195 if worse == 1 { return 3 } 196 197 return 0 198}