TimothyQiu's Blog

keep it simple stupid

字符编码

分类:技术,闲扯

我们平时所说的「文本」基本上都是在说「电脑屏幕上的字符」,但是小学生都知道「计算机只懂 0101」,那么电脑究竟是怎么处理三千世界中如此纷繁复杂的文字的呢?

开天辟地阿斯克

电脑是美国人发明的,所以最初的人们也只需要考虑「如何让电脑明白英文的字母和符号」的问题。

于是 ASCII(美国信息交换标准代码)诞生了。它参考了电报报文的设计,将 0 到 127 都赋予了对应的字母和符号。于是可以被电脑处理的数字序列 72 101 108 108 111 32 87 111 114 108 100 33 就可以通过查 ASCII 码表翻译成 Hello World!。当然,用更「计算机」一些的十六进制表示每一个数,就是:

48 65 6c 6c 6f 20 57 6f 72 6c 64 21
H  e  l  l  o     W  o  r  l  d  !

那么,输入并显示一个字符的过程就变成了:

  1. 你按下键盘的 H 键
  2. 电脑在内存中保存 0x48
  3. 电脑在屏幕上显示 0x48 号图形

也就是说,电脑不需要能够「明白」字符,只需要能够用数字「表示」字符。

百家争鸣,被榨干的单字节

随着时代发展,电脑开始在各地使用。以法语、希腊语等为母语的人发现 ASCII 真心坑爹,没有 è、é 没有 α、β、θ、让我们怎么活?

好消息是:计算机终于迎来了以 8 位为 1 字节的时代,而 ASCII 只为 0x00 到 0x7F 规定了对应字符。也就是说,ASCII 只占了低 7 位 0XXX XXXX,还有 0x80 到 0xFF 这余下的 128 个码位可以让人糟蹋。

这一利好消息的发现让人们大为振奋。

法国人开心地用 0xE8 表示 è,用 0xE9 表示 é;希腊人欢乐地用 0xE1 表示 α,用 0xE2 表示 β,用 0xE8 表示 θ……

E    9    7    1    7    5    6    9    7    6    6    1    7    5
1110 1001 0111 0001 0111 0101 0110 1001 0111 0110 0110 0001 0111 0101
é         q         u         i         v         a         u

所有 0 开头的字节在 ASCII 里找对应字符,所有 1 开头的字节在各自定义的字符集里找对应字符,问题解决了。

传说的巨龙,汉字的秘密

于是电脑来到了中国,但是中文不同于字母文字,如何给数万汉字编码就成了大问题。

一位伟人一拍脑袋:「一个字节只有 0 到 255,但两个字节就有 0 到 65535 啦!《新华字典》也就一万多个字,用两个字节表示一个汉字不就行了嘛~讨厌!」

没错,这就是一种后世所谓的多字节字符集(MBCS)。我们熟悉的 GB2312 和 GBK 使用的都是如下形式的二进制编码:

0XXX XXXX
1XXX XXXX XXXX XXXX

如果一个字节为最高位为 0,那么后续的 7 位表示一个字符(128 个码位)。如果最高位为 1,那么后续 15 位表示一个字符(32768 个码位)。

GB2312 前辈利用了这 32768 个码位中的 7445 个,而后辈 GBK 则利用了 21886 个。

例如二进制数据 48 69 20 CA C0 BD E7 的解析:

1| 4    8    6    9    2    0    C    A    C    0    B    D    E    7
2| 0100 1000 0110 1001 0010 0000 1100 1010 1100 0000 1011 1101 1110 0111
3| /100 1000 /110 1001 /010 0000 /100 1010 1100 0000 /011 1101 1110 0111
4| /4   8    /6   9     2   0    /4   A    C    0    /3   D    E    7
5|  H         i                   世                  界
  1. 字节序列(十六进制)
  2. 字节序列(二进制)
  3. 字节序列 --[GBK 解码]--> 码位(二进制)
  4. 字节序列 --[GBK 解码]--> 码位(十六进制)
  5. 码位 --[GBK 字符集]--> 字符

那么,几个之前没有讲的概念就比较明白了。

危机!乱码的陷阱

于是,全世界人民都一本满足了,但是这番和谐景象的背后却隐藏着天大的危机。之前,大家都用着自己的字符编码相安无事,但全球化却导致乱码横行。

聪明的你也许已经发现了:之前我们说过,法国人的 è 用 0xE8 表示,而希腊人的 θ 也用 0xE8 表示。有一天,法国人写了封 Email 给希腊人:

