TAOCP 7.1.3 Exercise 199

We restart from the actual existence condition.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 199. ▶ [23] [23] A person might try to encode #a as #c08a or #e0808a or #f080808a in UTF-8, because the obvious decoding algorithm produces the same result in each case. But such unnecessarily long forms are illegal, because they could lead to security holes. Suppose α1 and α2 are bytes such that α1 ≥#80 and #80 ≤α2 < #c0. Find a branchless way to decide whether α1 and α2 are the first two bytes of at least one legitimate UTF-8 string α(x).

Verified: yes
Solve time: 3m

We restart from the actual existence condition.

We are given bytes $a=\alpha_1$ and $b=\alpha_2$ with

$$ a \ge #80,\qquad #80 \le b < #c0. $$

So $b$ is already a syntactically valid UTF-8 continuation byte. The question is whether there exists at least one valid UTF-8 string whose first two bytes are exactly $(a,b)$.

This is equivalent to: does there exist a valid UTF-8 codepoint encoding whose first byte is $a$, second byte is $b$, and whose remaining continuation bytes can be chosen to complete a valid scalar value in the Unicode range?

The key point is that UTF-8 validity constraints are entirely local for a fixed prefix: once the first byte is fixed, the allowed range of the second byte is determined, and if the prefix is valid, the remaining continuation bytes can always be chosen to complete some scalar value in range. Thus the problem reduces to classifying all valid $(a,b)$ prefixes that can occur in any UTF-8 encoding.

1. Valid UTF-8 structure

UTF-8 leading byte classes are:

  • 2-byte: $0xC2$–$0xDF$
  • 3-byte: $0xE0$–$0xEF$
  • 4-byte: $0xF0$–$0xF4$

The byte $a \in [0x80,0xBF]$ cannot be a leading byte, so only these three cases matter.

For each class, the second-byte constraint is not uniform. It depends on $a$:

2-byte sequences

$$ 0xC2 \le a \le 0xDF,\quad 0x80 \le b \le 0xBF. $$

3-byte sequences

  • $a = 0xE0$: $0xA0 \le b \le 0xBF$
  • $a = 0xED$: $0x80 \le b \le 0x9F$
  • $a \in [0xE1,0xEC] \cup [0xEE,0xEF]$: $0x80 \le b \le 0xBF$

These restrictions are necessary because they enforce:

  • no overlong encodings
  • no UTF-16 surrogate range $0xD800$–$0xDFFF$

Importantly, once these constraints are satisfied, a third byte can always be chosen to complete a valid scalar value. There is no additional global obstruction.

4-byte sequences

  • $a = 0xF0$: $0x90 \le b \le 0xBF$
  • $a = 0xF4$: $0x80 \le b \le 0x8F$
  • $a \in [0xF1,0xF3]$: $0x80 \le b \le 0xBF$

Again, once these prefix constraints hold, the remaining two continuation bytes can always be chosen to reach a valid scalar in $[0x10000,0x10FFFF]$.

2. Why no further constraints are needed

Fixing $(a,b)$ in a valid class determines a partial codepoint interval:

  • For 3-byte: $x \in [\text{base}(a,b), \text{base}(a,b)+0x3F]$
  • For 4-byte: analogous with a larger suffix range

In every allowed case above, this interval always intersects the valid Unicode scalar range, and never forces an impossible value once the second-byte restrictions are satisfied. Hence existence reduces exactly to membership in the prefix tables above.

3. Complete characterization

A pair $(a,b)$ is valid iff one of the following holds:

(i) 2-byte case

$$ 0xC2 \le a \le 0xDF \ \wedge\ 0x80 \le b < 0xC0 $$

(ii) 3-byte cases

$$ \begin{aligned} & a = 0xE0 \ \wedge\ 0xA0 \le b < 0xC0 \ \vee;& a = 0xED \ \wedge\ 0x80 \le b \le 0x9F \ \vee;& (0xE1 \le a \le 0xEC \ \vee\ 0xEE \le a \le 0xEF)\ \wedge\ 0x80 \le b < 0xC0 \end{aligned} $$

(iii) 4-byte cases

$$ \begin{aligned} & a = 0xF0 \ \wedge\ 0x90 \le b < 0xC0 \ \vee;& a = 0xF4 \ \wedge\ 0x80 \le b \le 0x8F \ \vee;& (0xF1 \le a \le 0xF3)\ \wedge\ 0x80 \le b < 0xC0 \end{aligned} $$

4. Branchless form

We encode the classification using indicator masks.

Let all comparisons be unsigned integer operations.

Define:

  • $C_2(a) = (0xC2 \le a \le 0xDF)$
  • $E_0(a) = (a = 0xE0)$, $E_D(a) = (a = 0xED)$
  • $E_m(a) = (0xE1 \le a \le 0xEF)$
  • $F_0(a) = (a = 0xF0)$, $F_4(a) = (a = 0xF4)$
  • $F_m(a) = (0xF1 \le a \le 0xF3)$

Then the predicate is:

$$ \begin{aligned} F(a,b) =;& C_2(a)\wedge(0x80 \le b < 0xC0) \ \vee;& E_0(a)\wedge(0xA0 \le b < 0xC0) \ \vee;& E_D(a)\wedge(0x80 \le b \le 0x9F) \ \vee;& E_m(a)\wedge(0x80 \le b < 0xC0) \ \vee;& F_0(a)\wedge(0x90 \le b < 0xC0) \ \vee;& F_4(a)\wedge(0x80 \le b \le 0x8F) \ \vee;& F_m(a)\wedge(0x80 \le b < 0xC0) \end{aligned} $$

5. Correctness conclusion

Every disjunct corresponds exactly to a valid UTF-8 prefix class with its required second-byte restriction. No other pairs are valid because any violation of these constraints produces either:

  • an overlong encoding,
  • a surrogate code point,
  • or an out-of-range code point.

Conversely, every pair satisfying one of the disjuncts can be extended by suitable continuation bytes to a full valid UTF-8 encoding.

Thus the predicate is necessary and sufficient, completing the solution.