九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

反汇编时的函数识别及各函数调用约定的汇编代码分析


 反汇编时的函数识别及各函数调用约定的汇编代码分析

write by 九天雁翎(JTianLing) -- www.jtianling.com

其实在刚开始工作的时候,我就因为工作中需要处理异常处理时的dump,就分析过C++的函数调用原理,也写过一篇文章,现在因为另外的原因(反外挂)而重新提起,回头看以前写的文章,实在是略显稚嫩:)也是,那是9个月前的事情了。

原文《C++函数调用原理理解》http://www.jtianling.com/archive/2008/06/01/2501238.aspx

 

首先看一个很简单的例子(此例子的更简单原型(一个add函数)来自于《加密与解密》一书第三版第4章的第2节),这里列举出了各种函数调用约定的ADD函数(其实还有PASCAL调用约定,但是作为C++程序员我忽略了那种,所以我提到的几种函数调用约定都是参数反向入栈的,此点再下面不再提起)这里的编译器选择了VC6,不是我喜欢仿古。。。但是,因为VS2005(我平时用的)的优化太过于激进。。。。不知道此词妥否。。。。起码一般的小测试程序几乎不能反汇编得到什么信息,一般就是直接在编译器完成了很多操作了。这个我在以前也提到过,

比如在《Inside C++ Object 》 阅读笔记(1), NRV(Named Return Value)一文中:

http://www.jtianling.com/archive/2008/12/09/3486211.aspx

 

示例源代码1:

 

 1 int __cdecl Add1(int x,int y) // default
 2 {
 3         return(x+y);
 4 }
 5
 6 int __stdcall Add2(int x,int y)
 7 {
 8         return(x+y);
 9 }
10
11 int __fastcall Add3(int x,int y)
12 {
13         return(x+y);
14 }
15
16 int inline Add4(int x,int y)
17 {
18         return(x+y);
19 }
20
21 int main( )
22 {
23         int a=5,b=6;
24         Add1(a,b);
25         Add2(a,b);
26         Add3(a,b);
27         Add4(a,b);
28         return 0;
29  }

 

 

Release编译后,反汇编代码及其注释如下:

 

.text:00401030 ; main函数

.text:00401030

.text:00401030 ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401030 _main proc near ; CODE XREF: _mainCRTStartup+AFp

.text:00401030 push 6

.text:00401032 push 5

.text:00401034 call Add1 ; 将参数压入栈中,并调用Add1(__cdecl调用约定函数,

.text:00401034 ; 即C语言的调用规范,调用者负责栈的维护)

.text:00401039 add esp, 8 ; 此处由调用者维护调用了Add1后的栈,

.text:00401039 ; esp加8是因为两个参数

.text:0040103C push 6

.text:0040103E push 5

.text:00401040 call Add2 ; 参数入栈,并调用Add2(__stdcall调用规范,windows

.text:00401040 ; API的默认调用规范,由被调用者负责维护栈)所以

.text:00401040 ; 此函数调用完后,main函数中不需要有维护栈的操作

.text:00401045 mov edx, 6

.text:0040104A mov ecx, 5

.text:0040104F call Add3 ; 将参数赋值给寄存器edx,ecx,调用Add3(Fastcall调用约定,

.text:0040104F ; 函数尽量通过寄存器传递,也是由被调用者自己维护栈)

.text:00401054 xor eax, eax ; 此处清空eax作为main函数的返回值返回了,注意到并没有

.text:00401054 ; Add4(inline函数)的调用,并且因为返回值并没有用,

.text:00401054 ; 所以此函数即使在VC6中,也忽略了。

.text:00401056 retn

.text:00401056 _main endp

 

 

 

例2,稍微复杂一点

源码:

 1 #include
 2
 3 int __cdecl Add1(int x,int y) // default
 4 {
 5     int z = 1;
 6     return(x+y+z);
 7 }
 8
 9 int __stdcall Add2(int x,int y)
10 {
11     int z = 1;
12     return(x+y+z);
13 }
14
15 int __fastcall Add3(int x,int y)
16 {
17     int z = 1;
18     return(x+y+z);
19 }
20
21 int inline Add4(int x,int y)
22 {
23     int z = 1;
24     return(x+y+z);
25 }
26
27 int main( )
28 {
29     int a=5,b=6;
30     int c = 0;
31
32     c += Add1(a,b);
33     c += Add2(a,b);
34     c += Add3(a,b);
35     c += Add4(a,b);
36     printf("%d",c);
37     return 0;
38  }
39

 

比前面的例子多了一个变量c来累加返回值并输出,每个函数中再多了一个局部变量。

 

Release编译后,反汇编代码及其注释如下:

.text:00401030 ; main函数

.text:00401030

.text:00401030 ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401030 _main proc near ; CODE XREF: _mainCRTStartup+AFp

.text:00401030

.text:00401030 argc = dword ptr 4

.text:00401030 argv = dword ptr 8

.text:00401030 envp = dword ptr 0Ch

.text:00401030

.text:00401030 push esi ; 以下可以看到,esi后来一直用作局部变量c,

.text:00401030 ; 所以此处先保存以前的值

.text:00401031 push 6

.text:00401033 push 5

.text:00401035 call Add1

.text:0040103A add esp, 8

.text:0040103D mov esi, eax ; 默认约定eax是返回值,无论哪种调用约定都是一样的,

.text:0040103D ; 并且因为C/C++函数肯定只能由一个返回值,所以确定

.text:0040103D ; 是eax这一个寄存器也没有关系

.text:0040103F push 6

.text:00401041 push 5

.text:00401043 call Add2

.text:00401048 mov edx, 6

.text:0040104D mov ecx, 5

.text:00401052 add esi, eax

.text:00401054 call Add3

.text:00401059 lea eax, [esi+eax+0Ch] ; 内联的作用,Add4还是没有函数调用,并且用一个lea指令

.text:00401059 ; 实现了c+Add3()+5+6的操作,其中5+6的值在编译器确定

.text:0040105D push eax

.text:0040105E push offset aD ; "%d"

.text:00401063 call _printf

.text:00401068 add esp, 8 ; 可见C语言库函数的调用遵循的是__cdecl约定,所以此处

.text:00401068 ; 由main函数维护栈

.text:0040106B xor eax, eax

.text:0040106D pop esi

.text:0040106E retn

.text:0040106E _main endp

 

与前一个例子重复的内容我注释也就不重复了。

一下具体看看各个Add函数的内容

.text:00401000 Add1 proc near ; CODE XREF: _main+5p

.text:00401000

.text:00401000 arg_0 = dword ptr 4

.text:00401000 arg_4 = dword ptr 8

.text:00401000

.text:00401000 mov eax, [esp+arg_4] ; 因为函数是如此的简单,所以此处并没有将ebp入栈,也

.text:00401000 ; 并没有通过堆栈为z局部变量开辟空间,而是直接用esp

.text:00401000 ; 取参数,用lea指令来完成+1,以下几个函数相同

.text:00401004 mov ecx, [esp+arg_0]

.text:00401008 lea eax, [ecx+eax+1]

.text:0040100C retn ; 这里可以看到Add1函数并没有在内部维护栈,原因也说了

.text:0040100C Add1 endp ; __cdecl调用约定是由调用者来维护栈的

.text:0040100C

.text:0040100C ; ---------------------------------------------------------------------------

.text:0040100D align 10h

.text:00401010

.text:00401010 ; =============== S U B R O U T I N E =======================================

.text:00401010

.text:00401010

.text:00401010 Add2 proc near ; CODE XREF: _main+13p

.text:00401010

.text:00401010 arg_0 = dword ptr 4

.text:00401010 arg_4 = dword ptr 8

.text:00401010

.text:00401010 mov eax, [esp+arg_4]

.text:00401014 mov ecx, [esp+arg_0]

.text:00401018 lea eax, [ecx+eax+1]

.text:0040101C retn 8 ; 此处可以看到Add2自己维护了栈,retn 8相当于

.text:0040101C Add2 endp ; add esp 8

.text:0040101C ; retn

.text:0040101C ; ---------------------------------------------------------------------------

.text:0040101F align 10h

.text:00401020

.text:00401020 ; =============== S U B R O U T I N E =======================================

.text:00401020

.text:00401020

.text:00401020 Add3 proc near ; CODE XREF: _main+24p

.text:00401020 lea eax, [ecx+edx+1] ; 通过寄存器来传递参数,速度自然快,也不破坏栈,所以

.text:00401020 ; 也不用维护,此处的参数较少,所以可以达到完全不用

.text:00401020 ; 栈操作

.text:00401024 retn

.text:00401024 Add3 endp

.text:00401024

 

至此,完全没有源码,看到一个函数的调用,大概也知道参数是什么,返回值是什么,栈维护的操作是在干什么了。

这里再看两个复杂点的例子,一个是局部变量多一点的Add5,一个是参数多一点的fastcall调用的函数Add6

 1 #include
 2
 3 int __cdecl Add5(int x,int y) // default
 4 {
 5     int z1 = 1;
 6     int z2 = ++z1;
 7     int z3 = ++z2;
 8     return(x+y+z1+z2+z3);
 9 }
10
11 int __fastcall Add6(int x,int y,int z)
12 {
13     return(x+y+z);
14 }
15
16
17 int main( )
18 {
19     int a=5,b=6;
20     int c = 0;
21
22     c += Add5(a,b);
23     c += Add6(a,b,c);
24
25     printf("%d",c);
26     return 0;
27  }

 

反汇编:

.text:00401020 ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401020 _main proc near ; CODE XREF: _mainCRTStartup+AFp

.text:00401020

.text:00401020 argc = dword ptr 4

.text:00401020 argv = dword ptr 8

.text:00401020 envp = dword ptr 0Ch

.text:00401020

.text:00401020 push esi

.text:00401021 push 6

.text:00401023 push 5

.text:00401025 call Add5

.text:0040102A add esp, 8

