Please help with Stack Operations

Go To Last Post
116 posts / 0 new

Pages

Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi I was wondering if anyone could help me with My university assignment. In this part we are required to write a program to calculate the tower of Hanoi number using a for-loop within a subroutine. The C-code is provided.

typedef unsigned char byte; // define 8-bit variable type

int main(void) {
byte result, num = 6;
for( ;; ) {
// Calculate the result of the Tower of Hanoi
result = hanoi(num);
}
}

byte hanoi(byte n){
// calculate 2^n-1 without the pow() function
byte ret = 1;
for(byte i = 1; i <= n; i++) {
ret *= 2;
}
ret--;
return ret;
}

I need to implement this code using assembler language, and using the stack.

I started of with the basic

.include "m8515def.inc" ; include the ATMEGA8515(L) definitions file
.def NUM = r16 ; use this register to store "˜num'
.def RESULT = r17 ; use this register to store "˜result'
.def temp = r18
RESET:
LDI temp, high (RAMEND)
OUT SPH, temp
LDI temp, low (RAMEND)
OUT SPL, temp

This is where im now stuck, as after numersous hours of research, I am still not sure exactly how to implement the task at hand.

The specifications are that

LOOP:
ldi num, 0x06 ; this is our start number

*** setup passing parameters on the stack ***

rcall HANOI

*** capture the return value from the stack ***

rjmp LOOP ; Jump back to start

HANOI:
*** Add hanoi calculation ***
ret
.

I have tried multiple things such as PUSH NUM, PUSH RESULT, but my lecture notes, as well as other material confuses me, such as why is push used again in the function, and why are there different variables sometimes.

I also know i have to use LDD and also LSL to multiply by 2, but i just dont get at all how to work within a stack and passing parameters through the stack, as the previous labs before this was simple mathematical equations(ADD, SUB, EOR, etc, and now all of a sudden we get this.)

P.s I also tried using Dissasmebler in AVR Gcc but all it gives me is an infinite loop in the for loop section, as well as me needing to use LDD which was not present.

Any help would be appreciated.

Kindest Regards

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I am still not sure exactly how to implement the task at hand.

Why not look at what the C generates?

But as I understand the tower of hanoi problem it's really (like factorial) just a good example of using recursion - yet your C solution doesn't use recursion?

The very fact your thread title mentions "stack operations" also suggests to me that the intention here was that you would use recursion.

So I'd start by googling "hanoi C recursion". Then run that algorithmic code through your C compiler and use the Asm that it generates as the starting point for your solution.

YMMV.

EDIT Google says:

http://www.daniweb.com/software-...
http://stackoverflow.com/questio...
http://www.cs.cmu.edu/~cburch/su...
http://programminggeeks.com/c-co...

As you read those I think you may spot a pattern developing ;-)

