UTF-8 Validation
Lesson 5 of 11
5UTF-8 Validation
Your first serious meeting with bits: how UTF-8 encodes a character in one to four bytes, and how to validate it with a tiny state machine.
What the picture shows: م becomes the bytes 11011001 and 10000101: the prefix 110 opens a two-byte character, and 10 marks a continuation byte.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
An English letter fits in one small box, but an Arabic letter or emoji needs two, three or four. The first box carries a label saying how many boxes follow, and each following box has its own label. Validation means checking the labels tell the truth.
UTF-8 encodes a code point in 1 to 4 bytes: the first byte starts with 0, 110, 1110 or 11110, and each continuation byte starts with 10. You validate with a state machine reading the top bits by shifting and masking, as in byte >> 6 == 0b10.
Required fundamentals
Binary
A byte is eight bits with a value from 0 to 255. format(x, "08b") gives you the binary form and helps enormously while debugging.
The shift >>
byte >> 7 drops the last 7 bits and keeps the first one. That is your tool for inspecting the start of a byte.
The mask &
num & 0xFF keeps the lowest 8 bits and throws the rest away. The brief says outright that we handle only the 8 least significant bits.
A state machine
A simple, powerful idea: one variable holding "where am I?". Here it is the number of continuation bytes still expected. You need nothing more.
Core concepts
The task: a function that takes a list of integers, each representing one byte, and returns True if the list is a valid UTF-8 encoding.
1Why UTF-8 at all?
Unicode assigns a number to every character in every language, over a million possible numbers. If we stored each character in 4 bytes, an all-English file would be four times larger for no reason. UTF-8 answers that elegantly: a variable-length encoding, common characters (ASCII) in one byte, less common ones in two, three or four.
But if the length varies, how does a reader know where one character ends and the next begins? The answer is the leading bits of each byte, and that is exactly what we validate.
2The pattern table, the heart of the problem
| Character length | First-byte pattern | Continuation bytes | Range |
|---|---|---|---|
| 1 byte | 0xxxxxxx | none | 0, 127 (ASCII) |
| 2 bytes | 110xxxxx | 10xxxxxx ×1 | 192, 223 |
| 3 bytes | 1110xxxx | 10xxxxxx ×2 | 224, 239 |
| 4 bytes | 11110xxx | 10xxxxxx ×3 | 240, 247 |
| , (invalid) | 10xxxxxx | a continuation with no lead | 128, 191 |
| , (invalid) | 11111xxx | there is no 5-byte character | 248, 255 |
Notice the logic: the number of leading 1s in the first byte equals the character's length, separated by a zero. And every continuation byte always starts with 10, so a reader can never mistake a continuation byte for the start of a character.
3From pattern to code
To ask "does it start with 110?" we shift the byte 5 places right, leaving the first 3 bits, and compare with 0b110:
byte = 0b11000011 # 195 byte >> 5 = 0b110 # 6 -> yes, a 2-byte lead byte >> 6 = 0b11 # 3 -> not 0b10, so not a continuation byte >> 7 = 0b1 # 1 -> not 0, so not plain ASCII
All four checks follow the same principle:
| Question | Check |
|---|---|
| A one-byte character? | byte >> 7 == 0 |
| Lead of a two-byte character? | byte >> 5 == 0b110 |
| Lead of a three-byte one? | byte >> 4 == 0b1110 |
| Lead of a four-byte one? | byte >> 3 == 0b11110 |
| A continuation byte? | byte >> 6 == 0b10 |
byte >> 7 == 0 first. Had we started with byte >> 5 == 0b110, the byte 0b11000011 would pass by mistake, because its first 3 bits really are 110. The rule: check patterns shortest first, because the shorter pattern is the more specific one.4The & 0xFF mask and the 256 trap
The brief says: "each integer represents 1 byte of data, therefore you only need to handle the 8 least significant bits". Hence num & 0xFF. Look at the third test case [229, 65, 127, 256]:
num | num & 0xFF | Binary | Reading |
|---|---|---|---|
229 | 229 | 11100101 | Lead of a 3-byte character → expect 2 continuations |
65 | 65 | 01000001 | But this is 0xxxxxxx, not a continuation → False |
127 | 127 | 01111111 | We never reach it |
256 | 0 | 00000000 | Note: 256 becomes zero after the mask |
So the answer is False because of the second byte, not because of 256. Had the input been [256], it would be perfectly True, and that is the point that trips most people up.
5The final check: the truncated sequence
return continuation == 0 at the end is not decoration. If the input is [0xC3], that is the lead of a two-byte character, but the data ended before the continuation arrived. The loop finishes peacefully with continuation still at 1, the sequence is truncated, so the answer is False.
return True at the end of the function. That accepts every truncated sequence: [0xC3], [0xF0, 0x9F], and any lead byte without its continuations.How it works
Three pictures: the whole state machine, then the single-byte decision, then a real character taken apart byte by byte.
Diagram 12, The state machine: one "waiting for a lead" state and three waiting states. Data ending while in a waiting state means a truncated sequence, so the answer is false.
Diagram 13, The single-byte decision tree: shortest pattern first, and the last two branches are the invalid patterns.
Diagram 14, A real character: the grinning face 😀 in four bytes, a lead and three continuations, whose combined payload gives the Unicode number U+1F600.
Worked example, step by step
We write the solution, run it on the test cases, then on real characters from Python itself. Every output below is real.
Step 1, the solution
#!/usr/bin/python3
"""0-validate_utf8"""
def validUTF8(data):
"""Return True if data is a valid UTF-8 encoding."""
continuation = 0
for num in data:
byte = num & 0xFF
if continuation:
if byte >> 6 != 0b10:
return False
continuation -= 1
continue
if byte >> 7 == 0:
continuation = 0
elif byte >> 5 == 0b110:
continuation = 1
elif byte >> 4 == 0b1110:
continuation = 2
elif byte >> 3 == 0b11110:
continuation = 3
else:
return False
return continuation == 0Step 2, the test cases
$ cat 0-main.py
#!/usr/bin/python3
validUTF8 = __import__('0-validate_utf8').validUTF8
data = [65]
print(validUTF8(data))
data = [80, 121, 116, 104, 111, 110, 32, 105, 115, 32, 99, 111, 111, 108, 33]
print(validUTF8(data))
data = [229, 65, 127, 256]
print(validUTF8(data))
$ ./0-main.py
True
True
FalseStep 3, real characters from Python
>>> for ch in ["A", "é", "€", "😀", "م"]:
... b = list(ch.encode("utf-8"))
... print(repr(ch), b, [format(x, "08b") for x in b], validUTF8(b))
'A' [65] ['01000001'] True
'é' [195, 169] ['11000011', '10101001'] True
'€' [226, 130, 172] ['11100010', '10000010', '10101100'] True
'😀' [240, 159, 152, 128] ['11110000', '10011111', '10011000', '10000000'] True
'م' [217, 133] ['11011001', '10000101'] TrueThis is the best possible test: ch.encode("utf-8") produces a valid encoding by definition, so any False here means a bug in your solution. And note the Arabic letter م: two bytes, with the lead 11011001, which really is 110xxxxx ✓
Step 4, the invalid cases
>>> validUTF8([0xC3]) # a 2-byte lead with nothing after it False >>> validUTF8([0x80]) # a continuation byte with no lead False >>> validUTF8([0xF8, 0x80, 0x80, 0x80]) # 11111000 — no such lead pattern False >>> validUTF8([229, 65, 127, 256]) # 229 leads 3 bytes, 65 is not a continuation False
Step 5, walk 😀 byte by byte
Tracing four bytes, then breaking them on purpose
Input: [240, 159, 152, 128], the bytes of the grinning face 😀.
Start: continuation = 0.
Byte 240 = 11110000. continuation = 0, so no continuation is expected.
240 >> 7 = 1, so not ASCII. 240 >> 5 = 0b111, so not a 2-byte lead. 240 >> 4 = 0b1111, so not three. 240 >> 3 = 0b11110 ✓ → continuation = 3.
Byte 159 = 10011111. continuation = 3, so a continuation is expected.
159 >> 6 = 0b10 ✓ a valid continuation → continuation = 2.
Byte 152 = 10011000. 152 >> 6 = 0b10 ✓ → continuation = 1.
Byte 128 = 10000000. 128 >> 6 = 0b10 ✓ → continuation = 0.
The data ends with continuation == 0, so the answer is True ✓
Now break it: drop the last byte, leaving [240, 159, 152].
Everything proceeds as above, but the loop ends with continuation = 1. So the final line return continuation == 0 returns False, that is the line which catches a truncated sequence.
U+D800 to U+DFFF), and anything above U+10FFFF. The project does not ask for this, but knowing it separates "structurally valid" from "actually valid", and those distinctions are the source of real security holes in text parsers.Myth vs. reality
| The myth | The reality |
|---|---|
| “A byte with a value above 255 makes the input invalid.” | No. & 0xFF keeps the low 8 bits, so 256 becomes 0, a valid ASCII character. |
| “I check the lead patterns from longest to shortest.” | Backwards. byte >> 5 == 0b110 passes by mistake on a 4-byte lead, whose first 3 bits are 111. Start with the shortest. |
“return True at the end is enough.” | It accepts every truncated sequence. You need return continuation == 0 to reject a lead without its continuations. |
“A continuation byte 10xxxxxx can serve as a lead.” | Never. A 10xxxxxx with no lead before it is an immediate error, and that is what makes UTF-8 self-synchronising. |
| “There are 5- and 6-byte UTF-8 characters.” | There were in old drafts, but the current standard caps it at four. So the 11111xxx pattern is always invalid. |
| “If the structural check passes, the text is valid.” | Structurally yes, but overlong encodings and the surrogate range pass this check and are rejected by full validation. |
Where it is used in practice
Every piece of text on the internet
Over 98% of web pages are UTF-8. The browser performs exactly this check on every byte it receives, and you now know how.
Input security
Invalid and overlong encodings were a genuine vulnerability: malicious text slips past a filter and then decodes into something else. That is why modern parsers reject invalid bytes instead of ignoring them.
Self-synchronisation
Because a continuation byte always starts with 10, you can land in the middle of a huge file and know where the next character begins, without reading from the start.
State machines in general
One variable holding "where am I" is the same pattern used in JSON parsers, network protocols, and any incremental read of a stream.
Try it yourself
What does validUTF8([0xE2, 0x82]) return?
0xE2 = 11100010, the lead of a three-byte character, so two continuations are expected. 0x82 = 10000010 is a valid continuation, dropping the counter to 1. Then the data ends with continuation = 1, so return continuation == 0 returns False. (These are the first two bytes of [0xE2, 0x82, 0xAC] = €.)
Quick review flashcards
0xxxxxxx, 110xxxxx, 1110xxxx and 11110xxx, the number of leading 1s is the character's length.10xxxxxx. And it never works as the start of a character.num & 0xFF?256 becomes 0, for instance.byte >> 7 == 0 first?return continuation == 0 at the end of the function, not return True.11111xxx pattern is always invalid under the current standard.Check your understanding
1. Why does validUTF8([229, 65, 127, 256]) return False and not True?
229 = 11100101 is the lead of a three-byte character, so 10xxxxxx is expected next. But 65 = 01000001 is an ASCII pattern, not a continuation, so we return False immediately at the second byte. The 256 never even comes into it, we do not reach it.
2. Explain why byte >> 6 == 0b10 works at all.
Shifting six places drops the low 6 bits and keeps the first two. Comparing them with 0b10 checks exactly that the byte starts with 10, the continuation pattern. Every check uses the same technique: shift by however much you want to ignore.
3. (Spot the bug) Your solution returns True for [0x80]. Where is the mistake?
You never checked that a continuation byte comes after a lead. Most likely you put the byte >> 6 == 0b10 check in the main branch without the if continuation condition, so the byte 10000000 is accepted on its own.
4. Can a valid input have a length that is not a multiple of anything in particular?
Yes, and the length tells you nothing. [65] has length 1 and is valid, [195,169] has length 2 and is valid, [226,130,172] has length 3 and is valid. Validity lives in the patterns, not the count.
5. (Decision) You are building a text parser that receives data from the internet. Is this check enough?
No. This is a structural check, fine for the project, but a real parser must also reject overlong encodings (A written in two bytes), the surrogate range U+D800–U+DFFF, and values above U+10FFFF. The safest move is not to write the check yourself at all: use bytes(data).decode("utf-8"), which implements the full standard. Write the algorithm to understand it; use the library to depend on it.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Articles2
Done with this lesson?
Sign in to save your progress.