LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   I need help with understand a recursive assembly program. (https://www.linuxquestions.org/questions/programming-9/i-need-help-with-understand-a-recursive-assembly-program-746920/)

joeBuffer 08-12-2009 03:02 AM

I need help with understanding a recursive assembly program.
 
I've read through almost half this book, and have not had a problem understanding a program from it, except for this program. It's "Programming from the Ground Up" by Jonathan Bartlett.
This is a real headache. I would really appreciate a simple explanation of why this works. Maybe someone else will, too, sometime.
It's been a well-explained, easy-to-understand book, except for this:
Code:

#PURPOSE - Given a number, this program computes the
#          factorial. For example, the factorial of
#          3 is 3 * 2 * 1, or 6. The factorial of
#          4 is 4 * 3 * 2 * 1, or 24, and so on.
#
#This program shows how to call a function recursively.
.section .data

#This program has no global data
.section .text
.globl _start
.globl factorial  #this is unneeded unless we want to share
                  #this function among other programs
_start:
 pushl $4        #The factorial takes one argument - the
                  #number we want a factorial of. So, it
                  #gets pushed
 call factorial  #run the factorial function
 addl $4, %esp    #Scrubs the parameter that was pushed on
                  #the stack
 movl %eax, %ebx  #factorial returns the answer in %eax, but
                  #we want it in %ebx to send it as our exit
                  #status
 movl $1, %eax    #call the kernelís exit function
 int  $0x80
#This is the actual function definition
.type factorial,@function
factorial:
 pushl %ebp          #standard function stuff - we have to
                    #restore %ebp to its prior state before
                    #returning, so we have to push it
 movl %esp, %ebp    #This is because we donít want to modify
                    #the stack pointer, so we use %ebp.
 movl  8(%ebp), %eax #This moves the first argument to %eax
                    #4(%ebp) holds the return address, and
                    #8(%ebp) holds the first parameter
 cmpl $1, %eax      #If the number is 1, that is our base
                    #case, and we simply return (1 is
                    #already in %eax as the return value)
 je end_factorial
 decl %eax          #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial
 movl 8(%ebp), %ebx  #%eax has the return value, so we
                    #reload our parameter into %ebx
 imull %ebx, %eax    #multiply that by the result of the
                    #last call to factorial (in %eax)
                    #the answer is stored in %eax, which
                    #is good since thatís where return
                    #values go.
end_factorial:
 movl %ebp, %esp #standard function return stuff - we
 popl %ebp      #have to restore %ebp and %esp to where
                #they were before the function started
 ret            #return to the function (this pops the
                #return value, too)

I have no idea if I'm missing something, or didn't pay attention when I should've, or what. The rest of the book is all very easy for me to understand. For whatever reason, learning about recursive functions in C took me a few minutes ... but it only took a few minutes for me to slap myself. :doh:
This is ridiculous. I understand all the parts of this program, but not how they add up somehow. I've written it out, gone over it, maybe someone else would appreciate having a good explanation, I'm sleepy, etc. :(

nowonmai 08-12-2009 06:32 AM

It looks pretty straightforward...
The factorial keeps calling itself and decrementing its parameter (in eax) until it's equal to 1 at which point it returns, and moves the eax to ebx which will be returned to the calling program (or OS).

johnsfine 08-12-2009 06:56 AM

It would be hard to improve on the comments in that program. They explain everything clearly.

It is even harder to guess which aspect of the program you don't understand. If you understand each part, the total should take care of itself. With more complicated recursive functions that is the only way to "understand" the whole thing:

1) Assume the recursive function works correctly in all the places where it is called by itself.

2) Check whether it works correctly in all cases at the top level. (Including that the recursion is on "simpler" input).

For (2) we see the function is correct on its own if the input is 1. Then we see that for inputs greater than 1 it uses the (assumed correct) recursion to compute factorial for input minus one (which is "simpler" input) and then multiplies that result by the input.

Did you not know the recursive definition of factorial?
factorial(0) = 1
factorial(N) = N * factorial(N-1)