(oh dear god I just realised there's an implied pun in what I just said!)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This code does *not* solve the hanoi puzzle. All it does is to calculate the number of moves needed to solve the hanoi puzzle if all movements are done in an optimal way. Then the number is 2^n-1 if n is the number of plates to move. So, to calc. the number of moves, no recursion is necessary, and in fact i would forget any notion of the hanoi problem to solve this assignment. hanoi() is just an ordinary function expecting an input argument, and returning a result.

If the shifts inside the hanoi function are something you have problems with at the moment, just replace everything inside hanoi() and just add 1 to the input argument. If that works, implement the original calculations within hanoi().

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

the tower of Hanoi

Wow--takes me back to the 80's when we would test the speed of PCs and compare C compilers using Tower of Hanoi.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You'll probably get more meaningful disassembler output if you declare result as volatile.

C: i = "told you so";

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How sad am I - I just went to take a photo of a "tower of hanoi" I made in "Design and Technology" ("metalwork" to everyone else!) that I made aged 14 (~35 years ago). I even knew where it was until about 2 months ago - then it got "tidied" which presumably means I may never see it again? It was really cool - the "towers" were turned brass and the "counters" were turned on a lathe from green perspex while the platforms were thermally moulded red perspex. I learned a lot about lathes and working with perspex making it.

I'm not sure you get the same sense of satisfaction making a C program do the same thing? (but it sure helps to play the real thing and understand the "procedure" to solve it (7 counters in mine) to then understand how a virtual solution works).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Could the stack use be strictly for passing an argument from the C code to the assembly subroutine?
Kinda misleading assignment since there are no for-loops in assembly.

OP, start by declaring your variables and create the loop structure.
You'll need to use directives like .equ and .def
Get familiar with opcodes that do increment, decrement, and multiply.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I am half with Cliff, and half with your teacher taking the p?ss.

e.g. compile the C function and examine the generated ASM. See if you can 'improve' on it. Substitute the register numbers that you are 'supposed' to use.

e.g. can you see any recursion? can you see any stack operations? What do they do?

OTOH, if you are brave: Understand the algorithm from the C statements.
1. Lookup the ASM opcodes available for the AVR.
2. write the subroutine directly in the assembly language. Document it.

Your teacher may want you to use the second approach.
If you use Cliff's approach, you could do the assignment in any MCU family you can dream of. And possibly never even consult an ASM manual for that MCU !!

I know which student I would prefer.
You know your teacher.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Kinda misleading assignment

I'd be astonished if the teacher's intention here were not that the student would learn/understand recursion doing this.

Making them do it in Asm rather than C is a bit rich though. I suppose it does get you "closer" to the actual stack usage than implied by the use of automatics in C code though?

If this is about recursion I hope the teacher emphasises the point that it's seldom a great solution in a RAM limited microcontroller for any "problem" to be solved simply due to the difficulty in accurately gauging stack RAM usage.

(thinks: do compilers that do runtime RAM estimations get on OK with recursion?)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I'd be astonished if the teacher's intention here were not that the student would learn/understand recursion doing this.

Again, this code does *not* solve the hanoi puzzle, it merely calculates the minimum number of necessary steps. And this calculation for sure does not need recursion!

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Again, this code does *not* solve the hanoi puzzle,

That, presumably is OP's misunderstanding though?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

No. I expect that the teacher has deliberately muddied the waters.

At the end of the day, the student that understands what she is doing is in a different league to the one that pasted stuff from the internet.

I guess that you could just write out the Z80 instructions without blinking.
Likewise Danni in 8051.
Or I could in 6502.
But that requires my 'second' approach. e.g. reading the algorithm.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Kinda misleading assignment since there are no for-loops in assembly.
Then again, there is no need for a for loop in C at all. The function could simply be:

rbyte hanoi(byte n){ 
// calculate 2^n-1 without the pow() function 
    return (1<<n) - 1; 
} 

Of course, in assembly you would still need a loop.

Quote:
I have tried multiple things such as PUSH NUM, PUSH RESULT
Surely you would need to use POP somewhere too.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Then if really is just about calculating some power of 2 it's surely as easy as something like:

.include "m8515def.inc" ; include the ATMEGA8515(L) definitions file
.def NUM = r16 ; use this register to store ‘num’
.def RESULT = r17 ; use this register to store ‘result’
.def temp = r18
RESET:
  LDI temp, high (RAMEND)
  OUT SPH, temp
  LDI temp, low (RAMEND)
  OUT SPL, temp 
  LDI NUM, 6
  RCALL HANOI ; returns with RESULT
LOOP:
  RJMP LOOP

HANOI:
  LDI RESULT, 1
  LDI temp,   1      ; "temp" masquerading as "i"
FOR_LOOP:
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  RET

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just think how nicely it works in Z80 or 8051 (or many other families).

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Since the subject title involves STACK operation my take on this is that the exercise is about PUSH and POP instructions and their use in assembler language.
Any PUSH of a register need to be balanced by a POP to get the value of the pushed register back.
The last pushed register need to be popped first.
Think of the stack as a pile of paper.
The paper you put on top is the paper you remove first.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
(thinks: do compilers that do runtime RAM estimations get on OK with recursion?)
Generally not and that is one of the limitations that was mentioned in earlier discussions. I suppose that if the number of levels of recursion could be determined at compile time it could be handled but that would be an extremely small part of the universe of cases.

Don Kinzer
ZBasic Microcontrollers
http://www.zbasic.net

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Lennart wrote:
Since the subject title involves STACK operation my take on this is that the exercise is about PUSH and POP instructions and their use in assembler language.
Any PUSH of a register need to be balanced by a POP to get the value of the pushed register back.
The last pushed register need to be popped first.
Think of the stack as a pile of paper.
The paper you put on top is the paper you remove first.

Hi guys thank you for your responses, just reading it all helps understand more about Avrs.

SImply put yes the task is to calculate the number of turns it takes, in this case 6 disks are used, so the result should be 63. The teacher wants us to use pop and push, as we are meant to pass the paramters Via the stack, so then from what i learned you dont use simple registers anymore, you need to use push and dpop, but thats what i dont get, say I push Num , then start my function do i then within the function pop NUM out, our POP another variable name out, or doesn't it matter as POP is just what pops out the variable from the stack.

Last Edited: Wed. Mar 28, 2012 - 12:05 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Also recursion is the second task, once i complete this exersice i relace the above hanoi result calculation with one that uses recursion.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
say I push Num , then start my function do i then within the function pop NUM out, our POP another variable name out, or doesn't it matter as POP is just what pops out the variable from the stack.

When you do a RCALL instruction to that function the return address is loaded to the stack.
This means it is laid "on top" in stack and will prevent you from getting access to anything already in stack, i.e. a PUSHed register value.
To be able to retrieve that value (using POP) you first need to RET from your subroutine which will load the return addres to PC and make the stack pointer point to the previously pushed register value which you now can retrieve using POP.
If you have POPped the register value before RETurning from subroutine your return address will be incorrect and program will crash.
Remember that you as a programmer are responsible to keep the stack balanced, every PUSH need a POP, every RCALL need a RET.
Do not mix them.
If you PUSH several registers you need to POP them in reverse order, think of the stack of paper.
If you fail to keep the stack balanced your program will crash.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is the assembly code I did, thanks to some help from here.

.include "m8515def.inc" ; include the ATMEGA8515(L) definitions file
.def NUM = r16 ; use this register to store ‘num’
.def RESULT = r17 ; use this register to store ‘result’
.def temp = r18
RESET:
  LDI temp, high (RAMEND)
  OUT SPH, temp
  LDI temp, low (RAMEND)
  OUT SPL, temp
  LDI NUM, $6
  PUSH NUM
  RCALL HANOI ; returns with RESULT
  POP RESULT
  OUT PORTA, RESULT
LOOP:
  RJMP LOOP

HANOI:
  POP NUM
  LDI RESULT, $1
  LDI temp,   $1      ; "temp" masquerading as "i"
FOR_LOOP:
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  PUSH RESULT
  RET

I know its still wrong, and im guessing the main problem is that CP temp, NUM is comparing to NUM which is not a register anymore.

Can someone please elaborate exactly what is wrong, and how to fix it. I know I need to use LDD here as I am working within the stack, I am just not sure how to use LDD here.

P.s

Changing the code here

.include "m8515def.inc" ; include the ATMEGA8515(L) definitions file
.def NUM = r16 ; use this register to store ‘num’
.def RESULT = r17 ; use this register to store ‘result’
.def temp = r18
RESET:
  LDI temp, high (RAMEND)
  OUT SPH, temp
  LDI temp, low (RAMEND)
  OUT SPL, temp
  LDI NUM, $6
  PUSH NUM
  RCALL HANOI ; returns with RESULT
  POP RESULT
  OUT PORTA, RESULT
LOOP:
  RJMP LOOP

HANOI:
  LDI RESULT, $1
  LDI temp,   $1      ; "temp" masquerading as "i"
FOR_LOOP:
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  PUSH RESULT
  RET

causes a comparison but RET makes it go back to the stack initialization.

I am really confusing myself lol.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Your "PUSH RESULT" places a value on the stack, and the next RET uses that value. Not in a good way.

You can handle this a couple different ways. You could return the result in a register. If you want to use the stack, then you can POP the return address, PUSH the result, and PUSH the return address back. That way RET gets an address it needs.

C: i = "told you so";

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What exactly do you mean by pop the return address.

Sorry im still trying to learn AVRs, as this is my first subject we actually touched anything to do with assembly language.

Can somebody please show me quick versions of the code edits I need to do to make the program work.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

When the RCALL is executed, the return address is pushed onto the stack. When the RET occurs that address had better be on the top of the stack or your processor will go into the weeds.

So, if you want to return the result on the stack you had better get it under the return address.

C: i = "told you so";

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So i have to ensure I pop out anything I pushed in before I RET?

My other question is , what exactly is wrong in my Hanoi function, how to I manipulate the stack values through LDD calls, if I want to implement the above FOR loop to calculate the number of turns for the Hanoi puzzle.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think the concept of a stack can be understood best if you think how exactly a subroutine call and the correspondig RET is working. Ask yourself the question "How does the called function actually know where to RETurn to?" It can be called from many locations in your program. The solution is: it cannot know where it has been called. It simply executes the RET instruction as the very last instruction. This RET takes the topmost 16bit value from the stack and stores that value in the program counter, which implies that the next instruction that is executed is the one at the address (=16 bit value) that just got fetched (POPped) from the stack during the execution of the RET.

So, the subroutines hope is that the topmost value on the stack is the correct address to continue after the subroutine has finished. How can that be? Simple: the RCALL instruction being executed to actually call the subroutine just stuffs the address of the next instruction after that RCALL onto the stack (PUSH) automatically. In combining the inner working of both the RCALL and the RET instruction, you see that subroutine calling and returning just works perfectly together - if and only if noone else modifies the stack in between!!! So, if you are POPping something off the stack inside your subroutine, the first 16 bits will always be the return address. This POPping in itself is nothing to worry about, as long as you PUSH the value back before you actually execute the RET instruction. So, to pass parameters via the stack, you could easily POP the return address from the stack (AND SAVE IT!), pop your parameter values, and push the return address back again onto the stack to be prepared for the RET.

Now to the PUSH/POP instructions themselves: you can only PUSH/POP to and from registers. What register you actually use, is completely up to you. The important thing here is that you ALWAYS access the topmost location of the stack, either reading or writing it. This is important: the stack is a memory region where you ONLY can access the topmost location. Depending on the operation, after the access the address of the topmost location will be adjusted by the PUSH/POP/RCALL/RET instruction. (More advanced programmers of course will also access the stack via address arithmetics and such, you will see this if you look at the code generated by a compiler, but let's forget this until you fully understood the basic concept of the stack).

With these explanations, take a pencil and a sheet of paper, or even play with little cards literally being stacked on a table, and imagine you're the AVR CPU executing RCALLs, RETs, PUSHes and POPs. Then try to design a sequence of steps needed to pass parameters from a main program into a called subroutine - and back!

Have fun - and get it right: this is THE basic concept of almost any CPU architecture on the planet (not knowing how the vogons designed their computers)

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I do mostly understand all that, first in first served and reverse. I really dont get the advanced stuff within the function call such LDD calls.

If anyone could provide me with an example of how I would implement that in my code, or a similar problem I could work with for my own work.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
  LDI NUM, $6
  PUSH NUM
  RCALL HANOI ; returns with RESULT
  POP RESULT
  OUT PORTA, RESULT
LOOP:
  RJMP LOOP

HANOI:
  LDI RESULT, $1
  LDI temp,   $1      ; "temp" masquerading as "i"
FOR_LOOP:
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  PUSH RESULT
  RET

You have got mismatched PUSH and POP here.

I think that this PUSH, POP stuff has deliberately muddied the waters.
There are two methods of passing arguments to a subroutine:
1. pass the values in registers (or memory locations)
2. pass the values on the stack.

Likewise, you can retrieve the results from registers or stack.

IMHO, registers are the easiest and safest way with ASM subroutines. Hence you:

     ldi  NUM,6
     call hanoi     ; leaves answer in RESULT

This is all very well when you have a straightforward call.
Q. What happens if the NUM and RESULT registers have already been used in some other part of your program?

A. you save the current contents, do your business, restore them afterwards. This is where PUSH and POP are useful.

This example preserves your 'argument' register:

     push NUM
     ldi  NUM,6
     call hanoi     ; leaves answer in RESULT
     pop  NUM

The stack passing method involves PUSHing arguments onto the stack, and the called subroutine reading the arguments from the stack. You generally use the Y register as a secondary stack pointer to the 'stack frame'.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I do mostly understand all that, first in first served
Well, actually the last in is first served in stack operations.
Quote:
I really dont get the advanced stuff within the function call such LDD calls.
Is it part of your assignment that you need to use LDD instruction?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes Part of my assignment is
1) Pass the parameters Via the stack
2) Use LDD instructions