.text:0040102D mov esi, eax ; 保存第3个参数(即Add5的返回值)到esi

.text:0040102F mov edx, 6

.text:00401034 mov ecx, 5

.text:00401039 push esi ; 虽然时fastcall,但是edx,ecx不够用的时候,还是使用了栈

.text:0040103A call Add6

.text:0040103F add esi, eax

.text:00401041 push esi

.text:00401042 push offset aD ; "%d"

.text:00401047 call _printf

.text:0040104C add esp, 8

.text:0040104F xor eax, eax

.text:00401051 pop esi

.text:00401052 retn

.text:00401052 _main endp

 

 

Add函数:

.text:00401000 ; =============== S U B R O U T I N E =======================================

.text:00401000

.text:00401000

.text:00401000 Add5 proc near ; CODE XREF: _main+5p

.text:00401000

.text:00401000 arg_0 = dword ptr 4

.text:00401000 arg_4 = dword ptr 8

.text:00401000

.text:00401000 mov eax, [esp+arg_4]

.text:00401004 mov ecx, [esp+arg_0]

.text:00401008 lea eax, [ecx+eax+8] ; 虽然我尽量做了很多无用的操作,但是连VC6都要把这些

.text:00401008 ; 操作优化掉

.text:0040100C retn

.text:0040100C Add5 endp

.text:0040100C

.text:0040100C ; ---------------------------------------------------------------------------

.text:0040100D align 10h

.text:00401010

.text:00401010 ; =============== S U B R O U T I N E =======================================

.text:00401010

.text:00401010

.text:00401010 Add6 proc near ; CODE XREF: _main+1Ap

.text:00401010

.text:00401010 arg_0 = dword ptr 4

.text:00401010

.text:00401010 lea eax, [ecx+edx]

.text:00401013 mov ecx, [esp+arg_0] ; fastcall在VC中只会使用ecx,edx两个寄存器来传递参数,

.text:00401013 ; 当参数超过2个时,还是得通过栈来传递

.text:00401017 add eax, ecx

.text:00401019 retn 4

.text:00401019 Add6 endp

.text:00401019

.text:00401019 ; ---------------------------------------------------------------------------

 

 

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

从最简单的Win32汇编程序,HelloWorld说起


从最简单的Win32汇编程序,HelloWorld说起

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及文件

自从开始弄反外挂以来,我的个人目标很明确,就是借此机会,好好的重新学习Win32汇编,当年买了书,开始学了一下因为C++学习的紧迫性,就放弃了。。。这和Python当年学习的过程几乎是一样的。。。。。呵呵,人生真是戏剧性,当工作后,我因为工作需要学习了lua后,重拾对脚本语言的兴趣,对C++的学习紧迫性也没有那么强了(毕竟完全可以应付工作了,真是完全,我还没有因为C++语法的问题在工作中卡过,剩下需要学习的就是思想了),所以又开始扛着《Python核心编程》啃,最近反外挂的工作竟然也在工作中用了python一把,真是戏剧性啊。。。。。现在要反汇编嘛,乘机好好学好汇编吧。。。。我发现我对于越底层的东西好像兴趣越大。。。。不知道为什么,也许是因为毕竟是学硬件出身吧。。。。。。底层的东西离硬件近点。。。。但是怎么解释我去学习LUA,Python呢?所以结果还是没有办法解释。。。。。。。。。

书中的例子很简单,源代码如下:

.486                                ; create 32 bit code
.model flat, stdcall                ; 32 bit memory model
option casemap :none                ; case sensitive

include windows.inc
include masm32.inc
include user32.inc
include kernel32.inc

includelib masm32.lib
includelib user32.lib
includelib kernel32.lib

.data
    szCaption db "A MessageBox !",0
    szText db "Hello,World !",0

.code

start:
    invoke MessageBox,NULL,offset szText,/
            offset szCaption,MB_OK
    invoke ExitProcess,NULL

end start

 

然后编个makefile:

对了,书中是建议去下载微软的nmakeVS中都有的,但是我不知道是否和GNU make完全兼容,我只学过GNU make,并且好像也不太像去学微软的nmake语法(咋一看好像差不多),所以我下了个windows 版的GNU make来用,幸好还真有这个东西:)

makefile:

1 basename = helloWorld
2 exe = helloWorld.exe
3 obj = helloWorld.obj
4 files = helloWorld.asm
5 $(exe) : $(obj)
6     link /subsystem:windows /map:$(basename).map /out:$(exe) $(obj)
7 $(obj) : $(files)
8     ml /c /coff /Zi $(files)

 

这个makefile写的有点复杂了-_-!呵呵,还好例子简单。。。。。

然后用make命令编译就好了。。。。。这里因为我用了vim。。。所以一切都简单了很多,呵呵,其实大家假如用UE,EditPlus也不会坏到哪去,反正越是接触的语言越多,你也会越希望有个万能的编辑器的。。。。当然,万能的IDE最好。

编译,运行,都没有问题,但是,有的人脑袋就是进水了,因为我没有自己push去传递参数,也因为习惯了C++程序中微软做一大堆手脚,总感觉不踏实,我想看看这个程序中微软是不是也在我背后干了什么。。。。。。(C语言程序员不喜欢C++,其中一个很大的理由就是他们觉得编译器背着他们干了太多,他们不踏实,其实去看看然后多反汇编几次C++程序,要达到基本理解C++编译器干了些什么好像也不是太难。。。。。。但是起码比C语言干的多。。。又说了一大堆没有用的话,我发现我的文中有用的信息越来越少了,都是我东扯西扯。。。)

回到主题,于是我先看了一下生成的exe文件,发现无缘无故多了.rdata区段,虽然我并没有用,所以程序达到了4k(好像是普通不修改PE文件时最小的一个可执行程序的大小),反汇编一下生成的exe文件(还能叫反汇编吗-_-!)

00401000 >/$ 6A 00 push 0 ; /Style = MB_OK|MB_APPLMODAL

00401002 |. 68 00304000 push 00403000 ; |Title = "A MessageBox !"

00401007 |. 68 0F304000 push 0040300F ; |Text = "Hello,World !"

0040100C |. 6A 00 push 0 ; |hOwner = NULL

0040100E |. E8 07000000 call <_MessageBoxA@16 0040101a f user32:user32.dll> ; /MessageBoxA

00401013 |. 6A 00 push 0 ; /ExitCode = 0

00401015 /. E8 06000000 call <_ExitProcess@4 00401020 f kernel32:kernel32.dll> ; /ExitProcess

0040101A > $- FF25 08204000 jmp dword ptr [<&user32.MessageBoxA;>] ; _MessageBoxA@16 0040101a f user32:user32.dll

00401020 > .- FF25 00204000 jmp dword ptr [<&kernel32.ExitProcess;>] ; _ExitProcess@4 00401020 f kernel32:kernel32.dll

 

我只能说,总算在我们程序背后没有什么在偷偷摸摸进行了,一切就像我们的源代码一样,这正是我们需要的境界。。。。。用汇编这点还是好(其他高级语言使用者基本可以忽视此句)

 

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

PyQT学习 的开始,顺面小谈目前GUI的选择

PyQT学习 的开始,顺面小谈目前GUI的选择

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及文件

以前学习了MFC,工作前自己也做些小应用,工作后除了在工作组呆了2个月,还有在服务器组时客串写点计算md5值,密码,关键字过滤等小工具的时候,基本上用不到MFC。但是,总的来说,MFC的学习还算是在这段时间发挥了一点作用,也不算白费。至于说MFC的设计多么完善,实在不敢恭维,哪怕是自己随便开发一个小工具,都会有别扭的地方,以前学习的时候,更加是为其开发可以动态改变大小的对话框程序绞尽脑汁。。。。。基本上,理解了MFC的原理后,开发一般的东西是没有问题,除了要看看具体控件的函数调用啥以外,但是过程主要还是以痛苦为主,没有畅快的感觉。。。。而,想要用MFC开发出漂亮的界面,那就。。。。更加痛苦,虽然也许控制力更强,可定制的方式更多,但是。。。实在不是太方便。个人最痛苦的经历是在用MFC做一个游戏的时候,那个痛苦啊,基本上需要的功能基本上是从额外的控件库中获得,学习了CButtonBTCImageX等后,才好不容易弄出个雏形。。。。何止一个难字了得。这点。。。虽然怪我准备用MFC做游戏的不当,但是也体现了MFC的确有其复杂性所在。

       个人认为,像一般的程序语言使用时,控制力强,效率高还在某些时候有一定必要,比如公司现在开发网络游戏服务器,客户端的时候用的都是C++,嵌入式开发时用用C,甚至汇编都可,但是开发界面嘛,还有必要弄的非要绞尽脑汁,翻尽资料才能弄的一个控件有点小小的改变吗(比如自绘控件),RAD嘛,那样,速度岂不是慢了点,虽然一个软件的界面很重要,但是指的不是要求开发的多么痛苦,开发的GUI库要多么能自由的控制。。。。。

       综上所述,不喜欢MFC,但是其偏偏是我目前唯一懂的GUI库,我准备改变这一点,准备有空学习QTPyQT,一起学了,相对来说,QT的资料多些,PyQT就比较少,所以我写的时候可能以PyQT为主。

这里顺面谈谈GUI库的选择

本人其实最大的要求就是跨平台,我不希望到时候需要某个Linux工具的时候还需要额外学习其他库,要学习还不一次学完,虽然我现在使用Linux还是纯控制台(putty远程)。

这里基本上有QT,WxWidget,GTK+,等3种选择

这是我在参考了WxWidget,GTK+等相关了资料后做出的选择。。。。GTK+适应面太窄,而且原生为C设计,不喜欢,WxWidgetQT之间倒是抉择了很久,WxWidget也算是比较广泛使用的东西了,记得《梦断代码》一书中描述的Chandler就是使用了WxWidget,并且WxWidgetQT也有很多共同的优点。比如都有Python的绑定版本:)。