Do you not see how the asm code performs that operation (except they work only for 1 and up, not for 0).

In most asm coding you need to give some extra thought to understanding the stack layout. The comments in that code pretty well covered that (except they said "pops the return value, too" when they should have said "pops the recursive calling parameter if any").

You should understand the stack and calling conventions from the outside as well as from the inside:

From the outside:
pushl calling_parameter
call factorial
;now or later remove the calling parameter from the stack
;the result is in eax

From the inside
;calling parameter is at 4(%esp) return address is at 0(%esp)
pushl %ebp
movl %esp, %ebp
;now calling parameter is at 8(%ebp) return address is at 4(%ebp)

We can optionally push or not push another value on the stack because
movl %ebp, %esp
;Restored esp to what it was just after the above pushl %ebp
popl %ebp
ret
;The stack is back the way it was before the call

joeBuffer 08-12-2009 06:59 AM

I can't believe it. It's obviously very simple. I'm missing something, here.
Everything up to
Code:

je end_factorial
 decl %eax          #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial
 movl 8(%ebp), %ebx  #%eax has the return value, so we
                    #reload our parameter into %ebx
 imull %ebx, %eax    #multiply that by the result of the
                    #last call to factorial (in %eax)
                    #the answer is stored in %eax, which
                    #is good since that’s where return
                    #values go.
end_factorial:
 movl %ebp, %esp #standard function return stuff - we
 popl %ebp      #have to restore %ebp and %esp to where
                #they were before the function started
 ret            #return to the function (this pops the
                #return value, too)

is very straightforward and easy for me to understand. I have no idea, past this point, what I'm missing. I don't see what is happening, the order it's happening, anything, to cause this to work properly.
WHY, when you get to the test, and %eax does equal 1, and you jump to end_factorial, is everything else taken care of? What happens? I swear on anything ... I have never once seen a code example of any kind that has annoyed me so much in my life. Never.
So, like a C program, then you hit 1, jump to end_factorial, the rest finish and fall through to end_factorial? The %eax does double duty. It's decremented, and it's multiplied by %ebx to hold the return value. %eax doing double duty is one confusing thing to me, maybe one of the reasons I have lost track here.
I'm very, very, very tired of looking at this code.

joeBuffer 08-12-2009 07:11 AM

Quote:

Did you not know the recursive definition of factorial?
factorial(0) = 1
factorial(N) = N * factorial(N-1)
I know that, for instance, 5! is 5*4*3*2*1, and I didn't get the ! from the assembly book, either. The recursive definition I've never thought of.

Quote:

In most asm coding you need to give some extra thought to understanding the stack layout. The comments in that code pretty well covered that (except they said "pops the return value, too" when they should have said "pops the recursive calling parameter if any").

You should understand the stack and calling conventions from the outside as well as from the inside:
1. "pops the return value, too" I noticed myself. I thought it should've said "pops the return address". ?????
2. This book is using the C calling convention. Everything in this book so far I understand, yes. I understand the stack, and the process that is taking place in the rest of the examples in this book, so far.

Quote:

It would be hard to improve on the comments in that program. They explain everything clearly.
VERY.

I have no idea what I'm not understanding, that's the problem. Possibly, like I said in my last post, %eax doing double duty. I'm very frustrated, I have never run into a problem like this when reading code, especially examples like this, with comments and everything, in the middle of a book that is easy for me to understand. I'm used to C and PERL and bash scripting, and things like that. For some reason, this code just fell apart for me. :(

johnsfine 08-12-2009 07:57 AM

Look at this C code
Code:

int factorial(int input) {
  int result = input;
  if ( result == 1 ) goto end_factorial;
  --result;
  result = factorial( result );
  result *= input;
end_factorial:
  return result; }

Do you understand that C code? Do you understand the many uses of the variable "result" in that C code?

In asm %eax is the result variable (that is a rule of the calling convention). %eax also gets used a lot for other things. There are only a few registers and %eax is the most convenient register for most operations.

Compare to some better looking C code
Code:

int factorial(int input) {
  int result = input;
  if ( result != 1 ) {
      result *= factorial( result - 1 ); }
  return result; }

Why can't we do that version in asm?

1) We don't have general purpose if statements, we can only use if in combination with goto. So we needed the label.

