IF's :: Tag :: programming

哦对了，我的法线贴图做好了

看看这光影的变化，多漂亮啊：

其实那些凹凸并不在模型上，而只是通过一张图保存了平面的法线方向。

利用法线贴图上的法线信息计算光照的时候需要注意的是得要把它的坐标系（横着是 red, 竖着是 green, 立在平面上的是 blue）转换到空间上对应平面的坐标系中 —— 或者反过来，把光线和视线转换到法线平面的坐标系中（我就是这么做的），然后再那啥。

提一下，从网上搜到的信息来看这个的计算貌似挺复杂的，但是考虑线性变换其实也就是线性方程而已，从法线贴图的坐标系转换到空间坐标系，当前正在渲染的点所在的空间三角形的贴图的 u 坐标的正方向为 a，法向量为 n，不考虑位移（为什么可以不考虑位移？自己想），我们可以列出这么几个式子：

z = cross(a, n);

(1,0,0) -> (a.x, a.y, a.z)
(0,1,0) -> (n.x, n.y, n.z)
(0,0,1) -> (z.x, z.y, z.z)

 

有没有恍然大悟的感觉？

 

没有？再提示，设从法线贴图的坐标空间转换到空间三角形的坐标空间的矩阵为 M, 那么有

1,0,0            a.x, a.y, a.z
0,1,0  *  M  ==  n.x, n.y, n.z
0,0,1            z.x, z.y, z.z

好了，点到为止。

 

俺用的漫反射贴图是这样的：

漫反射贴图

法线贴图：

法线贴图

高光贴图：（虽然用了而且计算了，不过光源放的位置似乎不太恰当以至于完全看不到高光的效果，囧～）

高光贴图

可执行文件：

binary

 

源码……还是不给，因为写得丑了……

 

PS. 想要运行着玩玩看的话你得把上面三个贴图和这个程序保存在一起，如果你有更靠谱的贴图当然更好（分别保存为 tex.png, tex_NRM.png, tex_SPEC.png）。

PPS. 在学 DX，所以上面用到的线性变换也是假设向量是行向量，所以对向量的变换就是用行向量左乘矩阵，不过换个方式用矩阵左乘列向量区别也不大。

PPPS. 扫了几本 3D 数学方面的书，发现还是这本比较靠谱： http://book.douban.com/subject/1400419/

PPPPS. 非常感谢老胡当年让我感受到了线性代数的好玩之处，不然现在在公司里可要遭鄙视了。

PPPPPS. 我写的 3dmath.h，如果你有兴趣看的话——含有一个向量类一个矩阵类，若干无趣的函数，唯一比较有意思的东西是透视和投影。

PPPPPPS. 好几次看见自己拍的照片，突然想到，哇，这阴影好逼真啊。

2 comments 2011/04/30 22:10 categories: Programming tags: 3d  programming  just4fun  algorithm  fun 

无营养两则

1. 最近在补 3D 知识，上周花很大的精力试着手动逐像素渲染 3D 图形，挺好玩的：

老大的要求是高光贴图和法线贴图也是要的，我也做出来了，只不过几个小时之前突然意识到一个非常重要的坐标转换没有做，所以那个法线贴图的结果其实很不靠谱，代码先不放了，省得丢人，等把法线贴图做对了再说吧。

这是阉割版的程序 —— 如果你有兴趣围观的话：rending.7z

哦对了，这里用到的数学运算俺也都自己实现了一遍，等有时间了会整理一下的，毕竟这个其实挺好玩。

 

 

2. 觉得 mataball 这东西挺有意思，结果就整出了个奇丑的：

任何试图画出有两个眼睛一个嘴巴的面部的尝试都会得到一个青蛙

程序和代码在这儿：metaball.7z

圈圈们默认是会动的，如果你只是想画青蛙，把 render 函数的第二个参数设为 0 就好了。

BTW Fast inverse square root 真是威武，有多威武你自己试试就知道了。

 

0 comments 2011/04/26 01:07 categories: Programming tags: just4fun  c++  algorithm  3d  programming  algorithm 

还是流水帐加意识流

1   来到网易实习

这些天我一直在后悔一件事情，就是还没看保密协议上面都写有些什么就把它给签了………而且到目前为止我还不知道上面写了些什么。

嗯，透露一下下肯定不是商业机密的事情吧，网易的伙食还不错。

2   晒晒我的 vimrc

分到电脑的那一天花了一个上午装各种软件，其中最耗精力的要数 VIM 了，自己的 vimrc 没有随身带着，又考虑到里面塞满了各种从网上看到的看上去很好玩但实际上一万年用不到一次的设置，所以干脆自己重新写了一份，里面全是每天都会用到的东西，不长：

set nocompatible
source $VIMRUNTIME/mswin.vim
behave mswin

if has("gui_running")
  colo Ifs
  set gfn=consolas:h11
  set go-=m
  set go-=T
  set cursorline
else
  colo blue
  set nocursorline
endif

syntax on
filetype on
filetype indent on
filetype plugin on

map  <space> :
map  <C-j> <C-w><down>
map  <C-k> <C-w><up>
map  <C-h> <C-w><left>
map  <C-l> <C-w><right>
imap <C-j> <down>
imap <C-k> <up>
imap <C-h> <left>
imap <C-l> <right>

let mapleader=";"
map <leader>w :w!<cr>
map <leader>q :close<cr>
map <leader>[ <C-o>
map <leader>] <C-]>
map <leader><space> <C-w>

map <leader>j :bn<cr>
map <leader>k :bp<cr>
map <leader>bd :bd<cr>

map <leader>tn :tabnew<cr>
map <leader>l  :tabn<cr>
map <leader>h  :tabp<cr>
map <C-t>      :tabnew<cr>
map <C-tab>    :tabn<cr>
map <C-S-tab>  :tabp<cr>

map <silent> <leader><cr> :noh<cr>

map <leader>tl :TlistToggle<cr>
map <leader>gf :NERDTree<cr>

set history=50
set autoread
set ts=4
set expandtab
set smarttab
set shiftwidth=4
set autoindent
set smartindent
set cindent
set scrolloff=5
set wildchar=<Tab>
set wildmenu
set cmdheight=1
set ruler
set nu
set lz
set hid
set whichwrap+=<,>,h,l
set ignorecase
set incsearch
set magic
set showmatch
set hlsearch
set laststatus=2
set statusline=\ %P\ %F%m%r%h\ %y\ %w\ \ CWD:\ %{getcwd()}%h\ \ Line:\ %l/%L:%c
set showmatch
set showmode

