Debian Codegraph @

lib/rfc/uuid.scm

raw
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))