/
uuidv7.h
307 lines (274 loc) · 10.2 KB
/
uuidv7.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
/**
* @file
*
* uuidv7.h - Single-file C/C++ UUIDv7 Library
*
* @version v0.1.6
* @author LiosK
* @copyright Licensed under the Apache License, Version 2.0
* @see https://github.com/LiosK/uuidv7-h
*/
/*
* Copyright 2022 LiosK
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef UUIDV7_H_BAEDKYFQ
#define UUIDV7_H_BAEDKYFQ
#include <stddef.h>
#include <stdint.h>
/**
* @name Status codes returned by uuidv7_generate()
*
* @{
*/
/**
* Indicates that the `unix_ts_ms` passed was used because no preceding UUID was
* specified.
*/
#define UUIDV7_STATUS_UNPRECEDENTED (0)
/**
* Indicates that the `unix_ts_ms` passed was used because it was greater than
* the previous one.
*/
#define UUIDV7_STATUS_NEW_TIMESTAMP (1)
/**
* Indicates that the counter was incremented because the `unix_ts_ms` passed
* was no greater than the previous one.
*/
#define UUIDV7_STATUS_COUNTER_INC (2)
/**
* Indicates that the previous `unix_ts_ms` was incremented because the counter
* reached its maximum value.
*/
#define UUIDV7_STATUS_TIMESTAMP_INC (3)
/**
* Indicates that the monotonic order of generated UUIDs was broken because the
* `unix_ts_ms` passed was less than the previous one by more than ten seconds.
*/
#define UUIDV7_STATUS_CLOCK_ROLLBACK (4)
/** Indicates that an invalid `unix_ts_ms` is passed. */
#define UUIDV7_STATUS_ERR_TIMESTAMP (-1)
/**
* Indicates that the attempt to increment the previous `unix_ts_ms` failed
* because it had reached its maximum value.
*/
#define UUIDV7_STATUS_ERR_TIMESTAMP_OVERFLOW (-2)
/** @} */
#ifdef __cplusplus
extern "C" {
#endif
/**
* @name Low-level primitives
*
* @{
*/
/**
* Generates a new UUIDv7 from the given Unix time, random bytes, and previous
* UUID.
*
* @param uuid_out 16-byte byte array where the generated UUID is stored.
* @param unix_ts_ms Current Unix time in milliseconds.
* @param rand_bytes At least 10-byte byte array filled with random bytes. This
* function consumes the leading 4 bytes or the whole 10
* bytes per call depending on the conditions.
* `uuidv7_status_n_rand_consumed()` maps the return value of
* this function to the number of random bytes consumed.
* @param uuid_prev 16-byte byte array representing the immediately preceding
* UUID, from which the previous timestamp and counter are
* extracted. This may be NULL if the caller does not care
* the ascending order of UUIDs within the same timestamp.
* This may point to the same location as `uuid_out`; this
* function reads the value before writing.
* @return One of the `UUIDV7_STATUS_*` codes that describe the
* characteristics of generated UUIDs. Callers can usually
* ignore the status unless they need to guarantee the
* monotonic order of UUIDs or fine-tune the generation
* process.
*/
static inline int8_t uuidv7_generate(uint8_t *uuid_out, uint64_t unix_ts_ms,
const uint8_t *rand_bytes,
const uint8_t *uuid_prev) {
static const uint64_t MAX_TIMESTAMP = ((uint64_t)1 << 48) - 1;
static const uint64_t MAX_COUNTER = ((uint64_t)1 << 42) - 1;
if (unix_ts_ms > MAX_TIMESTAMP) {
return UUIDV7_STATUS_ERR_TIMESTAMP;
}
int8_t status;
uint64_t timestamp = 0;
if (uuid_prev == NULL) {
status = UUIDV7_STATUS_UNPRECEDENTED;
timestamp = unix_ts_ms;
} else {
for (int i = 0; i < 6; i++) {
timestamp = (timestamp << 8) | uuid_prev[i];
}
if (unix_ts_ms > timestamp) {
status = UUIDV7_STATUS_NEW_TIMESTAMP;
timestamp = unix_ts_ms;
} else if (unix_ts_ms + 10000 < timestamp) {
// ignore prev if clock moves back by more than ten seconds
status = UUIDV7_STATUS_CLOCK_ROLLBACK;
timestamp = unix_ts_ms;
} else {
// increment prev counter
uint64_t counter = uuid_prev[6] & 0x0f; // skip ver
counter = (counter << 8) | uuid_prev[7];
counter = (counter << 6) | (uuid_prev[8] & 0x3f); // skip var
counter = (counter << 8) | uuid_prev[9];
counter = (counter << 8) | uuid_prev[10];
counter = (counter << 8) | uuid_prev[11];
if (counter++ < MAX_COUNTER) {
status = UUIDV7_STATUS_COUNTER_INC;
uuid_out[6] = counter >> 38; // ver + bits 0-3
uuid_out[7] = counter >> 30; // bits 4-11
uuid_out[8] = counter >> 24; // var + bits 12-17
uuid_out[9] = counter >> 16; // bits 18-25
uuid_out[10] = counter >> 8; // bits 26-33
uuid_out[11] = counter; // bits 34-41
} else {
// increment prev timestamp at counter overflow
status = UUIDV7_STATUS_TIMESTAMP_INC;
timestamp++;
if (timestamp > MAX_TIMESTAMP) {
return UUIDV7_STATUS_ERR_TIMESTAMP_OVERFLOW;
}
}
}
}
uuid_out[0] = timestamp >> 40;
uuid_out[1] = timestamp >> 32;
uuid_out[2] = timestamp >> 24;
uuid_out[3] = timestamp >> 16;
uuid_out[4] = timestamp >> 8;
uuid_out[5] = timestamp;
for (int i = (status == UUIDV7_STATUS_COUNTER_INC) ? 12 : 6; i < 16; i++) {
uuid_out[i] = *rand_bytes++;
}
uuid_out[6] = 0x70 | (uuid_out[6] & 0x0f); // set ver
uuid_out[8] = 0x80 | (uuid_out[8] & 0x3f); // set var
return status;
}
/**
* Determines the number of random bytes consumsed by `uuidv7_generate()` from
* the `UUIDV7_STATUS_*` code returned.
*
* @param status `UUIDV7_STATUS_*` code returned by `uuidv7_generate()`.
* @return `4` if `status` is `UUIDV7_STATUS_COUNTER_INC` or `10`
* otherwise.
*/
static inline int uuidv7_status_n_rand_consumed(int8_t status) {
return status == UUIDV7_STATUS_COUNTER_INC ? 4 : 10;
}
/**
* Encodes a UUID in the 8-4-4-4-12 hexadecimal string representation.
*
* @param uuid 16-byte byte array representing the UUID to encode.
* @param string_out Character array where the encoded string is stored. Its
* length must be 37 (36 digits + NUL) or longer.
*/
static inline void uuidv7_to_string(const uint8_t *uuid, char *string_out) {
static const char DIGITS[] = "0123456789abcdef";
for (int i = 0; i < 16; i++) {
uint_fast8_t e = uuid[i];
*string_out++ = DIGITS[e >> 4];
*string_out++ = DIGITS[e & 15];
if (i == 3 || i == 5 || i == 7 || i == 9) {
*string_out++ = '-';
}
}
*string_out = '\0';
}
/**
* Decodes the 8-4-4-4-12 hexadecimal string representation of a UUID.
*
* @param string 37-byte (36 digits + NUL) character array representing the
* 8-4-4-4-12 hexadecimal string representation.
* @param uuid_out 16-byte byte array where the decoded UUID is stored.
* @return Zero on success or non-zero integer on failure.
*/
static inline int uuidv7_from_string(const char *string, uint8_t *uuid_out) {
for (int i = 0; i < 32; i++) {
char c = *string++;
// clang-format off
uint8_t x = c == '0' ? 0 : c == '1' ? 1 : c == '2' ? 2 : c == '3' ? 3
: c == '4' ? 4 : c == '5' ? 5 : c == '6' ? 6 : c == '7' ? 7
: c == '8' ? 8 : c == '9' ? 9 : c == 'a' ? 10 : c == 'b' ? 11
: c == 'c' ? 12 : c == 'd' ? 13 : c == 'e' ? 14 : c == 'f' ? 15
: c == 'A' ? 10 : c == 'B' ? 11 : c == 'C' ? 12 : c == 'D' ? 13
: c == 'E' ? 14 : c == 'F' ? 15 : 0xff;
// clang-format on
if (x == 0xff) {
return -1; // invalid digit
}
if ((i & 1) == 0) {
uuid_out[i >> 1] = x << 4; // even i => hi 4 bits
} else {
uuid_out[i >> 1] |= x; // odd i => lo 4 bits
}
if ((i == 7 || i == 11 || i == 15 || i == 19) && (*string++ != '-')) {
return -1; // invalid format
}
}
if (*string != '\0') {
return -1; // invalid length
}
return 0; // success
}
/** @} */
/**
* @name High-level APIs that require platform integration
*
* @{
*/
/**
* Generates a new UUIDv7 with the current Unix time.
*
* This declaration defines the interface to generate a new UUIDv7 with the
* current time, default random number generator, and global shared state
* holding the previously generated UUID. Since this single-file library does
* not provide platform-specific implementations, users need to prepare a
* concrete implementation (if necessary) by integrating a real-time clock,
* cryptographically strong random number generator, and shared state storage
* available in the target platform.
*
* @param uuid_out 16-byte byte array where the generated UUID is stored.
* @return One of the `UUIDV7_STATUS_*` codes that describe the
* characteristics of generated UUIDs or an
* implementation-dependent code. Callers can usually ignore
* the `UUIDV7_STATUS_*` code unless they need to guarantee the
* monotonic order of UUIDs or fine-tune the generation
* process. The implementation-dependent code must be out of
* the range of `int8_t` and negative if it reports an error.
*/
int uuidv7_new(uint8_t *uuid_out);
/**
* Generates an 8-4-4-4-12 hexadecimal string representation of new UUIDv7.
*
* @param string_out Character array where the encoded string is stored. Its
* length must be 37 (36 digits + NUL) or longer.
* @return Return value of `uuidv7_new()`.
* @note Provide a concrete `uuidv7_new()` implementation to enable
* this function.
*/
static inline int uuidv7_new_string(char *string_out) {
uint8_t uuid[16];
int result = uuidv7_new(uuid);
uuidv7_to_string(uuid, string_out);
return result;
}
/** @} */
#ifdef __cplusplus
} /* extern "C" { */
#endif
#endif /* #ifndef UUIDV7_H_BAEDKYFQ */