| 1 |
;;; |
| 2 |
;;; rfc.uuid - UUID |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2020-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;; RFC9562 https://www.rfc-editor.org/rfc/rfc9562.html |
| 35 |
|
| 36 |
(define-module rfc.uuid |
| 37 |
(use binary.io) |
| 38 |
(use gauche.record) |
| 39 |
(use gauche.threads) |
| 40 |
(use gauche.uvector) |
| 41 |
(use srfi.27) |
| 42 |
(export <uuid> uuid-value uuid-version |
| 43 |
make-uuid1-generator uuid1 make-uuid4-generator uuid4 |
| 44 |
make-uuid6-generator uuid6 make-uuid7-generator uuid7 |
| 45 |
nil-uuid |
| 46 |
uuid-random-source |
| 47 |
uuid-random-source-set! |
| 48 |
uuid-comparator |
| 49 |
write-uuid uuid->string parse-uuid) |
| 50 |
) |
| 51 |
(select-module rfc.uuid) |
| 52 |
|
| 53 |
;; value is 16-element u8vector |
| 54 |
(define-record-type <uuid> %make-uuid uuid? (value uuid-value)) |
| 55 |
|
| 56 |
(define-method write-object ((u <uuid>) out) |
| 57 |
(format out "#<uuid v~a ~s>" (uuid-version u) (uuid->string u))) |
| 58 |
|
| 59 |
;;; |
| 60 |
;;;I/O |
| 61 |
;;; |
| 62 |
|
| 63 |
(define (write-uuid uuid :optional (port (current-output-port))) |
| 64 |
;; speed-conscious code |
| 65 |
(define (writeb x) |
| 66 |
(write-char (integer->digit (ash x -4) 16) port) |
| 67 |
(write-char (integer->digit (logand x #xf) 16) port)) |
| 68 |
(assume-type uuid <uuid>) |
| 69 |
(let1 v (uuid-value uuid) |
| 70 |
(writeb (u8vector-ref v 0)) |
| 71 |
(writeb (u8vector-ref v 1)) |
| 72 |
(writeb (u8vector-ref v 2)) |
| 73 |
(writeb (u8vector-ref v 3)) |
| 74 |
(write-char #\- port) |
| 75 |
(writeb (u8vector-ref v 4)) |
| 76 |
(writeb (u8vector-ref v 5)) |
| 77 |
(write-char #\- port) |
| 78 |
(writeb (u8vector-ref v 6)) |
| 79 |
(writeb (u8vector-ref v 7)) |
| 80 |
(write-char #\- port) |
| 81 |
(writeb (u8vector-ref v 8)) |
| 82 |
(writeb (u8vector-ref v 9)) |
| 83 |
(write-char #\- port) |
| 84 |
(writeb (u8vector-ref v 10)) |
| 85 |
(writeb (u8vector-ref v 11)) |
| 86 |
(writeb (u8vector-ref v 12)) |
| 87 |
(writeb (u8vector-ref v 13)) |
| 88 |
(writeb (u8vector-ref v 14)) |
| 89 |
(writeb (u8vector-ref v 15)))) |
| 90 |
|
| 91 |
(define (uuid->string uuid) (call-with-output-string (cut write-uuid uuid <>))) |
| 92 |
|
| 93 |
(define (parse-uuid str :key (if-invalid :error)) |
| 94 |
(define (make-uuidx tl tm th cl nd) |
| 95 |
(let1 v (make-u8vector 16) |
| 96 |
(put-u32be! v 0 (string->number tl 16)) |
| 97 |
(put-u16be! v 4 (string->number tm 16)) |
| 98 |
(put-u16be! v 6 (string->number th 16)) |
| 99 |
(put-u16be! v 8 (string->number cl 16)) |
| 100 |
(let1 nnd (string->number nd 16) |
| 101 |
(put-u16be! v 10 (ash nnd -32)) |
| 102 |
(put-u32be! v 12 (logand nnd #xffffffff))) |
| 103 |
(%make-uuid v))) |
| 104 |
|
| 105 |
(assume (memq if-invalid '(#f :error)) |
| 106 |
"if-invalid argument must be either #f or :error, but got:" if-invalid) |
| 107 |
|
| 108 |
(rxmatch-case str |
| 109 |
[#/^(?:urn:uuid:)?([[:xdigit:]]{8})-([[:xdigit:]]{4})-([[:xdigit:]]{4})-([[:xdigit:]]{4})-([[:xdigit:]]{12})$/ |
| 110 |
(_ tl tm th cl nd) |
| 111 |
(make-uuidx tl tm th cl nd)] |
| 112 |
[#/^\{([[:xdigit:]]{8})-([[:xdigit:]]{4})-([[:xdigit:]]{4})-([[:xdigit:]]{4})-([[:xdigit:]]{12})\}$/ |
| 113 |
(_ tl tm th cl nd) |
| 114 |
(make-uuidx tl tm th cl nd)] |
| 115 |
[#/^[[:xdigit:]]{32}$/ (xx) |
| 116 |
(let1 v (make-u8vector 16) |
| 117 |
(put-uint! 16 v 0 (string->number xx 16) 'big-endian) |
| 118 |
(%make-uuid v))] |
| 119 |
;; invalid input |
| 120 |
[else |
| 121 |
(if if-invalid |
| 122 |
(error "Invalid UUID format: " str) |
| 123 |
#f)])) |
| 124 |
|
| 125 |
;;; |
| 126 |
;;;Generation |
| 127 |
;;; |
| 128 |
|
| 129 |
(define uuid-random-source |
| 130 |
(make-parameter |
| 131 |
(rlet1 s (make-random-source) |
| 132 |
(random-source-randomize! s)) |
| 133 |
(^x (assume (random-source? x) "SRFI-27 random source required, but got:" x) |
| 134 |
x))) |
| 135 |
|
| 136 |
(define (%make-uuid-random-int) |
| 137 |
(random-source-make-integers (uuid-random-source))) |
| 138 |
|
| 139 |
;; Deprecated. Use parameter. |
| 140 |
(define (uuid-random-source-set! s) (uuid-random-source s)) |
| 141 |
|
| 142 |
(define (make-timestate) (atom 0 -1)) ; last-time and clock-seq |
| 143 |
(define (make-utimestate) (atom 0 -1)) ; like timestate, but for uuidv7 |
| 144 |
|
| 145 |
;; Returns a fake node id, when the user doesn't provide one. |
| 146 |
(define (make-pseudo-node) |
| 147 |
(logior ((%make-uuid-random-int) (ash 1 47)) |
| 148 |
(ash 1 40))) ; multicast bit |
| 149 |
|
| 150 |
(define-constant jd-origin 2299160) ; julian day of 15 Oct 1582 |
| 151 |
(define-constant jd-unix 2440587) ; julian day of 1 Jan 1970 |
| 152 |
(define-constant ts-offset ; 100ns count of offset |
| 153 |
(* (- jd-unix jd-origin) 86400 #e1e7)) |
| 154 |
|
| 155 |
;; returns 60bit timestamp, 100ns resolution since 00:00:00 15 Oct 1582 |
| 156 |
;; and 14bit clock sequence |
| 157 |
(define (%ts timestate random-int) |
| 158 |
(atomic-update! timestate |
| 159 |
(^[ts0 cl0] |
| 160 |
(let* ([cl (if (negative? cl0) |
| 161 |
(random-int (ash 1 14)) ;initial |
| 162 |
cl0)] |
| 163 |
[now (current-time)] |
| 164 |
;; count by 100ns tick |
| 165 |
[ts (+ (* (~ now'second) #e1e7) |
| 166 |
(quotient (~ now'nanosecond) 100) |
| 167 |
ts-offset)]) |
| 168 |
(if (<= ts ts0) |
| 169 |
;; got clock skew; increment clock seq |
| 170 |
(values ts (logand (+ cl 1) #x3fff)) |
| 171 |
(values ts cl)))))) |
| 172 |
|
| 173 |
;; Similar to %ts, but the timestamp is 48bit millisecond resolution since |
| 174 |
;; unix epoch, plus 74bits monotonically increasing sequence number. |
| 175 |
;; This is for uuidv7. We use the latter for rand_a and rand_b fields. |
| 176 |
;; The increment step of sequence number is a random |
| 177 |
;; |
| 178 |
;; for the next millisecond before wrap around, to ensure monotonicity. |
| 179 |
(define (%uts utimestate random-int incr-bits) |
| 180 |
(define (wait-a-bit) (sys-nanosleep 500000)) |
| 181 |
(define (update ts0 cl0) |
| 182 |
(let* ([cl (if (negative? cl0) |
| 183 |
(random-int (ash 1 74)) ;initial |
| 184 |
cl0)] |
| 185 |
[now (current-time)] |
| 186 |
[ts (+ (* (~ now'second) 1000) |
| 187 |
(quotient (~ now'nanosecond) #e1e6))] |
| 188 |
[cl1 (logand (+ cl 1 (random-int (- (ash 1 incr-bits) 1))) |
| 189 |
(- (ash 1 74) 1))]) |
| 190 |
(cond [(> ts ts0) ;timestamp differ, so we just use cl1 |
| 191 |
(values ts cl1)] |
| 192 |
[(< cl1 cl) ;counter wraparound. wait for next millisec |
| 193 |
(wait-a-bit) |
| 194 |
(update ts0 cl0)] |
| 195 |
[else |
| 196 |
(values ts cl1)]))) |
| 197 |
(atomic-update! utimestate update)) |
| 198 |
|
| 199 |
(define nil-uuid |
| 200 |
(let1 u (%make-uuid (make-u8vector 16 0)) |
| 201 |
(^[] u))) |
| 202 |
|
| 203 |
;; UUID v1 and v6 |
| 204 |
;; They use the same info, just the order of timestamp bits differs. |
| 205 |
(define (make-uuid1-generator :optional (default-node-id #f)) |
| 206 |
(define nid (or default-node-id (make-pseudo-node))) |
| 207 |
(define tstate (make-timestate)) |
| 208 |
(define random-int (%make-uuid-random-int)) |
| 209 |
(^[:optional (node-id #f)] |
| 210 |
(let ([id (or node-id nid)] |
| 211 |
[v (make-u8vector 16)]) |
| 212 |
(receive (ts cs) (%ts tstate random-int) |
| 213 |
(put-u32be! v 0 (logand ts #xffffffff)) |
| 214 |
(put-u16be! v 4 (logand (ash ts -32) #xffff)) |
| 215 |
(put-u16be! v 6 (logior (logand (ash ts -48) #x0fff) |
| 216 |
#x1000)) ; Version 1 |
| 217 |
(put-u16be! v 8 (logior cs #x8000)) ; Variant 10 |
| 218 |
(put-u16be! v 10 (ash nid -32)) |
| 219 |
(put-u32be! v 12 (logand nid #xffffffff))) |
| 220 |
(%make-uuid v)))) |
| 221 |
|
| 222 |
(define uuid1 (make-uuid1-generator)) |
| 223 |
|
| 224 |
(define (make-uuid6-generator :optional (default-node-id #f)) |
| 225 |
(define nid (or default-node-id (make-pseudo-node))) |
| 226 |
(define tstate (make-timestate)) |
| 227 |
(define random-int (%make-uuid-random-int)) |
| 228 |
(^[:optional (node-id #f)] |
| 229 |
(let ([id (or node-id nid)] |
| 230 |
[v (make-u8vector 16)]) |
| 231 |
(receive (ts cs) (%ts tstate random-int) |
| 232 |
(put-u32be! v 0 (logand (ash ts -28) #xffffffff)) |
| 233 |
(put-u16be! v 4 (logand (ash ts -12) #xffff)) |
| 234 |
(put-u16be! v 6 (logior (logand ts #x0fff) |
| 235 |
#x6000)) ; Version 6 |
| 236 |
(put-u16be! v 8 (logior cs #x8000)) ; Variant 10 |
| 237 |
(put-u16be! v 10 (ash nid -32)) |
| 238 |
(put-u32be! v 12 (logand nid #xffffffff))) |
| 239 |
(%make-uuid v)))) |
| 240 |
|
| 241 |
(define uuid6 (make-uuid6-generator)) |
| 242 |
|
| 243 |
;; UUID v4 |
| 244 |
;; Mostly random bits. |
| 245 |
(define (make-uuid4-generator) |
| 246 |
(define random-int (%make-uuid-random-int)) |
| 247 |
(^[] |
| 248 |
(let1 v (make-u8vector 16) |
| 249 |
(put-u32be! v 0 (random-int (ash 1 32))) |
| 250 |
(put-u32be! v 4 (logior (logand (random-int (ash 1 32)) |
| 251 |
#xffff0fff) |
| 252 |
#x4000)) ;Verson 4 |
| 253 |
(put-u32be! v 8 (copy-bit-field (random-int (ash 1 32)) |
| 254 |
2 30 32)) ;Variant 10 |
| 255 |
(put-u32be! v 12 (random-int (ash 1 32))) |
| 256 |
(%make-uuid v)))) |
| 257 |
|
| 258 |
(define uuid4 (make-uuid4-generator)) |
| 259 |
|
| 260 |
;; UUID v7 |
| 261 |
;; Monotonically increasing over time. Similar to ULID. |
| 262 |
;; To guarantee monotonicity, we combine rand_a and rand_b fields |
| 263 |
;; to store monotonically increasing sequence with random increments. |
| 264 |
;; If it wraparounds, we wait till next milliseconds boundary. |
| 265 |
(define (make-uuid7-generator :optional (increment-bits 64)) |
| 266 |
(define utstate (make-utimestate)) |
| 267 |
(define random-int (%make-uuid-random-int)) |
| 268 |
(assume (>= increment-bits 1)) |
| 269 |
(^[] |
| 270 |
(let1 v (make-u8vector 16) |
| 271 |
(receive (ts cs) (%uts utstate random-int increment-bits) |
| 272 |
(put-u32be! v 0 (ash ts -16)) |
| 273 |
(put-u16be! v 4 (logand ts #xffff)) |
| 274 |
(put-u16be! v 6 (logior (logand (ash cs -62) #x0fff) |
| 275 |
#x7000)) ;Version 7 |
| 276 |
(put-u32be! v 8 (logior #x8000 ;Variant 10 |
| 277 |
(logand (ash cs -32) #x3fffffff))) |
| 278 |
(put-u32be! v 12 (logand cs #xffffffff))) |
| 279 |
(%make-uuid v)))) |
| 280 |
|
| 281 |
(define uuid7 (make-uuid7-generator)) |
| 282 |
|
| 283 |
;;; |
| 284 |
;;;Meta info |
| 285 |
;;; |
| 286 |
|
| 287 |
(define (uuid-version uuid) |
| 288 |
(assume-type uuid <uuid>) |
| 289 |
(ash (u8vector-ref (uuid-value uuid) 6) -4)) |
| 290 |
|
| 291 |
(define-method object-equal? ((u1 <uuid>) (u2 <uuid>)) |
| 292 |
(equal? (uuid-value u1) (uuid-value u2))) |
| 293 |
(define-method object-compare ((u1 <uuid>) (u2 <uuid>)) |
| 294 |
(u8vector-compare (uuid-value u1) (uuid-value u2))) |
| 295 |
(define-method object-hash ((u <uuid>) rec) |
| 296 |
(default-hash (uuid-value u))) |
| 297 |
|
| 298 |
(define-inline uuid-comparator |
| 299 |
(make-comparator/compare uuid? object-equal? object-compare object-hash)) |