⟵ 春水煎茶 · 王超的个人博客 算法 | 分类 | 归档 | 订阅 | 关于

基于状态机的 UTF-8 解码方法 (C++)

2023 年 10 月 13 日 ·春水煎茶 · 未经允许，不可转载

最近刚学 C++ 不久，遇到要把 utf8 字节串解码到 unicode codepoint 的问题。 C++ 并没有内置的 unicode 支持， 标准库中用来处理 utf8 编解码的 codecvt_utf8 也在 C++17 中标记了 deprecated 。 社区还是有很多开源解决方案的，比如著名的 simutf 、utfcpp 等， 其中有两个短小有趣的值得一看:

这让我觉得 utf8 的编解码并没有那么复杂，所以自己尝试做了一份:

https://github.com/hit9/simple-utf8-cpp

本文将介绍 utf8 的 编码格式、编码方法 和 我实现的 这个基于状态机的解码方法。

编码格式

从 rfc3629 文档上可以看到 utf8 编码的规则如下:

Char. number range  |        UTF-8 octet sequence
   (hexadecimal)    |              (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

可以看到:

  1. utf8 是变长编码格式，一个 unicode codepoint 可以编码到 1~4 个 utf8 字节。
  2. 连续字节 (continuation byte) 的最高两位都是 10 ，也就是形如 10xxxxxx。
  3. 如果第一个最高位是 0, 也就是形如 0xxxxxxx 的格式的话，整个 codepoint 就是 1 个字节的。
  4. 如果最高的三位是 110, 也就是形如 110xxxxx 的格式的话，整个 codepoint 就是 2 个字节的，需要进一步看连续字节。
  5. 依次类推 3 个字节、4 个字节的情况。

更进一步的格式如下, 其中红色部分表示高位标识 bit，蓝色部分表示数据本身，从中可以看出 codepoint 数字 和 utf8 字节中的每一个 bit 的映射关系：


 bytes | utf8 sequence  | codepoint number
-------+----------------+-------------------------------
   1   | 1st. 0xxxxxxx  | 0xxxxxxx
-------+----------------+-------------------------------
   2   | 1st. 110xxxxx  | 0xxx xxyyyyyy
       | 2nd. 10yyyyyy  |
-------+----------------+-------------------------------
   3   | 1st. 1110xxxx  | xxxxyyyy yyzzzzzz
       | 2nd. 10yyyyyy  |
       | 3rd. 10zzzzzz  |
-------+----------------+-------------------------------
   4   | 1st. 11110xxx  | 000xxxyy yyyyzzzz zzwwwwww
       | 2nd. 10yyyyyy  |
       | 3rd. 10zzzzzz  |
       | 4th. 10wwwwww  |

codepoint 计数

首先，给定一个 utf8 字节串，如果计算出其中有多少 codepoint ?

由于是变长格式，编码长度蕴含于数据之中， 所以，无法直接通过 utf8 字节串的长度来推断对应了多少 codepoint ，只能迭代整个字节串来计算。

观察 编码格式，一个聪明的办法是，计数时只需要忽略连续字节就可以了。

连续字节的特征是，高位 bit 是 10 , 非连续自己的高位一定不是 10。

下面的代码中 c & 0xc0 就是在检查是否为连续字节:

size_t CountCodes(std::string_view s) {
  size_t k = 0;
  for (auto c : s) {
    // 0xc0 = 11000000, 0x80 = 10000000
    if ((c & 0xc0) != 0x80) k++;
  }
  return k;
}

编码方法

考虑如何将单个 codepoint 编码到 1~4 个 utf8 字节, 注意结合 上面的表格:

  1. 当 code <= 0x7f 时，codepoint 形如 0xxxxxxx, 编码后即其自身。

    if (code <= 0x7f) {  // 0xxxxxxx
  s[0] = code & 0xff;
  return 1;
}

  2. 当 code <= 0x7ff 时，codepoint 形如 0xxx xxyyyyyy, 编码时:

    1. 前面的 5 个 bit xxx xx 给到第一个字节的低 5 位，再或上 110, 表示一共有 2 个字节。
    2. 后面的 6 个 bit yyyyyy 给到第二个字节的低 6 位，再或上 10, 属于连续字节。
    if (code <= 0x7ff) {  // 0xxx xxyyyyyy
  s[0] = 0xc0 | (code >> 6);    // 110xxxxx
  s[1] = 0x80 | (code & 0x3f);  // 10yyyyyy
  return 2;
}

  3. 剩下的 3 个字节 和 4 个字节的情况，和上面的分析如出一辙，不再赘述。

在 C++ 中，可以用 u32string 来表达 unicode codepoint 序列，其每个单元的类型是 char32_t。 最终，整体的解码方法:

codepoint 编码到 utf8 的方法 - C++
static size_t inline code_to_utf8(char32_t code, unsigned char* s) {
  if (code <= 0x7f) {  // 0xxxxxxx
    s[0] = code & 0xff;
    return 1;
  }
  if (code <= 0x7ff) { // 0xxx xxyyyyyy
    s[0] = 0xc0 | (code >> 6);    // 110xxxxx
    s[1] = 0x80 | (code & 0x3f);  // 10yyyyyy
    return 2;
  }
  if (code <= 0xffff) { // xxxxyyyy yyzzzzzz
    s[0] = 0xe0 | (code >> 12);          // 1110xxxx
    s[1] = 0x80 | ((code >> 6) & 0x3f);  // 10yyyyyy
    s[2] = 0x80 | (code & 0x3f);         // 10zzzzzz
    return 3;
  }
  if (code <= 0x10ffff) { // 000xxxyy yyyyzzzz zzwwwwww
    s[0] = 0xf0 | (code >> 18);           // 11110xxx
    s[1] = 0x80 | ((code >> 12) & 0x3f);  // 10yyyyyy
    s[2] = 0x80 | ((code >> 6) & 0x3f);   // 10zzzzzz
    s[3] = 0x80 | (code & 0x3f);          // 10wwwwww
    return 4;
  }
  return 0;
}

size_t Encode(std::u32string_view p, std::string& s) {
  size_t j = 0;
  for (auto code : p) {
    auto d = code_to_utf8(code, reinterpret_cast<unsigned char*>(&s.at(j)));
    if (!d) return 0;
    j += d;
  }
  return j;
}

解码方法

解码逻辑是否一样简单呢？不然。

并非所有的字节串都可以解码为合法的 codepoint 序列, 原因有二：

  1. 给到的字节串的可能存在格式错误。
  2. 出于一些安全原因，即使符合 utf8 编码格式，也要遵循最短编码原则。

codepoint 编码到 utf8 是存在唯一结果的。 但是反过来，utf8 字节串解码到 codepoint 时，我们要禁止一些过长的 (overlong) 情况。

举例来说，U+007F 可以编码如下，其中红色的是 utf8 高位标识，蓝色是数据部分：

  • 0x7f = 01111111
  • 0xc1 0xbf = 11000001 10111111
  • 0xe0 0x81 0xbf = 11100000 10000001 10111111
  • 0xf0 0x80 0x81 0xbf = 11110000 10000000 10000001 10111111

虽然，这些字节串都是符合编码规则的，但是，只有最短的 0x7f 是合法的编码。

在这个例子中，看两个字节的情况，事实上，0xc1=11000001 永远不可能成为 utf8 中的第一个字节，因为它一定会导致过长编码问题： 任意一种 2 字节编码结果 11000001 10xxxxxx 一定对应着一个等价的、更短的一个字节的编码结果 01xxxxxx。

对于 2 字节长度的编码结果，第一个字节至少是 0xc2=11000010 才可以, 因为这时的编码结果形如 11000010 10xxxxxx， 数据部分占 8 个 bit, 无法编码为长度为 1 的 utf8 字节串。

因此，编码结果的第一个字节可以是 00..7f , 但不能是 80..c1 (16 进制格式、前后均闭合区间)。 类似的 “空洞” 不止这一处，unicode.org 上有一个表格整理了所有合法的编码情况：

所有合法的 utf8 字节串

接下来，按照这个表格，设计一个 utf8 解码函数，将采用状态机的思路。

定义一个解析过程中的状态码 state :

  • state 0 表示解析成功，同时作为 (解析下一个 codepoint 的) 初始状态
  • state 8 表示解析错误 (过长编码、格式错误)
  • state 1 表示还需等待 1 个 80..BF 的连续字节输入, 才可以解析成功
  • state 2 表示还需等待 2 个 80..BF 的连续字节输入, 才可以解析成功
  • state 3 表示还需等待 3 个 80..BF 的连续字节输入, 才可以解析成功
  • state 4 表示头字节是 E0, 等待 A0..BF 的连续字节输入，再下一次会进入 state 1
  • state 5 表示头字节是 F0, 等待 90..BF 的连续字节输入，再下一次会进入 state 2
  • state 6 表示头字节是 F4, 等待 80..8F 的连续字节输入，再下一次会进入 state 2

可以结合下图的状态标记，来理解这几个状态的设计。其中，相同状态的表格拥有相同的背景色。

utf8 字节串表格的状态标记

状态跳转图如下 (其中没有画出 8 号错误状态，所有意外输入，都跳到 state 8)：

utf8 解码器的状态跳转表

如此一来，decode 函数就非常容易了, 用 switch-case 来写跳转函数就可以。

utf8 解码器状态跳转函数 - C++
static uint32_t inline
decode_next_naive(uint32_t* state, char32_t* code, unsigned char byte) {
  switch (*state) {
    case 0:
      if (byte <= 0x7f) { *code = byte; }
      else if (byte < 0xc2) { *state = 8; }
      else if (byte <= 0xdf) { *state = 1; *code = byte & 0x1f; }
      else if (byte == 0xe0) { *state = 4; *code = 0xe0 & 0xf; }
      else if (byte <= 0xef) { *state = 2; *code = byte & 0xf; }
      else if (byte == 0xf0) { *state = 5; *code = 0xf0 & 0x7; }
      else if (byte <= 0xf3) { *state = 3; *code = byte & 0x7; }
      else if (byte == 0xf4) { *state = 6; *code = 0xf4 & 0x7; }
      else { *state = 8; }
      break;
    case 1:
    case 2:
    case 3:
      if (byte >= 0x80 && byte <= 0xbf)
        { *state -= 1; *code = (*code << 6) | (byte & 0x3f); }
      else { *state = 8; }
      break;
    case 4:
      if (byte >= 0xa0 && byte <= 0xbf)
        { *state = 1; *code = (*code << 6) | (byte & 0x3f); }
      else { *state = 8; }
      break;
    case 5:
      if (byte >= 0x90 && byte <= 0xbf)
        { *state = 2; *code = (*code << 6) | (byte & 0x3f); }
      else { *state = 8; }
      break;
    case 6:
      if (byte >= 0x80 && byte <= 0x8f)
        { *state = 2; *code = (*code << 6) | (byte & 0x3f); }
      else { *state = 8; }
      break;
  }
  return *state;
}

解码函数的实现：

utf8 解码器实现 - C++
size_t DecodeNaive(std::string_view s, std::u32string& p) {
  uint32_t state = 0;
  char32_t code = 0;
  size_t k = 0;
  for (auto c : s) {
    decode_next_naive(&state, &code, c);
    if (state == 8) return 0;  // early fail.
    if (state == 0) p[k++] = code;
  }
  if (state != 0) return 0;
  return k;
}

所有完整的代码实现见： https://github.com/hit9/simple-utf8-cpp 。

最后，再次引用 《通灵芯片》 的话来感叹一句:

有限状态机为何如此有用，其原因之一是它们能识别序列。

（完）

相关阅读:

本文原始链接地址： https://writings.sh/post/utf8

王超 · 2023 年 10 月
原创文章，未经允许，不得转载
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