博文
函数调用时堆栈的使用(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恢复为调用者的堆栈指针，栈顶除断点地址外，还存有原e......
6.3 正确的尾调用(原文:Proper Tail Calls)(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)) &n......
循环队列的基本操作(2007-09-08 16:46:00)
摘要：#define maxsize 5
#include <stdio.h>
#include <alloc.h>
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;
堆栈的基本操作(2007-09-08 14:37:00)
摘要：#define STACK_INIT_SIZE 3
#define STACK_INCREAMENT 2
#define null 0
#include <stdio.h>
#include <alloc.h>
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));