文章归档

用kindle来阅读源代码

最近新买了一台kindle 4, 好家伙,可惜不能用来看论文,糟蹋了,转换也是乱七八糟不能看

于是萌生了在kindle上面阅读源代码的想法,方法如下

第一步:合并源文件

检索一个source目录,遍历src下所有的.h .c 文件合并输出到一个文件,支持分级,每一个文件为一个chapter。如果有多个子目录,封装,再迭代函数

C++代码

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <sys/types.h>
  4. #include <dirent.h>
  5. #include <stdlib.h>
  6. #define BUFFSIZE 1024
  7. int main(int argc, char **argv)
  8. {
  9. char buf[BUFFSIZE], *p = buf;
  10. FILE *fp, *nfp;
  11. DIR *dp;
  12. struct dirent *dir;
  13. char chapter[BUFFSIZE];
  14. int cp = 1;
  15. if (argc!=3) {
  16. printf("Usage:......n");
  17. exit(0);
  18. }
  19. strcpy(buf,argv[1]);
  20. p = p+strlen(argv[1]);
  21. *p++ = '/';
  22. if ((nfp = fopen(argv[2], "w")) == NULL) {
  23. printf("error for open the file:%sn",argv[2]);
  24. exit(0);
  25. }
  26. »» 继续阅读全文

github的'\n'文件名漏洞

这几天在部署github的时候发现了一个小问题,恰好我有个文件的名字是包含 'n' 换行符的,push上去之后结果导致整个project webpages不能访问,一直提示:

An unexpected error seems to have occurred. Why not try refreshing your page? Or you can contact us if the problem persists.

排查了很久才发现原来是这个的问题。

n 在ASCII码里属于控制字符,而我们平时一般习惯把文件名这类当作字符流来操作的。比如在某些应用程序间的通信,就很有可能将n当作特殊字来处理。ext等文件系统又默认是支持带n的文件名。所以,后话就来了

我立马发上很多应用程序都不能正确处理这种情况,会出现各种莫名其妙的问题:

  • p7zip仅保留n前面的字符并写到结果文件里面去,但是结果文件的文件名却没有改变
  • gzip可以正常解压缩,但是通过gzip处理的文件,file-roller是不能读取,Segmentation fault. 调试了一下,发现在 gtk_main() 里堆栈崩溃了,也没法跟进去
  • jar和zip等会将n替换成 ^J 这样的字符,或者 ^J
  • rar无法正常工作,根本没法压缩。奇怪的是,通过file-roller来调用rar却可以生成压缩文档,不过没法读取
  • 。。。。。

 

目前的猜想,应该只是webpage的问题,和后端服务器程序没有关系。

Smaz的小对象压缩技术

基于小对象的压缩算法。一个叫做 Smaz 的项目,https://github.com/antirez/smaz 目前应用在redis数据库上面。

与传统的压缩算法不同的是,Smaz更适合小对象的压缩,比如几个字节到几十个字节不等。除开字典的硬编码部分,压缩过程和解压过程加起来120行代码,非常的短小精罕,却有不俗的表现。平均测试能够达到40%~50%左右的压缩效果。

当然,代码在某些方面不是完美的,也不健壮,但是很实用。 antirez坚持追求高速度而放弃部分的安全性。一些相关讨论,请看

http://news.ycombinator.com/item?id=540048

 

核心代码

Smaz的核心代码只有两部分:

  1. 字典的设计
  2. Hash函数

字典方面,Smaz 采用了硬编码的方式,antirez应该是对大量的相关语料进行统计,分析,进而得出最常用的字符组合

C++代码

  1. /* Reverse compression codebook, used for decompression */
  2. static char *Smaz_rcb[254] = {
  3. " ", "the", "e", "t", "a", "of", "o", "and", "i", "n", "s", "e ", "r", " th",
  4. " t", "in", "he", "th", "h", "he ", "to", "", "l", "s ", "d", " a", "an",
  5. "er", "c", " o", "d ", "on", " of", "re", "of ", "t ", ", ", "is", "u", "at",
  6. " ", "n ", "or", "which", "f", "m", "as", "it", "that",

    »» 继续阅读全文

追寻自己的内心

云风离开了网易,惊讶,归于平静,我想起了安德逊教授:“人活到这把年纪,我发现历史正开始重复它自己,这太乏味了。真的,我该走了。”

10年了,是什么动力可以让一个人用10年的时间把所有经历都放在做好同一件事上,如果是你,十年后会不会回过头反思这十年来什么东西对自己来说才是真正重要的,如果重新再给你一个十年,你会选择做什么来填补这10年的空白。每个人,都会有一个自己不一样的答案吧

很久没听音乐了,因为已经很少有那种能一下子抓住耳朵的旋律,虽然我不太懂音乐,但我时常在想,音乐是不是和写文章一样?再优美华丽的词句,也不如最质朴而又简单的表达。干净的琴调,欢快的乐谱,忧伤的旋律,听听石进 夜的钢琴曲

我见过有两种人,一是科学家,一是工程师,科学家发觉自然现象和规律,工程师制造世界改善生活。但是很少有人能够完整的走完这一过程,从科研的源头 和到成品的问世,不是短短几十个年头就能走完的。我没记错的话,风魂2D游戏引擎应该是云洋在大三的时候开始开发了吧,从研发到大话,再到风靡一时的梦 幻,尽管今天风魂不再,但是云洋兄确实给后人留下了宝贵的财富,正如他自己说的:为后人留下点东西是我的愿望

 

此刻,仿佛自己正在面对着10年后的自己,同样的三年前,我跟自己说:人是不是一定要看到失败的时候才会开始后悔过去,所以我选择了奋斗自己的路,那么今天,我该以怎么样的心态去面对我的未来以及10年后,20年后的我

B.S.Kushwah:Life Is Too Short …… 人生苦短,趁年轻,做自己喜欢的事,完成自己的梦想,不怨不悔,我不是一直是这么过来的吗?

我不知道我们的将来是否一样,我希望10年后的我对今天的我予以厚望,因为有梦想才有希望,有梦想才有激情

希望不一定是我们必要的,激情也不一定是我们必要的,但是常抱梦想之心,我们的生是不是就会更有意思一些,即使将来走了也不会太寂寞,是不?

其实现实和梦想也不一定是冲突的,梦想还有多种实现的方式和途径,不同的人对它还有不一样的诠释

梦想应该是自己内心的一片清净之地,人生的不同阶段会有不一样的理想和追求,但是放弃一些东西并不意味着要丢掉梦想,总会有一些,是留下的,往后很长的一段路伴随着我们的,非常纯真的东西

真心祝福云洋兄,仅以此文,怀念云风的心路10年

每个人的內心都是一座孤岛,时时刻刻 / 甚至当心爱的人就在身侧,闭上眼睛想要留住这让人无限贪恋的一刻。 / 始终,我们选择倾诉和聆听的,都只是我们內心的独白。

Textpress开发笔记

美的东西一直是我所追求的,比如简洁与效率。

这几年用过不少Blog,先是 WordPress、MovableType、Drupal、Plone 后有 Textpattern、TextPress 等等,但总无法找到一个真正适合自己的Blog程序,也许是因为过分的追求完美,才对某些小小的问题过分苛刻吧。那个时候起,有了想自己动手写Blog程 序的想法,我这个人就是有点毛病,如果一样东西还能在我所能忍受的程度里解决我的需求,我就坚决不去改变它,所以我用了3年的vim,连自动补全都不会

真正动起手来是最近我在深圳研究生院(以下简称深研院)的那一个月里,大部分的空闲时间我都是在思考Blog程序的构架与设计上面,并且翻阅了不少 其他博客系统的源代码,包括 WordPress 和 Textpattern 等等。Textpattern 实在是太优秀了,我曾经花费过很长一段的时间去研究她,尤其是她的textile写作语法。

经过近一个月的不断调试和修改,我的第一个Blog程式诞生了,取名 Textpress 。没有 Tags ,没有 TrackBack ,只有简单的网志功能和一些基本的后台管理,但是我很喜欢它,她能满足我的需求,并且在我需要的时候,我可以很容易的扩展她,原始与质朴!

作为一名开发者,你想知道什么产品适合你,最好的办法就是:实践它,直到你满意为止

这是我深研院来为数不多的几张照片之一,感谢我女朋友,帮我记录了这些

后记:很怀念在深研院的这个月里,每天都过得很充实。我从来都没有这么深刻、认真的考虑过,我是否了解这个行业,我在做什么以及我将往何处走,在离开这个地方的时候,我给自己找到了一个答案。

很感谢我的女朋友,在这个月里给予我很多支持与鼓励,有时晚上回到家里还要加班到很夜没给她睡一个安稳觉,她也没怨过我,有时候忙得连饭都懒得吃, 本来可以好好打个瞌睡的时间却还要跑去食堂那么远的地方给我买饭。爱情的力量真是伟大啊还可以长肉,在我女朋友的悉心呵护下这个月我胖了四斤,真是前所未 有闻所未闻,希望回到学校不要一下子瘦掉,不然我会很心疼的。

今天女朋友研一新生开学了,心里很高兴,亲亲她

就这样吧,先去补牙

关于CAP理论

理论的弱一致性和最终一致性,理解,Werner Vogels 是这样说的:

  • Weak consistency. The system does not guarantee that subsequent accesses will return the updated value. A number of conditions need to be met before the value will be returned. The period between the update and the moment when it is guaranteed that any observer will always see the updated value is dubbed the inconsistency window.
  • Eventual consistency. This is a specific form of weak consistency; the storage system guarantees that if no new updates are made to the object, eventually all accesses will return the last updated value. If no failures occur, the maximum size of

    »» 继续阅读全文

平衡二叉树的自平衡策略

本文的目的,旨在为数据结构或者算法的设计提供一些启发性的思路。

数组 --> 二分搜索 --> 链表 --> 二叉搜索树

二分搜索

二分搜索是一种很重要的算法。最普遍的莫过于对排序数组的处理。而数组的一个特质,使得二分搜索在离散存储结构里难以实现

  • 连续的内存区域,依靠下标来自动计算偏移量

就是说,对排序数组的操作,仅仅依靠下标就可以进行的。但是在实际的系统中,我们有时无法一次性提供足够大的连续存储空间或者海量处理那些离散地存储在内存里的数据的时候,如链表等等,这种方法不适用。

回想一下对排序数组进行二分搜索的操作,每次二分是不是都在最中间进行,那链表该如何才能做到呢?

答案是,做不到吧。离散的本质就是随机,你不可能找到中结点的位置。二叉搜索树的出现解决了这个问题,直接从中结点出发和决定下一分支。

所以现在的问题是:谁来担任中结点。

  1. 对于静态的数据,递归选举中结点,然后形成最优二叉搜索树
  2. 对于动态的数据,关键的地方在于,当插入一个结点或者删除一个结点的时候,如何平衡整个二叉搜索树的二分结构。

所以出现了自平衡,解决了二分搜索思想在离散存储结构里的应用。

自平衡的策略

所谓自平衡是指通过执行一系列维持某种性质的操作,这个性质,是为了更好的实现二分搜索的思想。如AVL的平衡因子,红黑树的5个强制约束,等等。

而旋转操作则是实现自平衡最常用的一项策略,通过左右子树迁移结点以实现结构的动态平衡

左旋,相当于右子树往左字树迁移两个结点,右旋同理。下面以红黑树为例,讨论自平衡策略的实现

旋转的时机

左右子树的结点数不想等时结构处于不平衡状态,不平衡就要旋转。但具体的实现取决于不同的场景和需求,由结构自身的性质来决定的。如AVL树在当左右子树结点总数相差1时进行旋转,(待)

封装epoll的异步API

epoll的设计坚持Unix哲学KISS原则,keep it simple, stupid

但是KISS并不等于实用。epoll提供三个简单的函数供应用程序进行异步事件处 理,epoll_create(),epoll_ctl(),epoll_wait()。这几个函数并不友好,尤其面对复杂的业务逻辑时,缺乏清晰的思路, 需要进一步的封装。

通常开发人员需要什么:

  1. 异步处理的对象,文件描述符
  2. 需要监听的事件,可读或可写(EPOLLIN|EPOLLOUT)
  3. 事件产生时的处理函数,epoll并不提供,机制与策略分离

所以我对 epoll 提供的接口进行简单易用的封装,以适合更一般化的场景需求。

数据结构

C 代码

  1. typedef void eProc(struct eloop *el, int fd, void *argv, int mask);
  2. /* File event structure */
  3. typedef struct efile {
  4. int mask;
  5. eProc *rProc;
  6. eProc *wProc;
  7. void *data;
  8. } efile_t;
  9. typedef struct eloop {
  10. int efd;
  11. int stop;
  12. efile_t ev[AE_SETSIZE];
  13. efire_t rd[AE_SETSIZE];
  14. } EL;

efile_t 作为基本的异步io对象,保存事件发生时调用的处理函数以及传参的数据。eloop 为最主要的数据结构,efd 为 epoll_create() 返回的 epoll 专用描述符号,负责多个epoll_event。ev[AE_SETSIZE] 保存正在监听的所有事件。如果 epoll_t 是监控机,则 efd为执行者,events 为被监控对象。每次 epoll_wait() 返回的结果保存在 rd[AE_SETSIZE] 里。

编程接口

C

»» 继续阅读全文

数据结构接口对象化

c 语言适合平台及系统等一些的大型核心构架的开发,面向过程,不支持面向对象语义,

不过我始终认为,面向对象是一种思想,而不是指某种既定的技术,所以,OO 与语言没有关系,随便一种语言,一样可以写出面向对象的代码,OO 的思想绝对不只是继承,多态等那么简单,对于某些语言如 c++ 或者 Java,支持面向对象语义因而适合表达这种思想而已,况且 Java本身设计的出现就是为了解决面向语义的问题

做项目的时候,很头疼的问题就是关于接口命名的设计,包括内部接口和外部接口,小型的项目倒也罢了,如果构架过于庞大,就容易出现接口混乱的问 题,c 风格的代码并不像 c++ 或者 java 那样简单容易白,毕竟用 c 的都是写模块的多,功能越是复杂,函数的命名就越容易出现杂乱无章的情况,很难看出你在写什么,支持面向语义的编程语言,最大的优点就是,容易写出层次分 明,结构清晰的代码,但是像 c 这样的语言可不容易,所以,好的函数命名规范对项目来说很重要

回归正题,先说说什么是对象化技术,所谓数据结构对象化,就是一组结构有各自适合的管理接口,本质上是一样的,只是写法不同而已,以红黑树为例,看看内核是怎么实现的(部分接口):

C++代码

  1. /* Macros that define a red-black tree */
  2. #define RB_HEAD(name, type)
  3. struct name {
  4. struct type *rbh_root; /* root of the tree */
  5. }
  6. #define RB_INITIALIZER(root)
  7. { NULL }
  8. #define RB_INIT(root) do {
  9. (root)->rbh_root = NULL;
  10. } while (/*CONSTCOND*/ 0)
  11. #define RB_BLACK 0
  12. #define RB_RED 1
  13. #define RB_ENTRY(type)
  14. struct {
  15. struct type *rbe_left; /* left element */
  16. struct type *rbe_right; /* right element */
  17. struct type

    »» 继续阅读全文

这个世界是我们的

土豆是我的兄弟,我们一起长大,一起上小学,上初中,高中,说的搞笑一点,是穿着同一条内裤长大的

土豆很有天赋,很小的时候就会拿着粉笔满屋子的画画而且画的有模有样,可惜爸妈都是农民,身边又没几个知识分子,土豆遇不上伯乐。书法也很好,小学 就已经拿过全国奖,不过没人栽培,现在也就马马虎虎了。还看过很多书,他曾经断断续续地拿过家里一千多块钱,然后全用来买书了,当然,他还不知到一千块钱 是很大一笔数目。他让我看得最多的是卡耐集的文集比如人性的弱点等等,可惜我识字不多,看的少。这些书,对土豆的成长有过很大的影响

土豆原本是农村里睡大街的小屁孩,后来考上了镇上的一所三流小学,四年级的时候又去到了镇上最好的中心小学,小学毕业后,考上了市里最烂的职高,三年后又考上了市里最棒的高中,大学,当然是比较烂了。这是他的人生曲线,土豆的故事太多了

土豆对数学出奇的感兴趣,我曾经翻看过他的手稿本,厚厚的一沓,泛黄的膜皮,渗水的笔迹,记录了土豆小学六年来对各种数学问题的思考与研究,比如,圆心在同一条直线上的连续圆,半径有什么关系

土豆初中的时候还曾经挂名到另外一个学校参加全国赛,拿了将了,后来就不得而知了。

土豆喜欢看书,不喜欢交朋友,性格不算孤僻但是喜欢独来独往,土豆的外号很多,比如化骨龙,因为他很瘦,又比如轻工水上飘,因为土豆不喜欢把时间浪 费在走路上,所以每次吃饭的时候跑得特别快,尤其人多的时候怎么跑都撞不到人,就得了这个称号。我也给他起过花名,因为他笑起来跟女人一个模样,不过他很 少笑,更多的时候,静静的一个人做自己的事

我曾经问过他咱们班上的人,谁谁谁啦,可惜很少有他答得出来的,他对他们很少印象,土豆甚至自己老师的名字都不知道。不过数学老师他是知道的,那个 时候土豆有过很长一段时间的辉煌历史,他对数学,知道的远比别人的多,他老是觉得老师讲的慢,磨磨蹭蹭的,就自己找书看,土豆第一次参加校内竞赛的时候, 考的有很大一部分都是超纲的题目,倒是对土豆来说没什么难度,结果他考了全校第一名,第二名是同班的,差了4分,大红纸贴出来的时候,大家一下子就爆炸开 了,因为第三名已经缩了二十多分了,也是因为这个事情,我和土豆认识了第一个朋友,阿飞,此后一路考试直至毕业,都是土豆第一,然后阿飞跟着第二,不过阿 飞英语要比土豆好。后来高中之后土豆去了高州中学,阿飞跳到了茂名一中,此后就更少有了联系

别人看来,土豆很成熟,懂得很多道理,待人处事方式很不一样,所以土豆虽然没什么朋友,但是很多同学喜欢悄悄地跟他聊心事,哪怕自己失恋了。有一件 事,对土豆的影响很大,这么说来,要追溯到小学的时候了,土豆经常受到班里某几个同学的欺负,而且有一个还跟着土豆一起上了初中。土豆后来跟我回忆说,因 为一件小事,本来不是土豆的错,但是土豆主动给那个人写了一封信,详细地写了很多事情并表示真诚的道歉,我问土豆,你有没有想过他看到这封信会觉得你更好 欺负,土豆说不知到,书上学到的,想尝试一下。很快那个人有了回信,静悄悄地放在了土豆的铅笔盒里,信里同样讲了很多事情,说,没想过你会给我写信,我想 他一定很感动,为了不是自己的过失却站出来向别人道歉,这是一种谦卑。土豆说,原谅别人,就是善待自己

土豆很有理想,虽然他不知到他的理想是什么,不过也正是因为这样,所以他才努力的让自己成长,有朝一日,可以看到外面的世界。我相信每个半夜起来沿着单车棚上厕所的人都忘不了那段奋斗史,一群在路灯下挑灯夜读,卧辛尝胆学子们,是土豆,民开,祖森他们,当然,还有我

土豆还曾经有过几个很好的朋友,就是所谓的四人帮,土豆,金海,健强,还有文家周,认识文家周是入学第一天晚上的时候,宿舍很热闹,家周和土豆是邻 床,两个人都不出声,土豆在听心灵地图,家周放着别安的歌,然后很奇异的一幕发生了,家周伸直两条腿,使劲往上蹬,手脚像个婴儿一样,土豆肯定觉得家周很 二B,两人相互对视了一眼,就这样认识了

之后,土豆和我上了高州中学,民开去了二中,祖森在一中,还有玮琪,在四中,其余的人,从此断了联系

土豆高一的时候曾经疯狂的迷恋过黑客技术,经常上课不听课就是经常抱着一本黑客X档案或者黑客手册之类的书籍在看,我记得他好像收过一个学弟,叫陈威,这件事说起来有点搞笑

土豆觉得自己水平还行,然后搞了一个团队,叫什么极度深寒二进制网络安全联盟,名字其实是从邪恶八进制那里来的,正好阿威那时候也正在看这类书,两 人一拍即合就成了拍当,土豆觉得光有团队不行,还得有团规,团章,当然了,肯定要收团费的嘛。于是土豆就跑去杂货市买了各种材料,连印章都叫人刻好了,前 前后后花了几百块钱。弄妥了就去找阿威,跟阿威说了入团的事,要了照片,还说,要收5元的团费,其实土豆本来不想收这个钱,只是觉得不收的话觉得阿威可能 怀疑自己是骗子,就象征性地要了5块钱,还跟阿威说,还有几个其他团队的成员,以后让你认识认识,其实谁也没有,土豆有意把团队搞的神秘一点而已,毕竟那 个时候能成为一名黑客是多么牛B哄哄的事情,后来每每我一想起这件事就觉得特别逗笑

土豆成绩倒退得特别厉害,期末考试的时候全科9门加起来都不够400分,我想很大一部分是因为这个原因。我找到土豆,跟他说,你现在看到的,真的是你想要的吗。我说你不应该把时间浪费在这里,如果你真的喜欢,就应该到更高的层次去深造,起码也等上了大学再说。我们触膝盖长谈,谈理想,谈了很长时间,最后土豆接受我的意见,把心思放回到学习上,争取考上好的大学。

土豆又开始过上了三点一线的生活,似乎比以前更安静,更忙了,土豆还是那样记不起班里同学的名字,甚至不常说话,只是在思考自己的问题,土豆学习很 有自己的一套方法,不像其他的同学,他做很少的习题一样可以有效果。相比盲目的去熟练那些公式,土豆更喜欢发现这些自然规律之间的内在关系,土豆更多的时 候是在想和总结。有一次土豆想的深了,想不出来,就去问老师,老师很惊讶,说思路没有问题,不过是微积分的问题,你们还没有学

慢慢地,土豆成绩回到了班上中上水平,高三的时候,已经稳定在班里全十名内,考个自己想要的学校已经不是什么问题了

不过,这个世界有时真会捉弄人,土豆的人生,一如有规律的跌宕起伏不断,我想,那年高考,如果不是因为那一场意外,土豆的人生也不会发生那么大的转变,也许今天,他也可以像很多人一样游走在ACM等赛场里大显身手甚至成为实验室的宠儿。

这一切,似乎与土豆无缘。高考结束后,土豆没有留下任何联系方式,连毕业照都没有拍,自己一个人背起包裹离开了,一走就是两年,杳无音信

再次见到土豆,是我已经快结束大二学业的时候,人在迷茫的时候是不是应该回到原点好好探讨一下,他说很庆幸终于找到自己的理想了,谈话间我还得知他恋爱了,我问他嫂子哪的,他说河南的,我笑着跟他说,那也好,两个人一起奋斗总比一个人更有力量

土豆此后陆陆续续来找过几次我,我察觉得出土豆的上进,他的好强,我有时笑他是平民科学家,土豆说,人离开了实验室,会不会就真的什么也做不出来,我说那当然不是,对土豆来说,所谓科学,是一种信仰,是学术自由

最近土豆一次过来,我们在学校的体育馆大汗淋漓地跑了几圈球场,吃完饭,我送了送土豆,回来的路上自己一个人静静的踹步在这个大学的校园里,上大学这么多年,很少有现在这样的心境了,想想我们过去的二十年,不禁感概万千

土豆来了短信,说:这个世界不止是有你们,我也可以改变世界

是的,只要不放弃,这个世界就是我们的

第 12 页,共 13 页« 最新...910111213