2011年3月24日星期四

[Java Script]用递归方式绘制树

topology_array数组对象中存有一棵树所包含节点父子关系,通过get_topology_html生成jquery树插件所需HTML代码,最终实现树的绘制。

var topology_array = new Array(
// "switch", "designated switch", "if-traversed"
["ANDERS", "ROOT", 0],
["CINDY", "ANDERS", 0],
["DAVID", "ANDERS", 0],
["ERIC", "ANDERS", 0],
["FRANK", "ANDERS", 0],
["BILL", "ROOT", 0],
["GATES", "BILL", 0],
["HAVORD", "BILL", 0],
["IAN", "BILL", 0],
["JACK", "BILL", 0],
["KARAN", "CINDY", 0],
["LERRY", "KARAN", 0],
["MIKE", "LERRY", 0],
[ 0, 0, 0]
);

function sub(data, node)
{
for (i = 0; i <> if(data[i][1] == node && data[i][2] != 1) {
//alert(data[i][0]);
data[i][2] = 1;
return data[i][0];
}
}
return -1;
}

function get_topology_html(data, root)
{
var ret;

while((ret = sub(data, root)) != -1) {
topology_html += "<><>";
topology_html += ret;
get_topology_html(data, ret);
topology_html += "< /li >< /ul >";
}
}



2010年12月30日星期四

别了,2010!

高涨的房价,滋生的草根研究投资/经济的冲动。正所谓,初中研究中考;高中研究高考;大学研究就业。2010年作为P民的我实在没什么可以总结,没房的我还是总结总结房地产吧。

2010年的重大新闻
1 国资委:78家央企将退出房地产业务
央企是国家的嫡系部队,2010年主子让嫡系撤退。估计快撤退干净了。
2 银监会压力测试(假设房价未来跌去60%银行是否会死)
目前是地产绑架银行的局面,银监会提前尝试挥刀自宫,确认能否留有一个蛋来保证传宗接代。
3 存款保险制度(即将实现)
此制度规定如果银行破产储户最多获赔20万。无论你银行里有几个亿,对不起,只给20万。这是对那些有些土鳖钱但没能力把钱输送到瑞士银行的人群占有资本的一种掠夺。
4 房产税
2010年关于房产税的报道很多。正统消息,嫡系消息,小道消息。到处都是房产税的消息,但是还没落实。2010国家算是对房产税退出做个热身。目前看目的已达到,毕竟屁民不会对以后征收房产税莫名惊诧。
5 货币政策
上调准备金六次,年底加息二次。银行放贷开始谨慎,毕竟钱袋子钱不是很多。贷款的民众还款压力在逐步增加中。
6 十二五与政改
十二五规划中删除了以经济建设为中心。2010年算是一个变革的开始,换一个套路出牌,清洗改革开放30年来积累的种种矛盾,种种利益。


这些新闻很有趣,串起来逻辑是那么的强。我用阴谋论的思维小小解读一下:
在(6)这个动荡的时期,是最好的整合利益链条的时期。为了收编温州炒房团与利益集团构成的土鳖资本,以太子党为首的军队红色资本早早退出了房地产领域,并发文(1)另嫡系早早撤退,勿贪多恋战。知己知彼,百战不殆。红色资本用(2)来分析本方实力,力争在收编土鳖资本的时候不能废了自己的王子军团(银行),底线是至少留着一个蛋传宗接代。用(5)来移植土鳖资本发展壮大。(3)为一些王子阵亡做了相应的准备,实现有法可依,稳草民情绪。红色资本在围剿土鳖资本的同时为了地方财政弹药的充裕采取(4)来做粮饷补给。

从后勤保障,到敌我形式分析,都已经做了相当的准备。买不起房的不要J动,先保住饭碗,别死在金字塔尖的格斗中。最后用一个高人的话做结案陈词:

“过去几年里我一直在说,做自己看得懂的事情。本意是我相信一些事情迟早要来,但是时间点是我不能准且提早太多时间知道的。我之前只看见,一个又一个相关的配套在确立。我不停的和周围的人说风险与危机,也因此被很多人看作神经病。即使新一轮房产政策还会因为各种以而导致夭折。而这样的夭折在我看来,会次级更多严厉的政策博弈与更残酷与直接的手段来干预。其实温总在年初那句可以看作摊牌的话已经说的很明白了:这个是涉及政权稳定的问题了。”

别了,2010!

2010年6月25日星期五

感慨一下自己的吉他水平

