Felix021

本来这篇应该很早就写的，一直偷懒。今天简单记录一下吧。

其实很早就想买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了：


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

后记@2014.10.12

//from https://www.miniand.com/forums/forums/2/topics/82?page=9

#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. 在新页面里修改生日。

应该朋友要求已将操作视频录像，有兴趣的可以在 优酷 观看，或者从 百度网盘、 微云 下载，瞧瞧看看苹果的服务有多么不堪。

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:

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:

and two more lines were added to the error.log:
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:

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.

在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重复平方算法来实现，提高效率。

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

同样O(log(n))的递归算法其实很容易理解：

但是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 。

于是实现就容易了：


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

最近在看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开始算起）

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

因此需要改成迭代版，使用 (a, b) <- (a + b, a) 这样的方式。

虽然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](T[pq](a, b)) （即对(a, b)进行两次T[pq]变换），可以得到

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

给出了算法以后，代码就容易写了：

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

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

昨天黄老湿问了我个问题， [ -e ] 是true还是false？为什么？

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

这种坑题显然只能实践出真知：
果然坑了。

仔细想想，这个问题其实还是来源于实践的，比如一个很有可能会出现的写法是：
显然，在这个情况下，如果$somefile意外地是一个空串的话，bash实际上执行的就是 [ -e ] （这个可以很容易地验证），于是返回了 true。

简单过了一下源码(coreutils/src/test.c)，可以看到执行流是

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

然后才想起来，原来我还可以看manual啊，泪流满面。。。man test，果然看到这几行：
也就是说 test STRING 等于 test -n STRING ，检查非空串，于是 [ -e ] 就等于 test -n "-e"，自然就是true了。。。

对于上面提到的情况来说，解决办法是在引用变量的时候，记得加上双引号，这样test就会收到2个参数，其中第二个参数是空串，stat出错，于是就可以得到（可能原先）期望的结果了：
不过话说回来，bash脚本中引用不存在的变量这件事情本来就不应该发生，类似 rm -rf $some_path/ 这样的悲剧也不是没有发生过，但是bash又没有一个 explicit 模式，所以只能自己在使用之前检测了。

通常检测一个变量是否为空，用上面的 test -n "$VAR" 或者 test -z "$VAR" 即可(注意引号)，但是如果要检测某个变量是否根本不存在，BASH却没有内建方法，只能通过这种看起来很奇怪的方式（出自stack overflow)：

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

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

前面说了，Python的解释执行是由以下调用链组成的：

由于没有编译原理的基础，只能从全局上看出这些代码都做了什么，但是却很难从细节上去追查。通过修改源码我尽可能了解了 PyParser 将Python源码转换成AST的运行机制（虽然还是没有看懂tokens->cst的转换），但是run_mod的细节实在是看不懂了。于是我在StackOverflow上面提了一个问题，@Bakuriu大牛给了个hint，说是PyCompiler在处理lambda的时候，使用 compiler_add_o() 来将lambda对应的函数的__doc__设置为 PyNone:
这里头PyNone是常量，而且又出现了 c->u->u_consts ，大有看头。

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


简单解释下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，这样正好把多个赋值操作串起来。

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



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



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

(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，其中一些代码逻辑是这样的



    也就是说，这里把保存所有常量的 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的解释执行所经历的步骤都完整地串起来了。

    泪流满面，居然看懂了。

1. Python的除法

线上有一个简单的函数，运行一年多了，作用是把"分"表示的字符串转成"元"：
看起来也的确是没有什么问题，但是就这么简单的一点代码，它还是错了，原因是fen_to_yuan("-270")居然返回了"-3.30"！坑爹啊。简单测试一下，原来是这样：
所以只好蛋疼地修改成这样：

2. 线上有一个脚本，要得到上个月的月份，bash的实现就是

看起来也的确是没有什么问题，但是就这么简单的一点代码，它还是错了，原因是对于10月31号居然返回了10！坑爹啊。简单测试一下，原来是这样：
也就是说，先把月份减一，然后检查日期，超过当前月，再向上修正月份，再向上修正年份。

所以只好蛋疼地修改成这样：

#update: @whusnoopy补充说 向后查看1个月也会有这样的情况，总之记得用月来算是有坑的，千万注意。

3. crontab的小坑

crontab默认是不会读取.bashrc，需要自己去source一下.bashrc，并且不支持像bash一样用反引号来启动一个子命令（这个结论是错的，是因为%前面忘了加斜杠）。这个不展开细说了，有兴趣的试试吧。