从软件架构上来说,按性格我会更喜欢QT这样面向对象使用更加正规的工具而不是WxWidgetMFC这样太依赖宏的工具,虽然说也许速度会慢一点,我也愿意忍受了,就我的经验来说,似乎程序的瓶颈一般不大可能在这些问题上。并且,看资料了解了一下QT的信令槽机制,直观感觉会比可狰的宏操作的消息映射会好得多。

但是WxWidget有另外一个优点,其不与任何一家公司相关,QT毕竟是诺基亚的产品,毕竟受其控制,个人性格又不太喜欢受制于某一家公司的技术,(即便是微软这样的公司我都不愿意,何况诺基亚呢?)所以当年坚决的没有学Object C并买IPhone,而是打算就算是学JAVA也应该支持Android。当年没有学C#JAVA而是学了C++,并且,虽然在Windows下工作的较多,但是还是保持着对Linux的兴趣。这些对自己视野的开阔还是有一定好处的,并且对于知识的持久性也是有保证的。。。。听着骂C#多变的人我就偷笑了,呵呵,C++我盼着变都还不变呢。。。。。但是有利有弊吧,学的东西多了,自然不如专门学一个东西精罗,何况,C#多变,还不是其在发展嘛。。。。。。。这是个人在刚毕业,刚工作时候的取舍,不然一开始就太精,视野容易变得很狭窄,虽然也许这样一开始工资会涨的比较快,呵呵,这是关于GUI以外的题外话了。

但是最后我还是选择了QT,首先,QT虽然其属于诺基亚,但是开源,这点保证了不至于太受制于一家公司,另外,还因为QT有额外的优点:

1.他有原生的图形界面平台,那就是KDE,这点目前我能选择的范围内,就只有MFCGTK+,QT了,WxWidget没有这样的优势。虽然其实我以前用Linux的时候都是在Gnome下。。。(RedhatUbuntuLinux默认都是Gnome,并且因为我一开始用Redhat9Gnome,也习惯了,后来也没有准备改,看来以后可能需要改到KDE了。。。呵呵,不然怎么领悟QT的优势啊。。。。。)

2.QT能跑在很多移动设备上,除了WM,马上也就会有塞班的版本。

3.QT还能更方便的用于嵌入式开发,甚至QT还能开发命令行的图形界面。

因为这些优点。。。。我还是选择了QT,希望这些额外的优点不要是因为QT有一家大公司在宣传的缘故吧-_-!

 

最后的最后,其实一些东西没有提到,主要原因就是其不跨平台了,那么跨平台真的有那么重要吗?这点我说不清楚,个人爱好使然。只是,在同样的开发成本下,假如你的软件有跨平台特性,这有什么不好吗?那么JAVA的宣传口号算啥呢?“一次编写,到处运行”。。。。。呵呵,QT的口号是,“一次编写,到处编译”。。。

这里有个网页,做了一些比较,大家可以参考一下:

GUI programming with Python

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 


 

 

 

 

阅读全文....

OllyDbg,IDA pro强强联合!从OllyDbg中载入IDA Pro输出的map信息文件,带符号信息调试!


OllyDbg,IDA pro强强联合!从OllyDbg中载入IDA Pro输出的map信息文件,带符号信息调试!

write by 九天雁翎(JTianLing) -- www.jtianling.com

再强大的工具有的时候也不能独立解决问题,毕竟各有所长,就算是最最强大的IDA Pro, OllyDbg, SoftIce都不例外,对于静态分析自然是IDA Pro最强大,而静态分析不了的时候就需要SI,OD出马了,以前我找了很久才研究出一种从SoftIce中载入IDA Pro输出的map信息文件的方法,

《SoftIce,IDA pro强强联合!从SOFTICE中打开IDA Pro输出的map信息文件》

http://www.jtianling.com/archive/2009/01/07/3730240.aspx

 

这一次,我又在网上发现了从OllyDbg载入IDA Pro输出的map的信息的方法了:)

这样实现了OllyDbg带符号信息的调试,更加方便了。。。。呵呵

其实主要的问题在于OllyDbg的一个LoadMap的插件,因为看雪没有下载,我一直不知道,特意从国外download下来了:)

放到老地方,有需要的去下载吧。

http://groups.google.com/group/jiutianfile/files

方法就不多说了,用IDA Pro的Product功能,生成map,再用此插件载入就好了,连这都不知道的话估计也不会用这些软件了。

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

C++中通过指针,引用方式做返回值的汇编代码分析


C++中通过指针,引用方式做返回值的汇编代码分析

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

源代码因为是《加密与解密》(第3版)一书中的代码,我就不贴了,不然好像是侵犯版权吧。见书中79面。

基本原理可以讲讲,其实就是一个max(int*,int*)的函数,将大的值放入第一个参数返回,原书可能是在debug下编译的版本,我是在release下编译的,反汇编结果如下:

.text:00401040 ; void __cdecl max(int *, int *)

.text:00401040 void __cdecl max(int *, int *) proc near ; CODE XREF: _main+1Dp

.text:00401040

.text:00401040 arg_0 = dword ptr 4

.text:00401040 arg_4 = dword ptr 8

.text:00401040

.text:00401040 000 mov eax, [esp+arg_4]

.text:00401044 000 mov ecx, [esp+arg_0]

.text:00401048 000 mov eax, [eax] ; 相当于C语言中的dereference操作

.text:0040104A 000 mov edx, [ecx]

.text:0040104C 000 cmp edx, eax ; Compare Two Operands

.text:0040104E 000 jge short locret_401052 ; Jump if Greater or Equal (SF=OF)

.text:00401050 000 mov [ecx], eax ; 假如dex>=eax(a>=b)直接跳到locret_401052返回,即不变

.text:00401050 ; 假如dex

.text:00401050 ; 此处相当于*ecx = eax,:)注释扭曲了

.text:00401052

.text:00401052 locret_401052: ; CODE XREF: max(int *,int *)+Ej

.text:00401052 000 retn ; Return Near from Procedure

.text:00401052 void __cdecl max(int *, int *) endp

 

 

这里唯一需要注意的就是

mov eax, [esp+arg_4]

mov ecx, [esp+arg_0]

mov eax, [eax]

mov edx, [ecx]

这4句了,先将一个地址传入,eax/ecx,然后通过[eax]/[ecx]取值,就相当于dereference的操作,即相当于*操作符的作用。

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

C++中的虚函数调用原理的反汇编实例分析(2)


C++中的虚函数调用原理的反汇编实例分析(2)

write by 九天雁翎(JTianLing) -- www.jtianling.com

因为昨天的第一节中我其实感觉并没有太透彻的理解其原理,也对VC6的实现是否会继续抱有怀疑态度,所以今天特意用VS2005编译并分析了一下,只能说,从反汇编的角度来看都可以看出微软的进步实在是很大的,有钱嘛:)呵呵,也许Stanley B.Lippman的功劳不是白费的吧。速度上我是没有好好的去测试了,从逻辑上看,可读性都强了很多(呵呵,汇编代码要可读性干什么。。。。。)

为了可读性。。。。我个人就麻烦一点了,以后汇编代码也不是全黑出镜了。。。。我还是用gvim给大家上上色吧。。。。

 

示例程序:

#include

#include

#include

 

class CTestThisPointer

{

public:

    CTestThisPointer(int ai):mi(ai) { }

    virtual int Add(int ai)

    {

        mi += ai;

        return mi;

    }

 

private:

    int mi;

};

 

 

int main()

{

    CTestThisPointer loTest(10);

    CTestThisPointer *lp = &loTest;

 

    printf("%d/n",lp->Add(5));

    printf("%s/n",typeid(lp).name());

    return 0;

}

和在第一节中的源代码是一样的,只是这次我用VS2005最大速度优化release编译

 

反汇编:

主函数:

 1 .text:00401010 ; int __cdecl main(int argc, const char **argv, const char *envp)
 2 .text:00401010 _main           proc near               ; CODE XREF: __tmainCRTStartup+10A^Yp
 3 .text:00401010
 4 .text:00401010 var_8           = dword ptr -8
 5 .text:00401010 var_4           = dword ptr -4
 6 .text:00401010 argc            = dword ptr  4
 7 .text:00401010 argv            = dword ptr  8
 8 .text:00401010 envp            = dword ptr  0Ch
 9 .text:00401010
