2011年3月24日星期四
[Java Script]用递归方式绘制树
2010年12月30日星期四
别了,2010!
2010年6月25日星期五
感慨一下自己的吉他水平
2010年6月19日星期六
GTK+ OpenGL Extension 折腾日记
这套系统的作用就是根据传感器的输出数据来判定传感器所依附物体的姿态,然后在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日星期五
递归调用背后的玄机
函数调用是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
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.
2010年4月16日星期五
OpenWrt岁月(一)
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..)