And thank you David for the above help, I do understand a lot more then previously.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi, so can someone please help me with using LDD instructions and passing parameters via the stack, etc.

I tend to learn better from examples, can someone please show me some sample ways in code, or show me how I would implement the above task, through LDD.

To be clear, my assignment specifically states to use the stack entirely, and only the most minimal number of registers.

Regards.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The opcode manual contains this example code for LDD:

clr r29 ; Clear Y high byte
ldi r28,$60 ; Set Y low byte to $60
ld r0,Y+ ; Load r0 with data space loc. $60(Y post inc)
ld r1,Y ; Load r1 with data space loc. $61
ldi r28,$63 ; Set Y low byte to $63
ld r2,Y ; Load r2 with data space loc. $63 
ld r3,-Y ; Load r3 with data space loc. $62(Y pre dec)
ldd r4,Y+2 ; Load r4 with data space loc. $64

Does that not show most of what you need to know?

As for passing parms on the stack - with a single stack this is not a great way to pass parms on an AVR and C compilers only tend to resort to it when there are a huge number of parameters or they are variadic (a variable number of parameters) but the essence of it (in psuedo code not necessarily real code) is:

ldi somereg, parm1
push somereg
ldi somereg, parm2
push somereg
ldi somereg, parm3
push somereg
call three_parm_function

