花花草草

Jim Chan函数调用的汇编程序过程

7zeal — 2007-10-17 19:57:00

Jim Chan摘要：本文说明高级语言编译成汇编语言后，高级语言中函数调用的汇编程序过程。正文：高级语言编译成汇编程序以后，在高级语言中的函数调用的汇编程序过程如下：1.将函数参数入栈，第一个参数在栈顶，最后一个参数在栈底。2.执行CALL指令，调用该函数，进入该函数代码空间。a.执行CALL指令，将CALL指令下一行代码的地址入栈。b.进入函数代码空间后，将基址指针EBP入栈，然后让基址指针EBP指向当前堆栈栈顶，并使用它访问存在堆栈中的函数输入参数及堆栈中的其他数据。c.堆栈指针ESP减少一个值，如44H，向上移动一个距离，留出一个空间给该函数作为临时存储区。{ // 以上准备工作做好后，函数正式被执行，如下所示。 d.将其他指针或寄存器中的值入栈，以便在函数中使用这些寄存器。 e.执行代码。 f.执行return()返回执行结果，将要返回的值存入EAX中。 g.步骤2.d中的指针出栈。}h.将EBP的值传给堆栈指针ESP，使ESP复原为2.c之前的值。此时进入函数时EBP的值在栈顶。i.基址指针EBP出栈，复原为2.b之前的EBP的值。j.执行RET指令，“调用函数”的地址出栈，本函数返回到CALL指令的下一行。3.函数返回到CALL指令下一行，将堆栈指针加一个数值，以使堆栈指针恢复到以上步骤1执行之前的值。该数值是上面第一步入栈参数的总长度。注意：1.堆栈指针ESP指向栈顶的新入栈数据的最低位。2.MOV指令中偏移指针指向被“MOV”的数据的最低位。如下面指令是将ebp+8到ebp+11四个字节的内容传到eax寄存器中。00402048 mov eax,dword ptr [ebp+8]一个例子如下：高级语言代码中的函数调用如下：117: bR = t1(p);汇编代码如下：00401FB8 mov &nb

函数调用时堆栈的使用

7zeal — 2007-10-17 19:24:00

在经典的汇编语言教程中，函数调用时堆栈的使用都是着重讲解的问题。如今随着高级语言的越来越完善，单纯使用汇编开发的程序已经不多了。但对函数调用时堆栈动向的了解仍有助于我们明晰程序的执行流程，从而在程序编写和调试的过程中有一个清晰的思路。一．调用约定在Win32中，有关函数的调用主要有两种约定。 1．_stdcall 以__stdcall方式调用的函数有以下特征： ? 参数由右至左压栈 ? 调用返回时，堆栈由被调函数调整 2．__cdecl __cdecl约定是C/C++函数的默认调用约定。它有以下特征： ? 参数由右至左压栈 ? 调用返回时，堆栈由调用者调整二．Win32函数调用过程 1. 压入参数这里依据以上的调用方式将调用者给出的参数一一压入堆栈。 2. 压入断点当程序执行到Call指令的时候，当前语句的地址作为断点地址压入堆栈。 3. 跳转 eip的值被重新设置为被调函数的起始地址。 4. mov ebp, esp 这里ebp被用来在堆栈中寻找调用者压入的参数，同时作为调用者堆栈指针的一个备份。在此前还应该执行一条： push ebp 把ebp中原来的数值保存。 5. sub esp，N 这里N是函数内局部变量的总字节数加上一个整数，一般为40。此后esp即为被调函数的堆栈指针了。 6. 初始化esp ~ esp-N之间的N字节空间这是对堆栈中已分配给局部变量使用的内存空间的初始化，一般全部设置为0xcc。 7. 顺序执行函数内语句。此时函数的堆栈位于所有局部变量的内存空间之后，二者之间一般有40字节的隔离带。 8．返回为保障调用的正常返回，函数内应当保证规范使用堆栈，使即将返回的时候esp的值恢复为执行第一条语句前的状态。说明白点，就是每一条push都要有相应的pop。调用返回的过程如下： mov esp, ebp 执行后，esp恢复为调用者的堆栈指针，栈顶除断点地址外，还存有原ebp的值和调用时压入的参数。然后依次弹出ebp的值和断点地址。如果是__cdecl约定则直接返回调用者，调用者将负责调整堆栈，丢弃调先前压入的参数。如果是__stdcall则这个工作由被调函数来执行。程序样例如下： …… 0040B8E8 push 1 ;压入参数 0040B8EA call 00401028 ;调用函数 …… 0

Win32 环境下的堆栈选择自 slimak 的 Blog

7zeal — 2007-10-17 19:15:00

Win32 环境下的堆栈(一) 简介在Win32环境下利用调试器调试应用程序的时候经常要和堆栈(Stack)打交道,尤其是在需要手工遍历堆栈(Manually Walking Stack)的时候我们需要对堆栈的工作过程有一个比较清晰的了解.接下来的这些文字将通过一个例子程序详细的讲解堆栈的工作过程. 关键字调试堆栈 Stack Stack-Frame 目录 1.堆栈是什么? 2.堆栈里面放的都是什么信息? 3.堆栈是在什么时候被建立起来的?它的默认大小是多少? 4.默认才1M??那要是我的程序使用超过了1M的堆栈怎么办? 5.什么叫Stack Frame? 6.在一次函数调用中,堆栈是如何工作的? 7.老大,结合一个例子讲讲吧? 1.堆栈是什么? 从内存管理角度看,堆栈是就是一块连续的内存空间,对它的操作采用先入后出的规则,他的生长方向与内存的生长方向正好相反,也就是说它是从高地址向低地址生长. 从Win32程序内部的角度看,每一个线程有自己的堆栈,它主要用来给线程提供一个暂时存放数据的区域,程序使用POP/PUSH指令来对堆栈进行操作. 2.堆栈里面放的都是什么信息? 堆栈中存放的信息包括:当前正在执行的函数的局部变量,函数返回地址,该函数的上层函数传给该函数的参数,EBP的值,一些通用寄存器(EDI,ESI…)的值,注意这里提到的正在执行的函数,比如有下面的一段C代码: void B() { printf(“B\n”); } void A() { B(); } 那么当程序执行到B函数的pri

6.3 正确的尾调用(原文:Proper Tail Calls)

7zeal — 2007-10-17 19:00:00

6.3 正确的尾调用(原文:Proper Tail Calls)Lua中函数的另一个有趣的特征是可以正确的处理尾调用.(一些作者使用术语尾递归[原文:proper tail recursion],虽然并未涉及到递归的概念) .尾调用是一种类似在函数结尾的goto调用,当函数最后一个动作是调用另外一个函数时,我们称这种调用尾调用.例如:function f (x) return g(x) end g的调用是尾调用. 例子中f调用g后不会再做任何事情,这种情况下当被调用函数g结束时程序不需要返回到调用者f;所以尾调用之后程序不需要在栈中保留关于调用者的任何信息.一些编译器比如Lua解释器利用这种特性在处理尾调用时不使用额外的栈,我们称这种语言支持正确的尾调用. 由于尾调用不需要使用栈空间,那么尾调用递归的层次可以无限制的.例如下面调用不论n为何值不会导致栈溢出. function foo (n) if n > 0 then return foo(n - 1) end end需要注意的是:明确什么是尾调用.一些调用者函数调用其他函数后也没有做其他的事情但不属于尾调用.比如:function f (x) g(x) return end 上面这个例子中f在调用g后,不得不丢弃g地返回值,所以不是尾调用,同样的下面几个例子也不时尾调用: return g(x) + 1 -- must do the addition return x or g(x) -- must adjust to 1 result return (g(x)) -- must adjust to 1 result Lua中类似return g(...) 这种格式的调用是尾调用.但是g和g的参数都可以是复杂

QK

7zeal — 2007-10-12 19:37:00

循环队列的基本操作

7zeal — 2007-09-08 16:46:00

#define maxsize 5#include #include typedef struct{ int data[maxsize]; int front; int rear;}SqQueue; void InitQueue(SqQueue *&q){ q=(SqQueue*)malloc(sizeof(SqQueue));//有志向拉 q->front=q->rear=0;} void ClearQueue(SqQueue *&q){ free(q);} int EnQueue(SqQueue *&q,int &e){ if((q->rear+1)%maxsize==q->front) { printf("队列满了\n",e); return 0;//队满 } q->rear=(q->rear+1)%maxsize; q->data[q->rear]=e; return 1;} int ouQueue(SqQueue *&q,int &e){ if((q->rear==q->front)) { printf("队列为空\n",e); return 0;//队空 } q->front=(q->front+1)%maxsize; e=q->data[q->front]; printf("出队元素是%d\n",e); return 1;} void Show(SqQueue *&q){ int i=0; for(i=0;i<((q->rear-q->front+maxsize)%maxsize);i++) printf("%d ",q->data[(q->front+1+i)%max

堆栈的基本操作

7zeal — 2007-09-08 14:37:00

#define STACK_INIT_SIZE 3#define STACK_INCREAMENT 2#define null 0#include #include typedef struct stack{ int *base; int *top; int size;//当前已非配的空间，没数据也算 }Sqstack;//用作堆栈的指针de 类型 void Initstack(Sqstack &s)//建立堆栈{ s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(s.base==null) { printf("overflow"); } s.top=s.base; s.size=STACK_INIT_SIZE;} void Gettop(Sqstack &s,int &e){ if(s.top==s.base){printf("stack is empty");} e=*(s.top-1);//注意哦，有一个元素时top指向第二隔了,没改变TOP的指向} void Push(Sqstack &s,int e){ if((s.top-s.base)+1==s.size)//堆栈满了 { s.base=(int*)realloc(s.base,(s.size+STACK_INCREAMENT)*sizeof(int)); //仍然以源地址为基地址，从。size后续补充increase &nbs

打印斜下三角形

7zeal — 2007-09-08 14:35:00

int max=10;int a[10][10]={0};int i,j,t,q=0,s=0,n=max ; for(;n>0;n--) { s=s+n; } for(t=1,i=0,j=0;t

Stein算法--转bpttc的发言

7zeal — 2007-04-20 12:23:00

转自http://www.programfan.com/club/showbbs.asp?id=227318&page=1 bpttc的发言 int GCD_Stein( int x, int y ){ int factor = 0; int temp; if ( x < y ) { temp = x; x = y; y = temp; } while ( x != y ) { &

c#作业

7zeal — 2007-04-18 21:32:00

using System; namespace studywork2{ public class work { public static void sumjiecheng() { long n = 1, t = 1, s = 0; for (; n <= 20; n++) { t *= n; s += t; } Console.WriteLine("1到20的阶乘之和为:"); Console.WriteLine(s); } &n

gcc3

7zeal — 2007-04-18 15:24:00

#include #include #define M 20 char a[M][M]; int fuback(int k,int n,char u){ int i; if(k==0) u='T'; if(k==1) u='J'; for(i=k;i

gcc2

7zeal — 2007-04-18 15:23:00

#include /* 2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些人参加了竞赛：（１）Ａ参加时，Ｂ也参加；（２）Ｂ和Ｃ只有一个人参加；（３）Ｃ和Ｄ或者都参加，或者都不参加；（４）Ｄ和Ｅ中至少有一个人参加；（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。*/ int main(){ int a,b,c,d,e; /*其中值1为参加，0为不参加*/ for(a=0;a<=1;a++) for(b=0;b<=1;b++) for(c=0;c<=1;c++) for(d=0;d<=1;d++) for(e=0;e<=1;e++) if(((b&&!c)||(!b&&c))&&((c&&d)||(!c&&!d))&&(d||e)) /*分别代表条件2~4*/ if((a&&b||!a)&&(e&&(a&&d)||!e))/*代表条件1和5，特别注意a，e不一定参加*/ &nb

gcc1

7zeal — 2007-04-18 15:22:00

// gcc1.cpp : Defines the entry point for the console application./*1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不 D F G 同字母。编程求出这些数字并且打出这个数字的 + D F G 算术计算竖式。 ─────── X Y Z D E*/ #include "stdafx.h"#include #include int f=5,g=0,a,b,c,d,e,x,y,z=0;void Search(int n){ for(c=1;c<10;c++) { if(c==5) continue; for(d=1;d<10;d++) { &nbs

求割顶－－ZJU1311

7zeal — 2007-04-18 15:17:00

求割点（关键点）首先，对于单独的一个点，或者2个点，我们不予考虑，因为我们没法认定。分情况：如果待确定的点不是搜索树的根节点，那么关键点可以认为是这样的点V，他的子孙节点中存在一个节点P，从P出发继续向下拓展（也就是不再走已经走过的边，而是向下兜圈子，然后通过某个后向边回到前面已经访问过的点，这里可以看出后向边的价值，后向边在dfs中是不允许扩展的，但是我们说的“兜回到祖先”就是通过某个后向边实现的）dfs不能达到V的祖先，事实上，只要有任意一个子孙节点符合这个特性，那么v就是关键点，因为原本子孙和祖先是连通的，删除它之后，他的子孙至少无法走到他的祖先（包括它的兄弟姐妹。。。）如果是根节点，他如果只有一个子树，那么他不是关键点，如果有多于一个的子树，那么他必然是关键点具体实现：具体实现是这样的，我们定义一个点上的函数dfn(v)，表示v这个点在dfs过程中第一次访问的顺序，然后，为了达到上面的定义，我们再定义一个点上的函数low(v)，low(v)表示从v出发，继续向下拓展搜索，所能达到的最早的点，也就是dfn最小的点显然，low(v)有： low(v)=min(dfn(v),low(s),dfn(w)) 其中，s是所有儿子节点，w是v的后向边割顶：连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。注意：完全图的连通度为总顶点数－1；牵一发而动全身的点称为割点边连通度：连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；连通图的两个特征：1 连通度<=边连通度<=顶点数2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)块的概念：没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障至少两个站点同时发生故障，这种二连通分支称为块．显然各个块之间的关系有如下两种：1　互不连接2　通过割顶连接(割顶可以属于不同的块，也可以两个块公有一

四种寻路算法并比较

7zeal — 2007-04-18 15:16:00

四种寻路算法并比较好久没搞这些东西了...想了十分钟才勉强回忆起来...写了三个钟头...好累啊...四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*)用了两张障碍表，一张是典型的迷宫： char Block[SY][SX]={{1,1,1,1,1,1,1,1,1,1,1 },{1,0,1,0,1,0,0,0,0,0,1 },{1,0,1,0,0,0,1,0,1,1,1 },{1,0,0,0,1,0,1,0,0,0,1 },{1,0,1,1,0,0,1,0,0,1,1 },{1,0,1,0,1,1,0,1,0,0,1 },{1,0,0,0,0,0,0,0,1,0,1 },{1,0,1,0,1,0,1,0,1,0,1 },{1,0,0,1,0,0,1,0,1,0,1 },{1,1,1,1,1,1,1,1,1,1,1 }}; 第二张是删掉一些障碍后的: char Block[SY][SX]={{1,1,1,1,1,1,1,1,1,1,1 },{1,0,1,0,1,0,0,0,0,0,1 },{1,0,1,0,0,0,1,0,1,1,1 },{1,0,0,0,0,0,1,0,0,0,1 },{1,0,0,1,0,0,1,0,0,1,1 },{1,0,1,0,0,1,0,1,0,0,1 },{1,0,0,0,0,0,0,0,1,0,1 },{1,0,1,0,0,0,1,0,1,0,1 },{1,0,0,1,0,0,1,0,0,0,1 },{1,1,1,1,1,1,1,1,1,1,1 }}; 结果：尝试节点数合法节点数步数深度优先 416/133 110/43 19/25广度优先 190/188 48/49 19/15深度+启发 283/39 82/22 19/19广度+启发 189/185 48/49 19/15 所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。附：dfs+heu的源程序，bc++ 3.1通过 #include #include #include #define SX 11 //宽#define SY 10 //长 int

一个图和其中两点.求出该两点间的所有路径

7zeal — 2007-04-18 15:15:00

一个图和其中两点.求出该两点间的所有路径 void lookingforway(graph g){ bool visitedp[max] for (v=0;v

图的相关算法

7zeal — 2007-04-18 15:15:00

在广度优先搜索的基础上求图中两结点的最短路径需1,将链队列的结点改为“双链”结点，即结点中包含next和priou两个指针；2，修改入队列的操作，插入新的队尾结点时，令其priou域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；3，修改出队列的操作，出队列时，仅移动队头指针，而不将队头结点从链表中删除。由于普里姆算法的时间复杂度为O( N的平方)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为o(eloge)，则适于稀疏图。 7.5重（双）连通图和关节点若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。没有关节点的连通图为双连通图。关节点的特征：假设从某个顶点V出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。若生成树的根结点，有两个或两个以上的分支，则此顶点（生成树的根）必为关节点；对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。如何求关键点：1)对根结点来说深度优先遍历看count是否小于结点数，如果小于则该根结点为关节点。2)对生成树上的顶点定义一个函数：low(v)=Min{visited[v],low[w],visited[k]}（k为和v有回边相通的顶点）对顶点v，若（在生成树上）存在一个子树根w,且low[w]>=visited[v]则顶点v为关节点对深度优先遍历算法作如下修改：1，visited[v]的值改为遍历过程中顶点的访问次序count值2,遍历过程中求得low(v)=Min{visited[v],low[w],visited[k]}3,从子树遍历返回时判别low[v]是否>=visited[v] 7.6两点之间的最短路径问题从源点到其余各点的最短路径算法的基本思想：依路径长度递增的次序求得各条路径 7.7拓扑排序如何进行拓扑排序一，从有向图中选取一个没有前驱的顶点(入度为零的顶点)，并输出之；二，从有向图中删去此顶点

深度优先搜索算法（ＤＦＳ）源代码

7zeal — 2007-04-18 15:12:00

深度优先搜索算法（ＤＦＳ）源代码，Ｃ＋＋的， /*深度搜索，用邻接矩阵存储*/void DFSTraverse(Graph *G){int v;for(v=1;v<=G->vexnum;v++)visited[v]=false;for(v=1;v<=G->vexnum;v++)if(visited[v]==false)DFS(G,v);}void DFS(Graph *G,int v){int w;visited[v]=true;visitfunc(G,v);for(w=FirstAdjex(G,v);w>=0;w=NextAdjex(G,v,w))if(visited[w]==false)DFS(G,w);}int FirstAdjex(Graph *G,int v){int i;for(i=1;i<=G->vexnum;i++)if(G->Garr[v][i])return i;return -1;}int NextAdjex(Graph *G,int v,int w){int i;for(i=w+1;i<=G->vexnum;i++)if(G->Garr[v][i])return i;return -1;}

ACM竞赛之新人向导

7zeal — 2007-04-18 15:12:00

ACM竞赛之新人向导 2007-04-05 20:49 原创：怒火之袍 2003年4月29日我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。一、语言是最重要的基本功无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。 C++的另

[算法] 算法总汇

7zeal — 2007-04-18 15:10:00

路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化差分约束系统 Floyd 广义路径问题传递闭包极小极大距离 / 极大极小距离 Euler Path / Tour 圈套圈算法混合图的 Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path

花花草草

Jim Chan函数调用的汇编程序过程

函数调用时堆栈的使用

Win32 环境下的堆栈 选择自 slimak 的 Blog

6.3 正确的尾调用(原文:Proper Tail Calls)

QK

循环队列的基本操作

堆栈的基本操作

打印斜下三角形

Stein算法--转bpttc的发言

c#作业

gcc3

gcc2

gcc1

求割顶－－ZJU1311

四种寻路算法并比较

一个图和其中两点.求出该两点间的所有路径

图的相关算法

深度优先搜索算法（ＤＦＳ）源代码

ACM竞赛之新人向导

[算法] 算法总汇

Win32 环境下的堆栈选择自 slimak 的 Blog