Skip to main content
overcache

从 UTF-8 说开去

最近实现一个 cache 系统, 要求对 cache 的大小做限制. 但是 JavaScript 没有 sizeof 函数, 咋整? 只能自己实现一个了, js 里:

  • number: 规范规定是 double float 类型, 所以是 8 个字节
  • string: 规范只说了是 16 bit EcmaScript, 引擎可以用 ucs-2 编码, 也可以用 utf-16 编码 来源

事实上, ecmaScript 只对 number/string 做了规范, 至于其他类型占用多少内存空间, 无从得知. 我们只能毛估估做个假设吧:

  • boolean 虽然 1 bit 就够了, 但是从内存寻址的角度看, 应该会占用一个字节.
  • undefined/null 算一个字节吧...
  • function 算 toString() 后的字符串大小吧? 虽然肯定不止
  • symbol 也用 toString() 后的字符串大小来衡量吧
  • object 可枚举的 key(string) 的大小加上 value 的大小
  • array 所有项的大小之和

在这些假设的前提下, 找出 string 占用的内存大小是关键的一步, 这就要求搞清楚 utf-16 的编码机制, 扯到 utf 的编码, 就不能绕开字符集 Unicode 了.

Unicode 字符集

字符集是表示字符的一个集合, 比如 ascii/gb2312/big5/unicode 等, 其中 ascii 字符集只包含拉丁字母/常见的标点符号/以及一些控制字符. gb2312 是简体中文的字符集, 除了是 ascii 的超集之外, 还包含了众多的汉字. big5是包含繁体中文的一个字符集合, 用于台湾地区.

如果我们只有 gb2312 字符集, 那将无法显示繁体中文(准确地说, 是计算机无法知道某些二进制表示什么字符. 知道->显示的过程, 还需要字形的配合), 反之亦然. 所以我们的操作系统一般都预置了很多种字符集, 以显示地球上的不同文字. Unicode 是一个超大的字符集, 包含了地球上所以的文字/表情/以及符号. 如果所以人都使用 unicode, 那么计算机里只要装一份字符集就好.

Unicode 把每 2^16 个字符分一个集合, 称为一个平面(plane), 目前一个有 17 个平面. 所以 Unicode 一共可以表示 1114112 个字符, 每个字符都有自己的序号, 从0-1114112, 称之为码点(codepoint), 目前只用了不到 14 万的字符(link). 第一个平面称为基本平面(BMP: Basic Multilingual Plane), 常见的字符都在这个平面, 其他平面也有自己的名称, 如图:

unicode_planes

字符编码

在多种字符集并行存在的情况下, 如果地球上某处有人给你发了一份文件, 计算机如何知道该用哪种字符集来显示呢?

首先, 字符是人类的符号, 计算机只能认识0/1. 所以对于一个文件, 计算机采用什么字符显示, 那要看这个文件的二进制表示是什么, 不同的字符集有不同的二进制表示, 知道了文件的二进制表示情况, 大概就知道了它用什么字符集.

而字符集到二进制的过程, 称为 encoding, 即字符编码.

ANSI 编码

对于 ASCII 字符集来说, 由于它只有 128 个字符, 所以 7 bit 就能够表示完全了. 但是 ANSI 编码还是用了一个字节来表示一个ascii字符, 因为计算机寻址/指令等原因, 2 的幂次方的数据处理起来更高效. 所以 ascii 编码就相当简单, 每个字节的最高位全是 0. 计算机打开一份文本, 看到所有的字节都是 0 开头, 就用 ascii 字符显示吧, 八九不离十.

UTF-32 编码

unicode 也可以按照这个模式进行编码, 因为 2^21 就能表示完全该字符集中的字符, 用 21 bit 比特就够了, 三个字节24bit绰绰有余. 但如前文提到的, 计算机更合适处理 2 的幂次方的数据, 所以用4个字节对一个 unicode 字符进行编码(如果还想不通, 可以看看我们的计算机体系, 从 8 位计算机, 到 16 位, 32 位. 64位, 为啥没有24位,40位,48位?). 这种 unicode 的编码称为 utf-32 编码, 够简单粗暴但不完美. 采用这种编码的文件, 即使是全部由 ascii 字符组成, 占用的空间是用 ascii 编码的4倍.