10 .text:00401010                 sub     esp, 8          ;
此处为临时变量var_8,var_4预留空间,但是因为直接使用esp
11 .text:00401010                                         ;
所以我感觉后面的的堆栈有点混乱,比如后面的esp+10h,
12 .text:00401010                                         ;
这里有个有意思的优化在于5竟然是只有2个字节的使用,
13 .text:00401010                                         ;
所以esp-8以后,push esi(保存esi)然后又-4=0ch,然后
14 .text:00401010                                         ;
因为push 5(add参数)然后-2=010h,所以以后的临时变量
15 .text:00401010                                         ;
不得不先+10h以获取正确的地址,看到下面的汇编代码
16 .text:00401010                                         ;
应该就好理解了
17 .text:00401010                                         ;
18 .text:00401013                 push    esi
19 .text:00401014                 push    5               ;
这是Add函数的参数了,这里是先push参数,然后再正确为
20 .text:00401014                                         ; CTestThisPointer
赋值(从构造函数优化而来),再调用
21 .text:00401014                                         ; Add
函数,中间断开了,但是从栈的走向还是可以看出
22 .text:00401014                                         ;
此处实际是Add函数的参数
23 .text:00401016                 lea     ecx, [esp+10h+var_8] ;
此处也是Add函数的参数,即this指针了
24 .text:0040101A                 mov     [esp+10h+var_8], offset const CTestThisPointer::`vftable'
25 .text:00401022                 mov     [esp+10h+var_4], 0Ah ;
构造函数没有调用,直接优化为赋值操作
26 .text:0040102A                 call    ds:const CTestThisPointer::`vftable' ;
27 .text:0040102A                                         ;
一个虚函数的调用还是解释call this所在的地址就好了
28 .text:00401030                 mov     esi, ds:__imp__printf
29 .text:00401036                 push    eax
30 .text:00401037                 push    offset aD       ; "%d/n"
31 .text:0040103C                 call    esi ; __imp__printf
32 .text:0040103E                 add     esp, 8          ;
add esp,8为调整printf函数的栈平衡使用
33 .text:00401041                 push    offset __type_info_root_node ;
此处不明,可能需要多个RTTI对象才能知道
34 .text:00401041                                         ;
因为就命名上来推测,可能是维护了一个RTTI对象的链表
35 .text:00401041                                         ;
而因为元素只有一个,所以没有办法肯定了
36 .text:00401046                 mov     ecx, offset CTestThisPointer * `RTTI Type Descriptor' ;
此处相当于构建一个type_info的类,当时由于优化,没有
37 .text:00401046                                         ;
使用栈来创建局部变量和使用构造函数等,直接将type_info
38 .text:00401046                                         ;
的虚表赋值给ecx了,ecxthiscall调用约定中就是this
39 .text:00401046                                         ;
指针传递的参数啊,下面就调用了此对象的name成员函数
40 .text:0040104B                 call    ds:type_info::name(__type_info_node *)
41 .text:00401051                 push    eax
42 .text:00401052                 push    offset aS       ; "%s/n"
43 .text:00401057                 call    esi ; __imp__printf
44 .text:00401059                 add     esp, 8          ;
add esp,8也为调整printf函数的栈平衡使用
45 .text:0040105C                 xor     eax, eax
46 .text:0040105E                 pop     esi
47 .text:0040105F                 add     esp, 8          ;
此处才退出函数,CTestThisPointer结束生命周期,用
48 .text:0040105F                                         ; add esp,8
清空临时变量
49 .text:00401062                 retn                    ;
对了,才注意到main函数遵循的也是__cdecl调用约定。。。
50 .text:00401062 _main           endp                    ;
其实自然啦,因为main函数的参数个数也是不定的

 

虚表:

1 .rdata:00402114                 dd offset const CTestThisPointer::`RTTI Complete Object Locator' ;
2 .rdata:00402114                                         ;
这就是CTestThisPointerRTTI信息
3 .rdata:00402114                                         ;
正好在虚表前,由编译器静态分配,但是动态获取
4 .rdata:00402114                                         ; this
指针的指向还是vtbl的第一个虚函数,此例中
5 .rdata:00402114                                         ;
即为Add
6 .rdata:00402118 const CTestThisPointer::`vftable' dd offset CTestThisPointer__Add
7 .rdata:00402118                                         ; DATA XREF: _main+A^Xo
8 .rdata:00402118                                         ; _main+1A^Xr

 

而虚表的前4个字节就是一个指针,指向了表示正确类型的type_info类的子类。

到这里,一切就慢慢符合《inside C++ Object》中描述的虚表了,呵呵,有了lippman,微软总算走上正轨了,慢慢的。。。充满技术性天才的可怜borland也走入了末途。

 

继续,例2:

#include

#include

#include

 

class CTestThisPointer

{

public:

    CTestThisPointer(int ai):mi(ai) { }

    virtual int Add(int ai)

    {

        mi += ai;

        return mi;

    }

 

    // 纯废的析构函数

    virtual ~CTestThisPointer() { mi = 0;}

private:

    int mi;

};

 

// 无继承关系,仅为分析RTTI

class CTestBase

{

public:

    CTestBase(int ai):mi(ai) { }

    virtual int Add(int ai)

    {

        mi += ai;

        mi += ai;

        return mi;

    }

 

    // 纯废的析构函数

    ~CTestBase() { mi = 0;}

private:

    int mi;

};

 

    

int main()

{

    CTestThisPointer loTest(10);

    CTestThisPointer *lp = &loTest;

 

    printf("%d/n",lp->Add(5));

    printf("%s/n",typeid(lp).name());

 

 

 

    CTestBase loTestBase(20);

    CTestBase* lpTestBase = &loTestBase;

 

    printf("%s/n",typeid(CTestBase).name());

    printf("%s/n",typeid(loTestBase).name());

    printf("%s/n",typeid(lpTestBase).name());

    return 0;

}

 

反汇编代码:

不重复注释重复内容

主程序:

.text:00401070 ; int __cdecl main(int argc, const char **argv, const char *envp)
.text:00401070 _main           proc near               ; CODE XREF: __tmainCRTStartup+10A^Yp
.text:00401070
.text:00401070 var_1C          = dword ptr -1Ch
.text:00401070 var_18          = dword ptr -18h
.text:00401070 var_14          = dword ptr -14h
.text:00401070 var_10          = dword ptr -10h
.text:00401070 var_C           = dword ptr -0Ch
.text:00401070 var_4           = dword ptr -4
.text:00401070 argc            = dword ptr  4
.text:00401070 argv            = dword ptr  8
.text:00401070 envp            = dword ptr  0Ch
.text:00401070
.text:00401070                 push    0FFFFFFFFh
.text:00401072                 push    offset loc_401A50 ;
因为程序足够大了。。。。MS自动的加入了SEH异常处理
.text:00401077                 mov     eax, large fs:0 ; SEH
TEB(thread Environment Block)总是在FS:0
.text:0040107D                 push    eax
.text:0040107E                 sub     esp, 10h
.text:00401081                 push    esi
.text:00401082                 push    edi
.text:00401083                 mov     eax, __security_cookie
.text:00401088                 xor     eax, esp
.text:0040108A                 push    eax
.text:0040108B                 lea     eax, [esp+28h+var_C]
.text:0040108F                 mov     large fs:0, eax ;
之前的代码都是在初始化TEB结构。。。。。。。
.text:00401095                 mov     [esp+28h+var_1C], offset const CTestThisPointer::`vftable'
.text:0040109D                 mov     [esp+28h+var_18], 0Ah
.text:004010A5                 push    5
.text:004010A7                 lea     ecx, [esp+2Ch+var_1C]
.text:004010AB                 mov     [esp+2Ch+var_4], 0
.text:004010B3                 call    ds:const CTestThisPointer::`vftable'
.text:004010B9                 mov     esi, ds:__imp__printf
.text:004010BF                 push    eax
.text:004010C0                 push    offset aD       ; "%d/n"
.text:004010C5                 call    esi ; __imp__printf
.text:004010C7                 mov     edi, ds:type_info::name(__type_info_node *)
.text:004010CD                 add     esp, 8
.text:004010D0                 push    offset __type_info_root_node
.text:004010D5                 mov     ecx, offset CTestThisPointer * `RTTI Type Descriptor'
.text:004010DA                 call    edi ; type_info::name(__type_info_node *)
.text:004010DC                 push    eax
.text:004010DD                 push    offset aS       ; "%s/n"
.text:004010E2                 call    esi ; __imp__printf
.text:004010E4                 add     esp, 8
.text:004010E7                 mov     [esp+28h+var_14], offset const CTestBase::`vftable'
.text:004010EF                 mov     [esp+28h+var_10], 14h
.text:004010F7                 push    offset __type_info_root_node
.text:004010FC                 mov     ecx, offset CTestBase `RTTI Type Descriptor'
.text:00401101                 mov     byte ptr [esp+2Ch+var_4], 1
.text:00401106                 call    edi ; type_info::name(__type_info_node *)
.text:00401108                 push    eax
.text:00401109                 push    offset aS       ; "%s/n"
.text:0040110E                 call    esi ; __imp__printf
.text:00401110                 add     esp, 8
.text:00401113                 push    offset __type_info_root_node
.text:00401118                 mov     ecx, offset CTestBase `RTTI Type Descriptor'
.text:0040111D                 call    edi ; type_info::name(__type_info_node *)
.text:0040111F                 push    eax
.text:00401120                 push    offset aS       ; "%s/n"
.text:00401125                 call    esi ; __imp__printf
.text:00401127                 add     esp, 8
.text:0040112A                 push    offset __type_info_root_node
.text:0040112F                 mov     ecx, offset CTestBase * `RTTI Type Descriptor'
.text:00401134                 call    edi ; type_info::name(__type_info_node *)
.text:00401136                 push    eax
.text:00401137                 push    offset aS       ; "%s/n"
.text:0040113C                 call    esi ; __imp__printf
.text:0040113E                 add     esp, 8
.text:00401141                 xor     eax, eax
.text:00401143                 mov     ecx, [esp+28h+var_C]
.text:00401147                 mov     large fs:0, ecx
.text:0040114E                 pop     ecx
.text:0040114F                 pop     edi
.text:00401150                 pop     esi
.text:00401151                 add     esp, 1Ch
.text:00401154                 retn
.text:00401154 _main           endp
.text:00401154
.text:00401154 ; ---------------------------------------------------------------------------

贴出来仅仅是为了完整性,其实已经没有什么新意了,无非就是多一些,唯一有价值提起的就是SEH机制的加入,这又是另外一个话题了,在此不详述了,可以查阅相关书籍,推荐的有《windows核心编程》和《加密与解密》相关章节,虽然内容都并不是很多。

虚表。。。这才是符合主题的部分:

