32 位寄存器中非零字符的高效 UTF-8 字符长度解码

Question

我在 eax 中存储了一个 UTF-8 字符，稍后在处理过程中，我需要知道这个字符有多少字节组成。

我已经缩小了范围以尽量减少轮班和掩码，想知道我是否在某处遗漏了一些巧妙的技巧？

选项 1：蛮力

    mov     r11, 4      ;   Maximum bytes
    bt      eax, 31     ;   Test 4th MSB
    jc      .exit 
    dec     r11         ;   Lets try 3
    bt      eax, 23     ;   Test 3rd MSB
    jc      .exit 
    dec     r11         ;   Lets try 2
    bt      eax, 15     ;   Test 2nd MSB
    jc      .exit 
    dec     r11         ;   It's straight up ascii (1 byte)
.exit:

注：

我在 eax 寄存器中的积累是错误的，正如大家所指出的。
Margaret 和 Ped7g 都提供了解决方案，我学到的比预期的还要多。

Answer 1

如果您可以假设 correct encoding of the character，您可以简单地检查第一个代码单元中最高零的位置（感谢 UTF-8 的自动同步属性）。

罪魁祸首是对于一个代码单元的代码点，最高位是第 7 位。对于 n 代码单元的代码点，最高位是 7 - n（注意 "discontinuity"）。

假设第一个代码单元在 al.

not al                 ;Trasform highest 0 in highest 1
bsr al, al             ;Find the index (from bit0) of the first 1 from the left
xor al, 7              ;Perform 7 - index
                       ;This gives 0 for single code unit code points
mov ah, 1
cmovz al, ah           ;Change back to 1

请注意，bsr 未针对输入 0 定义，但这只会发生在无效的前导代码单元（值为 11111111b）时。

您可以在 bsr 指令后使用 jz <error handler> 检测无效的 0xff 代码单元。

感谢@CodyGray 指出原始版本的错误。
感谢@PeterCorders 指出执行 7 - AL 的 XOR 技巧。

Answer 2

如果您坚持颠倒字节顺序（出于任何奇怪的原因），您仍然可以简单地扫描设置为 1 的第一位，除以 8 和 +1 以获得字节数。

GetReversedShiftedUtf8BytesCount:
    ; eax = UTF8 code in reversed order, by from LSB
    ; 'É' (c3 89) => eax = 0x0000c389
    bsr ecx,eax
    cmovz ecx,eax   ; needed only for eax = 0
      ; ^ if eax is never 0 on input, this "cmovz" can be removed
    shr ecx,3
    inc ecx
    ret

当您将 char 的第一个字节放入 MSB 时，它将为多字节字符生成第 15、23 或 31 位的数字，对于 7b ASCII，bsr 将生成从 0 到 6 的任何内容。 "div 8" 会直接修复它们，无论哪种方式，它都不在乎。

这个例程实际上应该也适用于有效普通 UTF8 代码。

对于无效以零字节结尾的UTF8代码，它将return错误的字节数（没有零字节）。

当然还有总是也可能有LUT解决方案：

    movzx  ecx,al
    shr    ecx,3
    movzx  ecx,byte [utf8lengthLUT + ecx]  ; +rcx for 64b
    ; ecx = number of bytes or 0 for invalid leading byte value
    ...

utf8lengthLUT:                     ; 32B look-up table for upper 5b of 1st byte
    db     1, 1, 1, 1, 1, 1, 1, 1  ; 00000 - 00111 ; single byte
    db     1, 1, 1, 1, 1, 1, 1, 1  ; 01000 - 01111 ; single byte
    db     0, 0, 0, 0, 0, 0, 0, 0  ; 10000 - 10111 ; not valid leading byte
    db     2, 2, 2, 2              ; 11000 - 11011 ; two bytes code point
    db     3, 3                    ; 11100 - 11101 ; three bytes code point
    db     4                       ; 11110         ; four bytes code point
    db     0                       ; 11111         ; not valid leading byte

我没有调试它，只是尝试用nasm翻译以进行语法检查。我当然也没有介绍它。 :) 看看 bsr 变体的缺点，我怀疑即使在 bsr 受到伤害的 CPU 上，这也会更快。

但是这个以不同的方式处理无效的 UTF8 操作码，而不是检测非零 MSB 和 returning 数+1（对前导字节内容不敏感），它将正确解码前导字节信息和 return 0 当前导位错误时。但是正确的前导位和不正确的第 2+ 个字节（如 c3 00）仍将 return 2，而第一个变体 returns 1 在这种情况下。

（可以只使用 16B LUT table，如果您不关心无效的 11111 前导字节信息，您将把它作为 4 字节代码点）

顺便说一句，有一些 i18n 库（开源），可以做所有这些事情，比如验证 utf8 输入、修复无效输入、计算字符数等等......其中一些已经存在了十多年......但仍会收到错误报告和修复。这是一种微妙的暗示，正确地编写这些东西是多么困难（没有将应用程序暴露给某些输入数据漏洞利用）。 :)

（加上考虑有多少（修复）编辑收到了这两个答案...:)）

还有一个离题建议：如果你想用 PHP 写东西，应该处理 UTF8 输入数据（不是来自可信来源，但即使来自可信来源），尤其是如果那些输入数据来自 GET/POST 响应...只是不要自己输入。绝不。为那个得到一些框架。 :)

32 位寄存器中非零字符的高效 UTF-8 字符长度解码

Efficient UTF-8 character-length decoding for a non-zero character in a 32 bit register

assembly

x86-64

utf-8

nasm

micro-optimization