所以 utf-32 编码没有被广泛使用.

UTF-16 编码

unicode 还有一个 utf-16 的编码方法, 它不完全定长. 考虑到:

  • 基本平面有 2^16 个字符, 那么两个字节存储就够了
  • 其他平面一共有 2^16x16 = 2^20 个字符, 四个字节不用找了

这样可行吗? 还不行, 如果四个字节摆在计算机面前, 那么该解读为2个基本平面的符号还是1个其他平面的符号, 计算机才不会后悔莫及呢? 它没办法解读. 所以聪明的人想到了一个办法:

  • 在基本平面还有一些码点没有分配.
  • 其他平面的一个字符的码点需要4个字节的来表示, 如果能把这4个字节映射到基本平面的空码点上就好了.

如果能做到, 那么计算机看到4个字节的时候, 两个字节两个字节地看:

  • 如果算出来码点都在基本平面的非空位上, 那么这四个字节就是两个基本平面的字符
  • 如果前两个字节是算出来的码点位于空位, 那么它肯定是其他平面字符的表示的一部分, 而另一部分就在接下来的那两个字节中. 那么把这四个字节反映射回去, 就得到了原来的码点.

问题变成了: 怎么做这个映射?

  • 其他平面的所有字符总数是 2^20, 码点从 0xffff 开始, 到 17x2^16 - 1结束. 要用 20 bit 表示他们, 先把码点规整为从 0 开始. 即字符的码点要减去 0xffff
  • 然后把这20bit拆为高位的 10bit 和地位的 10bit, 各需要 1024 各位置来存放. 高位的10bit是 (c-0xffff)>>10, 地位的10bit是 (c-0xffff)&0x3ff
  • 在基本平面找4个字节的位置来存放高10bit, 就找 D800-DBFF 吧, 那么高位在基本平面里的容身之所(代理码点)就是 (c-0xffff)>>10 + 0xD800
  • 再找4个字节的位置来放低10bit, DC00-DFFF 就是你了. 那么代理码点是 (c-0xffff)&0x3ff + 0xDC00

和相反的操作一起, 构成了 utf-16 的编码方法, 其中 D800-DBFF 称为 high surrogate, DC00-DFFF 称为 low surrogate, 如图:

bmp

山寨的可变编码: UTF-B

UTF-16 的编码方法以及比 utf-32 节省很多空间了, 对于纯 ascii 组成的文本来说, 空间占用少了 50%. 但还是不够省. 拉丁文本的占用空间如果能跟 ascii 编码一样就好了, 可能吗? 我们试着构造一个山寨的 UTF-8 编码, 按照华强北的命名规律, 我们的编码方式应该叫 UTF-B

UTF-B 是变长的编码, 一个字符可能用一个字符表示, 也可能用多个字符表示. 因为长度不固定, 所以需要告诉计算机: 当前读到的字节是单独的一个字符, 还是字符的某一部分, 它的其他部分在哪里. 尝试设计如下:

ascii 字符128个, 一个字节就可以表示了. 而且它的最高的bit位是0. 我们灵光一现(别管怎么灵光的好吧): 是不是可以用最高位做文章呢?:

  • 一个字节的最高位是0, 表示这是基本平面的前128个码点之一, 也正好是ascii之一. 可以表示 2^7 个码点, 范围是 0-0x007f
  • 一个字节的最高位是1, 表示它和后续的一个字节组成一个码点, 可以表示 2^15 个码点.
  • 一个字节的最高位是11, 表示它和后续的两个字节组成一个码点, 可以表示 2^22 个码点, 到这里, 所有的码点都能得到表示了.

