UTF-8
In September 1992 there were two proposals on the table for packing Unicode into bytes. The other one was denser. It packed 13 bits into two bytes where this one packs 11, and reached the same 31 bits in five bytes instead of six. The one that won gave those bits away to buy a single property: you can join the stream anywhere and find where a character starts.
A character, the bytes it becomes, and reading them from the middle
1 A number arrives, and its size alone picks the length
Type a character, or a codepoint as U+ and hex. Nothing here consults a table: the rows below are computed from the rule that an n-byte sequence spends n+1 bits of its lead byte and two of every continuation byte.
- codepoint
- U+4E16
- in binary
- 100 111000 010110
- needs
- 15 bits
- so it takes
- 3 bytes
2 bytes carry 11 payload bits and reach U+07FF. This needs 15, so the first row wide enough is the 3-byte one, which carries 16 and reaches U+FFFF.
2 The length picks a tag, and the bits fill what is left
The lead byte announces the length in unary: three bytes means three ones and a zero. Every byte after it starts 10. What is left over is where the number goes.
3 bytes, 24 bits on the wire, of which 8 are tag and 16 are payload.
3 Drop into those bytes anywhere, and walk back to the boundary
This is the property the encoding was chosen for. Click any byte below, or drag the slider, to join the stream there. The rule is the whole implementation: back up while you are standing on a byte that begins 10.
That default is the full title of the paper Pike and Thompson published about this in 1993, which puts one, two and three byte characters side by side.
- that byte is
- a lead byte, so a character begins here
- character starts at
- byte 0
- bytes thrown away
- 0
Worst case anywhere in this stream: 2 bytes discarded before the reader is in step, which is less than one character.
4 Hand that same reader something illegal, and watch it refuse
A reader that guesses is the bug. RFC 3629 names a real one: a parser that rejected /../ and accepted 2F C0 AE 2E 2F, used against web servers in 2001. Each row below is read by the same decoder as everything above.
The shortest-form rule is the one that needs checking. The design UTF-8 beat biased every range by its minimum, so each value had exactly one encoding for free. UTF-8 dropped the bias, which is why an overlong sequence can be written at all, and why a decoder has to refuse it rather than decode it.
What it cost, in bits
Both tables below come from the same document: the proposal Ken Thompson mailed to X/Open at 03:22 on 8 September 1992. The left column is the design that was already circulating, the right is what he sent back. Neither is typed into this page; both are computed from their tag shapes, which is why the row for five bytes is filled in on one side and not the other.
| bytes | 1992 proposal | UTF-8 | given up |
|---|---|---|---|
| 1 | 7 bits | 7 bits | nothing |
| 2 | 13 bits | 11 bits | 2 bits |
| 3 | 19 bits | 16 bits | 3 bits |
| 4 | 25 bits | 21 bits | 4 bits |
| 5 | 31 bits | 26 bits | 5 bits |
| 6 | — | 31 bits | — |
The arithmetic is the whole argument, and it is one bit in every byte rather than only in the continuations. A continuation byte used to spend a single bit marking itself as part of something, and carry seven; in UTF-8 it spends two and carries six. The lead byte pays as well, and for the same reason: a two-byte character used to begin 10zzzzzz, which UTF-8 cannot allow, because that is exactly the shape it reserved for continuation bytes. So every lead tag shifts up by one and gives up a bit to get out of the way. An n-byte character costs n bits, forever.
What that bit buys is in the byte values themselves. In the older design a byte with the high bit set could be a continuation byte or the first byte of a two-byte character, and nothing about the byte tells you which: 120 of the 256 possible values are ambiguous that way. In UTF-8 the continuation bytes occupy 10xxxxxx and every lead byte is outside it, so the ambiguous count is 0. That is not a smaller number. It is a different kind of number, and it is what lets stage three work at all.
Why anyone cared
Pike and Thompson had just converted Plan 9 to Unicode and wrote up what happened. Of the encoding they were replacing they said: UTF’s major disadvantage is that the encoding is not self-synchronizing. It is in general impossible to find the character boundaries in a UTF string without reading from the beginning of the string
. A file system that wants to compare a name, an editor that wants to draw the middle of a file, a program that wants to seek: all of them need to start somewhere other than the beginning.
That is the same shape as parity bits placed where the answer falls out of the arithmetic, and the opposite of a shift that costs a whole character and stays in effect until something cancels it. Baudot's shift is state you have to have been present for. UTF-8's tag is state carried in every byte, which is why the reader can arrive late.
What is real here, and what is not
The encoder is checked against a different one, over every codepoint
The page encodes with its own arithmetic, so agreeing with itself would prove nothing. The test suite encodes all 1,112,064 defined codepoints, every value from U+0000 to U+10FFFF except the surrogates, and compares each one byte for byte against the platform's own TextEncoder. That is somebody else's implementation of the same standard, written by people who have never seen this page.
There is no table of byte layouts anywhere in the code
RFC 3629 gives four rows. This page derives them. The lead byte of an n-byte sequence spends n+1 bits on its tag and each continuation spends two, so the payload capacity is arithmetic, and the ranges are whatever the shorter forms could not reach. Swapping two rows of a typed table leaves most tests green, which is a mistake this studio has shipped before; there is no table here to swap.
The 1992 comparison is derived the same way, from the same document
The rejected design's numbers are not copied out of Rob Pike's archive either. Its lead byte spends n bits and its continuation bytes spend one, and applying that gives 7, 13, 19, 25 and 31, which is what the archived table says. If this page and that document ever disagreed, the page would be wrong in a way you could see.
The placemat is one person's recollection
The story is that Ken Thompson worked the bit-packing out over dinner in a New Jersey diner. The source for that is Rob Pike, writing in 2003: “I very clearly remember Ken writing on the placemat and wished we had kept it!” One recollection, eleven years later, and no placemat. The date is firmer than the napkin: Russ Cox found the original file in the Bell Labs archive dated 2 September 1992, 23:44:10.
Five and six byte sequences were real, and are not any more
The 1992 design reached 31 bits in six bytes and the page's cost table shows those rows. RFC 3629 withdrew them in November 2003, capping UTF-8 at four bytes and U+10FFFF to match what UTF-16 can address. Stage four refuses a five-byte lead for that reason and says which reason. Both facts are true of different things and the page tries never to blur them.
Nothing here is a text renderer
The characters above are drawn by your browser with whatever fonts it has. If one shows as a box, that is a font gap and not an encoding failure, and the bytes beside it are still correct. Combining marks, right-to-left order and how many codepoints make up something a reader would call one character are all display questions this page does not touch, which is the same line Pike and Thompson drew when they deferred them in 1993.
Which parts are the standard and which are this page
The rule, the four rows, the shortest-form requirement, the surrogate exclusion and the U+10FFFF ceiling are RFC 3629. The count of ambiguous byte values, the worst-case skip on a given stream, and the bit-by-bit cost table are this page's own arithmetic over that rule. They are computed in front of you rather than asserted, and the tests recompute them a second way.
Sources
- Rob Pike, UTF-8 history, mail of 30 April 2003 with Russ Cox's dig through the Bell Labs archive. The primary source for this page. It carries both bit tables, the list of desiderata including the sixth about finding character boundaries from an arbitrary position, the file timestamp of 2 September 1992, and Pike's own account of the placemat. It is also where he calls the “IBM designed it, Plan 9 implemented it” version the bungled history, while giving X/Open and IBM “full kudos for making the opportunity happen”.
- RFC 3629, UTF-8, a transformation format of ISO 10646, F. Yergeau, November 2003, which is STD 63. The current standard: the four-row table, the statement that its rows are mutually exclusive so there is only one valid encoding of any character, the prohibition on U+D800..U+DFFF, and the security section that names
2F C0 AE 2E 2Fand the 2001 attack. - Rob Pike and Ken Thompson, “Hello World or Καλημέρα κόσμε or こんにちは 世界”, USENIX Winter 1993. Their own write-up of converting Plan 9, and the source of the quotation about the previous encoding not being self-synchronising. The paper's title is the default stream in stage three because it is one, two and three byte characters side by side.
- The Unicode Standard, Table 3-7, for well-formed byte sequences. Used to cross-check the ranges the page derives, not to supply them.