Please help with Stack Operations

Go To Last Post
116 posts / 0 new
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.

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

Quote:
ADIW has nothing to do with the SP. Where in the documentation of ADIW do you see that?
Cliff provided an example where SP is loaded into Y (see above post).

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

Doesnt Y=SP? And its adiw Y. Thats where i got it from

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

Quote:
But why do you need to do add one and its done twice?
You need to add 2 to move the SP to the location where your earlier pushed variables are located, because when RCALL/CALL is used a 2-byte return address is loaded onto the stack and will prevent you from directly accessing those variables (using POP).

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

Maybe I should add that the SP is loaded at the highest SRAM address on init of a program and anything saved to the stack will move SP to a LOWER SRAM address.
Might not be obvious to a newbie that a growing stack chew its way DOWN through SRAM.

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

clawson and LENART, and others THANK YOU SO MUCH, with some more research I think I get the understanding of LDD and stack operations.

.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 = r19
RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM
  LDI RESULT,$1
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  POP RESULT
  POP NUM
  OUT PORTA, RESULT
  OUT PORTB, NUM
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,2

 LDD NUM, Y+0
 LDD RESULT, Y+1
 LDI TEMP, $1

FOR_LOOP:
 
 
 
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  std Y+0, NUM
  std Y+1, RESULT
 
  RET 

Here is my other attempt.

I'm pretty sure I implemented the Stack right, but when debugging at the

LDD NUM, Y+0

the Num register becomes 9 instead of 6, why is that.

Also the result at the end comes out as 6, so im pretty sure my loop is wrong.

Can someone give me a tip on the Loop function please.

Regards

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

Also is the main difference with LD, ST and LDD and SDD is that with LD, ST you use increments/decrements and with LDD,STD you use displacement?

And what is the main difference in simple Terms between the X, Y and Z pointers.

P.s this isnt for my assignment but just interested to know.

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

Quote:

the Num register becomes 9 instead of 6, why is that.

Cliff screwed up! I should have tested the code rather than just writing it theoretically. The Y adjustment needs to be:

 adiw r29:r28,3

That's because SP is pointing at the byte BELOW the two bytes of return address after entry to the function, not at the bottom byte of the return address so the adjustment is 3 not 2.

Quote:

Also is the main difference with LD, ST and LDD and SDD is that with LD, ST you use increments/decrements and with LDD,STD you use displacement?

You do have the PDF that documents the opcodes don't you? Read about LD/LDD there but, yes,. for Y and Z the extra D means "displacement". In fact "LD R24,Y" is really just an encoding of "LDD R24, Y+0" when you look at the bit pattern of the opcode.

Quote:

And what is the main difference in simple Terms between the X, Y and Z pointers.

Nothing. They give you 3 so you can pick whichever you like. Often if you are doing a memory to memory copy you will have one of X,Y,Z pointing at the source and another pointing at the destination then the core of the copy loop becomes:

LD reg, X+
ST Y+, reg

(or whatever from X,Y,Z you chose). X differs slightly from Y and Z in that it does not offer LDD/STD with the +n displacement.

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

Quote:
Also is the main difference with LD, ST and LDD and SDD is that with LD, ST you use increments/decrements and with LDD,STD you use displacement?

And what is the main difference in simple Terms between the X, Y and Z pointers.

LD/ST will load/store values in SRAM at a location pointed to by Index registers. LDD/STD is very similar to LD/ST but with an added number of displacement from Index registers.
As Index register you can use X, Y or Z.
X/Y/Z can be post-incremented or pre-decremented which makes them easy to use for loading/storing several bytes in a row. X/Y/Z can be used without +/- to load/store single bytes.
sys_init:
	ldi	zh,high(in_1)	;msb SRAM
	ldi	zl,low(in_1)	;lsb SRAM
	ldi	xh,0x00		;msb EEPROM
	ldi	xl,low(in_1)+16	;lsb EEPROM
sys_prom:
	rcall	prom_read		;read EEPROM
	st	z+,data		;save data to SRAM
	adiw	x,1			;inc EEPROM adress
	cpi	zl,low(sys_end)	;until beyond SYSTEM
	brne	sys_prom		;read EEPROM

Another option is LDS/STS which will load/store bytes at a location earlier defined. Useful since you don't need to set up any Index pointers.

foo:			.byte 1	;define foo
lds   r16,foo
inc   r16
sts   foo,r16

Only difference btw X/Y/Z is that only Z can be used to load data from FLASH(program memory).
Program memory is often used to store data that will not change such as tables or text strings.
To load data from FLASH you need to use LPM instruction.

send_cmd:
	lpm	data,z+		;get CMD CHAR
	tst	data			;if NULL
	breq	cmd_ok		;CMD DONE
	rcall	uart_tx		;else send CMD CHAR
	rjmp	send_cmd		;fetch CMD CHAR

Z can be post-incremented but not pre-decremented.

To understand what makes you get wrong numbers in your code you should use the simulator included in AVRStudio.
Use single stepping and look at how the registers and stack(at the end of your SRAM) change.

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

