Compact UUIDs for Constrained Grammars

1.1. Requirements

The aim of this specification is to eliminate work on the part of developers who find themselves in the position of needing to squeeze UUIDs into the aforementioned grammars, by defining alternative representations that are:¶

• Significantly shorter lexically than the canonical UUID representation (even after removing the hyphens),¶
• Guaranteed to begin with with a letter (/^[A-Za-z]/),¶
• Deployable (through different encodings) in case-sensitive and case-insensitive contexts,¶
• Devoid of non-payload characters (i.e., every character in the representation is part of the UUID; except for any padding to a prescribed length; see Section 3),¶
• Fully isomorphic to the canonical UUID representation (i.e., accommodates all possible future UUID versions and variants that [RFC4122] does),¶
• Amenable to detection and identification by heuristic (Section 4.1) (in a manner analogous to the canonical UUID representation).¶

1.2. Motivation & Applications

The purpose of an identifier in general is to pick out some information resource or other, such that it can be referred to, ideally unambiguously. The purpose of a large, generated identifier like the UUID, is to satisfy the uniqueness criterion while also specifying a datatype and normal form for said identifiers, and ultimately alleviate the need to set time aside to think up names for things. Why one would want to go inserting UUIDs in places they wouldn't otherwise fit, is so these UUIDs can be cross-referenced in some other database where they do fit. Consider:¶

• A programming environment that separates the task of writing logic from naming things, stores identifiers internally as UUID-NCName-32 prior to transforming them on display or export, thus preserving the correctness of the syntax.¶
• A component content management system that uses UUIDs to identify elementary content components, uses the UUID-NCName-64 (or UUID-NCName-58, but in this case Base64 works too and is one byte shorter) representations of the same UUIDs as fragment identifiers for when those components are transcluded.¶

4.1. Detection Heuristic

All encodings of UUID-NCName are a fixed length:¶

• UUID-NCName-32 is always 26 bytes.¶
• UUID-NCName-58 is always 23 bytes.¶
• UUID-NCName-64 is always 22 bytes.¶

All encodings likewise use the same "bookend" mechanism which always correspond to the first 16 symbols of Base32 (A to P, with the side effect that they are effectively case-insensitive). The first and last character in all three representations will therefore always be the same, modulo case, for a given UUID. Furthermore, since these "bookend" characters represent the version and variant bits, they will correspond to predictable values. Version 4 (random) UUIDs, for instance, will always begin with E, and any UUID with its variant bits set as defined in RFC 4122 [RFC4122] will always terminate (again, modulo case) with I, J, K, or L.¶

Given these facts, any UUID-NCName representation MAY be captured (and its "bookends" separated) using the following regular expression:¶

/\b([A-Pa-p]) # zero-width boundary and version bookend

([2-7A-Za-z]{24}|[-0-9A-Z_a-z]{20}| # base32 and 64

  (?:[1-9A-HJ-NP-Za-km-z]{15}_{6}|[1-9A-HJ-NP-Za-km-z]{16}_{5}|
     [1-9A-HJ-NP-Za-km-z]{17}_{4}|[1-9A-HJ-NP-Za-km-z]{18}___|
     [1-9A-HJ-NP-Za-km-z]{19}__|[1-9A-HJ-NP-Za-km-z]{20}_|
     [1-9A-HJ-NP-Za-km-z]{21})) # base58 with underscore pad

([A-Pa-p])\b/x # variant bookend and zero-width boundary

The scrupulous may also wish to examine the bookend characters, for which the first should only correspond to the numbers 1 through 5 (plus zero for the nil UUID) for UUID versions known at the time of this writing, and the other should have the same bits set as expected in Section 4.1.1 of RFC 4122 [RFC4122]. Note however that there is room in the spec for another ten UUID versions (up to a hypothetical version 15), and another variant bit that is currently unused.¶

This detection method is considered a heuristic because it is possible to identify false-positive matches in random strings of text, just as it would be with a canonical UUID representation. It is assumed that there would be sufficient enough context to positively identify these alternative UUID representations in the wild.¶

4.2. Equivalency

