奇文共欣赏~UTF-8设计与源码实现

原文链接:http://www.juzicode.com/archives/2272

在《编码: 一个隐藏了30多年的bug,Windows含蓄说过某通不行?》一文中我们简单讨论了Unicode和UTF-8的关系,UTF-8本身并不是一种字符集,而是实现Unicode字符集的一种编码方式。RFC3629规定的Unicode字符集和UTF-8编码的对应关系是下图这样的:

1、设计原则

在Unicode官网上V1.1.0的附录部分 (https://www.unicode.org/versions/Unicode1.1.0/appF.pdf) 介绍了UTF-8编解码的设计原则和C语言的实现方法,这套原则是大神Ken Thompson提出的(也是这位大神发明了B语言,并编写了Unix操作系统),这套原则具体包含了:

1、兼容历史存在的文件系统,不允许空字符(0x00)和斜杠( / )作为文件名的一部分。
2、兼容已经存在的程序,多字节字符的组成部分不能包含ASCII字符,也就是多字节部分的内容不能有0x00~0x7F的值。(这点和GB2312编码类似。)
3、和Unicode的相互转换要简单。
4、多字节序中的第1个字节要表明剩下组成的字节数目。
5、编码时不能浪费过多的字符。(这是在嘲笑UTF-32表示ASCII字符都用了4个字节?)
6、能高效地找到一个字符的开始字节。

在这篇附录中提出UTF-8使用变长字节表示0~0x7FFF FFFF范围内的编码(包含了rfc3629的Unicode编码范围)。如果是ASCII(0~0x7F)的范围,则直接可以使用单字节表示,其最高bit为0。当表示其他编码值时,则使用可变长度的字节表示,首字节前导部分根据编码范围用0b1[1,5]0的形式表示,括号[]中间可以有1~5个数值1,首字节剩余部分为组成Unicode编码的有效bit位,后续的字节都是10xxxxxx形式,x表示组成Unicode编码的有效bit位,正如下图所示,如果是2字节UTF-8,则首字节有5个有效bit,如果是3字节UTF-8,则首字节有4个有效bit,依次类推:

这样表示0~0x7FFF FFFF范围内Unicode数值的UTF-8编码就是下图这样子的,其中v表示Unicode的有效bit位:

2、源码分析

为了分析源码,我们先根据设计原则和UTF-8编码规则找下编码规律:

1、ASCII字符用一个字节表示,最高位bit为0。
2、根据Unicode值的不同范围,其长度是不一样的,但是在首字节的前导bit位上1和0之间有多少个1表示剩余就有多少个字节。
3、除了首字节,剩余字节都是以0b10开始的,这也符合”多字节不能包含ASCII字符”的原则,因为ASCII字符最高位为0。
4、UTF-8首字节的有效bit通过Unicode的数值右移剩余字节数*6得到,剩余字节依次右移6bit得到。

整个源码分为3部分,第1部分是为编解码设计的一种数据结构并定义了一个查找表。

第2部分是从UTF-8到Unicode的解码函数:int mbtowc(wchar_t *p, char *s, size_t n),s是UTF-8字节序起始地址的指针,p是保存编码后Unicode字符的指针,n是待解码UTF-8字节序的长度。

第3部分是从Unicode到UTF-8的编码函数:int wctomb(char *s, wchar_t wc),s为UTF-8字节序的起始地址指针,wc为待编码的Unicode字符。

2.1、查找表

一开始就掌握数据结构的全貌还是有些困难的,我们可以先了解些大概,通过分析实现函数再反过来促进理解数据结构,这个方法在学习其他的源代码时也同样适用,先对某个概念了解大概,通过上下文反过来融会贯通理解全貌。

从查找表可以看出第1列是首字节前导部分的掩码,首字节和该掩码相与得到的是首字节的前导部分;第2列是首字节前导部分补零后的值;第3列采用x*6的形式,x等于编码后的字节长度-1,Unicode编码值右移x*6位得到的是首字节中有效bit组成的数值;第4列对应的是Unicode编码范围的上限;第5列对应的是Unicode编码范围的下限。

2.2、解码

在解码函数中,首先保存首字节内容,在循环中查找tab表,每次移动一行, 当首字节和前导部分掩码相与后,如果等于前导部分的值查表结束,检查解码值的范围退出,如果不等于前导部分的值,则继续解码后面的剩余字节。解码剩余字节设计的比较巧妙,用这个值和0x80异或,这样一个操作既能得到剩余字节的有效6bit值,也能很快得到剩余字节的前2个bit是否等于0b10。

2.3、编码

在编码函数中for循环中查找tab表,每次移动一行,通过lmask找到Unicode的编码范围,如果找到了则提取shift值赋值给变量c,并作为首字节有效bit的位移数,如果c大于0需要继续编码剩余的字节,c每次自减6用Unicode编码数值右移c位,再和0x3F相与得到剩余字节的6个有效bit位。

大神出手着实不凡,整个编解码过程非常精简,特别是解码函数中剩余字节和0x80相异或的过程,简直是神来之笔。

推荐阅读:
编码: 一个隐藏了30多年的bug,Windows含蓄说过某通不行?
zbar:给我来10G打码图片
用你的邮箱为你看家护院
好冷的Python-- if __name__==’__main__’是啥东东
Python混合编程:C语言接口ctypes(2)
Python混合编程:代码级扩展 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注