http://v.youku.com/v_show/id_XMTkxNDMwMTY=.html
两年前我知道我吉他弹得很差,但是现在回顾一下两年前的作品,不由感概,现在水平更差了,汗!看来不管干什么,在知道自己水平差,也要留下当时的快照。因为日后很可能水平更差!真是逆水行舟,不进则退啊!

2010年6月19日星期六

GTK+ OpenGL Extension 折腾日记

最近在做一个姿态模拟系统,端午节前请Lynn帮我设计了传感器的PCB,昨天刚刚送去打板。今天早上又收到咸蛋帮我画了个3D Max的十字架。貌似万事俱备,就差我开工了!

这套系统的作用就是根据传感器的输出数据来判定传感器所依附物体的姿态,然后在PC上以3D效果显示出来。核心的东东就是一个姿态的识别算法,其他什么数据传输,图像显示都是绿叶。

由于软件是在Linux上编写,我采用了GTK+。为了显示3D效果,我google调查了一下,需要GTK+ OpenGL Extension。OK,问题就是找到3D Sample了。可是我下载GTK+ OpenGL Extension的Release版本1.2.0编译上就遇到了问题。gtkglext-1.2.0是2006年的版本,我现在用的GTK+还是比较新的版本,很显然gtkglext-1.2.0版本太老了。当时的思路是google解决掉所有出错点。经过一番恶战,我的确解决了编译的错误,但是运行起来依然有问题,总是说"gtkglext example 'GDK_IS_GL_DRAWABLE (gldrawable)' failed"。再google,貌似是gtkglext自己的问题。最后决定用git抓取最新版本。抓下来后configure那里又不过,晕死了!提示configure: error: Invalid target for GDK: use x11 or win32。怎么办呢?干脆Merge一下1.2.0和git的版本算了,我首先Merge了gtk/gtkglwidget.c,毕竟之前报错总来自这里。看来是人品爆发了,merge完这个文件,编译,执行再不出错了!哈哈!看来root cause找到了!Yeah!

GTK+ OpenGL Extension 的shapes例子还不错,可以3D显示并旋转一个茶壶,这正是我想要的东西^_^。



后记: 2011/08/10已经实现当时的想法,详见 AMCC 1.0 release


2010年6月11日星期五

递归调用背后的玄机

在函数调用前,首先要将被调用函数所需要的参数放入堆栈。然后执行汇编指令CALL进行函数调用,与此同时CALL下面一条指令的地址也压入到了堆栈中。当函数返回时,调用RET指令。RET指令会从堆栈中取出一个地址(CALL压入的地址),之后程序从这个地址继续向下执行。这样调用完函数还可以按照既定顺序去执行。

函数调用是A调用B,递归调用则是A调用A。递归调用和函数调用在堆栈的处理方式上是有区别的,只是我们平时不会用汇编去玩递归,很多堆栈操作都被Compiler代工。

下面是一段使用递归调用的C函数代码:
0001: void
0002: merge_sort(int array[], int p, int r)
0003: {
0004: int q;
0005:
0006: if (r > p) {
0007: q = (p + r) / 2;
0008: merge_sort(array, p, q);
0009: merge_sort(array, q + 1, r);
000a: merge(array, p, q, r);
000b: }
000c: }

反汇编(objdump -d)后函数代码如下:

0001 <merge_sort>:
0001: push %ebp
0002: mov %esp,%ebp
0003: sub $0x28,%esp
0004: mov 0x10(%ebp),%eax
0005: cmp 0xc(%ebp),%eax
0006: jle 8048691 <merge_sort+0x7f>
0007: mov 0x10(%ebp),%eax
0008: mov 0xc(%ebp),%edx
0009: lea (%edx,%eax,1),%eax
000a: mov %eax,%edx
000b: shr $0x1f,%edx
000c: lea (%edx,%eax,1),%eax
000d: sar %eax
000e: mov %eax,-0xc(%ebp)
000f: mov -0xc(%ebp),%eax
0010: mov %eax,-0x10(%ebp)
0011: mov -0xc(%ebp),%eax
0012: mov %eax,0x8(%esp)
0013: mov 0xc(%ebp),%eax
0014: mov %eax,0x4(%esp)
0015: mov 0x8(%ebp),%eax
0016: mov %eax,(%esp)
0017: call 8048612 <merge_sort>
0018: mov -0xc(%ebp),%eax
0019: lea 0x1(%eax),%edx
001a: mov 0x10(%ebp),%eax
001b: mov %eax,0x8(%esp)
001c: mov %edx,0x4(%esp)
001d: mov 0x8(%ebp),%eax
001e: mov %eax,(%esp)
001f: call 8048612 <merge_sort>
0020: mov 0x10(%ebp),%eax
0021: mov %eax,0xc(%esp)
0022: mov -0xc(%ebp),%eax
0023: mov %eax,0x8(%esp)
0024: mov 0xc(%ebp),%eax
0025: mov %eax,0x4(%esp)
0026: mov 0x8(%ebp),%eax
0027: mov %eax,(%esp)
0028: call 8048414 <merge>
0029: leave
002a: ret