..

three_parm_function:
  in r28, SPL
  in r29, SPH ; so "Y" now contains SP
;
; at this point the two bytes at Y+0 and Y+1 are the return address
;
; you could do something like this to pick up the 3 parms
;
  ldd workreg1, y+2
  ldd workreg2, y+3
  ldd workreg3, y+4
;
; or how about this:
;
  adiw r29:28,2
  ldd workreg1, y+
  ldd workreg2, y+
  ldd workreg3, y

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
include "m8515def.inc" ; include the ATMEGA8515(L) definitions file
.def NUM = r16 ; use this register to store ‘num’
.def RESULT = r17 ; use this register to store ‘result’
.def temp = r18
RESET:
  LDI temp, high (RAMEND)
  OUT SPH, temp
  LDI temp, low (RAMEND)
  OUT SPL, temp
  
  
  LDI NUM, $6
  LDI RESULT,$1
  PUSH NUM
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  POP RESULT
  POP NUM
  OUT PORTA, RESULT
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 LDI temp, $1
 PUSH temp
 ldd NUM, y+3
 ldd RESULT, y+2
 ldd temp, y+1 ; "temp" masquerading as "i"
FOR_LOOP:
  
  
  
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  POP temp
 
  RET

Here is my new code, its still looping infinitely, Can someone please show me how to fix it, Result has to be the number of turns it will take.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Also can someone tell me what is the largest number that can be inputted into this program without the output overflowing? and How is ldd different to ld?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Have you not stepped through your code in the simulator? When you do so can you not see that number that you are poping in HANOI is not the one that you pushed earlier? And why are you pushing temp in HANOI? And how do you expect the result to get back to main when you never put the result back on the stack?

