I wrote a little utility to check stdin for correct UTF-8, reporting any errors encountered, but I am concerned about its simplicity and performance. Could anyone take a look and suggest some improvements please?
#include <stdio.h>
#include <stdint.h>
int in, msz_byte, state = 0, cpbytes = 0;
uint8_t byte;
uint32_t cp;
unsigned long long offset = 0;
/* Find the position of the most significant zero bit in a byte. Return 0 to
7, or -1 if there is no zero bit. */
int msz(uint8_t value) {
int r = 0;
if (value == 0xff)
return -1;
value = ~value;
while (value >>= 1)
r++;
return r;
}
/* Check if a codepoint is valid, returning 1 if so and 0 otherwise. Invalid
codepoints include those higher than U+10ffff, any codepoint from U+fdd0 to
U+fdef inclusive, as well as the last two codepoints in every plane, and
all surrogate pair values (U+d800 to U+dfff inclusive). */
int valid(uint32_t cp) {
return (
(cp < 0x110000) &&
((cp < 0xfdd0) || (cp > 0xfdef)) &&
((cp & 0xfffe) != 0xfffe) &&
((cp & 0xfffff800) != 0xd800)
);
}
/* Print an error, then reset the parser state. */
char *errors[] = {
"invalid byte (0xc0, 0xc1, 0xfe or 0xff)",
"unexpected continuation byte; ASCII or start byte expected",
"unexpected ASCII byte; continuation byte expected",
"unexpected start byte; continuation byte expected",
"invalid codepoint",
"overlong sequence",
"unexpected EOF while waiting for a continuation byte",
};
void error(int i) {
printf("%lld: %s\n", offset, errors[i]);
state = 0;
cpbytes = 0;
}
int main(void) {
while ((in = getchar()) != EOF) {
byte = in;
msz_byte = msz(byte);
if (
byte == 0xc0 ||
byte == 0xc1 ||
byte == 0xfe ||
byte == 0xff
) {
error(0);
goto next_byte;
}
switch (state) {
case 0:
if (msz_byte == 6) {
error(1);
goto next_byte;
}
if (msz_byte >= 1 && msz_byte <= 5) {
state = 6 - msz_byte;
cp = (byte & ((1 << msz_byte) - 1)) <<
(state * 6);
cpbytes = 1;
}
break;
case 1:
case 2:
case 3:
case 4:
case 5:
if (msz_byte == 7) {
error(2);
goto next_byte;
} else if (msz_byte >= 1 && msz_byte <= 5) {
error(3);
goto next_byte;
} else if (msz_byte == 6) {
cp |= (byte & 0x3f) << (--state * 6);
cpbytes++;
if (!state) {
if (!valid(cp)) {
error(4);
goto next_byte;
}
if (
(cp <= 0x80) ||
(cp <= 0x800 && cpbytes > 2) ||
(cp <= 0x10000 && cpbytes > 3) ||
(cpbytes > 4)
) {
error(5);
goto next_byte;
}
}
}
break;
}
next_byte:
offset++;
}
if (state)
error(6);
return 0;
}
Paul Martel's answer helped greatly, reducing runtime by 50% on a 10 MB all-zeros file, and reducing runtime by 80% on a 10 MB file of random bytes.
#include <stdio.h>
#define ERROR(error) do {\
printf("%llu: %s\n", offset, errors[error]);\
needed = 0;\
continue;\
} while (0)
char *errors[] = {
"invalid byte (0xfe or 0xff)",
"unexpected continuation byte; ASCII or start byte expected",
"unexpected ASCII byte; continuation byte expected",
"unexpected start byte; continuation byte expected",
"invalid codepoint",
"overlong sequence",
"unexpected EOF while waiting for a continuation byte",
};
int byte_type[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,
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,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7
};
unsigned long initial_cp[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,
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, 0x40, 0x80, 0xc0, 0x100, 0x140, 0x180, 0x1c0,
0x200, 0x240, 0x280, 0x2c0, 0x300, 0x340, 0x380, 0x3c0,
0x400, 0x440, 0x480, 0x4c0, 0x500, 0x540, 0x580, 0x5c0,
0x600, 0x640, 0x680, 0x6c0, 0x700, 0x740, 0x780, 0x7c0,
0, 0x1000, 0x2000, 0x3000, 0x4000, 0x5000, 0x6000, 0x7000,
0x8000, 0x9000, 0xa000, 0xb000, 0xc000, 0xd000, 0xe000, 0xf000,
0, 0x40000, 0x80000, 0xc0000,
0x100000, 0x140000, 0x180000, 0x1c0000,
0, 0x1000000, 0x2000000, 0x3000000,
0, 0x40000000, 0, 0
};
unsigned long min_cp[6] = { 0, 0x80, 0x800, 0x10000, 0x200000, 0x4000000 };
int main(void) {
int in, needed = 0, needed_start;
unsigned long cp;
long long offset = -1;
while ((in = getchar()) != EOF) {
offset++;
if (byte_type[in] == 7)
ERROR(0);
switch (needed) {
case 0:
if (byte_type[in] == 1)
ERROR(1);
else if (byte_type[in] != 0) {
needed = byte_type[in] - 1;
needed_start = needed;
cp = initial_cp[in];
}
break;
case 1:
if (byte_type[in] == 0)
ERROR(2);
else if (byte_type[in] > 1)
ERROR(3);
else {
cp |= in & 0x3f;
needed = 0;
if (
(cp > 0x110000) ||
((cp >= 0xfdd0) && (cp <= 0xfdef)) ||
((cp & 0xfffe) == 0xfffe) ||
((cp & 0xfffff800) == 0xd800)
)
ERROR(4);
if (cp < min_cp[needed_start])
ERROR(5);
}
break;
case 2:
case 3:
case 4:
case 5:
if (byte_type[in] == 0)
ERROR(2);
else if (byte_type[in] > 1)
ERROR(3);
else
cp |= (in & 0x3f) << (--needed * 6);
break;
}
}
if (needed)
ERROR(6);
return 0;
}
One optimisation I made afterwards was to eliminate the getchar() function call overhead by reading and parsing 4096 bytes at a time. This cut down runtimes by at least another 50%.
(fixed bugs where not enough state was retained)
#include <stdio.h>
#define ERROR(error) do {\
printf("%llu: %s\n", state->offset, errors[error]);\
state->needed = 0;\
continue;\
} while (0)
struct parser_state {
long long offset;
int needed;
int needed_start;
unsigned long cp;
};
char *errors[] = {
"invalid byte (0xfe or 0xff)",
"unexpected continuation byte; ASCII or start byte expected",
"unexpected ASCII byte; continuation byte expected",
"unexpected start byte; continuation byte expected",
"invalid codepoint",
"overlong sequence",
"unexpected EOF while waiting for a continuation byte",
};
int byte_type[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,
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,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7
};
unsigned long initial_cp[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,
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, 0x40, 0x80, 0xc0, 0x100, 0x140, 0x180, 0x1c0,
0x200, 0x240, 0x280, 0x2c0, 0x300, 0x340, 0x380, 0x3c0,
0x400, 0x440, 0x480, 0x4c0, 0x500, 0x540, 0x580, 0x5c0,
0x600, 0x640, 0x680, 0x6c0, 0x700, 0x740, 0x780, 0x7c0,
0, 0x1000, 0x2000, 0x3000, 0x4000, 0x5000, 0x6000, 0x7000,
0x8000, 0x9000, 0xa000, 0xb000, 0xc000, 0xd000, 0xe000, 0xf000,
0, 0x40000, 0x80000, 0xc0000,
0x100000, 0x140000, 0x180000, 0x1c0000,
0, 0x1000000, 0x2000000, 0x3000000,
0, 0x40000000, 0, 0
};
unsigned long min_cp[6] = { 0, 0x80, 0x800, 0x10000, 0x200000, 0x4000000 };
void parse_block(struct parser_state *state, unsigned char *buf, long long len) {
long i;
for (i = 0; i < len; i++) {
state->offset++;
if (byte_type[buf[i]] == 7)
ERROR(0);
switch (state->needed) {
case 0:
if (byte_type[buf[i]] == 1)
ERROR(1);
else if (byte_type[buf[i]] != 0) {
state->needed = byte_type[buf[i]] - 1;
state->needed_start = state->needed;
state->cp = initial_cp[buf[i]];
}
break;
case 1:
if (byte_type[buf[i]] == 0)
ERROR(2);
else if (byte_type[buf[i]] > 1)
ERROR(3);
else {
state->cp |= buf[i] & 0x3f;
state->needed = 0;
if (
(state->cp > 0x110000) ||
((state->cp >= 0xfdd0) &&
(state->cp <= 0xfdef)) ||
((state->cp & 0xfffe) == 0xfffe) ||
((state->cp & 0xfffff800) == 0xd800)
)
ERROR(4);
if (state->cp < min_cp[state->needed_start])
ERROR(5);
}
break;
case 2:
case 3:
case 4:
case 5:
if (byte_type[buf[i]] == 0)
ERROR(2);
else if (byte_type[buf[i]] > 1)
ERROR(3);
else
state->cp |= (buf[i] & 0x3f) <<
(--(state->needed) * 6);
break;
}
}
}
int main(void) {
size_t bufread;
unsigned char buf[4096];
struct parser_state state = { -1, 0, 0, 0 };
while ((bufread = fread(buf, 1, 4096, stdin)))
parse_block(&state, buf, bufread);
if (state.needed)
puts(errors[6]);
return 0;
}
buf[i]
and/orbyte_type[buf[i]]
. \$\endgroup\$ – Paul Martel Jan 31 '12 at 14:250xc0
and0xc1
aserror(0)
and in fact (as I've already commented elsewhere) think you should build on it -- the first two 2s in byte_type should be 7s, (as well as the last two 4s and the 5s and 6s). \$\endgroup\$ – Paul Martel Jan 31 '12 at 14:45