1 5c5b700d 2021-01-11 op In one of the recent posts, the one were I was discussing the IRI implementation in gmid, I said that I wasn’t happy with the UTF-8 parser.
3 5c5b700d 2021-01-11 op => /post/iris-are-not-hard.gmi IRIs are not hard!
5 9a959102 2021-01-12 op Since then, I improved the valid_multibyte_utf8 function at least two times, and I’m happy with the current result, but I thought to document here the various “generations” of that function.
7 5c5b700d 2021-01-11 op The purpose of valid_multibyte_utf8 is to tell if a string starts with a valid UTF-8 encoded UNICODE character, and advance the pointer past that glyph. We’re interested only in U+80 and up, because of the characters in the ASCII range we’ve already taken care of.
9 5c5b700d 2021-01-11 op UTF-8 is a multibyte character encoding for UNICODE text. Multibyte means that a single UNICODE codepoint can occupy more than one byte; in fact, UTF-8 is also variable-length: a codepoint can span between one and four bytes.
11 5c5b700d 2021-01-11 op UTF-8 is also a nice encoding, easy to parse but, as with everything that is related to UNICODE, with subtle and annoying details.
13 5c5b700d 2021-01-11 op The UNICODE codepoints are encoded as follows:
15 5c5b700d 2021-01-11 op * U+0000 - U+007F: one byte, compatible with ASCII
16 5c5b700d 2021-01-11 op * U+0080 - U+07FF: two bytes
17 5c5b700d 2021-01-11 op * U+0800 - U+D7FF and U+E0000 - U+FFFF: three bytes
18 5c5b700d 2021-01-11 op * U+10000 – U+10FFFF: four bytes
20 5c5b700d 2021-01-11 op Byte-wise, every UTF-8 character starts with either a 0 or with the bit patter 11XXXXXX. Byte starting with 11 are called UTF-8 “start bytes”, and are followed by up to three byte that starts with 10XXXXXX, called “continuation bytes”.
23 5c5b700d 2021-01-11 op one byte: 0.......
24 5c5b700d 2021-01-11 op two bytes: 110..... 10......
25 5c5b700d 2021-01-11 op three bytes: 1110.... 10...... 10......
26 5c5b700d 2021-01-11 op four bytes: 11110... 10...... 10...... 10......
29 5c5b700d 2021-01-11 op A first, quick implementation in C of a UTF-8 parser could look something like this:
32 5c5b700d 2021-01-11 op #define CONT_BYTE(b) ((b & 0xC0) == 0x80)
35 5c5b700d 2021-01-11 op valid_multibyte_utf8(struct parser *p)
37 5c5b700d 2021-01-11 op /* p->uri is our string */
38 5c5b700d 2021-01-11 op uint8_t s = *p->uri;
40 5c5b700d 2021-01-11 op if ((s & 0x80) == 0)
41 5c5b700d 2021-01-11 op /* return 1 here to accept ASCII */
44 5c5b700d 2021-01-11 op /* 2 bytes seq */
45 5c5b700d 2021-01-11 op if ((s & 0xE0) == 0xC0)
46 5c5b700d 2021-01-11 op return CONT_BYTE(*(++p->uri));
48 5c5b700d 2021-01-11 op /* 3 bytes seq */
49 5c5b700d 2021-01-11 op if ((s & 0xF0) == 0xE0)
50 5c5b700d 2021-01-11 op return CONT_BYTE(*(++p->uri))
51 5c5b700d 2021-01-11 op && CONT_BYTE(*(++p->uri));
53 5c5b700d 2021-01-11 op /* 4 bytes seq */
54 5c5b700d 2021-01-11 op if ((s & 0xF8) == 0xF0)
55 5c5b700d 2021-01-11 op return CONT_BYTE(*(++p->uri))
56 5c5b700d 2021-01-11 op && CONT_BYTE(*(++p->uri))
57 5c5b700d 2021-01-11 op && CONT_BYTE(*(++p->uri));
63 5c5b700d 2021-01-11 op This reads nice, and seems pretty straightforward. It checks the first byte, and then the appropriate number of continuation bytes. It won’t overflow if a codepoint is truncated due to the short-circuit nature of the logical and in C.
65 5c5b700d 2021-01-11 op But it isn’t UNICODE compliant.
67 5c5b700d 2021-01-11 op This parser will happily accept byte sequence that looks like UTF-8 but aren’t valid. In particular, everything in the range U+D800 - U+DFFF and U+110000 - U+1FFFFF DO NOT contain valid UNICODE codepoints. But this parser will accept them.
69 5c5b700d 2021-01-11 op An easy “upgrade” could be something like this, that inverts the logic of the ifs and checks that the codepoint we parse is in the correct range:
73 5c5b700d 2021-01-11 op valid_multibyte_utf8(struct parser *p)
81 5c5b700d 2021-01-11 op if ((s & 0xE0) == 0xC0) {
82 5c5b700d 2021-01-11 op if (!CONT_BYTE(p->uri[1]))
84 5c5b700d 2021-01-11 op c = ((s & 0x1F) << 6) | (p->uri[1] & 0x3F);
86 5c5b700d 2021-01-11 op } else if ((s & 0xF0) == 0xE0) {
87 5c5b700d 2021-01-11 op if (!CONT_BYTE(p->uri[1]) ||
88 5c5b700d 2021-01-11 op !CONT_BYTE(p->uri[2]))
90 5c5b700d 2021-01-11 op c = (s & 0x0F) << 12
91 5c5b700d 2021-01-11 op | ((p->uri[1] & 0x3F) << 6)
92 5c5b700d 2021-01-11 op | ((p->uri[2] & 0x3F));
94 5c5b700d 2021-01-11 op } else if ((s & 0xF8) == 0xF0) {
95 5c5b700d 2021-01-11 op if (!CONT_BYTE(p->uri[1]) ||
96 5c5b700d 2021-01-11 op !CONT_BYTE(p->uri[2]) ||
97 5c5b700d 2021-01-11 op !CONT_BYTE(p->uri[3]))
99 5c5b700d 2021-01-11 op c = (s & 0x07) << 18
100 5c5b700d 2021-01-11 op | ((p->uri[1] & 0x3F) << 12)
101 5c5b700d 2021-01-11 op | ((p->uri[2] & 0x3F) << 6)
102 5c5b700d 2021-01-11 op | ((p->uri[3] & 0x3F));
107 5c5b700d 2021-01-11 op return (((0x080 <= c) && (c <= 0x7FF))
108 5c5b700d 2021-01-11 op || (((0x800 <= c) && (c <= 0xFFFF)))
109 5c5b700d 2021-01-11 op || (((0x10000 <= c) && (c <= 0x10FFFF))));
113 5c5b700d 2021-01-11 op Oh my, this is starting to become ugly, isn’t it? Well, at least we can be sure that this handle everything and move on.
115 9a959102 2021-01-12 op Except that even this version is not complete. Sure, we know that we’ve read a valid UNICODE codepoint, but here’s the twist: overlong sequences.
117 5c5b700d 2021-01-11 op In UTF-8 sometimes you can encode the same character in multiple ways. The classic example, the one that various RFCs mentions, is the case of 0xC080.
119 5c5b700d 2021-01-11 op ``` hexadecimal, binary and decimal visual representations of 0xC080
120 5c5b700d 2021-01-11 op C 0 8 0 hexadecimal
121 5c5b700d 2021-01-11 op 1100 0000 1000 0000 binary
122 5c5b700d 2021-01-11 op 12 0 8 0 decimal
125 5c5b700d 2021-01-11 op This looks like a legit UTF-8 two-byte characters, but it gets encoded to NUL, U+0000.
127 5c5b700d 2021-01-11 op In RFC3629 — “UTF-8, a transformation format of ISO 10646” — explicitly warns implementors about this issue:
129 5c5b700d 2021-01-11 op > Implementations of the decoding algorithm above MUST protect against decoding invalid sequences. For instance, a naive implementation may decode the overlong UTF-8 sequence C0 80 into the character U+0000, or the surrogate pair ED A1 8C ED BE B4 into U+233B4. Decoding invalid sequences may have security consequences or cause other problems. See Security Considerations (Section 10) below.
130 5c5b700d 2021-01-11 op > — RFC3629, 3. “UTF-8 definition”
132 5c5b700d 2021-01-11 op Well, we could reverse the logic and have the various checks in every if-else branch but, honestly, this is becoming even messier. Magic numbers everywhere, long checks, etc; if only there were a simpler decoder…
134 5c5b700d 2021-01-11 op Introducing the “Flexible and Economical UTF-8 decoder”, by Björn Höhrmann.
136 5c5b700d 2021-01-11 op => https://bjoern.hoehrmann.de/utf-8/decoder/dfa/ «Flexible and Economical UTF-8 decoder».
138 5c5b700d 2021-01-11 op The decoder goes as follows:
140 5c5b700d 2021-01-11 op // Copyright (c) 2008-2009 Bjoern Hoehrmann <bjoern@hoehrmann.de>
141 5c5b700d 2021-01-11 op // See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
143 5c5b700d 2021-01-11 op #define UTF8_ACCEPT 0
144 5c5b700d 2021-01-11 op #define UTF8_REJECT 1
146 5c5b700d 2021-01-11 op static const uint8_t utf8d[] = {
147 5c5b700d 2021-01-11 op /* lots of data */
150 5c5b700d 2021-01-11 op uint32_t inline
151 5c5b700d 2021-01-11 op decode(uint32_t* state, uint32_t* codep, uint32_t byte) {
152 5c5b700d 2021-01-11 op uint32_t type = utf8d[byte];
154 5c5b700d 2021-01-11 op *codep = (*state != UTF8_ACCEPT) ?
155 5c5b700d 2021-01-11 op (byte & 0x3fu) | (*codep << 6) :
156 5c5b700d 2021-01-11 op (0xff >> type) & (byte);
158 5c5b700d 2021-01-11 op *state = utf8d[256 + *state*16 + type];
159 5c5b700d 2021-01-11 op return *state;
163 5c5b700d 2021-01-11 op The beauty of this decoder lies in the technique used: a state machine. I love state machines: they’re easy to design and reason about, fun and compact to implement and require only a small fixed amount of resources.
165 5c5b700d 2021-01-11 op valid_multibyte_utf8 can now be built on top of decode easily as follows:
168 5c5b700d 2021-01-11 op valid_multibyte_utf8(struct parser *p)
170 5c5b700d 2021-01-11 op uint32_t cp = 0, state = 0;
172 5c5b700d 2021-01-11 op for (; *p->uri; p->uri++)
173 5c5b700d 2021-01-11 op if (!utf8_decode(&state, &cp, *p->uri))
176 5c5b700d 2021-01-11 op /* reject also the ASCII range */
177 5c5b700d 2021-01-11 op return !state && cp > 0x7F
181 5c5b700d 2021-01-11 op That’s all about it. I found interesting to study these various techniques to decode UTF-8. Also, if you don’t know the story behind how Ken Thompson designed it on a placemat, go read it, it’s fascinating!
183 5c5b700d 2021-01-11 op => https://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt UTF-8 history