Quote:
its still looping infinitely
No it isn't, it is just looping more than you want it to.
Quote:
Also can someone tell me what is the largest number that can be inputted into this program without the output overflowing?
That depends on the number of bytes you leave for the result. If it is one byte, then the largest value it could hold is 255. It should be easy for you to figure out how big the input can be.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I thought by using the pointer LDD it automatically updates the value from the stack, so when i pop it in main its already the new value. And i did run it in simulator, i just dont know what to look for, besides registers and memory.

We were really not shown anything about stack operations and are expected to find out ourselves, thats why im trying to understand it.

Also with temp i thought to push it there just because its only used for the loop.

I really confused myself more now.

can someone please tell me how to
1)Use the parameters I pushed into the stack within my function, without any extra registers..
2) How do put the result back to stack.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

We were really not shown anything about stack operations and are expected to find out ourselves, thats why im trying to understand it.

Oh this is madness. Don't teachers get paid to teach any more?

You are expecting far too much from LDD. All it offers is a mechanism to load an AVR register via an "index register". So while:

LDS r24, 0x1234

will load R24 from memory address 0x1234 you need to do this with indexing:

LDI r28, 0x34
LDI r29, 0x12
LDD r24, Y

In this you load Y (a combination of R28 and R29) with the address 0x1234 then the LDD says "go to the location held in Y and pick up the byte there". The real advantage of LDD comes when you want to step through memory (like arrays in C) and do something like:

  LDI counter, 10
  LDI r28, 0x34
  LDI r29, 0x12
