A Branchless UTF-8 Decoder
The core of the algorithm shows that UTF-8 is actually big-endian in its ordering of the bits, making it somewhat more difficult to implement efficiently on the usual little-endian machine --- the first byte, at the lowest address, actually contains the <i>most</i> sigificant bits. Had it been the other way around, the final shift would not be length-dependent.<p>Also, none of the compilers I tried at <a href="https:&#x2F;&#x2F;godbolt.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;</a> were able to combine the 4 s[0...3] 8-bit reads into one 32-bit read, which is somewhat disappointing. They generated 4 separate byte-read instructions, one for each s[0..3]. Yes, I know it could be unaligned, but this is x86 where it would still be faster than 4 separate reads. You would need to do this instead (and sacrifice endianness&#x2F;alignment-independence):<p><pre><code>    uint32_t v = *(uint32_t*)s;
    *c  = (uint32_t)(v &amp; masks[len]) &lt;&lt; 18;
    *c |= (uint32_t)((v&gt;&gt;8) &amp; 0x3f) &lt;&lt; 12;
    *c |= (uint32_t)((v&gt;&gt;16) &amp; 0x3f) &lt;&lt;  6;
    *c |= (uint32_t)((v&gt;&gt;24) &amp; 0x3f) &lt;&lt;  0;
    *c &gt;&gt;= shiftc[len];
</code></pre>
We&#x27;re still left with a bunch of shifts, ands, and ors, the purpose of which is to essentially &quot;compact&quot; the 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx bitstring into one 21-bit codepoint by removing the bits in the middle. All the compilers I tried weren&#x27;t so clever as to do this (assuming eax = v from above after masking, and cl = slightly modified shiftc[len]) at any optimisation level:<p><pre><code>    bswap eax
    mov ebx, eax
    and ebx, 00FF00FFh
    lea ebx, [ebx + ebx*2]
    add eax, ebx
    shr eax, 2
    shl ax,4
    shr eax, cl
</code></pre>
I played around with optimising UTF-8 decoding a while ago, and the above resembles one of the fastest and smallest ways to &quot;compact&quot; the 4 bytes into a codepoint.<p>Of course, this bit string manipulation would be much faster and trivial in hardware (essentially rearranging wires), which makes me want a LODSUTF8 instruction that operates like LODSB but reads a whole codepoint instead, and sets CF on error...