其中 <space> 和 <leader> 的设置照目前看来貌似很非主流，但是 <space> 不映射成 : 实在是可惜了，毕竟向下滚动有 j 就够了，而且 j 很好用，把 <space> 映射成 : 可以在敲命令的时候感觉十分痛快；另外 ; 就在小拇指上面，用来敲快捷键再方便不过，默认的用于重复 f, t, F, T 的操作也是基本上用不到的，所以，嗯……

这个设置没考虑到 Linux 下的情况，不过除了 gfn 之外其他应该没什么需要改动的吧。另外 Ifs 主题是我在 lettuce 主题的基础上改的，自己喜欢而已。

插件装得不多，因为发现插件多了启动会慢：

  • bufexplorer
  • c
  • mark
  • matchit
  • NERD_tree
  • supertab
  • taglist

c.vim 要修改一下，它有个 <leader>lcs 的映射，除了让我的 <leader>l 响应变慢之外啥用途都没有，罪过很大。

——然后用起来就很舒服了。

3   Qt，各种吐槽

最新版本的 Qt 光是安装文件竟然就有 1.5 GB !!! 它完全疯了!!!

有段时间特别喜欢 Qt，因为它的每个类都显得非常漂亮，比如说字符串类里面会提供宽字符和窄字符的转换，再比如说 QImage 类光是构造函数就有这么多种：

  • QImage ()
  • QImage ( const QSize & size, Format format )
  • QImage ( int width, int height, Format format )
  • QImage ( uchar * data, int width, int height, Format format )
  • QImage ( const uchar * data, int width, int height, Format format )
  • QImage ( uchar * data, int width, int height, int bytesPerLine, Format format )
  • QImage ( const uchar * data, int width, int height, int bytesPerLine, Format format )
  • QImage ( const char * const[] xpm )
  • QImage ( const QString & fileName, const char * format = 0 )
  • QImage ( const char * fileName, const char * format = 0 )
  • QImage ( const QImage & image )

不但功能上一应俱全，而且甚至不需要任何文档，一眼看上去就能知道每个函数是怎么用的。

让人不爽的还是 C++ 的二进制不兼容问题，上次做的一个小实验清楚的说明了想让不同的 C++ 编译器生成的二进制程序共用一个 C++ 类实在是很难的事情；而更早之前的经验表明即使是同一个编译器，不同的版本之间也不见得可以兼容，坑爹啊，也就是说你根本提供不了一个统一的运行时环境，写了个好玩的程序想发给别人装 B，只有每次都把一堆几十 MB 的 dll 和自己几 kb 的程序放在一起才行...这不是比 .Net 还过分吗...

还有，很大程度上托无所不能的 template 的福，C++ 编译的那速度... 上次编译 Qt 4.6 花了 4 个小时左右，后来我专门统计了一下，不算文件头注释和空行，Qt 4.6 一共有 2362083 行代码[1]，按 4 个小时来算的话，那么编译+链接速度平均就是每秒钟 164 行了，还有什么语言能比它更慢一点的！！

怎么好像在对 C++ 吐槽……

……都怪 Qt 太大了， FLTK 这种 kb 级别和谁都能静态链接在一起的图形库，用 C++ 我当然没意见，否则您丫每隔一两月更新一次，每次都扔给我好几 G 的东西，还让我以前的程序面临死翘翘的危险，太过分了。

4   乱七八糟

今天在 cnBeta 上看到一句话 “别人一开源，我们就自主研发了。” 笑死了

“搞ACM的你伤不起[2]” - 一看就知道是大牛手笔

[1] 包括自动生成的 moc 文件夹下的
[2] 墙外 其实不在墙外... 作者竟然是同事的同学，世界真小
4 comments 2011/03/22 02:31 categories: Misc tags: programming  just4fun  vim 

一个想法：could

曾经在 Notepad++ 的官网上看到过一个关于 Linux 为何不和谐的笑料：

bash-3.2$ peace
bash: peace: command not found
bash-3.2$ harmony
bash: harmony: command not found
bash-3.2$ kill
kill: you need to specify whom to kill
base-3.2$ _

 

前几天不知为何又想到了这个笑话，突然有了个让他变得和谐一点的想法，为何不让命令行指令看上去人性化一点呢，比如说，在命令行输入 could you calculate 1+41 for me?

输出 Of course! The answer is 42 这样。

于是，俺就动手码了几行代码，写了个名为 could 的 python 脚本，which 可以把命令行参数分给不同的程序去做，在上面这个例子中，他所做的就是把 calculate 1+41 交给 calculate.py 处理。

虽然没啥技术含量，但是，等把它相关的功能实现得差不多了，应该会比较有趣吧——尤其对于那些不知道命令行是什么玩意儿的生物。

 

已经完成的代码在这儿，目前只能算是个 demo。

走过路过的你如果觉得有点意思，不妨留个爪印，咱可以一起整点好玩的。

0 comments 2011/02/22 22:36 categories: Programming tags: fun  just4fun  python  programming 

悲剧啊，只能混个纪念品玩玩

我的程序在这儿了： http://code.google.com/p/harmless/

很想把他叫做 Mostly Harmless，可是不能太狂啊，它明明就是 TOTALLY harmless。

另外眼下 svn 连接不上 google code, 不出意外的话原因应该就是众所周知的那个吧，我最近也懒得折腾了，所以代码先就在压缩包里看吧。

核心代码在这里： http://code.google.com/p/harmless/source/browse/trunk/main.cpp

Windows / Linux 可执行程序以及源码压缩包在这里： http://code.google.com/p/harmless/downloads/list

 

用到的技术有 alpha-beta, iterative deepening, transposition table, null move heuristic, bit board, threat space search (没写完而且不准的版本), principal variation ，然而这些算法中没有几个是容易调试的，再加上核心的评价函数依然是瞎掰的（试过用进化算法让它进化出一个比较靠谱的参数，然而结果是它进化到了一种自娱自乐的境界，和自己这种风格的AI竞赛倒还好，可实际棋力依旧不行），再加上整体框架上还有好些不成熟的地方，比如说我干嘛要记录下某个空位在四个方位的子力呢，记录下最好的两个方位就OK了啊——反正，改来改去，最后一次练习赛之后的版本棋力竟然越变越差，真伤心。

