loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

#

博客迁移

博客迁移

3年前我从CSDN博客迁移到CPPBLOG写博客。然后我乱七八糟地写一篇博客声明。那个时候还 没把写博客当一回事,纯碎是出于为自己做记录的目的。如今写博客一半还是出于记录,另 一半则是出于在外面自我表现,还有那么一点点说出来觉得崇高的理由就是分享自己的知识 。

这回我倒不是迁移出CPPBLOG。CPPBLOG整体上是个更低调做技术的圈子,一如我博客的副标 题。自己建了个独立博客,主要还是因为学习Lisp的原因。

在过去的若干年中,有各种各样的技术点因为长久的疏远,一个一个淡出于大脑。虽说技术 点不大重要,学习能力、方法才是终生受用的东西。但完全忘记,也算是一大遗憾。Lisp不 应该被我忘记,一个程序员至少应该在他常用的语言之外,熟悉另一门语言。而这另一门语 言应该是更“快速的“、更“方便的“,它能在你需要的时候更快速地构建你的想法。虽然出于 工作原因,我得时不时地捣鼓下Lua。

Anyway,这个独立博客就是我用Lisp搭建的。从Web server到博客系统。其中博客系统也有 我很大一部分代码在其中,在可预见的未来,在Lisp应用方面我将主要用于构建这个博客系 统。靠自己写的代码(虽然只有一部分)搭建出来的博客就是爽啊。如果要我用个现成的, 我还真懒得去独立门户。

程序员嘛,只有在不断地自我折腾(简写自虐)中,才能成长。最后,请求大家(+强迫) 移步我的新博客 codemacro.com 。要参考技术信息的,可以 参考这里 ,要看看我使用 Lisp是如何捣鼓出这个博客系统的,可以 点这里 。当然,在可预见的未来,我还是会在 CPPBLOG同步更新的。 。

posted @ 2011-04-24 17:30 Kevin Lynx 阅读(4326) | 评论 (7)编辑 收藏

传递Lua函数到C/C++中

传递Lua函数到C/C++中

问题

在Lua中,因为函数也是第一类值,所以会出现将函数作为另一个函数的参数,或者函数作 为函数的返回值。这种机制在很多地方都能代码更灵活更简洁,例如:

table.sort(table [,comp])

这里的comp就要求传入一个函数,我们在调用时,大概会有如下形式:

table.sort(t, comp) -- 直接写函数名
table.sort(t, local_comp) -- 某个局部函数
table.sort(t, function (a, b) xxx end ) -- 临时构造一个匿名函数

其中最后一种方式最为灵活,任意时候在需要的时候构造一个匿名函数。这种在Lua自身的 环境中使用,自然没有问题。但是,当我们在C/C++中注册一些函数到Lua环境中,而这些 函数也需要使用函数参数的时候,问题就出来了。

Lua本身是不支持将Lua函数作为函数参数传入C/C++的,不管这个想要传入的函数是全局的 、局部的、或者匿名的(匿名的本质上也算局部的)。一般情况下,我们唯一的交互方式, 不是传入一个函数,而是一个全局函数名。C/C++保存这个函数名,在需要回调Lua的时候, 就在Lua全局表中找到这个函数(根据函数名),然后再调用之。情况大致如下:

function lua_func () xxx end
cfunc(lua_func) -- wrong
cfunc("lua_func") -- right

我们这回的脚本模块,策划会大量使用需要回调函数的C/C++函数。显然,创建大量的全局 函数,先是从写代码的角度看,就是很伤神的。

解决

我们最终需要的方式,大概如下:

cfunc(lua_func) -- ok
cfunc(function () xxx end) -- ok
local xxx = function () xxx end
cfunc(xxx) -- ok

要解决这个问题,我的思路是直接在Lua层做一些包装。因为C/C++那边仅支持传入一个全局 函数名(当然不一定得全局的,根据实际情况,可能在其他自己构造的表里也行),也就是 一个字符串,所以我的思路就是将Lua函数和一个唯一的字符串做映射。:

function wrap (fn)
    local id = generate_id()
    local fn_s = "__callback_fn"..id
    _G[fn_s] = fn
    return fn_s
end

这个wrap函数,就是将一个函数在全局表里映射到一个字符串上,那么在使用时:

cfunc(wrap(function () xxx end))
cfunc(const char *fn_name, xxx); -- cfunc的原型

cfunc是C/C++方注册进Lua的函数,它的原型很中规中矩,即:只接收一个函数名,一个字 符串,如之前所说,C/C++要调用这个回调函数时,就根据这个字符串去查找对应的函数。 脚本方在调用时,如果想传入一个匿名函数了,就调用wrap函数包装一下即可。

一个改进

上面的方法有个很严重的问题,在多次调用wrap函数后,将导致全局表也随之膨胀。我们需 要想办法在C/C++完成回调后,来清除wrap建立的数据。这个工作当然可以放到C/C++来进行 ,例如每次发生回调后,就设置下全局表。但这明显是不对的,因为违背了接口的设计原则 ,这个额外的机制是在Lua里添加的,那么责任也最好由Lua来负。要解决这个问题,就可以 使用Lua的metamethods机制。这个机制可以在Lua内部发生特定事件时,让应用层得到通知。 这里,我们需要关注__call事件。

Lua中只要有__call metamethod的值,均可被当作函数调用。例如:

ab(1, 2)

这里这个函数调用形式,Lua就会去找ab是否有__call metamethod,如果有,则调用它。这 个事实暗示我们,一个table也可以被调用。一个改进的wrap函数如下:

local function create_callback_table (fn, name)
    local t = {}
    t.callback = fn
    setmetatable (t, {__call =  -- 关注__call
        function (func, ...) -- 在t(xx)时,将调用到这个函数
            func.callback (...) -- 真正的回调
            del_callback (name) -- 回调完毕,清除wrap建立的数据
        end })
    return t
end

function wrap (fn)
    local id = generate_func_id() -- 产生唯一的id
    local fn_s = "_callback_fn"..id
    _G[fn_s] = create_callback_table(fn, fn_s) -- _G[fn_s]对应的是一个表
    return fn_s
end

在我们的C/C++程序中,依然如往常一样,先是从_G里取出函数名对应的对象。虽然这个对 象现在已经是一个table。然后lua_call。

上面的代码是否会在原有基础上增加不可接受的性能代价?虽然我没有做过实际测试,但是 从表明看来,排除meta table在Lua里的代价,也就多了几次Lua函数调用。

最后,感叹一下,Lua里的table及metatable机制,实在非常强大。这种强大不是功能堆砌 出来的强大,而是简单东西组合出来的强大。其背后的设计思想,着实让人佩服。

4.26.2011 Update

之前的文中说“Lua本身是不支持将Lua函数作为函数参数传入C/C++的“,这句话严格来说不 正确(由某网友评论)。假设函数cfun由c/c++注册,我们是可以编写如下代码的:

cfunc(print) -- 传入Lua函数

但是问题在于,我们无法取出这个函数并保存在c/c++方。Lua提供了一些接口用于取cfunc 的参数,例如luaL_checknumber(封装lua_tonumber)。但没有类似luaL_checkfunction的 接口。Lua中的table有同样的问题。究其原因,主要是Lua中的函数没有直接的c/c++数据结 构对应。

;; END

posted @ 2011-04-24 17:28 Kevin Lynx 阅读(11316) | 评论 (9)编辑 收藏

浅谈代码分层:构建模块化程序

浅谈代码分层:构建模块化程序

Author:Kevin Lynx
Date:4.4.2011
Contact:kevinlynx at gmail dot com

模块化的程序是怎样的程序?我们可以说一个具有明显物理结构的软件是模块化的,例如带 插件的软件,一个完整的软件由若干运行时库共同构建;也可以说一个高度面向对象的库是 模块化的,例如图形引擎OGRE;也可以说一些具有明显层次结构的代码是模块化的。

模块化的软件具有很多显而易见的好处。在开发期,一个模块化的设计有利于程序员实现, 使其在实现过程中一直保持清晰的思路,减少潜伏的BUG;而在维护期,则有利于其他程序 员的理解。

在我看来,具有良好模块设计的代码,至少分为两种形式:

  • 整体设计没有层次之分,但也有独立的子模块,子模块彼此之间耦合甚少,这些子模块 构成了一个软件层,共同为上层应用提供服务;
  • 整个库/软件拥有明显的层次之分,从最底层,与应用业务毫无相关的一层,到最顶层, 完全对应用进行直接实现的那一层,每一个相对高层的软件层依赖于更底层的软件层, 逐层构建。

上述两种形式并非完全分离,在分层设计中,某一层软件层也可能由若干个独立的模块构成 。另一方面,这里也不会绝对说低层模块就完全不依赖于高层模块。这种双向依赖绝对不是 好的设计,但事实上我们本来就无法做出完美的设计。

本文将代码分层分为两大类:一是狭义上的分层,这种分层一般伴有文件形式上的表现;一 是广义上的分层,完全着眼于我们平时写的代码。

软件分层

软件分层一般我们可以在很多大型软件/库的结构图中看到。这些分层每一层本身就包含大 量代码。每个模块,每一个软件层都可能被实现为一个运行时库,或者其他以文件形式为 表现的东西。

Example Android

Android是Google推出的智能手机操作系统,在其官方文档中有Android的系统架构图:

imgs/android-architecture.jpg

这幅图中很好地反映了上文中提到的软件层次。整个系统从底层到高层分为Linux kernel, Libraries/Runtime,Application Framework,Applications。最底层的Kernel可以说与应 用完全不相关,直到最上层的Applications,才提供手机诸如联系人、打电话等应用功能。

每一层中,又可能分为若干相互独立(Again,没有绝对)的模块,例如Libraries那一层 中,就包含诸如Surface manager/SGL等模块。它们可能都依赖于Kernel,并且提供接口给 上层,但彼此独立。

Example Compiler

