Month: February 2011

逆向工程

Posted on by hawk

上帝用祂的手编写了这个世界。

科学家们则辛勤地尝试将其逆向工程。

在一个不知道目标架构，源代码语言和编译方式的前提下。

=========

计算机绝不会发现，

他们其实被程序员的上帝之手所操纵。

因为他们生活在逻辑严格的自我证明的世界里。

=========

我们，能否发现构造我们的代码之源？

或者，我们只是悄悄地从生存走向毁灭。

车窗上的雨滴

Posted on by hawk

最近以来困扰我的一个物理小问题是如何通过车窗上的雨滴滑落的角度来估计车行速度。因为很不巧的是似乎每次我要旅行，就一定会下雨。所以我总是盯着这些斜斜落下的雨滴，困扰着。

我最初的想法很简单。就是考虑受力情况。水滴受到的重力和迎风力的合力，一定是沿着水滴滑落的方向。当然要考虑车窗的摩擦力，但是由于那个力一定跟合力的方向相反，所以不会影响夹角。也就是说，当水滴沿着45度滑落的时候，迎风力刚好等于重力。接着考虑动量和冲量关系。假设空气在时间t内撞击水滴的动量mv全都转化为推动水滴的冲量Ft。其实不然，因为空气推动水滴后会随水滴一同移动，而非耗尽全部动量。但是由于水滴在玻璃上的滑动速度非常慢，而空气的推动速度很快（这里是以车为参考系所以空气速度就是车速），我想即使忽略之也不会有太大的误差。然后我再近似认为水滴是长a宽b高c的长方体。其迎风面积为b·c。则方程如下，发现t正好可以消去。

    Ma = Va·ρa·t·b·c
    Ma·Va = F·t
    =>
    Va2·ρa·b·c = F

我们又假设F是水受到的重力

    F = Mw·g = a·b·c·ρw·g
    a·b·c·ρw·g = Va2·ρa·b·c
    Va2 = a·ρw·g / ρa

其中除了水滴的长度a只能猜测外，其他都是常量。水的密度差不多是空气的1000倍。g估算为10。水滴的长度估计为0.5cm也就是0.005m。则这个Va差不多是25km/h。

这个数值这么低，是因为我取的角度是45度。实际行驶的时候，雨滴几乎是横着划过玻璃。可惜我没有测量他的tan值。下次旅行假如我又遇到下雨就可以通过实际测量检验我的理论是否正确啦～

协程的C实现

Posted on by hawk

今天正好跟ownwaterloo聊到协程，于是查了查资料，顺便写个博客记录一下吧。

我主要参考的是这篇资料http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html，是Simon Tatham提出的一个协程的C实现，非常有意思。

协程的思想主要是为了解决多个任务如何分享CPU这个问题的。线程在很多协作问题上处理的不好，而且需要锁机制，导致运行缓慢，不易理解，容易出错。协程的思想是，一系列互相依赖的协程间依次使用CPU，每次只有一个协程工作，而其他协程处于休眠状态。与线程不同，协程是自己主动让出CPU，并交付他期望的下一个协程运行，而不是在任何时候都有可能被系统调度打断。因此协程的使用更加清晰易懂，并且多数情况下不需要锁机制（或者说他本身就是一个全局锁）。

Simon的举例是一个生产者消费者例子。传统的程序可能是生产者一个循环不断产生字符，之后退出。而消费者一个循环不断读取字符，并处理之。使用时或许会用一个管道，将生产者的输出重定向到消费者的输入。从而使两者协作。

Simon提出，如何使这样的简单任务无需通过管道这类操作系统相关的重型机制，就能完成。他提出，生产者或者消费者之间，有一方需要改变自己的工作模式。不再是在循环中不断处理任务，而是一次只处理一个字符然后立刻返回。而另一方依旧保持原状，只需在原本输出到或读取自标准IO的地方修改为调用对方的那个函数就可以了。

但这种写法难以维护。他提出了协程的概念，并期待写出类似这样的代码：

int function(void) {
    int i;
    for (i = 0; i < 10; i++)
        return i;   /* won't work, but wouldn't it be nice */
}

在这里return语句并不是终止函数，而是将函数转入睡眠的状态，并将CPU交付给另一个函数执行。例如生产者写入一个字符后，调用类似的return语句，交付消费者处理这个字符。稍后当消费者处理完并调用return语句后，能重新激活生产者协程，并继续这个for循环。

如何在C语言中实现这样的功能而不需使用汇编代码去hack堆栈和寄存器呢？他给出的最初的实现是使用goto语句。

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: goto LABEL0;
        case 1: goto LABEL1;
    }
    LABEL0: /* start of function */
    for (i = 0; i < 10; i++) {
        state = 1; /* so we will come back to LABEL1 */
        return i;
        LABEL1:; /* resume control straight after the return */
    }
}

巧妙的使用静态变量存储函数状态，并使用goto语句来继续for循环。但这种写法不够优美，于是又引入了Duff’s device。

switch (count % 8) {
        case 0:        do {  *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                       } while ((count -= 8) > 0);
    }

使用这种trick来将switch-case语句作为循环中的跳转。这就避免了goto-label语句需要同时维护goto和label两处代码的麻烦。于是前面的代码可以变成这个样子。

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: /* start of function */
        for (i = 0; i < 10; i++) {
            state = 1; /* so we will come back to "case 1" */
            return i;
            case 1:; /* resume control straight after the return */
        }
    }
}

他的文章后面还有一些内容，例如如何使用宏包装这套机制。如何使用__LINE__宏避免state被赋予相同的数值。如何避免多线程调用下干扰静态变量等等。我这里就不赘述了，大家有兴趣可参考原文。
总之读此文的两个收获一个是认识协程，一个是学习到了一种诡谲的C语言用法。非常开心。