I recently found the need to generate universally unique identifier (IDs used to uniquely identify data) for a project at work, and found myself knee deep in unfamiliar material: blog post time! Let’s walk through one ferocious implementation I found online.
The first half of our function uses time to add additional randomness to our pseudo-random number generator. The second half generates random hex values based on our numbers. But before we break down how each line accomplishes this, let’s learn a bit about what UUIDs are.
UUIDs
Universally unique identifier (UUID a.k.a. GUID) a is a 128-bit number that can be used to identify unique items online. A 128-bit number can hold a lot of data: 340,282,366,920,938,463,463,374,607,431,768,211,455 (3.4 * 10³⁸) ones and zeroes. Counting by tens takes a lot of characters (39). We can cut it down to 32 characters if we just count by 16s (hexadecimal a.k.a hex) instead of by 10s (decimals). Hexadecimals accomplish 16 digits before starting over by using 16 possible characters: ‘0’ through ‘9’ and ‘A’ through ‘F’. Hexadecimals are used everywhere — even in this blog post’s URL! But you’re not here for the math! Let’s summarize:
- Hexadecimal (base 16): 16^³² = 128-bits
- Decimal (base 10): 3.4 * 10³⁸ = 128-bits
- 2¹²⁸ (base 2): 2¹²⁸ = 128-bits
Whew. I’m eager to talk code, but there’s one more thing about UUIDs I must mention before we continue: they are a standard. An all volunteer group called the Internet Engineering Task Force (IETF) came up with a standard for IDs called RFC 4122. The format looks like so:
xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx
That 4 is strange, right? It’s part of the standard. It means these numbers are generated from pseudo-random numbers. Version 1: generates a unique ID based on a network card MAC address and a timer. This version is intended to be unique, but is not secure. Version 3: generates a unique ID from an MD5 hash of a namespace and name. Version 5: generates a unique ID from a SHA-1 hash of a namespace and name.
Lines 2
let time = new Date().getTime();
Javascript’s Date object holds time based on Unix time, or the amount of seconds since 00:00:00 UTC on January 1st, 1970 (minus a leap second here and there). The getTime method simply displays current Unix time. Factoid: if you type date +%s into your terminal you’ll also see current Unix time.
Line 3–5
if ( performance && typeof performance.now === 'function' ){
time += performance.now();
}
The performance.now() function returns the time that has elapsed since the web page loaded with accuracy between a millisecond and five thousandths of a millisecond. The gap in accuracy is due constraints in the computer. And that is how the first half of our UUID generator functions.
Line 6
'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function)
Let’s break down the second half of our function: the generator mechanism. We start with a string with the UUID format you see above, but we perform a Javascript String method called replace to substitute the x and y characters using a regular expression. With our second and final replace argument we unveil the superstar of our function.
function (c) {
let random = ( time + Math.random() * 16 ) % 16 | 0;
time = Math.floor( time / 16 );
return ( c === 'x' ? random: ( random & 0x3 | 0x8)).toString( 16 );
}
If you’re unfamiliar with Math.random, it returns a psuedo-random number between 0 and nearly 1. Pseudo-random number generation is not truly random! Its randomness is also determined by the current time. We’re going to do the same, and by doing so we defend ourselves from rainbow table attacks. We multiply our pseudo-random value by 16, then add our time calculation (integer time> 1,500,000,000). Finally, we use the modulo operator to get the remainder after dividing the number by 16 (getting a number between 0–16).
Line 7
let random = ( time + Math.random() * 16 ) % 16 | 0
So we end up with a decimal between 0 and 15. But what’s that strange looking pipe (|) between the 16 and our semicolon? It’s a bitwise operator! Remember our old friend hex? It’s back with cryptographic vengeance. But first, a refresher on names for data:
- 1 bit is the smallest unit of information (can be 0 or 1)
- 4 bits = hex
- 8 bits = 1 byte
A hex has 16 possible values. Why isn’t it 2 possible numbers times 4 different locations resulting in 8 pieces of information? Because there are 16 possible combinations of 1s and 0s when you have 4 units to fill, making it 2⁴ instead of 2 * 4.
But back to the bitwise operator. Bitwise operations are just like boolean operations, only you compare two series of 1s and 0s.
1 OR 1 = 1 OR
10 = 1 OR
00 = 0 AND
11 = 1 AND
10 = 0 AND
00 = 0
So if you have a hex bitwise operation, it will look like this:
We’ve got a decimal between 0–15 that needs to be turned into an integer between 0–15. We could just round it, but then we have to call Math, which imports a library, then performs a function depending on arguments… Using the bitwise operator OR (|), we can ensure we get a bit-friendly integer as a result.
Now that we’ve replaced a single x in our UUID, it’s time to change our time variable to hide its origin.
Line 8
time = Math.floor( time / 16 )
You’re probably wondering why we use Math.floor instead of just the bitwise OR operation, like the line above it. The bitwise OR results begin to diverge from the Math.floor() due to something called the Year 2038 problem. Sometime in the year 2038, Unix time will hit 2³¹– 1 (the maximum value 32 bits can hold), which causes the date to wrap around and become stored internally as a negative number, which these systems will interpret as having occurred on 13 December 1901 rather than 19 January 2038. It then begins to count backward toward 0.
Line 9
Now, for our grand finale:return ( c === 'x' ? random: ( random & 0x3 | 0x8 )).toString( 16 )
We’ve got a ternary operation that converts our random number into a hex number using the .toString(16) method, the argument in the toString method informing us of which radix (base of numeration) we want to use. Hexadecimals use 16. There is only one character that will hit the second half of our ternary: y. In Javascript, we prepend the hex number with 0x to indicate that the number is in base 16. For example:
Decimal /Hex
1 = 0x1
2 = 0x2
10 = 0xA
11 = 0xB
Our y character is AND bitwise operated against to 0x3 (hex-3/ 0011 binary) then OR bitwise operated against 0x8(hex-8/1000 binary). This makes the y character especially random.
Now stand back and smile; you’ve just generated yourself a UUID!