.rdata:00402124                 dd offset const CTestThisPointer::`RTTI Complete Object Locator'
.rdata:00402128 const CTestThisPointer::`vftable' dd offset CTestThisPointer__Add
.rdata:00402128                                         ; DATA XREF: CTestThisPointer___CTestThisPointer^Xo
.rdata:00402128                                         ; CTestThisPointer___scalar_deleting_destructor_+8^Xo ...
.rdata:0040212C                 dd offset CTestThisPointer___scalar_deleting_destructor_ ;
.rdata:0040212C                                         ;
哈雷卤鸭。。。。。好吃吗?-_-!果然虚表果然扩张了,
.rdata:0040212C                                         ;
顺序排列的函数分别是Add,destructor
.rdata:00402130                 dd offset const CTestBase::`RTTI Complete Object Locator'
.rdata:00402134 const CTestBase::`vftable' dd offset CTestBase__Add
.rdata:00402134                                         ; DATA XREF: CTestBase___CTestBase^Xo
.rdata:00402134                                         ; _main+77^Xo
.rdata:00402134                                         ;
.rdata:00402134                                         ;
此处也可以看出来,在虚表前的一个4字节结构,的确是
.rdata:00402134                                         ; RTTI
使用的。。。。只是this指针直接指向的是虚表

 

 

以下是__type_info_node的链表。。。。。。。。。,没有上色了。。。

.rdata:00402274 dd offset CTestBase::`RTTI Class Hierarchy Descriptor'

.rdata:00402278 const CTestThisPointer::`RTTI Complete Object Locator' db 0

.rdata:00402278 ; DATA XREF: .rdata:00402124o

.rdata:00402279 db 0

.rdata:0040227A db 0

.rdata:0040227B db 0

.rdata:0040227C db 0

.rdata:0040227D db 0

.rdata:0040227E db 0

.rdata:0040227F db 0

.rdata:00402280 db 0

.rdata:00402281 db 0

.rdata:00402282 db 0

.rdata:00402283 db 0

.rdata:00402284 dd offset CTestThisPointer `RTTI Type Descriptor'

.rdata:00402288 dd offset CTestThisPointer::`RTTI Class Hierarchy Descriptor'

.rdata:0040228C CTestThisPointer::`RTTI Class Hierarchy Descriptor' db 0

.rdata:0040228C ; DATA XREF: .rdata:00402288o

.rdata:0040228C ; .rdata:004022BCo

.rdata:0040228D db 0

.rdata:0040228E db 0

.rdata:0040228F db 0

.rdata:00402290 db 0

.rdata:00402291 db 0

.rdata:00402292 db 0

.rdata:00402293 db 0

.rdata:00402294 db 1

.rdata:00402295 db 0

.rdata:00402296 db 0

.rdata:00402297 db 0

.rdata:00402298 dd offset CTestThisPointer::`RTTI Base Class Array'

.rdata:0040229C CTestThisPointer::`RTTI Base Class Array' dd offset CTestThisPointer::`RTTI Base Class Descriptor at (0,-1,0,64)'

.rdata:0040229C ; DATA XREF: .rdata:00402298o

 

 

__type_info_node的链表。。。。可以在VS2005的头文件中找到依据:

struct __type_info_node {

void *memPtr;

__type_info_node* next;

};

 

extern __type_info_node __type_info_root_node;

呵呵,不就是这个吗?

 

最后,在VS2005的头文件中可以看到type_info类的声明和反汇编代码上看到的完全一致。。。。

 

 

class type_info {

public:

virtual ~type_info();

_CRTIMP_PURE bool __CLR_OR_THIS_CALL operator==(const type_info& rhs) const;

_CRTIMP_PURE bool __CLR_OR_THIS_CALL operator!=(const type_info& rhs) const;

_CRTIMP_PURE int __CLR_OR_THIS_CALL before(const type_info& rhs) const;

_CRTIMP_PURE const char* __CLR_OR_THIS_CALL name(__type_info_node* __ptype_info_node = &__type_info_root_node) const;

_CRTIMP_PURE const char* __CLR_OR_THIS_CALL raw_name() const;

private:

void *_m_data;

char _m_d_name[1];

__CLR_OR_THIS_CALL type_info(const type_info& rhs);

type_info& __CLR_OR_THIS_CALL operator=(const type_info& rhs);

_CRTIMP_PURE static const char *__CLRCALL_OR_CDECL _Name_base(const type_info *,__type_info_node* __ptype_info_node);

_CRTIMP_PURE static void __CLRCALL_OR_CDECL _Type_info_dtor(type_info *);

};

 

至此。。。。C++中虚函数调用的机制差不多可以知道了。。。。顺面还搞定了RTTI....加上继承不过就是换个虚表的问题了。虚表的结构又不会变。。。。。不深究了,生命是有限的。。。。。

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

C++中的虚函数调用原理的反汇编实例分析(1)


C++中的虚函数调用原理的反汇编实例分析(1)

write by 九天雁翎(JTianLing) -- www.jtianling.com

具体的原理我并不想多讲,最好的办法是看《inside C++ Object》一书,我只是通过实际的反汇编代码来检验一下。。。。

其实仅仅是最近老在看反汇编的东西,这应该也属于逆向分析初步的知识吧,起码看到汇编代码能知道你看到的到底是什么

 

测试1

 1 #include <stdio.h>
 2 #include <string.h>
 3
 4 class CTestThisPointer
 5 {
 6 public:
 7     CTestThisPointer(int ai):mi(ai) { }
 8     virtual int Add(int ai)
 9     {
10         mi += ai;
11         return mi;
12     }
13     
14 private:
15     int mi;
16 };
17
18
19 int main()
20 {
21     CTestThisPointer loTest(10);
22
23     printf("%d",loTest.Add(5));
24     return 0;
25 }
26

VC6默认优化release编译

反汇编代码如下:

main函数

.text:00401000 ; Attributes: bp-based frame

.text:00401000

.text:00401000 ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401000 _main           proc near               ; CODE XREF: _mainCRTStartup+AFp

.text:00401000

.text:00401000 var_8           = byte ptr -8

.text:00401000 argc            = dword ptr  8

.text:00401000 argv            = dword ptr  0Ch

.text:00401000 envp            = dword ptr  10h

.text:00401000

.text:00401000                 push    ebp

.text:00401001                 mov     ebp, esp

.text:00401003                 sub     esp, 8

.text:00401006                 push    0Ah

.text:00401008                 lea     ecx, [ebp+var_8]

.text:0040100B                 call    CTestThisPointer__CTestThisPointer

.text:00401010                 push    5

.text:00401012                 lea     ecx, [ebp+var_8]

.text:00401015                 call    CTestThisPointer__Add ; 呵呵,此处因为是通过对象访问的,所以其实根本没有用到

.text:00401015                                         ; 虚表,我疏忽了........

.text:0040101A                 push    eax

.text:0040101B                 push    offset aD       ; "%d"

.text:00401020                 call    _printf

.text:00401025                 add     esp, 8

.text:00401028                 xor     eax, eax

.text:0040102A                 mov     esp, ebp

.text:0040102C                 pop     ebp

.text:0040102D                 retn

.text:0040102D _main           endp

 

 

构造函数:

.text:00401030 CTestThisPointer__CTestThisPointer proc near ; CODE XREF: _main+Bp

.text:00401030

.text:00401030 this            = dword ptr -4

.text:00401030 arg_0           = dword ptr  8

.text:00401030

.text:00401030                 push    ebp

.text:00401031                 mov     ebp, esp

.text:00401033                 push    ecx

.text:00401034                 mov     [ebp+this], ecx ; 以下可以看到,此临时变量主要用于存储this指针,所以

.text:00401034                                         ; 我直接将其改名了

.text:00401037                 mov     eax, [ebp+this]

.text:0040103A                 mov     ecx, [ebp+arg_0]

.text:0040103D                 mov     [eax+4], ecx    ; 将构造函数的参数保存在this+4的位置上

.text:00401040                 mov     edx, [ebp+this]

.text:00401043                 mov     dword ptr [edx], offset const CTestThisPointer::`vftable' ;

.text:00401043                                         ; 此处可以看出在VC中虚表其实是放在一个类的最开始位置的,

.text:00401043                                         ; 这点的解释可以参考《inside C++ Ojbect》一书

.text:00401049                 mov     eax, [ebp+this] ; 此句用途不明,返回this?外部也没有使用此eax寄存器

.text:0040104C                 mov     esp, ebp

.text:0040104E                 pop     ebp

.text:0040104F                 retn    4               ; 可以看到在这里C++的函数默认是__stdcall调用约定的

.text:0040104F CTestThisPointer__CTestThisPointer endp

 

CTestThisPointer虚表所在位置只读代码段片段

.rdata:004070DC const CTestThisPointer::`vftable' db 60h,10h,40h,0

.rdata:004070DC                                         ; DATA XREF: CTestThisPointer__CTestThisPointer+13o

.rdata:004070DC                                         ; 因为只有唯一的函数Add,此处是Add函数的地址,经检验

.rdata:004070DC                                         ; 401060的确是Add函数的地址

.rdata:004070DC                                         ; 有个疑问留待进行更多测试,那就是此虚表中没有运行时

.rdata:004070DC                                         ; 类型识别需要的标志(RTTI),有两种可能,一是VC6没有

.rdata:004070DC                                         ; 实现此功能,二是因为此处不需要,所以优化掉了

 

Add函数:

.text:00401060 ; 可以看到此地址的确与虚表中的地址一致

.text:00401060 ; Attributes: bp-based frame

.text:00401060

.text:00401060 CTestThisPointer__Add proc near         ; CODE XREF: _main+15p

.text:00401060

.text:00401060 var_4           = dword ptr -4

.text:00401060 arg_0           = dword ptr  8

.text:00401060

.text:00401060                 push    ebp

.text:00401061                 mov     ebp, esp

.text:00401063                 push    ecx

.text:00401064                 mov     [ebp+var_4], ecx

.text:00401067                 mov     eax, [ebp+var_4]

.text:0040106A                 mov     ecx, [eax+4]

.text:0040106D                 add     ecx, [ebp+arg_0]

.text:00401070                 mov     edx, [ebp+var_4]

.text:00401073                 mov     [edx+4], ecx

.text:00401076                 mov     eax, [ebp+var_4]

.text:00401079                 mov     eax, [eax+4]

.text:0040107C                 mov     esp, ebp

.text:0040107E                 pop     ebp

.text:0040107F                 retn    4