Jeux de caractères codés

希腊人收到一看:

Jeux de caractθres codιs

这是毛啊?于是转发给了中国人,中国人打开一看:

Jeux de caract鑢es cod閟

擦,顿时感觉自己没文化了……于是回复:

我看不懂……

希腊人无辜地打开一看:

Ξ?Ώ΄²»Ά?‘­‘­

这这这……于是转发给法国人,法国人也一头雾水:

ÎÒ¿´²»¶®¡­¡­

「我还是删了吧,妈妈说不要跟外国人发邮件……」

1| J  e  u  x     d  e     c  a  r  a  c  t  è  r  e  s     c  o  d  é  s
2| 4a 65 75 78 20 64 65 20 63 61 72 61 63 74 e8 72 65 73 20 63 6f 64 e9 73
3| J  e  u  x     d  e     c  a  r  a  c  t  θ  r  e  s     c  o  d  ι  s
4| 4a/65/75/78/20/64/65/20/63/61/72/61/63/74/68 72/65/73/20/63/6f/64/68 73
5| J  e  u  x     d  e     c  a  r  a  c  t  鑢    e  s     c  o  d  閟
  1. 法国人写的文字
  2. 法国人根据 latin-1 将文字转换为码位、并将码位编码得到实际保存的字节序列
  3. 希腊人根据 latin/greek 将序列解码得到码位、并将码位转换为字符,得到的文字
  4. 中国人根据 GBK 解码后得到的码位
  5. 中国人根据 GBK 字符集将码位转换到的字符

所以,二进制文本数据就相当于密文,而编码和解码如同加密和解密,只有用正确的密钥才能得到明文,也只有用正确的字符编码才能得到码位。然后通过码位在字符集里取得最终的字符。

(历史上,常常将字符集与字符编码等同起来。因为大部分字符集都是 8 位的,编码/解码形同虚设,N 编码后还是 N,可以直接 1:1 映射。例如上面例子中的 latin-1 和 lantin/greek,编码都是相同的 1:1 编码,只是字符集中相同码位对应着不同字符而已。)

大逆转,万国码的光荣

打开浏览器菜单,肯定存在一个叫做「编码」的选项,点开就能看到这世界上至少存在着多少种流行的字符编码。如果浏览器「自动检测」检测得不对,网页就乱码了。索性懒人是社会进步的阶梯。为了免去百家争鸣带来的麻烦,试图让全世界「书同文」的 Unicode 诞生了。

Unicode 标准化了一个字符集,包含了世界上所有的字符,每一个字符都拥有唯一的码位 U+XXXX。(起初的码位是 16 位的,可以容纳 65536 个字符。其后不断扩展,现今已经扩展到了 U+10FFFF。)

Unicode 还提供了几套编码方案,来将 U+XXXX 的码位编码为字节序列,例如:UTF-8 和 UTF-16。

UTF-8

UTF-8 顾名思义,是一套以 8 位为一个编码单位的可变长编码。会将一个码位编码为 1 到 4 个字节。

U+ 0000 ~ U+ 007F: 0XXXXXXX
U+ 0080 ~ U+ 07FF: 110XXXXX 10XXXXXX
U+ 0800 ~ U+ FFFF: 1110XXXX 10XXXXXX 10XXXXXX
U+10000 ~ U+1FFFF: 11110XXX 10XXXXXX 10XXXXXX 10XXXXXX

例如「萌」在 Unicode 中的码位为 U+840C,对应的 UTF-8 编码为 E8 90 8C

1|     8       4     0     C
2|     1000    0100  0000  1100
3|     1000    010000    001100
4| 11101000  10010000  10001100
5| E   8     9   0     8   C
  1. 码位(十六进制)
  2. 码位(二进制)
  3. 根据 UTF-8 编码规则将码位分为三段
  4. 为每一段加上前缀,编码完成(二进制)
  5. 编码完成(十六进制)

UTF-16

UTF-16 则是一套以 16 位为一个编码单位的可变长编码。会将一个码位编码为 1 到 2 个双字节。编码算法大同小异并不重要,但有一个问题却亟待解决:字节序。

不同的系统,字节序可能不同。小端序系统的 0x1234 实际上是 34 12,把这个字节序列发给大端序系统,34 12 就会被理解成 0x3412。

于是,Unicode 中引入了一个特殊字符:字节序标(BOM),码位 U+FEFF。用于加在被编码的数据之前,表示编码时的字节序。于是,解码时,首先读出第一个双字节:

当然,UTF-16 还有派生的 UTF-16LE 和 UTF-16BE,实际上就是按字节序特化的版本。

Python 正则表达式

分类:技术

先说一个比较囧的事情:在写虾米音乐试听下载器的时候遇到一个问题,因为保存的文件都是用音乐的标题命名的,所以碰到一些诸如「対峙/out border」等含有非法字符(哼哼,说的就是你 →_→ Windows)的标题的时候,就会保存失败。于是我想起了迅雷的解决方法:把所有的非法字符替换成下划线。

于是就引入了正则表达式的使用。一番搜索囫囵吞枣后,我写下了这样的函数:

def sanitize_filename(filename):
    return re.sub('[\/:*?<>|]', '_', filename)

最近意识到了这个函数里的好多问题:

于是感觉得正正经经看看文档了。

Raw strings

看了文档后才意识到,Python 正则表达式模块的转义是独立的。例如匹配一个反斜杠字符需要将参数写成:'\\\\'

  1. Python 将字符串转义:\\\\ 被转义为 \\
  2. re 模块获得传入的 \\ 将其解释为正则表达式,按照正则表达式的转义规则将其转义为 \

如此麻烦的前提下,Raw String 就大有作为了,顾名思义就是(除了结尾的反斜杠)不会被转义的字符串。于是匹配一个反斜杠字符就可以写作 r'\\'

所以上面的 sanitize_filename 改成了:

def sanitize_filename(filename):
    return re.sub(r'[\\/:*?<>|]', '_', filename)

Regex 和 Match

于是正经看看 re 模块吧~以下为流水帐,供急性子观看。

Python 的正则表达式模块 re 中主要的对象其实是这俩:

RegexObject 是正则表达式对象,所有 match sub 之类的操作都归它所有。由 re.compile(pattern, flag) 生成。

>>> email_pattern = re.compile(r'\w+@\w+\.\w+')
>>> email_pattern.findall('My email is abc@def.com and his is user@example.com')
['abc@def.com', 'user@example.com']

其中的方法:

re 模块里提供的函数如 re.sub re.match re.findall 实际上都可以认为是一种省去直接创建正则表达式对象的捷径。而由于 RegexObject 对象本身可以反复使用,这也是它相对于这些捷径函数的优势所在。

MatchObject 则是匹配对象,表示一次正则表达式匹配的结果。由 RegexObject 的一些方法返回。匹配对象永远是 True 的,另外还有一大堆用来取得正则表达式中分组(group)相关信息的方法。

>>> for m in re.finditer(r'(\w+)@\w+\.\w+', 'My email is abc@def.com and his is user@example.com'):
...     print '%d-%d %s %s' % (m.start(0), m.end(0), m.group(1), m.group(0))
...
12-23 abc abc@def.com
35-51 user user@example.com

参考内容:The Python Standard Library

虾米音乐试听下载器

分类:技术

最近做视频需要从虾米上找些音乐做 BGM 用,无奈从虾米上下音乐是要花「米」这种虚拟货币的。所幸的是试听是完整的,而且就我的耳朵而言听不出这个「试听」的音质有什么变化,加上最近在学 Python,就写了这么一个东西。

原理依旧简单:歌曲和专辑都有 ID(从 URL 上看得出来),试听播放器根据 ID 拼接地址得到一个 XML 播放列表文件。而这个播放列表就是需要在试听播放器里添加的播放列表。其中表示位置的 location 字段是被加密过的,类似于

6hAFat2221F19E4pt%fm%FF%6%78853t23i21528579_3pF..F98F2E%136%%xn4275%15%2.32ie%%912_E57m

仔细观察,或者对照实际 URL 可以看出可以将这一串字符写作如下形式:

6
hAFat2221F19E4p
t%fm%FF%6%78853
t23i21528579_3
pF..F98F2E%136
%%xn4275%15%2.
32ie%%912_E57m

其中第一个「6」表示将后面的内容折成六行。如此处理后的内容,就成为了前几天特别流行的藏头了。

http%3A%2F%2Ff3.xiami.net%2F4%2F192%2F58792%2F511682%2F%5E1_177%5E9891%5E8_3274536.mp3

进行 unquote 后变成

http://f3.xiami.net/4/192/58792/511682/^1_177^9891^8_3274536.mp3

继而将 ^ 替换为 0 就是最终的 URL 了!

