Decoding UTF-8 by Hand, and the Three Traps That Are Security Bugs
UTF-8 is the encoding that won the internet, and its design is genuinely clever: it is backward-compatible with ASCII, self-synchronizing, and tells you a character's length from its first byte. Decoding the happy path takes a few lines. Decoding it safely is where the interesting work is, because the invalid inputs are not just garbage to skip. Some of them have been used to sneak past security checks.
The bit layout
A code point is encoded in one to four bytes, and the high bits of the lead byte announce the length:
1 byte: 0xxxxxxx U+0000 .. U+007F (ASCII)
2 bytes: 110xxxxx 10xxxxxx U+0080 .. U+07FF
3 bytes: 1110xxxx 10xxxxxx 10xxxxxx U+0800 .. U+FFFF
4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx U+10000 .. U+10FFFF
Every continuation byte starts with 10. You strip the marker bits, then shift the payload bits together, six per continuation byte:
if ((b & 0xE0) == 0xC0) { cp = b & 0x1F; extra = 1; min = 0x80; } // 2-byte lead
// ... for each continuation byte c:
if ((c & 0xC0) != 0x80) return -1; // not a continuation byte
cp = (cp << 6) | (c & 0x3F); // shift in six more bits
That is the decode. If that were the whole story, UTF-8 would be a five-minute exercise. It is not, because three families of byte sequences pass the decode but must be rejected, and each one is a real trap.
Trap 1: overlong encodings
UTF-8 says every code point must use the shortest form that fits. But the mechanics happily let you encode a small value in too many bytes. The character / (U+002F) is a one-byte 0x2F, yet 0xC0 0xAF also decodes to 0x2F using two bytes. That is an overlong encoding, and it is forbidden.
Why does anyone care? Because overlong encodings were a classic way to smuggle dangerous characters past filters. A security check scans for the bytes of ../ to block path traversal, sees none, and passes the input. Then a downstream decoder turns the overlong sequence back into ../ and the attacker walks out of the web root. Microsoft IIS had exactly this bug. The defense is one comparison: after assembling the code point, reject it if it is below the minimum value for the length you decoded.
if (cp < min) return -1; // overlong: could have used fewer bytes
Trap 2: surrogates
The range U+D800 to U+DFFF is reserved for UTF-16's surrogate pairs and does not represent characters on its own. A valid UTF-8 stream must never contain a code point in that range. The bytes 0xED 0xA0 0x80 decode cleanly to U+D800, and you must throw them out anyway:
if (cp >= 0xD800 && cp <= 0xDFFF) return -1; // surrogate half, not a scalar value
Letting surrogates through corrupts text and breaks anything that re-encodes to UTF-16, and like overlongs it has been a source of cross-system smuggling bugs.
Trap 3: out of range
Unicode stops at U+10FFFF. Four UTF-8 bytes can physically encode values above that, all the way past U+1FFFFF, but those code points do not exist. Reject anything larger:
if (cp > 0x10FFFF) return -1; // beyond the Unicode ceiling
The shape of a correct decoder
Notice the pattern: the validation checks all happen after you have assembled the code point, and they are all simple range comparisons.
// b is the lead byte; assemble cp from b and its continuation bytes, then:
if (cp < min) return -1; // overlong
if (cp > 0x10FFFF) return -1; // out of range
if (cp >= 0xD800 && cp <= 0xDFFF) return -1; // surrogate
Plus the structural checks along the way: a lead byte that is actually a lone continuation (10xxxxxx) or a 5-plus-byte form is invalid, a continuation byte that does not start with 10 is invalid, and a sequence that runs off the end of the input (truncated) is invalid.
The lessons
- Decoding is the easy half; validating is the job. The bit-shuffling is mechanical. The reason UTF-8 decoders are subtle is that "looks decodable" and "is valid" are different, and the gap between them is where bugs live.
- Invalid input can be an attack, not an accident. Overlong and surrogate encodings are not random corruption; they are how people have historically bypassed filters. "Be liberal in what you accept" is exactly the wrong instinct for a text decoder at a trust boundary.
- It is all bit masks and range checks. No tables, no library, no allocation. Mask the lead byte to learn the length, shift in six bits per continuation, then guard three ranges. That is the whole thing, and getting the three guards right is what separates a real decoder from a vulnerability.
UTF-8 rewards you for reading the spec to the end. The encoding is elegant, and its elegance includes precise rules about what is not allowed, rules that exist because someone, somewhere, tried to exploit the gap.
Build it yourself. Solve the UTF-8 Decode & Validate challenge on barehands and get graded on correctness and speed. No libraries, just cc -std=c11.