Quote:

To understand what makes you get wrong numbers in your code you should use the simulator included in AVRStudio.
Use single stepping and look at how the registers and stack(at the end of your SRAM) change.

I think that's how he saw the 9 where there should have been a 6. It's also where I saw the same thing and realised that SP points BELOW the return address not at the base of it after CALL.

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

Quote:
It's also where I saw the same thing and realised that SP points BELOW the return address not at the base of it after CALL.
This was new to me too.
Suppose you never get too old to learn.

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

What this thread needs is pictures..

Second entry googling for "AVR stack pointer"
http://www.avr-tutorials.com/gen...

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

What very confusing pictures - a stack pointer that goes "up" as items are added to the stack? On the other hand I suppose it's natural to show ascending addresses going down the page?

I guess that because a "stack" is so called because of the spring loaded stack of plates metaphor what should really be shown is an SP that never moves and a stack of data that itself moves up and down.

How confusing.

Last Edited: Tue. Apr 3, 2012 - 11:05 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yeah - I didn't say they were good pictures :)
..I just wish forums had a neat way of allowing people to draw pictures to explain things..I'm sure this thread would be only half its length if all these attempts at describing stack operations via words were replaced with some (agreed and useful) pictures.

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

Cliff, a stack pointer growing upwards (that is: lower addresses are above higher addresses) is something that is quite common when visualized in a picture. Maybe it is originating from many common designs where the stack simply grows from the opposite end of the available address space than the user program/data does. To maximize efficiency using the space in between those 2 areas, they grow towards each other from opposite directions. That's why the stack grows upwards but towards lower addresses.

And who said that the stack pointer moved in the referred picture? It's all a matter of relativity - you can as well state that the observer moved together with the data, but the stack pointer remained at a fixed position :-)

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 guess it's the same old argument as to which way up your draw a memory space diagram?

Do you have 0x0000 at the top of the page or the bottom?

For me it only "feels right" with 0x000 at the bottom of the page yet memory layout diagrams in Atmel datasheets are drawn the other way up ((non BOOTRST)reset/vectors at the top, bootloader at the bottom). An odd form of OCD makes my flesh creep when I see this! :?

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

But imagine a 4GB address space fully occupied and you want to see what's at the beginning??? Would you happily scroll down thru dozens of pages just to see user code that resides in lower space traditionally?

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:

But imagine a 4GB address space fully occupied and you want to see what's at the beginning???

OK in your scheme what if you want to check what's at the end? ;-)

(quite a few chips have vectors at the very end of memory)

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

clawson wrote:
Quote:

But imagine a 4GB address space fully occupied and you want to see what's at the beginning???

OK in your scheme what if you want to check what's at the end? ;-)

(quite a few chips have vectors at the very end of memory)


I'd say: tough luck then! But for a matter of data dynamics it surely is more effective to have that space readily at hand where the suspected user code & data structures reside, not the constant vector table at the very end of a design's address space layout?

But i will happily admit that this little rathole is best discussed in the next pub with a pint of beer at hand.

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
.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 = r19
RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM
  LDI RESULT,$1
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  POP RESULT
  POP NUM
  OUT PORTA, RESULT
  OUT PORTB, NUM
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,3

 LDD RESULT, Y+0
 LDD NUM, Y+1
 LDI TEMP, $1

FOR_LOOP:
 
 
 
  ADD RESULT, RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  temp, NUM      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  std Y+1, NUM
  std Y+0, RESULT
 
  RET 

I also got the Ldd wrong, as Result is +0, and Num is +1, as thats the order I pushed them, so thats fixed now.

So my variables now are equal what they should, One thing left is the for Loop, its still not doing what it should for some silly reason

Last Edited: Tue. Apr 3, 2012 - 12:49 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

So my variables now are equal what they should, One thing left is the for Loop, I am just using one I was suggested earlier in this thread, but it doesn't work, as Result just comes of as one.

This is where you learn to be a software engineer. As the ADIW,3 thing shows software is not always right when you first implement what you thought was a great idea so the next step is to debug it and find out what's going on.

As you've already found, for code like this that doesn't really care much about hardware inputs and outputs (apart from the very end - you never set DDR by the way!), then the simulator is perfect for stepping through it and finding out what does/doesn't work.

So I load your code into AVR Studio 4, build and run it in the simulator and watch what happens in "HANOI:".

After the first ADD RESULT,RESULT I see 2 in RESULT. "temp" then increments to 2. The CPU flags show C(arry) to be set after the CP temp,NUM because temp=2 and NUM=1 so it does not loop back and ends (including the SUBI) which seems to tell me that Cliff screwed up again and got the CP the wrong way round!

So I corrected it to be:

  CP  NUM, temp      ; i <= n ?

After doing this I get the result 0x3F (63) which I believe is correct?

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

Quote:
which seems to tell me that Cliff screwed up again and got the CP the wrong way round!

Just in case the Op doesn't yet know:
After the excution of this instruction sequence,

LDI R0, Cliff
CP  R0, clawson

the Z flag has been set.

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