泥人五子棋里面似乎有好几个可以借鉴的想法，开局库可以多折腾几条记录进去，proof number search + threat space search + 开局库效果应该就会还可以了吧；另外可惜 db-search 接触得太晚了，它的思想也很吸引人。

寒假重写。

 

 

最后，附上两张几天前在厕所玩水的照片：

 

还有好多张，有时间了再传到网易去。

2 comments 2010/12/31 23:12 categories: Programming Misc tags: just4fun  programming  gomoku  algorithm 

KMP 算法的复杂度和最差情况

此段已经加入到了俺写的 MP/KMP 算法详解 中了；缺少这一段正是它一直保持着草稿状态的主要原因；但由于害怕疏忽，目前也还不敢改变其状态。(囧)

好吧，下面开始正文

6   复杂度分析

至于为什么 KMP 算法的复杂度是线性的，我们再回头看看 另一种表示 一节中的算法主体：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F);
    for(;text[i];++i,++j) { // j 增大，i 增大
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];       // j 减小
        }
        if(j>=m-1) {
            return (i+1-m);
        }
    }
    return -1;
}

i 只有增大的份，所以 ++i 最多执行 n 次，这个很显然。

j 初始值为 0，一共增加了 n 次，而 j>=-1 ，于是 j = F[j] 这一句最多也就执行了 n+1 次（否则就会出现 j<-1 的情况了）。

所以就是线性的了！

7   KMP 算法的最长停顿

为了说明 KMP 算法在文本串上的某一个字符上进行了很多次比较的极限情况（也就是所谓的停顿或者E文的 delay ），我们首先要介绍一下 “费波拉契串” —— 因为，很巧，它就是能使 KMP 算法达到最糟糕状况的模式串，一会儿我们会说到。

提到 “费波拉契” ，相信不少人会直接想到 1, 1, 2, 3, 5, 8, 13, 21, 34 ... ，是的，费波拉契串的定义也十分类似：

设 P 是个费波拉契串，那么：

P[0] = b
P[1] = a
P[i] = P[i-1]P[i-2]

所以：

P[2] = ab
P[3] = aba
P[4] = abaab
P[5] = abaababa
P[6] = abaababaabaab
P[7] = abaababaabaababaababa
P[8] = abaababaabaababaababaabaababaabaab
...

计算出 P[7] 的 F 数组和 Next 数组如下，我们一会儿要用到，你也可以先把它当作找规律的题看看：

P a b a a b a b a a b a a b a b a a b a b a  
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
F -1 0 0 1 1 2 3 2 3 4 5 6 4 5 6 7 8 9 10 11 7 8
Next -1 0 -1 1 0 -1 3 -1 1 0 -1 6 0 -1 3 -1 1 0 -1 11 -1 8

费波拉契串有几个性质值得注意一下：

Note

文章前面已经假设了我的世界里费波拉契数列下标是从 0 开始的，这里再强调一遍。

  1. strlen(P[n]) == Fibonacci[n] （这个应该很容易理解吧）

  2. 设函数 c(t) 的作用是交换字符串 t 的最后两个字符，例如 c("abcdef") == "abcdfe"，那么当 n>=2 时 P[n-1]P[n-2] == c(P[n-2]P[n-1]) ：
    n == 2 时这是显然的；
    当 n>2 时可以用数学归纳法证明：
    c(P[n-2]P[n-1]) = P[n-2]c(P[n-1]) = P[n-2]P[n-3]P[n-2] = P[n-1]P[n-2]
  3. 由上面两条性质我们又可以推导出：
    Next[Fibonacci[n]-2] == F[Fibonacci[n]-2] == Fibonacci[n-1]-2, n>=2
    这是因为，可以把一个费波拉契串分解开：
    P[n] == P[n-1]P[n-2] == P[n-2]P[n-3]P[n-2] == c(P[n-3]P[n-2])P[n-2] == P[n-3]c(P[n-2])P[n-2] == ...
    具体以 P[7] 为例，
    P[7] == ab-ab-ba---ab------ba
    其中省略掉的部分根据 性质2 表现出的规律与前方相等，因此如果在 P[7] 的最后一个字符 b 处发生了不匹配，接下来应该在下列位置重新试着匹配：
    ab-a--b----a-------b-
    它们正好占据着 Fibonacci[2]-2, Fibonacci[3]-2, .. , Fibonacci[7]-2, ... 的位置。

因此，如果在费波拉契串的第 n 位，n == Fibonacci[k]-2 上发生了不匹配，接下来则还需要 k-1 次比较；

又因为 Fibonacci[k-1] == (φk - (-1)kφ-k)/sqrt(5) == round( φk / sqrt(5) )， 于是可以解得 k ~ logφ(n)，其中 φ 是黄金比例 (1+sqrt(5))/2 == 1.618...

—— k 便是文本串上的一个字符的最多比较次数。

8   为什么费波拉契串这么神奇

为了证明为何费波拉契串就是使停顿时间最长的模式串，我们再看看 MP 算法的基本思想：将字符串已匹配的一个前缀和一个对应的后缀匹配。

假设字符串 S 有且仅有一个相等的前缀和后缀（设为 a ），那么 S 可以表示为

S = aB = Ca

再假设 a 本身也有且仅有一个相等的前缀和后缀（设为 e ），那么 a 也可以表示为

a = eF = Ge

对应 MP 算法，匹配 Ca 时若在 a 之后失败，则会将 aB 的 a 与其对齐：

Cax
Cay

==>

Cax
 aBy

若在 B 的第一个字符处再次失败，则下一次对齐是这样的：

CGex
 GeBy

==>

CGex
  eFBy

KMP 算法在这里还要求 F 的第一个字符和 B 的第一个字符不等（否则会跳过这一段）

我们很容易可以证明想要 KMP 算法在这个地方停留尽可能长的时间需要满足 |S| <= |e| + |a| ：因为若 |e| + |a| > |S|，那么令 d = |e| + |a| - |S| 则 Ca = CGe = aB 算式中， a 和 e 将有长度为 d 的重叠，于是 B 的第一个字符等于 e[d]；同理，在 aB = eFB = Ca 算式中，可以得到 F 的第一个字符为 a[d]，由 a = eF 可以得到 a[d] = e[d]，和 KMP 的要求不符。

