ulid
ulid_uint128.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <chrono>
4 #include <cstdlib>
5 #include <ctime>
6 #include <functional>
7 #include <random>
8 #include <vector>
9 
10 namespace ulid {
11 
12 /**
13  * ULID is a 16 byte Universally Unique Lexicographically Sortable Identifier
14  * */
15 typedef __uint128_t ULID;
16 
17 /**
18  * EncodeTime will encode the first 6 bytes of a uint8_t array to the passed
19  * timestamp
20  * */
21 void EncodeTime(time_t timestamp, ULID& ulid) {
22  ULID t = static_cast<uint8_t>(timestamp >> 40);
23 
24  t <<= 8;
25  t |= static_cast<uint8_t>(timestamp >> 32);
26 
27  t <<= 8;
28  t |= static_cast<uint8_t>(timestamp >> 24);
29 
30  t <<= 8;
31  t |= static_cast<uint8_t>(timestamp >> 16);
32 
33  t <<= 8;
34  t |= static_cast<uint8_t>(timestamp >> 8);
35 
36  t <<= 8;
37  t |= static_cast<uint8_t>(timestamp);
38 
39  t <<= 80;
40 
41  ULID mask = 1;
42  mask <<= 80;
43  mask--;
44 
45  ulid = t | (ulid & mask);
46 }
47 
48 /**
49  * EncodeTimeNow will encode a ULID using the time obtained using std::time(nullptr)
50  * */
51 void EncodeTimeNow(ULID& ulid) {
52  EncodeTime(std::time(nullptr), ulid);
53 }
54 
55 /**
56  * EncodeTimeSystemClockNow will encode a ULID using the time obtained using
57  * std::chrono::system_clock::now() by taking the timestamp in milliseconds.
58  * */
59 void EncodeTimeSystemClockNow(ULID& ulid) {
60  auto now = std::chrono::system_clock::now();
61  auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
62  EncodeTime(ms.count(), ulid);
63 }
64 
65 /**
66  * EncodeEntropy will encode the last 10 bytes of the passed uint8_t array with
67  * the values generated using the passed random number generator.
68  * */
69 void EncodeEntropy(const std::function<uint8_t()>& rng, ULID& ulid) {
70  ulid = (ulid >> 80) << 80;
71 
72  ULID e = rng();
73 
74  e <<= 8;
75  e |= rng();
76 
77  e <<= 8;
78  e |= rng();
79 
80  e <<= 8;
81  e |= rng();
82 
83  e <<= 8;
84  e |= rng();
85 
86  e <<= 8;
87  e |= rng();
88 
89  e <<= 8;
90  e |= rng();
91 
92  e <<= 8;
93  e |= rng();
94 
95  e <<= 8;
96  e |= rng();
97 
98  e <<= 8;
99  e |= rng();
100 
101  ulid |= e;
102 }
103 
104 /**
105  * EncodeEntropyRand will encode a ulid using std::rand
106  *
107  * std::rand returns values in [0, RAND_MAX]
108  * */
109 void EncodeEntropyRand(ULID& ulid) {
110  ulid = (ulid >> 80) << 80;
111 
112  ULID e = (std::rand() * 255ull) / RAND_MAX;
113 
114  e <<= 8;
115  e |= (std::rand() * 255ull) / RAND_MAX;
116 
117  e <<= 8;
118  e |= (std::rand() * 255ull) / RAND_MAX;
119 
120  e <<= 8;
121  e |= (std::rand() * 255ull) / RAND_MAX;
122 
123  e <<= 8;
124  e |= (std::rand() * 255ull) / RAND_MAX;
125 
126  e <<= 8;
127  e |= (std::rand() * 255ull) / RAND_MAX;
128 
129  e <<= 8;
130  e |= (std::rand() * 255ull) / RAND_MAX;
131 
132  e <<= 8;
133  e |= (std::rand() * 255ull) / RAND_MAX;
134 
135  e <<= 8;
136  e |= (std::rand() * 255ull) / RAND_MAX;
137 
138  e <<= 8;
139  e |= (std::rand() * 255ull) / RAND_MAX;
140 
141  ulid |= e;
142 }
143 
144 std::uniform_int_distribution<uint8_t> Distribution_0_255(0, 255);
145 
146 /**
147  * EncodeEntropyMt19937 will encode a ulid using std::mt19937
148  *
149  * It also creates a std::uniform_int_distribution to generate values in [0, 255]
150  * */
151 void EncodeEntropyMt19937(std::mt19937& generator, ULID& ulid) {
152  ulid = (ulid >> 80) << 80;
153 
154  ULID e = Distribution_0_255(generator);
155 
156  e <<= 8;
157  e |= Distribution_0_255(generator);
158 
159  e <<= 8;
160  e |= Distribution_0_255(generator);
161 
162  e <<= 8;
163  e |= Distribution_0_255(generator);
164 
165  e <<= 8;
166  e |= Distribution_0_255(generator);
167 
168  e <<= 8;
169  e |= Distribution_0_255(generator);
170 
171  e <<= 8;
172  e |= Distribution_0_255(generator);
173 
174  e <<= 8;
175  e |= Distribution_0_255(generator);
176 
177  e <<= 8;
178  e |= Distribution_0_255(generator);
179 
180  e <<= 8;
181  e |= Distribution_0_255(generator);
182 
183  ulid |= e;
184 }
185 
186 /**
187  * Encode will create an encoded ULID with a timestamp and a generator.
188  * */
189 void Encode(time_t timestamp, const std::function<uint8_t()>& rng, ULID& ulid) {
190  EncodeTime(timestamp, ulid);
191  EncodeEntropy(rng, ulid);
192 }
193 
194 /**
195  * EncodeNowRand = EncodeTimeNow + EncodeEntropyRand.
196  * */
197 void EncodeNowRand(ULID& ulid) {
198  EncodeTimeNow(ulid);
199  EncodeEntropyRand(ulid);
200 }
201 
202 /**
203  * Create will create a ULID with a timestamp and a generator.
204  * */
205 ULID Create(time_t timestamp, const std::function<uint8_t()>& rng) {
206  ULID ulid;
207  Encode(timestamp, rng, ulid);
208  return ulid;
209 }
210 
211 /**
212  * CreateNowRand:EncodeNowRand = Create:Encode.
213  * */
214 ULID CreateNowRand() {
215  ULID ulid;
216  EncodeNowRand(ulid);
217  return ulid;
218 }
219 
220 /**
221  * Crockford's Base32
222  * */
223 const char Encoding[33] = "0123456789ABCDEFGHJKMNPQRSTVWXYZ";
224 
225 /**
226  * MarshalTo will marshal a ULID to the passed character array.
227  *
228  * Implementation taken directly from oklog/ulid
229  * (https://sourcegraph.com/github.com/oklog/ulid@0774f81f6e44af5ce5e91c8d7d76cf710e889ebb/-/blob/ulid.go#L162-190)
230  *
231  * timestamp:
232  * dst[0]: first 3 bits of data[0]
233  * dst[1]: last 5 bits of data[0]
234  * dst[2]: first 5 bits of data[1]
235  * dst[3]: last 3 bits of data[1] + first 2 bits of data[2]
236  * dst[4]: bits 3-7 of data[2]
237  * dst[5]: last bit of data[2] + first 4 bits of data[3]
238  * dst[6]: last 4 bits of data[3] + first bit of data[4]
239  * dst[7]: bits 2-6 of data[4]
240  * dst[8]: last 2 bits of data[4] + first 3 bits of data[5]
241  * dst[9]: last 5 bits of data[5]
242  *
243  * entropy:
244  * follows similarly, except now all components are set to 5 bits.
245  * */
246 void MarshalTo(const ULID& ulid, char dst[26]) {
247  // 10 byte timestamp
248  dst[0] = Encoding[(static_cast<uint8_t>(ulid >> 120) & 224) >> 5];
249  dst[1] = Encoding[static_cast<uint8_t>(ulid >> 120) & 31];
250  dst[2] = Encoding[(static_cast<uint8_t>(ulid >> 112) & 248) >> 3];
251  dst[3] = Encoding[((static_cast<uint8_t>(ulid >> 112) & 7) << 2) | ((static_cast<uint8_t>(ulid >> 104) & 192) >> 6)];
252  dst[4] = Encoding[(static_cast<uint8_t>(ulid >> 104) & 62) >> 1];
253  dst[5] = Encoding[((static_cast<uint8_t>(ulid >> 104) & 1) << 4) | ((static_cast<uint8_t>(ulid >> 96) & 240) >> 4)];
254  dst[6] = Encoding[((static_cast<uint8_t>(ulid >> 96) & 15) << 1) | ((static_cast<uint8_t>(ulid >> 88) & 128) >> 7)];
255  dst[7] = Encoding[(static_cast<uint8_t>(ulid >> 88) & 124) >> 2];
256  dst[8] = Encoding[((static_cast<uint8_t>(ulid >> 88) & 3) << 3) | ((static_cast<uint8_t>(ulid >> 80) & 224) >> 5)];
257  dst[9] = Encoding[static_cast<uint8_t>(ulid >> 80) & 31];
258 
259  // 16 bytes of entropy
260  dst[10] = Encoding[(static_cast<uint8_t>(ulid >> 72) & 248) >> 3];
261  dst[11] = Encoding[((static_cast<uint8_t>(ulid >> 72) & 7) << 2) | ((static_cast<uint8_t>(ulid >> 64) & 192) >> 6)];
262  dst[12] = Encoding[(static_cast<uint8_t>(ulid >> 64) & 62) >> 1];
263  dst[13] = Encoding[((static_cast<uint8_t>(ulid >> 64) & 1) << 4) | ((static_cast<uint8_t>(ulid >> 56) & 240) >> 4)];
264  dst[14] = Encoding[((static_cast<uint8_t>(ulid >> 56) & 15) << 1) | ((static_cast<uint8_t>(ulid >> 48) & 128) >> 7)];
265  dst[15] = Encoding[(static_cast<uint8_t>(ulid >> 48) & 124) >> 2];
266  dst[16] = Encoding[((static_cast<uint8_t>(ulid >> 48) & 3) << 3) | ((static_cast<uint8_t>(ulid >> 40) & 224) >> 5)];
267  dst[17] = Encoding[static_cast<uint8_t>(ulid >> 40) & 31];
268  dst[18] = Encoding[(static_cast<uint8_t>(ulid >> 32) & 248) >> 3];
269  dst[19] = Encoding[((static_cast<uint8_t>(ulid >> 32) & 7) << 2) | ((static_cast<uint8_t>(ulid >> 24) & 192) >> 6)];
270  dst[20] = Encoding[(static_cast<uint8_t>(ulid >> 24) & 62) >> 1];
271  dst[21] = Encoding[((static_cast<uint8_t>(ulid >> 24) & 1) << 4) | ((static_cast<uint8_t>(ulid >> 16) & 240) >> 4)];
272  dst[22] = Encoding[((static_cast<uint8_t>(ulid >> 16) & 15) << 1) | ((static_cast<uint8_t>(ulid >> 8) & 128) >> 7)];
273  dst[23] = Encoding[(static_cast<uint8_t>(ulid >> 8) & 124) >> 2];
274  dst[24] = Encoding[((static_cast<uint8_t>(ulid >> 8) & 3) << 3) | (((static_cast<uint8_t>(ulid)) & 224) >> 5)];
275  dst[25] = Encoding[(static_cast<uint8_t>(ulid)) & 31];
276 }
277 
278 /**
279  * Marshal will marshal a ULID to a std::string.
280  * */
281 std::string Marshal(const ULID& ulid) {
282  char data[27];
283  data[26] = '\0';
284  MarshalTo(ulid, data);
285  return std::string(data);
286 }
287 
288 /**
289  * MarshalBinaryTo will Marshal a ULID to the passed byte array
290  * */
291 void MarshalBinaryTo(const ULID& ulid, uint8_t dst[16]) {
292  // timestamp
293  dst[0] = static_cast<uint8_t>(ulid >> 120);
294  dst[1] = static_cast<uint8_t>(ulid >> 112);
295  dst[2] = static_cast<uint8_t>(ulid >> 104);
296  dst[3] = static_cast<uint8_t>(ulid >> 96);
297  dst[4] = static_cast<uint8_t>(ulid >> 88);
298  dst[5] = static_cast<uint8_t>(ulid >> 80);
299 
300  // entropy
301  dst[6] = static_cast<uint8_t>(ulid >> 72);
302  dst[7] = static_cast<uint8_t>(ulid >> 64);
303  dst[8] = static_cast<uint8_t>(ulid >> 56);
304  dst[9] = static_cast<uint8_t>(ulid >> 48);
305  dst[10] = static_cast<uint8_t>(ulid >> 40);
306  dst[11] = static_cast<uint8_t>(ulid >> 32);
307  dst[12] = static_cast<uint8_t>(ulid >> 24);
308  dst[13] = static_cast<uint8_t>(ulid >> 16);
309  dst[14] = static_cast<uint8_t>(ulid >> 8);
310  dst[15] = static_cast<uint8_t>(ulid);
311 }
312 
313 /**
314  * MarshalBinary will Marshal a ULID to a byte vector.
315  * */
316 std::vector<uint8_t> MarshalBinary(const ULID& ulid) {
317  std::vector<uint8_t> dst(16);
318  MarshalBinaryTo(ulid, dst.data());
319  return dst;
320 }
321 
322 /**
323  * dec storesdecimal encodings for characters.
324  * 0xFF indicates invalid character.
325  * 48-57 are digits.
326  * 65-90 are capital alphabets.
327  * */
328 const uint8_t dec[256] = {
329  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
330  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
331  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
332  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
333 
334  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
335  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
336  /* 0 1 2 3 4 5 6 7 */
337  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
338  /* 8 9 */
339  0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
340 
341  /* 10(A) 11(B) 12(C) 13(D) 14(E) 15(F) 16(G) */
342  0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10,
343  /*17(H) 18(J) 19(K) 20(M) 21(N) */
344  0x11, 0xFF, 0x12, 0x13, 0xFF, 0x14, 0x15, 0xFF,
345  /*22(P)23(Q)24(R) 25(S) 26(T) 27(V) 28(W) */
346  0x16, 0x17, 0x18, 0x19, 0x1A, 0xFF, 0x1B, 0x1C,
347  /*29(X)30(Y)31(Z) */
348  0x1D, 0x1E, 0x1F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
349 
350  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
351  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
352  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
353  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
354 
355  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
356  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
357  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
358  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
359 
360  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
361  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
362  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
363  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
364 
365  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
366  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
367  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
368  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
369 
370  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
371  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
372  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
373  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
374 };
375 
376 /**
377  * UnmarshalFrom will unmarshal a ULID from the passed character array.
378  * */
379 void UnmarshalFrom(const char str[26], ULID& ulid) {
380  // timestamp
381  ulid = (dec[int(str[0])] << 5) | dec[int(str[1])];
382 
383  ulid <<= 8;
384  ulid |= (dec[int(str[2])] << 3) | (dec[int(str[3])] >> 2);
385 
386  ulid <<= 8;
387  ulid |= (dec[int(str[3])] << 6) | (dec[int(str[4])] << 1) | (dec[int(str[5])] >> 4);
388 
389  ulid <<= 8;
390  ulid |= (dec[int(str[5])] << 4) | (dec[int(str[6])] >> 1);
391 
392  ulid <<= 8;
393  ulid |= (dec[int(str[6])] << 7) | (dec[int(str[7])] << 2) | (dec[int(str[8])] >> 3);
394 
395  ulid <<= 8;
396  ulid |= (dec[int(str[8])] << 5) | dec[int(str[9])];
397 
398  // entropy
399  ulid <<= 8;
400  ulid |= (dec[int(str[10])] << 3) | (dec[int(str[11])] >> 2);
401 
402  ulid <<= 8;
403  ulid |= (dec[int(str[11])] << 6) | (dec[int(str[12])] << 1) | (dec[int(str[13])] >> 4);
404 
405  ulid <<= 8;
406  ulid |= (dec[int(str[13])] << 4) | (dec[int(str[14])] >> 1);
407 
408  ulid <<= 8;
409  ulid |= (dec[int(str[14])] << 7) | (dec[int(str[15])] << 2) | (dec[int(str[16])] >> 3);
410 
411  ulid <<= 8;
412  ulid |= (dec[int(str[16])] << 5) | dec[int(str[17])];
413 
414  ulid <<= 8;
415  ulid |= (dec[int(str[18])] << 3) | (dec[int(str[19])] >> 2);
416 
417  ulid <<= 8;
418  ulid |= (dec[int(str[19])] << 6) | (dec[int(str[20])] << 1) | (dec[int(str[21])] >> 4);
419 
420  ulid <<= 8;
421  ulid |= (dec[int(str[21])] << 4) | (dec[int(str[22])] >> 1);
422 
423  ulid <<= 8;
424  ulid |= (dec[int(str[22])] << 7) | (dec[int(str[23])] << 2) | (dec[int(str[24])] >> 3);
425 
426  ulid <<= 8;
427  ulid |= (dec[int(str[24])] << 5) | dec[int(str[25])];
428 }
429 
430 /**
431  * Unmarshal will create a new ULID by unmarshaling the passed string.
432  * */
433 ULID Unmarshal(const std::string& str) {
434  ULID ulid;
435  UnmarshalFrom(str.c_str(), ulid);
436  return ulid;
437 }
438 
439 /**
440  * UnmarshalBinaryFrom will unmarshal a ULID from the passed byte array.
441  * */
442 void UnmarshalBinaryFrom(const uint8_t b[16], ULID& ulid) {
443  // timestamp
444  ulid = b[0];
445 
446  ulid <<= 8;
447  ulid |= b[1];
448 
449  ulid <<= 8;
450  ulid |= b[2];
451 
452  ulid <<= 8;
453  ulid |= b[3];
454 
455  ulid <<= 8;
456  ulid |= b[4];
457 
458  ulid <<= 8;
459  ulid |= b[5];
460 
461  // entropy
462  ulid <<= 8;
463  ulid |= b[6];
464 
465  ulid <<= 8;
466  ulid |= b[7];
467 
468  ulid <<= 8;
469  ulid |= b[8];
470 
471  ulid <<= 8;
472  ulid |= b[9];
473 
474  ulid <<= 8;
475  ulid |= b[10];
476 
477  ulid <<= 8;
478  ulid |= b[11];
479 
480  ulid <<= 8;
481  ulid |= b[12];
482 
483  ulid <<= 8;
484  ulid |= b[13];
485 
486  ulid <<= 8;
487  ulid |= b[14];
488 
489  ulid <<= 8;
490  ulid |= b[15];
491 }
492 
493 /**
494  * Unmarshal will create a new ULID by unmarshaling the passed byte vector.
495  * */
496 ULID UnmarshalBinary(const std::vector<uint8_t>& b) {
497  ULID ulid;
498  UnmarshalBinaryFrom(b.data(), ulid);
499  return ulid;
500 }
501 
502 /**
503  * CompareULIDs will compare two ULIDs.
504  * returns:
505  * -1 if ulid1 is Lexicographically before ulid2
506  * 1 if ulid1 is Lexicographically after ulid2
507  * 0 if ulid1 is same as ulid2
508  * */
509 int CompareULIDs(const ULID& ulid1, const ULID& ulid2) {
510  return -2 * (ulid1 < ulid2) - 1 * (ulid1 == ulid2) + 1;
511 }
512 
513 /**
514  * Time will extract the timestamp used to generate a ULID
515  * */
516 time_t Time(const ULID& ulid) {
517  time_t ans = 0;
518 
519  ans |= static_cast<uint8_t>(ulid >> 120);
520 
521  ans <<= 8;
522  ans |= static_cast<uint8_t>(ulid >> 112);
523 
524  ans <<= 8;
525  ans |= static_cast<uint8_t>(ulid >> 104);
526 
527  ans <<= 8;
528  ans |= static_cast<uint8_t>(ulid >> 96);
529 
530  ans <<= 8;
531  ans |= static_cast<uint8_t>(ulid >> 88);
532 
533  ans <<= 8;
534  ans |= static_cast<uint8_t>(ulid >> 80);
535 
536  return ans;
537 }
538 
539 }; // namespace ulid
ulid::UnmarshalBinary
ULID UnmarshalBinary(const std::vector< uint8_t > &b)
Definition: ulid_struct.hh:584
ulid::CreateNowRand
ULID CreateNowRand()
Definition: ulid_struct.hh:360
ulid::Distribution_0_255
std::uniform_int_distribution< uint8_t > Distribution_0_255(0, 255)
ulid
Definition: ulid_struct.hh:10
ulid::Create
ULID Create(time_t timestamp, const std::function< uint8_t()> &rng)
Definition: ulid_struct.hh:351
ulid::ULID
__uint128_t ULID
Definition: ulid_uint128.hh:15
ulid::Unmarshal
ULID Unmarshal(const std::string &str)
Definition: ulid_struct.hh:550
Generated by   doxygen 1.8.11