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

I happened to come across this decoder again recently in Niels Lohmann's JSON library for C++:

https://github.com/nlohmann/json

I see that this is mentioned in a previous post:

https://lemire.me/blog/2018/05/09/how-quickly-can-you-check-...

One thing I'd like to check in the new code is whether it's as picky about things like overlong sequences as Bjoern's code is.

I believe that's what checkContinuation() is doing, based on its use of the "counts" parameters. I don't understand how it works, but I don't see any other reason for count_nibbles() to compute the '->count' member.

A while back, I read that the Chinese Longson processors were a (subset?) of the MIPS instruction set with added instructions for Unicode handling, but that's all I've heard of processors with Unicode accelerating instructions, and I'm not sure which encoding(s) was/were accelerated.

[0]https://news.ycombinator.com/item?id=11263378

If we took this attitude with every new technology, we'd have a large number of instructions that are now useless. At one time it probably seemed a good idea to have custom instructions for parsing XML, and people really were doing custom instructions for interpreting JVM bytecode.

Not to mention that I think it's fair to say that UTF-8 will outlast AES (it's actually older than AES). After all, AES was only standardised in 2001 -- and AES-NI was added when it was 7 years old. Unicode (and UTF-8) were standardised in 1991. So if we have AES instructions we should already have UTF-8 instructions.

Say what? Unless you mean something other than ‘elliptic curve’ by ‘EC,’ that doesn’t make sense to me: AES & EC are completely different kinds of thing, the former being symmetric & the latter being asymmetric. Indeed, it’s quite common to use an EC-derived secret as the key for AES-encrypted material.

Plus, there are already several instructions on x86 that for string manipulation.

Also SHA1, AES, CRC32, and other specialized functions that may have less staying power than UTF-8 (SHA1 in particular, but also AES being a block cipher has some nuisances that means it is not always used in new algorithms).

Ah yes, ARM Jazelle, and the good ol' ARM926EJ-S...

https://en.wikipedia.org/wiki/Jazelle

Did the concept die with ARMv8 (64bit)?

  $ cat /proc/cpuinfo
  processor       : 0
  model name      : ARMv7 Processor rev 4 (v7l)
  BogoMIPS        : 38.40
  Features        : half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 lpae evtstrm crc32 
  CPU implementer : 0x41
  CPU architecture: 7
  CPU variant     : 0x0
  CPU part        : 0xd03
  CPU revision    : 4

If it’s so easy to remove instructions how come it almost never happens for real?

https://www.nxp.com/docs/en/data-sheet/MC68060UM.pdf

https://en.wikipedia.org/wiki/Jazelle

https://web.archive.org/web/20131109151245/http://developer....

We already have a large number of instructions that are useless. Look at the difference between CISC and RISC.

I think it would be faster to OR the entire string with itself, then finally check the 8th bit though. On Skylake that would cut it to 0.33 cycles per 16 bytes (HSW 1 per 16).

https://github.com/lemire/fastvalidate-utf-8/pull/2

[1] https://lemire.me/blog/2018/05/09/how-quickly-can-you-check-...

The string could have NUL (zero) bytes in between.

That's more or less what std::str::from_utf8 is: it runs UTF8 validation on the input slice, and just casts it to an &str if it's valid: https://doc.rust-lang.org/src/core/str/mod.rs.html#332-335

from_utf8_unchecked nothing more than an unsafe (c-style) cast: https://doc.rust-lang.org/src/core/str/mod.rs.html#437 and so should be a no-op at runtime.

As for the assumption of mostly-ascii, the validation function has a "striding" fast path for ascii which checks 2 words at a time (so 128 bits per iteration on 64b platforms) until it finds a non-ascii byte: https://doc.rust-lang.org/src/core/str/mod.rs.html#1541

Rust’s current implementation of full validation: https://github.com/rust-lang/rust/blob/2a3f5367a23a769a068c3...

I have a vague feeling there’s an even faster path for probably-ASCII out there, but I can’t immediately recall where and am going to bed. Doubtless someone else will answer before I get up.

The core team will be amenable to replacing this algorithm with something faster presuming it’s still correct.

Having that as a 3rd party crate would make complete sense however.

For example, valid utf-8 must always use the shortest possible sequence or it's invalid. Validator must check against decoding invalid sequences.

example of invalid sequence:

    0xF0 0x80 0x80 0x8A

The first is to classify each byte by type, using the highest 4-5 bits. The types are:

ASCII

continuation

initial byte of:

   2 

   3 

   4-byte sequence

The next task is to check for overlongs. These are just bitfields in the first or second bytes which should be nonzero, and they can be checked at least two ways. One is masking and checking for any nonzero bits, based on a lookup table of masks. Another is comparison, based on the idea that any 1 bits in the bitfield of interest will make the byte larger than all 0's (the higher-order bits are fixed). Both of these methods assign checks on a per-length basis, using a lookup table from the highest 4 bits. Longer sequences also check the second byte in similar fashion.

