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 31import "syscalls.nx" 32import "rand.nx" 33import "crockford32.nx" 34 35const ULID_LEN: i64 = 26 36const ULID_BYTES: i64 = 16 37 38// Build a 16-byte ULID value into `out`. Caller handles time. 39func ulid_bytes(unix_ms: i64, out: *u8) -> i64 { 40 // 48-bit big-endian timestamp into out[0..6]. 41 out[0] = (unix_ms >> 40) & 0xFF 42 out[1] = (unix_ms >> 32) & 0xFF 43 out[2] = (unix_ms >> 24) & 0xFF 44 out[3] = (unix_ms >> 16) & 0xFF 45 out[4] = (unix_ms >> 8) & 0xFF 46 out[5] = unix_ms & 0xFF 47 // 80 random bits into out[6..16]. 48 rand_bytes(out + 6, 10) 49 return 0 50} 51 52// Encode a 16-byte ULID as 26 Crockford-32 chars. Specialised 53// here (not via c32_encode) because ULID's 128 bits don't align 54// to base-32 group boundaries; the layout is: 55// time high: first 2 chars (10 high bits of timestamp) 56// -- wait, actually ULID packs 128 bits into 26 chars by 57// padding 2 zero bits at the top. We encode the bitstream 58// big-end-first, 5 bits at a time. 59func ulid_render(bytes: *u8, out: *u8) -> i64 { 60 // Pack 16 bytes big-endian into a 130-bit virtual stream (with 61 // 2 leading zero bits), emit 26 5-bit groups. We produce each 62 // group by extracting the appropriate slice of the input byte 63 // array. 64 // 65 // The canonical ULID spec has specific alignment: 66 // char 0 = top 3 bits of byte 0 (prefixed with 2 zeros -> top bit 0) 67 // char 1 = bottom 5 bits of byte 0, top 0 bits of byte 1 68 // ... 69 // To stay simple we do a shift register: build a 128-bit 70 // number from bytes, emit 26 chars from the TOP 130 bits 71 // (treating the buffer as having 2 leading zero bits). 72 // 73 // NishiLang i64 is 64-bit so we handle the 128-bit value as 74 // two halves (hi, lo) of 64 bits each. Shift operations on 75 // the pair extract 5 bits at a time from the top. 76 let hi_raw: *i64 = (sys_mmap(16)) as *i64 77 let lo_raw: *i64 = (sys_mmap(16)) as *i64 78 var hi: i64 = 0 79 var lo: i64 = 0 80 var i: i64 = 0 81 while i < 8 { 82 hi = (hi << 8) | bytes[i] 83 i = i + 1 84 } 85 while i < 16 { 86 lo = (lo << 8) | bytes[i] 87 i = i + 1 88 } 89 90 // 130-bit stream has the 128 bits of (hi, lo) starting at 91 // bit index 2 (top two bits are the padding zeros). Emit 92 // 26 groups of 5 bits, top-first. 93 // 94 // For each group g in 0..25: 95 // bit_top_pos = 130 - 5*(g+1) (from LSB side of the 130-bit value) 96 // 97 // Use a helper to extract 5 bits at a given LSB position. 98 var g: i64 = 0 99 while g < 26 { 100 let bit_pos: i64 = 125 - 5 * g // LSB of this 5-bit group 101 var v: i64 = 0 102 if bit_pos >= 64 { 103 // All 5 bits live in hi. 104 v = (hi >> (bit_pos - 64)) & 0x1F 105 } else { 106 if bit_pos + 5 <= 64 { 107 // All 5 bits live in lo. 108 v = (lo >> bit_pos) & 0x1F 109 } else { 110 // Straddles: low part from lo, high part from hi. 111 let lo_bits: i64 = 64 - bit_pos // how many from lo 112 let lo_mask: i64 = (1 << lo_bits) - 1 113 let lo_part: i64 = (lo >> bit_pos) & lo_mask 114 let hi_part: i64 = hi & ((1 << (5 - lo_bits)) - 1) 115 v = (hi_part << lo_bits) | lo_part 116 } 117 } 118 out[g] = c32_enc_char(v) 119 g = g + 1 120 } 121 *hi_raw = hi // discard-use so the vars don't get optimised to unused 122 *lo_raw = lo 123 return ULID_LEN 124} 125 126// Convenience: emit a fresh 26-char ULID at caller's time. 127func ulid_new(unix_ms: i64, out: *u8) -> i64 { 128 let tmp: *u8 = sys_mmap(ULID_BYTES) 129 ulid_bytes(unix_ms, tmp) 130 return ulid_render(tmp, out) 131} 132 133// Compile-only smoke. 134func main() -> i64 { 135 let out: *u8 = sys_mmap(64) 136 ulid_new(1777000000000, out) 137 // All 26 characters must be valid Crockford-32 (alnum minus 138 // I/L/O/U; encoder always upper-case). 139 var i: i64 = 0 140 while i < 26 { 141 let c: i64 = out[i] 142 var ok: i64 = 0 143 if c >= 0x30 { 144 if c <= 0x39 { ok = 1 } 145 } 146 if c >= 0x41 { 147 if c <= 0x5A { 148 if c != 0x49 { // 'I' 149 if c != 0x4C { // 'L' 150 if c != 0x4F { // 'O' 151 if c != 0x55 { // 'U' 152 ok = 1 153 } 154 } 155 } 156 } 157 } 158 } 159 if ok == 0 { return 1 } 160 i = i + 1 161 } 162 163 // Two ULIDs at the same timestamp should differ (random suffix). 164 let out2: *u8 = sys_mmap(64) 165 ulid_new(1777000000000, out2) 166 var diff: i64 = 0 167 i = 0 168 while i < 26 { 169 if out[i] != out2[i] { diff = 1; break } 170 i = i + 1 171 } 172 if diff != 1 { return 2 } 173 174 // Later timestamp should produce a lexicographically-greater 175 // prefix (first 10 chars). This is the whole reason ULID exists. 176 let out3: *u8 = sys_mmap(64) 177 ulid_new(1777000001000, out3) 178 // Compare first 10 chars. Can't be lower -- at minimum 179 // later timestamps give equal-or-greater prefix. 180 var worse: i64 = 0 181 i = 0 182 while i < 10 { 183 if out3[i] < out[i] { worse = 1; break } 184 if out3[i] > out[i] { break } 185 i = i + 1 186 } 187 if worse == 1 { return 3 } 188 189 return 0 190}