在编译器实现中,也有非常明显的层次之分。这些层次可以完全按照编译原理理论来划分。 包括:

  • 词法分析:将文本代码拆分为一个一个合法的单词
  • 语法分析:基于 词法分析 得到的单词流构建语法树
  • 语义分析:基于 语法分析 得到的语法树进行语义上的检查等
  • 生成器:基于 语义分析 结果(可能依然是语法树)生成中间代码
  • 编译器:基于 生成器 得到的中间代码生成目标机器上的机器代码
  • 链接器:基于 编译器 生成的目标代码链接成最终可执行程序

软件分层的好处之一就是对任务(task)的抽象,封装某个任务的实现细节,提供给其他 依赖模块更友好的使用接口。隔离带来的好处之一就是可轻易替换某个实现。 例如很 多UI库隔离了渲染器的实现,在实际使用过程中,既可以使用Direct X的渲染方式,也可 以使用OpenGL的实现方式。

但正如之前所强调,凡事没有绝对,凡事也不可过度。很多时候无法保证软件层之间就是单 向依赖。而另一些时候过度的分层也导致我们的程序过于松散,效率在粘合层之间绕来绕去 而消失殆尽。

代码分层

如果说软件分层是从大的方面讨论,那么本节说的代码分层,则是从小处入手。而这也更是 贴近我们日常工作的地方。本节讨论的代码分层,不像软件分层那样大。每一层可能就是 百来行代码,几个接口。

Example C中的模块组织

很多C代码写得少的C++程序员甚至对一个大型C程序中的模块组织毫无概念。这是对其他技 术接触少带来的视野狭窄的可怕结果。

在C语言的世界里,并不像某些C++教材中指出的那样,布满全局变量。当然全局变量的使 用也并不是糟糕设计的标志(goto不是魔鬼)。一个良好设计的C语言程序懂得如何去抽象、 封装模块/软件层。我们以Lua的源代码为例。

lua.h文件是暴露给Lua应用(Lua使用者)的直接信息源。接触过Lua的人都知道有个结构体 叫lua_State。但是lua.h中并没有暴露这个结构体的实现。因为一旦暴露了实现,使用者就 可能会随意使用其结构体成员,而这并不是库设计者所希望的。 封装数据的实现,也算 是构建模块化程序的一种方法。

大家都知道暴露在头文件中的信息,则可能被当作该头文件所描述模块的接口描述。所以, 在C语言中任何置于头文件中的信息都需要慎重考虑。

相对的,我们可以在很多.c文件中看到很多static函数。例如lstate.c中的stack_init。 static用于限定其修饰对象的作用域,用它去修饰某个函数,旨在告诉:这个函数仅被当前文件( 模块)使用,它仅用于本模块实现所依赖,它不是提供给模块外的接口! 封装内部实现 ,暴露够用的接口,也是保持模块清晰的方式之一。

良好的语言更懂得对程序员做一种良好设计的导向。但相对而言,C语言较缺乏这方面的语 言机制。在C语言中,良好的设计更依赖于程序员自己的功底。

Example Java中的模块组织

相较而言,Java语言则提供了模块化设计的语法机制。在Java中,如同大部分语言一样,一 般一个代码文件对应于一个代码模块。而在Java中,每个文件内只能有一个public class。 public class作为该模块的对外接口。而在模块内部,则可能有很多其他辅助实现的class ,但它们无法被外部模块访问。这是语言提供的封装机制,一种对程序员的导向。

Example OO语言中类接口设计

无论在C++中,还是在Java中,一个类中的接口,都大致有各种访问权限。例如public、 private、protected。访问权限的加入旨在更精确地暴露模块接口,隐藏细节。

在C中较为缺乏类似的机制,但依然可以这样做。例如将结构体定义于.c文件中,将非 接口函数以static的方式实现于.c文件中。

OO语言中的这些访问权限关键字的应用尤为重要。C++新手们往往不知道哪些成员该public ,哪些该private。C++熟手们在不刨根挖底的情况下,甚至会对每个数据成员写出get/set 接口(那还不如直接public)。在public/private之间,我们需要做的唯一决策就是,哪些 数据/操作并非外部模块所需。如果外部模块不需要,甚至目前不需要,那么此刻,都不要 将其public。一个public信息少的class,往往是一个被使用者更喜欢的class。

(至于protected,则是用于继承体系之间,类之间的信息隐藏。)

Example Lisp中的模块设计

又得提提Lisp。

基于上文,我们发现了各种划分模块、划分代码层的方式,无论是语言提供,还是程序员自 己的应用。但是如何逐个地构建这些层次呢?

Lisp中倡导了一种更能体现这种将代码分层的方式:自底而上地构建代码。这个自底而上, 自然是按照软件层的高低之分而言。这个过程就像上文举的编译原理例子一样。我们先编写 词法分析模块,该模块可能仅暴露一个接口:get-token。然后可以立马对该模块进行功能 测试。然后再编写语法分析模块,该模块也可能只暴露一个接口:parse。语法分析模块建 立于词法分析模块之上。因为我们之前已经对词法分析模块进行过测试,所以对语法分析的 测试也可以立即进行。如此下去,直至构建出整个程序。

每一个代码层都会提供若干接口给上层模块。越上层的模块中,就更贴近于最终目标。每一 层都感觉是建立在新的“语言“之上。按照这种思想,最终我们就可以构建出DSL,即Domain Specific Language。

分层的好处

基于以上,我们可以总结很多代码分层的好处,它们包括(但不限于):

  • 隐藏细节,提供抽象,隐藏的细节包括数据的表示(如lua_State)、功能的实现
  • 在新的一层建立更高层的“语言”
  • 接口清晰,修改维护方便
  • 方便开发,将软件分为若干层次,逐层实现

一个问题的解决

有时候,我们的软件层很难做到单向依赖。这可能是由于前期设计的失误导致,也可能确实 是情况所迫。在很多库代码中,也有现成的例子。一种解决方法就是通过回调。回调的实现 方式可以是回调函数、多态。多态的表现又可能是Listener等模式。

所有这些,主要是让底层模块不用知道高层模块。在代码层次上,它仅仅保存的是一个回调 信息,而这个信息具体是什么,则发生在运行期(话说以前给同事讲过这个)。这样就简单 避免了底层模块依赖高层模块的问题。

END

精确地定义一个软件中有哪些模块,哪些软件层。然后再精确地定义每个模块,每个头文件 ,每个类中哪些信息是提供给外部模块的,哪些信息是私有的。这些过程是设计模块化程 序的重要方式。

但需要重新强调的是,过了某个度,那又是另一种形式的糟糕设计。但其中拿捏技巧,则只 能靠实践获取。

posted @ 2011-04-05 10:12 Kevin Lynx 阅读(18808) | 评论 (5)编辑 收藏

Lisp实践:开发RSS阅读器

Lisp实践:开发RSS阅读器

Author:Kevin Lynx
Date:3.30.2011
Contact:kevinlynx at gmail dot com

Tip

本文简要介绍了如何使用Lisp实现一个简单的RSS阅读器,对Lisp无兴趣的TX可以 只对RSS阅读器的实现思路稍作了解即可。

一、RSS阅读器的实现

RSS Reader的实现并不像它看上去那么复杂。当初在决定写这个作为Lisp练习时,甚至觉得 没有多少内容可做。其简单程度甚至用不了你启动一个慢速IDE的时间:D。对Lisp无兴趣的 TX只需要读完这一节即可,

什么是RSS阅读器?

RSS在实现上,可以说是XML的又一次扩张式的应用。因为RSS最重要的东西就是一个XML文件 。RSS主要用于Web中的内容同步。例如我们写的博客,门户网站的新闻,都是内容。Web服 务器将这些内容组织成XML,然后我们通过一个客户端来解析这些XML,就可以在不用直接访 问网站的情况下获取信息:

imgs/rss-overview.png

RSS阅读器就是这样一个从Web服务器通过RSS(表现形式为XML)来获取信息内容的工具。它 可以被实现为一个独立的客户端程序,也可以实现为像Google Reader这种网页形式。后者 其核心功能其实是Google服务器在做,取得信息后再发给用户。

RSS文件

上已提及,RSS的实现其实就是个XML文件。这个XML文件格式非常简单,例如:

<?xml version="1.0"?>
<rss version="2.0">
   <channel>
      <title>Liftoff News</title>
      <link>http://liftoff.msfc.nasa.gov/</link>
      <description>Liftoff to Space Exploration.</description>
      <item>
         <title>Star City</title>
         <link>http://liftoff.msfc.nasa.gov/news/2003/news-starcity.asp</link>
         <description>Oh no, you wrote another blog!</description>
      </item>
    </channel>
</rss>

我们身边到处都是RSS文件,例如 http://www.cppblog.com/rss.aspx 。RSS文件的框架大 致为:

<rss>
    <channel>
        <item>
        </item>
        <item>
        </item>
        ...
    </channel>
</rss>

对,其框架就是这样,一个channel节点,其下若干个item节点。举例来说, CPPBLOG首页就 是一个channel,该channel下有若干原创文章,每篇文章就是一个item。 无论是channel ,还是item,都会有很多属性,例如title/description/link,有些属性是RSS规范里要求 必须有的,有的是可选的。

交互过程

那么,服务器和客户端是如何交互的呢?首先,服务器上的程序针对其某个页面,生成对应 的RSS文件。这个RSS文件基本上是有固定的URL的。客户端每次获取内容时,就从这个固定 的URL获取这个RSS文件。客户端获取到这个RSS文件后,解析之,再呈现给用户。这就是整 个过程。这个过程中客户端与服务器的交互,全部是正常的HTTP请求。

而RSS阅读器,如果做得足够简单,则只需要从指定的地方获取到RSS文件,然后解析这个 XML文件,然后以相对友好的形式显示即可。

扩展

虽然RSS阅读器在核心功能上很简单,但是作为一个可以使用的工具,依然有很多功能点需 要实现。基本功能包括:

  • 记录用户关注的RSS
  • 缓存某个RSS过去一段时间更新的内容
  • 对HTTP回应的处理,最重要的就是重定向处理

