UTF-8 编解码实现

2019-07-04 ⏳2.3分钟(0.9千字) 🕸️

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

在开始之前，我们先简单回顾一下 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 指针，此处备份一下 */
  /* 汉字「吕」的编码是 `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);
      }

      /* 最终 s 最初指向的区域存有 11100000, 10010101, 10010000 */
      return nc;
    }
  }
  return -1;
}

到此，代码就分析完了。你看懂了吗？