GitHub Repo: https://github.com/timothyqiu/xiami-downloader

SS 源码阅读小记

分类:技术

阅读一下某源代码,学习一些 Python 的基本知识 = =

注意:以下内容均为 Python 基础知识笔记,几乎都可以通过上述途径获得。

肉馅

使用 hashlib 模组求哈希值,需要首先指定算法来创建 hash object,而后使用。

该模组提供了 new 函数,通过填入算法名得到 hash object,例如 hashlib.new('sha1') 创建一个使用 SHA-1 算法的 hash object,而另一种更快的方法是使用特定的函数直接创建,例如 hashlib.sha1()

至于 hash object,主要方法不外乎 update(添加被哈希的数据)和 digest(取哈希值的二进制表示)、hexdigest(取哈希值的十六进制表示)。

行李

所谓 Python 与 C Struct 交互的说法可能说得比较玄乎,也许可以描述成 Python 值与二进制数据的相互转换吧。

struct.pack(fmt, v1, v2, ...) 即将 v1v2 等数据以 fmt 规定的形式转换为二进制数据。而 struct.unpack(fmt, string) 反之,是将二进制数据解释到若干个 Python 值。

顺带一提,Lua 也有类似的模组:http://www.inf.puc-rio.br/~roberto/struct/

地图

接下来,string.maketrans(from, to) 的大意是返回一个长度为 256 的字符串作映射表用(可以提供给 string.translate 使用,表示将 ASCII 为 N 的字符映射到字符串中的第 N 个字节),其中已经把 from 中的每一个字节映射到了 to 里的相应位置。

题外话,Python 中的字符串求长度是没有 length 方法的(虽然有 __len__),只有一个 len 函数统一对各种可以求长度的对象求长度。这个让我想起了 C++11 中建议将 vector::begin 改为使用 ::begin 的做法。

阅读理解

List(列表)表示一个可变的序列。创建 List 可以使用方括号:

L = [] # 空
L = [expression, ...]

也可以使用 list 函数:

L = list() # 空
L = list(sequence)

更可以使用让 Python 做阅读理解的方法(好吧,是 List Comprehensions)。

正如喆哥在 Pipeline 中所说,将一个集合变换到另一个集合是一种非常常见的操作。Python 提供了 List Comprehensions 来提供这一机能:通过类似 [expression for variable in sequence] 的语法产生一个新的 List ,使得其中每一项都是满足后面「for 和 if 的组合」的 expression。举个栗子:

>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

另外需要顺带一提的是,Python 的 for 循环只有类似 foreach 的 for x in y 形式。

列表排序

终于有一个正常向的小标题了 >.<

使用全局的 sorted 函数可以返回排序后的列表。而如果需要就地排序,可以使用 List 类型自带的 list.sort 方法来进行。

a = [5, 1, 4, 3]
print sorted(a) # [1, 3, 4, 5]
print a         # [5, 1, 4, 3]

可以通过给出其它参数来对排序过程进行详细控制,比如:

a = ['an', 'Apple', 'is', 'good']
print sorted(a)                # ['Apple', 'an', 'good', 'is']
print sorted(a, key=str.lower) # ['an', 'Apple', 'good', 'is']
print sorted(a, reverse=True)  # ['is', 'good', 'an', 'Apple']

也可以用 lambda 定义用于比较的函数:

a = ['an', 'Apple', 'is', 'good']
print sorted(a, lambda x,y: cmp(str.lower(x), str.lower(y))) # 效果和上面使用 key 的例子相同

古董

曾几何时的 Visual Basic 中就有这么一对函数:ChrAsc,分别用于将 ASCII 值转为字符、将字符转为 ASCII 值。

而到了 Python 中,就是 chrord 函数,不同的是,针对 Unicode 还有一个 unichr

开膛破肚

对 List 除了可以使用下标进行普通的 index 操作外,还有一种名为 slice 的操作,使用「slice notation」表示:起始下标:结束下标:步长

yuruyuri = ['akari', 'kyouko', 'yui', 'chinatsu']
print yuruyuri[1]    # 'kyouko'
print yuruyuri[1:3]  # ['kyouko', 'yui']
print yuruyuri[1:-1] # ['kyouko', 'yui']
print yuruyuri[1::2] # ['kyouko', 'chinatsu']

可以看出,结束下标是不包含在最终结果里的哟。另外,每一个数字都可以省略:省略起始下标则默认为 0,省略结束下标则默认为全长,省略步长则默认为 1。

