Improving a UTF-8 'validator'

Question

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;
}

The buffered version would fail to handle a multi-byte char crossing a 4k boundary unless needed_start and cp are part of parse_state, so that parse_block is essentially stateless as it exits. For performance, you might want to consider keeping them as locals and only reading/writing them on parse_state at parse_block entry/exit. Other candidates for caching in local vars for performance (and readability?) are buf[i] and/or byte_type[buf[i]]. — Paul Martel, Jan 31 '12 at 14:25
I prefer the more explicit original handling for 0xc0 and 0xc1 as error(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). — Paul Martel, Jan 31 '12 at 14:45
Thanks for catching that bug. I implemented state very quickly and forgot that needed_start and cp would need to be retained between blocks. With regards to the handling of start bytes that would generate overlongs or codepoints higher than U+10FFFF, the reason why I no longer catch any of them as explicitly invalid is because I think it is cleaner to catch them through the normal routes, and because explicit catching will cause several "unexpected continuation byte; ASCII or start byte expected" errors to follow once the parser state has been reset. — Delan Azabani, Feb 1 '12 at 4:31

Paul Martel · Accepted Answer · 2012-01-31 04:23:29Z

Move all of these declarations into main where they are used (mostly) and pass them as arguments as needed elsewhere (like error).

int in, msz_byte, state = 0, cpbytes = 0;
uint8_t byte;
uint32_t cp;
unsigned long long offset = 0;

Replace computations with vector lookups: replace msz(value) with msz[value] and eliminate the function.

For performance, valid(uint32_t) is simple enough to expand inline in the one place it is called, reversing the sense to account for the !.

Pass offset as an argument into error. Keep state within main; possibly reset it in an ERROR macro that calls error:

void error(int i, unsigned long long offset) {
    printf("%lld: %s\n", offset, errors[i]);
}

int main(void) {
    while ((in = getchar()) != EOF) {
        byte = in;
        msz_byte = msz(byte);

An offset++ HERE instead of at the bottom of the loop, would allow you to just continue; when finished processing each char (error or no error) eliminating the goto and break statements that all go the same place, anyway. You'd just need to remember to use offset-1 when reporting errors -- you can remember that in the ERROR macro that also remembers to reset state.

        if (
            byte == 0xc0 ||
            byte == 0xc1 ||
            byte == 0xfe ||
            byte == 0xff
            ) {

There's a fair amount of redundancy around these error cases. msz(0xff) is currently treated as a hard-coded special-case returning -1, but that's actually a don't care value to the caller. So is msz(0xfe) -- the only case returning 0, which is valid but way too subtle justification for there being no later handling for msz_byte<1. Possibly more useful than msz(int) or even msz[] would be something more general like char_class[] that gives one integer code (maybe -1) for these 4 error cases, another code (maybe 0) for ASCII chars, another for each of the 5 patterns that initiates a multi-byte sequence, and another (possibly 6) for continuation byte patterns. The code would be more readable if the values, especially the special values like -1, 0, and 6 were given named constants, or just use an enum.

            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;

The transformation from initial byte to initial codepoint could also be determined by vector lookup rather than repeated calculations, as in cp = initial_cp[byte];. Run your formula once per byte value to generate the vector, ideally in a separate program (simple code generator):

                cp = (byte & ((1 << msz_byte) - 1)) << (state * 6);

cpbytes is an odd duck. Since it gets incremented exactly when state gets decremented, it always ends up with a value one greater than the original state value. There's less maintenance involved in just setting an original_state = state; once, here, and testing that later instead of cpbytes.

                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) {

case 1: is actually the only one that (ever and always) transitions to (!state). It's simpler to rewrite/simplify (no shifting!) the generic code above for case 1: as a special case and only (unconditionally) adding the following code in that special case.

                    if (!valid(cp)) {
                        error(4);
                        goto next_byte;
                    }
                    if (
                        (cp <= 0x80) ||
                        (cp <= 0x800 && cpbytes > 2) ||
                        (cp <= 0x10000 && cpbytes > 3) ||
                        (cpbytes > 4)
                        ) {

This is another example where a vector could be used to simplify things. Put the boundary values in a vector and have something like if (cp < min_cp[original_state]).

Since cpbytes > 4 corresponds exactly to original_state > 3, it's strange to be eventually ruling out all state==4 and state==5 cases as:

                        error(5);

Oh, I just wanted to also respond to your last sentence. The reason is because any non-overlong sequences in five or six bytes (state == 4 or state == 5) are above U+10FFFF (not valid Unicode codepoints), and are caught by the valid(cp) test. Any sequences of five or six bytes that make it to the next test are implicitly overlong. — Delan Azabani, Jan 31 '12 at 7:38
That being the case, the validator should simply reject bytes from 0xf5 through 0xfd as illegal error(0) (expanding the error message) vs. error(5). From the user view, the problem is likely a corrupt byte at that offset. error(0) at THAT point seems more indicative than error(5) at the end, or the more likely error(2) or error(3) wherever it happens to run out of continuation bytes (one to four bytes later). — Paul Martel, Jan 31 '12 at 13:52
I'm not really sure I agree on this particular point. If a stream contained fd bc 95 86 b0 bf for example, I think it would be more meaningful to report that the codepoint is too high at the end, rather than report that the start byte is quasi-invalid, followed by an error reported for each continuation byte which is no longer expected. — Delan Azabani, Feb 1 '12 at 4:38

Stack Exchange Network

current community

your communities

more stack exchange communities

Improving a UTF-8 'validator'

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged c performance or ask your own question.

Hot Network Questions

Improving a UTF-8 'validator'

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c performance or ask your own question.

Related

Hot Network Questions