我们还可以做很多扩展,例如Google Reader之类的在线RSS阅读器。这些阅读器的RSS抓取 功能做在服务器端,它们除了上面提到的基础功能外,还会包含内容分类,给内容打一些 标签,分析用户的订阅习惯然后推荐类似的内容等等。

二、Lisp实现

本节描述在Lisp中实现上文的内容。主要包括: 通过HTTP请求获取到RSS文件、解析RSS文件 。

获取RSS文件

Lisp虽然历史悠久,但其扩展库标准却做得很拙劣。偏应用级的扩展库要么由编译器实现提 供,要么就得自己在网上找。一方面使用者希望库使用起来方便,另一方面库开发者在跨编 译器实现方面也头疼不已。所幸现在有了quick lisp,安装第三方库就像Ubuntu里安装软件 一样简单(大部分)。

socket支持就是面临的第一个问题。不过我这里并不考虑跨编译器实现的问题,直接使用 SBCL里的socket接口。

要获取RSS文件,只需要连接Web服务器,发起HTTP的GET请求即可。当然,建立TCP连接,组 建HTTP请求包,就不是这里的讨论了。我们还是拿CPPBLOG首页的RSS为例,该RSS的URL为:

http://www.cppblog.com/rss.aspx

拆分一下,得到host为www.cppblog.com(即我们要connect的地址),rss的uri为 /rss.aspx(即HTTP请求里的文件URI),于是建立HTTP请求包:

GET /rss.aspx HTTP/1.0
Host: www.cppblog.com

关于HTTP请求的一些基础知识,可以参考我很早前写的一篇博客:<实现自己的http服务器>。 正常情况下,Web服务器就会返回RSS的文件内容。然后我们就可以继续解析。

解析RSS

RSS本身是一个XML格式的文件。之前连接Web服务器发起HTTP请求没有用到第三方库,但是 解析XML文件不是几十来行代码能搞定的事情,所以这里需要选用一个第三方库。

我用的是s-xml,这个库在我之前的 关于Lisp的文章 中提到过。s-xml与我之前在C++ 领域见到的XML解析库最大的不同点在于,它提供的API是基于事件模式的。意思是说,你不 要去查询某个element的值是多少,当我解析到的时候会告诉你。事件模式的编程方式自然 离不开回调函数:

(s-xml:start-parse-xml
  stream
  (make-instance 's-xml:xml-parser-state
                 :new-element-hook #'decode-rss-new-element
                 :finish-element-hook #'decode-rss-finish-element
                 :text-hook #'decode-rss-text)))

与s-xml交互的也就是上面代码里提到的三个函数:new-element-hook, finish-element-hook , text-hook。这种类型的接口导致解析代码大量减少,但不利于理解。我们要在整个解析 过程中传递数据,需要通过与s-xml交互的函数参数(当然不会蠢到去用全局变量)。

解析过程中通过往函数参数指定的对象身上塞数据完成,整个解析实现也就几十行代码。 文章尾可下载代码看看。

显示出来

通过上面两步,我们得到了RSS文件、解析出了具体内容,最后一步就是呈现出来看看。RSS 文件里每个Item都是一篇文章(新闻之类),这个文章内容可直接包含HTML标记,说白了, 这些内容就是直接的HTML内容。要显示这些内容,最简单的方法就是把一个RSS转换成一种 简单的HTML文件,以供阅读。

这里就涉及到HTML generator,几乎所有的Lisper都会写一个HTML产生器(库)(虽然目前 我还没写)。这种库的作用就是方便地输出HTML文件。

Lisp相对于其他语言很大的一个特点,或者说是优点,就是其语言本身的扩展能力。这种扩 展不是简单的添加几个函数,也不是类,而是提供一些就像语言本身提供的特殊操作符一样 的东西。而HTML generator正是这种东西大放异彩的地方。这种感觉有点像在C++中通过模 板造出各种增强语言特性的东西一样(例如boost/loki)。

因为我这里只是输出简单的HTML文件,何况我对HTML的标记了解的也不多,也懒得再花经历 。所以我暂时也就将就了些土方法:

(with-output-to-string (stream)
  (let ((channel (rss-channel rss))) ;取出channel对象
   (format stream "<html><head><title>~a</title></head>"
           (get-property channel :|title|)) ;取出channel的title

最后组合一些接口,即可将整个过程联系起来,导出html文件:

(cl-rss-test:test-rss-http :uri "/news/newshot/hotnewsrss.xml"
                           :host "cd.qq.com")

然后在浏览器里查看,如图:

imgs/screenshot.png

其他

当一些代码可以工作起来的时候,就可以着手测试这批代码。然后我就用这个工具测试我 Google Reader里订阅的一些RSS。最大的问题,就是关于HTTP重定向的问题。

当服务器返回301或者302的错误信息时(HTTP回应),就标示请求的URI被移动到了其他地 方,客户端需要访问新的地址。这个其实查查 HTTP的规范 就可以轻易解决。重定向时, 新的URI被指定在Response Header里的Location域,取出来发起第二次请求即可。

下载代码

posted @ 2011-03-30 09:32 Kevin Lynx 阅读(4025) | 评论 (0)编辑 收藏

Lisp一瞥:增强型变量Symbol

Lisp一瞥:增强型变量Symbol

Author: Kevin Lynx
Date: 3.21.2011
Contact: kevinlynx at gmail dot com

Note

本文描述的Lisp主要指Lisp的方言Common Lisp。

变量,是所有编程语言里都有的语法概念。在C/C++中,变量用于标示一个内存地址,而变 量名则在语法层面上代表这个地址。当链接器最终链接我们的程序时,就将这些名字替换 为实际的地址。在其他语言中,变量虽然或多或少有其他不同的含义,但也大致如此。

Lisp中的变量也差不多这样,但若将variable和Lisp中的 symbol 放在一起,则多少会 带来些困惑。

Lisp中的“变量"

很多教授Lisp的书中,大概会简单地告诉我们可以使用如下的方式定义一个全局变量 [1].

(defparameter *var* 1)

如上代码,我们便定义了一个全局变量 *var*[2] ,它被初始化为数值1。同样,我们 还可以使用另一种基本相同的方式:

(defvar *var* 1)

除了全局变量,我们还可以定义局部变量。但局部变量的定义稍显麻烦(却可能是另一种 设计考虑)。定义局部变量需要使用一些宏,或者特殊运算符,例如:

(let ((var 1))
(format t "~a" var))

好了,就这些了。Lisp中关于变量的细节,也就这些。你甚至能用你在C/C++中的经验来窥 探一切。但是,我们很快就看到了很多困惑的地方。

我遇到的第一个困惑的地方来源于函数,那么等我讲讲函数再来分享下坎坷。

Lisp中的函数

Lisp中的函数绝对不复杂,你绝对不用担心我在忽悠你 [3] 。作为一门函数式语言,其首要 任务就是加强函数这个东西在整个语言里的功能。如果你喜欢广阅各种与你工作不相干的 技术,你肯定已经对很多函数式语言世界中的概念略有耳闻。例如闭包,以及first class type [4]

Lisp中的函数就是first class type。这什么意思呢?直白来说, Lisp中的函数和变量 没什么区别,享有同等待遇 。进一步来说,变量fn的值可以是数值1,也可以是字符串 "hello",甚至是某个函数。这其实就是C++程序员说的functor。

Lisp中定义函数非常简单:

(defun add2 (x)
(+ 2 x))

这样,我们就定义了一个名为add2,有1个参数,1个返回值的函数。要调用该函数时,只需 要 (add2 2) 即可。这简直和我们在Lisp中完成一个加法一模一样:(+ 2 3)

Lisp作为一门函数式语言,其函数也能作为另一个函数的参数和返回值 [5]

(defun apply-fn (fn x)
(funcall fn x))

apply-fn函数第一个参数是一个函数,它使用funcall函数间接地调用fn指向的函数。作为 一个C++程序员,这简直太好理解了,这完全就是一个函数指针的语法糖嘛。于是,假设我 们要使用apply-fn来间接调用add2函数:

(apply-fn add2 2) ;; wrong

可是这是不对的。我们需要通过另一个特殊操作符来完成这件事:

(apply-fn #'add2 2) ;; right

#'操作符用于将add2对应的函数取出来,这么说当然不大准确。Again,作为一个C++程序员 ,这简直就是个取地址操作符&的语法糖嘛。好吧,这么理解起来似乎没问题了。

Lisp中能甚至能在任何地方定义一个函数,例如我们创建一个函数,该函数返回创建出来的 函数,这是一个典型的讲解什么是 闭包 的例子:

(defun get-add-n (n)
#' (lambda (x)
(+ x n)))

无论如何,get-add-n函数返回一个函数,该函数是add2函数的泛型实现。它可以将你传入 的参数加上n。这些代码里使用了lambda表达式。lambda表达式直白来说,就是创建一个字 面上的函数。这又是什么意思呢?就像我们在代码中写出2,写出"hello"一样,2就是个字 面上的数字,"hello"就是个字面上的字符串 [6]

那么,总而言之,通过lambda创建一个函数体,然后通过#'操作符即可得到一个函数,虽然 没有名字。有了以上知识后,Again and again,作为一个C++程序员,很快我们就能得到一 个程序:定义变量,用变量去保存一个函数,然后通过这个变量来调用这个函数。这是多么 天经地义的事,就像之前那个通过参数调用其指向的函数一样:

;; wrong
(defvar fn #' (lambda (x) (+ x 2)))
(fn 3)

这样的代码是不对的,错误发生于第二行,无论你使用的Lisp实现是哪种,大概会得到如下 的错误信息:

"The function FN is undefined."

老实说,这已经算是多么有迹可循的错误提示了啊。将以上代码和之前的apply-fn对比,是 多么得神似啊,可惜就是错的。这是我们遇到的第一个理解偏差导致的问题。如果你还不深 入探究,你将会在这一块遇到更多麻烦。及时地拿出你的勇气,披荆斩棘,刨根究底,绝对 是学习编程的好品质。

“万恶之源“:SYMBOL

上文中提到的变量函数之类,之所以会在某些时候与我们的理解发生偏差,并且总是存在些 神秘的地方无法解释。这完全是因为我们理解得太片面导致。Lisp中的Symbol可以说就是某 个变量,或者某个函数,但这太片面。Lisp中的Symbol拥有更丰富的含义。

Symbol的名字

就像很多语言的变量、函数名一样,Lisp中的Symbol比其他语言在命名方面更自由: 只 要位于'|'字符之间的字符串,就表示一个合法的Symbol名。 我们可以使用函数 symbol-name来获取一个Symbol的名字,例如:

(symbol-name '|this is a symbol name|)
输出:"this is a symbol name"

'(quote)操作符告诉Lisp不要对其修饰的东西进行求值(evaluate)。但假如没有这个操作符 会怎样呢?后面我们将看到会怎样。

Symbol本质

<ANSI Common Lisp>一书中有句话真正地揭示了Symbol的本质: Symbols are real objects 。是的,Symbols是对象,这个对象就像我们理解的C++中的对象一样,它是一个 复合的数据结构。该数据结构里包含若干域,或者通俗而言:数据成员。借用<ANSI Common Lisp>中的一图:

imgs/symbol-obj.png

通过这幅图,可以揭开所有谜底。一个Symbol包含至少图中的几个域,例如Name、Value、 Function等。在Lisp中有很多函数来访问这些域,例如上文中使用到的symbol-name,这个 函数本质上就是取出一个Symbol的Name域。

Symbol与Variable和Function的联系

自然而然地,翻阅Lisp文档,我们会发现果然还有其他函数来访问Symbol的其他域,例如:

symbol-function
symbol-value
symbol-package
symbol-plist

但是这些又与上文提到的变量和函数有什么联系呢?真相只有一个, 变量、函数粗略来 说就是Symbol的一个域,一个成员。变量对应Value域,函数对应Function域。一个Symbol 这些域有数据了,我们说它们发生了绑定(bind)。 而恰好,我们有几个函数可以用于判 定这些域是否被绑定了值:

boundp ;判定Value域是否被绑定
fboundp;判定Function域是否被绑定

通过一些代码来回味以上结论:

(defvar *var* 1)
(boundp '*var*) ; 返回真
(fboundp '*var*) ; 返回假
(defun *var* (x) x) ; 定义一个名为*var*的函数,返回值即为参数
(fboundp '*var*) ; 返回真

上面的代码简直揭秘了若干惊天地泣鬼神的真相。首先,我们使用我们熟知的defvar定义了 一个名为 *var* 的变量,初值为1,然后使用boundp去判定 *var* 的Value域是否 发生了绑定。这其实是说: 原来定义变量就是定义了一个Symbol,给变量赋值,原来就 是给Symbol的Value域赋值!

其实,Lisp中所有这些符号,都是Symbol。 什么变量,什么函数,都是浮云。上面的 例子中,紧接着用fboundp判断Symbol *var* 的Function域是否绑定,这个时候为假。 然后我们定义了一个名为 *var* 的函数,之后再判断,则已然为真。这也是为什么, 在Lisp中某个函数可以和某个变量同名的原因所在。 从这段代码中我们也可以看出 defvar/defun这些操作符、宏所做事情的本质。

More More More

事情就这样结束了?Of course not。还有很多上文提到的疑惑没有解决。首先,Symbol是 如此复杂,那么Lisp如何决定它在不同环境下的含义呢?Symbol虽然是个对象,但它并不像 C++中的对象一样,它出现时并不指代自己!不同应用环境下,它指代的东西也不一样。这 些指代主要包括变量和函数,意思是说: Symbol出现时,要么指的是它的Value,要么是 它的Function。 这种背地里干的事情,也算是造成迷惑的一个原因。

当一个Symbol出现在一个List的第一个元素时,它被处理为函数。这么说有点迷惑人,因为 它带进了Lisp中代码和数据之间的模糊边界特性。简单来说,就是当Symbol出现在一个括号 表达式(s-expression)中第一个位置时,算是个函数,例如:

(add2 3) ; add2位于第一个位置,被当作函数处理
(*var* 3) ; 这里*var*被当作函数调用,返回3

除此之外,我能想到的其他大部分情况,一个Symbol都被指代为它的Value域,也就是被当 作变量,例如:

(*var* *var*) ; 这是正确的语句,返回1

这看起来是多么古怪的代码。但是运用我们上面说的结论,便可轻易解释:表达式中第一个 *var* 被当作函数处理,它需要一个参数;表达式第二部分的 *var* 被当作变量 处理,它的值为1,然后将其作为参数传入。

再来说说'(quote)操作符,这个操作符用于防止其操作数被求值。而当一个Symbol出现时, 它总是会被求值,所以,我们可以分析以下代码:

(symbol-value *var*) ; wrong

这个代码并不正确,因为 *var* 总是会被求值,就像 (*var* *var*) 一样,第二 个 *var* 被求值,得到数字1。这里也会发生这种事情,那么最终就等同于:

(symbol-value 1) ; wrong

我们试图去取数字1的Value域,而数字1并不是一个Symbol。所以,我们需要quote运算符:

(symbol-value '*var*) ; right

这句代码是说,取Symbol *var* 本身的Value域!而不是其他什么地方。至此,我们 便可以分析以下复杂情况:

(defvar *name* "kevin lynx")
(defvar *ref* '*name*) ; *ref*的Value保存的是另一个Symbol
(symbol-value *ref*) ; 取*ref*的Value,得到*name*,再取*name*的Value

现在,我们甚至能解释上文留下的一个问题:

;; wrong
(defvar fn #' (lambda (x) (+ x 2)))
(fn 3)

给fn的Value赋值一个函数, (fn 3) 当一个Symbol作为函数使用时,也就是取其 Function域来做调用。但其Function域什么也没有,我们试图将一个Symbol的Value域当作 Function来使用。如何解决这个问题?想想,symbol-function可以取到一个Symbol的 Function域:

(setf (symbol-function 'fn) #' (lambda (x) (+ x 2)))
(fn 3)

通过显示地给fn的Function域赋值,而不是通过defvar隐式地对其Value域赋值,就可以使 (fn 3) 调用正确。还有另一个问题也能轻易解释:

(apply-fn add2 2) ; wrong

本意是想传入add2这个Symbol的function域,但是直接这样写的话,传入的其实是add2的 Value域 [7] ,这当然是不正确的。对比正确的写法,我们甚至能猜测#'运算符就是一个 取Symbol的Function域的运算符。进一步,我们还可以给出另一种写法:

(apply-fn (symbol-function 'add2) 2)

深入理解事情的背后,你会发现你能写出多么灵活的代码。

END

关于Symbol的内容还有更多,例如Package。正确理解这些内容以及他们之间的关系,有助 于更深刻地理解Lisp。

注解

[1] 在Lisp中全局变量又被称为dynamic variables
[2] Lisp中按照习惯通常在为全局变量命名时会加上星号,就像我们习惯使用g_一样
[3] 因为我确实在忽悠你
[4] first class type,有人翻译为“一等公民”,我觉得压力巨大
[5] 即高阶函数
[6] “字面“主要是针对这些信息会被词法分析程序直接处理
[7] 这可能导致更多的错误

posted @ 2011-03-22 11:33 Kevin Lynx 阅读(5106) | 评论 (8)编辑 收藏

用lisp开发博客客户端

用lisp开发博客客户端

Author: Kevin Lynx
Date: 3.13.2011

最近一直在学习Lisp这门语言。回头一看,基本上接近1个月了。刚开始接触Lisp是因为看 了<Lisp本质>,然后我发现有很多人宗教般地忠诚这门语言,于是就来了兴趣。

imgs/lisp_believer.png

当然并不是每次因为某篇写得很geek技术文章就去学习某个新的技术点。一个月时间对我来 说还是很珍贵了。但是Lisp绝对是大部分程序员都值得一学的语言(就像Haskell一样)。 我能给出的简单理由包括:

  • 大部分程序员只会命令式语言(C/C++/C Like etc),缺乏函数式语言解决编程问题的思 想(当然Lisp不是纯函数式)
  • Lisp是仅次于Fortran的古老语言,很多优秀的语言设计思想在现代的一些语言里都找得 到
  • 装B党必备

另一方面,结合我一个月以来的读书和两个练习工程的实践经历,我觉得也有些理由值得你 不去学习Lisp:

  • 你会Haskell或者其他函数式语言
  • 我目前还是觉得Lisp学习曲线高(大概是因为我读到的书都在应用语法层兜圈子,事实上 Lisp的语法之统一,全特么的是s-expression),你不愿意花费这些成本
  • you are too old bo to be a B

关于这篇文档

这篇博客我使用reStructuredText格式编写,然后用docutls导出为html,再然后使用这回 用lisp开发的基于metaweblog API的博客客户端,自动发布到CPPBLOG。

他们怎么说Lisp

我就摘录些书上的观点(历史):

  • 1958年,John McCarthy和他的学生搞出了Lisp,包括其第一个实现,最初貌似也是以一 篇论文起头
  • Lisp可以让你做其他语言里无法做的事情(<ANSI common Lisp>)
  • 大部分编程语言只会告诉你不能怎样做,这限制了你解决问题的思路,Lisp not (<ANSI Common Lisp>)
  • Lisp让你以Lisp的思维思考问题,换到其他语言你会说:为什么X语言就不支持这个特性 呢(Once you've leanred Lisp, you'll even dream in Lisp) (<Land Of Lisp>)
  • Lisp代码更清晰地体现你的想法(<Practical Common Lisp>)

And my opinion

我可还没到把Lisp捧上天的地步。如果Lisp如此之好,为什么用的人不多?<Land Of Lisp> 里作者恰好对这个问题做了回答(bla bla bla,懒得细读)。

  • Lisp也是一门杂和型风格的语言,函数式、命令式、面向对象,以及最被人吹捧的宏编程 --程序自己写自己
  • Lisp的语句全部以(xxx xxx)的形式出现,被称为s-expression,我看称为括号表达式还 差不多
  • Lisp每条语句都有返回值,没基础过函数式编程的同学,if语句也是有返回值的
  • 函数式编程语言的一个重要特性就是闭包(closure),这个东西用来避免全局变量实在太 geek了

开始学习Lisp

Lisp不像有些语言,有个直接的机构来维护。感觉它更像C/C++一样,只有个标准,然后有 若干编译器(解释器)实现。Lisp在几十年的发展中,产生了很多种方言。方言也就是形变 神不变的语言变种,本文说的Lisp均指Lisp的方言Common Lisp。另一个比较有名的方言是 Scheme,关于各个方言的特点,<Land Of Lisp>里也给了一个图片:

imgs/dialect.png

其中,最左边那只wolf就是Common Lisp,右边那只sheep就是Scheme。

要学习Lisp,首先就是选择方言。然后最重要的就是选择一个编译器实现。世界上知名的有 十几种实现(也许更多)。一些商业版本非常强大,甚至能编译出很小的本地代码执行文件 ,不过价格也不菲。当然也有很多开源免费的实现,例如CLISP、SBCL。我选用的是SBCL。

SBCL交互式命令行不支持括号匹配,甚至没有输入历史。要实现这两个功能,可以装一个 lisp工具:linedit。在lisp的世界中,要获得一个lisp的库实在不是件方便的事。尤其是 这些免费的编译器实现,并不像有些语言一样,直接随编译器带个几十M的库。

然后就有了quicklisp这个工具。该工具就像Ubuntu系统里的软件管理器一样,你可以在 lisp里直接获取某个库。quicklisp检查该库是否存在,不存在直接从它的服务器上下载人 然后自动安装。

此外,在lisp的世界里,写出来的程序不再是跨OS。OS的差异由编译器实现来解决。但是, 写lisp程序却需要考虑跨编译器实现(egg hurt)。这也是个无比伤神的事,比跨OS更伤 神。因为OS就那么几个,但lisp的编译器实现,流行的也有好几个。

lisp的世界里,工程组织也有特殊的一套,就像makefile一样,这就是asdf。

博客客户端如何实现

像我们这种基本没接触过Web开发的人,可能完全没有思路去实现一个博客客户端。事实上 实现起来非常简单。

使用过其他博客客户端(例如Windows Live writer)的人肯定知道metaweblog API,在配 置客户端的时候需要填入。例如CPPBLOG的这个地址就是 http://www.cppblog.com/kevinlynx/services/metaweblog.aspx。这个页面展示了一些API 说明。这些API就是博客客户端和服务器进行操作通信的接口。意思是说,服务器端提供这 这些接口,我们的客户端调用这些接口即可。例如:

blogger.deletePost,调用该接口即可删除一篇博客文章

但是客户端如何调用到这个接口呢?这需要通过一种新的技术(或者说标准),即 xml rpc 。rpc大家应该清楚,xml rpc其实说白了, 就是把接口调用的细则塞进 http 请求发给web服务器,服务器接收请求完成操作后再把结果以http回应的形式丢给客户端, 即完成了一次接口调用

至于http请求回应的细则就不提了,无非就是一些特殊格式的数据,通过tcp连接与服务器 交互这些数据。

所以,基本上,整个过程还是非常简单。如何来将调用细节塞进http请求,则是以xml rpc 标准来做,其格式正好是xml格式。举个例子吧:

<?xml version='1.0'?>
<methodCall>
    <methodName>title_or_id</methodName>
        <params>
        </params>
</methodCall

当然这部分数据之前就是若干http请求的数据。服务器回应也是以xml格式组织:

<?xml version='1.0'?>
<methodResponse>
    <params>
        <param>
            <value><string>Welcome to Zope.org</string></value>
        </param>
    </params>
</methodResponse>

我们的博客客户端所要做的,就是把这些博客发布相关的操作封装起来提供给使用者。底层 实现主要包括http请求、xml-rpc的组织等。何况,这两部分在各个语言里都有大量的库存 在,lisp自然也有。

我这里直接选取了lisp的一个xml-rpc库:s-xml-rpc,基本上百来行代码就可以把各个功 能跑一遍。例如以下lisp代码就实现了通过s-xml-rpc删除CPPBLOG的一篇文章:

(defun delete-post (postid)
  (rpc-call
    "blogger.deletePost"
    postid
    "kevinlynx"
    "password"
    t))

发布博客也很简单,根据metaweblog API接口的说明,发布博客时需要填充一个结构体。但 主要涉及到的数据仅包括:文章内容、文章标题、文章分类(可选):

(defun new-post (title context &optional (cates))
  (rpc-call
    "metaWeblog.newPost"
    ""
    "kevinlynx"
    "password"
    (new-post-struct title context cates)
    t))

值得注意的是,如果文章中有贴图,则需要事先将图片文件上传到服务器。CPPBLOG的 metaweblog API里恰有API提供:

(defun new-media-object (filename)
  (rpc-call
    "metaWeblog.newMediaObject"
    ""
    "kevinlynx"
    "password"
    (new-media-object-struct filename)))

该函数读入图片文件,然后调用metaWeblog.newMediaObject接口,即可完成上传。上传成 功后,服务器会返回该图片的URL。然后在我们的文章中就可以使用该图片了。

完整实现方案

仅仅将metaweblog的一些接口做封装,对于一个可以使用的博客客户端来说还远远不够。大 部分同类工具都有一个友好的GUI编辑界面。我并不打算弄一个编辑界面出来,吃力不讨好 的事情。

我的打算是先用其他工具对文章做排版处理,最后导出为html格式。因为CPPBLOG支持直接 发布一个html文件。然后在用这个lisp工具将整个文件作为博客文章内容发布。

恰好公司最近打算用reStructureText(rst)格式来编辑文档,作为熟悉手段,我决定拿这个 来练手。rst格式非常简单,同wiki命令很相似。在vim里编辑该文件非常合适,因为默认支 持。见图:

imgs/rst.png

由图即可看出,rst是一种半所见即所得的格式。即:它遵循你在编辑器里的排版,同时也 通过一些tag(例如image)来控制更丰富的输出。

rst有很多前端工具,可以将rst文件输出,例如rst2html.py就可以输出为html。好吧,最 最终我们得到了html格式的博客文章。

但是如果文章中出现了图片,而图片基本上在本地,转成html后也是相对路径。我需要我的 lisp writer(cl-writer)能自动扫描文章,发现有图片的地方,就自动将图片上传。最恶心 的是上传后还得替换图片引用路径。这个工作可以在rst格式上做,也可以在结果格式html 上做。通过xml解析库解析html比直接解析rst格式更简单,并且在扩展性上更好。

最终这个html中图片路径替换工作只消耗了不到100行lisp代码。这在很大程度上也依赖于 s-xml库的接口设计。

最终封装好的发布接口如下,从这里也可以看出,函数式语言锻炼我们写出功能单一代码度 短小的接口:

(defun writer-post-new (post-file &key (u (get-default-user))(cates))
  (read-post-file u post-file context title
                  (new-post u title context cates)))

END

别指望我发布的代码能够让你一键在你的博客上留下"this is a test",你甚至别指望它能 能够工作。但如果你本来就是一个资深的lisper,或者虽然不是lisper但却执意想看看结果 。这里我就简要说说如何让这些代码欢乐起来:

  1. OS Ubuntu10.04,下载安装SBCL,不会有问题;

  2. 下载安装quicklisp,官方文档hand by hand,简单不会有问题;

  3. SBCL交互环境中使用quicklisp安装s-xml-rpc:

    (ql:quickload "s-xml-rpc")
    
  4. 装载我的代码:

    (asdf:load-system :cl-writer)
    
  5. 在home下添加配置文件.cl-writer.lisp,配置你博客信息,例如:

    (in-package cl-writer)
    (setf *default-user* (make-cppblog-user "账户名" "密码"))
    

    如果你的博客不在CPPBLOG,虽然也许也是metaweblog,但我不能保证成功,配置文件则 要复杂点:

    (setf *default-user* (make-user-info :name "帐户名"
                          :password "密码" :host "www.cppblog.com"
                          :url "/kevinlynx/services/metaweblog.aspx"))
    
  6. SBCL交互环境下测试:

    (in-package cl-writer)
    (new-post (get-default-user) "this is a test" "title")
    

下载代码

最后,终于敲完这篇文章,我需要通过以下步骤来发表它:

in shell:
rst2html.py lisp_xml_rpc.rst lisp_xml_rpc.html
in SBCL:
(writer-post-new "lisp_xml_rpc.html")

;;EOF;;

posted @ 2011-03-13 13:19 Kevin Lynx 阅读(16789) | 评论 (8)编辑 收藏

飞秋lua版:luafeiq0.1.0发布

继上次捣鼓出了飞秋的群聊协议后,鉴于年底没啥事情做,就用lua写了个简单的协议兼容的IM。本来开始让

另一个同事在iptux的基础上修改的,结果大概是因为iptux的代码不是那么容易修改,就不了了之了。这个

刚发布的luafeiq功能非常简单,仅支持与飞秋(包括大部分兼容IP messager的IM)进行单聊,群消息的

收发,简易的消息盒子(暂存未读消息)。因为选的库都是跨平台的,所以很容易的luafeiq也是跨平台的,

最主要的是我想在linux下使用。

 

之所以选用lua,一方面是想练练lua,另一方面则是因为开发效率。前段时间在android下写了些java代码

用java写代码觉得甚为爽快(当然算不了完美)。这几天写了千把行的lua(也许有3K行,未统计过),

感觉也不错。综合来说,这些高级语言的很多好用的语法特性,例如闭包(closure),垃圾回收,都提高

了不少写代码的速度。当然,lua于我而言也算不上完美的语言。例如我经常因为变量敲错字母,而在运行时

才暴露nil错误。这也许可以通过诸如IDE之类的工具在写代码的时候就给予提示。lua 在遇到一个符号时,

默认地将其处理为全局的。关于这个语法特性早有人提出不爽,只能说大家设计的准则不一样。(在我们

项目里,我直接改写了全局变量的metatable,从而防止策划随意定义全局变量)

 

再来谈谈实现过程中的一些琐事。因为飞秋也算是IP messager协议的兼容实现,很多通信除了可以使用

抓包软件分析外,还可以直接通过IP messager的源码来了解。所以,基础通信协议的实现过程也比较

简单。飞秋与飞秋之间发送私聊消息是经过加密的。其加密过程也不简单,更重要的是,我并不想浪费太

多时间在这上面。后来发现其实可以通过上线消息里某个标志位表明自己不需要加密。这个标志就是消息头

里的option。上线广播出去的消息里一旦表明自己不加密,那么以后和飞秋通信也就不需要解密了。

 

发送私聊消息时,消息里会携带一个消息ID。这个ID可以通过任意算法生成,例如直接取time的值。接收到

对方的消息时,需要取出该ID,然后加入回应消息。对方收到回应消息后,就知道自己发送成功。这个过程

算是ip messager在UDP上做的消息可靠验证,过程也比较简单。

 

群聊消息在之前提到过,是通过UDP多播实现。我们可以接收所有群的消息。如果之前已经处于某个群里,

那么一旦你上线后(广播上线消息),你就可以直接在这个群里发言。但如果你之前不在这个群里,则

可以通过多播一个加入群的消息,然后就可以不请自来地在这个群里发言。详细的消息值和实现都可以从

luafeiq的代码里读到(message_sender.lua)。

 

在linux下接收windows上的飞秋消息,是需要做字符编码转换的。因为luafeiq使用IUP作为UI库,IUP在

linux下使用GTK作为底层实现,默认全部是UTF8编码。luafeiq里我自己写了个lua库,用于编码转换。

 

话说IUP作为一个UI库,还是比较不错的。正如其介绍文档里所说,学习曲线低,基本上看一会文档,就可以

直接使用了。luafeiq使用的IUP版本至少需要3.0以上。当初在linux下为了安装IUP3.3,基本花了4个小时

时间,各种奇怪的没多大意义的错误信息。后来换成3.2版本,居然一下子就和谐了,无限怨念。

 

luafeiq目前放在googlecode的版本,可以说是一个很不负责任的版本。早上我才刚把字符编码转换的代码

调试好。今天已经请假,家里就一台电脑,也就测试不了这个字符编码转换是否真的能正常工作。我在

windows下dump了些字符,看上去能正常功能。明天得回老家过春节,上不了网,索性就提前发布了。

 

luafeiq项目地址:http://code.google.com/p/luafeiq/

posted @ 2011-01-31 16:51 Kevin Lynx 阅读(4462) | 评论 (2)编辑 收藏

逆向思路:破解飞秋群聊协议

题外

飞秋是一款局域网内的IM软件,界面类似QQ,实现上与飞鸽(IP message)有点渊源,免费,不开源。

公司大概两年前开始使用这款软件作为员工之间办公吹牛的工具。最近游戏玩得少,就想彻底换到linux下,

组内也有其他两人是llinux-er,不过悲剧的是换到linux下就无法收取飞秋群里的聊天信息了,不免寂寞。

所以,就想写个协议兼容的程序(或者说改个东西)来收取群信息。

 

准备

我本身并不擅长逆向工程,破解什么的纯碎业余。在GOOGLE/BAIDU之后发现并没有前人留下的成果。

使用抓包程序,以及综合网络上的信息,还是可以得出不少有用的信息:

# 飞秋兼容了飞鸽的协议,其协议格式基本上基于文本形式,各个内容之间使用冒号作为分隔,例如:

1:100:user:pcname:32:message_body

# 飞秋在私聊情况下的消息内容是没有加密的,但群聊信息加密了,解密这个内容也是我的目标所在

# 在抓包软件下根据消息的目标IP地址可以推断飞秋发送群信息是基于UDP组播的,即就算你不是这个群

   的成员,也会收到群消息

有用的文章: 《局域网内实现飞鸽欺骗》《飞鸽传书数据加密分析》(个人感觉没有任何实质内容,而

且飞鸽传书并不是飞秋,属于误导性文章,但是依然有用)。最重要的,稍微浏览IP message的代码,

以及linux下的iptux(另一个兼容飞鸽的局域网IM)代码,都是对接下来的破解有益的。

 

破解

我希望我提供更多的,是一种crack的思路,虽然我不是一个cracker。破解和写程序不太一样,它需要

更多的耐心、运气、程序之外的思考。如前所做的准备,尤其重要。

工具及环境:飞秋2.4版本、OllyDbg,为了方便接收群信息,最好有两台电脑。

 

STEP 1 找入手点

在开始面对一大推汇编代码时,我们需要一个最接近目标的点。获取这个点根据目标的不同而不同。例如,

这里主要是针对网络数据的解密。所以,最直接的就是去找这些网络数据。当然,根据具体程序的表现,也

可以从其他点入手,例如飞秋收到群消息后会在任务栏闪烁图标,也可以从这个功能逆向过去。

 

因为飞秋使用UDP协议,所以我们可以在recvfrom函数下断点(bp recvfrom)。因为接收UDP包的接口

可能还有WSARecvFrom,甚至winsock1.0中的recvfrom,所以最好都下断点。另一台机器发送群消息,

程序在winsock1.0里的recvfrom断下来:

71A43001 >  8BFF            mov     edi, edi
71A43003    55              push    ebp
71A43004    8BEC            mov     ebp, esp
71A43006    51              push    ecx

这个不是我们需要的,我们需要根据这个点获得用户层代码,这将是整个破解过程的起点。所以,OD中

ALT+K查看调用堆栈,然后跳到调用recvfrom的函数处:

00490890  /$  56            push    esi                              ;  接收数据的函数入口
00490891  |.  8B7424 08     mov     esi, dword ptr [esp+8]
00490895  |.  8D46 10       lea     eax, dword ptr [esi+10]
00490898  |.  50            push    eax                              ; /pFromLen
00490899  |.  56            push    esi                              ; |pFrom
0049089A  |.  C700 10000000 mov     dword ptr [eax], 10              ; |
004908A0  |.  8B09          mov     ecx, dword ptr [ecx]             ; |
004908A2  |.  6A 00         push    0                                ; |Flags = 0
004908A4  |.  8D46 18       lea     eax, dword ptr [esi+18]          ; |
004908A7  |.  68 FF3F0000   push    3FFF                             ; |BufSize = 3FFF (16383.)
004908AC  |.  50            push    eax                              ; |Buffer
004908AD  |.  51            push    ecx                              ; |Socket
004908AE  |.  E8 C7F30C00   call    <jmp.&WSOCK32.#17>               ; \recvfrom

邪恶的OD已经将调用recvfrom时传入参数的指令标记出来了。中文注释是我分析时加的。recvfrom里传入

的接收缓存,是我们应该关注的。如果能跟进这个缓存,假设程序的流程比较简单:接收了数据,然后在某个

地方直接解密,不管它的加密方式是什么,只要能找到这个缓存数据从加密变为解密的地方,对于整个破解而言,

都算是迈进了一大步。

于是,在00490890(上面找到的函数入口)下断点,准备跟进接收缓存。注意:在OD里调试跟在vc里不一样,

跳到调用堆栈里的某个函数,寄存器依然是当前的值。所以需要重新跟。

 

STEP 2 内存断点

F9让程序继续运行,再次在另一台机器上发送群消息。这回程序在00490890处断下,然后跟接收缓存:

004908AC  |.  50            push    eax                              ; |Buffer = 0011F4CC
004908AD  |.  51            push    ecx                              ; |Socket
004908AE  |.  E8 C7F30C00   call    <jmp.&WSOCK32.#17>               ; \recvfrom

接收缓存Buffer的值为0011F4CC,如前所述,我们要跟进这个地址指向的内存的变化情况。F8单步运行到

recvfrom后,也就是接收了网络数据后,查看内存内容

(d 0011F4CC):

0011F4CC  31 5F 6C 62 74 34 5F 30 23 31 32 38 23 38 38 41  1_lbt4_0#128#88A
0011F4DC  45 31 44 44 34 36 36 46 44 23 30 23 30 23 37 32  E1DD466FD#0#0#72
0011F4EC  3A 31 32 39 35 37 32 31 32 31 33 3A 41 64 6D 69  :1295721213:Admi
0011F4FC  6E 69 73 74 72 61 74 6F 72 3A 50 43 2D 32 30 31  nistrator:PC-201
0011F50C  30 31 31 30 34 32 30 30 35 3A 34 31 39 34 33 33  011042005:419433
0011F51C  39 3A 5E 3B 83 A1 14 6D A4 D2 E3 D8 E8 AB B1 3A  9:^;儭mひ阖璜?
0011F52C  5B BC C2 FE E9 DA CB DD 00 BC 59 FC 9D A7 D7 91  [悸谒?糦鼭ё

内容开头正是飞秋的协议头,未加密,不过没多大用。根据之前获取的飞秋协议,可知,在0011F51E

处就是聊天内容的密文。

很自然地,为了监视这段内存的变化情况,在该位置下内存访问断点(右击数据区即可看到下断点的选项)。

F9继续走,然后马上断下来:

0049010F  |.  F3:A5         rep     movs dword ptr es:[edi], dword ptr [>
00490111  |.  8B4A 04       mov     ecx, dword ptr [edx+4]
00490114  |.  C74424 24 000>mov     dword ptr [esp+24], 0
0049011C  |.  894D 64       mov     dword ptr [ebp+64], ecx
0049011F  |.  33C9          xor     ecx, ecx

程序到了一个陌生的环境(在这种满世界都是汇编代码的情况下,几乎一不小心就会迷失其中),看了下

附近的代码,没什么可疑。通过下内存访问断点的思路,似乎显得荆棘丛生。

 

STEP 3 靠近目标

不妨冷静下来思考,如果没有直接的路,我们可能需要悲惨地大海捞针。在写一个网络程序时,网络底层

收到数据包,无非要么直接进行逻辑处理,要么缓存到一个逻辑处理队列里稍后处理。后者虽然对于程序员

而言是个好方法,但是因为跨了线程,又涉及到队列缓存,对于逆向而言,绝对是悲剧。

 

但是如果使用了前者呢?对于一个网络客户端程序而言,也许直接进行逻辑处理才是最KISS的方法。(这种猜测

的破解方式,绝对需要运气。)所以,如果是直接进行处理,那么在接收到网络数据附近,必然就有解密函数。

所以,不妨顺着收包函数附近随意浏览一番。(但不要走进太深的call,不然又迷失了。)

0048FE10  /$  B8 18400000   mov     eax, 4018                          
0048FE15  |.  E8 560A0C00   call    00550870
0048FE1A  |.  8D4424 00     lea     eax, dword ptr [esp]
0048FE1E  |.  56            push    esi
0048FE1F  |.  8BF1          mov     esi, ecx
0048FE21  |.  50            push    eax
0048FE22  |.  E8 690A0000   call    00490890                             ;  接收网络数据

0048FE10函数调用了刚才发现的收包函数。这个函数在收完数据后,不久就调用了另一个函数:

0048FE3F  |.  51            push    ecx
0048FE40  |.  52            push    edx
0048FE41  |.  8BCE          mov     ecx, esi
0048FE43  |.  E8 88020000   call    004900D0                             ;  似乎很可疑?

进到004900D0函数,发现这个函数真TMD巨大。随意浏览之,发现OD有这种提示:

00490178  |.  68 34FD5E00   push    005EFD34                             ;  ASCII "_lbt"
0049017D  |.  8D4C24 14     lea     ecx, dword ptr [esp+14]
00490181  |.  89BC24 544000>mov     dword ptr [esp+4054], edi

_lbt,恩,消息头里有这个字符串标识。估计是在做些消息头的逻辑操作。这个函数太长,里面还有若干call,

可谓头大。所以说,代码写得丑,可读性差,对于防破解还是颇有益处的。跳回到0048FE43,发现当前

函数基本完了。

 

于是往上看,来到调用这个函数的地方:

0050F647  |.  E8 C407F8FF   call    0048FE10
0050F64C  |.  BF 01000000   mov     edi, 1

回顾下,我们有函数A接收网络数据,有函数B调用A,现在回到了C,来到了调用B的地方0050F647。C函数

也很巨大,直接往下浏览,会发现一些switch语句:

0050F71A  |.  81E6 FF000000 and     esi, 0FF
0050F720  |.  8D46 FF       lea     eax, dword ptr [esi-1]               ;  Switch (cases 1..D3)
0050F723  |.  3D D2000000   cmp     eax, 0D2
0050F728  |.  0F87 8C000000 ja      0050F7BA
0050F72E  |.  33C9          xor     ecx, ecx
0050F730  |.  8A88 60315100 mov     cl, byte ptr [eax+513160]
0050F736  |.  FF248D 403051>jmp     dword ptr [ecx*4+513040]
0050F73D  |>  8D9424 F40000>lea     edx, dword ptr [esp+F4]              ;  Case 1 of switch 0050F720

往后浏览下这个switch…case,发现非常之大,这个函数也因此非常巨大。不妨猜测这个是根据不同消息做不同

逻辑处理的地方。这个想法正是给予我们灵感的关键。

 

群聊消息必然也有个类型,通过之前OD获取到的网络数据(或者截取网络封包所得),群聊消息的类型为:4194339

(16进制400023H),去掉高位,也就是23H。仔细地对比每一个case,果然发现了一段处理代码:

00512787  |> \39AC24 640100>cmp     dword ptr [esp+164], ebp             ;  Case 23 of switch 0050F720
0051278E  |.  75 07         jnz     short 00512797                       ;  群聊天处理
00512790  |.  8BC7          mov     eax, edi
00512792  |.  E9 8C080000   jmp     00513023

这个代码之下的处理也有不少代码。在不涉及到更多细节之前,我们可以大胆地将注意力放在接下来的call上。从这个case

往下,第一个call为:

005127E6  |.  50            push    eax
005127E7  |.  E8 A4A20000   call    0051CA90                             ;  非常可疑
005127EC  |.  B8 01000000   mov     eax, 1
005127F1  |.  E9 2D080000   jmp     00513023

 

STEP 4 多尝试

有怀疑,就用事实来证明。果断地在005127E6处下断点。然后发群消息,程序断下来。因为这个函数压入了

eax作为参数,且对ecx做了赋值:

005127E4  |.  8BCB          mov     ecx, ebx
005127E6  |.  50            push    eax
005127E7  |.  E8 A4A20000   call    0051CA90                             ;  非常可疑

在调用一个函数前对ecx做赋值,一般都是C++成员函数调用。eax作为一个参数,非常值得关注,果断查看eax

指向的内存值:

001235C8  41 64 6D 69 6E 69 73 74 72 61 74 6F 72 00 6D 00  Administrator.m.
001235D8  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
001235E8  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
001235F8  00 00 50 43 2D 32 30 31 30 31 31 30 34 32 30 30  ..PC-20101104200
00123608  35 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  5...............
00123618  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00123628  8A 7B 00 00 C0 A8 00 03 09 79 00 00 01 00 00 00  妠..括..y.....
00123638  04 00 00 00 00 00 00 00 80 00 00 00 38 38 41 45  .......€...88AE
00123648  31 44 44 34 36 36 46 44 00 00 00 00 00 00 00 00  1DD466FD........
00123658  00 00 00 00 F4 C7 23 00 FD 22 3B 4D 23 00 40 00  ....羟#.?;M#.@.
00123668  49 00 00 00 36 00 00 00 5E 3B 83 A1 14 6D A4 D2  I...6...^;儭mひ

有用户名、机器名、发送者MAC地址,这么多可疑信息。完全可以猜测,eax传入的是一个结构体地址,

当然对象地址也可以,反正是个复杂数据结构。更重要的,在这块内存往下不远处,果断地发现了从

网络接收到的加密的聊天内容:

00123670  5E 3B 83 A1 14 6D A4 D2 E3 D8 E8 AB B1 3A 5B BC  ^;儭mひ阖璜?[
00123680  C2 FE E9 DA CB DD 00 BC 59 FC 9D A7 D7 91 CF 5A  漫橼溯.糦鼭ё懴Z

F8直接步过0051CA90函数。任务栏开始出现闪烁的图标(虽然没有闪),上面的内存数据变了:

00123670  74 65 73 74 7B 2F 66 6F 6E 74 3B 2D 31 34 20 30  test{/font;-14 0
00123680  20 30 20 30 20 34 30 30 20 30 20 30 20 30 20 31   0 0 400 0 0 0 1
00123690  33 34 20 33 20 32 20 31 20 32 20 CB CE CC E5 20  34 3 2 1 2 宋体

test正是我发的内容。

 

STEP 5 缩小范围

实际上走到这里,凭借运气和程序编写的常识,已经找到关键点。不过看来0051CA90这个函数做的事情

有点多,除了解密内容似乎还有UI上的一些处理(例如那个闪烁的任务栏图标)。所以,我们要做的是,进一步

跟进,找到关键点。

 

现在缩小范围要容易得多,因为我们得到了一个会变化的内存地址:00123670。只需要F8一步一步地

运行代码,一旦发现内存内容改变,则可以进一步进如,从而找到关键call。具体过程我就不给了,大概为:

0051CB02  |.  52            push    edx
0051CB03  |.  68 00400000   push    4000
0051CB08  |.  56            push    esi
0051CB09  |.  50            push    eax
0051CB0A  |.  56            push    esi
0051CB0B  |.  E8 F041F7FF   call    00490D00                             ; 跟进

 

00490DB0  |.  6A 00         push    0
00490DB2  |.  83E1 03       and     ecx, 3
00490DB5  |.  6A 22         push    22
00490DB7  |.  F3:A4         rep     movs byte ptr es:[edi], byte ptr [es>
00490DB9  |.  8BBC24 344000>mov     edi, dword ptr [esp+4034]
00490DC0  |.  50            push    eax                                  ;  数据长度
00490DC1  |.  8D4424 20     lea     eax, dword ptr [esp+20]
00490DC5  |.  57            push    edi                                  ;  输出缓存
00490DC6  |.  50            push    eax                                  ;  输入缓存(加密内容)
00490DC7  |.  8D4C24 20     lea     ecx, dword ptr [esp+20]
00490DCB  |.  E8 5049F7FF   call    00405720                             ;  最终解密函数

 

00405720函数内的实现基本上全是数据操作指令。加解密算法无非就是捣鼓这些数据,所以当我进到

00405720函数时,基本上可以断定它就是最终的解密函数。

 

STEP 6 解密

事实上我们并不需要去弄懂它的具体解密算法,就算是直接的C++代码,没有算法论文的话也很难看懂,更何况

是这里的汇编。最直接的方式,就是查看这个解密函数对外界的依赖情况,例如需要的参数,this里是否有依赖

的数据。在了解了这些情况后,大可以将这段汇编复制出来直接作为C++内嵌汇编代码使用。

 

不过,这里我想到了更简单的方式。因为我注意到飞秋和飞鸽在实现上有着不解之缘,而且我琢磨着作者也不会

为了一个加解密不太重要的应用场合而去整些高深的算法。我想到,飞秋也许会直接使用飞鸽里的加解密代码!

 

在IP message的源码里,有blowfish加密算法的实现,我们来看接口:

class CBlowFish
{
private:
    DWORD    *PArray;
    DWORD    (*SBoxes)[256];
    void    Blowfish_encipher(DWORD *xl, DWORD *xr);
    void    Blowfish_decipher(DWORD *xl, DWORD *xr);

public:
            CBlowFish(const BYTE *key=NULL, int keybytes=0);
            ~CBlowFish();
    void    Initialize(const BYTE *key, int keybytes);
    DWORD    GetOutputLength(DWORD lInputLong, int mode);
    DWORD    Encrypt(const BYTE *pInput, BYTE *pOutput, DWORD lSize, int mode=BF_CBC|BF_PKCS5, _int64 IV=0);
    DWORD    Decrypt(const BYTE *pInput, BYTE *pOutput, DWORD lSize, int mode=BF_CBC|BF_PKCS5, _int64 IV=0);
};

从接口实现来说算是简洁漂亮友好和谐。我也用Decrypt这个函数的参数比对了上面没找到的那个call(00405720),

因为这里只是怀疑这个call就是这里的Decrypt,但并没有确切的证据。不过,对比下他们的参数就可以非常肯定了:

00490DB0  |.  6A 00         push    0           ;参数IV
00490DB2  |.  83E1 03       and     ecx, 3
00490DB5  |.  6A 22         push    22        ;参数mode
00490DB7  |.  F3:A4         rep     movs byte ptr es:[edi], byte ptr [es>
00490DB9  |.  8BBC24 344000>mov     edi, dword ptr [esp+4034]
00490DC0  |.  50            push    eax                                  ; 参数 数据长度
00490DC1  |.  8D4424 20     lea     eax, dword ptr [esp+20]
00490DC5  |.  57            push    edi                                  ;  参数输出缓存
00490DC6  |.  50            push    eax                                  ; 参数输入缓存(加密内容)
00490DC7  |.  8D4C24 20     lea     ecx, dword ptr [esp+20]
00490DCB  |.  E8 5049F7FF   call    00405720                             ;  最终解密函数

最重要的,是参数mode。Decrypt默认参数mode是BF_CBC|BF_PKCS5的位组合,结果,恰好为22!

所以,基本上可以断定:飞秋的加解密实现,就是使用了IP message的blowfish算法:blowfish.cpp/h/h2。

 

STEP 7 密钥

查看CBlowFish的使用,在解密前需要初始化,大概就是传入密钥之类。如果我们上面的猜测没有错,那么我们

从网络上取得的数据,然后取得密钥,直接使用blowfish的源码,就可以解密出消息内容。

 

接下来的关键就是,找到这个密钥。关于这个密钥,之前在飞秋的配置文件FeiqCfg.xml里绕了很久的圈子,因为

发现加入一个群的时候,这个文件里就会多出一项很长的16进制字符串。也一度猜测密钥就是保存在这个字符串的

某个偏移里。接下来会让人大跌眼镜。

 

因为CBlowFish这个类确实简单,使用它的最简单方式就是直接创建局部对象,然后传入key和keysize,即可完成

初始化。在之前展示的思路里,我也一度先去尝试最简单的方法。对于C++局部对象的创建,有个显著特征就是

mov ecx, dword ptr [esp+xxx],也就是往ecx里写入一个栈地址。而且可以肯定的是,这个构造代码,必然发生

于call 00405720前面不远处,往上跟进:

00490D3F  |> \8B8C24 304000>mov     ecx, dword ptr [esp+4030]
00490D46  |>  51            push    ecx                                  
00490D47  |.  52            push    edx                                  
00490D48  |.  8D4C24 0C     lea     ecx, dword ptr [esp+C]
00490D4C  |.  E8 3F3DF7FF   call    00404A90                             

一个压入两个参数的函数调用,对比CBlowFish的构造函数,刚好是2个参数。跟进00404A90:

 

00404A90  /$  56            push    esi
00404A91  |.  8BF1          mov     esi, ecx
00404A93  |.  6A 48         push    48
00404A95  |.  E8 69301600   call    00567B03
00404A9A  |.  68 00100000   push    1000
00404A9F  |.  8906          mov     dword ptr [esi], eax
00404AA1  |.  E8 5D301600   call    00567B03

 

又是可爱的立即数!48H、1000H,这种特别的立即数总能让人安心,对比CBlowFish构造函数实现:

CBlowFish::CBlowFish (const BYTE *key, int keybytes)
{
    PArray = new DWORD [NPASS + 2];//NPASS=16
    SBoxes = new DWORD [4][256];

    if (key)
        Initialize(key, keybytes);
}

sizeof(DWORD)*18=48H,sizeof(DWORD)*4*256=1000H!这么极具喜剧意义的汇编C++代码映射,

基本可以肯定,00404AA1处,正是构造CBlowFish对象的地方,而构造的参数,正是我们魂牵梦萦的解密密钥:

 

00490D46  |> \51            push    ecx                                  ;  key长度
00490D47  |.  52            push    edx                                  ;  密钥key
00490D48  |.  8D4C24 0C     lea     ecx, dword ptr [esp+C]
00490D4C  |.  E8 3F3DF7FF   call    00404A90                             ;  构造blowfish对象

 

在此处下断点,发送群消息,程序断下来,看看密钥究竟是什么。如果它确实是FeiqCfg.xml里的某个值,

那么我们还要进一步跟这个值具体在哪个配置项里。看看吧,密钥edx:

 

edx=00123644, (ASCII "88AE1DD466FD")

 

 

TM的密钥居然是发送者的MAC地址!当我看到这个的时候我几乎快摔倒地上。如果飞秋使用一个MAC地址

作为密钥,那么这意味着:通过自己写的程序,可以取得局域网内其他群里的聊天内容!这个实在太邪恶了。

上回抓包的时候,虽然看不到内容,但可以看到美术、策划在群里聊的无比欢乐。这回有喜感了。

 

STEP END 可略

看看时间,悲剧地发现整篇文章花了接近3个小时才写完。此刻我正踌躇要不要把代码发上来,但转念一想

最后那个STEP的发现实在让人蛋疼,所以还是算了。打算稍微封装下,然后使用这份代码在iptux 上改改包装

个界面,目的就算达成了。相信浏览完整篇文章,写出自己的代码不是什么大问题。

 

其实我大可以直接给结论,但是我依然乐于分享过程和思路。一来算是自我总结记录(每次拿起OD,总是快捷

键一路忘);二来也给有心人一个指引。

 

最后,对这种东西还是有必要出个免责声明:根据本文章所造成的一切后果与文章作者无关。为了不糟蹋我这3个

小时的时间,转载麻烦注明出处。

PS,最后回顾下结论,其实发现这个解密非常非常简单。你说如果直接给卢本陶(飞秋作者)发封邮件,他会不

会直接告诉我?

posted @ 2011-01-23 21:01 Kevin Lynx 阅读(25263) | 评论 (9)编辑 收藏

一段tricky codes:函数调用的那些底层细节


有一天,被同事问到了下面这段代码,就简单分析了一下,发觉还有点意思:

__declspec(naked)
void call(void* pfn, 
{
    __asm 
    
{
        pop eax;
        add eax, 
3;
        xchg dword ptr[esp], eax;
        push eax;
        ret;
    }

}

 

再看它的用法:

 

void print_str( const char *s )
{
    printf( 
"%s\n", s );
}

call( print_str, 
"a string" );

 

call函数的大致作用,就是调用传递进去的函数print_str,并将参数"a string"传递给目标
函数。

但是它是怎么做到的呢?虽然call只有简单的几句汇编代码,但是却包含了很多函数在编译
器中的汇编层实现。要了解这段代码的意思,需要知道如下相关知识:

0、函数调用的实现中,编译器通过系统堆栈(ESP寄存器指向)传递参数;
1、C语言默认的函数调用规则(_cdecl)中,调用者从右往左将参数压入堆栈,并且调用者负
责堆栈平衡,也就是保证调用函数的前后,ESP不变;
2、汇编指令call本质上是先将返回地址,通常是该条指令的下一条指令压入堆栈,然后直
接跳转到目标位置;
3、汇编指令ret则是先从堆栈栈顶取出返回地址,然后跳转过去;
4、汇编指令add加上其操作数,貌似占3个字节长度;
5、在visual studio中,DEBUG模式下编译器会在我们的代码中插入各种检测代码,而
__declspec(naked)则是告诉编译器:别往这里添加代码。

了解了以上常识后,再看这段代码,其本质无非就是利用了这些规则,在代码段跳来跳去。
我们来逐步分析一下:

在调用call函数的地方,大概的代码为:

 

caller:
// 堆栈状态,从左往右分别表示栈顶至下
// ret_addr是call后的地址,即add esp, 8的位置
// a1, a2表示函数参数,callee_addr是这里的print_str
// stack: ret_addr, callee_addr, a1, a2, 
call( print_str, "a string" ); 
add esp, 
8 //清除参数传递所占用的堆栈空间,维持堆栈平衡
end_label //位于add后的指令,后面会提到

call:
// 此时堆栈stack: ret_addr, a1, a2
pop eax // eax = ret_addr; stack: callee_addr, a1, a2, 
add eax, 3 // eax = end_label; stack: callee_addr, a1, a2, 
xchg dword ptr[esp], eax // eax = callee_addr; stack: end_label, a1, a2, 
push eax // stack: callee_addr, end_label, a1, a2, 
ret // 取出callee_addr并跳转,也就跳转到print_str函数的入口,此时堆栈
    
// stack: end_label, a1, a2, 

callee(print_str):

 无视函数内容

ret 
// print_str返回,此时正常情况下,堆栈stack: end_label, a1, a2, 
 
// 取出end_label并跳转,stack: a1, a2, 

 

那么当callee结束时,则跳转回caller函数中。不过,如过你所见,此时堆栈中还保留着再
调用call函数时传入的参数:stack: a1, a2, ...,所以,DEBUG模式下,VS就会提示你堆
栈不平衡。这里简单的处理就是手动来进行堆栈平衡:

 

    call( print_str, "a string" );
    __asm
    
{
        add esp, 
4
    }

 

传入了多少个参数,就得相应地改变esp的值。

话说距离上篇博客都有半年了,自己都不知道时间晃得如此之快。最近业余折腾了下android开发
一不小心就跨年了。
 

posted @ 2011-01-02 16:34 Kevin Lynx 阅读(4862) | 评论 (4)编辑 收藏

网游中的玩家移动

     摘要: MMORPG中,玩家的移动主要逻辑都放在客户端进行,包括自动寻路和响应玩家的操作,服务
器在这里担当一个被动角色。但是服务器端的玩家数据却是真正的被其他逻辑模块参考的数
据。  阅读全文

posted @ 2010-06-22 21:27 Kevin Lynx 阅读(4711) | 评论 (8)编辑 收藏

仅列出标题
共12页: First 2 3 4 5 6 7 8 9 10 Last