分析:
1 C[0008]对应A[0017],可以看出A[000e~0016]是把参数array,p,q
压入堆栈,这和普通的函数调用相同。所以很显然,在 r > p 的情况下, C[0008]的持续执行,会导致堆栈中有很多组 array, p,
q,r变量。
2 C[0009]对应A[001f],C[0009]什么时候调用?答:C[0008]引起的调用违反条件(r >
p)后,C[0009]会被执行。A[0018~001e]在做什么?嗯,这就是递归调用的特殊一面,如果是正常函数调用,是不需要这段代码的。那到底A[0018~001e]在做什么?就是把堆栈里面之前保存的一组参数提取出来,然后再讲这组参数压入堆栈,为C[0009]调用做准备。你可能会想拿出来在放进去这不是瞎折腾吗?非也!我们从C代码角度看,提取步骤让局部变量(array,p,q,r)的值已经变成之前堆栈保存的那组数据了,这是重点。之后再把局部变量放入堆栈这是为了后续函数调用做准备。
3 C[000a]对应A[0028],C[000a]什么时候调用?答:道理同上。A[0020~0027]在做什么?道理同上,哈哈。
4 对A程序的疑惑,为什么上来只有push,没有看到pop?其实leave就完成了这个动作,请看注释2。

总结:
递归调用需要在汇编语言级别做特殊处理。对于特殊处理,直白点讲,就是把最后吃进去的给我吐出来。吐到哪里?吐到局部变量里。这样变量就来了一次超级大变身!!!

注释1:C[000a] 代表 C语言000a行;A[000a] 代表汇编语言000a行;
注释2:LEAVE : Set SP to BP, then pop BP.

2010年6月9日星期三

How to become a world-class programmer

If you want to be a good programmer, you just program ever day for two
years, you will be an excellent programmer. If you want to be a
world-class programmer, you can program every day for ten years, or
you can program every day for two years and take an algorithms class.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

2010年4月16日星期五

OpenWrt岁月(一)

由于鄙人不想只停留在交换机的开发路上而忘记摘采盛开的路由器野花,面对OpenWrt的诱惑,女朋友走后我和她亲密接触并放纵了几个夜晚(昨天从晚上8点奋战到了今天凌晨1点)。本想透过svn
co svn://svn.openwrt.org/openwrt/trunk/去抓取ING的她,不过却始终无法成功,不知道是否北G*.F$#W所为。无奈选择了http://downloads.openwrt.org/kamikaze/8.09.2/kamikaze_8.09.2_source.tar.bz2

#tar xvfj kamikaze_8.09.2_source.tar.bz2 ./*
#make menuconfig (Target System选择BCM947XX/953XX [2.6])
这个配置方案以下简称"她"
#make

基本上就是上面这几步骤,就可以把方案需要的bin档案生成了,档案放在./bin目录下。插一句:为了更了解她,我加入了一个她的QQ群,进去后我就出来了,里面很像华强北的商家,天天讨论的话题都是刷机刷机刷JJJJ,我当然要的不是刷JJ这么简单,我要了解她的灵魂。

在与她亲密接触的途中,我带着疑惑考察了下面几个要点。

一 Flash分区
嵌入式系统的Flash就像PC的硬盘。硬盘有分区,Flash也有分区。她给Flash分了4个区块,分别是bootloader(cfe),kernel(linux),root
file system(rootfs),configuration(nvram),详细见下面结构:

/build_dir/linux-brcm47xx/linux-2.6.25.20/drivers/mtd/maps/bcm47xx-flash.c
static struct mtd_partition bcm47xx_parts[] = {
{ name: "cfe", offset: 0, size: 0, mask_flags: MTD_WRITEABLE, },
{ name: "linux", offset: 0, size: 0, },
{ name: "rootfs", offset: 0, size: 0, },
{ name: "nvram", offset: 0, size: 0, },
{ name: NULL, },
};