In the end we basically have bitmaps of each type, and we check that they don't intersect and that their union covers the range. The code is a bit complicated by carrying over the previous range so that sequences that span registers will still get checked.

There is no sense of "validator" in which an expression that accepts overlong sequences could be called a UTF-8 validator.

nabla9 likely knows this, but for those wondering: utf8 can’t contain overlong encodings (https://en.m.wikipedia.org/wiki/UTF-8#Overlong_encodings), but need not use precomposed characters (https://en.m.wikipedia.org/wiki/Precomposed_character) whenever possible (another way in which a shorter sequence is possible)

* \xc0\x9f (overlong U+001F)

* \xed\xa0\x81 (surrogate)

    #include <stdbool.h>
    #include <string.h>
    #include <stdio.h>
    #include "simdutf8check.h"
    
    int
    main(int argc, char *argv[])
    {
        const char euro[] = "\xe2\x82\xac";
        const char eurolong[] = "\xf0\x82\x82\xac";
    
        bool valid = validate_utf8_fast(euro, sizeof euro);
        printf("validate_utf8_fast(euro): %d\n", valid);
    
        valid = validate_utf8_fast(eurolong, sizeof eurolong);
        printf("validate_utf8_fast(eurolong): %d\n", valid);
    
        return 0;
    }

No. I think the implementor of Factor's unicode support originally did that but it turns out to not be useful:

* it blows up memory usage for ASCII and BMP (4 bytes per codepoint versus 1~3)

* this also has impact on CPU caches, lowering the average amount of data you can fit in your cache and work on

* it requires a complete conversion of incoming ascii and utf8 data (which only get more and more common as time goes on) rather than just a validation

* and because Unicode itself is variable-length (combining codepoints) it's not actually helpful when you're trying to properly manipulate unicode data

The only "advantage" of representing strings as codepoint arrays is that you get O(1) access to codepoints which is a terrible idea you should not encourage.

UTF-32 internal encoding makes some manipulations very slightly easier, but not enough to matter in the long run, and it encourages bad habits. If you don't need the O(1) access thing for backwards compatibility reasons, don't bother.

[0] not that that's always the case, the navajo alphabet can have both ogonek and acute on the same latin base character

> it blows up memory usage for ASCII and BMP (4 bytes per codepoint versus 1~3)

Python 3.3+, I believe, looks at the string and chooses ASCII/UCS-2/UCS-4 based on the character that takes the highest amount of bytes [1]. Elixir uses UTF-8 for strings (but you can get the codepoints easily), whereas Erlang uses the list of unicode ints style.

[1] https://www.b-list.org/weblog/2017/sep/05/how-python-does-un...

If by "arrays of codepoints" you mean "each element of the array is a single codepoint", then you get O(1) indexing regarding codepoints, but may use up to 4x the memory as the variable-length encoding.

I see strings larger than that all the time, and care about using low RSS. YMMV.

Luckily not. If you absolutely must deal with legacy encodings, feed them through a conversion pass beforehand.

1. Standard ALUs on modern processors are 64-bits at a time. So right there, you're 8x faster on a per-byte basis.

2. He's using vectorized operations, so he can work with 128-bits, 256-bits (or potentially even 512-bits on high-end processors like Skylake-X). So 16x, 32x, or 64x at a time per operation.

3. Modern processors are super-scalar with multiple ALUs and multiple execution ports. I forget what the precise theoretical limit is, but Intel AND AMD machines can execute something like 4 or 5 operations per clock, depending on circumstances.

That assumes that all operations have been decoded into micro-ops (uops), they fit inside the uop cache (think of a uop cache as a L0 cache: beyond even the L1 cache), that they perfectly line up to available execution ports, that your data has no dependencies, and a whole host of other conditions. But its theoretically possible.

---------

In practice: your code will be limited by memory (even L1 cache is slower than the CPU), by decoding speed (not everything fits in the uOp cache, and only loops really benefit from the uop cache), dependencies (a = x + 1. a = a+2. The 2nd instruction depends on the 1st one to execute first, so the two instructions can't be done in parallel / superscalar).

The CPU is pretty good at trying to figure out how to optimally reorder and out-of-order execute your code. But that means that predicting the performance of the CPU is incredibly difficult: you have to keep in mind all of the parts of the CPU while thinking of the assembly code.

He's using vectorized operations to handle 16 bytes at a time, basically:

    __m128i has_error = _mm_setzero_si128();
    __m128i zero = _mm_setzero_si128();
    for (...) {
        __m128i current_bytes = _mm_loadu_si128(src);
        has_error =
          _mm_or_si128(has_error, _mm_cmpgt_epi8(zero,current_bytes));
    }
    return _mm_testz_si128(has_error, has_error);