Unlimited UTF-8! ASCII ⊆ UTF-8 ⊆ UTF-8000.
No special cases introduced. All properties preserved.
Try out the reference implementation with $ pipx install UTF-8000.
UTF-8000 is in no way endorsed by or representative of the Unicode Consortium.
This is a fun standalone project / proposal.
TLDR / Examples
ASCII 1 0xxxxxxx UTF-8 2 110xxxxx 10xxxxxx 3 1110xxxx 10xxxxxx 10xxxxxx 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx UTF-8000 5 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 6 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 7 11111110 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 8 11111111 100xxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 9 11111111 1010xxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10 11111111 10110xxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ... 22 11111111 10111111 10111111 10110xxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ... 10xxxxxx ...
There is nothing special-case-y about the example 22-byte code unit here. It is just a good prototypical example, demonstrating the power of UTF-8000 with multiple start bytes.
There are only two special cases, both of which are inherited from UTF-8: ASCII as is, and 2-byte UTF-8 having 4 mandatory content bits to check against overlong encoding as opposed to 5 for all longer length code units.
Anatomy
Here is anatomical diagram of the example 22-byte code unit from the tldr.
See the glossary for more information on the definitions of the terms.
Byte number four is exciting! It is a continuation byte, a start byte, the final start byte, has content bits, and has only some of the mandatory content bits, which are straddled across the final start byte and first non-start byte.