That joke was close to being too subtle for me! ;-)

Of course I'm a C programmer so:

if (Cliff==clawson) {
  printf("you are Cliff Lawson and I claim my £5");
}

And that subtle reference may be lost on anyone who is not from UK and at least 40+ years old ;-) (see: http://en.wikipedia.org/wiki/Lob... see also: http://www.worldofspectrum.org/c... )

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

The lovely new working code.
Thank You Cliff, Much appreciated mate.

.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 = r19
RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM
  LDI RESULT,$1
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  POP RESULT
  POP NUM
  OUT PORTA, RESULT
  OUT PORTB, NUM
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,3

 LDD RESULT, Y+0
 LDD NUM, Y+1
 LDI TEMP, $1

FOR_LOOP:
 
 
 
  LSL RESULT ; "ret *= 2"
  INC temp           ; i++
  CP  NUM, TEMP      ; i <= n ?
  BRCC FOR_LOOP
  SUBI RESULT, 1     ; "ret--"
  std Y+1, NUM
  std Y+0, RESULT
 
  RET 

Btw I replaced ADD RESULT, RESULT with just LSL command, I forgot about it earlier.

Thank you everyone for explaining it to me, I know it would get frustrating teaching a newbie something something like this =)[/code]

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

Quote:

Btw I replaced ADD RESULT, RESULT with just LSL command, I forgot about it earlier.

Guess what (taken from the opcode manual):

LSL Rd:    0000 11dd dddd dddd
ADD Rd,Rr: 0000 11rd dddd rrrr

So when r=d that becomes:

ADD Rd,Rd: 0000 11dd dddd dddd

Time of a game of "spot the difference" between the LSL and the latter form of ADD! ;-)

This is why in the description of LSL the opcode manual says "16-bit Opcode: (see ADD Rd,Rd)".

There are far more opcodes listed in that manual than there are really opcode bit patterns. For another example look up BSET then look at each of SEC, SEH, SEI, SEN, SES, SET, SEV, SEZ in turn. And you probably thought that was really 9 different opcodes ?

And here is a list that shows the ones that are the same - any line with " = " in it is just another name for the bit pattern already listed:

0000 0010 dddd rrrr   muls    d,d		1
0000 0011 0ddd 0rrr   mulsu   a,a		1
0000 0011 0ddd 1rrr   fmul    a,a		1
0000 0011 1ddd 0rrr   fmuls   a,a		1
0000 0011 1ddd 1rrr   fmulsu  a,a		1
0000 01rd dddd rrrr   cpc     r,r		1
0000 10rd dddd rrrr   sbc     r,r		1
0000 11rd dddd rrrr   add     r,r		1
        =             lsl     r

0001 00rd dddd rrrr   cpse    r,r		1
0001 01rd dddd rrrr   cp      r,r		1
0001 10rd dddd rrrr   sub     r,r		1
0001 11rd dddd rrrr   adc     r,r		1
        =             rol     r

0010 00rd dddd rrrr   and     r,r		1
        =             tst     r
0010 01rd dddd rrrr   eor     r,r		1
        =             clr     r
0010 10rd dddd rrrr   or      r,r		1
0010 11rd dddd rrrr   mov     r,r		1

0011 KKKK dddd KKKK   cpi     d,M		1

0100 KKKK dddd KKKK   sbci    d,M		1

0101 KKKK dddd KKKK   subi    d,M		1

0110 KKKK dddd KKKK   ori     d,M		1
        =             sbr     d,M

0111 KKKK dddd KKKK   andi    d,M		1
        =             cbr     d,n

100! 000d dddd ee-+   ld      r,e		1
100! 001r rrrr ee-+   st      e,r		1
10o0 oo0d dddd booo   ldd     r,b		1
10o0 oo1r rrrr booo   std     b,r		1

1001 000d dddd 0000   lds     r,i		2
1001 000d dddd 010+   lpm     r,z		1
1001 000d dddd 011+   elpm    r,z		1
1001 000r rrrr 1111   pop     r			1
1001 001d dddd 0000   sts     i,r		2
1001 001r rrrr 1111   push    r			1
1001 0100 0000 1001   ijmp				1
1001 0100 0001 1001   eijmp				1
1001 0100 0SSS 1000   bset    S			1
        =             sec
        =             sez
        =             sen
        =             sev
        =             ses
        =             seh
        =             set
        =             sei
1001 0100 1SSS 1000   bclr    S			1
        =             clc
        =             clz
        =             cln
        =             clv
        =             cls
        =             clh
        =             clt
        =             cli
