libpcap试玩

2013-08-04
linux network

libpcap驱动了tcpdump,和wireshark这类抓包工具.提供了高度灵活的包过滤语言. 据wikipedia,高性能的包过滤最早是在bsd上作为一个问题被解决,被称为bpf,在内核实现了一个解释器,进行包匹配,用户态提供一个字符设备, linux作为后来者,支持与bsd基本相同的packet filter,称为lpf,不同的是,linux是通过在一个raw socket来支持包过滤的,通过setsockopt来SO_ATTACH_FILTER,挂载过滤器. strace 可知,libpcap实际上进行了如下syscall:

1
2

socket(PF_PACKET, SOCK_RAW, 768) = 59 
setsockopt(59, SOL_SOCKET, SO_ATTACH_FILTER, "\1\0\0\0\0\0\0\0\250\327Vc\375\177\0\0", 16) = 0

libpcap的api文档和demo代码可以参见

  1. http://www.tcpdump.org/pcap3_man.html
  2. http://www.tcpdump.org/sniffex.c

参考文档了demo,我写了一个小的sniffer,

阅读更多

[翻译]轻松7步，导出Y结合子

2012-04-09
translate scheme

本文译自 “Deriving the Y Combinator in 7 Easy Steps“，

原文链接：http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html

在没有原生递归支持的语言中，Y结合子（Y Combinator）是一种实现递归的方式（事实上，它更常被作为一种锻炼程序思维的方式）。要实现Y结合子，要求这种语言支持匿名函数。

此处，我选择JavaScript来推导Y结合子，从递归阶乘函数的定义开始，一步一步进行变换。

Step 1

最初的实现，使用JavaScript内建的递归机制。

1
2
3
4

var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};

 

Step 2

获得递归的最简单方法是什么？我们可以定义一个函数，它接受它自身作为参数，并且用这个参数作为参数，调用这个参数。当然，这是一个无限循环，会导致栈溢出。

1
2
3
4
5

(function (f) {
    f(f);
})(function (f) {
    f(f);
});

我们的阶乘函数套用上面的模板，再做点改动，阶乘函数接受一个我们还不知道的参数，所以我们要的是返回一个接受该参数的函数。然后这个函数可以被用于计算阶乘。同时，这可以让我们的阶乘函数不会无限循环下去。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

var fact = (function (f) {
    return function (n) {
        // 终止条件
        if (n < 2) return 1;

        //因为f返回一个函数，所以这有一个双重调用。 
        return n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
        // 终止条件
        if (n < 2) return 1;

        // 因为f返回一个函数，所以这有一个双重调用。
        return n * f(f)(n - 1);
    };
});
阅读更多

一个基于约束传播的微型计算语言的设计和实现

2012-04-09
scheme python

一个基于约束传播的，玩具级微型计算语言的设计和简单实现。

这个程序就是做来玩和练习的，代码是玩具级别的，用的python，基本可以正常工作了。

先介绍应用背景：

在流体机械设计中，通常根据性能参数进行设计，算出其它变量，但问题是，在设计过程中，需要进行变量的手工调整，例如圆整，修正到某一范围，校核等等。

其计算模式举例如下：

1.定义变量，如输入压力Pin=0.98，输入温度Tin=27,输入流量Qvin=400,kv2，φ2r，b2，D2，u2，qin等等。。。

2.根据某些物理公式，算出几个新的量，如转速 n=33.9*sqrt(kv2*φ2r*b2/D2*(u2^3)/qin)

3.把n从8296.93圆整为整数8300，

4.重新计算b2/D2=0.06455，校核可知0.02<0.06455<0.065，符合要求

5.根据n计算出其它新的变量，修正，校核。。。

。。。

观察可以发现，这种计算模式，和《计算机程序的构造与解释》中提到的约束传播系统很像，如果把一个变量看作一个对象，那么，当它位于一个公式的左侧，例如n，也就意味着，右侧变量例如kv2更新时，应该给它发送一个消息，让它重新计算自己的值，当n更新后，如果它发现有别的变量依赖于自己，它应该发消息通知它们更新自己的值。

还可以看出，这种依赖关系形成了一个图，例如应该有一条从kv2到n的边，把n称为kv2的订阅者。

所以这种计算模式可以用约束传播系统建模，但是此处和书里的约束传播系统有差异：此处的约束传播系统是有向图，而书里是无向图，设计成有向图主要是为了简单，无向图的消息发送顺序是难以控制的，而且构造的时候公式中的每个变量都要持有其它对象的引用，太麻烦，有向图只需要在公式左侧的那个变量哪里保存公式右侧的每个变量的引用。

形成有向图后，每个变量的状态设为invaild，这种状态下，不会向它的会订阅者发送更新消息，收到获取值的消息时报错。

有向图中，还有一些源点，是最初给定值的变量。

当某个变量被赋值时，它把自己设为新值，同时向它的订阅者发送更新消息。订阅者计算自己的新值，如果和旧值相同，就沉默；否则，更新自己，通知订阅者更新。

so，想象一下，在你的面前，虚空之中漂浮着一张有向图， 由kv2—>n这样的一条条边练成，当一个点被赋予值，从这点荡出一圈圈涟漪，传到它的下一级，再从更新过的点荡出新的波纹，传开，传开。。。直到所有的点都收敛，水面恢复宁静。

 

阅读更多