Skip to content

Instantly share code, notes, and snippets.

@skeeto

skeeto/utf8_decode.c

Last active Jan 26, 2021
Star
Embed
What would you like to do?
Learn more about clone URLs
Download ZIP
Branchless UTF-8 decoder automaton
Raw
utf8_decode.c
/* Branchless UTF-8 decoder automaton
*
* This automaton accepts one byte of input at a time, eventually either
* entering an ACCEPT state (0) and leaving a code point, or entering
* the REJECT state (-1). The state and code point must be zero on the
* first call of a new code point.
*
* The state value is always in the range -1 to 7.
*
* This is free and unencumbered software released into the public domain.
*/
enum { UTF8_ACCEPT = 0, UTF8_REJECT = -1 };
int
utf8_decode(int state, long *cp, int byte)
{
static const signed char table[8][256] = {
{+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+3, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +4, +2, +2,
+5, +6, +6, +6, +7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
+0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0, +0,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};
static unsigned char masks[2][8] = {
{0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f},
{0x7f, 0x1f, 0x0f, 0x0f, 0x0f, 0x07, 0x07, 0x07}
};
int next = table[state][byte];
*cp = (*cp << 6) | (byte & masks[!state][next&7]);
return next;
}
#ifdef TEST
/* Usage:
* $ cc -Os -fsanitize=address -fsanitize=undefined -DTEST utf8.c
* $ ./a.out
*/
#include <stdio.h>
#define IS_SURROGATE(c) ((c) >= 0xd800L && (c) <= 0xdfffL)
static void *
utf8_encode(void *buf, long c)
{
unsigned char *s = buf;
if (c >= (1L << 16)) {
s[0] = 0xf0 | (c >> 18);
s[1] = 0x80 | ((c >> 12) & 0x3f);
s[2] = 0x80 | ((c >> 6) & 0x3f);
s[3] = 0x80 | ((c >> 0) & 0x3f);
return s + 4;
} else if (c >= (1L << 11)) {
s[0] = 0xe0 | (c >> 12);
s[1] = 0x80 | ((c >> 6) & 0x3f);
s[2] = 0x80 | ((c >> 0) & 0x3f);
return s + 3;
} else if (c >= (1L << 7)) {
s[0] = 0xc0 | (c >> 6);
s[1] = 0x80 | ((c >> 0) & 0x3f);
return s + 2;
} else {
s[0] = c;
return s + 1;
}
}
static int
try_decode(const unsigned char *buf, int len)
{
long cp = 0;
int i, state = 0;
for (i = 0, state = 0; i < len; i++) {
state = utf8_decode(state, &cp, buf[i]);
if (state == UTF8_REJECT || state == UTF8_ACCEPT) {
break;
}
}
return state;
}
int
main(void)
{
long cp;
int result = 0;
for (cp = 0; cp <= 0x1fffff; cp++) {
long out = 0;
int state = 0;
unsigned char *p;
unsigned char buf[4];
unsigned char *end = utf8_encode(buf, cp);
for (p = buf; p < end; p++) {
state = utf8_decode(state, &out, *p);
if (state == UTF8_REJECT || state == UTF8_ACCEPT) {
break;
}
}
if (cp > 0x10ffff) {
switch (state) {
case UTF8_ACCEPT:
printf("FAIL: accepted U+%06lx (as U+%06lx)\n", cp, out);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
} else if (IS_SURROGATE(cp)) {
switch (state) {
case UTF8_ACCEPT:
printf("FAIL: accepted U+%06lx (as U+%06lx)\n", cp, out);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx (surrogate)\n", cp);
result = 1;
break;
}
} else {
switch (state) {
case UTF8_ACCEPT:
if (cp != out) {
printf("FAIL: wrong decode U+%06lx != U+%06lx\n", cp, out);
result = 1;
}
break;
case UTF8_REJECT:
printf("FAIL: rejected U+%06lx\n", cp);
result = 1;
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
}
}
for (cp = 0; cp <= 0x007fL; cp++) {
unsigned char buf[4];
buf[0] = 0xc0 | (cp >> 6);
buf[1] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 2)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (2) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
buf[0] = 0xe0;
buf[1] = 0x80 | (cp >> 6);
buf[2] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 3)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (3) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
buf[0] = 0xf0;
buf[1] = 0x80;
buf[2] = 0x80 | (cp >> 6);
buf[3] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 4)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (4) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
}
for (cp = 0x0080L; cp <= 0x07ffL; cp++) {
unsigned char buf[4];
buf[0] = 0xe0;
buf[1] = 0x80 | (cp >> 6);
buf[2] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 3)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (3) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
buf[0] = 0xf0;
buf[1] = 0x80;
buf[2] = 0x80 | (cp >> 6);
buf[3] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 4)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (4) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
}
for (cp = 0x0800L; cp <= 0xffffL; cp++) {
unsigned char buf[4];
buf[0] = 0xf0;
buf[1] = 0x80 | (cp >> 12);
buf[2] = 0x80 | ((cp >> 6) & 0x3f);
buf[3] = 0x80 | (cp & 0x3f);
switch (try_decode(buf, 4)) {
case UTF8_ACCEPT:
printf("FAIL: accepted overly-long (4) U+%06lx\n", cp);
result = 1;
break;
case UTF8_REJECT:
break;
default:
printf("FAIL: incomplete U+%06lx\n", cp);
result = 1;
break;
}
}
if (!result) puts("PASS");
return result;
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment