Felix021

1. 虽然都用 -lpthread 来链接到 libpthread.so ，但是实际上 pthread 是POSIX规范规定的接口，不是某一个库的名字。不同的类Unix系统在底层对pthread的实现不一样。

2. 在Linux的实现里，每个pthread线程都对应一个LWP（light weight process）；而LWP是由内核线程支持的，由内核统一调度，所以每个pthread线程都有对应task_struct，以及对应的tid（不是pthread_self()返回的那货，而是类似于pid），所以效率就不会太高（因为切换什么的都要回到内核里，而syscall的效率……），而且对应地，还要消耗内核线程的栈空间等资源，所以效率不会很高。

3. man gettid可以看到这个syscall是在 sys/types.h 里，但是实际上在我的ubuntu 12.04, kernel 3.2.0上面没有，需要这样：

不加上的话，结果就是 error: ‘gettid’ was not declared in this scope

4. 每个线程都有单独的cpu_affinity，通过 pthread_setaffinity_np, pthread_getaffinity_np 来读写。

5. Linux下，在 /proc/[PID]/task 下面包含了进程的所有线程的相关信息，每个线程一个目录，目录名就是线程的ID；每个线程的相关信息与进程类似，：


5. 每个线程可以被调度到不同CPU上面，类似于进程的/proc/PID/stat文件，线程当前运行的CPU ID保存在对应目录内的stat文件中第39个字段：


6. 可以用ps的 L 和 F 参数列出所有的LWP：

其中LWP列就是LWP的id，PSR是processor，也就是CPU ID。

p.s. 另外有个GNU PTH，这个是 n:1 的，纯用户空间完成调度的线程库，POSIX兼容。

今天看到80386+里 BSF/BSR 这对指令貌似挺有意思，Bit Scan Forward/Reverse，它们的作用是正向/逆向扫描一个WORD(16bit)/DWORD(32bit)，找出第一个等于1的bit编号。比如对于BX=0x1010，执行 BSF CX, BX 得到的CX=4，而 BSR CX, BX 得到的CX=12。

咋一看是个神器啊。《编程之美》什么的，不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位，秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期，不过这里的数据指出，在80486+，BSF需要6～43个时钟周期才能完成（BSR则需要6～104个clocks），也就是说，它似乎并没有被特别优化，而是使用了CPU内的微码来完成循环，所以不要指望能带来性能上的BONUS，详情可参见这篇：求整数中比特为1的二进制位数。

这篇文章里面给出的用上BSF/BSR的代码是：

想试试这段代码，不过蛋疼的是这是VS的汇编语法，GCC不能识别，于是终于下了决心翻出GCC-Inline-Assembly-HOWTO，看了下，其实也不是很复杂，简单改了下，变成这样：

跑了一下，果然效率不行，跟最差的直接循环在同一个量级。

仔细看了下代码，发现这里用的是BSR，而且还用上了n和count两个变量，感觉不太爽，于是完全改成汇编，写成这样：

结果。。。基本没变。嗯，所以就这样吧。。。

原文: 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 消除和错误纠正

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

其实很早就想买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. 以上代码均经过测试。