The main contribution of UTF-8000's specification is clarity on splitting the highest bits of the first byte of UTF-8 code units into self-synchronization bits and start bits, and then making it clear how to stripe the start bits across the continuation bytes if needed, to achieve arbitrarily large code units.
Glossary
These terms are ordered somewhat by chronology of first requirement, rather than alphabetically, for convenience.
Codepoint
A non-negative integer, aka an unsigned integer.
Code Unit
A sequence of UTF-8000 bytes that encode a single codepoint.
First Byte
The first, one and only, byte that begins a UTF-8000 code unit.
The self-synchronization prefix of a first byte is either 0 for ASCII or 11 for multi-byte code units.
This term is not synonymous with start byte. A first byte is necessarily a start byte, but not the other way around. It is for this reason that first byte is sometimes also known as first start byte.
Fun observation: because of the self-synchronization prefix 0 the upper hex nibble of ASCII bytes can only be one of 0, 1, 2, 3, 4, 5, 6, 7.
This term is mutually exclusive with continuation byte due to self-synchronization.
Continuation Byte
A byte beyond the first byte of a multi-byte UTF-8000 code unit.
The self-synchronization prefix of a continuation byte is 10, which is also known as the continuation prefix bits.
Fun observation: because of the self-synchronization prefix 10 the upper hex nibble of continuation bytes can only be one of 8, 9, A, B.
This term is mutually exclusive with first byte due to self-synchronization.
Self-Synchronization Prefix
The highest bits of every UTF-8000 byte that indicate whether it is a first byte or a continuation byte.
The possible self-synchronization prefixes form a prefix-free tree:
.----0 First byte for ASCII
`----1---0 Continuation byte for multi-byte UTF-8000
`----1 First byte for multi-byte UTF-8000
This piece of the clever architecture of UTF-8, which UTF-8000 inherits, provides the property of self-synchronization at a byte level: we can instantaneously tell what kind of byte we are looking at, and where it should belong in a code unit, just by looking at these highest bits.
This is most useful when decoding part of a file encoded in UTF-8000. If we randomly seek through the file to an arbitrary byte, we can unambiguously tell whether we are at a first byte whence we can begin decoding a new code unit immediately, or that we are at a continuation byte whence we need to seek a little further on in order to find the next first byte in order to begin decoding. Nor do we have to process any bytes prior to our seek position in order to discover some global state or the context of the byte we have seek-ed to; a first byte is always unambiguously a first byte wherever it appears, which we can deduce by its self-synchronization prefix being either 0 or 11.
This is useful not only for random access, but also for error recovery. Suppose that we are decoding an error-prone stream of UTF-8000 bytes and that whenever when we encounter an error (e.g. a rogue 0xC0 byte) we wish to keep calm and carry on instead of immediately exiting. We can yield Unicode replacement characters U+FFFD � and then await the next first byte, discarding anything in the interim.
See the Wikipedia article for self-synchronizing code for more general info.
These bits are highlighted in bright cyan.
Start Byte
A byte containing one or more start bits. The start bytes exist contiguously at the beginning of a UTF-8000 code unit. The power of UTF-8000 is that we can have multiple start bytes, to achieve arbitrary code unit lengths, to encode arbitrarily large codepoints.
Sometimes it is sensible to colloquially also include ASCII as a start byte when we are talking about the bytes towards the start of a code unit, even though ASCII bytes have no start bits.
Every non-ASCII code unit has at least one start byte. The first start byte is the first byte, and it is followed by zero or more continuation bytes that are also start bytes. Therefore because a UTF-8000 code unit can have multiple start bytes, this term is not synonymous with first byte.
In restricting to only UTF-8 without UTF-8000, this term is synonymous with first byte. This is because UTF-8-length code units only require one start byte, whether using up to 4 bytes in the current UTF-8 standard (RFC 3629 (2003)), or using up to 6 bytes in former standards (RFC 2044 (1996) and RFC 2279 (1998).
Start Bits
The unary-code sequence of bits contained in the start bytes of a multi-byte UTF-8000 code unit that tells us the length of the code unit in bytes.
For a code unit made of n bytes the start bits are n-2 1 bits followed by a terminating 0 bit. To be clear, the start bits include this terminating zero bit. Thus the start bits sequence is of length n-1 and looks like 111...10.
The possible start bits sequences form a prefix-free tree:
.----0 Two byte UTF-8
`----1---0 Three byte UTF-8
`----1---0 Four byte UTF-8
`----1---0 Five byte UTF-8000
`----... n byte UTF-8000
For an n byte code unit where n < 8 the start bits all fit together snugly in the first byte. Otherwise they are striped across as many of the first few bytes as they need, filling the free bits that are not occupied by continuation prefix bits.
This is another piece of the clever architecture of UTF-8, which UTF-8000 inherits, that provides the property of self-punctuation also known as a prefix code or a prefix-free code: when decoding a multi-byte code unit, once we have read to the end of the start bytes, that is we have encountered the terminating 0 bit, we know exactly how many bytes we expect in that code unit. Notwithstanding errors we can therefore succeed in decoding the code unit by reading exactly that many bytes, and no more.
This avoids a problem of dumber variable-length encodings whose code units do not intrinsically indicate their length: one has to read beyond the last byte of a code unit, that is one reads the first byte of the next code unit, in order to know that the current code unit has finished. For very dumb encodings which have neither self-synchronization nor self-punctuation, to make random access possible one would have to put dedicated auxiliary bytes, punctuation like a comma byte, between code units to be able to tell where one ends and another begins.
See the Wikipedia articles for prefix code and unary coding for more general info.
This term is mutually exclusive with content bits.
These bits are highlighted in bright magenta.
Content Byte
A byte containing one or more content bits.
A byte being a content byte does not imply that it is a continuation byte. For example a 3-byte code unit begins with 1110xxxx, which contains 4 content bits and is not a continuation byte.
A byte being a continuation byte does not imply that it is a content byte. For example a 22-byte code unit contains 10111111 as its second byte, which is a continuation byte and has no content bits.
Content Bits
The sequence of bits in a code unit beyond the start bits and to the end of the code unit, in which the codepoint's binary bits are stored. For example a 3-byte code unit, which has the form 1110xxxx 10xxxxxx 10xxxxxx, has 16 content bits.
For ASCII there are 7 content bits. These seven bits xxxxxxx combined with a byte's highest bit being set to the self-synchronization prefix 0 means that ASCII is perfectly included into UTF-8 without being altered. Thus ASCII code units take the form 0xxxxxxx.
Otherwise for an n byte code unit, where n > 1, there are 5n+1 content bits. This is how we arrive at that formula: We start with n blank bytes, each of which has 8 bits. For each byte 2 bits are taken by the self-synchronization prefix. Then an additional n-1 bits are taken by the start bits. Thus there are 8n - 2n - (n-1) = 5n+1 bits left for content bits. Another way to think about the 5 in this formula is by extending from n-1 bytes to n bytes by appending another continuation byte. By doing this we gain 6 free bits in the continuation byte, but we lose 1 bit to the longer start bits sequence, thus overall we gain 6-1 = 5 bits for content bits.
This term is mutually exclusive with start bits.
These bits are highlighted in lime.
Mandatory Content Byte
A byte containing one or more mandatory content bits.
These are the bytes we check for overlong encoding when decoding a code unit.
Mandatory Content Bits
The first 0, 4, or 5 content bits of a code unit in which there must be at least one 1 bit, lest the bytes form an overlong encoding, which is forbidden.
For ASCII there are 0 mandatory content bits, and thus no anti-overlong checking is required. This is because ASCII is the smallest possible code unit.
For 2-byte UTF-8000 there are 4 mandatory content bits. This is because in the jump from 1-byte ASCII to 2-byte UTF-8 we jump from 7 content bits to 11 content bits. Thus the number of content bits we gain is 11 minus 7 which is 4.
Otherwise for n byte UTF-8000, where n > 2, there are 5 mandatory content bits. This is because in the jump from n-1 byte UTF-8000 to n byte UTF-8000 we add on an extra continuation byte, which has 6 free bits, but we lose 1 bit to the longer start bits sequence. Thus overall the number of content bits we gain is 6 minus 1 which is 5.
Read about overlong encoding for why mandatory content bits are of interest.
These bits are highlighted in bright lime.
Overlong Encoding
Forbidden encodings of codepoints that could be encoded correctly in UTF-8000 using a shorter code unit.
For example one could incorrectly try to encode the codepoint 0x41, 65, ASCII capital A, using 2-byte UTF-8 as 11000001 10000001. Observe that all the mandatory content bits are 0 which is the definition an overlong encoding. This indicates that we could have encoded 0x41 in a shorter code unit, in this case as ASCII 01000001.
Security is one main reason why we forbid overlong encoding. For example we ensure that 11100000 10000000 10000000 cannot be decoded as codepoint 0, the null byte, lest one speciously pass such an overlong byte (code unit) to C functions like strcpy(3) and friends. strcpy would not interpret this code unit as a null byte, leading to a segfault at best, and serious vulnerabilities at least-worst.
Uniqueness of encoding is another reason why we forbid overlong encoding. Every codepoint has one unique valid representation as a UTF-8000 code unit, which is easy to encode and decode using bitshifting.
Fun observation: because all 4 of 2-byte UTF-8's mandatory content bits lie in the first-and-final start byte, we can explicitly rule out 11000000 (0xC0) and 11000001 (0xC1) as permanently invalid bytes. They will never ever appear anywhere in a valid UTF-8000 code unit!
Properties
Many of these properties of UTF-8000 are explained in detail in an appropriate section of the glossary and hyperlinks to the glossary are provided.
Bit Counts
The number of content bits and mandatory content bits are very predictable as a function of n, the length of a code unit.
| code unit length |
number of content bits |
number of mandatory content bits |
n = 1 |
7 |
0 |
n = 2 |
5n+1 ( = 11) |
4 |
n > 2 |
5n+1 |
5 |
Why the Special Cases?
As stated in the tldr, there are only two special cases, both of which are inherited from UTF-8:
1-byte UTF-8 (ASCII) which has two points of interest:
- It has 7 content bits which does not fit the pattern of
5n+1. See the glossary section for content bits for an explanation, and see the rejected alternative ASCVI code for a version of UTF-8 if ASCII were 6 bit instead of 7 bit which eliminates this special case.
- ASCII has 0 mandatory content bits because it cannot possibly be overlong since it is the smallest possible code unit. This is fine.
2-byte UTF-8 which has one point of interest:
- It has 4 mandatory content bits, as opposed to 5 for all longer code units. See the glossary section for mandatory content bits for an explanation.
The remarkable fact that UTF-8000 does not introduce any new special cases in extending UTF-8 is confirmation to me that this is the canonical, correct way to extend UTF-8. In other words UTF-8 in its current restricted 4 byte form is UTF-8000, but only a small part of it.
The fact that we are even able to extend in the first place is also testament to the clever planning and care that Ken Thompson and Rob Pike put into the architecture of UTF-8, which we ensure to maintain as we extend to UTF-8000. Unary code codewords for the start bits sequences, which form a self-similar tree, were a great choice being simple and extensible. In the earliest draft of UTF-8, the six-byte start-byte looked like 111111xx. This was changed a few days later to 1111110x. That way the number of content bits is not a special case, and the start bits don't saturate the unary code binary tree, leaving the door open for our future expansion.
This is why I think of UTF-8 as the capstone of the Unix Philosophy.
Information Rate
What proportion of a code unit is content bits?
For ASCII this is 7/8 = 87.5%.
Otherwise for an n byte code unit this is (5n+1) / 8n, that is 5n+1 content bits out of a total of 8n bits from n bytes. We can rewrite this as (5/8) + 1/(8n) which moderately quickly approaches 5/8 = 62.5%. It is nice that this limit is nonzero and does not depend on n.
Self-Synchronization
Inherited from UTF-8 and maintained in UTF-8000.
See the glossary section for self-synchronization prefix for an explanation of self-synchronization.
Here's a bit of history: Self-synchronization is one of the reasons why Ken Thompson and Rob Pike decided to design UTF-8, to supersede the earlier FSS-UTF draft by Dave Prosser et al. FSS-UTF proposed a design like eg 110xxxxx 1xxxxxxx 1xxxxxxx for three-byte code units. The problem with it is that one cannot distinguish between first bytes (110xxxxx) and continuation bytes (110xxxxx) without knowing the prior history of a stream. The UTF-8 fix is to make first byte and continuation byte values disjoint from each other, as one can witness in the byte map below. I have not put Prosser's draft into the rejected ideas section as it has already been formally addressed and superseded by UTF-8.
Self-Punctuation
Inherited from UTF-8 and maintained in UTF-8000.
See the glossary section for start bits for an explanation of self-punctuation.
Byte Map
Extended from UTF-8, making use of the higher value bytes. Based off Wikipedia's UTF-8 Byte Map.
All bytes except 0xC0 and 0xC1, colored in tomato red, can appear in a valid UTF-8000 stream. See the glossary section for overlong encoding for an explanation of why those two bytes never appear.
ASCII, colored in gold yellow, occupies the first half of the table, being 7-bit. Continuation bytes occupy the region colored in sandybrown orange. All other bytes are first bytes for multi-byte code units, whose lengths are indicated in the table.
strcmp(3) Ordering
Inherited from UTF-8 and maintained in UTF-8000.
The self-synchronization prefixes of first bytes are monotonically-increasing-ly ordered with respect to code unit length. In other words ASCII is of length 1 and multi-byte is of length greater than 1, and 0 < 11 occupying the highest bits of UTF-8000 bytes.
The start bit sequences are also monotonically-increasing-ly ordered with respect to code unit length. In other words if n < m then 111...[n]...10 < 111...[m]...10 as an integer value, occupying the heads of the code unit bytes beyond the self-synchronization prefixes. This would not have been the case had UTF-8 been designed to use the alternative form of unary codewords given by 000...01.
The content bits of code units are also monotonically-increasing-ly ordered with respect to codepoint value.
Combining these three things together means that strcmp(3), the C stdlib string comparing function, works the same way on UTF-8000 bytes as it does on UTF-8, as it does on ASCII, effectively comparing the encoded codepoint values against each other without having to actually decode the code units. Nice!
No Endianness
The quantum of ASCII, UTF-8, and UTF-8000 is a single byte. This makes life a breeze! There is no need for a concept of endianness for UTF-8000.
UTF-16 however has a quantum of two bytes, 16-bit units. When writing the codewords in bytes, 8-bit units, should the byte containing the most significant digits or least significant digits be written first? Big-endian, or little-endian? This choice gives UTF-16 two variants, UTF-16-BE and UTF-16-LE. If one cannot predetermine the endianness of a stream, one may wish to use a BOM which is discussed below.
BOM Support
A Byte Order Mark (BOM) is used at the start of an encoded text stream to indicate what encoding is used. I have never actively used BOMs myself so I've only put a bit of thought into this section.
As far as I'm aware we don't break BOM support for UTF-8, though we may wish to have a different BOM to strictly distinguish UTF-8 from UTF-8000. Maybe UTF-8000 could have multiple BOMs, one for each integer N greater than or equal to four, to indicate to a decoder the maximum expected code unit length.
One of the reasons why U+FFFE is not a valid Unicode Scalar Value is because 0xFE 0xFF is the BOM for UTF-16. Since UTF-16 code units are two bytes wide, one may read either 0xFE 0xFF or 0xFF 0xFE depending on endianness. To make it clear that 0xFF 0xFE implies correct for endianness and cannot be mistaken for a legitimate character, U+FFFE is designated as <noncharacter-FFFE>. We are relieved in that neither 11111111 11111110 nor 11111110 11111111 are valid UTF-8000 sequence extracts, ie UTF-8000 does not introduce incompatibilities with UTF-16.
Arbitrary Lengths, Sensible Limits
I think we've made it clear by now that UTF-8000 code units can be arbitrarily large. In practice however one may wish to set a sensible limit on code unit lengths when decoding. Here we'll discuss a method of finding some nice code unit lengths whose code units store 5n+1 = 2^N bits, as we are often interested in powers of 2 in computer science.
It is a common observation that 3-byte UTF-8 stores 5 * 3 + 1 = 16 bits, meaning the Basic Multilingual Plane of Unicode can be encoded in one two and three byte UTF-8. We see that 2^4 mod5 = 16 mod5 = 1 mod5; if 5n+1 is to be 2^N for some n then certainly 2^N = 1 mod5. If we enumerate powers of two modulo five then there is a very predictable repeating pattern of 1, 2, 4, 3. Formally you might say that 2 is a generator of 𝔽5* if you want impress a mathematician! The takeaway is that when N=4K for K≥1 we can find a corresponding n such that 5n+1 = 2^N. We can rewrite 2^N as 2^(4K) = 16^K.
In other words any power of 16 has a UTF-8000 code unit length containing that many bits. Here are a few of these for reference.
K |
N=4K |
number of content bits = 2^N |
code unit length = (2^N - 1) / 5 |
1 |
4 |
16 |
3 |
2 |
8 |
256 |
51 |
3 |
12 |
4096 |
819 |
4 |
16 |
65536 |
13107 |
... |
... |
... |
... |
Do remember that strictly speaking one shouldn't allow overlong encodings, if one were for example thinking of storing a small uint256_t key in a 51 byte code unit! UTF-8000's variable width nature helps out leading to smaller code units for smaller integers.
Intuitive Derivation
There are a few ways that one could arrive at the design for UTF-8000 and the bit counts above.
One may think to start with UTF-8, notice that the start byte of an n byte code unit is prefixed with the unary codeword of length n+1, that is n 1 bits followed by a 0, and then figure out how to extend those bits and roll them over into the continuation bytes without losing any important properties. This is what I originally did.
Writing this document over a couple of weeks made me introspect the code unit anatomy further, whence I figured out that separating the leading bits into a self-synchronization part and self-punctuation part further illuminates and simplifies the thought process. We shall thus proceed with this perspective.
Blank Slate
We set out to derive the design of an n byte code unit, starting out with n blank bytes, all of whose bits could possibly be content bits.
00000000 00000000 00000000 ... 00000000
To achieve self-synchronization we need to distinguish the first byte of the code unit from the continuation bytes that follow. We could do that by setting the highest bit of first bytes to a 0 and to 1 for continuation bytes. Doing it this way round maintains compatibility with ASCII's highest bit being 0.
00000000 10000000 10000000 ... 10000000
With the design so far, all code units begin with an ASCII byte. When decoding a code unit, we have no idea whether this first byte actually is ASCII, or it is the first byte of a multi-byte code unit. We want self-punctuation, where a code unit intrinsically tells us how long it is.
To achieve self-punctuation we create a prefix-free code binary tree, whose leaf node codewords correspond to code unit lengths. These are the start bits sequences. The codeword for n shall be embedded inside the code unit towards the start. It must therefore be short enough to fit into the n bytes, and reasonably computationally predictable. We try:
.----0 One byte UTF-8 (ASCII)
`----1---0 Two byte UTF-8
`----1---0 Three byte UTF-8
`----1---0 Four byte UTF-8
`----1---0 Five byte UTF-8000
`----... n byte UTF-8000
This seems reasonably simple so far. We stripe the start bits into the available bits not taken by the self-synchronization prefix. All other bits shall be content bits.
1 00xxxxxx 2 010xxxxx 1xxxxxxx 3 0110xxxx 1xxxxxxx 1xxxxxxx ... 17 01111111 11111111 1110xxxx 1xxxxxxx ... 1xxxxxxx ...
But wait we've broken the distinction of ASCII! We cannot tell the difference between eg 0110xxxx and 0110xxxx, or 01111111 and 01111111. This code would only work if ASCII were six-bit instead of seven-bit. Out of curiosity we investigate this code in the rejected alternatives section ASCVI.
To maintain compatibility with ASCII we must treat it as a special case, whereby the self-synchronization prefix 0 is alone sufficient to characterize ASCII. This highlights that the architecting of UTF-8 was not purely a mathematics problem, but was also an engineering problem, working around what already exists.
Seeing the ASCII-characterizing prefix 0 and the erstwhile continuation prefix 1 as forming a prefix-free tree, albeit only of size two, we must repurpose the the latter codeword as the beginning of the self-synchronization prefixes for first bytes and continuation bytes of multi-byte code units. We choose our new self-synchronization prefixes as 11 for start bytes and 10 for continuation bytes. This produces the following tree:
.----0 First byte for ASCII
`----1---0 Continuation byte for multi-byte UTF-8000
`----1 First byte for multi-byte UTF-8000
Accordingly adjusting the self-punctuation codewords to apply only to multi-byte code units produces the following tree:
.----0 Two byte UTF-8
`----1---0 Three byte UTF-8
`----1---0 Four byte UTF-8
`----1---0 Five byte UTF-8000
`----... n byte UTF-8000
Putting these mechanisms together yields UTF-8000 and we're done!
ASCII 1 0xxxxxxx UTF-8 2 110xxxxx 10xxxxxx 3 1110xxxx 10xxxxxx 10xxxxxx 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx UTF-8000 5 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 6 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 7 11111110 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 8 11111111 100xxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 9 11111111 1010xxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10 11111111 10110xxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ... 22 11111111 10111111 10111111 10110xxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ... 10xxxxxx ...
It is a trivial* result of coding theory that the product of two prefix-free codes is also a prefix-free code. The product of our trees looks like:
.----0 ASCII byte
`----1---0 UTF-8 continuation byte
`----1---0 Two byte UTF-8 start byte
`----1---0 Three byte UTF-8 start byte
`----1---0 Four byte UTF-8 start byte
`----1---0 Five byte UTF-8000 start byte
`----... n byte UTF-8000 start byte
Without the color highlighting this is how most people think about UTF-8: a start byte whose prefix of n 1 bits and a terminating 0 bit provides both self-synchronization and self-punctuation, and continuation bytes using a short prefix of 10 for space-efficient encoding. This makes sense for a small number of bytes, but the trick to unlock a perspective of infinite extensibility is to split this tree into the self-synchronization part and self-punctuation part; ie we un-product those prefix-free codes. Failing to do this leads to the rejected alternative UTF-Infinity.
Encoding
This section is based off the reference implementation which is written in Python. It is well documented, and is more specific on how to use bitwise operations. This is an abridged HTML version.
Suppose that we have an unsigned integer n that we want to encode in UTF-8000. Initialize an empty dynamic array of bytes ret_ints that will store the UTF-8000 code unit.
If n < 0x80, eg n = 0x41, then insert n at the head of ret_ints and we are done. This is the ASCII byte for n, which in our example of n = 0x41 is a capital letter a, 'A'.
Otherwise for n ≥ 0x80, eg n = 0x0321C0FFEE8086, we use UTF-8000. Initialize an integer counter n_bits_content_occupied to zero.
Our example n's content bits look like 11 001000 011100 000011 111111 111011 101000 000010 000110 as a big raw number, with spaces added for visual ease.
While n has more than 6 content bits, aka n > 63 = 00111111, extract the least-significant 6 bits of n and insert them at the head of ret_ints, incrementing n_bits_content_occupied by 6 and downwards bitshifting n by 6.
n_bits_content_occupied = 48, n = 0b11,
ret_ints: 00001000 00011100 00000011 00111111 00111011 00101000 00000010 00000110
Now insert the rest of n at the head of ret_ints. Count the number of bits left in n by downwards bitshifting n one bit at a time while it is non-zero. This is between 1 and 6 (inclusive), which we also add to n_bits_content_occupied.
n_bits_content_occupied = 50, n = 0,
ret_ints: 00000011 00001000 00011100 00000011 00111111 00111011 00101000 00000010 00000110
Now we calculate how many bytes our UTF-8000 code unit requires, n_utf_8000_bytes_needed. We know that a k-byte code unit has capacity for 5k+1 content bits. Therefore ⌈(n_bits_content_occupied-1) / 5⌉ is the sufficient and minimal answer. Any larger code unit size would lead to an overlong encoding! For our example n_utf_8000_bytes_needed = ⌈(50-1) / 5⌉ = 10.
Leftwards pad ret_ints with empty bytes to the length n_utf_8000_bytes_needed.
ret_ints: 00000000 00000011 00001000 00011100 00000011 00111111 00111011 00101000 00000010 00000110
Now we add the start bits. The number of 1 start bits is equal to two less than the number of bytes in the code unit, which we just calculated. We therefore calculate q, r = divmod(n_utf_8000_bytes_needed-2, 6), which tells us we need q hextets full of 1 start bits, and a final hextet of zero to five 1 bits, which also has space to contain the terminating 0 bit. In our example (q = 1, r = 2) = divmod(10-2, 6).
Apply the start bits across ret_ints using bitwise-or. The final start bits hextet can be given by ((1 << r) - 1) << (6 - r).
ret_ints: 00111111 00110011 00001000 00011100 00000011 00111111 00111011 00101000 00000010 00000110
Any of the lowest six bits of each byte that are not set by this point, unoccupied by content bits and untouched by start bits, are really content bits that the k-byte capacity provides but that we didn't need. Our example's n_bits_content_occupied = 50 is one less than 5k+1 = 5*10+1 = 51. We can color highlight it green as a content bit for completion's sake.
ret_ints: 00111111 00110011 00001000 00011100 00000011 00111111 00111011 00101000 00000010 00000110
Now we crown the bytes with their self-synchronization prefixes, which delivers us from hextets to UTF-8000 octets. The first byte's self-synchronization prefix is 11, and continuation bytes have 10.
ret_ints: 11111111 10110011 10001000 10011100 10000011 10111111 10111011 10101000 10000010 10000110
And we're done!
Decoding
As with the encoding section, this section is based off the reference implementation which is written in Python and well documented.
Suppose that we are receiving a stream of UTF-8000 bytes (possibly with errors!), and we wish to extract and taxonomically annotate the incoming code units. There are a few ways that we could approach this, such as using the byte map as a state machine, which I want to try in the future, or the classic way of using bitwise masks. We are going to use the latter approach in this section, as we describe how to decode a single code unit. But first, a look at error handling.
Error Recovery
The errors that can occur when decoding a UTF-8000 stream are:
Reading a continuation byte (10) when we are expecting the first byte of a code unit (0 or 11).
Reading a first byte (0 or 11) when we are expecting a continuation byte (10).
Early EOF midway through a code unit.
Encountering an overlong encoding
- For 2-byte code units this is bytes 0xC0 (
11000000) and 0xC1 (11000001).
- For
n-byte code units in general, with n > 2, eg 11100000 10010111 10010000.
Encountering an encoded surrogate codepoint in the range U+D800 to U+DFFF, which is forbidden for compatibility with UTF-16.
For standard UTF-8 one would also have to be concerned with codepoints beyond the range U+10FFFF whence bytes 0xF5 to 0xFF go unused.
For any of these errors a parser could raise an exception and refuse to continue. Alternatively it could take advantage of UTF-8000's self-synchronization property, and keep calm and carry on, yielding Unicode replacement characters U+FFFD � until we reach the first byte of the next code unit. Let us investigate the latter course.
To handle error 1. the parser should return one � and get ready to parse the next code unit. When handling error 2. the parser should make sure to unpop the byte encountered, as it is the first byte of the next code unit. When handling errors 2. through to 5. there are a couple of mainstream approaches for yielding � characters:
Maximal Subpart
The Unicode Consortium recommends, but does not enforce, a maximal subpart approach, in which the longest well-formed part of a code unit should return a single � character, rather than one for each byte involved. For example the three bytes in error 4.2. above should return one � as it is well-formed with respect to self-synchronization and self-punctuation, and only invalid at an overlong level, being an overlong encoding of 11010111 10010000 U+05D0, a Hebrew letter Aleph 'א'.
I dislike this approach. Waiting for maximal subparts has the problem that the rest of an invalid code unit may never arrive. If we receive the bytes 11100000 10010111 from a socket, then the remote end may be waiting for us to chastise their overlong opening bytes with a response, because we can already tell that these bytes form part of an invalid code unit. Using the maximal subpart approach we also would be waiting, for the remote end to send a continuation byte eg 10010000 to form an overlong but otherwise complete 3-byte code unit. This is uncooperative, and not what I want.
One � For Each Byte Read
We are going to do what Python, my terminal KDE Konsole, and others do, and simply return a � character for each invalid byte. In Python b'\xE0\x97\x90'.decode(errors='replace') returns '���'.
This approach is easier and more versatile. The end user can see how many invalid bytes occurred by counting the number of � characters. There are no deadlock waiting events that can occur with the maximal subpart approach.
The Main Decode Loop
Initialize an empty dynamic array of bytes parsed_bytes that will store the bytes as we parse them.
Read a byte, store it as start_byte. Use bitwise masks to find the index, idx_0, of the most-significant zero bit in the byte. If there are no zeros in this byte, idx_0 should be set to -1.
If idx_0 == 7 (0xxxxxxx) then start_byte is an ASCII byte, which has seven content bits. Append start_byte to parsed_bytes and we are done.
If idx_0 == 6 (10xxxxxx) then start_byte is a continuation byte, which is an invalid start byte. Go to error 1.
If idx_0 == 5 (110xxxxx) then this is the first byte of a 2-byte code unit. We treat this as a special case because there are only 4 mandatory content bits, not 5. As they are all contained in start_byte we can check them immediately for overlong encoding, to see if we need to handle error 4.1. If start_byte passes this check then append it to parsed_bytes and await a continuation byte. Handle error 2 if necessary, else append the continuation byte to parsed_bytes and we're done.
We could (should really) make idx_0 == 4 a special case too, to check for and forbid the surrogate ranges. I have omitted this for the time being and we drop through to the generic case below.
Otherwise we enter the generic case (111[1...]). Initialize an integer counter n_bytes_expected to 2. Increment n_bytes_expected by 5 - idx_0, as idx_0 now serves the purpose being the index of the terminating zero of the start bits, 0.
If idx_0 == -1 then our code unit has multiple start bytes, exciting! Append start_byte to parsed_bytes, and while(1):
Read a byte, and make sure it is a continuation byte lest we go to error 2. Use bitwise masks to find idx_0, the index of the most-significant zero bit in the lowest six bits of the byte, setting idx_0 to -1 if there is none. This is to continue trying to find the 0 start bit. Increment n_bytes_expected by 5 - idx_0. If idx_0 == -1 then append start_byte to parsed_bytes and continue again through this loop, until we find the 0 bit, at which point we break this loop.
At this stage, whether our code unit has multiple start bytes or just one, start_byte is the final start byte of the code unit, idx_0 is between 0 and 5 (inclusive), and we move towards checking for overlong encoding. Just as ordinals count the number of things less than themselves, idx_0 counts the number of content bits contained start_byte, occupying the least significant bits.
There are six cases for anti-overlong checking, which correspond to idx_0's value. That may sound like a lot, but the looping gif below that I made should relax you. It demonstrates periodic behavior. Even though it shows deep code unit sections with multiple start bytes, this animation still applies for all code units of length n > 2. The colored bars are based off the anatomy section image.

If idx_0 == 5 then all the mandatory content bits are contained together in the final start byte. Thus we should immediately check start_byte using the mask 00011111. We then read the first non-start byte, a continuation byte which does not need overlong checking (10xxxxxx).
Otherwise we read another continuation byte, the first non-start byte. If idx_0 == 0 then all the mandatory content bits are contained together in this first non-start byte (10xxxxxx), and we use the mask 00111110 to check for overlong encoding. Else idx_0 is between 1 and 4 (inclusive) and the mandatory content bits are straddled across the final start byte and first non-start byte. In these cases we use two masks to check for overlong encoding, which one can see in the gif above.
Perhaps the case of idx_0 == 0 could be grouped in with idx_0 being between 1 and 4, by using an empty mask to check the final start byte, in order to make the algorithm less branch-y, but this walkthrough isolates which bytes are responsible for potential overlong encoding.
Given that the final start byte and first non-start byte have passed the overlong check, append them to parsed_bytes. Finally while the length of parsed_bytes is less than n_bytes_expected, read plain-old continuation bytes (10xxxxxx) and append them to parsed_bytes.
And we're done!