.text:0040107F CTestThisPointer__Add endp

 

测试2

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <typeinfo.h>
 4
 5 class CTestThisPointer
 6 {
 7 public:
 8     CTestThisPointer(int ai):mi(ai) { }
 9     virtual int Add(int ai)
10     {
11         mi += ai;
12         return mi;
13     }
14     
15 private:
16     int mi;
17 };
18
19
20 int main()
21 {
22     CTestThisPointer loTest(10);
23     CTestThisPointer *lp = &loTest;
24
25     printf("%d/n",lp->Add(5));
26     // Test If VC6 implement RTTI
27     printf("%s/n",typeid(lp).name());
28     return 0;
29 }
30

 

反汇编:

主函数:

.text:00401000     ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401000     _main   proc near                       ; CODE XREF: _mainCRTStartup+AFp

.text:00401000

.text:00401000     thisTemp2= dword ptr -0Ch

.text:00401000     thisTemp= byte ptr -8

.text:00401000     argc    = dword ptr  8

.text:00401000     argv    = dword ptr  0Ch

.text:00401000     envp    = dword ptr  10h

.text:00401000

.text:00401000 000         push    ebp

.text:00401001 004         mov     ebp, esp

.text:00401003 004         sub     esp, 0Ch                ; Integer Subtraction

.text:00401006 010         push    0Ah

.text:00401008 014         lea     ecx, [ebp+thisTemp]     ; Load Effective Address

.text:0040100B 014         call    CTestThisPointer__CTestThisPointer ; Call Procedure

.text:00401010 010         lea     eax, [ebp+thisTemp]     ; Load Effective Address

.text:00401013 010         mov     [ebp+thisTemp2], eax

.text:00401016 010         push    5

.text:00401018 014         mov     ecx, [ebp+thisTemp2]

.text:0040101B 014         mov     edx, [ecx]

.text:0040101D 014         mov     ecx, [ebp+thisTemp2]

.text:00401020 014         call    dword ptr [edx]         ; 直接调用了this指针所在位置的函数,即vtbl中唯一的函数

.text:00401020                                             ; Add,可能这也是将虚表放在整个C++对象第一个位置的原因

.text:00401020                                             ; 吧,因为这样虚函数的调用寻址最短

.text:00401022 010         push    eax

.text:00401023 014         push    offset aD               ; "%d/n"

.text:00401028 018         call    _printf                 ; Call Procedure

.text:0040102D 018         add     esp, 8                  ; Add