这样有个问题, 一个字节的高位是 11, 那它是可能是2-3个字节的开始, 这就有歧义了. 改进一下, 用 0 把他们区分开:

  • 一个字节的最高位是0, 表示这是基本平面的前128个码点之一, 也正好是ascii之一. 可以表示 2^7 个码点
  • 一个字节的最高位是10, 表示它和后续的一个字节组成一个码点, 可以表示 2^14 个码点
  • 一个字节的最高位是110, 表示它和后续的两个字节组成一个码点, 可以表示 2^21 个码点

这么搞貌似没问题了. 后续的这几个字节需要做格式上的规范吗? 文件并不是只能从头开始读的, 如果从文件中间的某个字节开始读, 如果读到的字节是 1100 1010, 那么这个字节一定表示和后续的两个字节组成一个码点吗?

不一定, 它还可能是组成码点的某个中间字节! 为了区分一个字节是火车头还是火车中间车厢, 还需要约定一下: 其他车厢不准长得跟火车头一样! 要不你们统一以 1110 开始吧...到了这一步, 计算机随便读到一个字节, 都能分辨出这个字节的作用了. 现在规则变成了:

  • 一个字节的最高位是0, 表示这是基本平面的前128个码点之一, 也正好是ascii之一. 可以表示 2^7 个码点
  • 一个字节的最高位是10, 表示它和后续的一个字节 1110xxxx 组成一个码点, 可以表示 2^10 个码点, 有效载荷 10bit
  • 一个字节的最高位是110, 表示它和后续的两个字节 1110xxxx 1110xxxx 组成一个码点, 可以表示 2^13 个码点, 有效载荷 13bit

这样表示的话还有一部分码点没办法表示, 所以再加一条规则: 四个字节表示一个码点. 非火车头的车厢统一以 11110 开始吧:

  • 一个字节的最高位是0, 表示这是基本平面的前128个码点之一, 也正好是ascii之一. 可以表示 2^7 个码点
  • 一个字节的最高位是10, 表示它和后续的一个字节 11110xxx 组成一个码点, 可以表示 2^9 个码点, 有效载荷 9bit
  • 一个字节的最高位是110, 表示它和后续的两个字节 11110xxx 11110xxx 组成一个码点, 可以表示 2^11 个码点, 有效载荷 11bit
  • 一个字节的最高位是1110, 表示它和后续的三个字节 11110xxx 11110xxx 11110xxx 组成一个码点, 可以表示 2^13 个码点, 有效载荷 13bit

就算我们用了1-4个字节表示码点, 还是没能把所有的码点表示完全, 以上编码能表示的码点总数还不到 2^15 个: 2^7 + 2^9 + 2^11 + 2^13 < 2^13 x4 = 2^15. 原因在于, 非火车头的车厢作为载荷的主体, 浪费了太多 bit 来表示他们的身份, 把这部分bit和火车头对调一下, 降低火车头的有效载荷提高整体的有效载荷:

  • 一个字节的最高位是0, 表示这是基本平面的前128个码点之一, 也正好是ascii之一. 可以表示 2^7 个码点
  • 一个字节的最高位是110, 表示它和后续的一个字节 10xxxxxx 组成一个码点, 可以表示 2^11 个码点, 有效载荷 11bit
  • 一个字节的最高位是1110, 表示它和后续的两个字节 10xxxxxx 10xxxxxx 组成一个码点, 可以表示 2^16 个码点, 有效载荷 16bit
  • 一个字节的最高位是11110, 表示它和后续的三个字节 10xxxxxx 10xxxxxx 10xxxxxx 组成一个码点, 可以表示 2^21 个码点, 有效载荷 21bit

如此我们确定了基本的编码规则, 但还有一些细节需要处理:

  • 单字节可以表示 [0, 0x7f]这些码点. 这和 UTF-8 一致
  • 两个字节有可以表示 2^11 个码点, 范围从"单字节能表示的最大码点的后一个码点"开始, 码点范围也就是 [0x80, 0x80+2^11-1] = [0x80, 0x87F]
  • 三个字节可以表示 2^16 个码点, 范围从"双字节能表示的最大码点的后一个码点"开始, 码点范围也就是[0x880, 0x880+2^16-1] = [0x880, 0x1087F]
  • 四个字节可以表示 2^21 个码点(实际上已经用不了那么多了), 范围从"三字节能表示的最大码点的后一个码点"开始, 到 Unicode 的最后一个码点结束, 也就是[0x10880, 0x10FFFF]