loop:
  LDD r24, Y+
  OUT PORTB, r24
  DEC counter
  BRNE loop

The advantage now is that Y starts at 0x1234 and the byte there is retrieved and output to PORTB but the Y+ means "during this opcode increment Y to the next location". So it moves to 0x1235 then 0x1236 and so on as the loop goes round and round.

So back to your code. I already told you how to get some parameters into a function using the stack then using Y as the "frame pointer" that points to the same place as SPL/SPH and LDD is then used to load those same bytes that were PUSHd before entry from the stack. If you want to put a result back then use the store version of LDD which is "ST Y, something" that would put a result back to where Y is "Pointing". When the function RETs the bytes that were initially PUSHd are still there and now modified by the use of ST so can finally be POPd back into result registers.

This really is very complex stuff and personally I think it is the wrong thing to be teaching a beginner in AVR Asm. I wonder if you have mis-interpreted what the tutor is asking? If I were you I'd ask your tutor to read this thread and confirm that you are heading in the right direction.

(while he's here maybe he could explain why I am teaching you this stuff and not him?!?)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I regard this as very complex ASM programming.

Something that you would never consider until you were very proficient in regular programming. e.g. passing arguments to subroutines, simple maths, saving and re-using registers.

You could even write complete applications in ASM without ever using complex tricks with stacks.

OTOH, reading some working ASM is a useful skill. e.g. tracing some code and watching how it works.

You can do this without being skilled at writing. Something like reading Shakespeare without being able to write a new play yourself.

I think your teacher is taking the p*ss.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Totally agree with Cliff and David that using LDD is quite complex and not something to expect a newbee to wrap his head around.
Have programmed AVR's for more than a decade and the times I felt the need to use LDD can be counted on the fingers.
I think compilers use LDD frequently but for humans it's not as attractive.

I.e looking at Cliff's last two code examples, why use LDD and not simply LD?.

LDI r28, 0x34
LDI r29, 0x12
LD  r24, Y 
  LDI counter, 10
  LDI r28, 0x34
  LDI r29, 0x12
loop:
  LD  r24, Y+
  OUT PORTB, r24
  DEC counter
  BRNE loop 

I suppose for the given task LDD can be useful to load the value of a variable that's not placed on top of the stack(not accessible without first POPping the return address and then PUSHing it back).
LDD can only be used if you know where in the stack the variable is located.
OTOH I'd never PUSH that variable to stack in first place unless forced to, I'd use a dedicated register.
YMMV...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Lennart,

Well you see a lot of Y base stack frame processing in code generated by C compilers but usually this is a stack adjustment made "inside" the called function where the stack is adjusted down to make room for local variables. So I suppose there is some merit in learning about this if only to make you more proficient at reading compiler generated code. An early point I made though is that even a C compiler does not switch to passing parameters in by the stack until there are a huge number of parameters or the number varies (such as printf()). The AVR, with 32 registers kind of makes the need for "tricks" like stack frame passing to be irrelevant.

I wonder if the tutor on this course is stuck in a 6800/Z80/6809 mindset still and has missed the point that the AVR was actually designed as a processor suited to C style parameter passing? (ie oodles of registers).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think that teacher wants to show how to call a subroutine recursively. But I cannot see why a student should know this intimately. i.e. should only understand the concept, and understand compiler generated code.

Some algorithms are incredibly elegant with recursion.
AFIK, you can always convert recursion to iteration.

Iteration may not look quite so elegant, but it is almost always considerably more efficient.

The iterative algorithm shown earlier can be replaced with recursion. It would be horrific.

As a general rule, iteration is far more suited to microcontrollers. Some MCUs have a very limited stack.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ye im definately sure thats what she wants us to do, this is my first time learning anything to do with assembly, and the previous three labs where just basics such as ldi and sts and outputting to ports, but this lab as you can tell involves a lot more.

This is the extract from our assignment

We will assume no math library, so the “pow()” function will need to be calculated using a for-loop. The “ldd”
instruction will be very useful in manipulating the stack values in this program. Additionally, multiplying by 2
can be done easily by using the “lsl” instruction. Look these up and understand how it to use them.


.include "m8515def.inc"  ; include the ATMEGA8515(L) definitions file 
.def num = r16  ; use this register to store ‘num’ 
.def result = r17  ; use this register to store ‘result’ 
 
RESET: 
  *** Initialise the stack *** 
 
LOOP: 
  ldi num, 0x06  ; this is our start number 
 
  *** setup passing parameters on the stack *** 
 
  rcall HANOI 
 
  *** capture the return value from the stack *** 
   
  rjmp LOOP  ; Jump back to start  
 
HANOI: 
  *** Add hanoi calculation *** 
  ret 
 
; END of code 

where hanoi is

typedef unsigned char byte;    // define 8-bit variable type 
 
int main(void) { 
  byte result, num = 6; 
  for(;;) {   
    // Calculate the result of the Tower of Hanoi 
    result = hanoi(num); 
  } 
} 
 
byte hanoi(byte n){ 
  // calculate 2^n-1 without the pow() function 
  byte ret = 1; 
  for(byte i = 1; i <= n; i++) { 
    ret *= 2; 
  } 
  ret--; 
  return ret; 
} 

As you can see from my previous posts i keep attempting, but yes still stuck.

can someone give me a jist of what i am to change in my code to get this functioning.

Also by the way this is part one.

Recursion is part 2.

typedef unsigned char byte;    // define 8-bit variable type 
 
int main(void) { 
  byte result, num = 6; 
  for(;;) {   
    // Calculate the result of the Tower of Hanoi 
    result = hanoi(num); 
  } 
} 
 
byte hanoi(byte n){ 
  if(n <= 1)  
    return n; 
  else 
    return ( 2*hanoi(n-1) + 1 ); 
} 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

. The “ldd”
instruction will be very useful in manipulating the stack values in this program.

That's as maybe but I don't personally see how LDD+stack would fit into such a program (and by the looks of it nor do any of my learned colleagues here either).

Can you contact her and ask for clarification as to where in the solution of a pow() replacement she sees the stack and LDD being of any use.

It seems you are being forced to over-engineer a solution simply to accommodate for this mis-guided wish?

It would be VERY enlightening if your tutor could be asked to read/respond to the points in this thread to justify her thinking.

I still think there's some misinterpretation going on. However on the other hand you don't skip from 3 lessons about simple use of LDI/OUT/etc. to using stack frame variables and index addressing to access them so the requirement does look very very odd!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have talked to her in person a few days ago, and yes she confirmed using LDD.

The begining of the task states
In this task you will write a program to calculate the tower of Hanoi number using a for-loop within a
subroutine. The C-code is provided. You are required to implement the program in assembly. The
parameters and return values must be passed via the stack.

Thus why I assumed the need of push, pop and the fact that she mentioned using LDD as you saw in the post above.

And yes tell me about it, the lab before that was simple arithmetic calculations and storing them in registers and then in memory, so this is definitely a step up.

If anyone could thing of a way to do this from what you read thats easier, maybe I miss understood it wrong.
Can someone show me at least basic code, such as pushing 2 numbers, adding them via the stack and then popping them or etc.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

The
parameters and return values must be passed via the stack.

But this is utter tosh. A C compiler wouldn't do that (and it's written by real Asm experts!) so why would you?
Quote:

