7 ms·

Validating UTF8 Strings via Lookup Tables

64 points by petermcneeley 8y ago

amluto 8y ago
> 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).
- petermcneeley 8y ago
  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.
  - amluto 8y ago
    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 https://bugs.llvm.org/show_bug.cgi?id=39438
    - petermcneeley 8y ago
      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
      - amluto 8y ago
        Is msvc a serious target any more? I have the impression that it’s kind of deprecated in favor of clang.
        pianoben 8y ago
        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).
        MaulingMonkey 8y ago
        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.
    - cesarb 8y ago
      Would a memcpy into a uint16_t be less fragile?
      - pjscott 8y ago
        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).
        beached_whale 8y ago
        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.
      - amluto 8y ago
        IIRC memcpy is borderline UB here. It also has the same endianness problem.
    - amluto 8y ago
      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.
  - unwind 8y ago
    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.
inetknght 8y ago
Talking about lookup tables without using constexpr is like pissing away performance.
- petermcneeley 8y ago
  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.
  - inetknght 8y ago
    Why wait for standard containers to be constexpr? This was recently shared on HN: https://github.com/hogliux/semimap https://github.com/hogliux/semimap
- pianoben 8y ago
  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.
  - beached_whale 8y ago
    What version of c++? Sounds like you are mixing 11 and 14+
    - pianoben 8y ago
      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"?
aaaaaaaaaab 8y ago
Warning: unaligned reads invoke undefined behaviour!
- woadwarrior01 8y ago
  Not on modern x86 processors[1]. [1]: https://lemire.me/blog/2012/05/31/data-alignment-for-speed-myth-or-reality/ https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m...
  - aaaaaaaaaab 8y ago
    Undefined behaviour has nothing to do with CPU architecture...
    - woadwarrior01 8y ago
      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.
      - cesarb 8y ago
        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.
        woadwarrior01 8y ago
        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.
devwastaken 8y ago
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.
- ubernostrum 8y ago
  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).
  - carlmr 8y ago
    Yeah, this is the previous step.
- cmyr 8y ago
  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̮̺̣̬͍ḙ̬̫̹̻̤͖̗.͎
- kevingadd 8y ago
  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.
  - VMG 8y ago
    There are always trade-offs. Even written language is a constraint by itself.
karlisolte 8y ago
Wait. Does it actually validate utf8 or just checks ranges in which 1-4 byte characters are encoded?
- kevin_thibedeau 8y ago
  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/ https://bjoern.hoehrmann.de/utf-8/decoder/dfa/
  - petermcneeley 8y ago
    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.
- jepler 8y ago
  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
- kwillets 8y ago
  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.
nradov 8y ago
Has anyone tried to feed it strings from @glitchr_? https://twitter.com/glitchr_ https://twitter.com/glitchr_ ٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰ ه꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲ 　　#oͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦ ╰̩̩̩̩̩̻̍̍̍̍̍̊●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊ᴗ̩̩̩̩̩̩̩̩̩̩̪̺̍̍̍̍̍̍̍̍̍̍̆̑●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊╯̩̩̩̩̩̩̻̍̍̍̍̍̊ فͤ҈ͨͥ҉҉ͦ҈҉ͨ҈ͩ҉ͪ҈ͣͯͫ҉ͥͬͨ҈ͭ҉ͮ҈ͯ҉ͨ҈ͭͭͬ҉ͧͥ҈ͣ҉ͨ҉҉҈ͧͥ҉ͯ҈ͮͥ҉ͭ҈ͤ҈ͦ҈ͥ҉ͧ҈ͩͯ҉ͭ҈ͨ҉ͨͥ҉҉ͣ҉ͣͪ҉ͧ҈ͭ҉ͩ҈ͤ҉ͮ҈ͯͥ҈ͬ҈ͭ҈ͦ҈ͨͣ҉ͥ҈ͯ҉҉ͣͧ҈ͫ҉ͭ҈ͥͯͯ҉ͦ҈ͥ҉ͧ҉҈ͩ҉ͭ҈ͣͨ҉ͣͥ҈ͪ҉ͧ҈ͭ
- xiconfjs 8y ago
  thanks mentioning it.