Two UUID-NCName symbols are necessarily identical if they convert to the same (canonical) UUID. Two UUID-NCName-32 symbols are identical if their string values match when normalized to all upper- or lower-case letters. Two UUID-NCName-58 or UUID-NCName-64 symbols are identical if their string values match when the "bookend" characters are normalized to either upper- or lower-case.¶

5.1. Encoding Algorithm

First we apply the shifting algorithm:¶

1. Convert the UUID to a binary string bin.¶
2. Convert bin to an array of four 32-bit unsigned network-endian integers ints.¶
3. Extract version as (ints[1] & 0x0000f000) >> 12.¶
4. Extract variant as (ints[2] & 0xf0000000) >> 24.¶
5. Assign ints[1] = (ints[1] & 0xffff0000) | ((ints[1] & 0x00000fff) << 4) | ((ints[2] & 0x0fffffff) >> 24).¶
6. Assign ints[2] = (ints[2] & 0x00ffffff) << 8 | (ints[3] >> 24).¶
7. Assign ints[3] = (ints[3] << 8) | variant.¶
8. Convert ints back into a binary string and return it along with the version.¶

Then apply one of the formatting algorithms; here is Base32:¶

1. Take the binary string bin and shift the last octet to the right by one bit.¶
2. Encode bin with the Base32 algorithm to get the string b32.¶
3. Truncate b32 to 25 characters, removing any padding.¶
4. Convert version to its value in the Base32 table.¶
5. Return version concatenated to b32, optionally in either upper or lower case.¶

And Base58:¶

1. Remove the last octet from the binary string bin, convert it to an integer and assign it to variant.¶
2. Shift variant to the right by 4 bits, and convert it to its value in the Base32 table.¶
3. Encode the remaining bin with the Base58 algorithm to get the string b58.¶
4. If b58 is less than 21 characters long, append underscores (_) until it is.¶
5. Convert version to its value in the Base32 table.¶
6. Return the concatenation of version, b58, and variant.¶

And finally, Base64:¶

1. Take the binary string bin and shift the last octet to the right by two bits.¶
2. Encode bin with the base64url algorithm to get the string b64.¶
3. Truncate b64 to 21 characters, removing any padding.¶
4. Convert version to its value in the Base32 table.¶
5. return version concatenated to b64.¶

5.2. Decoding Algorithm

1. First use the detection heuristic (Section 4.1) to determine whether the symbol ncname is Base32, Base58, or Base64.¶
2. Remove the first character of the symbol ncname and convert it into an integer according to the Base32 spec; call that integer version.¶

3. If ncname is Base58:¶

   1. Remove the last character and decode it to an integer according to the Base32 spec; call that integer variant.¶
   2. Shift variant four bits to the left.¶
   3. Remove all trailing underscores from the remainder of ncname.¶
   4. Decode the remainder of ncname with the Base58 algorithm as bin.¶
   5. Append the octet corresponding to the value of variant to bin.¶

4. Otherwise:¶

   1. If ncname is Base64, and the last character is lowercase, set it to uppercase.¶
   2. Append padding if necessary to satisfy the decoder, A====== for Base32 and A== for Base64.¶
   3. Decode the remainder of ncname by either the base32 or base64url decoding algorithm into binary string bin.¶
   4. If ncname is Base32, shift the last octet of bin one bit to the left; if Base64 shift it two bits.¶

Now we apply the shifting algorithm in reverse:¶

1. Ensure version &= 0xf so it is in the range of 0-15.¶
2. Convert the binary string bin into an array of four 32-bit unsigned network-endian integers ints.¶
3. Assign variant = (ints[3] & 0xf0) << 24.¶
4. Shift and assign ints[3] >>= 8.¶
5. Union and assign ints[3] |= ((ints[2] & 0xff) << 24).¶
6. Shift and assign ints[2] >>= 8.¶
7. Union and assign ints[2] |= ((ints[1] & 0xf) << 24) | variant.¶
8. Assign ints[1] = (ints[1] & 0xffff0000) | (version << 12) | ((ints[1] >> 4) & 0xfff).¶
9. Convert ints back into the new binary string bin.¶
10. Format bin as a canonical UUID.¶