Mar 24
原文: Reed–Solomon codes for coders
参考: AN2407.pdf
WIKI: 里德-所罗门码
实现:Pypi ReedSolo

#译注:最近看到了RS码,发现还挺有意思的,找了一些资料学习了下,发现对于程序员来说,从这篇看起会比较容易。看完以后想着翻译一下试试,看看自己到底看懂了多少,于是就有了这篇。本文有部分错误,以及一些排版不对的地方,有兴趣的还是看原文更好:)

为程序员写的Reed-Solomon码解释

Reed-Solomon纠错码(以下简称RS码)广泛用于数据存储(如CD)和传输应用中。然而,在这些应用中,码字是藏在了电子设备里,所以无法一窥它们的模样以及它们是如何生效的。有些复杂的条形码设计也采用了RS码,能够暴露出所有的细节,对于想要获得这种技术如何生效的第一手技术的爱好者,这是一种很有趣的方式。

在这篇文章里,我是试图从程序员的视角(而不是数学家的视角)来介绍RS码的基本原理。我会用以当下流行的QR码作为例子来介绍。我选择了Python(主要是因为写出来的代码看起来整洁美观),但是我也会介绍一些不那么显而易见的Python特性,以便那些不熟悉Python的人也能看懂。里头涉及到的数学知识对读者有一定要求,并且一般是大学才教授的,但是应当能让对高中代数掌握较好的人看懂。

内容:
1 QR码结构
1.1 掩码
1.2 格式信息
1.3 数据
1.4 解码
2 BCH码
2.1 BCH错误检测
2.2 BCH纠错
3 有限域理论
3.1 乘法
3.2 基于对数的乘法
3.3 除法
3.4 多项式
4 RS码
4.1 RS生成多项式
4.2 RS编码
4.3 伴随式(Syndrome)计算
4.4 消除(erasure)纠正
4.5 错误(error)纠正
4.6 消除和错误纠正
Mar 23

mk802的wifi配置 不指定

felix021 @ 2013-3-23 16:21 [IT » 硬件] 评论(0) , 引用(0) , 阅读(7913) | Via 本站原创
本来这篇应该很早就写的,一直偷懒。今天简单记录一下吧。

其实很早就想买raspberry pi,但是代购的话比原价贵太多,不了了之。后来看到mk802,说是Arm Cortex A8 1GHz + 1GB Ram,性能远超树莓派,而且可以刷原生Linux(自带的是安卓),一冲动就买了。买回来才发现,mk802只有HDMI输出,用 hdmi 转 dvi 线连 dvi 显示器不行,所以刚买回来的时候蛋疼了两天。

首先是为内置的android配置wifi。幸亏默认是打开了USB调试的,连上PC,用类似腾讯手机管家这样的软件可以看到桌面截图,如果开启连续截图的话,就可以像幻灯片一样“远程桌面”。而mk802有一个标准usb host和一个mini usb otg,因此可以直接连接鼠标和键盘。主要问题是慢,相当慢。有耐心的话还是可以设置好的,甚至我把usb摄像头连上去,可以通过android qq跟电脑视频。

其次是刷Linux。这个才是重点——如果不是它可以刷原生Linux的话我就不会买了。从MiniAnd的这个帖子下载到了ubuntu的镜像包(直接dd写到tf卡),不过问题是Linux下面默认没办法看到桌面了(没有显示器,没有网络),所以只能通过不断修改配置文件的方式来尝试让它一启动就自动连接wifi。蛋疼了好久,不过还好最后问题解决了,而且解决办法也很简单,没兴趣看基本思路的同学可以直接跳到第3步。

基本思路是:

1. 挂载tf卡(拆下来在linux上挂载,或者也可以直接在mk802的android上挂载,通过adb shell连上去即可),修改 rc.local 或其他配置,让它在启动的时候自动执行一些命令,例如 ifconfig -a 和 iwconfig 、 iwscan 等。

2. 启动mk802,等待一段时间,让它把命令的输出并重定向到某个文件,然后关掉它,再次挂载tf,读取那些信息。由此可知它的网卡名字是 wlan0 ,并且可以搜到家里的wifi。

3. 挂载tf卡,修改 /etc/network/interfaces ,加入以下这一段配置(#号和它后面的就别加了),重启后它就自动连上wifi了:
引用
auto wlan0
iface wlan0 inet static
address 192.168.1.11
gateway 192.168.1.1
netmask 255.255.255.0
dns-nameservers 192.168.1.1
wpa-ssid OpenWrt_2E8B84 #这里是WIFI的SSID
wpa-psk password #这里是WIFI的密码
wpa-key-mgmt WPA-PSK
wpa-pairwise TKIP CCMP
wpa-group TKIP CCMP
wpa-proto WPA RSN
wpa-ap-scan 1
wpa-scan-ssid 1


后记:某次用一个5000mah的移动电源测试大约坚持了13个小时,推算功率大约是1.5w,后来它就一直开机,作为一个小vps用了。。。

后记@2014.10.12
引用
As root, create a file /etc/modprobe.d/8192cu.conf with the following contents:
options 8192cu rtw_power_mgnt=0 rtw_enusbss=0
This prevents the power down/up cycles of the 8192 wifi chip.

//from https://www.miniand.com/forums/forums/2/topics/82?page=9
Mar 23
#Update@3.23 23:05 早上9点之前密码重置功能被Apple暂停了,下午根据CNBETA的消息漏洞已经修复。

今天一个朋友的苹果帐号密码被修改,iMac、iPad、iPhone上的所有资料都被抹除,iMac被锁定无法登陆,几百GB的资料瞬间化为乌有,怀疑是同行恶意行为。悲剧详情可到v2ex的这个帖子凭吊。

根据提示这个帖子描述漏洞详情的两个连接 国外版 国内版 里提到的方法,我用自己的apple id和新注册的apple id验证,的确存在

重置密码过程异常简单(使用chrome):

1. 登录https://iforgot.apple.com/iForgot/iForgot.html,填写指定的apple id,点击下一步
2. 选择验证方法—— 回答安全提示问题,点击下一步
3. 填写apple id注册时填写的出生日期,先不提交
4. 打开开发者工具,在elements处搜索"security"字样(某个hidden的input的value),改成null
5. 提交,进入密码重置页面,输入新密码,重置完成。

因此强烈建议立即修改自己apple id的生日

修改流程:

1. 打开 https://appleid.apple.com ,登陆
2. 点击左边的“帐户和密码安全”
3. 填写安全提示问题的答案,并点击继续
4. 在新页面里修改生日。

应该朋友要求已将操作视频录像,有兴趣的可以在 优酷 观看,或者从 百度网盘微云 下载,瞧瞧看看苹果的服务有多么不堪。
Mar 21
After wasting over 45 minutes on moving database out of the default "/var/lib/mysql" on Ubuntu, I think this crazy problem should be written down, in case someone get confused by the same problem again.

I thought this problem to be very simple: go to /etc/mysql/, edit my.cnf, change the "datadir = /var/lib/mysql" to a new place, say, /home/mysql, and run "service mysql restart". But mysqld just refused to start, it says something like this:
引用
/usr/sbin/mysqld: Can't find file: './mysql/plugin.frm' (errno: 13)
130321 22:48:26 [ERROR] Can't open the mysql.plugin table. Please run mysql_upgrade to create it.
130321 22:48:26 [Note] Server hostname (bind-address): '127.0.0.1'; port: 3306
130321 22:48:26 [Note]  - '127.0.0.1' resolves to '127.0.0.1';
130321 22:48:26 [Note] Server socket created on IP: '127.0.0.1'.
130321 22:48:26 [ERROR] /usr/sbin/mysqld: Can't find file: './mysql/host.frm' (errno: 13)
130321 22:48:26 [ERROR] Fatal error: Can't open and lock privilege tables: Can't find file: './mysql/host.frm' (errno: 13)

I'm very sure I've done chmod/chgrp to "/home/mysql", so it won't be file permission problem. It occurred to me that the original database 'mysql' may contain some path information, since it's a newly installation, so I backed up the mysql directory, tried to run "mysql_install_db --user=mysql --datadir=/home/mysql", and failed again:
引用
$ mysql_install_db --user=mysql --datadir=/home/mysql/
Installing MySQL system tables...
130321 23:18:17 [Warning] Can't create test file /home/mysql/localhost.lower-test
130321 23:18:17 [Warning] Can't create test file /home/mysql/localhost.lower-test

Installation of system tables failed!  Examine the logs in/home/mysql/ for more information.

and two more lines were added to the error.log:
引用
ERROR: 1005  Can't create table 'db' (errno: 13)
130321 23:06:48 [ERROR] Aborting

That was weird. I used bash -x to run mysql_install_db again (it's a bash script) and found out that It started mysqld with some certain parameters which printed the Warning message shown above. So the problem went back to mysqld. A forum thread somewhere also noticed the problem but didn't come up with a solution.

With no choice, I went through the manual of mysql_install_db, and fortunately found a comment at the end of the page:
引用
Ubuntu 9.10
Moving the database from /var/lib/mysql to /data/databases/mysql

You'll get errors when running mysql_install_db until you go into /etc/apparmor.d, update the usr.sbin.mysql file, and run /etc/init.d/apparmor restart

You may also get an error when running /etc/init.d/mysql start:

Access denied for user debian-sys-maint at localhost

Check /etc/mysql/debian.cnf for the account information.

You'll need to run mysql, add the grant tables, and then restart mysql.

As the 'usr.sbin.mysql' requests, I added two lines to the end of "/etc/apparmor.d/local/user.sbin.mysql" and restarted apparmor(/etc/init.d/apparmor restart), thus fixed the problem.
引用
  /home/mysql/ r,
  /home/mysql/** rwk,
Mar 18

模重复平方算法 不指定

felix021 @ 2013-3-18 15:20 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(14124) | Via 本站原创
在RSA算法里头经常要用到“求x的n次方模m”这样的过程,通常使用O(log(n))的模重复平方算法来实现,提高效率。

其实这是大二学的《信息安全数学基础》里面的内容,那时为了考试需要(手算+写出很罗嗦的过程),还专门写了代码放在Blog空间里考试的时候用—……

同样O(log(n))的递归算法其实很容易理解:
/* C */
int square(int x) { return x * x; } /* 这里可不能用宏哟 */
int fast_mod(int x, int n, int m)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return square(fast_mod(x, n / 2, m)) % m;
    else
        return x * fast_mod(x, n - 1, m) % m;
}

#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m

;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
    (define (square x) (* x x))
    (cond ((= n 0) 1)
          ((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
          (else (remainder (* x (mod-fast x (- n 1) m)) m))))

(mod-fast 79 24 33)
;16

但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制(比如n=13, 1101),然后一位一位地推。

试推了一下从高位到低位,倒是挺简单的,记B[i]为第 i 位的值,通过A[i] = A[i+1]^2 * x^B[i] 从高到低计算出A[0],就得到结果了。但是问题是,为了从高到低计算,又得一次递归,似乎不能满足要求。

于是只好反过来,从低位往高位推。这个过程其实也挺简单的,举例来说:

当n=13,即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时,最终结果

ans = x^n % m
    = x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
    = [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m

也就是说,从低到高,在第 i 位的时候,将 x^(Bit[i] * 2^i) % m 乘到结果中即可。这里可以稍微变换一下:仅当Bit[i] == 1的时候,将x^(2^i) % m乘进去即可。所以这里可以用一个辅助的变量 b 来保存 x^(2^i) % m,在每次迭代的过程中 b = b^2 % m 。

于是实现就容易了:
/* C */
int fast_mod_iter(int x, int n, int m)
{
    int a = 1, b = x; //i=0的时候b = x^(2^0) = x
    while (n)
    {
        if (n % 2 == 1)
            a = a * b % m;
        b = b * b % m;
        n /= 2;
    }
    return a;
}

#Python
def fast_mod(x, n, m):
    a = 1
    b = x
    while True:
        if n == 0:
            return a
        if n % 2 == 1:
            a = a * b % m
        b = b * b % m
        n /= 2

;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
    (define (iter a b n)
        (cond ((= n 0) a)
              ((even? n)
                (iter a (remainder (* b b) m) (/ n 2)))
              (else
                (iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
    (iter 1 x n))

(mod-fast-iter 79 24 33)
;16


//网上搜了下模重复平方算法,居然没有靠谱的算法解释,看来可能还是这个算法太简单了吧。。。
Mar 18

fibonacci 的进化 不指定

felix021 @ 2013-3-18 01:06 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(14939) | Via 本站原创
最近在看SICP,抛弃旧的世界观和方法论压力很大,不过还是很有收获的,比如学习了个O(log(n))的fibonacci算法,大涨姿势啊。

想起前几天看到的某个笔试题,说是用最快的办法计算fibonacci数列的第n项。虽然我知道它是有个通项公式的,但是不适用于精确计算,因此写了个迭代的算法,自以为已经很好了,现在看了真是too simple sometimes naive了。

众所皆知 fibonacci 的定义是f(n) = f(n - 1) + f(n - 2); f(1) = f(2) = 1(从f(1)=1开始算起)
#Python版:
fibonacci = lambda n: 1 if n <= 2 else fibonacci(n - 1) + fibonacci(n - 2)

/* C版 */
int fibonacci(int n) {
    return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

;Scheme版
(define (fibonacci n) (if (<= n 2) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

不幸的是这样树形展开效率太低了,当n=42的时候,C语言需要的时间已经超过1s了。

因此需要改成迭代版,使用 (a, b) <- (a + b, a) 这样的方式。
#Python版
def fibonacci(n):
    a = 1; b = 0;
    for i in range(n):
        a, b = a + b, a
    return b

/* C版 */
int fibonacci(int n) {
    int a = 1, b = 0, c;
    while (n--) {
        c = a;
        a = a + b;
        b = c;
    }
    return b;
}

;Scheme版
(define (fibonacci n)
  (define (iter n a b)
    (if (= n 0) b (iter (- n 1) (+ a b) a)))
  (iter n 1 0))

虽然O(n)的效率已经有显著的提升,但是由于这个数列的增长超过了2^n,所以当对于稍大的n,就需要使用大整数的运算,效率很低。python版的代码,当n=300,000的时候,需要超过1s才能得出结果;Scheme版则需要大约9s。

SICP的练习1-19里面则提到一个O(log(n))的巧妙算法:将计算fibonacci的每次迭代 (a, b) <- (a + b, a) 表示为一个变换T[p=0, q=1],具体表示为(似乎是用矩阵乘法倒推过来的)
引用
T[pq](a, b) = (a(p+q) + bq, aq + bp)


通过计算 T[pq](T[pq](a, b)) (即对(a, b)进行两次T[pq]变换),可以得到
引用
(a((pp+qq) + (2pq+qq)) + b(2pq+qq), a(2pq+qq) + b(pp+qq))

记 p' = pp + qq, q' = 2pq+qq 则有
T[p'q'](a, b) = T[pq](T[pq](a, b)) = (a(p' + q') + bq', aq' + bp')

于是
f(n+1) = T[pq]n(f(1))

也就是说——可以通过类似分治计算 《a的n次方模b》 的算法来计算fibonacci了!

给出了算法以后,代码就容易写了:
#Python版
def fibonacci(n):
    def iter(a, b, p, q, n):
        if n == 0:
            return b
        elif n % 2 == 0:
            return iter(a, b, p * p + q * q, 2 * p * q + q * q, n / 2)
        else:
            return iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1)
    return iter(1, 0, 0, 1, n)

/* C版 */
typedef unsigned long long ull;
ull fibo_iter(ull a, ull b, ull p, ull q, int n) {
    if (n == 0)
        return b;
    else if (n % 2 == 0)
        return fibo_iter(a, b, p *p + q * q, 2 * p * q + q * q, n / 2);
    else
        return fibo_iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1);
}

ull fibonacci(int n) {
    return fibo_iter(1, 0, 0, 1, n);
}

/* Scheme版 */
(define (even? n) (= (remainder n 2) 0))
(define (fibonacci n)
    (define (iter a b p q n)
        (cond ((= n 0) b)
              ((even? n)
                (iter
                    a
                    b
                    (+ (* p p) (* q q))
                    (+ (* 2 p q) (* q q))
                    (/ n 2)))
              (else
                (iter
                    (+ (* a (+ p q)) (* b q))
                    (+ (* a q) (* b p))
                    p
                    q
                    (- n 1)))))
    (iter 1 0 0 1 n))

经过这样的优化以后,效率显著,对于n=300,000,python版仅需要不到0.04s,而Scheme版也仅需要0.12s即可得出结果。

p.s. 以上代码均经过测试。
Mar 8

test和bash的小坑 不指定

felix021 @ 2013-3-8 12:57 [IT » 软件] 评论(0) , 引用(0) , 阅读(4102) | Via 本站原创
昨天黄老湿问了我个问题, [ -e ] 是true还是false?为什么?

==== 啦啦啦啦啦的分割线,猜猜吧 ====

这种坑题显然只能实践出真知:
引用
$ [ -e ] && echo yes || echo no 
yes

果然坑了。

仔细想想,这个问题其实还是来源于实践的,比如一个很有可能会出现的写法是:
引用
[ -e $somefile ] && do_sth || do_sth_else

显然,在这个情况下,如果$somefile意外地是一个空串的话,bash实际上执行的就是 [ -e ] (这个可以很容易地验证),于是返回了 true。

简单过了一下源码(coreutils/src/test.c),可以看到执行流是
value = posixtest(argc - 1 <as> nargs);
    switch(nargs)
        case 1: //只有一个参数
            return one_argument();
                return argv[pos++][0] != '\0';  //检查不为空串
        case 2: //只有俩参数
            return two_arguments();
                if (argv[pos] 是 - 开头 <且> 只有俩字符 <且> 是unary_operator)
                    return unary_operator()
                        switch(argv[pos][1]):
                            case 'e':
                                unary_advance() //里面pos加了2
                                return stat(argv[pos-1], &stat_buf) == 0;
        case .. //更多参数
test_exit(value ? TEST_TRUE : TEST_FALSE);

也就是说对于只有一个参数的情况下,test只是简单地判断这个参数是否为空(无论是不是它支持的操作符),有两个参数的情况,才会去判断是否是合法操作符,再执行相应的检测。

然后才想起来,原来我还可以看manual啊,泪流满面。。。man test,果然看到这几行:
引用
-n STRING
      the length of STRING is nonzero

STRING equivalent to -n STRING

也就是说 test STRING 等于 test -n STRING ,检查非空串,于是 [ -e ] 就等于 test -n "-e",自然就是true了。。。

对于上面提到的情况来说,解决办法是在引用变量的时候,记得加上双引号,这样test就会收到2个参数,其中第二个参数是空串,stat出错,于是就可以得到(可能原先)期望的结果了:
引用
$ [ -e "$somefile" ] && echo yes || echo no
no

不过话说回来,bash脚本中引用不存在的变量这件事情本来就不应该发生,类似 rm -rf $some_path/ 这样的悲剧也不是没有发生过,但是bash又没有一个 explicit 模式,所以只能自己在使用之前检测了。

通常检测一个变量是否为空,用上面的 test -n "$VAR" 或者 test -z "$VAR" 即可(注意引号),但是如果要检测某个变量是否根本不存在,BASH却没有内建方法,只能通过这种看起来很奇怪的方式(出自stack overflow):
if [ -z "${VAR+xxx}" ]; then echo VAR is not set at all; fi

//本博客3月份真高产。。。
Mar 7

Python int缓存的那点事[续] 不指定

felix021 @ 2013-3-7 02:57 [IT » Python] 评论(0) , 引用(0) , 阅读(3139) | Via 本站原创
上一篇 说到,对于这样的一段代码:
a = 257
b = 0x101
print a is b

Python解释器会为 a 和 b 各 创建一个 PyIntObject (通过修改PyInt_FromLong打印int的id可以看出来),但是在实际的执行中,a和b却指向了同一个PyIntObject。也就是说,在执行之前,a和b已经被映射到了同一个PyIntObject。

前面说了,Python的解释执行是由以下调用链组成的:
引用

PyRun_FileExFlags()
    mod_ty *mod = PyParser_ASTFromFile() //把py源码转换成AST(Abstract Syntax Tree)
    run_mod(mod, ...) //执行AST
        co = PyAST_Compile(mod, ...) //将AST转换成CFG(Control Flow Graph) bytecode
            PySymtable_Build() //创建符号表
            co = compiler_mod() //编译ast为bytecode
        PyEval_EvalCode(co, ...) //执行bytecode
            PyEval_EvalCodeEx()

由于没有编译原理的基础,只能从全局上看出这些代码都做了什么,但是却很难从细节上去追查。通过修改源码我尽可能了解了 PyParser 将Python源码转换成AST的运行机制(虽然还是没有看懂tokens->cst的转换),但是run_mod的细节实在是看不懂了。于是我在StackOverflow上面提了一个问题,@Bakuriu大牛给了个hint,说是PyCompiler在处理lambda的时候,使用 compiler_add_o() 来将lambda对应的函数的__doc__设置为 PyNone:
/* Make None the first constant, so the lambda can't have a
  docstring. */
if (compiler_add_o(c, c->u->u_consts, Py_None) < 0)
    return 0;

这里头PyNone是常量,而且又出现了 c->u->u_consts ,大有看头。

有了线索以后,突然一切都变得清晰了,简单加了些代码追,可以发现对于上面给出的代码, compiler_mod 是这样处理mod_ty *mod(也就是那棵AST)的:

引用
compiler_mod(compiler *c, mod_ty *mod)
    case Module_kind: //mod->kind = 1
        compiler_body(c, mod->v.Module.body <as> stmts)
            for (i = 0; i < asdl_seq_LEN(stmts); i++) //循环3次,因为有3个stmt
                VISIT(c, stmt, asdl_seq_GET(stmts, i)) //宏展开到compiler_visit_stmt
                    compiler_visit_stmt(c, asdl_seq_GET(stmts,i) <as> s)//访问每个stmt
                        case Assign_kind: //第一个stmt的kind = 5,表示一个赋值操作
                            //赋值操作允许 a = b = 1 所以看起来有点罗嗦,
                            //它会被解析成如下AST:
                            //Assign([AssName('a', 'OP_ASSIGN'),
                            //      AssName('b', 'OP_ASSIGN')], Const(1))
                            n = asdl_seq_LEN(s->v.Assign.targets);
                            VISIT(c, expr, s->v.Assign.value);
                            for (i = 0; i < n; i++) {
                                if (i < n - 1)
                                    ADDOP(c, DUP_TOP);
                                VISIT(c, expr, asdl_seq_GET(s->v.Assign.targets, i));
                            }

简单解释下Assign操作的代码:
    1. 获得赋值目标的数量(比如a=b=1,就是2个)
    2. "VISIT"要赋的值
    3. 挨个ADDOP(c, DUP_TOP)是告诉编译器,增加一个OPCODE=DUP_TOP

DUP_TOP 是 Duplicates the reference on top of the stack 的简写,意思是取得上次计算的值(比如对于b,就是int(1)的reference,而对于a,就是b=1的返回值,也就是b的reference)加入stack_top,这样正好把多个赋值操作串起来。

不过我关注的主要是第二条,对应的代码就是:

引用
VISIT(c, expr, s->v.Assign.value); //宏展开到compiler_visit_expr
    compiler_visit_expr(c, s->v.Assign.value <as> e)
        case Num_kind: //e->kind = 16
            ADDOP_O(c, LOAD_CONST, e->v.Num.n, consts) //宏展开到compiler_addop_o
                //这里e->v.Num.n是在CST->AST的过程中生成的PyIntObject
                //下面的c->u->u_consts是一个PyDictObject,用来保存常量对象
                compiler_addop_o(c, LOAD_CONST <as> opcode,
                                c->u->u_consts <as> dict, e->v.Num.n <as> o)
                    arg = compiler_addop_o(c, dict, o)//塞入dict
                    compiler_addop_i(c, opcode, arg) //将插入顺序作为opcode的oparg


这个compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)的作用是将一个变量o及其type组成的tuple(o, o->ob_type)塞入到dict中。但是并不是简单暴力地直接插入,它的源码大约是这样的:

static int
compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)
{
    PyObject *t, *v;
    Py_ssize_t arg;

    if (PyFloat_Check(o)) {
        //省略部分与int无关的代码
    }
    else {
        t = PyTuple_Pack(2, o, o->ob_type); //t = tuple(o, type(o))
    }

    if (t == NULL)
        return -1;

    v = PyDict_GetItem(dict, t); //看看t是否已经在dict中出现过
    if (!v) { //如果没有
        arg = PyDict_Size(dict); //获取dict的当前大小(PyIntObject)
        v = PyInt_FromLong(arg);
        if (!v) {
            Py_DECREF(t);
            return -1;
        }
        if (PyDict_SetItem(dict, t, v) < 0) { //dict[(o, type(o))] = v
            Py_DECREF(t);
            Py_DECREF(v);
            return -1;
        }
        Py_DECREF(v);
    }
    else
        arg = PyInt_AsLong(v); //如果出现过,取得之前设置的v
    Py_DECREF(t);
    return arg;
}


这个代码乍看挺诡异的,因为还与后续编译成字节码的部分有所耦合,这里大致解释一下:

(1) 对于LOAD_CONSTS, 在compiler_visit_expr里面已将dict指定为c->u->u_consts,也就是专门用来存放常量的dict
(2) 所有常量都是用 (o, type(o)) 作为 key 存进去的,并返回顺序递增的编号v,表示o是第v个存进去的常量
(3) dict是个hash表,所以往dict里面塞东西时要计算key的hash
(4) tuple的hash值是将每个元素的hash值组合起来哈希(详见tuplehash函数),类似于sdbmhash或者jshash
(5) int对象的哈希是针对int的值,int对象比较时仅比较它们的值

    尽管 a 和 b 对应的key (a, int)和(b, int)虽然不是同一个对象,但是它们的哈希值是一样的!并且!PyDict_GetItem()查找到某个slot去比较key的时候,递归地去比较key的每一个元素,而两个int的比较,“正好”是比较它们的值是否相等!

    所以,在遍历AST生成bytecode之前,两个相同的const只会在c->u->u_consts中出现1次。

    在compiler_mod函数的末尾有一个assemble(c, addNone),它是将前面生成好的opcode等数据转换成最终的bytecode,其中一些代码逻辑是这样的

        assemble(c, addNone)
            struct assembler a;
            完成一些初始化
            makecode(c, &a);
                PyObject *tmp = dict_keys_inorder(c->u->u_consts, 0); //convert to Tuple
                consts = PySequence_List(tmp); //convert to List
                ...
                PyCodeObject *co = PyCode_New(..., consts, ...);
                    co->co_consts = consts


    也就是说,这里把保存所有常量的 c->u->u_consts 按照插入元素的顺序将所有塞进来的PyObject逐个插入到 consts 里,并最后赋值给PyCodeObject的PyListObject *co_consts。而在最最后的eval环节,LOAD_CONST这个opcode会将它的oparg(就是前面 compiler_addop_i 塞进去的值,也就是compiler_addop_o返回的值)作为索引,从co_consts里取出来,PUSH到栈顶(参见Python/ceval.c +1123行),供下一个指令读取。

    于是int常量整个python的解释执行所经历的步骤都完整地串起来了。

    泪流满面,居然看懂了。
分页: 9/95 第一页 上页 4 5 6 7 8 9 10 11 12 13 下页 最后页 [ 显示模式: 摘要 | 列表 ]