于是 |S| == |e| + |a| 是使 KMP 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

1 comments 2010/11/23 19:07 categories: Programming tags: algorithm  programming 

聊聊 memcpy

嗯 .. 提到 memcpy 你是不是就条件反射的想到了这样的东西呢：

void * memcpy(void * dst, const void * src, size_t size)
{
    size_t i=0;
    unsigned char * _dst = dst;
    const unsigned char * _src = src;
    for(; i<size; ++i) {
        _dst[i] = _src[i];
    }
    return dst;
}

其实吧，memcpy 里面还是很有学问的 ... 首先从一个新闻说起吧

最近某个由 memcpy 引发的血案似乎引起了不少人关注，事情大概是 glibc 使用了一个号称经过优化的 memcpy 函数，这个函数对源地址和目标地址 重叠 的情况没有处理（虽然实际上 memcpy 函数也不要求处理这种情况），于是 Adobe Flash Player 闹情绪了，原因在于那个 tricky 的 memcpy 函数作风比较诡异，在某些机器上它是把数据 从后往前 拷贝的，对此 Linus 的评价是：

That said - why the heck would you ever do memcpy() backwards? Things like automatic prefetchers usually work better for the "natural" patterns, so a backwards memcpy is generally a bad thing to do unless you have some active reason for it, like doing a memmove()

不过我其实更觉得这完全是 Adobe 的问题，因为如果从后往前拷贝它就会出问题，那么遇到下面这种情况，从前往后拷贝也可以照样整垮它：

A: bbbbbaaaaa
B:      aaaaabbbbb

memcpy(B,A,10);

Anyway，事情到现在已经基本上算是平息了： glibc 相信问题不在于 memcpy 而在于 Adobe 没有正确使用它，问题不再讨论；Linus 则给出了一个暂行方案，他的那个方案已经非常优秀了以至于想想很有可能破坏掉读者的挑战欲望，所以还是留着过一会儿再说吧……

现在我们回到主题上，memcpy，怎么样让它更快些呢。

首先， dst[i] = src[i] 这一句实际上的效率就相当于 *(dst+i) = *(src+i) ， 这里的加法显得有点太过分了。稍微修改一下下：

void * memcpy(void * dst, const void * src, size_t size)
{
    unsigned char * _dst = dst;
    const unsigned char * _src = src, * _src_end;
    for(_src_end = _src+size; _src<_src_end; ++_src, ++_dst) {
            * _dst = * _src;
    }
    return dst;
}

Andorid 上面的 libc 似乎就是类似这样的实现了。

但是，其实还不够，拷贝 size 个字节，比较运算就执行了 size 次，可不可以少一点？

答案：Yes!

方案一：Duff's Device

Duff's Device 是个非常 tricky 的东西，以至于你第一眼见到很可能怀疑“这货真能通过编译？”

void * memcpy(void * dst, const void * src, size_t size)
{
    register n=(size+7)/8;
    register unsigned char * _dst = dst;
    register const unsigned char * _src = src;
    switch(size%8){
        case 0:     do{     *_dst++ = *_src++;
        case 7:             *_dst++ = *_src++;
        case 6:             *_dst++ = *_src++;
        case 5:             *_dst++ = *_src++;
        case 4:             *_dst++ = *_src++;
        case 3:             *_dst++ = *_src++;
        case 2:             *_dst++ = *_src++;
        case 1:             *_dst++ = *_src++;
        } while(--n>0);
    }
}

这样，被 switch 一次之后便陷入了 do while 循环；这里 case 0 - case 7 如果不够还可以再加， 此段代码相当于把上面的小于比较省掉了 7/8 。

方案二：不要一个字节一个字节操作，而要一个字一个字的处理：

通常一个机器字有好几个字节长 —— 比如 32 位机器上是 4 个字节，64 位机器上是 8 字节。

将每 n 个字节作为一个整体“超级字符”进行操作，在这种场合算是很常见的应用了：

void * memcpy(void * dst, const void * src, size_t size)
{
    void * orig = dst;
    asm volatile("rep ; movsq"
        :"=D" (dst), "=S" (src)
        :"0" (dst), "1" (src), "c" (size >> 3)
        :"memory");
    asm volatile("rep ; movsb"
        :"=D" (dst), "=S" (src)
        :"0" (dst), "1" (src), "c" (size & 7)
        :"memory");
    return orig;
}

解释一下，这里汇编代码的原理也就是先把 size/8 个字（size>>3）拷贝过去（movsq）， 再把后 size%8 个字节（size&7）拷贝过去（movsb）

这个就是 Linus 给出的临时方案了。

另外这里一个字是八个字节，那是因为这里出现症状的机器是 64 位的。

方案三（其实不算方案三）：结合以上二者

以字为单位，用 Duff's Device 操作…… 这个想想就觉得挺牛的，Newlib 似乎就是这么玩的了：

/* Nonzero if either X or Y is not aligned on a "long" boundary.  */
#define UNALIGNED(X, Y) \
  (((long)X & (sizeof (long) - 1)) | ((long)Y & (sizeof (long) - 1)))

/* How many bytes are copied each iteration of the 4X unrolled loop.  */
#define BIGBLOCKSIZE    (sizeof (long) << 2)

/* How many bytes are copied each iteration of the word copy loop.  */
#define LITTLEBLOCKSIZE (sizeof (long))

/* Threshhold for punting to the byte copier.  */
#define TOO_SMALL(LEN)  ((LEN) < BIGBLOCKSIZE)