UTF-B 的编解码算法

确定了所有的编码规则, 我们确定编码过程, 对于某个码点 c, encode(c):

  • 确定他需要的字节数
    • 如果 c <= 0x7F, 一个字节
    • 0x80 <= c <= 0x87F, 两个字节
    • 0x880 <= c <= 0x1087F, 三个字节
    • 0x10880 <= c, 四个字节
  • 确定字节数后, 做数据的规整, 码点根据相应的字节数, 减去0x80/0x880/0x10880等求得偏移量, 得到偏移后的码点表示 c'
  • 因为字节数确定了有效 bit, 设为 n 位. 把 c' 用 n 位二进制表示, 不足部分用前导 0 补齐. 放入字节的有效载荷的位置中.

解码过程, decode(bytes):

  • 由最高字节的最高 bit, 得到该码点一共由 m 个字节表示的信息, 也就得到了有效 n 位 bit 的信息
  • 算出这 n 位有效 bit 组成的二进制数的对应值, 也就得到了矫正后的码点 c' 的值.
  • c' 的值加上相应的偏移, 得到了码点 c

如果 const bytes = encode(c) 那么有 c === decode(bytes), 反之亦然

找个具体的例子, 以汉字'你'为例. 编码过程如下:

  • '你'字的码点是 0x4F60, 它落在了3个字节的范围
  • 用它的码点减去"三字节码点的第一个码点 0x880", 得到'你'在三字节里的偏移量: 0x4F60 - 0x880 = 0x46E0, 用前导 0 补齐 16 bit 的有效载荷. 得到 0100 011011 100000
  • 填充到3字节的有效bit中, 得到最终的表示: 11100100 10011011 10100000 , 即 0xE49BA0

与之相反的解码过程, 对于三个字节的数据 0xE49BA0:

  • 首字节高位有3个bit 的 1 , 表示这是三个字节组成的一个码点
  • 取出有效 bit 位: 0100 011011 100000 === 0x46E0
  • 加上"三字节表示的第一个码点 0x880"的偏移量, 即 0x46E0 + 0x880 = 0x4F60, 也就得到了'你'的码点

这么看的话, 我们的 UTF-B 编码应该很完美了. 看看我们实现的和正宗的 UTF-8 一不一样.

查看汉字'ni'的 UTF-8 编码: echo '你' | hexdump, 得到

0000000 e4 bd a0 0a
0000004

最后一个字节是结束符, '你'的 UTF-8 编码为: e4 bd a0, 二进制为: 1110 0100 10 111101 10 100000

除了 hexdump, 也可以用 unibits 来查看字符的编码结果:

unibits

跟我们的实现有所出入, 看看他的实现.

UTF-8 编码

utf-8

在真正的 UTF-8 编码里, 汉字'你' 的编码过程如下:

  • 找到它的码点: '你'.codePointAt(0), 得到 20230, 即 0x4F60 === 0b100111101100000
  • 它落在了3个字节的范围, 用前导0 减去偏移 2176 得到矫正码点 c': 18054, 0b100011010000110
  • 落在了三个字节的范围, 用前导 0 补齐 16 bit的有效载荷. 得到 0b 0100 111101 100000
  • 填充到3字节的有效bit中, 得到最终的表示: 1110 0100 10 111101 10 100000

解码过程如下:

  • 由高字节的 1110 可知, 这是一个由3个字节表示的码点
  • 取出有效 bit, 即 0b 0100 111101 100000, 得到码点值: 20230
  • 加上三字节的偏移 2176, 得到码点 c: 20230

