alexandru@corlan.net
October 12, 2012, last change October 18, 2012
Archived by WebCite® at http://www.webcitation.org/6BVGUDscA Accessed: 2012-10-18.
Abstract
This specification defines a compatible extension of the UUID encoding
scheme detailed in RFC-4122. It folds into the UUID format numerous
establoshed identifier schemes, including but not limited to: numbers,
physiscal units and ammounts, colors, instants in time, publications,
chemicals, various catalogs-for example of astronomical objects.
Versions of UUIDs specified by RFC-4122 provide for randomly generated
identifiers that could very rarely colide. Sometimes however, the object
that is identified already has its well established identifier. Generating
a sepparate UUID for it would result into the need to maintain a
correspondence database.
This draft document describes a scheme for folding the numerous well
established digital identification schemes currently in use into a new
version of the RFC-4122 UUID. The scheme fits into a new UUID version
(could be version 6 or another version). It is currently called EXTUUID.
Besides providing a compact identification tool, the proposed scheme also
allows efficient representation, addressing and programming interfaces for
a large databases consisting of heterogenous vectors of such data.
There is a current implementation effort in the form of the corlpack
project. This proposal for a network version of the corlid (which is
architecture-specific and not as broad) is being developed in parallel
with that implementation.
The homepage of this document is:
http://dan.corlan.net/software/corlpack/extuuid.html
Contributions and comments are welcome.
Contents
1 Introduction
2 Motivation
3 Specification
3.1 Type
3.2 Character encoding schemes
3.2.1 Scheme A. 6 bit upper and lower case alphanumeric
3.2.2 Scheme B. 6 bit upper (any) case, decimal number and punctuation
3.2.3 Scheme C. 5 bit upper (any) case and punctuation
3.2.4 Scheme D. Packed alphabetic
3.2.5 Scheme E. EBCDIC-6
3.2.6 Scheme F. Packed alphanumeric
3.3 Symserial
3.4 Fixed
3.5 Vectors
3.6 Mapping into the 128 bit UUID format
3.7 Human readable printed representation
3.7.1 Minimal and smart parser
3.7.2 Symbols
3.7.3 Serial numbers
3.7.4 Fixed numbers
3.7.5 Vectors
3.8 Algorithm for determining the type given printed identifier syntax
4 General implementation
4.1 App types vs representation types
4.1.1 Example: a currency value
5 History of this document
6 References
1 Introduction
Various types of objects, such as numbers, symbols, serial numbers,
ammount, country codes, chemical substances, books and periodicals,
already have one or more well established numbering schemes. Further
encoding them with randomly generated UUIDs results in unnecessary
inefficiencies including the necessity of maintaining a sepparate database
of correspondences with the well known identities.
URN names [RFC] cover the uniform specification of many of these objects.
However, they also have unlimited, variable length which results into
further efficiency issues with both computational and communication use.
There are numerous other identification schemas that are not yet covered
by URNs.
Here we propose a representation format for producing unique 128 bit
identifiers that correspond to data objects that are relatively widely
used.
2 Motivation
The primary motivation behind adoption of this scheme is the reduction of
the complexity of application programming interfaces that are otherwise
needed to store and communicate data of the types described below.
UUIDs generated based on this proposal are entirely compatible with
version 1-5 UUIDs and may be represented syntactically in the same way.
A meaningful form for reading and writing by humans is also specified.
3 Specification
The RFC-4122 UUIDs use 6 bits for version and variant. This specification
covers the encoding of the other 122 bits, when the variant is 10x and the
version is 110 (version 6).
The 122 bits are specified as a continuous string from 0, representing the
most significant, to 121, representing the least significant.
The mapping of the 122 bits into the UUID format is described in
section 3.6.
The 122 bit string is designated below as EXTUUID.
The section on printed representation of EXTUUIDS, section 3.7 actually
specifies what data can be encoded as EXTUUIDS, the sections below only
specify how the encoding is assembled into the EXTUUID.
3.1 Type
Types are represented by the first 2 bits.
00: Symserial
is a character string (symbol) followed by an optional integer
number, for existing numbering schemes such as PMID, ISSN, ISBN,
MAC address, etc, but also for names and other symbols (when the
number part is not used).
01: Fixed
is composed, like a simserial, from a character string and a
number, but the number is a fixed point decimal.
10: Vector or quant
a vector of numbers with a context field specifying the meaning of
the numbers; a quant is a specific type of inhomogeneously
represented vector, consisting of a number accompanied by a unit
of measure of a physical measurable that can be expressed as a
product of SI units at integer powers (from -7 to 8), at
fractional powers with a denominator of 1 to 7.
11: Reserved
3.2 Character encoding schemes
In order to optimize the available space, a variety of character encoding
schemes are used in EXTUUIDs. These are specified below.
3.2.1 Scheme A. 6 bit upper and lower case alphanumeric
Each character is encoded on 6 bits, as follows (hex encoding and the
corresponding graphic character).
00 A 06 G 0c M 12 S 18 Y 1e 2 24 8 2a e 30 k 36 q 3c w
01 B 07 H 0d N 13 T 19 Z 1f 3 25 9 2b f 31 l 37 r 3d x
02 C 08 I 0e O 14 U 1a . 20 4 26 a 2c g 32 m 38 s 3e y
03 D 09 J 0f P 15 V 1b _ 21 5 27 b 2d h 33 n 39 t 3f z
04 E 0a K 10 Q 16 W 1c 0 22 6 28 c 2e i 34 o 3a u
05 F 0b L 11 R 17 X 1d 1 23 7 29 d 2f j 35 p 3b v
3.2.2 Scheme B. 6 bit upper (any) case, decimal number and punctuation
00 A 06 G 0c M 12 S 18 Y 1e 2 24 8 2a % 30 / 36 < 3c [
01 B 07 H 0d N 13 T 19 Z 1f 3 25 9 2b ^ 31 \ 37 = 3d ]
02 C 08 I 0e O 14 U 1a . 20 4 26 ! 2c & 32 ~ 38 > 3e (
03 D 09 J 0f P 15 V 1b _ 21 5 27 @ 2d + 33 , 39 ? 3f )
04 E 0a K 10 Q 16 W 1c 0 22 6 28 # 2e - 34 ' 3a |
05 F 0b L 11 R 17 X 1d 1 23 7 29 $ 2f * 35 ` 3b
3.2.3 Scheme C. 5 bit upper (any) case and punctuation
00 A 06 G 0c M 12 S 18 Y 1e *
01 B 07 H 0d N 13 T 19 Z 1f /
02 C 08 I 0e O 14 U 1a .
03 D 09 J 0f P 15 V 1b _
04 E 0a K 10 Q 16 W 1c +
05 F 0b L 11 R 17 X 1d -
3.2.4 Scheme D. Packed alphabetic
The number of bits needed to represent the 26 any case letters in base 26
is:
m = ceil(4.7004398 * n)
Where ceil(x) is the smallest integer number larger or equal to x. The
base26 numbers are as in scheme C, up to position 0x19 (26).
For example, 10 characters take 47 bits with this scheme.
3.2.5 Scheme E. EBCDIC-6
This is an already existing standard that fits the 6-bit needs we tried to
fill with scheme B. It is not currently supported, but it might be in the
future.
3.2.6 Scheme F. Packed alphanumeric
The minimum number of bits needed to represent characters in base 38 is:
m = ceil(5.2479276 * n)
Where ceil(x) is the smallest integer number larger or equal to x.
The base28 numbers are as in scheme A and B, up to position 0x25 (38).
For example, 10 characters take 53 bits with this scheme.
3.3 Symserial
Symserial representation consists of 4 fields: c (encoding) on 3 bits, l
(length) on 5 bits, s (symbol), that is l*5 or l*6 bits or another length
given by the respective formula depending on the encoding, and q, the
serial number, that is on the rest of the bits, considered as an unsigned
integer.
If q is 0, then the uuid represents just a symbol.
The smallest possible named symserial has one 5 bit character, the c+l
that make up 8 bits and a 105 bit integer that allows values of a bit
above 4**31 to be represented.
The longest name with a fixed encoding has 22 characters. Two bits are
left for q. With packed encoding, 23 characters are possible, thus there
isn't much to gain. With 6 characters encodings, up to 18 charactes are
available.
For example, to encode the Messier catalogue, a historic, fixed list of
sky objects that cannot increase, one would need 110 entries that take 7
bits. Thus, a string to identify the catalogue could be up to 21
characters with a 5 bit encoding or 17 with a 6 bit encoding.
3.4 Fixed
The fixed representation consists of 5 fields: c (encoding) on 3 bits, l
(length) on 5 bits, e (number of decimal digits after the decimal point)
on 5 bits, s (symbol), that is l*5 or l*6 bits or another length given by
the respective formula depending on the encoding, and q, the quantity,
that is on the rest of the bits, considered as an signed integer.
The ammount represented is q * 10 ** (-e).
For example, using encoding B, and using a 4 letter string to represent a
real currency, the first three letters being the 3-letter code of the
currency (for example GBP) and the last being '$' to indicate we are
refering to a currency, this would leave 120-3-5-5-24 = 83 bits that can
represent numbers up to 9.6714066 * 10 ** 24, that is almost 25
significant digits.
3.5 Vectors
Vectors may have a number of subtypes. The first three bits represent the
subtype, y:
000 - int: single signed integer
sign, followed by 116 bits.
001 - q: quant
Quants are floating point numbers that have an associated unit of
measure for a physical quantity, that is covertible into SI units.
It consists of 7 `xponents' for the 7 fundamental SI units, x0
thorugh x6, one 64 bit floating point number, f (IEEE double
precision) and a 4 bit context field. They are stored as follows:
+------------------------+---+---------+
| component | | bits |
+------------------------+---+---------+
+------------------------+---+---------+
| context field | a | 5--8 |
+------------------------+---+---------+
| xponents | x | 9-57 |
+------------------------+---+---------+
| value | v | 58-121 |
+------------------------+---+---------+
The xponents correspond, each, to a fundamental SI unit, as
follows:
+-------------+----------------+--------+-------+
| xponent | SI unit | abbrev | bits +
+-------------+----------------+--------+-------+
| x0 | metre | m | 9-15 |
| x1 | kilogram | kg | 16-22 |
| x2 | second | s | 23-29 |
| x3 | Ampere | A | 30-36 |
| x4 | Kelvin | K | 37-43 |
| x5 | candela | cd | 44-50 |
| x6 | mole | mol | 51-57 |
+-------------+----------------+--------+-------+
The 7 bits used are: sign (s) on 1 bit, followed by a 3 bit
numerator, n, and a 3 bit denominator, d. It means that the power
to which the respective unit is raised is x = -1sn∕d. For
example, if x0 is recorded in binary as: 1001010 it means s=1
(that is minus), n=1, d=2. If x1-x6 are 0, then the unit of
measure is m -1∕2 or 1∕m2.
A Joule is represented with an x0 reading 0010001, an x1 reading
0001001, and x2 reading 1010001 and the rest 0, meaning
kgm2∕s2 or Nm.
A Watt is like a Joule except x2 reads 1011001, meaning
J∕s.
010 - f: single float
the exponent is (the last) 16 bits. There remains one sign bit and
an 100 bit mantissa providing for 30 significant digits.
011 - t: time
A field, l, of 7 bits specifies the number of bits that are used
to represent fractions of a second. The next fields consists of a
sign, and then 109-l bits, the number of full seconds since (or
before, if the sign is 1) october 15, 1582. The last l bits
represent fractions of a second since the last full second, in
units of 2 -l.
The best accuracy that can be specified for current events is the
number of time intervals that fit in between 1582 and the relevant
date using 116 bits.
Until year 2200 this is (using 4):
((2200 - 1582) * 3600 * 24 * 365.25) / (2^109) = approx. 3.0048508E-23
It is a about 30 yoctoseconds, 30 millionthes of an attosecond.
This would be achieved using
log2((2200 - 1582) * 3600 * 24 * 365.25) = approx. 34.182947
That is 35 bits before the binary point and 71 after the point.
The initial and most obvious option was that the signed 116 bits
integer represents femtoseconds since the start of the Gregorian
calendar (15 October 1582). It identifies instants every
femtosecond for:
2116 3600 * 24 * 365.2515 = 2.6325433 * 1012years
before and after that event, which means 2632 thousand billion
years, much more than the 13 billion years that the universe is
supposed to have existed.
However, this didn't look fine; attosecond laser pulses are
produced and recorded when they occur could in principle be
desirable; we don't need this resolution more than 2 mil years
before and after today, so even zepto-seconds would be fine; also,
116 bits are hard to parse and handle; we could allow 64 bits in a
second, that is about 54.21 zepto-seconds and the higher integer
could provide for 2116 -64 that is about 100 million years. This
does not, then, allow for representation of the mere history of
the Cambrian period, not to speak about the emergence of galaxyes,
and then 54.21 zepto-seconds may be quite inaccurate to fix
attoseconds in time.
But, then, we don't need to, and cannot map the cambrian period
with attosecond accuracy.
So it resulted that a some kind of float was needed.
100 - int: generic signed integer vector
n, 7 bits, number of signed integers; l, 7 bits, size in bits of
each integer; z, context field, 104-n*l, then the n elements of
the vector, l bits each, the first of which is the sign.
101 - uint: generic unsigned integer vector
n, 7 bits, number of unsigned integers; l, 7 bits, size in bits of
each integer; z, context field, 104-n*l, then the n elements of
the vector, l bits each.
110 - f/xx: generic float vector
n, 7 bits, number of floating points l, 7 bits, size in bits of
each floating point, e, 5 bits, size of each exponent; z, context
field, 99-n*l, then the n elements of the vector, l bits each of
which e are the exponent, 1 sign and l-e-1 mantissa.
111 - standard float vector
f, format, on 3 bits, specifies either:
000-ieee-80 floating point number
, preceded by a 24 bit context field, z, that is
represented as 4 scheme B characters;
001-ieee-64 floating point number
, preceded by a 40 bit context field, z, as 8 scheme
C characters;
010-3 x ieee-32 floating point numbers
, preceded by an 8 bit context field, z as a decimal
number between 0 and 255;
011-2 x ieee-32 floating point numbers
, preceded by a 40 bit context field, z as 8 scheme C
characters;
100-1 x ieee-32 floating point numbers
, preceded by a 72 bit context field, z, that is
encoded as 12 scheme B characters;
101-6 x ieee-16 floating point numbers
, preceded by an 8 bit context field, z as a decimal
number between 0 and 255;
110-1-5 ieee-16 floating point number
, followed by a 2 bit number that is n-1, the number
of floating point numbers, and (102 - n*16) bits
(that can be: 32, 48, 64 or 80 bits) that are encoded
as 6-bit, scheme B characters.
111
reserved for other schemes with non-uniform length.
3.6 Mapping into the 128 bit UUID format
3.7 Human readable printed representation
For each identifier there is an explicit printed representation, that uses
the format scheme:{scheme:}*value that may produce any EXTUUID
representation representation, and an implicit printed representation that
is transformed into an UUID in a deterministic but necesarily obvious way.
The most explicit way to provide such a printed representation is to
specify the first scheme as extuuid. For example: extuuid:int:212323232423
produces the exact 117 bit signed integer; extuuid:quant:22.4*m3 means
22.4 cubic meters.
The same expressions may appear without extuuid: or even without any
qualifier if they are in a context that conducts to them being driven as
inputs into the extuuid parser. However, if presented with "22.4" the
parser would not know for sure if it is a quant, a float, a single number
float vector or standard float vector, etc. It would decide in a
deterministic way following the algorithm described in section 3.8, but to
the user this may be not obvious.
3.7.1 Minimal and smart parser
A minimal parser will only be able to parse the full canonical syntax
described below. A smart parser may be provided by an application, that
may infer the type and representation from shorter or more convenient
forms. A smart parser can also be implemented as a filter.
3.7.2 Symbols
A string is interpreted as an extuuid symbol if preceded by any of the
following: extuuid:sym:, extuuid:sym[A-F]:, sym: or sym[A-F]. Encodings
are tried in order, and the first that allows the representation of the
symbol is used.
should not the 5-bit appear first, as it uses the least ammount of memory?
No, because it is also more ambiguous.
3.7.3 Serial numbers
The generic format:
[extuuid:]serial[A-F]::
where the name is encoded with the specified scheme or the first that
fits. The number must be a decimal unsigned integer that may contain any
number of dashes or underscores that are ignored.
3.7.4 Fixed numbers
[extuuid:]fixed[A-F][0-32]::[-].
It is like a serial except that it may contain an optional explicit number
of decimal places after the optional encoding and it may be negative. If
the number of decimal places is not given then the minimum such number is
used.
3.7.5 Vectors
[extuuid:][{int|q|t|uint|f}[/[*[*]]]:][:][,]*[[/*][]]*
(full syntax will have to be provided)
The fields have the following meaning:
int
an integer number or signed integer vector; if or are
provided then it is a signed integer vector with the specified
number and length; also, if a name is provided, or a list of
values-instead of a single value-then it is a signed integer
vector instead of a single integer; the unit must not occur in
ints; the value is an optional sign followed by a string of
decimal digits, with optionally interspersed undescores; the first
and the last character in a value must be a digit.
uint
an unsigned integer vector; it may have , and a number of
values, but of course no unit.
q
quant; it may not have dimensional attributes (n,l,e), nor name,
but may have any number of units. The unit names are case
sensitive abbreviations of the fundamental SI units. They are
preceded by a '*' if the power is positive and a '/' if it is
negative. The power, if higher than 1, must be given as a single
digit. Fractional powers are given as /.
t
time; it may have an "n" attribute representing the number of bits
to be used for subsecond resolution; it may not have a name; the
value may be either a decimal number without sign, a single
decimal dot, representing seconds from the reference time, or it
may be of the format:
yyyy[-/]MM[-/]dd;hh:mm:ss.n*
where yyyy is the year, MM is the month, dd is the day, hh the
hour (0-23), mm the minute and ss.n* represent the seconds and
fractions of a second.
Any of the tailing components may be missing.
Other formats are acceptable by preceding with a format string and
':'. The format string is not yet specified.
f
a vector of one or more floating point numbers; name and dimension
fields are accepted, units are not; the shortest representation
possible for the given constants is used.
3.8 Algorithm for determining the type given printed identifier syntax
4 General implementation
4.1 App types vs representation types
The types mentioned in section 3 are called "representation types".
For a particular use, the application programmer will develop an app type.
4.1.1 Example: a currency value
The follwing steps must be to considered.
Design. Common currencies are stored using the "Fixed" type, with four
decimals after the decimal point and with a name consisting of three
letters (ISO 4217) followed by '$', encoded with type B. A canonical
example is:
extuuid:fixedB4:GBP$:222.31
Other formats are, however, also accepted for input by a smart parser,
such as GBP222.31, GBP$222.31, 222.31$GBP or 222.31GBP.
An identifier is selected for the type, say it is "money". A restriction
can be established that, for example, only ISO 4127 valid letter
combinations are acceptable.
Implementation An unpacked type for this kind of objects is implemented.
The object is probably a record consisting of a 3-character string and a
64 bit integer number or a fixed point type.
Besides operations for the type (such as addition or multiplication with a
float), constructors, predicates (is it a valid currency?) and selectors
(what is the currency name?) must be provided.
For interfacing with the EXTUUID system, the following functions need to
be provided:
* Is_Money(U: EXTUUID) return Boolean; tests whether an object is of
this type.
* Enpack(M: Money) return Extuuid; packs the money object as an extuuid.
* Unpack(U: Extuuid) return Money; the reverse of enpack.
* Is_Money(S: String) return Boolean; tests whether the string is a
valid input object of the money type (this is the smart parser).
* Parse(S: String) return Money;
* Parse(S: String) return Extuuid;
* Format(U: Extuuid) return String; (this may have more arguments).
The functions that do not use the Money type can be recorded as generic
readers and formatters to be used but procedures that do not directly see
this module.
5 History of this document
12 oct. first version.
16 oct. posted online
18 oct. revised, section on implementation and reference to corlpack added
6 References
[1] RFC 4122 A Universally Unique IDentifier (UUID) URN Namespace. P.
Leach, M. Mealling, R. Salz. 2005
[2] RFC 2141 URN Syntax. R Moats. 1997.
[3] http://www.webcitation.org
[4] http://qalculator.sourceforge.net/