_PTR
_DEFUN (memcpy, (dst0, src0, len0),
        _PTR dst0 _AND
        _CONST _PTR src0 _AND
        size_t len0)
{
#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
  char *dst = (char *) dst0;
  char *src = (char *) src0;

  _PTR save = dst0;

  while (len0--)
    {
      *dst++ = *src++;
    }

  return save;
#else
  char *dst = dst0;
  _CONST char *src = src0;
  long *aligned_dst;
  _CONST long *aligned_src;

  /* If the size is small, or either SRC or DST is unaligned,
     then punt into the byte copy loop.  This should be rare.  */
  if (!TOO_SMALL(len0) && !UNALIGNED (src, dst))
    {
      aligned_dst = (long*)dst;
      aligned_src = (long*)src;

      /* Copy 4X long words at a time if possible.  */
      while (len0 >= BIGBLOCKSIZE)
        {
          *aligned_dst++ = *aligned_src++;
          *aligned_dst++ = *aligned_src++;
          *aligned_dst++ = *aligned_src++;
          *aligned_dst++ = *aligned_src++;
          len0 -= BIGBLOCKSIZE;
        }

      /* Copy one long word at a time if possible.  */
      while (len0 >= LITTLEBLOCKSIZE)
        {
          *aligned_dst++ = *aligned_src++;
          len0 -= LITTLEBLOCKSIZE;
        }

       /* Pick up any residual with a byte copier.  */
      dst = (char*)aligned_dst;
      src = (char*)aligned_src;
    }

  while (len0--)
    *dst++ = *src++;

  return dst0;
#endif /* not PREFER_SIZE_OVER_SPEED */
}

方案四，有请硬件牛

翻出 glibc 2.9 的代码，它的代码看上去倒是不长：

void *
memcpy (dstpp, srcpp, len)
     void *dstpp;
     const void *srcpp;
     size_t len;
{
  unsigned long int dstp = (long int) dstpp;
  unsigned long int srcp = (long int) srcpp;

  /* Copy from the beginning to the end.  */

  /* If there not too few bytes to copy, use word copy.  */
  if (len >= OP_T_THRES)
    {
      /* Copy just a few bytes to make DSTP aligned.  */
      len -= (-dstp) % OPSIZ;
      BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);

      /* Copy whole pages from SRCP to DSTP by virtual address manipulation,
     as much as possible.  */

      PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);

      /* Copy from SRCP to DSTP taking advantage of the known alignment of
     DSTP.  Number of bytes remaining is put in the third argument,
     i.e. in LEN.  This number may vary from machine to machine.  */

      WORD_COPY_FWD (dstp, srcp, len, len);

      /* Fall out and copy the tail.  */
    }

  /* There are just a few bytes to copy.  Use byte memory operations.  */
  BYTE_COPY_FWD (dstp, srcp, len);

  return dstpp;
}

从注释可以看出，现在它在玩的都是些硬件相关的 trick 了 (更别提 Linux Kernel 中的那些对应不同处理器的汇编实现)，于是我发现我似乎不太适合再继续挖下去了。




文章最后，我想以高中语文考试作文体结尾，非常感谢所有这些 —— hacker 也好 geek 也好 —— 做了这么多有意思又有意义的工作， 让我们有 Linux 这么优秀的操作系统可以用；正是由于这样的细节，这样的竞争气氛，这一点一滴的积累，才有了（ 我自己的测试中 ）比 Win7 快上近 1/3 的速度，让人没有理由再质疑开源的力量。

4 comments 2010/11/17 05:04 categories: Programming tags: algorithm  just4fun  c  programming 

最长公共子串 [后缀树应用之二]

1. 我干了什么

我写了个小程序，用 1.276 秒找出了《银河系漫游指南》和《宇宙尽头的餐馆》的最长公共子串：

the history of every major galactic civilization tends to pass through three distinct and recognizable phases, those of survival, inquiry and sophistication, otherwise known as the how, why and where phases.

用 1.266 秒找出了《宇宙尽头的餐馆》和《再见，谢谢所有的鱼》的最长公共子串：

in the uncharted backwaters of the unfashionable end of the western spiral arm of the galaxy

用 8.671 秒找出了《魔戒》和《1984》的最长公共子串：

. it was inevitable that they should make

用 6.728 秒找出了《飘》和《基本无害》的最长公共子串：

more than anything else in the world.

...

我发现这是件很好玩的事情～

2. 怎么做的

Again，有了 后缀树 ，这样的工作太简单了：