.text:00401030 010         mov     ecx, offset CTestThisPointer * `RTTI Type Descriptor' ; 数据段上编译器已经存在的type_info对象。。。。。

.text:00401035 010         call    type_info::name(void)   ; 此函数实现不深究了,不过咋一看就觉得效率奇低,竟然

.text:00401035                                             ; 还需要分配释放内存,malloc,free,strcpy.........晕掉了

.text:00401035                                             ; 主要实现功能的函数是系统_unDName

.text:0040103A 010         push    eax

.text:0040103B 014         push    offset aS_0             ; "%s/n"

.text:00401040 018         call    _printf                 ; Call Procedure

.text:00401045 018         add     esp, 8                  ; Add

.text:00401048 010         xor     eax, eax                ; Logical Exclusive OR

.text:0040104A 010         mov     esp, ebp

.text:0040104C 004         pop     ebp

.text:0040104D 000         retn                            ; Return Near from Procedure

.text:0040104D     _main   endp

 

其他内容没有变!这代表在VC6RTTI的实现不是通过在虚表中加内容的方式实现的(《inside C++ Object》只提到这种实现方式),并且实际中分析代码,感觉是开始就为要识别类型的类加了一个特定的type_info类,然后主要是由__unDName这个系统函数实现了类型的鉴别。

__unDName函数嘛,调用了

.text:004015A4 080         call    Replicator::Replicator(void) ; Call Procedure

.text:004015A9 080         lea     ecx, [ebp+var_3C]       ; Load Effective Address

.text:004015AC 080         call    Replicator::Replicator(void) ; Call Procedure

.text:004015B1 080         mov     eax, [ebp+arg_4]

.text:004015B4 080         lea     ecx, [ebp+var_78]       ; Load Effective Address

.text:004015B7 080         mov     char const * const UnDecorator::name, eax

.text:004015BC 080         mov     char const * const UnDecorator::gName, eax

.text:004015C1 080         mov     eax, [ebp+arg_8]

.text:004015C4 080         mov     char * (*UnDecorator::m_pGetParameter)(long), esi

.text:004015CA 080         mov     int UnDecorator::maxStringLength, eax

.text:004015CF 080         mov     eax, [ebp+arg_0]

.text:004015D2 080         mov     char * UnDecorator::outputString, eax

.text:004015D7 080         lea     eax, [ebp+var_3C]       ; Load Effective Address

.text:004015DA 080         mov     Replicator * UnDecorator::pZNameList, eax

.text:004015DF 080         lea     eax, [ebp+var_78]       ; Load Effective Address

.text:004015E2 080         mov     Replicator * UnDecorator::pArgList, eax

.text:004015E7 080         movzx   eax, [ebp+arg_14]       ; Move with Zero-Extend

.text:004015EB 080         mov     ulong UnDecorator::disableFlags, eax

.text:004015F0 080         call    UnDecorator::operator char *(void) ; Call Procedure

.text:004015F5 080         mov     ecx, offset dword_40F920

.text:004015FA 080         mov     esi, eax

.text:004015FC 080         call    HeapManager::Destructor(void) ; Call Procedure

.text:00401601 080         mov     eax, esi

 

这么多类和函数。。。。。。。。。这些已经超过windows API的范围了,估计是属于VC6编译器内部实现的类了,呵呵,因为Windows内部实现不是主要用C吗?上面用了那么多类,应该不是Windows XP的代码吧。

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

C++中的成员函数调用原理及this指针的传递方式


C++中的成员函数调用原理及this指针的传递方式

write by 九天雁翎(JTianLing) -- www.jtianling.com

测试 源代码:

 1 #include
 2 #include
 3
 4 class CTestThisPointer
 5 {
 6 public:
 7     CTestThisPointer(int ai):mi(ai) { }
 8     int Add(int ai)
 9     {
10         mi += ai;
11         return mi;
12     }
13     
14 private:
15     int mi;
16 };
17
18
19 int main()
20 {
21     CTestThisPointer loTest(10);
22
23     printf("%d",loTest.Add(5));
24     return 0;
25 }
26

 

反汇编:

.text:00401000 ; int __cdecl main(int argc, const char **argv, const char *envp)

.text:00401000 _main proc near ; CODE XREF: _mainCRTStartup+AFp

.text:00401000

.text:00401000 this = byte ptr -4

.text:00401000 argc = dword ptr 8

.text:00401000 argv = dword ptr 0Ch

.text:00401000 envp = dword ptr 10h

.text:00401000

.text:00401000 push ebp ; 在默认优化的时候,总算看到了正统的一个push ebp;

.text:00401000 ; mov ebp,esp的保护堆栈并用ebp的过程

.text:00401001 mov ebp, esp

.text:00401003 push ecx

.text:00401004 push 0Ah ; 构造函数的除了默认this外的唯一参数,10

.text:00401006 lea ecx, [ebp+this] ; 这个参数时this指针,通过寄存器ecx传递

.text:00401009 call CTestThisPointer__CTestThisPointer

.text:0040100E push 5 ; Add函数除默认的this外唯一的参数,5

.text:00401010 lea ecx, [ebp+this] ; this指针

.text:00401013 call CTestThisPointer__Add

.text:00401018 push eax ; 将add的返回值入栈,调用printf

.text:00401019 push offset aD ; "%d"

.text:0040101E call _printf

.text:00401023 add esp, 8 ; 变长参数的函数,只能是通过__cdecl调用约定罗,由main

.text:00401023 ; 函数来维护栈平衡

.text:00401026 xor eax, eax

.text:00401028 mov esp, ebp

.text:0040102A pop ebp

.text:0040102B retn

.text:0040102B _main endp

 

 

构造函数:

.text:00401030 CTestThisPointer__CTestThisPointer proc near ; CODE XREF: _main+9p

.text:00401030

.text:00401030 var_4 = dword ptr -4

.text:00401030 arg_0 = dword ptr 8

.text:00401030

.text:00401030 push ebp

.text:00401031 mov ebp, esp

.text:00401033 push ecx ; 将this指针入栈保存

.text:00401034 mov [ebp+var_4], ecx

.text:00401037 mov eax, [ebp+var_4] ; 将this的值传给eax,默认优化的代码实在够繁琐,接下来

.text:00401037 ; 几步都是的,其实本质无非就是一个

.text:00401037 ; mov [ecx],[ebp+arg_0]的过程,但是因为不能直接的从

.text:00401037 ; 内存mov到内存,所以中间用了临时变量,但是因为要用

.text:00401037 ; 寄存器做临时变量,所以得先保存寄存器。。。。。

.text:00401037 ; 其实还有那么多寄存器,咋不用呢?呵呵,因为是默认优化

.text:0040103A mov ecx, [ebp+arg_0]

.text:0040103D mov [eax], ecx

.text:0040103F mov eax, [ebp+var_4]

.text:00401042 mov esp, ebp

.text:00401044 pop ebp

.text:00401045 retn 4

.text:00401045 CTestThisPointer__CTestThisPointer endp

 

 

Add函数:

.text:00401050 CTestThisPointer__Add proc near ; CODE XREF: _main+13p

.text:00401050

.text:00401050 var_4 = dword ptr -4

.text:00401050 arg_0 = dword ptr 8

.text:00401050

.text:00401050 push ebp

.text:00401051 mov ebp, esp

.text:00401053 push ecx

.text:00401054 mov [ebp+var_4], ecx ; 这个临时变量用的最费

.text:00401057 mov eax, [ebp+var_4]

.text:0040105A mov ecx, [eax]

.text:0040105C add ecx, [ebp+arg_0] ; 因为返回的是mi,所以以下是老老实实的取出this指针中的

.text:0040105C ; 地址到寄存器,然后在通过mov re,[re]的形式取出值

.text:0040105C ; BTW:看没有优化的代码实在不习惯

.text:0040105F mov edx, [ebp+var_4]

.text:00401062 mov [edx], ecx

.text:00401064 mov eax, [ebp+var_4]

.text:00401067 mov eax, [eax]

.text:00401069 mov esp, ebp

.text:0040106B pop ebp

.text:0040106C retn 4

.text:0040106C CTestThisPointer__Add endp

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

C/C++与汇编的函数相互调用分析


C/C++与汇编的函数相互调用分析

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及相关文件下载

昨天好好研究了一下内嵌汇编的情况。。。。。更进一步的,该是看看独立编译的汇编程序与C/C++互相调用的情况了。

呵呵,最近怎么好像老在搞这个,想当年学习的时候,一门心思的学C++,到现在老是在弄诸如怎么在C/C++中调用LUA函数,或者反过来,怎么C/C++中调用Python函数,或者反过来,今天又是怎么在C/C++中调用汇编的函数,或者反过来。。。。。。。。。。。。。呵呵,自从学习的语言越来越多,类似的情况碰到的也就越来越多了,但是,只懂一门语言就不能在合适的时候使用合适的语言来解决问题,并且看问题会带有狭隘的偏见,谁说的来着?毕竟无论是lua,python,asm都会有用的上的时候,我最近似乎老是喜欢说闲话。。。。这是某些哥们说的自己的见解,还是某些时候无聊的牢骚呢?谁知道呢,过年了嘛,还不让人多说几句话啊。。。。。。-_-!

首先来看

C中调用汇编的函数

先添加一个汇编文件写的函数吧,在VS2005中对此有了明显的进步,因为就《加密与解密》一书描述,在2003中需要自己配置编译选项,但是在VS2005中很明显的,当你添加asm文件后,可以自己选定masm的编译规则,然后一切就由IDE把你做好了,这也算是IDE的一个好用的地方吧。。。。

非常不好的一点就是,VS2005中对于汇编没有任何语法高亮。。。。damnit!IDE怎么做的?就这点而言,其甚至不如一般的文本编辑工具!。。。又是废话了。。

因为是C,这个目前全世界可能是最具有可移植性的语言,所以问题要简单的多。但是。。。也不全是那么简单,先看看直觉的写法:

汇编代码:

PUBLIC GetArgument

.486                      ; create 32 bit code

.model flat       ; 32 bit memory model

;option casemap :none      ; case sensitive

_TEXT SEGMENT PUBLIC 'CODE'

GetArgument PROC

    MOV EAX, [ESP+4]

    RETN

GetArgument ENDP

_TEXT ENDS

END

 

C语言代码:

#include <stdio.h>

#include <windows.h>

 

int GetArgument(int);

int _tmain(int argc, _TCHAR* argv[])

{

 

    printf("%d/n",GetArgument(10));

 

    system("PAUSE");

 

    return 0;

}

 

声明是必不可少的,毕竟汇编没有头文件给你包含,不过多的话,可以考虑组织一个专门用于包含汇编函数实现的头文件。但是在编译时却不会通过。

1>InlineAsm.obj : error LNK2001: 无法解析的外部符号_GetArgument

1>    D:/My Document/Visual Studio 2005/Projects/InlineAsm/Release/InlineAsm.exe : fatal error LNK1120: 1 个无法解析的外部命令

看到错误原因也知道是怎么回事了,C中的函数名被编译器处理时多了个前置的下划线,当然,这个问题好解决。

一种方式是改变汇编代码的函数,直接添加一个前置下划线就完了,一种方式是将其声明为C语言的方式,那么链接程序也知道正确的链接了。两种方式分别如下:

直接改变函数名:

PUBLIC _GetArgument

.486                      ; create 32 bit code

.model flat       ; 32 bit memory model

;option casemap :none      ; case sensitive

_TEXT SEGMENT PUBLIC 'CODE'

_GetArgument PROC

    MOV EAX, [ESP+4]

    RETN

_GetArgument ENDP

_TEXT ENDS

END

 

改变.model声明:

PUBLIC GetArgument

.486                      ; create 32 bit code

.model flat,c       ; 32 bit memory model

;option casemap :none      ; case sensitive

_TEXT SEGMENT PUBLIC 'CODE'

GetArgument PROC

    MOV EAX, [ESP+4]

    RETN

GetArgument ENDP

_TEXT ENDS

END

 

个人推荐第2种方式,因为看起来最舒服,将改变函数名的工作交给编译和链接程序吧。

假如是在C++中调用ASM函数的话,相对复杂一点,因为没有.model C++的生命方式。。。这个世界是不公平对待CC++的。。。。呵呵,但是C++有完整的向C靠拢的机制,这就够了。

汇编代码不变,C++调用时用如下形式:

#include <stdio.h>

#include <windows.h>

 

extern "C" int _cdecl GetArgument(int);

int _tmain(int argc, _TCHAR* argv[])

{

 

    printf("%d/n",GetArgument(10));

 

    system("PAUSE");

 

    return 0;

}

 

即将C++函数完整的声明为C语言的形式。。。。。但是我在MSDN中看到了.model起码有stdcall的声明方式,有这种声明方式为什么不用呢?呵呵,用一下。

将汇编语言的.model声明改成下面这样:

.model flat,c,stdcall       ; 32 bit memory model

C++中函数声明为下面这样:

extern "C" int __stdcall GetArgument(int);

结果却是链接错误:

1>    InlineAsm.obj : error LNK2001: 无法解析的外部符号_GetArgument@4

当我自以为声明一致时,却不知道发生了什么,假如是以前,我可能得一筹莫展。。。但是现在嘛。。。。既然知道obj文件其实也是可读的,那么,看看链接的时候出了什么问题,为什么汇编出来的obj文件中没有这个符号呢?可以在obj文件的最后一行看到答案:

原来汇编的代码声明stdcall后函数符号被解析成_GetArgument@0了,那不是表示没有参数吗?看来是我汇编写错了。

改成如下形式:

PUBLIC GetArgument

.486                      ; create 32 bit code

.model flat,c,stdcall       ; 32 bit memory model

;option casemap :none      ; case sensitive

_TEXT SEGMENT PUBLIC 'CODE'

GetArgument PROC x:DWORD

    MOV EAX, x

    RETN 4

GetArgument ENDP

_TEXT ENDS

END

然后再运行程序,崩溃。。。。。。

看看原因:

 

GetArgument PROC x:DWORD

00401030  push        ebp 

00401031  mov         ebp,esp

    MOV EAX, x

00401033  mov         eax,dword ptr [x]

    RETN 4

00401036  ret         4  

很明显汇编编译后自动加了push        ebpmov         ebp,esp这两句来保护栈指针esp,问题是却没有自动生成还原的代码。。。那还不崩溃?典型的栈错误。可以用下面的方式修复

GetArgument PROC x:DWORD

    MOV EAX, x

    pop ebp

RETN 4

但是这样做个人感觉实在是太不优美了。。。。。。。奇怪的是编译器为什么要这样解析代码。。。。呵呵,即便你是用汇编。。。特别是伪汇编。。。你都会发现编译器在你的背后动了太多手脚,很多,是你根本不想要它去做的。这一点也可能是我汇编代码声明或写的有问题,导致编译器奇怪的处理了,有知道正确结果的高人请指点一下.

 

下面,在汇编中调用C/C++函数:

在此不分辨CC++了,差别仅在于一个extern “C”而已,调用约定采用__stdcall其他请参考

汇编代码如下:

PUBLIC GetArgument2

.486                      ; create 32 bit code

.model flat,stdcall       ; 32 bit memory model

;option casemap :none      ; case sensitive

GetArgument PROTO  :DWORD   ; 函数声明

_TEXT SEGMENT PUBLIC 'CODE'

GetArgument2 PROC x:DWORD

    INVOKE GetArgument,x

    MOV EAX, x

    POP EBP

    RETN 4

GetArgument2 ENDP

_TEXT ENDS

END

 

C++代码:

#include <stdio.h>

#include <windows.h>

 

extern "C" int __stdcall GetArgument(int ai)

{

    return ai;

}

 

extern "C" int __stdcall GetArgument2(int ai);

 

int _tmain(int argc, _TCHAR* argv[])

{

 

    printf("%d/n",GetArgument2(10));

 

    system("PAUSE");

 

    return 0;

}

 

 

至此,你会高兴的发现,一个10,从C++中调用汇编的函数GetArgument2,再从汇编中调用C++的函数GetArgument再返回,得到正确结果。。。真不容易啊。。。这例子举得真够折腾的:)呵呵,说明问题就好了。最重要的一句就在于GetArgument PROTO  :DWORD    ; 函数声明

一行,另外,这一行应该在.model声明以后,不然编译器不知道你该采用那种调用约定和名字编码方式。

 

 

 

参考资料:MSDN

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

《数据结构与算法分析C++描述》 搜索二叉树的C++实现


《数据结构与算法分析C++描述》
搜索二叉树的C++实现

write by 九天雁翎(JTianLing) -- www.jtianling.com

 
 

《数据结构与算法分析c++描述》 Mark Allen Weiss
人民邮电大学出版
中文版第93-100面,搜索二叉树

需要说明一点的是,此搜索二叉树并没有平衡算法,所以可能会导致有可能出现O(M logN)的最坏情况。

并且几乎所有代码都用递归实现,所以效率并不是太高,并且当N足够大的时候,很多操作都可能导致栈溢出。但是因为对于树的操作用递归描述起来理解上还是比循环好的多,并且以后可以用平衡算法,所以这里都用递归了。

 

搜索二叉树的实现:

  1
  2 #ifndef __BINARY_SEARCH_TREE_H__
  3 #define __BINARY_SEARCH_TREE_H__
  4
  5 template<typename T>
  6 class CBinarySearchTree
  7 {
  8 public:
  9     CBinarySearchTree():mpRoot(NULL) { }
 10     CBinarySearchTree(const CBinarySearchTree& aOrig)
 11     {
 12         mpRoot = Clone(aOrig.mpRoot);
 13     }
 14     ~CBinarySearchTree()
 15     {
 16         MakeEmpty();
 17     }
 18
 19     ////////////////////////////////////////////
 20     // const member function
 21     ////////////////////////////////////////////
 22     const T* FindMin() const;
 23     const T* FindMax() const;
 24
 25     bool Contains( const T& aElement) const;
 26     bool IsEmpty() const
 27     {
 28         return (mpRoot != NULL) ? true : false;
 29     }
 30
 31     // I don't know how to print it in a good format
 32     //void PrintTree() const;
 33
 34     ////////////////////////////////////////////
 35     // non-const member function
 36     ////////////////////////////////////////////
 37     void MakeEmpty();
 38     void Insert( const T& aElement);
 39     void Remove( const T& aElement);
 40
 41     const CBinarySearchTree& operator=(const CBinarySearchTree& aOrig);
 42
 43 private:
 44     struct CBinaryNode
 45     {
 46         CBinaryNode(const T& aElement, CBinaryNode* apLeft, CBinaryNode* apRight)
 47             : mElement(aElement),mpLeft(apLeft),mpRight(apRight) {  }
 48
 49         T mElement;
 50         CBinaryNode *mpLeft;
 51         CBinaryNode *mpRight;
 52     };
 53
 54     // Root Node
 55     CBinaryNode *mpRoot;
 56
 57     ////////////////////////////////////////////
 58     // private member function to call recursively
 59     ////////////////////////////////////////////
 60
 61     // I don't like to use reference to pointer
 62     // so I used pointer to pointer instead
 63     void Insert(const T& aElement, CBinaryNode** appNode) const;
 64     void Remove(const T& aElement, CBinaryNode** appNode) const;
 65
 66     CBinaryNode* FindMin(CBinaryNode* apNode) const;
 67     CBinaryNode* FindMax(CBinaryNode* apNode) const;
 68     bool Contains(const T& aElement, CBinaryNode * apNode) const;
 69     void MakeEmpty(CBinaryNode** apNode);
 70     //void PrintTree(CBinaryNode* apNode) const;
 71     CBinaryNode* Clone(CBinaryNode* apNode) const;
 72
 73 };
 74
 75
 76 template<typename T>
 77 bool CBinarySearchTree::Contains(const T& aElement) const
 78 {
 79     return Contains(aElement, mpRoot);
 80 }
 81
 82 template<typename T>
 83 bool CBinarySearchTree
::Contains(const T &aElement;, CBinaryNode *apNode) const
 84 {
 85     if( NULL == apNode )
 86     {
 87         return false;
 88     }
 89     else if ( aElement < apNode->mElement )
 90     {
 91         return Contains(aElement, apNode->mpLeft);
 92     }
 93     else if ( aElement > apNode->mElement )
 94     {
 95         return Contains(aElement, apNode->mpRight);
 96     }
 97     else
 98     {
 99         return true;      // Find it
100     }
101 }
102
103 template<typename T>
104 void CBinarySearchTree
::Insert(const T &aElement;)
105 {
106     Insert(aElement, &mpRoot;);
107 }
108
109 template<typename T>
110 void CBinarySearchTree
::Insert(const T& aElement, CBinaryNode** appNode) const
111 {
112     CBinaryNode *lpNode = *appNode;
113     if(NULL == lpNode)
114     {
115         *appNode = new CBinaryNode(aElement, NULL, NULL);
116     }
117     else if( aElement < lpNode->mElement )
118     {
119         Insert(aElement, &(lpNode->mpLeft) );
120     }
121     else if( aElement > lpNode->mElement)
122     {
123         Insert(aElement, &(lpNode->mpRight) );
124     }
125
126     // had not deal with duplicate
127 }
128
129 template<typename T>
130 void CBinarySearchTree
::Remove(const T &aElement;)
131 {
132     Remove(aElement, &mpRoot;);
133 }
134
135 template<typename T>
136 void CBinarySearchTree
::Remove(const T &aElement;, CBinaryNode** appNode) const
137 {
138     CBinaryNode* lpNode = *appNode;
139     if(NULL == lpNode)
140     {
141         return;       // Item removing is not exist
142     }
143
144     if( aElement < lpNode->mElement )
145     {
146         Remove(aElement, &(lpNode->mpLeft) );
147     }
148     else if( aElement > lpNode->mElement )
149     {
150         Remove(aElement, &(lpNode->mpRight) );
151     }
152     else if( NULL != lpNode->mpLeft && NULL != lpNode->mpRight) // Two children
153     {
154         lpNode->mElement = FindMin(lpNode->mpRight)->mElement;
155         Remove( lpNode->mElement, &(lpNode->mpRight) );
156     }
157     else
158     {
159         CBinaryNode *lpOldNode = lpNode;
160         // Even if lpNode equal NULL, this is still the right behavior we need
161         // Yeah,When lpNode have no children,we make lpNode equal NULL
162         *appNode = (lpNode->mpLeft != NULL) ? lpNode->mpLeft : lpNode->mpRight;
163         delete lpOldNode;
164     }
165 }
166
167
168 template<typename T>
169 const T* CBinarySearchTree
::FindMin() const
170 {
171     CBinaryNode* lpNode = FindMin(mpRoot);
172     return (lpNode != NULL) ? &(lpNode->mElement) : NULL;
173 }
174
175
176 // damn it! So redundant words to fit to C++ syntax
177 // the only way to fix this problom is compositing defines and declares
178 // I even doubt that are there programmers could write it right
179 template<typename T>
180 typename CBinarySearchTree
::CBinaryNode * CBinarySearchTree::FindMin(CBinaryNode* apNode) const
181 {
182     if( NULL == apNode)
183     {
184         return NULL;
185     }
186     else if( NULL == apNode->mpLeft)
187     {
188         // Find it
189         return apNode;
190     }
191     else 
192     {
193         return FindMin(apNode->mpLeft);
194     }
195 }
196
197 template<typename T>
198 const T* CBinarySearchTree
::FindMax() const
199 {
200     CBinaryNode* lpNode = FindMax(mpRoot);
201     return (lpNode != NULL) ? &(lpNode->mElement) : NULL;
202 }
203
204 template<typename T>
205 typename CBinarySearchTree
::CBinaryNode * CBinarySearchTree::FindMax(CBinaryNode* apNode) const
206 {
207     if( NULL == apNode)
208     {
209         return NULL;
210     }
211     else if( NULL == apNode->mpRight)
212     {
213         // Find it
214         return apNode;
215     }
216     else 
217     {
218         return FindMax(apNode->mpRight);
219     }
220 }
221
222 template<typename T>
223 void CBinarySearchTree
::MakeEmpty()
224 {
225     MakeEmpty(&mpRoot;);
226 }
227
228
229 template<typename T>
230 void CBinarySearchTree
::MakeEmpty(CBinaryNode** appNode)
231 {
232     CBinaryNode* lpNode = *appNode;
233     if( lpNode != NULL)
234     {
235         MakeEmpty( &(lpNode->mpLeft) );
236         MakeEmpty( &(lpNode->mpRight) );
237         delete lpNode;
238     }
239
240     *appNode = NULL;
241 }
242
243 // how long the syntax is...............
244 template<typename T>
245 const CBinarySearchTree
& CBinarySearchTree::operator =(const CBinarySearchTree &aOrig;)
246 {
247     if(&aOrig; == this)
248     {
249         return *this;
250     }
251
252     MakeEmpty();
253     mpRoot = Clone(aOrig.mpRoot);
254
255     return *this;
256
257 }
258
259 // when you use nest class and template both,you will find out how long the C++ syntax is.....
260 // I use it once,I ask why couldn't we have a short once again.
261 template<typename T>
262 typename CBinarySearchTree
::CBinaryNode* CBinarySearchTree::Clone(CBinaryNode *apNode) const
263 {
264     if(NULL == apNode)
265     {
266         return NULL;
267     }
268
269     // abuse recursion
270     return new CBinaryNode(apNode->mElement, Clone(apNode->mpLeft), Clone(apNode->mpRight));
271 }
272
273
274
275
276 #endif // __BINARY_SEARCH_TREE_H__

 

 

测试代码:

 1 #include
 2 #include "BinarySearchTree.h"
 3 using namespace std;
 4
 5 int _tmain(int argc, _TCHAR* argv[])
 6 {
 7     CBinarySearchTree<int> loTree;
 8
 9     loTree.Insert(10);
10     loTree.Insert(20);
11     loTree.Insert(30);
12     loTree.Insert(40);
13     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  "<20) <
14     loTree.Remove(40);
15     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <
20) <
16     loTree.Remove(30);
17     loTree.Remove(20);
18     loTree.Remove(10);
19
20
21     loTree.Insert(40);
22     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <
20) <
23     loTree.Insert(30);
24     loTree.Insert(20);
25     loTree.Insert(10);
26     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <
20) <
27     loTree.Remove(40);
28     loTree.Remove(30);
29     loTree.Remove(20);
30     loTree.Remove(10);
31
32     loTree.Insert(30);
33     loTree.Insert(40);
34     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <
20) <
35     loTree.Insert(10);
36     loTree.Insert(20);
37     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <
20) <
38     CBinarySearchTree<int> loTree2 = loTree;
39     cout <<"Min: " <<*loTree2.FindMin() <<" Max: " <<*loTree2.FindMax() <<" IsContains(20)  " <20) <

40
41     loTree.MakeEmpty();
42
43
44
45     system("pause");
46     return 0;
47 }
48

 

 

 

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....