navaati 8y ago
> 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...
- kwillets 8y ago
  I think it's 2^12 = 4096 in size.

64 points by petermcneeley 8y ago

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

petermcneeley 8y ago
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.
- amluto 8y ago
  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 https://bugs.llvm.org/show_bug.cgi?id=39438
  - petermcneeley 8y ago
    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
    - amluto 8y ago
      Is msvc a serious target any more? I have the impression that it’s kind of deprecated in favor of clang.
      - pianoben 8y ago
        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).
      - MaulingMonkey 8y ago
        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.
  - cesarb 8y ago
    Would a memcpy into a uint16_t be less fragile?
    - pjscott 8y ago
      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).
      - beached_whale 8y ago
        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.
    - amluto 8y ago
      IIRC memcpy is borderline UB here. It also has the same endianness problem.
  - amluto 8y ago
    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.
- unwind 8y ago
  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.

inetknght 8y ago

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

petermcneeley 8y ago
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.
- inetknght 8y ago
  Why wait for standard containers to be constexpr? This was recently shared on HN: https://github.com/hogliux/semimap https://github.com/hogliux/semimap
pianoben 8y ago
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.
- beached_whale 8y ago
  What version of c++? Sounds like you are mixing 11 and 14+
  - pianoben 8y ago
    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"?

aaaaaaaaaab 8y ago

Warning: unaligned reads invoke undefined behaviour!

woadwarrior01 8y ago
Not on modern x86 processors[1]. [1]: https://lemire.me/blog/2012/05/31/data-alignment-for-speed-myth-or-reality/ https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m...
- aaaaaaaaaab 8y ago
  Undefined behaviour has nothing to do with CPU architecture...
  - woadwarrior01 8y ago
    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.
    - cesarb 8y ago
      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.
      - woadwarrior01 8y ago
        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.

devwastaken 8y ago

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.

ubernostrum 8y ago
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).
- carlmr 8y ago
  Yeah, this is the previous step.
cmyr 8y ago
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̮̺̣̬͍ḙ̬̫̹̻̤͖̗.͎
kevingadd 8y ago
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.
- VMG 8y ago
  There are always trade-offs. Even written language is a constraint by itself.

karlisolte 8y ago

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

kevin_thibedeau 8y ago
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/ https://bjoern.hoehrmann.de/utf-8/decoder/dfa/
- petermcneeley 8y ago
  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.
jepler 8y ago
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
kwillets 8y ago
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.

nradov 8y ago

Has anyone tried to feed it strings from @glitchr_? https://twitter.com/glitchr_ https://twitter.com/glitchr_ ٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٳٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰٰ ه꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲҉꙰꙱҈̿꙲ 　　#oͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦͦ ╰̩̩̩̩̩̻̍̍̍̍̍̊●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊ᴗ̩̩̩̩̩̩̩̩̩̩̪̺̍̍̍̍̍̍̍̍̍̍̆̑●̩̩̩̩̩̩̩̻̍̍̍̍̍̍̍̊╯̩̩̩̩̩̩̻̍̍̍̍̍̊ فͤ҈ͨͥ҉҉ͦ҈҉ͨ҈ͩ҉ͪ҈ͣͯͫ҉ͥͬͨ҈ͭ҉ͮ҈ͯ҉ͨ҈ͭͭͬ҉ͧͥ҈ͣ҉ͨ҉҉҈ͧͥ҉ͯ҈ͮͥ҉ͭ҈ͤ҈ͦ҈ͥ҉ͧ҈ͩͯ҉ͭ҈ͨ҉ͨͥ҉҉ͣ҉ͣͪ҉ͧ҈ͭ҉ͩ҈ͤ҉ͮ҈ͯͥ҈ͬ҈ͭ҈ͦ҈ͨͣ҉ͥ҈ͯ҉҉ͣͧ҈ͫ҉ͭ҈ͥͯͯ҉ͦ҈ͥ҉ͧ҉҈ͩ҉ͭ҈ͣͨ҉ͣͥ҈ͪ҉ͧ҈ͭ

xiconfjs 8y ago
thanks mentioning it.

navaati 8y ago

> 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...

kwillets 8y ago
I think it's 2^12 = 4096 in size.