1 /*
2 * Copyright 2022 Búraló Technologies
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 */
17 package com.buralotech.oss.identifier.uuid;
18
19 import com.buralotech.oss.identifier.api.Identifier;
20 import com.buralotech.oss.identifier.api.IdentifierService;
21
22 import java.time.*;
23 import java.time.temporal.Temporal;
24 import java.util.Arrays;
25
26 /**
27 * Generate identifiers and parse binary and textual representations of identifiers. The generator uses either a Type 1
28 * UUID generator and juggles the bits so that the binary representations can be ordered by generation time or a new
29 * Type 6 UUID which is reordered in a similar way but is standardised. The textual representation is a modified
30 * URL-safe base 64 encoding that is also sortable.
31 */
32 public final class UUIDIdentifierService implements IdentifierService {
33
34 /**
35 * Look-up table used during encoding.
36 */
37 private static final char[] ENCODING = {
38 '-', '0', '1', '2', '3', '4', '5', '6', '7', '8',
39 '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
40 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
41 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '_', 'a', 'b',
42 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
43 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
44 'w', 'x', 'y', 'z'
45 };
46
47 /**
48 * Look-up table used during decoding.
49 */
50 private static final int[] DECODING = new int[256];
51
52 /*
53 * Initialise the array used for look-ups during decoding.
54 */
55 static {
56 // First mark all the values as invalid (-1)
57
58 Arrays.fill(DECODING, -1);
59
60 // Now map all the supported Base64 digits to their ordinal value
61
62 for (int i = 0; i < ENCODING.length; i++) {
63 DECODING[ENCODING[i]] = i;
64 }
65 }
66
67 /**
68 * Number of ticks per millisecond. The UUID tick is 100 nanoseconds.
69 */
70 private static final long TICKS_PER_MILLISECOND = 10000L;
71
72 /**
73 * Number of ticks per second. TheUUID thick is 100 nanoseconds.
74 */
75 private static final long TICKS_PER_SECOND = 10000000L;
76
77 /**
78 * The adjustment to apply to convert UUID epoch to Unix Epoch. The UUID epoch 15 October 1582, while the Unix
79 * epoch is 1 January 1970.
80 */
81 private static final long EPOCH_ADJ = 122192928000000000L;
82 // private static final long EPOCH_ADJ = 122192910170000000L;
83
84 /**
85 * Delegate that encapsulates logic that is specific to the UUID format.
86 */
87 private final UUIDVersionDelegate delegate;
88
89 /**
90 * Constructor used to inject the delegate that encapsulates the logic that is specific to the UUID format.
91 *
92 * @param delegate Encapsulates logic that is specific to the UUID format.
93 */
94 public UUIDIdentifierService(final UUIDVersionDelegate delegate) {
95 this.delegate = delegate;
96 }
97
98 /**
99 * Generate an identifier using an underlying UUID generator.
100 *
101 * @return The generated identifier.
102 */
103 @Override
104 public Identifier generate() {
105 final var binary = delegate.generate();
106 final var text = encode(binary);
107 return new UUIDIdentifier(text, binary);
108 }
109
110 /**
111 * Decode an identifier using its text representation.
112 *
113 * @param text The text representation.
114 * @return The identifier.
115 */
116 @Override
117 public Identifier fromText(final String text) {
118 if (text == null || !delegate.isValidText(text)) {
119 throw new IllegalArgumentException("invalid text representation of identifier");
120 }
121 final var binary = decode(text);
122 return new UUIDIdentifier(text, binary);
123 }
124
125 /**
126 * Decode an identifier using its binary representation.
127 *
128 * @param binary The binary representation.
129 * @return The identifier.
130 */
131 @Override
132 public Identifier fromBinary(final byte[] binary) {
133 if (binary == null || binary.length != 16 || !delegate.isValidBinary(binary)) {
134 throw new IllegalArgumentException("invalid binary representation of identifier");
135 }
136 final var text = encode(binary);
137 return new UUIDIdentifier(text, binary);
138 }
139
140 /**
141 * Encode 16 bytes as 22 Base64 digit string.
142 *
143 * @param bytes The 16 input bytes.
144 * @return The 22 digit Base64 string.
145 */
146 private String encode(final byte[] bytes) {
147 assert bytes != null && bytes.length == 16;
148 final var chars = new char[22];
149 var i = 0;
150 var j = 0;
151 do {
152 encode3(bytes[i], bytes[i + 1], bytes[i + 2], chars, j);
153 i += 3;
154 j += 4;
155 } while (i < 15);
156 encode1(bytes[i], chars, j);
157 return new String(chars);
158 }
159
160 /**
161 * Encode three bytes as 4 Base64 digits.
162 *
163 * @param b1 The first byte.
164 * @param b2 The second byte.
165 * @param b3 The third byte.
166 * @param chars The output character array in which the base 64 digits will be stored.
167 * @param j The position at whichthe first Base64 digit will be stored.
168 */
169 private void encode3(final byte b1,
170 final byte b2,
171 final byte b3,
172 final char[] chars,
173 final int j) {
174 chars[j] = ENCODING[(b1 & 0xfc) >> 2];
175 chars[j + 1] = ENCODING[((b1 & 0x3) << 4) | ((b2 & 0xf0) >> 4)];
176 chars[j + 2] = ENCODING[((b2 & 0xf) << 2) | ((b3 & 0xc0) >> 6)];
177 chars[j + 3] = ENCODING[b3 & 0x3f];
178 }
179
180 /**
181 * Encode a single byte as 2 Base64 digits.
182 *
183 * @param b1 The input byte.
184 * @param chars The output character array in which the base 64 digits will be stored.
185 * @param j The position at whichthe first Base64 digit will be stored.
186 */
187 private void encode1(final byte b1,
188 final char[] chars,
189 final int j) {
190 chars[j] = ENCODING[(b1 & 0xfc) >> 2];
191 chars[j + 1] = ENCODING[(b1 & 0x3) << 4];
192 }
193
194 /**
195 * Decode a 22 Base64 digit string into 16 bytes.
196 *
197 * @param str The Base64 digit string.
198 * @return The 16 bytes.
199 */
200 private byte[] decode(final String str) {
201 assert str != null && str.length() == 22;
202 final var bytes = new byte[16];
203 var i = 0;
204 var j = 0;
205 do {
206 decode4(bytes, i, str, j);
207 i += 3;
208 j += 4;
209 } while (i < 15);
210 decode2(bytes, i, str, j);
211 return bytes;
212 }
213
214 /**
215 * Decode 4 Base64 digits into 3 bytes.
216 *
217 * @param bytes The destination where decoded bytes will be stored.
218 * @param i The position at which to store the first decoded bytes.
219 * @param str A string of Base64 digits.
220 * @param j The position of the first Base64 digit.
221 */
222 private void decode4(final byte[] bytes,
223 final int i,
224 final String str,
225 final int j) {
226 final var w = decode(str.charAt(j));
227 final var x = decode(str.charAt(j + 1));
228 final var y = decode(str.charAt(j + 2));
229 final var z = decode(str.charAt(j + 3));
230 bytes[i] = (byte) ((w << 2) | ((x & 0x30) >> 4));
231 bytes[i + 1] = (byte) (((x & 0xf) << 4) | ((y & 0x3c) >> 2));
232 bytes[i + 2] = (byte) (((y & 0x3) << 6) | z);
233 }
234
235 /**
236 * Decode 2 Base64 digits into 1 byte.
237 *
238 * @param bytes The destination where decoded bytes will be stored.
239 * @param dest The position at which to store the decoded byte.
240 * @param string A string of Base64 digits.
241 * @param src The position of the first Base64 digit.
242 */
243 private void decode2(final byte[] bytes,
244 final int dest,
245 final String string,
246 final int src) {
247 final var w = decode(string.charAt(src));
248 final var x = decode(string.charAt(src + 1));
249 bytes[dest] = (byte) ((w << 2) | ((x & 0x30) >> 4));
250 }
251
252 /**
253 * Decode a single Base64 digit.
254 *
255 * @param ch The Base64 digit.
256 * @return The value of the Base64 digit.
257 */
258 private int decode(final char ch) {
259 assert ch <= 256;
260 final var value = DECODING[ch];
261 assert value != -1;
262 return value;
263 }
264
265 /**
266 * Extract an instant from an identifier.
267 *
268 * @param identifier The identifier.
269 * @return The instant.
270 */
271 @Override
272 public Instant toInstant(final Identifier identifier) {
273 if (identifier == null) {
274 return null;
275 }
276 if (identifier instanceof UUIDIdentifier uuidIdentifier) {
277 return delegate.toInstant(uuidIdentifier.binary());
278
279 } else {
280 throw new IllegalArgumentException("UUIDIdentifier is required");
281 }
282 }
283
284 /**
285 * Generate a lower-bound identifier for temporal value that can be used in range queries.
286 *
287 * @param time The temporal value ({@link java.time.Instant}, {@link java.time.LocalDate},
288 * {@link java.time.LocalDateTime}, {@link java.time.OffsetDateTime},
289 * {@link java.time.ZonedDateTime})
290 * @return A lower-bound identifier that can be used in a range query.
291 * @throws IllegalArgumentException If the temporal type is not supported.
292 */
293 @Override
294 public Identifier asLowerBound(final Temporal time) {
295 final var binary = delegate.fromTicks(toTicks(time, false), 0x8000000000000000L);
296 final var text = encode(binary);
297 return new UUIDIdentifier(text, binary);
298 }
299
300 /**
301 * Generate an upper-bound identifier for temporal value that can be used in range queries.
302 *
303 * @param time The temporal value ({@link java.time.Instant}, {@link java.time.LocalDate},
304 * {@link java.time.LocalDateTime}, {@link java.time.OffsetDateTime},
305 * {@link java.time.ZonedDateTime})
306 * @return An upper-bound identifier that can be used in a range query.
307 * @throws IllegalArgumentException If the temporal type is not supported.
308 */
309 @Override
310 public Identifier asUpperBound(final Temporal time) {
311 final var binary = delegate.fromTicks(toTicks(time, true), 0x8FFFFFFFFFFFFFFFL);
312 final var text = encode(binary);
313 return new UUIDIdentifier(text, binary);
314 }
315
316 /**
317 * Given a temporal value extract the number of UUID ticks (100 nanoseconds).
318 *
319 * @param temporal The temporal value ({@link java.time.Instant}, {@link java.time.LocalDate},
320 * {@link java.time.LocalDateTime}, {@link java.time.OffsetDateTime},
321 * {@link java.time.ZonedDateTime})
322 * @return The number of ticks.
323 * @throws IllegalArgumentException If the temporal type is not supported.
324 */
325 private long toTicks(final Temporal temporal, final boolean upper) {
326 switch (temporal) {
327 case Instant instant -> {
328 final var adj = EPOCH_ADJ + (upper ? TICKS_PER_MILLISECOND - 1 : 0L);
329 return instant.toEpochMilli() * TICKS_PER_MILLISECOND + adj;
330 }
331 case LocalDate date -> {
332 final var time = upper ? LocalTime.of(23, 59, 59) : LocalTime.of(0, 0, 0);
333 final var adj = EPOCH_ADJ + (upper ? TICKS_PER_SECOND - 1 : 0L);
334 return date.toEpochSecond(time, ZoneOffset.UTC) * TICKS_PER_SECOND + adj;
335 }
336 case LocalDateTime dateTime -> {
337 final var adj = EPOCH_ADJ + (upper ? TICKS_PER_SECOND - 1 : 0L);
338 return dateTime.toEpochSecond(ZoneOffset.UTC) * TICKS_PER_SECOND + adj;
339 }
340 case OffsetDateTime dateTime -> {
341 final var adj = EPOCH_ADJ + (upper ? TICKS_PER_SECOND - 1 : 0L);
342 return dateTime.toEpochSecond() * TICKS_PER_SECOND + adj;
343 }
344 case ZonedDateTime dateTime -> {
345 final var adj = EPOCH_ADJ + (upper ? TICKS_PER_SECOND - 1 : 0L);
346 return dateTime.toEpochSecond() * TICKS_PER_SECOND + adj;
347 }
348 default -> throw new IllegalArgumentException(temporal.getClass().getName() + " is not supported");
349 }
350 }
351 }