/*
 * Author  : If
 * Date    : Oct/16th/2010
 * License : Boost License v1

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license  (the "Software")  to use,  reproduce,  display,  distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED,  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#include "suffixtree.h"
#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <ctime>
using namespace std;

static void ticToc_(bool s)
{
    static clock_t start_ = clock();
    if(s) {
        start_ = clock();
    } else {
        clock_t end_=clock();
        std::cerr
            << (end_ - start_) << " ticks"
            << "    (" << (end_ - start_) * (1000.)/CLOCKS_PER_SEC <<"ms)"
            << std::endl;
    }
}

inline void tic()
{
    ticToc_(true);
}

inline void toc()
{
    ticToc_(false);
}

struct Info
{
    vector<int> belongTo;
};

typedef Node<char, Info>       NodeT;
typedef SuffixTree<char, Info> STree;

// 初始化节点的从属属性。
void initInfo(NodeT& leaf)
{
    NodeT* node = leaf.parent;
    int    nth  = leaf.belongTo;
    while ( node->parent!=node && (
            node->info.belongTo.empty() ||
            node->info.belongTo.back()!=nth )) {
        node->info.belongTo.push_back(nth);
        node=node->parent;
    }
}

void printPath(NodeT const* node)
{
    if(node->parent!=node)
        printPath(node->parent);
    copy(node->str, node->str+node->len,
         ostream_iterator<char>(cout));
}

// 将连续的空白字符转换成单个空格；将大写全转换为小写。
void filter(char * text, int & len)
{
    char*p=text,*q=text;
    for(;q<text+len;++p,++q){
        if(*q>='A'&&*q<='Z') {
            *p=*q-'A'+'a';
        } else if(isspace(*q)) {
            *p=' ';
            while(isspace(*q))
                ++q;
            --q;
        } else {
            *p=*q;
        }
    }
    len = p-text;
}

struct LetsRock
{
    NodeT const*& result;
    int   longestNow;
    int   nStrings;
    LetsRock(int n, NodeT const*& root):
        result(root),
        longestNow(0),
        nStrings(n)
    { }
    void operator()(NodeT const& node) {
        if (node.depth + node.len > longestNow &&
            node.info.belongTo.size()==nStrings) {
            longestNow = node.depth + node.len;
            result     = &node;
        }
    }
};

int main(int c,char**v)
{
    STree tree;
    tic();
    for(int i=1;i<c;++i) {
        cerr<<"reading "<<v[i]<<" ...\n";
        FILE*  file = fopen(v[i],"r");
        string content;
        char   buf[8192];
        int    bytesRead=0;
        int    bytesTotal=0;
        while((bytesRead=fread(buf,1,8192,file))==8192) {
            filter(buf,bytesRead);
            content.append(buf,bytesRead);
            bytesTotal += bytesRead;
        }
        if(bytesRead) {
            filter(buf,bytesRead);
            content.append(buf,bytesRead);
            bytesTotal += bytesRead;
        }
        fclose(file);
        cerr<<"done. ( " << bytesTotal <<" bytes )\n";
        cerr<<"adding to suffix tree ...\n";
        tree.addString(content);
        cerr<<"done.\n";
    }
    NodeT const* ans = tree.root();
    tree.eachLeaf(initInfo);
    LetsRock fun(c-1,ans);
    tree.dfs(fun);
    printPath(ans);
    cout<<endl;
    toc();
    return 0;
}
9 comments 2010/10/19 17:50 categories: Programming tags: algorithm  just4fun  c++  suffix tree  programming 

代码压缩工具原型 [后缀树应用之一]

嗯，对我来说是代码压缩工具原型；对大多数地球生物来说这其实是最长不重叠重复子串问题。

1. 我干了什么

我写了个程序，运行时内存占用峰值为 323 MB，耗时 6.582s，从 2,827,372 字节的《魔戒》全本中找出了不算空格、大小写敏感的情况下出现两次或更多的最长子串：

All that is gold does not glitter,
Not all those who wander are lost;
The old that is strong does not wither,
Deep roots are not reached by the frost.
 
From the ashes a fire shall be woken,
A light from the shadows shall spring;
Renewed shall be blade that was broken,
The crownless again shall be king.

耗时 7.022 秒，内存占用峰值 351 MB，从 3,872,493 字节的 sqlite 3.6.22 的合并 c 文件中找到了最长重复子串：(忽略空格)

.c****************//**************Beginfileos_common.h********************
****** *************//***2004May22****Theauthordisclaimscopyrighttothissou
rcecode.Inpla ceof**alegalnotice,hereisablessing:****Mayyoudogoodandnotevi
l.**Mayyoufindforgiv enessforyourselfandforgiveothers.**Mayyousharefreely,
nevertakingmorethanyougive.  *********************************************
*********************************** ****Thisfilecontainsmacrosandalittlebi
tofcodethatiscommonto**alloftheplatform-sp ecificfiles(os_*.c)andis#includ
edintothose**files.****Thisfileshouldbe#includedb ytheos_*.cfilesonly.Itis
nota**generalpurposeheaderfile.*/#ifndef_OS_COMMON_H_#de fine_OS_COMMON_H_
/***AtleasttwobugshaveslippedinbecausewechangedtheMEMORY_DEBUG* *macrotoSQ
LITE_DEBUGandsomeoldermakefileshavenotyetmadethe**switch.Thefollowingc ode
shouldcatchthisproblematcompile-time.*/#ifdefMEMORY_DEBUG#error&quot;TheME
MORY_DEB UGmacroisobsolete.UseSQLITE_DEBUGinstead.&quot;#endif#ifdefSQLITE
_DEBUGSQLITE_PRIVATE intsqlite3OSTrace=0;#defineOSTRACE1(X)if(sqlite3OSTra
ce)sqlite3DebugPrintf(X)#de fineOSTRACE2(X,Y)if(sqlite3OSTrace)sqlite3Debu
gPrintf(X,Y)#defineOSTRACE3(X,Y,Z) if(sqlite3OSTrace)sqlite3DebugPrintf(X,
Y,Z)#defineOSTRACE4(X,Y,Z,A)if(sqlite3OST race)sqlite3DebugPrintf(X,Y,Z,A)
#defineOSTRACE5(X,Y,Z,A,B)if(sqlite3OSTrace)sqli te3DebugPrintf(X,Y,Z,A,B)
#defineOSTRACE6(X,Y,Z,A,B,C)\if(sqlite3OSTrace)sqlite3D ebugPrintf(X,Y,Z,A
,B,C)#defineOSTRACE7(X,Y,Z,A,B,C,D)\if(sqlite3OSTrace)sqlite3D ebugPrintf(
X,Y,Z,A,B,C,D)#else#defineOSTRACE1(X)#defineOSTRACE2(X,Y)#defineOSTRA CE3(
X,Y,Z)#defineOSTRACE4(X,Y,Z,A)#defineOSTRACE5(X,Y,Z,A,B)#defineOSTRACE6(X,
Y, Z,A,B,C)#defineOSTRACE7(X,Y,Z,A,B,C,D)#endif/***Macrosforperformancetra
cing.Norm allyturnedoff.Onlyworks**oni486hardware.*/#ifdefSQLITE_PERFORMAN
CE_TRACE/***hwti me.hcontainsinlineassemblercodeforimplementing**high-perf
ormancetimingroutines.* //**************Includehwtime.hinthemiddleofos_com
mon.h****************//******* *******Beginfilehwtime.h*******************
***********************//***2008May27 ****Theauthordisclaimscopyrighttothi
ssourcecode.Inplaceof**alegalnotice,hereisab lessing:****Mayyoudogoodandno
tevil.**Mayyoufindforgivenessforyourselfandforgiveo thers.**Mayyousharefre
ely,nevertakingmorethanyougive.*************************** ***************
******************************************Thisfilecontainsinlinea smcodefo
rretrieving&quot;high-performance&quot;**countersforx86classCPUs.*/#ifndef
_HWTIME_ H_#define_HWTIME_H_/***Thefollowingroutineonlyworksonpentium-clas
s(ornewer)proce ssors.**ItusestheRDTSCopcodetoreadthecyclecountvalueoutoft
he**processorandreturn sthatvalue.Thiscanbeusedforhigh-res**profiling.*/#i
f(defined(__GNUC__)||defined( _MSC_VER))&amp;&amp;\(defined(i386)||defined
(__i386__)||defined(_M_IX86))#ifdefined(__GN UC__)__inline__sqlite_uint64s
qlite3Hwtime(void){unsignedintlo,hi;__asm____volati le__(&quot;rdtsc&quot;
:&quot;=a&quot;(lo),&quot;=d&quot;(hi));return(sqlite_uint64)hi&lt;&lt;32|
lo;}#elifdefined(_MS C_VER)__declspec(naked)__inlinesqlite_uint64__cdeclsq
lite3Hwtime(void){__asm{rdt scret;returnvalueatEDX:EAX}}#endif#elif(define
d(__GNUC__)&amp;&amp;defined(__x86_64__))_ _inline__sqlite_uint64sqlite3Hw
time(void){unsignedlongval;__asm____volatile__(&quot;r dtsc&quot;:&quot;=A
&quot;(val));returnval;}#elif(defined(__GNUC__)&amp;&amp;defined(__ppc__))
__inline__ sqlite_uint64sqlite3Hwtime(void){unsignedlonglongretval;unsigne
dlongjunk;__asm__ __volatile__(&quot;\n\1:mftbu%1\n\mftb%L0\n\mftbu%0\n\cm
pw%0,%1\n\bne1b&quot;:&quot;=r&quot;(retval) ,&quot;=r&quot;(junk));return
retval;}#else#errorNeedimplementationofsqlite3Hwtime()foryour platform./**
*Tocompilewithoutimplementingsqlite3Hwtime()foryourplatform,**youcan remov
etheabove#errorandusethefollowing**stubfunction.Youwilllosetimingsupportfo
r many**ofthedebuggingandtestingutilities,butitshouldat**leastcompileandru
n.*/SQLI TE_PRIVATEsqlite_uint64sqlite3Hwtime(void){return((sqlite_uint64)
0);}#endif#endi f/*!defined(_HWTIME_H_)*//**************Endofhwtime.h*****
********************** *******************//**************Continuingwherew
eleftoffinos_common.h******** **********/staticsqlite_uint64g_start;static
sqlite_uint64g_elapsed;#defineTIMER_ STARTg_start=sqlite3Hwtime()#defineTI
MER_ENDg_elapsed=sqlite3Hwtime()-g_start#de fineTIMER_ELAPSEDg_elapsed#els
e#defineTIMER_START#defineTIMER_END#defineTIMER_EL APSED((sqlite_uint64)0)
#endif/***IfwecompilewiththeSQLITE_TESTmacroset,thenthefo llowingblock**of
codewillgiveustheabilitytosimulateadiskI/Oerror.This**isusedfort estingthe
I/Orecoverylogic.*/#ifdefSQLITE_TESTSQLITE_APIintsqlite3_io_error_hit=0 ;/
*TotalnumberofI/OErrors*/SQLITE_APIintsqlite3_io_error_hardhit=0;/*Numbero
fnon -benignerrors*/SQLITE_APIintsqlite3_io_error_pending=0;/*Countdowntof
irstI/Oerro r*/SQLITE_APIintsqlite3_io_error_persist=0;/*TrueifI/Oerrorspe
rsist*/SQLITE_APIi ntsqlite3_io_error_benign=0;/*Trueiferrorsarebenign*/SQ
LITE_APIintsqlite3_diskfu ll_pending=0;SQLITE_APIintsqlite3_diskfull=0;#de
fineSimulateIOErrorBenign(X)sqli te3_io_error_benign=(X)#defineSimulateIOE
rror(CODE)\if((sqlite3_io_error_persist &amp;&amp;sqlite3_io_error_hit)\||
sqlite3_io_error_pending--==1)\{local_ioerr();CODE;}st aticvoidlocal_ioerr
(){IOTRACE((&quot;IOERR\n&quot;));sqlite3_io_error_hit++;if(!sqlite3_io _e
rror_benign)sqlite3_io_error_hardhit++;}#defineSimulateDiskfullError(CODE)
\if( sqlite3_diskfull_pending){\if(sqlite3_diskfull_pending==1){\local_ioe
rr();\sqlit e3_diskfull=1;\sqlite3_io_error_hit=1;\CODE;\}else{\sqlite3_di
skfull_pending--;\ }\}#else#defineSimulateIOErrorBenign(X)#defineSimulateI
OError(A)#defineSimulateD iskfullError(A)#endif/***Whentesting,keepacounto
fthenumberofopenfiles.*/#ifdefSQ LITE_TESTSQLITE_APIintsqlite3_open_file_c
ount=0;#defineOpenCounter(X)sqlite3_ope n_file_count+=(X)#else#defineOpenC
ounter(X)#endif#endif/*!defined(_OS_COMMON_H_) *//**************Endofos_co
mmon.h*******************************************//** ************Continui
ngwhereweleftoffinos_