1001 0101 0000 1000   ret				1
1001 0101 0000 1001   icall				1
1001 0101 0001 1000   reti				1
1001 0101 0001 1001   eicall			1
1001 0101 1000 1000   sleep				1
1001 0101 1001 1000   break				1
1001 0101 1010 1000   wdr				1
1001 0101 1100 1000   lpm     ?			1
1001 0101 1101 1000   elpm    ?			1
1001 0101 1110 1000   spm				1
1001 010h hhhh 110h   jmp     h			2
1001 010h hhhh 111h   call    h			2
1001 010r rrrr 0000   com     r			1
1001 010r rrrr 0001   neg     r			1
1001 010r rrrr 0010   swap    r			1
1001 010r rrrr 0011   inc     r			1
1001 010r rrrr 0101   asr     r			1
1001 010r rrrr 0110   lsr     r			1
1001 010r rrrr 0111   ror     r			1
1001 010r rrrr 1010   dec     r			1
1001 0110 KKdd KKKK   adiw    w,K		1
1001 0111 KKdd KKKK   sbiw    w,K		1
1001 1000 pppp psss   cbi     p,s		1
1001 1001 pppp psss   sbic    p,s		1
1001 1010 pppp psss   sbi     p,s		1
1001 1011 pppp psss   sbis    p,s		1
1001 11rd dddd rrrr   mul     r,r		1

1011 0PPd dddd PPPP   in      r,P		1
1011 1PPr rrrr PPPP   out     P,r		1

1100 LLLL LLLL LLLL   rjmp    L			1

1101 LLLL LLLL LLLL   rcall   L			1

1110 KKKK dddd KKKK   ldi     d,M		1
	    =			  ser     d (K=FF)

1111 00ll llll lsss   brbs    s,l		1
        =             brcs    l
        =             brlo    l
        =             breq    l
        =             brmi    l
        =             brvs    l
        =             brlt    l
        =             brhs    l
        =             brts    l
        =             brie    l
1111 01ll llll lsss   brbc    s,l		1
        =             brcc    l
        =             brsh    l
        =             brne    l
        =             brpl    l
        =             brvc    l
        =             brge    l
        =             brhc    l
        =             brtc    l
        =             brid    l
1111 100d dddd 0sss   bld     r,s		1
1111 101d dddd 0sss   bst     r,s		1
1111 110r rrrr 0sss   sbrc    r,s		1
1111 111r rrrr 0sss   sbrs    r,s		1

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

That applies to most MCUs. There are several pseudonyms for the same instruction.

It keeps most people happy, most of the time.

It is no trouble for Assemblers. It is confusing for Disassemblers.

David.

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

Quote:

It is confusing for Disassemblers.

And simulators ;-) (hence my list above).

Atmel do seem to make a thing of:

Page 1 of just about any AVR datasheet wrote:
• Advanced RISC Architecture
– 130 Powerful Instructions – Most Single-clock Cycle Execution

I've always thought it a bit disingenuous of them to make this "130" claim in each datasheet when there aren't 130 different ones ;-)

Even with blank lines inserted my list above is exactly 130 lines long (Notepad++ says).

EDIT: a quick look at mega640/1280/2560 datasheet bumps the number to 135 (above was mega8)

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

sinedo,

To get bonus points, tidy up the code and add your own comments that describe what happens.
I still don't see the point with LDD/STD, you could have used LD/ST for this if you post-incremented Y and loaded/stored NUM and RESULT in reverse order.
But you'd better do what your teacher told you to make her happy.

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

Quote:

I still don't see the point with LDD/STD,

In fact the funny thing is that when HANOI: returns and the code does the POP's into RESULT and NUM those registers already hold those values - which rather proves the point about the idiocy of being forced to use the stack!

Perhaps "inside" HANOI: you should use different registers simply to show that the return value *is* then being passed back correctly on the stack (and not the fact that the registers already hold the output anyway when you get back)?

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

Quote:
sinedo,

To get bonus points, tidy up the code and add your own comments that describe what happens.
I still don't see the point with LDD/STD, you could have used LD/ST for this if you post-incremented Y and loaded/stored NUM and RESULT in reverse order.
But you'd better do what your teacher told you to make her happy.

Yep I definitely will, and yes she asks for LDD so ill leave it at that, but thanks to this forum I know a lot more then she ever told us about this.

Now just to do the second part.

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 ); 
} 

Using the previous code for the stack parts, first step i did was see what the dissasembler shows me.

3:        byte hanoi(byte n){ 
+0000001A:   3082        CPI       R24,0x02       Compare with immediate

+0000001B:   F020        BRCS      PC+0x05        Branch if carry set

7:            return ( 2*hanoi(n-1) + 1 ); 
+0000001C:   5081        SUBI      R24,0x01       Subtract immediate

+0000001D:   DFFC        RCALL     PC-0x0003      Relative call subroutine

+0000001E:   0F88        LSL       R24            Logical Shift Left

+0000001F:   5F8F        SUBI      R24,0xFF       Subtract immediate

8:        }
+00000020:   9508        RET                      Subroutine return

The result does end up 63, I just need to figure out how to put this inside my code.

I think a much better way will be to do a flow chart of what's happening and then step by step input it into assembly.

Thank you everyone for your help once again, ill update on how I go soon, but now its bed time in Sydney =)

Last Edited: Tue. Apr 3, 2012 - 02:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Perhaps "inside" HANOI: you should use different registers simply to show that the return value *is* then being passed back correctly on the stack (and not the fact that the registers already hold the output anyway when you get back)?
IIRC part of the assignment was to use as few registers as possible.
Was looking for a way to get rid of TEMP but that would need more PUSH and POP and might just be confusing.

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