而对 slice 的直接赋值,会对原 List 造成修改:

yuruyuri[0:1] = []
print yuruyuri        # ['kyouko', 'yui', 'chinatsu']
yuruyuri[0:1][0] = ''
print yuruyuri        # ['kyouko', 'yui', 'chinatsu']

题外话,「slice notation」还可以用在字符串上,使得产生一个字串。而由于 Python 的字符串不像 C 的字符串,是不可以通过 s[2] = 'a' 更改内容的,于是通过 slice 来进行就方便多了。(s[:n] + s[n:] == s 哟。)

天下大势

将字符串拆分为子字符串列表、将字符串列表合并为一个字符串,这些也是常见操作。Python 中实现这种机能的函数分为两组:

其实都是一样的作用,只是前者是内置字符串类的方法,后者是 string 模组的函数。

红色警戒 II

类似于 C++ 的 RAII 和 C# 的 using,Python 有 with 语句。

熟悉的应该一看就懂了吧~(虽然我不清楚三者是否可以等价,但从效果上说还是差不多的嘛~)

C++11 Variadic Template

分类:技术

听说这个特性是很久以前了,总是读作「维拉迪克·坦普雷特」,一直没反应过来中文到底该叫什么,因为 C 时代的 Variadic Macro 我一直是很象形地读作「点点点」的 = =||

OK,扯远了。Variadic Template 对应中文应该是「可变参数模板」。

Parameter Pack

既然是可变参数,就需要通过某种方式来表示这些参数,而这里的解决方案就是 Parameter Pack 参数包,不知道可不可以简称「餐包」 =_,=

声明参数包的方法是在类型和名称之间加 ...

template<typename... Types> struct Tuple {};
Tuple<>           t0;   // Types 中不含参数
Tuple<int>        t1;   // Types 中包含一个参数:int
Tuple<int, float> t2;   // Types 中包含两个参数:int 和 float

template<typename... Types> void f(Types... args);
f();        // args 中不包含参数
f(1);       // args 中包含一个参数:int(1)
f(2, 1.0);  // args 中包含两个参数:int(2) 和 double(1.0)

上面的两个示例中,Types 称作模板参数包,args 称作函数参数包。

参数包所包含的参数的个数可以用 sizeof... 取得。

Pack Expansion

既然提出了参数包,把所有可变参数容纳其中,那么就需要存在将其解包的操作。与 C 中 va_list 一个参数一个参数地手动解包不同,参数包的 Pack Expansion 是一口气将所有的参数以某种形式展开:

template<int... Entries>
struct IntArray {
    int array[sizeof...(Entries)] = { Entries... };
};

template<typename... Types> void bar(Types... args) {}
template<typename... Types> void foo(Types... args) {
    bar(&args...);
}

所谓「以某种形式」展开,就是将 pattern ... 转换为逗号分隔的 pattern_1, pattern_2, ... , pattern_N 的形式。从上面的函数 foo 就可以看出,传给 bar 的是各个参数的地址(没啥大意义);即 void foo(a, b, c)&args... 会展开成 &a, &b, &c

std::tuple

作为一个可变参数模板的实际用例,C++11 还引入了 std::tuple 作为 std::pair 的推广形式(tuple 的意思即为元祖……哦不对,是元组……我是吃货我自重……),表示任意多个元素的组合。

使用 std::make_tupleauto 可以很方便地声明一个元组:

auto x = std::make_tuple(3, 0.14, std::string("pie")); // std::tuple<int, double, std::string>

而对于各个元素的访问可以统一使用 std::get 实现(包括 std::arraystd::pair 的大一统):

auto element = std::get<2>(x);

另一个好玩的地方是使用 std::tie 创建 lvalue reference 的 tuple:

std::set<int> some_instance_of_std_set;
std::set<int>::iterator itr;
bool success;
std::tie(itr, success) = some_instance_of_std_set.insert(2012);

虽然看着有些丑陋,但似乎可以看到些「多返回值」的影子……

当然,也可以参照 Lua 中的 _ 使用 std::ignore 忽略多返回值中的特定位置的值:

int r1, r2;
std::tie(r1, std::ignore, r2) = std::make_tuple(3, 0.14, 4);

顺带的,既然是 lvalue reference,试图一句话交换两个变量的值是不可以全用 std::tie 的:

std::tie(a, b) = std::tie(b, a);        // 错误方式
std::tie(a, b) = std::make_tuple(b, a); // 正确方式