看到上面是否觉得奇怪,为何offset和size都为0,my god~
我迷糊了,到底每个区块从哪里开始,多大尺寸啊!不过又仔细看了看bcm47xx-flash.c,原来里面有动态分析Flash的代码,然后填充了bcm47xx_parts[]
的 size 和 offset 变量。那么问题又来了:用什么方法分析的呢?原来她的Firmware文件采用TRX文件格式,动态解析TRX
Head就可以分析出个个区块的offset和size了,具体TRX结构的详细信息请参阅
https://forum.openwrt.org/viewtopic.php?id=6938

二 Root File System
在Kernel目录下的.config文件中找到了CONFIG_CMDLINE的定义:
CONFIG_CMDLINE="root=/dev/mtdblock2 rootfstype=squashfs,jffs2
init=/etc/preinit noinitrd console=ttyS0,115200"
所以她采用squashfs或jffs2来作为Root File
System,squashfs是read-only的文件系统,jffs2是r/w都OK的系统,如果你想在Router
Shell下用ipkg(轻量级包管理工具)来动态安装Package,那么推荐使用jffs2作为Root
FS,不过忧着点,Flash不是硬盘,没多少空间,动态df看看有多少结余,别纵欲过度。

三 启动流程
由于CONFIG_CMDLINE把init配置成了/etc/preinit,所以内核启动后会执行/etc/preinit,
preinit会做根文件系统的加载动作,然后执行/sbin/init。

/build_dir/mipsel/root-brcm47xx/etc/inittab
::sysinit:/etc/init.d/rcS S boot
::shutdown:/etc/init.d/rcS K stop
tts/0::askfirst:/bin/ash --login
ttyS0::askfirst:/bin/ash --login
tty1::askfirst:/bin/ash --login

/build_dir/mipsel/root-brcm47xx/etc/init.d/rcS
#!/bin/sh
# Copyright (C) 2006 OpenWrt.org

run_scripts() {
for i in /etc/rc.d/$1*; do
[ -x $i ] && $i $2 2>&1
done | $LOGGER
}

LOGGER="cat"
[ -x /usr/bin/logger ] && LOGGER="logger -s -p 6 -t sysinit"

if [ "$1" = "S" ]; then
run_scripts "$1" "$2" &
else
run_scripts "$1" "$2"
fi

看了inittab和rcS就很清楚了,接下来就是执行/etc/rc.d/S*,基本上就是初始化各种各样应用程序的脚本。

四 让我苦闷一晚的Web
在/etc/rd.d/下有一个文件叫S50httpd,是负责开启http server的脚本,她采用busybox内潜的httpd做http server
anders@ubuntu:~/share/openwrt/8.09.2/build_dir/mipsel/root-brcm47xx/usr/sbin$
ls -l
lrwxrwxrwx 1 anders anders 17 2010-04-16 14:21 httpd -> ../../bin/busybox
httpd是用www作为web目录的,于是我进入了www目录,发现里面竟然空空如野,WHY?她没有Web?那还玩个P :-(
不过,这么有名气的她,怎么可能没Web呢?上google搜索来搜索去都有web啊,为何我没有?(先讲讲五再回头说这个)

五 IPKG的包管理方式
In an OpenWrt firmware, almost everything is an .ipk, a software
package which can be added to the firmware to provide new features or
removed to save space. Note that packages are also maintained outside
of the main trunk and can be obtained from subversion using the
package feeds system:
$ ./scripts/feeds update
Those packages can be used to extend the functionality of the build
system and need to be symlinked into the main trunk. Once you do that,
the packages will show up in the menu for configuration. From kamikaze
you would do something like this:
$ ./scripts/feeds search nmap
Search results in feed 'packages':
nmap Network exploration and/or security auditing utility
$ ./scripts/feeds install nmap
To include all packages, issue the following command:
$ make package/symlinks

原来她有几个仓库,仓库里面有N多软件,web只是仓库的软件之一了,于是我用下面的方法安装了她的web:
anders@ubuntu:~/share/openwrt/8.09.2$./scripts/feeds update packages luci
anders@ubuntu:~/share/openwrt/8.09.2$./scripts/feeds install -a -p luci
anders@ubuntu:~/share/openwrt/8.09.2$make menuconfig
Administration
- LuCI Components
- luci-admin-full: M
anders@ubuntu:~/share/openwrt/8.09.2$make
anders@ubuntu:~/share/openwrt/8.09.2/build_dir/mipsel/root-brcm47xx/www$ ls
cgi-bin index.html luci-static resources


(To be continued..)