2) The function result is always returned in %eax, so when we call factorial recursively we lose the value of result replacing it with the result of the recursive call. So we cannot do
result *= factorial( ...
We can only do
result = factorial( ...
Now look back at my first C version and it should make sense.

joeBuffer 08-12-2009 08:37 AM

To tell the truth, other than applying it to computers, I have absolutely no interest in math or 95% of science. Some geometry is good to know, etc. I've sort of been learning and doing as much as possible without getting into extremely mathematical topics. When a simple, silly example like this makes me scratch my head for 24 hours, I feel very, very far from caring enough about it to extend the amount of time spent to 10 years in school and college just so I can breeze through an introductory assembly book.
On a separate topic, and at the risk of having this thread moved to general, what is your opinion on why mathematics is a good thing to learn? Take computers for instance, what do you apply it to? What else is it good for?

johnsfine 08-12-2009 09:19 AM

Quote:

Originally Posted by joeBuffer (Post 3640400)
On a separate topic, and at the risk of having this thread moved to general, what is your opinion on why mathematics is a good thing to learn?

All math concepts were trivial for me when I was a teenager (though I was quite impatient with a lot of the terminology and symbols), so I didn't worry about what it was good for. It just was easy.

I can't really imagine what life would be like not knowing math well. When I read any news story involving any aspect of economics or public policy or many other topics, I always notice the mathematical aspects of it and usually see that the authors of the story depend on their readers not understanding the math of the situation in order to mislead those readers (most news is written with a liberal bias and clear intent to mislead).

When I shop, I like to get the best value and I notice that "unit prices" on the shelf labels in the supermarket are often incorrect (sometimes wildly incorrect) so if you want to compare by unit price you need to be comfortable with arithmetic.

I'm not very handy with mechanical or physical things, so when I do them (repair a bike, cut down a tree, buy the right amount of paint to paint something, etc.) I try to plan well to compensate for lack of skill. Planning physical tasks (especially when done in an unusual amateur way) often requires significant math.

Quote:

Take computers for instance, what do you apply it to?
Graphics and game programming involve a lot of trig and matrix math. Even calculus can be applied to good effect if you are used to it.

The computer work I currently do involves a lot of more serious math, most of which is beyond my current level of math expertise. (Near the end of high school I found myself loosing most of my math skills and they never came back. I retained math skills well above the top 1% of ordinary people, but that is only a fraction of what I had when I was 15).

The work requires math skills beyond what I have, electrical engineering knowledge beyond what I have, and software engineering skills beyond what anyone at my work other than me has. That is why hard projects need good teams. But relative to your question, there are important parts of computer programming where math skill merely way better than ordinary people doesn't even start to cover it.

neonsignal 08-12-2009 10:11 AM

Recursion is not always an easy concept to grasp, so don't be hard on yourself. The 'aha' moment will come. It is worth thinking about the concept before you get caught up in the implementation, because it is one of the most significant concepts in programming.

The factorial example is not the best use of recursion, but it keeps the example short.

Imagine that you wrote a whole lot of functions to give factorial values:

int f1() {return 1;}
int f2() {return 1*2;}
int f3() {return 1*2*3;}
int f4() {return 1*2*3*4;}
int f5() {return 1*2*3*4*5;}

and so on.

But then you see a lot of code is in common, so you rewrite to make use of the earlier functions in the later ones:

int f1() {return 1;}
int f2() {return f1()*2;}
int f3() {return f2()*3;}
int f4() {return f3()*4;}
int f5() {return f4()*5;}

and so on.

When you evaluate f5, it calls f4, which calls f3, etc.

Then you can see that f2, f3, f4, f5 are really all the same function, just with different values being used in the multiply.

So they can be roughly rewritten as:

int f1() {return 1;}
int fn(int x) {return fn(x-1)*x;}

This is the heart of the recursion. But it doesn't work properly yet. The problem is that when fn is called, it just keeps calling itself forever. It needs a termination condition, so that it stops at f1. This is done by combining fn and f1:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}

And there is your recursive function. The 'if' stops it from going on forever, and the 'else' is the heart of the recursion.

When using recursion in practice, the approach is sometimes the opposite to this. Recursion is most useful when the problem is too complicated, and needs to be broken up into stages.

For example, if you were coding a chess game player, you want to examine all the possible moves and their consequences. This is difficult, because each move leads to many other moves, and so on. You can't just write a loop to search all the moves, because there are many branches ahead.

So instead of writing a hugely complicated function, you just assume that this 'all-the-following-moves()' function already exists. You write a function that merely evaluates the first move, then calls the pretend function to do the rest.

"for each possible current move, choose the best according to all-the-following-moves()"

Of course, the rules of chess don't change from move to move, so the simpler function you have written already encompasses the whole problem; instead of calling a pretend 'all-the-following-moves', the function just calls itself (recursion). Each invocation checks the current possible moves, then uses itself to check the second move, and so on.

That's an oversimplification: you have to find some way to end the recursion; in chess you have to alternate between the players; and you might need to reduce the number of possibilities or it will take too long. But it demonstrates how recursion can turn a complicated problem into a simpler one.

joeBuffer 08-12-2009 05:56 PM

I think I basically understand, I'll have to read some more. These posts have been helpful, but it's just this assembly example, sort of. I'll figure it out completely before reading more of this book, so it doesn't bother me. :)

RaptorX 08-12-2009 06:49 PM

Quote:

Originally Posted by neonsignal (Post 3640515)
So they can be roughly rewritten as:

int f1() {return 1;}
int fn(int x) {return fn(x-1)*x;}

This is the heart of the recursion. But it doesn't work properly yet. The problem is that when fn is called, it just keeps calling itself forever. It needs a termination condition, so that it stops at f1. This is done by combining fn and f1:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}

And there is your recursive function. The 'if' stops it from going on forever, and the 'else' is the heart of the recursion.

And this, my friend, was a quality post. :D

I would add to the whole topic that when you are tired things simply dont go through, you should try and stand up from the computer, take some air, eat something, and then come back and write everything up or talk out loud to help your brain to `just get it, damn it!!`...

Everybody can understand everything but the most important thing is to understand how YOUR brain understands things easier... do you get it?:cool:

joeBuffer 08-12-2009 07:18 PM

Okay, I have a more specific question. How does %eax end up with the right return value.
When you make a recursive call to the function, and make a recursive call to the function, and make a recursive call to the function, and then it ends, then the rest finish up. How does the proper return value end up in %eax? If %eax is used for pushing the argument to the stack AND used for holding the return value, how do both work?
How are the values built up to the return value?
The whole function at the end is like someone put it in a blender, to me.


Also, using Google and entering "recursion", then clicking on recursion when it asks "did you mean recursion" has helped me so far, but I'll have to use it some more. :D

RaptorX 08-12-2009 07:51 PM

Code:

cmpl $1, %eax      #If the number is 1, that is our base
                    #case, and we simply return (1 is
                    #already in %eax as the return value)
 je end_factorial
 decl %eax          #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial


I guess there is the answer.

recursion is basically doing the same over and over again UNTIL you reach a specific condition [or that is one of the ways of using recursion].

In this case you are decreasing the value of %eax over and over again with the factorial function UNTIL it reaches 1. Each time you decrease it you perform a specific task OVER AND OVER. That is recursion in a very general way.

So, we get !5, we pass that number to our function, which then checks if 5==1, not true, then decrease that number, which makes 4, and do all over again. Hence I pointed out that
everything is explained right here:

Quote:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}
Look closely. The function "fn" says, IF x==1, then exit. Thats the condition to go out of the loop, and while x != 1 then you gonna (5-1 * 4) OVER AND OVER AND OVER, you keep calling the function to make sure to test if x == 1.