Can someone show me at least basic code, such as pushing 2 numbers, adding them via the stack and then popping them or etc.

Well I kind of already did but:

 ldi r16, 137
 push r16       ; going to add 137
 ldi r16, 194
 push r16       ; and 194
 call add_2_stacked
 pop R16
 out PORTB, r16 ; then output result to PORTs B and C
 pop r16
 out PORTC, r16
end: rjmp end

add_2_stacked:
 in r28, SPL
 in r29, SPH   ; Y (r28:r29) = SP
 adiw Y,1
 adiw Y,1      ; skip the 2 byte return address
 ldi r16, Y+0  ; get first parm to R16
 ldi r17, 0
 ldi r18, y+1  ; and second to R18
 ldi r19. 0
 add r16, r18  ; add r17:r16 to r19:r18 (upper bytes start 0)
 adc r17, r19
 st  Y+0, r16  ; store result back to parameters on stack
 st  Y+1, r17
 ret

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quick question, what does adiw do, and why are registers 17 and 19 needed?
Regards

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sinedo - you say you are on a university course. Have you looked at the first entry for http://lmgtfy.com/?q=avr+adiw ?

...or even http://lmgtfy.com/?q=AVR+Instruc... ?

r17, r19? What do you think the result of adding 137 and 194 together would be if you only targeted an 8 bit register to hold the result? Maybe you would need to hold the result in more than one register perhaps? Think it through - do a bit of thinking and investigating before asking questions where you think the answer might be simple :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Quote:
The parameters and return values must be passed via the stack.
But this is utter tosh.

