How do I write an x86 assembly function that recursivly calculates exp(2,n) ie 2^n using the stack to pass n.
Please note the code below is stuck in a loop only run in your debugger, plus is is not doing the require calculation yet i am still trying to get the stack working as it iterates through the formula.
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
First of all : why did you call the function factorial ? Did you base the code on some recursive function that calculates the factorial ? You didn't change much ... Are you trying to implement a factorial function ?
I would suggest you first write down the algorithm you want to use in pseudo code. How would you approach calculating 2^n recursively ?
>> ok will do.
Post the algorithm you intend to use here, and I will have a look at it :)
>> yes i have found some similar programs and trying to modify them.
That's not the best idea. You should write the algorithm first, and then try to implement that specific algorithm. You can use other recursion code as a guideline for how recursion works, but don't try to modify existing code that is unrelated. You'll only make it harder on yourself, and will probably be left with something that doesn't work, because it's a mix of two different algorithms.
>> However my main issue has been using the stack.
What issue do you have with that.
>> isnt n the number that is used as the power of 2?
Yes.
Take a look at the iterative algorithm :
>> while n > 0
>> a = a * 2
>> n = n - 1
>> loop
You used n as the number of iterations (which is correct). When transforming the iterative algorithm to a recursive algorithm, n becomes the number of times that the function is called recursively.
>> i am trying to work it out
If you want, you can show your progress here. As well as your doubts, questions, etc. I'm here to help you :)
i got it working in c.
now the real challenge convert that to assembly
#include <iostream.h>
#include <ctype.h>
#include <stdlib.h>
int power(int x, int n);
void main()
{
int target;
cout << "enter desired power";
cin >> target;
for (int n = 0; n < (target+1); n++)
cout << "2 to the power " << n << " is " << power(2, n) << endl;
//return 0;
}
int power(int x, int n)
{
if (n < 0)
{ cout << "Illegal argument to power.\n";
exit(1);
}
if (n > 0)
return(power(x,n-1) * x);
else //n=0
return(1);
}
Did you write this yourself ?
It's not valid C or C++, and it was written for generic powers, not just powers of 2.
Anyway, the algorithm is good. So, you can just translate it to assembler code one line at a time. Do just the power function for now, and leave out the error checking. Just the core algorithm.
>> i am still lost but i feel abit closer.
Good. I'll guide you along until you get there :)
So, you have an algorithm now. Try to start putting that in assembler code like I suggested in my previous post.
You can use the factorial code you posted earlier as a guideline.
Can you post the assignment ? So that I get a better idea of what the intent is ?
sorry i got distracted by
>>You can use the factorial code you posted earlier as a guideline
here are the questions
Question 1
Write an assembly language function that uses recursion to produce exp(2,n) i.e. . Pass the parameter on the stack and return the result in an appropriate register. Make sure the function conforms to the standard.
Hint : Try writing a C function to do it. Then convert the logic of the C function into assembly language. The recursive equation for exp(2,n) are
exp(2,n) = exp(2,n-1)*2 n>0
exp(2,0) = 1
Question 2
Modify your code for reading in the number n, so that it is now a function according to the standards illustrated in the notes. Call the function readnum. Type in the example writenum function and test to see that it works with readnum and writenum. Create a program that reads in a number and writes out 2 to the power of the number read in.
; Standardisation Example 2
;
; This code shows how to set out standardised
; function calls suitable for use with C and any
; language that passes parameters by value.
.
.
.
call readnum ; Read in a number (to ax)
mov [bp-2], ax ; Save value on stack
call newline ; Start on a new line
mov ax, [bp-2] ; Get value off the stack
push ax ; Setup first (and only) parameter
call writenum ; Write the number out
add sp, 2 ; Clean up the stack (2 bytes used)
.
.
.
writenum: push bp ; Function entry sequence
mov bp, sp
sub sp, 2 ; Leave space for a local variable
mov ax, [bp+4] ; Get first argument off the stack
mov dx, 0 ; Clear high order 16 bits
mov bx, 10 ; Store 10 for divide operation
div bx ; Divide dx/ax by bx (10)
mov [bp-2], dx ; Store number to display on stack
cmp ax, 0 ; Is there anything left to do?
je writenum1 ; Jump if nothing left
push ax ; Setup first (and only) parameter
call writenum ; Write the number out
add sp, 2 ; Clean up the stack (2 bytes used)
writenum1: mov dx, [bp-2] ; Get number to display off stack
add dl, '0' ; Convert binary number to ASCII
mov ah, 02h ; Display character service routine
int 21h ; Call BDOS
mov sp, bp ; Function exit sequence
pop bp
ret
.
.
.
; Standardisation Example 1
;
; This code shows how to set out standardised
; assembler for the start up and the shut down
; processing.
.model small
.stack 1000h
.data ;Start of data segment
.code ;Start of code segment
start: mov ax, @data ; Get the data segment address
mov ds, ax ; Set the data segment
call main ; Start program execution
exit: mov ah, 4ch ; Exit process service routine
int 21h ; Call BDOS
main: push bp ; Function entry sequence
mov bp, sp
.
. ; Body of main function
.
mov sp, bp ; Function exit sequence
pop bp
ret
.
. ; Rest of assembler program
.
end start ; Last line of code
; Start execution at star
i dont understand how to get the variables in [bp-4] etc in snippet below.
Let us first look at calling a function, with parameters, from some point in a program. There is a standard way of doing this, and the method shown below is compatible with the C programming language convention. Consider the following C code:
.
.
.
num = func(a, b); /* call func */
.
.
.
The assembly code translation of this would look something like the following:
mov [bp-4], .. ; Move parameter 'a' in the stack.
mov [bp-6], .. ; Move parameter 'b' in the stack.
.
.
.
mov ax, [bp-4] ; Setup first parameter, in local variable, a.
push ax ; Push first parameter onto the stack.
mov ax, [bp-6] ; Setup second parameter, in local variable, b.
push ax ; Push second parameter onto the stack.
call _func ; Call the function, func.
add sp, 4 ; On return, clean up the stack.
mov [bp-2], ax ; Store value in local variable, num.
.
.
.
>> sorry i got distracted by
>>
>> >>You can use the factorial code you posted earlier as a guideline
That was just a suggestion to get you started :)
>> i dont understand how to get the variables in [bp-4] etc in snippet below.
To put a value on the stack, you usually push it on the stack, like here :
push ax ; Push first parameter onto the stack.
So, you put the value you want to put on the stack in ax, and then you push ax on the stack.
Take a look at the factorial code you posted earlier for example :
push 4
call factorial
So, 4 is pushed on the stack, and then the factorial function is called. This is equivalent to :
factorial(4);
Inside the factorial function, you get the parameter like this :
mov ax,[bp+8]
bp contains a copy of the stack pointer (sp). [bp+8] is the value that is 8 bytes before the top of the stack - ie. the location of the parameter. The instruction above will take that value (4 in this case), and put it in ax.
From the PDF you posted, it IS for a 16bit architecture. Are you sure you are using the correct assembler tool ? What version of borland turbo assembler are you using ?
>> not sure have not tried
Please do :)
Btw, the PDF is very informative, and explains everything with enough detail. Did you read it ?
>> when then function looped or called itself again the stach had "#exp#_exp" in it
That looks like a stack trace (ie. function calls), not the complete contents of the stack. I don't know your debugger, but you should have the option to get a stack dump, and you should see the value 4 on there - since you pushed it on the stack.
i found it CPU has the registers to see clips
clip1 first push
clip2 the spot you wanted to see
clip1
clip2
clip2
[bp-4] and [bp-6] are used as local function variables (on the stack).
Remember that the stack grows from high to low memory addresses. So, -4 means 4 bytes UP in the stack.
Also remember that bp is the current frame pointer - it points to the start of the current stack frame.
So, [bp-4] is 4 bytes after the start of the current stack frame.
>> why
>> please explain.
As I said : -4 means that you write 4 bytes UP in the stack. If the current stack pointer is at bp, then bp-4 is ABOVE the top of the stack, so not visible when you show the stack.
data <--- bp + 4 |
data <--- bp + 2 | stack grows in this direction
data <--- bp \/
data <--- bp - 2
data <--- bp - 4
If the top of the stack is at bp for example, then the values at bp-2 and bp-4 are NOT on the stack - they are ABOVE the stack.
If you want to use the stack as local storage, you will have to increment the stack pointer by the required amount of bytes first. By using :
add sp, 4
for example to add 4 bytes to the stack (and let sp point to bp-4)
Business Accounts
Answer for Membership
by: Fang1964Posted on 2008-05-11 at 19:03:28ID: 21544269
Help will be much appreciated.