The answer IS there you just have to make your brain see it. Talk the function out loud, write the output of the program like:

fn (int 5) { if (5 == 1) return 1; else return fn(5-1)*5;}

note that the return is then:

fn (int 4) { if (4 == 1) return 1; else return fn (4-1)*5;}
fn (int 3) { if (3 == 1) return 1; else return fn (3-1)*5;}

and so on...

Dont forget the multiplication at the end of the function... note that the multiplication will happen at the end because it is NESTED..

By writing it or talking it maybe you get the idea of what is it doing... it should be the same with the original code that you posted, probably the comments are making it difficult for you to see it.

neonsignal 08-12-2009 08:20 PM

Quote:

If %eax is used for pushing the argument to the stack AND used for holding the return value, how do both work?
Ah, but it isn't used for both at the same time. It is used for the argument on the way in, and for the answer on the way out.

Once you reach the bottom, the values (5, 4, 3, 2, 1) have all been pushed on to the stack by the 'pushl %eax' before the recursive call to factorial.

On the way out, eax can no longer be used to get the parameter (because it has been overwritten with the working result). Instead, the parameter is grabbed from the stack and put into ebx by the 'movl 8(%ebp), %ebx' following the recursive call to factorial.

It might have been clearer if they had used different registers for the parameter and for the result (especially the termination value 1, which relies on the trick that the parameter is the answer, so they don't bother explicitly setting eax).

joeBuffer 08-12-2009 08:50 PM

:D thank you :D

Quote:

On the way out, eax can no longer be used to get the parameter (because it has been overwritten with the working result). Instead, the parameter is grabbed from the stack and put into ebx by the 'movl 8(%ebp), %ebx' following the recursive call to factorial.
This is what I completely overlooked. Like I said, I was sitting here looking at it, and it got to a point where it was like someone hit the button on a blender. That's exactly what I was missing, for some reason. :D

joeBuffer 08-12-2009 09:04 PM

One last tiny question, and I'm sure I could get this by reading it maybe ... but just in case:
I'm still a little thrown off ... in _start, before the first call to factorial, why only one addl $4, %esp after all that?
The rest of them don't clear the arguments from the stack...? I understand how it's working now, much better ... I'm just not sure I understand this quite yet.
This is just the first book I've ever read on assembly, and I'm still getting used to it, and this example really threw me off, I was learning a lot and really understanding things well up until this.

Code:

movl %ebp, %esp
popl %ebp
ret

what about clearing the stack of the argument?
maybe I'm still confused. :cry:

neonsignal 08-12-2009 09:19 PM

Normally you would fix up the stack pointer at the end of each function by using the frame pointer in bp. The main factorial code does this at the end:

Code:

movl %ebp, %esp
In the initial function, they save a few instructions by not using a frame pointer, and just resetting the stack pointer directly (effectively a pop)

Code:

addl $4, %esp

joeBuffer 08-12-2009 09:34 PM

Now, the most obvious question I could possibly ask.
How do the values of ALL of the parameters to ALL of the recursive calls get combined into one return value?
Then, where do all of the parameters passed in recursively go, before you get back to _start and addl $4, %esp?

neonsignal 08-12-2009 09:41 PM

Sorry, perhaps that wasn't very clear. Each time you come back up a level, you are throwing away the parameter from that level

Code:

movl %ebp, %esp
They don't all get combined at once. Each level multiplies the parameter into the result, so the result is 'accumulated' in eax.

movl 8(%ebp), %ebx
imull %ebx, %eax

So the stack will go through the following stages:
5
5 4
5 4 3
5 4 3 2
5 4 3 2 1 (result = 1)
5 4 3 2 (result = 1*2)
5 4 3 (result = 1*2*3)
5 4 (result = 1*2*3*4)
5 (result = 1*2*3*4*5

joeBuffer 08-12-2009 09:44 PM

Isn't it happening in the opposite direction, then?
Wouldn't it call the factorial function recursively, until the parameter was 1, then 1 is in %eax, then %ebx is multiplied by that %eax in the factorial function with the parameter of 2, then %ebx is multiplied by that %ebx in the factorial function with the parameter of 3, etc.?
It isn't like an actual factorial, 4 * 3 * 2 * 1,
it ends up being 1 * 2 * 3 * 4?

neonsignal 08-12-2009 09:48 PM

Yes, it is happening in the opposite way to the way you would typically express a factorial. Fortunately multiply operations are commutative (meaning you can swap the order and get the same result)!

They are also associative, which means you can also do
5 * (4 * (3 * (2 * (1)))) and get the same result.

So there are several ways to calculate the answer.

Interestingly, this is not true of all other mathematical objects. The chess game example I gave is one where you would have to be more careful about doing things in the correct order when recursing.

joeBuffer 08-12-2009 09:49 PM

I'm sorry to drag this out like this, but I'm very thoroughly under this impression:

the way the stack is for the function, is this:
the argument
the return address
old %ebp <- ebp

When the kaleidoscope of functions here come to an end, this happens:
Code:

movl %ebp, %esp
popl %ebp
ret

for every one.
Every one of them has "the argument" at the highest address in the stack.
then it's this:
Code:

movl %ebp, %esp:
    the argument
    the return address
    old %ebp <- %esp
pop %ebp:
    the argument
    the return address
ret:
    the argument (since ret pops the return address)

This happens for EVERY call to the function, then at the end of ALL of these calls, you use:
addl $4, %esp

So after all those recursive calls to the factorial function, you clear the stack of one argument. The argument for each individual function is not cleared in the end_factorial code. Where did they go?

joeBuffer 08-12-2009 09:51 PM

Thanks for the additional information ... I did know that, though. I know about the commutative and associative and distributive properties, etc. I'm just not really advanced in algebra.
Thanks for the additional information, though.

neonsignal 08-12-2009 10:06 PM

Quote:

The argument for each individual function is not cleared in the end_factorial code. Where did they go?
It is cleared each time by the copying of 'ebp' into 'esp' (or, not so much cleared as skipping back over it). 'esp' is the actual stack pointer, so overwriting it causes arguments to be lost from the stack. Actually, all a 'pop' does too is to copy something from the stack and then adjust the stack pointer.

So adjusting (or setting) the stack pointer is the same as one or more pops, while ignoring what was on the stack. Effectively the end_factorial code does simply add 4 to the stack pointer (since the value in ebp is esp+4).

In older architectures, there was no frame pointer, and the stack had to be fixed up explicitly. There are big advantages to having a frame pointer: it makes it easier to access parameters from a known point; and it makes it trivial to restore the stack pointer at the end.

In reality, everything is still in the stack memory, but all that matters is where the stack pointer is pointing to. The next time you do a function call, the old information will get overwritten.

joeBuffer 08-12-2009 10:15 PM

Quote:

They don't all get combined at once. Each level multiplies the parameter into the result, so the result is 'accumulated' in eax.

movl 8(%ebp), %ebx
imull %ebx, %eax
This and the other stuff in this post, and the one I thanked you for before, is what I was really *missing*, where I thought I had no idea what I was looking at.
-----

In this book, it's this way through the whole book:
push the parameter
call the function
push %ebp
mov %esp, %ebp
then the local variables or whatever go here.

this would leave the parameter untouched, if you use:
mov %ebp, %esp
pop %ebp
ret

it changes the stack from:
parameter
return address
old %ebp <- %ebp
local variables, or whatever

to:
parameter

and I've had a good understanding of the stack pointer ... but in this book, it is always mov %ebp, %esp and pop %ebp goes back to where the return address is, then you use ret, then use the addl $4, %esp(or whatever the case may be) to clear the parameter from the calling function. In this case, it's a single addl $4, %esp, after the recursive function having the parameters pushed and not cleared repeatedly. It appears.

Code:

movl 8(%ebp), %eax #This moves the first argument to %eax
                  #4(%ebp) holds the return address, and
                  #8(%ebp) holds the first parameter


joeBuffer 08-12-2009 10:33 PM

I've just been thinking that since I have been learning a lot and had very good comprehension of the rest of the examples in this book, so far, maybe I should just read the rest of the book, and worry about recursive functions later, or when I absolutely have to. I don't think there are any other recursive functions in this book, and it has a lot of information in it.

neonsignal 08-12-2009 10:34 PM

Yeah, I can see that it could be confusing. They haven't cleaned up the stack directly after the call to factorial, because it is taken care of in the end code. It is a common optimization; it doesn't matter how much you push on the stack in the middle of the function, the end code will take care of it.

Interestingly, compilation of some other high level languages had the opposite convention; it was the callee that cleaned up the stack, rather than the caller. The nature of the C language (particular in allowing variable numbers of arguments) has tended to favor the caller cleaning up the stack. There are also some advantages in optimization, since the caller knows what the subsequent code is, so the cleanup can be delayed as much as possible).

But I agree - if you already understand the recursive process in C, you won't learn much more by being able to follow every line of the assembler. Understanding recursion is much more important than being able to follow a few assembler optimizations.

joeBuffer 08-12-2009 10:37 PM

Well, thank you for your time and help, but I still don't really see how the parameters are being cleaned up in the factorial function or afterward ... can you give a brief description? It can be a little technical, if I don't really understand I'll just look it up ... but I've been able to understand what's in this book up until this example very easily ... I know it doesn't seem like it, but I guess it's just this example.
The examples of C recursion are easy for me to understand.

neonsignal 08-12-2009 10:57 PM

Code:

1 pushl %ebp
2 movl %esp, %ebp
...
3 pushl %eax
4 call factorial
...
5 movl %ebp, %esp
6 popl %ebp
7 ret

Okay, this is the relevant bits of the code. Let us say that esp starts at the value 42.

0. the call to the function pushes the return address. esp is now 38.
1. ebp is saved on the stack. esp is now 34.
2. esp is copied to ebp. both are 34.
3. eax is pushed. esp is now 30.
4. factorial is called. Let us assume for the sake of the argument that it has fixed up the stack at the end. so esp is still 30.
5. ebp is moved to esp. this sets esp to 34 (see step 3)
6. ebp is restored to the calling frame pointer. esp is now 38.
7. the function returns by popping the return address to the program counter. esp is now 42 (back to the original point).

Notice that even if they added 4 to esp after the recursive call to factorial, it would have made no difference, because ebp was used to overwrite esp in step 5 anyway.

Even if the recursive call to factorial totally messed up the stack (it can't, or its return would have failed), the stack would still be fixed up by step 5.

joeBuffer 08-12-2009 11:10 PM

I see. It's just that the factorial function uses the stack and the function call in a different way than _start and pretty much all the other examples in this book, other than this one.
Thanks. This was very helpful.
I know a few others in this book, they use the stack and things differently, but for some reason this example really got to me. It was very annoying, and seemed simple at first.

joeBuffer 08-13-2009 01:20 AM

I've written it out again, and gone through it step by step and understand every little part of it, now. Thanks for your help, it really did point things out that I didn't think of.
C recursive programs are so much simpler. :D
I was right about the arguments, though ... it doesn't pushl $4, %esp for the inner functions, and it's not just the pushl %ebp, %esp and pop %ebp, either. It's just taken care of because of the way it's structured ... it's all just taken back to where it starts in _start, and then the pushl $4, %esp is used to finished up with the stack and that first pushed argument. Now it's as straightforward as I thought it was when I first saw it. :D

joeBuffer 08-16-2009 11:36 PM

I was going to add, also, that this book did end up being a good introductory book. It's easy to follow (mostly), and it's full of information. :)


All times are GMT -5. The time now is 04:01 AM.