UTF-8 编解码演算法赏析

我们在前文《UTF-8往事》中提到，Ken 和 Rob 用一个晚上就实现了 UTF-8 编解码的演算法。代码非常精炼，很值得一读，分享给大家。

如果你对 UTF-8 编码不熟悉，请先阅读

吕海涛：UTF-8 往事?

zhuanlan.zhihu.com

在开始之前，我们先简单回顾一下 UTF-8 的编码规则。

UTF-8 编码回顾

这是 UTF-8 编码规则表：

/* Bytes Bits Hex Min Hex Max Byte Sequence in Binary */ /* 1 7 00000000 0000007f 0vvvvvvv */ /* 2 11 00000080 000007FF 110vvvvv 10vvvvvv */ /* 3 16 00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv */ /* 4 21 00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv */ /* 5 26 00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv */ /* 6 31 04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv */

第一列表示编码所需位元组数，第二列为能表示的 Unicode 的最大二进位位数，第三列和第四列为能表示的 Unicode 范围，最后一列表示编码后的位元组布局。把编码中字母 v 表示的部分连接起来就是对应的 Uniocde 编码。

还是举一下前文的例子。汉字「吕」的 Unicode 编码是 U+5415，对应二进位为 0101010000010101，总共有 15 位。因为两位元组最多表示 11 位，三位元组最多表示 16 位，所以使用三位元组编码。对应二进位拆成（从低位到高位）三部分，分别是 0101, 010000, 010101，再拼上编码前缀得到 11100101, 10010000, 10010101，对应十六进位为 0xe5, 0x90, 0x95，这就是汉字「吕」的 UTF-8 编码。

现在我们开始读 c 代码。理解代码的关键是理解数据结构。

数据结构

Ken 引入一个 Tab 列表。前面说的编码规则表一共有六条，每条一个 Tab。每个 Tab 包含五个栏位。其中 lmask 和 lval 最简单，对应所能表示的 Unicode 的最大值和最小值。Tab 所在的行号代表表示该范围 Unicode 所需要的位元组数。剩下的 cmask, cval 和 shift 则没那么容易理解了。

还是使用汉字「吕+U5415」讲解。它的 UTF-8 编码是 11100101, 10010000, 10010101。解码的时候，我们先读到第一个位元组 11100101，这时演算法需要判后面还有几个位元组。判断的依据则是当前位元组从高位开始连续 1 的个数。对于 11100101 而言，显然其高位连续 1 的数量为 3，但这个事情对于计算机就没有那么「显然」了。Ken 引入两个辅助数字 cmask = 11110000 和 cval = 11100000，让计算机判断 11100101&cmask == cval 是否相等。如果相等，则证明该位元组的高四位一定是 1110。

cmask 和 cval 取值规则非常简单。将 UTF-8 首位元组的 vvv 部分置 0 就得到 cval。将 cval 最高位的 0 置 1 就得到了对应的 cmask。以四位元组编码为例，首位元组为 11110vvv，vvv 置 0，得到对应的 cval 为 11110000，也就是 0xf0；将 11110000 的第四位置 1，得到对应了 cmask 为 111110000，也就是 0xf8。其他的依此类推。

shift 是最不容易理解的。我们放在下面分析 UTF-8 编码演算法的时候再讲。

数据结构代码如下：

typedef struct { int cmask; int cval; int shift; long lmask; long lval; } Tab;

static
Tab tab[] =
{
0x80, 0x00, 0*6, 0x7F, 0, /* 1 byte sequence */
0xE0, 0xC0, 1*6, 0x7FF, 0x80, /* 2 byte sequence */
0xF0, 0xE0, 2*6, 0xFFFF, 0x800, /* 3 byte sequence */
0xF8, 0xF0, 3*6, 0x1FFFFF, 0x10000, /* 4 byte sequence */
0xFC, 0xF8, 4*6, 0x3FFFFFF, 0x200000, /* 5 byte sequence */
0xFE, 0xFC, 5*6, 0x7FFFFFFF, 0x4000000, /* 6 byte sequence */
0, /* end of table */
};

弄清楚了数据结构，我们开始看演算法。

解码演算法

解码演算法就是将 UTF-8 位元组序列转化成 Unicode。代码使用 wchar_t 表示 Unicode。在我的 Mac 上一个 wchar_t 占四个位元组。代码请看注释。依然使用「吕+U5415」的 UTF-8 编码 11100101, 10010000, 10010101 进行讲解。