正如之前在 后缀树的介绍 中说过的那样，俺想要弄出个能压缩 C 程序代码的工具，而上面的就是原型了：找出出现多次且较长的子串， #define 一下，重复多次，差不多了。

2. 怎么做的

有了后缀树，这样的工作可真是简单啊：

/*
 * Author  : If
 * Date    : Oct/14th/2010
 * Version : 0.0.1
 */
/*
Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license  (the "Software")  to use,  reproduce,  display,  distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED,  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#include "suffixtree.h"
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;

static void ticToc_(bool s)
{
    static clock_t start_ = clock();
    if(s) {
        start_ = clock();
    } else {
        clock_t end_=clock();
        std::cerr
            << (end_ - start_) << " ticks"
            << "    (" << (end_ - start_) * (1000.)/CLOCKS_PER_SEC <<"ms)"
            << std::endl;
    }
}

inline void tic()
{
    ticToc_(true);
}

inline void toc()
{
    ticToc_(false);
}


struct Info {
    int cv,depth,isLeaf;
    Info():cv(-1),depth(-1),isLeaf(0){}
};

typedef Node<char,Info> NodeT;

void initInfo(NodeT& node) {
    node.info.depth = node.depth + node.len;
    if(node.branches.empty()){
        node.info.isLeaf = 1;
        node.info.cv = node.leafNum;
    } else {
        node.info.isLeaf = 0;
        NodeT* p = node.branches[0];
        if(p->info.cv==-1) {
            initInfo(*p);
        }
        node.info.cv = p->info.cv;
    }
}

void printPath(NodeT const* node)
{
    if(node->parent!=node) {
        printPath(node->parent);
    }
    copy(node->str, node->str+node->len, ostream_iterator<char>(cout));
}

struct LetsHaveFun
{
    NodeT const*& result;
    LetsHaveFun(NodeT const*& root):result(root){}
    void operator()(NodeT& node){
        if(!node.info.isLeaf &&  // more than once
            node.depth != 0 &&   // not root
            node.info.depth > result->info.depth && // better
            abs(node.info.cv - node.branches.back()->info.cv) >=
                node.info.depth  // do not overlap
        ) {
            this->result = &node;
        }
    }
};

int main(int c,char**v) {
    if(c>2)
        return 1;
    SuffixTree<char, Info> stree;
    NodeT const* ans = stree.root();
    LetsHaveFun fun(ans);
    string source;
    if(c==2&&v[1][0]=='-') {
        if(v[1][1]=='S') // do not skip white space
            cin>>noskipws;
        else if(v[1][1]=='s')
            cin>>skipws;
        else
            return 1;
    } else {
        return 1;
    }

    copy(istream_iterator<char>(cin), istream_iterator<char>(),
         back_inserter(source));
    tic();
    stree.addString(source);
    stree.dfs(initInfo);
    stree.dfs(fun);
    printPath(ans);
    cout<<endl;
    toc();
}

3. Question

这次有问题顺便想要请教一下高人们，在上面的代码中有一段让我很不爽：

struct LetsHaveFun
{
    NodeT const*& result;
    ...

我的本意是想用 NodeT const* result ; 然而那么做的话 stree.dfs(fun) 这句话结束之后 fun.result 又回到了 root （LetsHaveFun::operator() 中 result 的确会变的！），百思不得其解，似乎碰到了某个语法的黑暗角落；然而在这个问题上 VC2008 和 GCC 4.5.0 竟然表现得出奇的一致以至于我开始怀疑自己了，谁来救救我？

4. PostScript

suffixtree.h 全部内容在我的 后缀树的介绍 中。

5. Update

Ubuntu 威武，同样的代码，同样的文件系统，同样的计算机配置，同样的编译器，同样的编译选项，在 Ubuntu 上面，此处(Win7)耗时 6.5 秒的程序变得只要 4.5 秒了，Astonishing

0 comments 2010/10/15 00:57 categories: Programming tags: suffix tree  programming  just4fun  c++  algorithm 

CKEditor Plugin For Micolog

个人比较喜欢 CKEditor, 所以就给 micolog 整了个 ckeditor 插件： 

http://micolog.appspot.com/plugins/view?key=agdtaWNvbG9nchsLEgZQbHVnaW4iD0NLRWRpdG9yIHBsdWdpbgw

 

其实 tinymce 也还可以啦，只是我做好这个插件之后才发现原来在 /views/admin/entry.html 中把 tinymce 的初始化代码改成这样，它也完全可以接受了：

（主要是它之前总是自作主张的把 URL 改成相对路径 —— 而且还是个错的，还有 html 的预览把 <p> 弄没了，结构一塌糊涂）

<script type="text/javascript">
$('#content').ready(function() {
    $('.editor-toolbar').show();
    var editor = null;
    $('#edButtonPreview').click(function(){if(editor);else initTinymce();});
    $('#edButtonHTML').click(function(){if(editor)tinymce.execCommand('mceRemoveControl',false,'content'); editor=null;});

    function initTinymce(){
        editor = $('#content').tinymce({
            script_url : '/tinymce/tiny_mce.js',
            theme : "advanced",
            
            plugins : "safari,pagebreak,save,advhr,advimage,advlink, inlinepopups,media,directionality,visualchars,nonbreaking,fullscreen,preview,autoresize",

            theme_advanced_buttons1:"bold,italic,underline,strikethrough,|,bullist,numlist,blockquote,|,forecolor,backcolor,|,justifyleft,justifycenter,justifyright,justifyfull,|,link,unlink,image,code,preview,|,fullscreen",
            theme_advanced_buttons2:"styleselect,formatselect,fontselect,fontsizeselect,|,pastetext,pasteword,removeformat,|,media,charmap,|,outdent,indent,|,undo,redo",
            theme_advanced_buttons3:"",
            theme_advanced_buttons4:"",

            theme_advanced_toolbar_location : "top",
            theme_advanced_toolbar_align : "left",
            theme_advanced_statusbar_location : "bottom",
            theme_advanced_resizing : true,
            
            content_css : "/tinymce/wordpress.css",
            extended_valid_elements : "textarea[cols|rows|disabled|name|readonly|class],script[src,type],canvas",
 
            file_browser_callback: 'micolog_file',
            relative_urls: false
        });
    }
    initTinymce();
});
function micolog_file(field_name, url, type, win){
   if (type=='image')
       {ext='jpg|png|jpeg|gif|svg';}
   else if (type=='mdeia')
       {ext='swf|wmv|avi|wma|mp3|mid|asf|rm|rmvb|flv';}
   else
       {ext="*";}

    tinyMCE.activeEditor.windowManager.open({
        file : '/admin/uploadex?ext='+ext,  
        title : '{%trans "Files"%}',
        width : 420,
        height : 200,
        resizable : "no",
        inline : "yes",
        popup_css: false,
        close_previous : "no"
    }, {
        window : win,  
        input : field_name  
    });
    return false;
}
</script>
0 comments 2010/10/12 13:12 categories: Programming Misc tags: programming  just4fun 

C++ ABI, Screw You!

用 TDM-GCC 4.5 编译了 OpenCV 2.1 和 boost 1.44 

下载了用(某不知道来源的) MinGW GCC 4.4 编译的 Qt 4.6

问题在于，这两个版本的 MinGW 显然不兼容！

今天需要用到这三个库时，链接就总是悲剧 —— 用 TDM-GCC 编译工程，则找不到 _Unwind_Resume 函数（链接 libgcc_s.a 还是找不到、同时还会伴随出现 n 个重复定义）；用 Qt 目录下那个 MinGW 编译工程的话，则有无数个找不到实现的 boost 库函数。

 

现在我在想是要重新编译一下 OpenCV 以及 Boost 呢，还是重新编译一下 Qt 呢。

 

update:
花了近四个小时把 Qt 自己编译了一遍，其间顺便(终于)看了《银翼杀手》，问题果然解决，真累。
话说银翼杀手确实是部不可多得的好片，情节引人入胜同时又发人深省，只是我还不敢说看懂了，什么时候还得再看几遍。
另外，从编译的流程来看 Qt 的确是世界上最容易编译的东西之一了，configure，make，done —— 只是，它好大啊。 

1 comments 2010/09/17 16:13 categories: Programming tags: fml  programming  c++