首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

UTF-8 为什么要这么设计

  •  2
     
  •   Chingim · 310 天前 · 4163 次点击
    这是一个创建于 310 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天想通过 自己设计一个 Unicode 的 编码 来了解字符编码, 结果和真正的 UTF-8 对比, 发现有一些出入, 搜索不到相应的信息, 所以有了这个小小的疑问, 不知道 UTF-8 是一开始就设计成这样还是逐步演变成这样的?

    utf-8 是字符集 unicode 的一种不定长的编码格式, 一个 code point 会用 1-4 个字节表示, 具体用多少字节取决于 codepoint 落在哪个区间.

    它具体的编码规则是(来源):

    以汉字严为例,演示如何实现 UTF-8 编码。 严的 Unicode 是 4E25 ( 100111000100101 ),根据上表,可以发现 4E25 处在第三行的范围内( 0000 0800 - 0000 FFFF ),因此严的 UTF-8 编码需要三个字节,即格式是 1110xxxx 10xxxxxx 10xxxxxx。然后,从严的最后一个二进制位开始,依次从后向前填入格式中的 x,多出的位补 0。这样就得到了,严的 UTF-8 编码是 11100100 10111000 10100101,转换成十六进制就是 E4B8A5。

    但是为什么 UTF-8 不用完所有的有效 bit 呢?

    • 拿上图的两个字节来说, 第一个字节有 5 个 x, 第二个字节 6 个 x, 11 bit 的有效位, 完全可以表示 2^11=2048 个码点, 但 UTF-8 只用来表示 [0x80, 0x7ff] 这个区间(一共 1920 个)的码点, 低位的 128 个值都被浪费了: 110 00000 10 000000 ~ 110 00001 10 111111 这些值都空着.
    • 再看三个字节: 一共 16 bit 的有效载荷, 可以表示 2^16 = 65536 个码点, 但 UTF-8 也只用了其中的 63488 个, 低位的 2048 个值空着.

    UTF-8 是为了省空间而设计的, 是要把这些有效位塞满的吧? 两个字节就把所有的值用上:

    • 最小值 110 00000 10 000000 有效 bit 的值是 0, 加上 0x80 的偏移量, 用来表示 0x80 这个码点
    • 最大值 110 11111 10 111111 有效 bit 的值是 0x7FF, 加上 0x80 的偏移量, 可以用来表示 0x87f 这个码点
    • 表示的范围是 [0x80, 0x87f].
    • 四个字节的同理, 用满所有的有效 bit, 可以多表示 2048 个码点.

    难道 UTF-8 让这些位置空着, 就为了不用做额外的加减偏移量的操作? 有了解的老哥来解惑一下么? 有来源就最好了

    第 1 条附言  ·  310 天前

    很多朋友误会了我的意思, 我说的"使用完所有的有效bit", 绝对不是 指把中间字节的前导 10 这两个bit也给占用了, 不是这个意思. 但是一部分回复我也没看懂, 说明我可能存在着认知的误区. 所以我试着说得更明白一点:

    还是拿两个字节的表示来说, UTF-8 里用两个字节表示一个码点时, 格式是这样的:

    110xxxxx 10xxxxxx

    • 这两个字节里只有 x 位是可以填充数据的, 也就是有 11 bit 的有效数据
    • 2^11 可以表示 2048 个码点
    • UTF-8 的双字节规定只能表示 1920 个码点, 范围是 码点0x00000080 到 码点0x000007FF. 按照它的编码规则, 编码成二进制, 也就是 11000001 10000000 到 11011111 10111111
    • 还有一部分数据没有用上, 这部分是 11000000 10000000 到 11000000 10111111. 我的疑问是, 为什么不使用这部分数据. 这部分数据并不会引起歧义
    第 2 条附言  ·  310 天前

    假设我们有一个编码方法, 姑且称为 UTF-B, 它的规则如下:

    • 一个字节的最高位是0
    • 一个字节的最高位是110, 表示它和后续的一个字节 10xxxxxx 组成一个码点, 有效bit 11位
    • 一个字节的最高位是1110, 表示它和后续的两个字节 10xxxxxx 10xxxxxx 组成一个码点, 有效bit 16位
    • 一个字节的最高位是11110, 表示它和后续的三个字节 10xxxxxx 10xxxxxx 10xxxxxx 组成一个码点,有效bit 21位

    这部分的编码规则和 UTF-8 是一致的. 不一致的地方主要在于: 多字节时, 表示范围的不一致

    • 单字节可以表示 [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]

    范围确定后就可以实施编码了, 以汉字’你’为例. 编码过程如下:

    • '你'字的码点是 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-8 多表示 128 个码点, 这部分码点在 UTF-8 里需要用 3个字节表示
    • 三字节能比 UTF-8 多表示 2048 个码点, 这部分码点在 UTF-8 里需要 4 个字节表示

    我的猜测是(很不确定), 这部分优势太弱, 还不如省点偏移量的计算...

    到底是不是这样呢? 求实锤肯定/否定

        1
    lance6716   310 天前 via Android   ♥ 1
    > 就为了不用做额外的加减偏移量的操作

    对,消耗这么一点点空间能让实现更优雅,是程序员通常会想的
        2
    DGideas   310 天前   ♥ 2
    关于“为什么 UTF-8 不用完所有的有效 bit 呢?”这个问题

    https://en.wikipedia.org/wiki/UTF-8#History 上的“ FSS-UTF proposal (1992) ”表格展示了你说的“最大压缩程度”的 UTF 的一种可能实现:the additional loss in compactness is relatively insignificant, but readers now have to look out for invalid encodings to avoid reliability and especially security issues。在 StackExchange 上的( https://softwareengineering.stackexchange.com/questions/262227/why-does-utf-8-waste-several-bits-in-its-encoding )这篇提问和回答也说了,用这种编码方式能够避免你在解析一个多字节序列时误认为它表示一个单字节( ASCII )字符,避免攻击者精心构造一个字符串,使得编码正好表达一系列 ASCII 表示的指令。
        3
    GeruzoniAnsasu   310 天前   ♥ 1
    前段时间也是在 v 站看到人发的

    http://utf8everywhere.org/zh-cn

    > UTF-8 编码在设计上保证了一个 ASCII 字符或子字符串永远不会匹配到一个多字节编码的字符中间。这在 UTF-16 中也适用。这两个编码中,多字节编码的码位的编码单元会将 MSB 设为 1。

    > 此外,你还可以像在简单的字节数组中一样,直接在一个 UTF-8 编码的字符串中搜索 UTF-8 编码的非 ASCII 的子字符串——无需关注码位边界。这要归功于 UTF-8 的另一个设计特点——一个码位编码的起始字节永远不会与其他码位的尾随字节相同。


    第一个字节的高位,在 utf8 中可用来判断这个码点编码成的 utf8 字节串有多长,而低位字节为了实现上面说到的设计,区间就不能包括开头字节的值

    比如两位,低字节最多到 10111111,如果编码到 11000000,就无法与开头字节区分
        4
    raysonx   310 天前 via iPad
    有一种针对中文 GB 编码的 SQL 注入方法,称为半字符注入或者宽字符注入,UTF-8 的这种设计则会避免这种攻击方式。
        5
    keakon   310 天前
    1100000x 不能出现在 UTF-8 的字节中,因为 110 开头表示是双字节字符的第 1 个字节,但第 2 个字节只能是 10 开头,还剩 6 个有效位,于是一共 7 位有效位,只能表示 0 ~ 127,和单字节的重复了。
        6
    imn1   310 天前
    实际上你还没理解 UTF-8

    试试用你所说的方法,这些字符,U4E,U25,U4E25,U014E25
    他们的二进制该如何排列?放在一起如何区分?
        7
    Vegetable   310 天前 via Android   ♥ 1
    半夜看到帖子里大佬们讨论的问题,都不好意思睡觉了,想赶紧起来学习。
        8
    msg7086   310 天前
    靠位移就能解码,按照你这种设计的话还要涉及到数学运算。先不说写程序更容易出 Bug。光说 CPU 运算效率,直接位移速度要快很多,甚至还能直接做成 CPU 指令集,或者利用已有的 SIMD 进行快速处理。你可以搜一下 UTF-8 SIMD 看看别人的快速实现。
        9
    Chingim   310 天前
    @DGideas
    @GeruzoniAnsasu 抱歉说得不清楚, 我 append 了. 我了解中间字节必须是 10xxxxxx 格式的必要性, 所以我指的不是"占用这两个比特"


    @keakon 1100000x 为什么不能出现在 UTF-8 的字节中呢? 11000001 10000000 这样的两个字节应该不会引起歧义吧?


    @imn1 如果按照 append 里提到的编码方法:
    - 0x4E,0x25 落在单字节区间, 一个字节就表示了, 二进制分别是: 01001110 以及 00100101
    - 0x4E25 落在了三字节区间, 在三字节序列里的偏移是 0x45A5, 填入三字节的格式, 最终的二进制: 11100100 10010110 10100101
    - 0x014E25 落在了四字节区间, 在四字节序列里的偏移也是 0x45A5, 填入四字节的格式中, 得到: 11110100 10010110 10100101
    - 解码器读到这些字节, 应该也可以还原回去
        10
    BXIA   310 天前 via iPhone
    目测会有 shell code 注入攻击
        11
    Chingim   310 天前
    @Chingim

    0x014E25 少写了一个字节, 应该是 11110000 10000100 10010110 10100101

    @BXIA 这么说还是有安全的考虑在里面的...
    @msg7086 嗯, 编解码速度可能也是造成它这么设计的原因, 位移确实比加减省事
        12
    AlphaTr   310 天前 via iPhone
    应该就是为了减少偏移,提高编解码效率,不知道有没有其他历史因素
        13
    guanaco   310 天前 via iPhone
    应该和老的 CPU 字节宽度有关?
        14
    wsxyeah   309 天前 via iPhone
    对于 110xxxxx 10xxxxxx:

    如果左边全为 0,那它的 Unicode 码点就跟单字节的是重复的了,这部分的数量就是单字节能表示的容量:128 个字符,也就是楼主奇怪的 2048-1920。
        15
    yidinghe   309 天前 via Android
    简单解释就是:0,110,1110,11110 是前缀标记,看到这个标记就知道一个字符是从这里开始,而且知道接下来有几个字节要读; 10 是中间标记,当你从一个字节流的某个位置开始读取,如果遇到 10,就知道它不是一个字符的开头,应该换一个位置读起了。
        16
    imn1   309 天前
    根据 APPEND2
    你有没有想过 U+800 和你说的 U+880 的区别呢?
    前者二进制只有一个「 1 」,后者有两个
    意味着通过位运算判断 800 前后,只需一个判断,880 前后则需要两个判断(注意说的是位运算,不是逻辑大于小于)
    同理 UTF-8 几个边界点都是这样,都是二进制仅有一个 1,并且是位于最左边,适合各种位运算

    你 APPEND2 所定边界,并没有比 UTF-8 多多少,却不适合高速判断,还不好记
        17
    BlackL   309 天前
    我觉得 @wsxyeah 说的比较对,以双字节为例,10000001 10111111 转换成 Unicode 码点就是 U+007F,而 10000000 10000000 转换成 Unicode 码点就是 U+0000,与 UTF-8 单字节表示的范围重复了,而三字节没有使用的那些范围也和双字节的范围重复,所以必须要避免重复。如果重复的话我觉得从 Unicode 转换成 UTF-8 的时候就不知道是使用哪种长度的字节好了
        18
    reus   309 天前
    所以 UTF-8 并不完全为了省空间而设计
        19
    somebody   309 天前
    如果楼主从一开始就通过 https://en.wikipedia.org/wiki/UTF-8 学习 UTF8,并且不要跳过任何一个字,就不会有这个问题了。不同来源的信息可信度、准确度不同,如果是深入研究细节,最好找可信度高的来源,不要找二手的
        20
    Chingim   309 天前
    @wsxyeah
    @BlackL 不会重复的, 有一个计算偏移的操作. 在假想的算法里, 10000000 10000000 表示的码点不是 U+0000 而是 U+0080
        21
    Chingim   309 天前
    @Chingim 上条打错了..在假想的算法里, 11000000 10000000 表示的码点不是 U+0000 而是 U+0080
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1296 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 23:24 · PVG 07:24 · LAX 16:24 · JFK 19:24
    ♥ Do have faith in what you're doing.