我们的 UTF-B 编码和它的区别在于: 为了尽可能多的用尽可能少的字节表示码点, 多了一步偏移量的操作.

  • 两字节表示的码点, 同样是 11 bit 的有效载荷. 它表示 [0x80, 0x7FF] 的码点, 数量是 1920. 比我们的编码少了 128
  • 三字节表示的码点, 16 bit 的有效载荷. 它表示 [0x800, 0xFFFF] 的码点, 数量是 63488. 比我们的编码少了 65536 - 63488 = 2048
  • 四字节表示的码点, 21 bit 的有效载荷. 它表示 [0x1 0000, 0x10 FFFF] 的码点, 数量是 1048576. 比我们的编码多了 1048576-1046400 = 2176

表示的码点数目是对的上的, 但是我目前不清楚他们为什么不用满所有的有效 bit? 比如两字节, 2^11 的空间里只使用了后半部分的 1920 个.

可能是为了节省计算吧? (知道原因的读者一定要留言告诉我!)

题外话: Little endian / Big endian / BOM

对于多字节的编码方式, 不同的字节顺序有不同的二进制编码结果. 比如'你'的码点用 32 bit 来表示的话是: 00000000 00000000 01001111 01100000

  • 如果是开头的字节表示高位, 也就是如 00000000 00000000 01001111 01100000 的形式, 称为 Big endian
  • 如果是开头的字节表示地位, 也就是如 01100000 01001111 00000000 00000000 的形式, 称为 Little endian

wiki_be_le

所以多个字节的编码, 其实都要确定字节序, UTF-32BE/UTF-32LE, UTF-16BE/UTF-16LE:

be_le

所以计算机知道一个文件的编码还不够, 它还要知道这个编码是 LE 还是 BE. 聪明的人想到一个办法, 在一个文件的前几个字节把这些信息告诉计算机, 这些字节称为 Byte Order Marks (BOM):

BOM

说好的 sizeof 去哪了

为了 sizeof, 还得再聊聊 UCS-2 编码, UCS-2 编码是一个已经废弃的编码(或者说已经被合并到 UTF-16), 它用两个字节表示码点, 所以只能表示 Unicode 中的基本平面的码点. 按照这篇文章, 很多 JavaScript 引擎, 应该都是用 UTF-16 对字符串进行编码, 但对外的接口却表现得他们是用 USC-2 一样. 比如字符串str = 'a😀', 它明明是两个字符, 码点分别是 0x0061 和 0x1F600, 但是 str.length === 3 // true, 因为笑脸是基本平面以外的码点, 被映射到了 surrogate , 一共占用4个字符, 也就是 2x16. 规范里规定的字符是 16 bit, 好了, 长度是 3 无疑.

不仅 String.length, 大部分字符串的 API 都可能和你预期的结果不一致. 如果一致, 那说明字符串里的字符都是基本平面里的. ES6虽然可以使用 for (let char of str) {} 来正确循环字符串, 但 str.length 为了保持兼容, 还是一个"不准确"的结果, 所以求长度, 只能曲线救国用 Array.from(str).length

话说回来, str.length 的这个特性, 反而让 sizeof 变得简单. 还是以 str = 'a😀' 为例, 如果是 str.length 返回 2, 那么我们还得一个个去判断字符的码点, 基本平面内的码点占用两个字节, 其他平面占用4个字节. 但是 str.length 返回了 3 , 因为它忠于规范(string 是 16bit), 所以 str 的内存占用是 length * 2byte = 16bit*3 = 6 byte.

// fixme: 一下方法如果处理存在环形结构的数据(比如双向链表), 会无法结束导致栈溢出
// fixme: 还很不精确

function sizeof (item) {
  let totalSize = 0
  const helper = (item) => {
    if (Number.isNaN(item) || item === null || item === undefined ) return 1
    if (typeof item === 'number') return 8
    if (typeof item === 'boolean') return 1
    if (typeof item === 'string') return item.length * 2
    if (typeof item === 'function') return item.toString().length * 2
    if (typeof item === 'symbol') return item.toString().length * 2
    if (Object.prototype.toString.call(item) === '[object Map]') {
      return helper(Array.from(item.entries()))
    }
    if (Object.prototype.toString.call(item) === '[object Array]') {
      return item.reduce((sum, cur) => sum + helper(cur), 0)
    }

    return helper(Object.entries(item))
  }
  totalSize += helper(item)
  return totalSize
}