Validating UTF8 Strings via Lookup Tables | Hacker News Reader

Validating UTF8 Strings via Lookup Tables

darkcephas.blogspot.com

64 pointspetermcneeley41 comments

Has anyone tried to feed it strings from @glitchr_?

ٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰ

ه꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲

　　#oͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦ

╰̩̩̩̩̩̻̍̍̍̍̍̊●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊ᴗ̩̩̩̩̩̩̩̩̩̩̪̺̍̍̍̍̍̍̍̍̍̍̆̑●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊╯̩̩̩̩̩̩̻̍̍̍̍̍̊

فͤ҈ͨͥ҉҉ͦ҈҉ͨ҈ͩ҉ͪ҈ͣͯͫ҉ͥͬͨ҈ͭ҉ͮ҈ͯ҉ͨ҈ͭͭͬ҉ͧͥ҈ͣ҉ͨ҉҉҈ͧͥ҉ͯ҈ͮͥ҉ͭ҈ͤ҈ͦ҈ͥ҉ͧ҈ͩͯ҉ͭ҈ͨ҉ͨͥ҉҉ͣ҉ͣͪ҉ͧ҈ͭ҉ͩ҈ͤ҉ͮ҈ͯͥ҈ͬ҈ͭ҈ͦ҈ͨͣ҉ͥ҈ͯ҉҉ͣͧ҈ͫ҉ͭ҈ͥͯͯ҉ͦ҈ͥ҉ͧ҉҈ͩ҉ͭ҈ͣͨ҉ͣͥ҈ͪ҉ͧ҈ͭ

thanks mentioning it.

> const uint16_t* asShort = reinterpret_cast<const uint16_t*>(src);

Ick. That violates the aliasing rules in many cases and is therefore UB. And it’s wrong on big-endian systems.

Just do src[i] | ((size_t)(src[i+1]) << 8).

That code might produce two byte reads and a shift and the bitwise-or to reformulate the 16 bit value in memory . In the original code the 16 bit read feeds directly into the lookup table.

The compiler always might produce garbage. But a decent compiler won't:

    #include <stddef.h>
    #include <stdint.h>
    
    uint16_t read_2byte_le(const uint8_t *src)
    {
        return (uint16_t)(src[0] |
               ((uint16_t)(src[1]) << 8));
    }

This generates the correct code with gcc and with clang. Sadly, clang is a bit fragile in this regard: https://bugs.llvm.org/show_bug.cgi?id=39438

Even more sadly, msvc produces this type of asm:

lea r10,[r10+8] shl rcx,8 or rcx,rax shl r9,8 movzx eax,byte ptr [r10-8] shl rax,8 or rdx,rax shl r8,8

etc

Is msvc a serious target any more? I have the impression that it’s kind of deprecated in favor of clang.

MSVC supports the Clang front-end, but its optimizer and backend are absolutely not deprecated, as far as I can tell (Microsoft employee here, opinions are my own, no private info disclosed here, etc).

Clang doesn't have support for C++/CLI (.NET Interop) nor C++/CX (newfangled COM for Windows 8/10 APIs) AFAIK, so that's already two targets where clang isn't even an option[1], nevermind to the point of deprecating MSVC or supplanting it as a default.

Similarly, I've yet to see a gamedev codebase that doesn't use MSVC as the primary compiler for Windows builds.

[1] Technically you can consume C++/CX APIs as straight up COM in vanilla C++ but that's really not the intention, nor necessarily supported for some things.

Would a memcpy into a uint16_t be less fragile?

Just tried this with godbolt.org and yes, the memcpy() thing is consistently good while the shift-and-or version often gets an unoptimized implementation (depending on compiler and version).

In C++, not necessarily C, memcpy is how you type pun. Seeing as they often are the same compiler it's probably the fastest way.

IIRC memcpy is borderline UB here. It also has the same endianness problem.

I suppose I should add: this operation is so common that I’m surprised it’s not part of the language or the standard library.

The original code was accused of triggering UB. By definition you cannot defend it by saying what it does since that has been claimed to be undefined.

Focus on proving it's well-defined, or rewrite it until it is.

While out of scope to the post somewhat, with validating utf-8 it'd be great to know of a standard way to toss out special characters like the vertical ones that can be used to interrupt page content. Seems most places just never filter it. Even back in Neverwinter nights I believe you could do some fun names.

So validate the stream first, then apply your exclusion logic afterward (until you validate, you wouldn't have any way of knowing if you're excluding the right things, because you wouldn't yet know if you're even working with UTF-8).

Yeah, this is the previous step.

