Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

Libpcap试玩

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

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,

开始写博客

我开始在这写博客了。

这个博客专注在技术方面,C++,Linux,等等,务求原创,务求深度。

可能还会有一些文字。

早于此的,是从cnblogs上迁移过来的文章,基本写于学生时期。

圆形坠落模拟算法设计

目标:实现一个算法,模拟在一个封闭二维区域,圆形小球朝给定方向坠落的过程,实现二维区域的紧密填充。

像下面这样:

难点,及其简单解决:

1.如何把粒子移动尽可能远?

图中的粒子i,能往下移动多远?一般情况,碰撞?边界?

一个简单解法:

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

本文译自 “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);
    };
});

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

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

先介绍应用背景:

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

其计算模式举例如下:

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

2.根据某些物理公式,算出几个新的量,如转速 n=33.9sqrt(kv2φ2rb2/D2(u23)/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这样的一条条边练成,当一个点被赋予值,从这点荡出一圈圈涟漪,传到它的下一级,再从更新过的点荡出新的波纹,传开,传开。。。直到所有的点都收敛,水面恢复宁静。

 

sicp练习2.42 [解8皇后问题的Scheme语言实现]

代码框架来自sicp 练习2.42。算是作业吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
(define (enumerate-interval l r)
  (if (= l r)
      (list l)
      (cons l (enumerate-interval (+ l 1) r))))

;(enumerate-interval 1 10)

(define (contains? e pl)
  (if (null? pl)
      #f
      (or (eq? e (car pl))
          (contains? e (cdr pl)))))

;检查形如(2 1 4 3 2)这样的positions list中有没有重复元素,简单办法,hash会是更好的办法。
(define (no-repeat? positions)
  (if (null? positions)
      #t
      (and (not (contains? (car positions) (cdr positions)))
           (no-repeat? (cdr positions)))))

;(no-repeat? '(1 2))
;(no-repeat? '(1 2 1))

;按理说应该检查一下rest-of-queens是不是length = (- k 1)...
;使用cons可以想象成把所有列往右移一列再把新的添到第一列,这样不影响safe?的判断,简单。
(define (addjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

(define (flatmap proc seq)
  (foldr append () (map proc seq)))

(define (safe? k positions)
  ;两个点在对角线上,也就是满足同一个方程x+y=n或x-y=n
  ;所以要判断两个点是不是在同一条“左下至右上对角线”上,
  ;只需要算出两个x-y,判断是否相等即可。左上至右下同理。
  (define (px-y pl)
    (map + positions (enumerate-interval 1 k)))
  (define (px+y pl)
    (map - positions (enumerate-interval 1 k)))
  (and
   (no-repeat? positions);不在同一行
   (no-repeat? (px-y positions));不在同一条“左下至右上对角线”上
   (no-repeat? (px+y positions));不在同一条“左上至右下对角线”上
   ))

;(safe? 1 '(1))
;(safe? 2 '(1 2))
;(safe? 3 '(1 2 3))
;(safe? 4 '(3 1 4 2))
;(safe? 4 '(2 4 1 3))

;层次遍历状态空间树,剪掉每一层中不合适的分支后再扩展到下一层。
(define (queens board-size)
  (define empty-board ())
  (define (queen-cols k)
    ;一个布局表示成一个list,形如(2 4 1 3),表示第一列为2,第二列为2,第三列为1...
    ;queens-cols 返回((1,2,3)(2,1,3)(3,2,1))这样的布局组成的list
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (reat-of-queens)
            (map (lambda (new-row)
                   (addjoin-position new-row k reat-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

;(queens 4)
(queens 8)

符号求导,scheme实现

sicp练习2.57

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
(define variable? symbol?)
(define (same-variable? a b)
  (and (variable? a)
       (variable? b)
       (eq? a b)))

(define (sum-exp? exp)
  (and (pair? exp)
       (eq? (car exp) '+)))

(define (product-exp? exp)
  (and (pair? exp)
       (eq? (car exp) '*)))

(define (expon-exp? exp)
  (and (pair? exp)
       (eq? (car exp )'**)))

(define (** x n)
  (exp (* n (log x))))

(define (make-sum lst)
  (let ((num (foldl + 0 (filter number? lst)))
        (sym (filter (lambda (x) (not (number? x))) lst)))
    (if (= 0 num)
        (cond ((= (length sym) 0) 0)
              ((= (length sym) 1) (car sym))
              (else (cons '+ sym)))
        (if (= (length sym) 0)
            num
            (cons '+ (cons num sym))))))

;(make-sum '(0 0))
;(make-sum '(2 -2 3 -3 a b))
;(make-sum '(2 3))
;(make-sum '(2 -2 3 a 4 b))
;(make-sum '((+ a b) (+ b d)))
;(make-sum '((* a 0) (* 1 (+ 0 b x))))
;(make-sum '( (* a b) ) )
;(make-sum '(a b) )

(define (make-product lst)
  (let ((num (foldl * 1 (filter number? lst)))
        (sym (filter (lambda (x) (not (number? x))) lst)))
    (cond ((= num 0) 0)
          ((= num 1) (if (= (length sym) 1)
                         (car sym)
                         (cons '* sym)))
          (else (cons '* (cons num sym)))
          )))

;(make-product '(0 1 2))
;(make-product '(0 a b 1 c))
;(make-product '(0.5 2 a))
;(make-product '(0.5 2 a c (+ a c)))
;(make-product '(a b 1 3 -1 (* f va)))

(define (make-expon x n)
  (cond ((eq? n 0) 1)
        ((eq? x 0) 0)
        (else  (list '** x n))
        ))

;(make-expon 0 'a)
;(make-expon 0 0)
;(make-expon 'a 0)
;(make-expon 'a 'b)
;(make-expon 2 3)

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var)
             1
             0))

        ((sum-exp? exp)
         (make-sum
          (map 
           (lambda (x) (deriv x var))
           (cdr exp))))

        ((product-exp? exp)
         (let ((first (cadr exp))
               (second (make-product (cddr exp))))
           (make-sum (list 
                      (make-product (list first (deriv second var)))
                      (make-product (list (deriv first var)  second ))))
           ))

        ((expon-exp? exp)
         (let ((base (cadr exp))
               (n (caddr exp)))
           (make-product (list n
                               (make-expon base (make-sum (list n -1)))
                               (deriv base var) ))
           ))
        ))

(deriv '(+ a (+ a a) b a) 'a) ;4
(deriv 'a 'b) ;0
(deriv '(* a b x) 'a) ;(* b x)
(deriv '(* (+ (* a b) (* a c)) d) 'a) ;(* (+ b c) d)
(deriv '(* (+ a b c) (* a b b)) 'a) ;(+ (* (+ a b c) (* b b)) (* a b b))
(deriv '(** x n) 'x) ;(* n (** x (+ -1 n)))
(deriv '(** (* 3 a ) n) 'a) ;(* n (** (* 3 a) (+ -1 n)) (* 3))

Church计数

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
;Church计数

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
(define (show-num n)((n (lambda (x) (+ 1 x))) 0))
(define (add a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

(show-num zero)
(show-num one)
(show-num two)
(newline)
(show-num (add-1 zero))
(show-num (add-1 (add-1 zero)))
(show-num (add-1 (add-1 (add-1 zero))))
(show-num (add-1 (add-1 (add-1 (add-1 zero)))))

(newline)
(display "my add\n")
(show-num (add zero zero))
(show-num (add (add-1 zero) (add-1 zero)))
(show-num (add (add-1 zero) (add-1 (add-1 zero))))

(define (multi a b)
  (lambda (f)
    (lambda (x)
      ((a (b f) ) x))))

(define (expon a b)
  (lambda (f)
    (lambda (x)
      (((a b) f)  x))))

(show-num (multi two two))
(show-num (multi (add one two) two))

(show-num (expon two two))
(show-num (expon (expon two two) two))

 

Church计数,通过(lambda (f))把f作为参数,这样f就不会被求值,而f的执行次数就代表了数字。

lambda中的形参其值是未知的,所以不会被求值。

形参好比糖果的包装纸,要把一段代码包起来,把它放到一个匿名函数里就行了

比如有一个函数

(lambda (a b) (+ a b))

要把它包装起来,可以写成

(lambda (x) (lambda (a b) (+ a b)) )

要剥开糖纸,传个参数就行了。

Church计数就是这个思想。

show-num用来把Church计数方式的数字转换成普通数字。

jdbc使用DataSource连接mysql,postgresql,oracle的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.sql.Connection;
import java.sql.ResultSet;
import java.sql.ResultSetMetaData;
import java.sql.SQLException;
import java.sql.Statement;

import org.postgresql.ds.PGSimpleDataSource;

import oracle.jdbc.pool.OracleDataSource;

import com.mysql.jdbc.jdbc2.optional.MysqlDataSource;

public class DBConnection {

    /**
     * @param args
     * @throws SQLException
     */
    public static void main(String[] args) throws SQLException {
        // TODO Auto-generated method stub
        MysqlDataSource mysqlDataSource = new MysqlDataSource();
        // mysqlDataSource.setPassword("dev");
        // mysqlDataSource.setUser("dev");
        mysqlDataSource
                .setURL("jdbc:mysql://localhost/forJava?user=dev&#038;password=dev");
        Connection conn = mysqlDataSource.getConnection();
        Statement stmt = conn.createStatement();
        stmt.executeUpdate("create table if not exists web\n" + "(\n"
                + "        id int not null primary key,\n" + "        name varchar(100),\n"
                + "        created timestamp,\n" + "        content blob\n" + ");\n" + "");
        for (int i = 0; i &lt; 1; i++) {
            stmt.executeUpdate("insert into web (name,content) values ('HL','frgertrhrtnthtohioh')");
        }
        showResultSet(stmt.executeQuery("select * from web limit 10"));

        // Driver driver = new com.mysql.jdbc.Driver();
        // driver.connect("jdbc:mysql://localhost/forJava?user=dev&#038;password=dev",
        // null);

        PGSimpleDataSource pgSimpleDataSource = new PGSimpleDataSource();
        pgSimpleDataSource.setServerName("localhost");
        pgSimpleDataSource.setDatabaseName("dev");
        pgSimpleDataSource.setUser("dev");
        pgSimpleDataSource.setPassword("dev");
        conn = pgSimpleDataSource.getConnection();
        // conn =
        // DriverManager.getConnection("jdbc:postgresql://localhost/test",
        // "dev", "dev");
        showResultSet(conn.createStatement().executeQuery("select * from cities"));

        OracleDataSource oraDataSource = new OracleDataSource();
        // oraDataSource.setServerName("127.0.0.1");
        // oraDataSource.setDatabaseName("HR");
        // oraDataSource.setUser("HR");
        // oraDataSource.setPassword("HR");
        oraDataSource.setURL("jdbc:oracle:thin:hr/hr@//localhost:1521/XE");
        conn = oraDataSource.getConnection();
        stmt = conn.createStatement();
        stmt.execute("select * from tab");
        showResultSet(stmt.getResultSet());
        stmt.execute("select * from jobs");
        showResultSet(stmt.getResultSet());
        stmt.execute("select * from DEPARTMENTS");
        showResultSet(stmt.getResultSet());
    }

    static void showResultSet(ResultSet resultSet) throws SQLException {
        ResultSetMetaData resultSetMetaData = resultSet.getMetaData();
        int num = resultSetMetaData.getColumnCount();
        while (resultSet.next()) {
            for (int i = 1; i &lt;= num; i++) {
                System.out.print(resultSetMetaData.getCatalogName(i) + " "
                        + resultSet.getString(i));
            }
            System.out.println();
        }
    }
}

呃,在自己电脑上同时安装了mysql, postgresql,oracle,db2,sqlite的人是不是很蛋疼?

Java多线程网页下载代码

小项目,练手的。

1.使用了java.util.concurrent包里的线程池,可以飙升到满带宽,在100M带宽上,可以达到10MB/s。

2.使用了java.nio里的channels,性能比自己缓冲有一些提高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.FileOutputStream;
import java.io.InputStream;
import java.net.URL;
import java.net.URLConnection;
import java.nio.channels.Channels;
import java.nio.channels.FileChannel;
import java.nio.channels.ReadableByteChannel;
import java.util.Calendar;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class HttpDownloader implements Callable {
    URLConnection connection;
    FileChannel outputChann;
    public static volatile int count = 0;

    public static void main(String[] args) throws Exception {

        ExecutorService poll = Executors.newFixedThreadPool(100);

        for (int i = 0; i &lt; 100; i++) {
            Calendar now = Calendar.getInstance();
            String fileName = "../data/" + now.get(Calendar.YEAR) + "年"
                    + (now.get(Calendar.MONTH) + 1) + "月"
                    + now.get(Calendar.DAY_OF_MONTH) + "日--" + i + ".txt";
            poll.submit(new HttpDownloader("http://www.sina.com",
                    (new FileOutputStream(fileName)).getChannel()));
        }

        poll.shutdown();

        long start = System.currentTimeMillis();
        while (!poll.isTerminated()) {
            Thread.sleep(1000);
            System.out.println("已运行"
                    + ((System.currentTimeMillis() - start) / 1000) + "秒,"
                    + HttpDownloader.count + "个任务还在运行");
        }
    }

    public HttpDownloader(String url, FileChannel fileChannel) throws Exception {
        synchronized (HttpDownloader.class) {
            count++;
        }
        connection = (new URL(url)).openConnection();
        this.outputChann = fileChannel;
    }

    @Override
    public String call() throws Exception {
        connection.connect();
        InputStream inputStream = connection.getInputStream();
        ReadableByteChannel rChannel = Channels.newChannel(inputStream);
        outputChann.transferFrom(rChannel, 0, Integer.MAX_VALUE);
        // System.out.println(Thread.currentThread().getName() + " completed!");
        inputStream.close();
        outputChann.close();
        synchronized (HttpDownloader.class) {
            count--;
        }
        return null;
    }
}