By the way quickly looking at the c code (PART 2), i can see that it begins with n = 1, so quick calculation, i get

2*1 +1 =3
2*3 +1 = 7
2*7 +1 = 15
2*15 +1 = 31
2*31 + 1 =63

I probably should of started from that instead of running to dissasembler.

As for part one, I have to explain in person to the Tutors that mark us what i did, so regardless I will be showing them step by step what my code does, so they know I understand it, its not just a submit electronically and walk away type of task

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

Because im still not asleep, I tried part 2

Is this all I have to do, from what you experts can see that the c-code specifies?

.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 = r19
RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM
  LDI RESULT,$1
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  POP RESULT
  POP NUM
  OUT PORTA, RESULT
  OUT PORTB, NUM
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,3

 LDD RESULT, Y+0
 LDD NUM, Y+1
 LDI TEMP, $2 ; two because ++ after 2x see below

IF_ST:
 
 
             ;;ELSE
  LSL RESULT ; 2*(n-(n-1)
  INC RESULT ; ++
  INC TEMP   ; counter ++       
  
  CP  NUM, TEMP  ;if(n <= TEMP)    
  BRCC IF_ST
      
  std Y+1, NUM
  std Y+0, RESULT
 
  RET 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I guess it's the same old argument as to which way up your draw a memory space diagram?

Do you have 0x0000 at the top of the page or the bottom?

I do mine left to right ;) But to me, you start 0 where you start writing on a page, which for all cultures that I can think of is the top of the page (though left or right might change).
Quote:
[In fact the funny thing is that when HANOI: returns and the code does the POP's into RESULT and NUM those registers already hold those values - which rather proves the point about the idiocy of being forced to use the stack!
And I don't see the point of pushing both NUM and RESULT anyways. Since both are the same size, and NUM only goes in and RESULT only goes out, I would simply push NUM, replace the value on the stack with the result, then pop RESULT. No need waste space on the stack for a number that won't change.

I would also not bother comparing NUM against temp. I would grab NUM off the stack and decrement it until it reaches 0 to end the loop.

Regards,
Steve A.

The Board helps those that help themselves.

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

'Tain't obvious that push and pop are required at all.
At most three registers are required, two with the gnu API.
One or two clobberable registers are all that is necessary to avoid pushes and pops.
The gnu API has more than two.

Moderation in all things. -- ancient proverb

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

Quote:
'Tain't obvious that push and pop are required at all.
No, I think most of us already agreed that we would handle this as you suggest.
Unfortunately the assignment forces him to use stack for passing parameters and as few registers a s possible.
Hopefully this exercise have some value for future understanding of how the stack operations work.

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

Lennart wrote:
Quote:
'Tain't obvious that push and pop are required at all.
No, I think most of us already agreed that we would handle this as you suggest.
Unfortunately the assignment forces him to use stack for passing parameters and as few registers a s possible.
Hopefully this exercise have some value for future understanding of how the stack operations work.
Sorry about that.
When I wrote it, I'd forgotten that I was only on the first of five pages.
Had it not drawn a response already, I'd have deleted it.

Moderation in all things. -- ancient proverb

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

Quote:
Is this all I have to do, from what you experts can see that the c-code specifies?

1. You could certainly improve on it if you are anally-retentive.
2. Otherwise you could just add the explanatory comments that are so loathed by students.

I know which I prefer. You know your teacher.

David.

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

I talked to my lecturer today, shes fine with Part A, but i realised what is wrong with part B, im still using iteration.

I actually need to Rcall Hanoi within Hanoi.. Duhh =)

  • 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 = r19
RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM
  LDI RESULT,$1
  PUSH RESULT
  RCALL HANOI ; returns with RESULT
  
  POP RESULT
  POP NUM
  OUT PORTA, RESULT ;Displays result in Port A
  OUT PORTB, NUM    ; Displays original NUM in Port B
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,3

 LDD RESULT, Y+0
 LDD NUM, Y+1
 LDI TEMP, $1


 
 CP  TEMP, NUM      ; i <= n ?
  BRCC RETURN
  SUBI NUM, 1
   
  std Y+1, NUM
  LSL RESULT ; "ret *= 2"
  INC RESULT           ; i++
  std Y+0, RESULT 
  POP TEMP
  POP TEMP
 
  
  
 
  RCALL HANOI
  ;std Y+1, NUM
  ;std Y+0, RESULT
 
 RETURN:
 RET
 

This is my beta code, RET doesnt work as it should, as I assume i lost the return a address somewhere in the stack or something like that.

Can someone comment on the code please

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

You lost the return address here:

  POP TEMP 
  POP TEMP 

You can't just throw away the return address and expect to get back to where you started. When you call your routine recursively, you need to call it the same way you called it the first time.

Regards,
Steve A.

The Board helps those that help themselves.

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

Yes I realised thats what I did, but would you overcome the the fact that Ret is only executed at the End of the Recursive function, as I was specifically told to Rcall Hanoi Within Hanoi itself.

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