/* s 指向 UTF-8 位元组序列，n 表示位元组长度 */ /* p 指向一个 wchar_t 变数 */ /* mbtowc 对 s 指定的位元组进行解码，得到的 Unicode 存到 p 指向的变数 */ int mbtowc(wchar_t *p, char *s, size_t n) { long l; int c0, c, nc; Tab *t;

if(s == 0)
return 0;

nc = 0;
if(n <= nc)
return -1;

/* c0 保存第一个位元组内容，后面会移动 s 指针，此处备份一下 */
/* 汉字「吕」的 UTF-8 编码是 `11100101`, `10010000`, `10010101` */
/* 此时 l = c0 = 11100101 */
c0 = *s & 0xff;
/* l 保存 Unicode 结果 */
l = c0;

/* 根据 UTF-8 的表示范围从小到大依次检查 */
for(t=tab; t->cmask; t++) {
/* nc 以理解为 tab 的行号 */
/* tab 行号跟这个范围内 UTF-8 编码所需位元组数量相同 */
nc++;

/* c0 指向第一个位元组，不会变化 */
/* l 在 n == 1 和 n == 2 时左移 6 位两次 */
/* 到 nc == 3 时才会进入该分支 */
/* 此时的 l 已经是 11100101+010000+010101 了 */
if((c0 & t->cmask) == t->cval) {
/* lmaxk 表示三位元组能表示的 Unicode 最大值 */
/* 使用 & 操作，移除最高位的 111 */
/* 所以 l 最终为 00000101+010000+010101 */
/* 也就是 l = 0x5415，对应 Unicode +U5415 */
l &= t->lmask;

if(l < t->lval)
return -1;

/* 保存结果并反回 */
*p = l;
return nc;
}

if(n <= nc)
return -1;

/* s 指向下一个位元组 */
s++;
/* 0x80 = 10000000 */
/* UTF-8 编码从第二个位元组开始高两位都是 10 */
/* 这一步是为了把最高位的 1 去掉 */
c = (*s ^ 0x80) & 0xFF;
/* n == 1 时 */
/* c = 00010000 */
/* n == 2 时 */
/* c = 00010101 */

/* 0xc0 = 1100000 */
/* 这一上检查次高位是否为 1，如果是 1，则为非法 UTF-8 序列 */
if(c & 0xC0)
return -1;

/* c 只有低 6 位有效 */
/* 根据 UTF-8 规则，l 左移 6 位，将 c 的低 6 位填入 l */
l = (l<<6) | c;
/* n == 1 时 */
/* l 的值变成 11100101+010000 */
/* n == 2 时 */
/* l 的值变成 11100101+010000+010101 */
}
return -1;
}

解码演算法讲完了。继续说编码演算法。

编码演算法

编码演算法就是把 Unicode 转换成 UTF-8 位元组序列。还是以汉字「吕+U5415」为例。

/* wc 存有一个 Unicode */ /* s 指向存放 UTF-8 的内存 */ /* wctomb 返回最终 UTF-8 编码的位元组长度 */ int wctomb(char *s, wchar_t wc) { long l; int c, nc; Tab *t;

if(s == 0)
return 0;

/* l = wc = 101010000010101 */
l = wc;
nc = 0;
/* tab 每一行表示的 Unicode 的范围是递增的 */
for(t=tab; t->cmask; t++) {
nc++; /* 记录行数，也就是位元组数 */
/* 找到第一个可以表示的 Tab */
/* 对于「吕+U5412」nc == 3 */
if(l <= t->lmask) {
/* c->shift = 2 * 6 */
/* c->cval = 11100000 */
c = t->shift;
/* UTF-8 共需要 3 个位元组 */
/* 第 2 个和第 3 个位元组各有 6 个有效位 */
/* 所以将 l 右移 2 * 6 位得到的结果需要存到第一个位元组 */
/* 首位元组高 4 位还要存储后续位元组长度标识 */
*s = t->cval | (l>>c);

/* 处理剩余位元组 */
while(c > 0) {
c -= 6;
/* s 依次指向下一个位元组 */
s++;
/* 0x3f = 00111111 */
/* 0x80 == 10000000 */
/* c == 0 时，取 l 的低 6 位并将其高两位置成 10 */
/* 此时 s 指向的位置存有 10010101 */
/* c == 1 时，取 l 的次低 6 位并将其高两位置成 10 */
/* 此时 s 指向的位置存有 10010000 */
*s = 0x80 | ((l>>c) & 0x3F);
}