But it's doable, even though it's not the way things are done in most AVR compilers. I've seen other compilers that DO do this, pretty consistently. In fact, there are switches for some compilers along the lines of "always create a standard stack frame, even if you know how to optimize it away." And I've used it, because then the debuggers work much better.

In pseudo-code (so as not to do all the work), it would look something like:

main:
     :
   push result  ;; dummy spot for return value
   push num   ;; argument "num"
   call hanoi
   pop result  ;; discard arg from stack
   pop result  ;; get actual result
     :
   ;; rest of program


hanoi:
    ;; save y, or z
    ;; move sp to y, or z as "frame pointer"
    ;;   possible adjust fp so you can use ld r, ld+q form
    ;; save additional registers
    ldd n, fp + numoffset
    ;; do for loop equiv
    std fp + retvaloffset, result
    ;; restore registers
    ret
 

Note that most of those symbols (fp, result, num) will need to resolve to registers...
This results in a "stack frame" that will look like:

n:  saved registers   <---- SP points here.
      more saved registers
        :
n+m: return address   <---- FP points here
      return address H
     num
     result
n+m+4: 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

From what i understood it makes Sp into a single 16bit register, and adds 1 to it. But why do you need to do add one and its done twice?
Im sorry if i sound stupid, im jist trying to get my head around it all
Regards

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
From what i understood it makes Sp into a single 16bit register
ADIW has nothing to do with the SP. Where in the documentation of ADIW do you see that?

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Actually you can use any number btw 1-63 in ADIW
so

adiw   y,2    ;add 2 to Y (r28:r29)

would work.

Pages