| 1 |
;;; |
| 2 |
;;; data.ulid - ULID |
| 3 |
;;; |
| 4 |
|
| 5 |
;; This is Gauche-specific port of https://github.com/shirok/scheme-ulid |
| 6 |
|
| 7 |
;; Copyright 2022-2024 by Shiro Kawai <[email protected]> |
| 8 |
|
| 9 |
;; Permission is hereby granted, free of charge, to any person obtaining |
| 10 |
;; a copy of this software and associated documentation files (the |
| 11 |
;; "Software"), to deal in the Software without restriction, including |
| 12 |
;; without limitation the rights to use, copy, modify, merge, publish, |
| 13 |
;; distribute, sublicense, and/or sell copies of the Software, and to |
| 14 |
;; permit persons to whom the Software is furnished to do so, subject to |
| 15 |
;; the following conditions: |
| 16 |
|
| 17 |
;; The above copyright notice and this permission notice shall be |
| 18 |
;; included in all copies or substantial portions of the Software. |
| 19 |
|
| 20 |
;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 21 |
;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 22 |
;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 23 |
;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
| 24 |
;; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
| 25 |
;; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
| 26 |
;; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 27 |
|
| 28 |
(define-module data.ulid |
| 29 |
(use gauche.record) |
| 30 |
(use gauche.uvector) |
| 31 |
(use scheme.bitwise) |
| 32 |
(use scheme.vector) |
| 33 |
(use srfi.13) |
| 34 |
(use srfi.19) |
| 35 |
(use srfi.27) |
| 36 |
(export make-ulid-generator |
| 37 |
ulid? |
| 38 |
ulid-timestamp |
| 39 |
ulid-randomness |
| 40 |
ulid=? |
| 41 |
ulid<? |
| 42 |
ulid-hash |
| 43 |
ulid-comparator |
| 44 |
ulid->string |
| 45 |
ulid->integer |
| 46 |
ulid->bytevector |
| 47 |
string->ulid |
| 48 |
integer->ulid |
| 49 |
bytevector->ulid)) |
| 50 |
(select-module data.ulid) |
| 51 |
|
| 52 |
(define (milliseconds-from-epoch) |
| 53 |
(receive (secs usecs) (sys-gettimeofday) |
| 54 |
(+ (* secs 1000) (quotient usecs 1000)))) |
| 55 |
|
| 56 |
(define (wait-a-bit ri) (sys-nanosleep 500000)) |
| 57 |
|
| 58 |
(define *randomness-range* (expt 2 80)) |
| 59 |
(define *digits* (string->vector "0123456789ABCDEFGHJKMNPQRSTVWXYZ")) |
| 60 |
|
| 61 |
;; Ulid record |
| 62 |
(define-record-type ulid %make-ulid ulid? |
| 63 |
(timestamp ulid-timestamp) |
| 64 |
(randomness ulid-randomness)) |
| 65 |
|
| 66 |
(define ulid-random-source |
| 67 |
(rlet1 s (make-random-source) |
| 68 |
(random-source-randomize! s))) |
| 69 |
|
| 70 |
;; API |
| 71 |
;; NB: The ULID spec says ULID generation may fail if randomness is very close |
| 72 |
;; to 2^80 and lots of ULIDs are generated in the same millisecond, causing |
| 73 |
;; randomness field to overflow. We can, however, wait just one millisecond |
| 74 |
;; to overcome that situation. |
| 75 |
(define (make-ulid-generator :optional (random-source ulid-random-source)) |
| 76 |
(let ((randomness (random-source-make-integers random-source)) |
| 77 |
(last-ts 0) |
| 78 |
(last-rn 0)) |
| 79 |
(define (make-it ts rn) |
| 80 |
(set! last-ts ts) |
| 81 |
(set! last-rn rn) |
| 82 |
(%make-ulid ts rn)) |
| 83 |
(^(:optional (timestamp #f)) |
| 84 |
(let retry () |
| 85 |
(let ((ts (or timestamp (milliseconds-from-epoch)))) |
| 86 |
(if (not (= ts last-ts)) |
| 87 |
(make-it ts (randomness *randomness-range*)) |
| 88 |
(if (< last-rn (- *randomness-range* 1)) |
| 89 |
(make-it ts (+ last-rn 1)) |
| 90 |
(begin |
| 91 |
(wait-a-bit randomness) |
| 92 |
(retry))))))))) |
| 93 |
|
| 94 |
;; API |
| 95 |
(define (ulid=? u1 u2) |
| 96 |
(assume (ulid? u1)) |
| 97 |
(assume (ulid? u2)) |
| 98 |
(and (= (ulid-timestamp u1) (ulid-timestamp u2)) |
| 99 |
(= (ulid-randomness u1) (ulid-randomness u2)))) |
| 100 |
|
| 101 |
;; API |
| 102 |
(define (ulid<? u1 u2) |
| 103 |
(assume (ulid? u1)) |
| 104 |
(assume (ulid? u2)) |
| 105 |
(or (< (ulid-timestamp u1) (ulid-timestamp u2)) |
| 106 |
(and (= (ulid-timestamp u1) (ulid-timestamp u2)) |
| 107 |
(< (ulid-randomness u1) (ulid-randomness u2))))) |
| 108 |
|
| 109 |
;; API |
| 110 |
(define (ulid-hash u) |
| 111 |
(bitwise-xor (default-hash (ulid-timestamp u)) |
| 112 |
(default-hash (ulid-randomness u)))) |
| 113 |
|
| 114 |
;; API |
| 115 |
(define ulid-comparator |
| 116 |
(make-comparator ulid? ulid=? ulid<? ulid-hash)) |
| 117 |
|
| 118 |
;; API |
| 119 |
(define (ulid->bytevector ulid) |
| 120 |
(assume (ulid? ulid)) |
| 121 |
(let ((uv (make-u8vector 16)) |
| 122 |
(ts (ulid-timestamp ulid)) |
| 123 |
(rn (ulid-randomness ulid))) |
| 124 |
(u8vector-set! uv 0 (arithmetic-shift ts -40)) |
| 125 |
(u8vector-set! uv 1 (bitwise-and (arithmetic-shift ts -32) #xff)) |
| 126 |
(u8vector-set! uv 2 (bitwise-and (arithmetic-shift ts -24) #xff)) |
| 127 |
(u8vector-set! uv 3 (bitwise-and (arithmetic-shift ts -16) #xff)) |
| 128 |
(u8vector-set! uv 4 (bitwise-and (arithmetic-shift ts -8) #xff)) |
| 129 |
(u8vector-set! uv 5 (bitwise-and ts #xff)) |
| 130 |
|
| 131 |
(u8vector-set! uv 6 (arithmetic-shift rn -72)) |
| 132 |
(u8vector-set! uv 7 (bitwise-and (arithmetic-shift rn -64) #xff)) |
| 133 |
(u8vector-set! uv 8 (bitwise-and (arithmetic-shift rn -56) #xff)) |
| 134 |
(u8vector-set! uv 9 (bitwise-and (arithmetic-shift rn -48) #xff)) |
| 135 |
(u8vector-set! uv 10 (bitwise-and (arithmetic-shift rn -40) #xff)) |
| 136 |
(u8vector-set! uv 11 (bitwise-and (arithmetic-shift rn -32) #xff)) |
| 137 |
(u8vector-set! uv 12 (bitwise-and (arithmetic-shift rn -24) #xff)) |
| 138 |
(u8vector-set! uv 13 (bitwise-and (arithmetic-shift rn -16) #xff)) |
| 139 |
(u8vector-set! uv 14 (bitwise-and (arithmetic-shift rn -8) #xff)) |
| 140 |
(u8vector-set! uv 15 (bitwise-and rn #xff)) |
| 141 |
uv)) |
| 142 |
|
| 143 |
;; API |
| 144 |
(define (ulid->integer ulid) |
| 145 |
(+ (arithmetic-shift (ulid-timestamp ulid) 80) |
| 146 |
(ulid-randomness ulid))) |
| 147 |
|
| 148 |
;; API |
| 149 |
(define (ulid->string ulid) |
| 150 |
(do ((i 0 (+ i 1)) |
| 151 |
(v (ulid->integer ulid) (arithmetic-shift v -5)) |
| 152 |
(cs '() (cons (vector-ref *digits* (bitwise-and v #x1f)) cs))) |
| 153 |
((= i 26) (list->string cs)))) |
| 154 |
|
| 155 |
|
| 156 |
;; API |
| 157 |
(define (bytevector->ulid uv) |
| 158 |
(define (get-uint start size) |
| 159 |
(do ((i start (+ i 1)) |
| 160 |
(size size (- size 1)) |
| 161 |
(v 0 (+ (arithmetic-shift v 8) (u8vector-ref uv i)))) |
| 162 |
((zero? size) v))) |
| 163 |
(assume (and (u8vector? uv) (= (bytevector-length uv) 16))) |
| 164 |
(%make-ulid (get-uint 0 6) (get-uint 6 10))) |
| 165 |
|
| 166 |
;; API |
| 167 |
(define (integer->ulid n) |
| 168 |
(assume (and (exact? n) (positive? n) (< n (expt 2 128)))) |
| 169 |
(%make-ulid (arithmetic-shift n -80) |
| 170 |
(bitwise-and n (- (expt 2 80) 1)))) |
| 171 |
|
| 172 |
;; API |
| 173 |
(define (string->ulid s) |
| 174 |
(assume (and (string? s) (= (string-length s) 26))) |
| 175 |
(let ((val |
| 176 |
(string-fold (lambda (ch n) |
| 177 |
(let ((d (vector-index (lambda (c) (char-ci=? ch c)) |
| 178 |
*digits*))) |
| 179 |
(unless d |
| 180 |
(error "Invalid character as ULID:" ch)) |
| 181 |
(+ (arithmetic-shift n 5) d))) |
| 182 |
0 s))) |
| 183 |
(when (>= val (expt 2 128)) |
| 184 |
(error "ULID string representation out of range:" s)) |
| 185 |
(integer->ulid val))) |
| 186 |
|
| 187 |
;; Fancier printing, if possible |
| 188 |
(define-method write-object ((u ulid) port) |
| 189 |
(format port "#<ulid ~a>" (ulid->string u))) |