T̙̙̳̠͕h̩͍̣̗͇̙e̖̙͇̺͍̝̙r̭̦̭̗̯͓͍̘e̮̜̼̝'̬͕̦̭̠s͖͎ ̙͎̫̭ͅa̲͖͙̟̹͚̱̜l̮͇w̥̙͙͎͍̻a͇̦̤̭̫̼͍͔y͖̰̱̣͉̗̼̟̘s̲͇̼̻̻͍͉ ̠̞̦̲̝̱̗o̪n͈͎̞e̥͈̠̬͍̬̱̲ ̪̼̝̞̮g̥ṵ͈̥y͎̤͖̥ ̜̬ṯ̳̗̜̼̱̬r̠̫̪̺̫y̗͍͔̜͇͍ị̼̲n̖̥͙͓̹̘̞̳͕g͕̗ͅ ̪t̤o̰̞̱͓̫̙̙͔͕ ͍r̟u̺͈̞͚͖i͖͈̗̭͖̯n͈̼̜̹ ͙̙̪̰̫̼͓i̻̩̰̪t̤̦̖͉ ͇̳̰f͔̥͕̟̝o͉̬r̥͕̝̬̰ ̟̪͇̺͉̰̭ḛ̙͕͕̜v͚ͅe̥͈̰̮̭̼ṟ̥͔͎̯̖y̤̞̮̳̪̞̰o͖̱͙͖̜̦n̙̦e̘̰͉͓̫̥̞ ̩e͖͕ḽ̭̪͚͕ͅs̮̺̣̬͍ḙ̬̫̹̻̤͖̗.͎

Keep in mind those characters largely exist to allow people to write in their native languages, so you need to make sure your filter doesn't stop them from expressing themselves.

There are always trade-offs. Even written language is a constraint by itself.

Warning: unaligned reads invoke undefined behaviour!

Not on modern x86 processors[1].

[1]: https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m...

Undefined behaviour has nothing to do with CPU architecture...

It is undefined in multithreaded scenarios, not in single threaded code. In a world where memory access latencies dominate and you pay a huge penalty for cache misses, and a smaller yet significant penalty for TLB misses, there are some significant performance gains that can be gained by tightly packing fields in structures, while still maintaining alignment at a structure level. We’ve been doing this safely for years in prod now. I understand that the dogma of “unaligned reads invoke undefined behavior” is rather popular given how memorable it is, but it isn’t always true.

It's undefined even in single threaded code. The compiler can assume it's aligned and make optimizations which depend on it.

It sounds like what you were doing is marking a struct as "packed", and accessing the fields directly (instead of through a pointer to the field). That should be fine.

This might be a bit too late to reply. It’s undefined in C, but it’s well defined at a processor level (on x86). IIRC, there was one particular bit of code that’d crash on AArch64 due to unaligned pointers, but would run a bit faster than aligned code on x86-64. On the other hand, this trick wouldn’t work in multithreaded code even if the semantics were well defined, due to false sharing of cache lines.

Talking about lookup tables without using constexpr is like pissing away performance.

std::set is used in the lookup table construction. We will have to wait till c++ finalizes how memory is allocated in constexp before this type of code will execute at compile time.

Why wait for standard containers to be constexpr? This was recently shared on HN: https://github.com/hogliux/semimap

IMO this kind of lookup table is best computed externally, e.g. by a python script, and included as a literal `constexpr std::array` or something. I was recently trying to do something very similar with constexpr lookups, and threw in the towel due to different compilers having different levels of constexpr support. With literal tables, you know exactly what's going to happen.

Constexpr has tons of promise, but the compiler support just isn't there yet - we still have to think really hard about it and look at the generated code to verify.

What version of c++? Sounds like you are mixing 11 and 14+

c++14. I hit limits in clang relating to the depth of computation it will perform at compile-time, and those limits differ from gcc's and msvc's, so I switched.

What do you mean by "mixing 11 and 14"?

It sounded kind of like the differences in constexpr between 11 and 14 where 11 only allowed a single statement type thing.

Some people have used trampoline techniques to get around the depth limits. CRTP just did this for compile time regex.

> Lookup tables perform computations in a manner such that they are in effect creating new instructions custom fit for the algorithms specific purpose.

This is interesting. Considering validating utf8 is something a computer does a lot these days, would it be practical to provide this lookup table and associated instruction hardwired in a processor ? I'm thinkink about the ISA extensions possibilities provided by RiscV for example.

I may be way off, this table is 64kB in size right ? I have no idea about how much silicon real estate that represents relatively speaking...

I think it's 2^12 = 4096 in size.

Wait. Does it actually validate utf8 or just checks ranges in which 1-4 byte characters are encoded?

Björn Höhrmann wrote the gold standard for a minimalist scalar decoder and didn't depend on UB to do it:

https://bjoern.hoehrmann.de/utf-8/decoder/dfa/

Björn's decoder is nearly identical to the naive validity checker found here. It is about 9x slower than the superposition lookup table found here.

I gave it a whirl and it correctly rejects examples of each 'invalid byte sequence' cited by wikipedia.

    "\xff", // invalid byte
    "\x82", // unexpected continuation byte
    "\xc0", // not enough continuation bytes
    "\xed\xa0", // not enough continuation bytes
    "\xc0\x80", // "modified UTF-8's not really NUL (over-long encoding)
    "\xf0\x82\x82\x8c", // over-long euro symbol
    "\xed\xa0\x80", // invalid surrogate character U+d800

Most of the checks reduce to range checks, eg overlong sequences have 0's in the low-order bits of the first byte, which means 0xE0 is invalid.

I don't think he missed anything.

Reply on news.ycombinator.com