Quote:

the the fact that Ret is only executed at the End of the Recursive function

No, you misunderstand recursion - it's executed (probably 6 times) each time the nested call to the function unwinds.

To be honest I'd be a bit leery myself about handling stack frame parameters and recursion at the same time!

I guess your journey starts with paper and pencil. Sketch out on a page what you expect to be happening on the stack both as you go 6 levels down the chain doing the repeated CALLs and then as you post results and unwind back up the stack.

(I still cannot picture this in my mind just yet!)

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

Quote:
I guess your journey starts with paper and pencil. Sketch out on a page what you expect to be happening on the stack both as you go 6 levels down the chain doing the repeated CALLs and then as you post results and unwind back up the stack.

I can only second Cliff's advice: use the paper/pencil method to see what will happen on the stack, and perform all stack manipulations manually with the pen. To simplify this task, forget about all parameter passing via the stack for now and get absolutely familiar how nested calls and RETs and return addresses being pushed onto the stack really work. Once you're familiar with the mechanics of nested calls, and you recognized that every called routine must not modify the stack contents at the beginning of its own invocation, then you may proceed with actually doing parameter passing via the stack in addition.

As for a mental picture: that old-fashioned spring-loaded stack of plates in my view is still the best analogy. What it does *not* provide is that every single plate is the same form of stack object, whereas in your CPU stack you will find return addresses *and* data items on the stack, which complicates the picture a bit.

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:

which complicates the picture a bit.

return address = 2 plates, simple ;-)

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

No no, i was about to explain the different meaning successive plates could have for the waiters behind you in the queue. So, in the cantina, each plate stands for exactly the same purpose, whereas in calling a subroutine, the callee could find other items on the stack besides the address to finally return to. So, you need a mental concept of an agreement of how exactly the stack does look like when you enter a subroutine. That's what a calling standard will provide. Basically caller and callee simply agree upon the stack contents when the callee enters execution: is there only a return address on top of the stack, or are there additional data items that have been pushed onto the stack just below (beware: this would imply: at higher stack addresses!) the return address? And who is responsible for the removal of those data items (mostly the calling program, but who knows?)?

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 have a bit of a mad idea for OP (perhaps not that mad, several C compilers do it):

Two stacks.

Use the hardware stack simply for CALL/RET then implement a second data stack for the variables. This helps to avoid the mish-mash of interleaved items on the single stack.

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

To simplify things, why not create your own data stack? Avoids having to make stack frames and indexing around the return address. Then just write functions or macros to push/ pop values.

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

Great minds think alike! Cliff just beat me to the punch.

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

Do we say "SNAP!" now? ;-)

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

Well i do understand that Rcall each time puts in the address of the location into the stack and moves the pointer under the 2 bytes of the address, Ret does the opposite it gets the adress out of the stack, pops it out and voila. And yes i know poping twice as i did in my code just discards that address thus, i can not get back to the top, and the ret I used just goes back to ret, as thats the next thing after the last Rcall Hanoi.

I want to try to preserve that first address, and discard all other 2bytes that the Rcall Hanoi within the function then creates. Thats one approach im thinking of, will research further if its possible and how.

Would placing that address into 2 registers, and then storing them back onto the stack right before I do the final RET work, so STD - ing them back? Would I just then need to not do this

in r28, SPL
 in r29, SPH
 adiw r29:r28,3 

and instead

LDD RESULT, Y+3
 LDD NUM, Y+4

Is my understanding right that the address of the rcall is stored in Y+0, Y+1?

edit

Just got onto my pc with AVRSTUDIO 4.
Y+3, and Y+4 is not the right values, My understanding is fogged up again. Need to re-read the manual

Last Edited: Wed. Apr 4, 2012 - 11:56 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You aren't going to do this without paper and pencil!

Perhaps it's because I am a bear of very little brain but I cannot picture exactly what's going to be happening on a single stack when you are mixing up passed parameters and return addresses and how you access and then return values that way as you first go in and then unwind the recursion. So you need a picture (or at least I do).

I'm beginning to think your course tutor may be a reincarnation of Beelzebub!

(don't discount the 2 stack idea - when you draw the pictures draw both - you may find things easier to follow with the input/output parms on a different stack),

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

clawson wrote:
You aren't going to do this without paper and pencil!

Perhaps it's because I am a bear of very little brain but I cannot picture exactly what's going to be happening on a single stack when you are mixing up passed parameters and return addresses and how you access and then return values that way as you first go in and then unwind the recursion. So you need a picture (or at least I do).

I'm beginning to think your course tutor may be a reincarnation of Beelzebub!

(don't discount the 2 stack idea - when you draw the pictures draw both - you may find things easier to follow with the input/output parms on a different stack),

Ye ill try it with pen and paper, Im just looking through the Memory view in AVR, and seeing how the stack changes, and I see that it just keeps adding the address by 2 pointers each Rcall.

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

The first hurdle is to get the algorithm correct THEN write the code. As Cliff mentions - use pencil and paper. Formulate a simple stack machine with simple instructions like push and pop. Execute the simple codes on paper. When you have got this working then convert the operations to assembler, C or whatever. Your tutor will be impressed with the logical technique applied to solve the problem. You'll also solve your problem a lot more efficiently.

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

Well this works on debugging

.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 = r19

RESET:
  LDI r18, high (RAMEND)
  OUT SPH, r18
  LDI r18, low (RAMEND)
  OUT SPL, r18
 
 
  LDI NUM, $6
  PUSH NUM ; Push NUM onto stack
  LDI RESULT,$1
  PUSH RESULT ;Push Result onto stack
  RCALL HANOI ; returns with RESULT
 
  ;POPs  the no longer needed address
  POP TEMP 
  POP TEMP
  
  ;Extracting The Result and NUM(for debugging)
  POP RESULT
  POP NUM
  
  OUT PORTA, RESULT ;Displays result in Port A
  OUT PORTB, NUM    ; Displays original NUM in Port B (for debugging)
LOOP:
  RJMP LOOP

HANOI:
 in r28, SPL
 in r29, SPH
 adiw r29:r28,3

 LDD RESULT, Y+0 ; Loading Result from Stack
 LDD NUM, Y+1 ; Loading Result from Stack
 
 
 
 LDI TEMP, $1 ; Temp = 1
 LDI r26, $4 ;  r26 = 4 for further calculations

  ; When Num reaches 1, skip further calculations
  CP  TEMP, NUM      ; i <= n ?
  BRCC RETURN
  SUBI NUM, 1 ; Num --
   
  std Y+1, NUM ; store new Num value back into memory
  LSL RESULT ; "ret *= 2"
  INC RESULT           ; i++
  std Y+0, RESULT ;store current Result value into memory
 
 ; if NUM<=4 skip to HOME
 CP r26, NUM 
 BRCC HOME 
 ;else
 POP r22 ;stores byte 1 of the Rcall address
 POP r23 ;stores byte 2 of the Rcall address
RCALL HANOI
 
 ; Removes the unnecessary Rcall Address from the stack
 HOME:    ;; if NUM<=4
 POP TEMP 
 POP TEMP
 
 RCALL HANOI ; Recursive
 
  RETURN: ; Result Obtained
 PUSH r23 ; push byte 2 back to stack of the address
 PUSH r22 ; push byte 1 back to stack of the address
 
 RET 
Last Edited: Wed. Apr 4, 2012 - 01:47 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I just did a swift go on the PC.

#include 

int iterate(int n)
{
    int ret = 1;
    while (n--)
        ret *= 2;
    return ret - 1;
}

int recurse(int n)
{
    n--;
    if (n <= 0)
        return 1;
    else
        return 2 * recurse(n) + 1;
}

void main(int argc, char **argv)
{
    int n;
    while (--argc) {
        n = atoi(*++argv);
        printf("recurse(%d) = %d,  iterate(%d) = %d\n",
            n, recurse(n), n, iterate(n));
    }
}

I would write the iterate algorithm as above rather than the for() loop. It also translates to ASM quite well. Although not as good as 8051 or Z80 does.

As I see it the recursive function is more complex than the iterative. And that is before you have to write it in ASM with the stack.

Incidentally, you can make several improvements to your ASM code. Print it on paper, and edit while enjoying a nice cup of tea.

You can also do things quite happily without stack frames. e.g. regular register pushes. Look at what avr-gcc would do.
OTOH, your teacher seems to want stack frames.

David.

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

I am enjoying your ASM project.

I have the iterate(6) taking 38 cycles and recurse(6) taking 102 cycles.
I have the iterate(8 ) taking 46 cycles and recurse(8 ) taking 138 cycles.

Does your teacher give prizes?

David.

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

Quote:

Does your teacher give prizes?

Only if you pass the parms in/out on the stack (and it looks like that is mixed with CALL addresses).

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

Cliff,

I can't believe that this teacher is serious. Unless, as I have suspected all along, she is taking the p*ss.

I think I have shown that a 200% time penalty is hardly worth it. She may want to show a 300% or 400% penalty to prove the point. She might also be showing that a student who 'goes for help' on the internet can waste four days when he could have read his lecture notes.

Look at the other poor chap. He (dakinet) had his whole assignment thought through. And then he was led on a wild goose chase !

I am taking the dog out. I will see how complex the 'stack pass' method is when I come back. I suppose that I can just translate the C with CodeVision. OTOH, it is more satisfying to do it by hand.

David.

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

Quote:
I want to try to preserve that first address, and discard all other 2bytes that the Rcall Hanoi within the function then creates.
No you don't.

I modified your original recursion code in about 20 minutes to work perfectly. But you are not going to be able to do that until you understand how recursion works.
It main you did the function call like this:

PUSH
RCALL HANOI
POP

You must do the exact same thing inside HANOI in order to call HANOI recursively.

Quote:
I have the iterate(6) taking 38 cycles and recurse(6) taking 102 cycles.
I have the iterate(8 ) taking 46 cycles and recurse(8 ) taking 138 cycles.
If you got that from your C code, then that is cheating since it is unlikely that that code passed the argument on the stack, and it certainly does not return the result on the stack. My ASM code has the recurse at 129 cycles for an input of 6 and 175 cycles for an input of 8.

Regards,
Steve A.

The Board helps those that help themselves.

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

Six pages. Wow.
It might be helpful to define an API.
Edit: oops, ABI not API, both above and below
Maybe that has been done.
I've only read the first and last pages.
Not all APIs are allowed.
On entry and just before return
the return address must be on top of the stack.
Any arguments passed on the stack must be below the return address.
The space for the result must be below the return address.
The primary choices are whether the result will replace the argument and what registers the function is allowed to clobber.

Moderation in all things. -- ancient proverb

Last Edited: Thu. Apr 5, 2012 - 04:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well her reasoning is that attempting to do the recursive function, will force u to understand exactly how the stack is being used with pushes, pops, rcalls, pointers, which obviously did, as before this project I though Pop and Push was a game involving tackles and pop corn

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

Koshchi wrote:
Quote:
I want to try to preserve that first address, and discard all other 2bytes that the Rcall Hanoi within the function then creates.
No you don't.

I modified your original recursion code in about 20 minutes to work perfectly. But you are not going to be able to do that until you understand how recursion works.
It main you did the function call like this:

PUSH
RCALL HANOI
POP

You must do the exact same thing inside HANOI in order to call HANOI recursively.

Quote:
I have the iterate(6) taking 38 cycles and recurse(6) taking 102 cycles.
I have the iterate(8 ) taking 46 cycles and recurse(8 ) taking 138 cycles.
If you got that from your C code, then that is cheating since it is unlikely that that code passed the argument on the stack, and it certainly does not return the result on the stack. My ASM code has the recurse at 129 cycles for an input of 6 and 175 cycles for an input of 8.

But what am i supposed to push within Rcall, as I still need to use the NUM that i Pushed earlier.
And as far as I understand Recursion is just calling upon itself, which I did.
Can you please provide an example of what you did to modify my code so I can understand?

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

Recursion is a very useful mathematical technique. It can often create very elegant solutions.

You can generally convert any recursive algorithm to iterative and vice versa.

IMHO, it is a very worthwhile skill to learn how to do this conversion. i.e. given a specification, create both an iterative and recursive solution.

Computer languages are designed to cope with recursion by:
1. using an MCU's CALL/RET mechanism that stores return addresses on a hardware stack.
2. using a hardware or software stack to save local variables.

So you can write your recursive function in C or other HLL. I have even given you an example C function. This is very useful to test your algorithm on a PC without writing any ASM.
You can equally well trace it on paper. That is how most University courses would expect you to calculate your solution.

Your teacher wants you to write an ASM implementation.
You must follow the (2) rule. But IMHO, the niceties of passing arguments or returning results are not critical. (except apparently to your teacher)

int recurse(int n)
{
    n--;                    // n is local copy
    if (n <= 0)
        return 1;
    else
        return 2 * recurse(n) + 1;
}

Before you can use any register or memory location for 'n' (a local), you must save its current contents on a stack. At the end of the function, you must restore these contents.

There are many methods of doing this. Examine a C or Pascal compiler output. Or even ASM examples that I am sure teacher has already shown you.

Use your Simulator to step through any recursive routine. Watch how local variables are stored on a stack, and how you get a new copy for each depth of recursion.

If you had spent two days learning how to write HLL recursive functions, you will be able to answer any recursion question in any exam ever invented.
If you had spent an hour with an AVR simulator you would have learned the 'general knowledge':
1. you get a fresh copy of locals with each depth.
2. recursion is much less efficient than iteration.
3. must have a 'stop condition' e.g. (n <= 0)
4. a bad 'stop condition' crashes your computer !!

I bet that these points were all covered in your lectures. I also bet that textbooks are better at explaining than me.

David.

Edit. I have just looked at the avr-gcc translation of a uint8_t recurse() algorithm.
Since it uses R24 for both argument and return value, it does not use a stack for locals at all !!

And it beats any ASM version that I could ever write myself.

This shows just how clever Compilers can be.

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

david.prentice wrote:
Edit. I have just looked at the avr-gcc translation of a uint8_t recurse() algorithm.
Since it uses R24 for both argument and return value, it does not use a stack for locals at all !!
The argument and return value locations are part of the ABI.
Not retaining a no longer used local variable is an obvious optimization.
Quote:
And it beats any ASM version that I could ever write myself.

This shows just how clever Compilers can be.

Moderation in all things. -- ancient proverb

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

Quote:
But what am i supposed to push within Rcall
The exact thing that you pushed the first time, except with the current value of NUM.
Quote:
I still need to use the NUM that i Pushed earlier.
And it is still on the stack for you to use.
Quote:
And as far as I understand Recursion is just calling upon itself, which I did.
No you didn't, you modified how you called the function (the pushes and pops are an integral part of the function call).

Regards,
Steve A.

The Board helps those that help themselves.