Stack Overflow challenge ...

BESQUEUT

Senior Member
Is it possible to make a stack overflow without using the GOTO command ?
Rich (BB code):
' ! démonstration de ce qu'il ne faut pas faire !

Main:
      sertxd("b0=",#b0,13,10)
      gosub SousProg
      goto Main
     
     
     
SousProg:
      inc b0
      if b0>0 then goto Main
      return
 

westaust55

Moderator
I am not entirely sure what you are trying to achieve.

8 gosub commands each within the previous subroutine without any corresponding RETURN commands is the limit (stack depth for X1, X2 and M2 parts = 8)
Then one more GOSUB will result in stack overflow.
 

BESQUEUT

Senior Member
I am not entirely sure what you are trying to achieve.

8 gosub commands each within the previous subroutine without any corresponding RETURN commands is the limit (stack depth for X1, X2 and M2 parts = 8)
Then one more GOSUB will result in stack overflow.
YES : good remark.
The chalenge is more against the GOTO command :
can we say that good practices to avoid stack overflow are :
- avoiding the GOTO command,
- not embedding more than 8 GOSUB commands,

or are there others things to avoid ?
 

Buzby

Senior Member
Code:
main: gosub sousprog

sousprog: gosub sousprog
Challenge !

This uses 12 bytes on 28X2. Is there a shorter version ?
 

AllyCat

Senior Member
Hi,

AFAIK a GOTO will NEVER affect the stack in a PIC{axe}.

If you want to "overflow" the stack then 7 bytes will do it: ;)
Code:
myself: GOSUB myself
#no_end
The simulator will pick that up as an "overflow error", but a real PICaxe will just loop endlessly since the "stack" is a simple hardware circular buffer.

Strictly, since the same return address is being written every time, no return address has been lost by the overflow ! All that is being "lost" is the number of times that the subroutine was called. :)

Cheers, Alan.
 

AllyCat

Senior Member
Hi,

Recursive programs were quite popular with the BBC Microcomputer, partly because it had a large and flexible stack to PUSH and POP data, etc.. The PIC{axe} is moderately unusual in having a small stack that can be used ONLY for return addresses (and wraps "safely" so it will never corrupt any other memory locations). Actually, I'm fairly sure that PICaxe Basic's Stack in not the "real" (hardware) stack, it's just emulated somewhere in the RAM to have the same size and parameters.

From my last comment in the previous post, here's a different challenge: A simple recursive program will write the same return address every time it calls itself, so we are NOT limited to a maximum of 8 nested Returns! So, write a recursive program for a PICaxe that calls itself MORE than 8 times and still gives a satisfactory result. ;)

Cheers, Alan.
 

tmfkam

Senior Member
Does a PicAxe device not reset on a stack overflow? Due to extensive use of (nested) subroutines I have accidently caused overflow errors in "real" PICs, which has always seemed to cause them to reset and start the program from the beginning. Is this not the case for PicAxe?
 

hippy

Technical Support
Staff member
Does a PicAxe device not reset on a stack overflow?
No. The PICAXE return address stack, as said, is implemented as a circular buffer, so it eventually overwrites earlier things written to it.

This means that any issue related to overflowing the stack will not be observed with the GOSUB calls but on RETURN statements.
 

AllyCat

Senior Member
Hi,

The Simulator gives an incorrect error report if more than 8 addresses (subroutine calls) are pushed onto the stack, but the "real" PICaxes appear to behave as expected/specified.
Does a PicAxe device not reset on a stack overflow?
You might be (partly) correct that it "always" crashes (on the 9th Return), but not that it (necessarily) Resets. Of course normally a crash is to be expected because the ninth Return would be to an incorrect (overwritten) address, (although theoretically it should be possible to predict what will happen ;) ).

However, in my first attempt to program a solution to the new "challenge" that I set in #7, the Simulator stops at the 9th Call (as expected), but a "real" PICaxe (08M2) crashes (continuously transmits a spurious character) at the 9th Return, even though the same return address had been pushed more than 8 times onto the "Stack" (so the 8 addresses should all be identical). Therefore, it looks as if the (08M2) PICaxe Basic interpreter doesn't emulate (or use) the circular buffer entirely correctly? Not a serious issue in practice, but it does rather spoil the fun. :)

Cheers, Alan.
 

tmfkam

Senior Member
A base PIC device always appears to reset on overflow. Though after I originally posted that I did wonder if when the pointer returned to the first address on the stack, if that was the startup routine which initialises the program it would appear to an observer (me!) to have reset, when in fact it had simply returned to the startup routine. I will have to look and see which is the case.
 

hippy

Technical Support
Staff member
Therefore, it looks as if the (08M2) PICaxe Basic interpreter doesn't emulate (or use) the circular buffer entirely correctly?
It does seem that the M2's may not behave as earlier PICAXE devices did and one can no longer rely on predictable behaviour if one overflows or underflows the return address stack.

My guess would be that this came about as a result of adding multi-tasking to the M2 or improving firmware efficiency where the focus would have been on code which is behaving correctly rather than incorrectly - Don't overflow or underflow the stack and everything will be fine.
 

BESQUEUT

Senior Member
Don't overflow or underflow the stack and everything will be fine.
As this is not so easy to explain to a beginner, I prefer saying :
do not use the GOTO command and everything will be fine...
Isn't it ?

Note that I never saw a beginner writing a recursing structure like :
sousprog: gosub sousprog
But lot of them use GOTO command without parcimony...
 

premelec

Senior Member
It would probably help to have beginners look at machine language fundamentals - mostly things go well with 'returns' placed well... JMPs work in proper context; so many opportunities for things to go wrong... ;-0 Details count...
 

mikeyBoo

Senior Member
hi folks,
The following is a little more complicated than many of the "Why
won't my LED come on?" type questions I see on this site. However, some
of you guys are really ingenious, so it may be of some use or interest.
While I agree that never using Jumps (aka GOTOs) is good from a style
perspective, there are some situations where jumps are a really good idea.

What can jumps do for us? 01 save code space 02 extreme speed gains
For example (on a Picaxe) if you have 20 2-part procedures where the
first portion of the proc is unique but the second half is identical, it's
more code-efficient to use a GOTO at the end of each proc than to use a
GOSUB and a RETURN at the end of each proc. After all, the 2nd portion of
each proc is identical, so then you have only a single RETURN that services
all 20 procs. Don't take my word for it, try it. (If you look at my first
Picaxe project (Kayak Control System) you'll see what I mean).
Now, while the above is certainly useful for Picaxe programming, once
you move into the assembly language (or any C-based language) world, Jump
tables can yield astronomical speed gains. Sadly, most programmers don't
take advantage of this.

The following is an excerpt from a table used for really fast input/output
access: Following is a brief example using an 8052-BASIC or C program to
invoke functions. Each of up to 255 tables x 255 functions takes exactly
the same few uSecs to access. Even received ascii chars can use jump vectors
so I'm talkin' extreme speed gains! (the ascii code is the vector number)
Additionally, subroutines can be moved around anywhere in code space & the
"jump vectors" will follow them (via the compiler). You can give names to the
vector number via the Symbol directive (e.g. Symbol MCP23017_read = 01 etc. )

If you wanna' understand the theory behind vector tables, read the attached
.pdf. It's from a discussion I had with a unix DCS programmer years ago.


Same calc used to access EVERY program function (from BASIC or C) It's fast!
;-----------------------------------------------------------------------------\
; Function : Calculate a jump table vector |
; Enter With : Base Addr. in DPTR, Offset Code in A (Func/Key Request Number) |
; Exits With : Calculated Address in DPTR |
; Remarks : calculates a jump vector ((A reg. +1) x 3) + dptr |
; Dependency : none |
; Declarator : (for use with the function table) |
; ljmp key_calc ; xxx Calc a jump table vector DPTR,A->DPTR|
;-----------------------------------------------------------------------------|
key_calc: PROC ; calc jmp vec (((acc +1) x 3)+ dptr)-> dptr|
clr c ; Clear Carry to Prep for Addition |
addc a,#01 ; Prevents a Multiply by 0 |
mov b,#03 ; Index Multiplier for JMP table |
mul ab ; Multiply to find Table Address Offset |
; A=Lo-Byte / B=Hi-Byte (of Offset) |
; |
clr c ; Clear Carry to Prep for Addition |
addc a,dpl ; Add Offset Lo-Byte to Base Address |
mov dpl,a ; Save Result to DPL ( Calculated DPL ) |
mov a,dph ; Put Base Address Hi-Byte in A |
addc a,b ; Add Offset Hi-Byte to Base Address |
mov dph,a ; Save Result to DPH ( Calculated DPH ) |
clr a ; Set A = 00 |
ret ; Return to Caller |
key_calc ENDPROC ; end of procedure |
;-----------------------------------------------------------------------------/

...
FUNC_MAX_5: EQU 255 ; maximum function # (vector) allowed for table 5
;-----------------------------------------------------------------------------\
; Function : MCP23017 I2C discrete IO expander function table: |
; TAKE NOTE: the FUNC_MAX_5 constant for this function table |
; MUST BE defined so that it is not possible to jump |
; beyond the last vector in this table (doing so could|
; cause program crash or and/or undesired results) |
; e.g. last vector is 9, plug in 9 to FUNC_MAX_5 |
; Edit Date : 08-21-2013 |
; Status : (works ok) add functions as needed |
; Enter With : BASIC CPU Register 20H = requested function code (00...255) |
; registers used varies by function (TAKE NOTE: when this table |
; is called via MCSBASIC, r0 is copied to acc) |
; Exits With : depends on called function |
; Remarks : "plug-in" needed functions into the table below. The function |
; call will be vectored to whatever proc is "plugged in" at |
; the numbered "function code" slot position. The "Vector" |
; from the related procedure should be copied from the function |
; source code to the chosen slot. The table may be shortened or |
; added to as needed (CAUTION!! Don't jump beyond last vector) |
;-----------------------------------------------------------------------------|
func_table_5: PROC ; function table 5 (MCP23017 I2C discrete IO expander functions)
ljmp MCP23017_vrp ; 00 VRP functions remote $r0 device...
ljmp MCP23017_read ; 01 @r4r5 <- all MCP23017 IC2 device...
ljmp MCP23017_write ; 02 @r4r5 -> all MCP23017 IC2 device regs...
ljmp MCP23017_register_get ; 03 r2 <- MCP23017 I2C device $acc...
ljmp MCP23017_register_set ; 04 r2 -> MCP23017 I2C device $acc...
ljmp MCP23017_bit_get ; 05 r3 <- I2C device $acc reg...
ljmp MCP23017_bit_set ; 06 set I2C device $acc reg...
; etc... up to 255 vectors (jumps)
func_table_5 ENDPROC
;...
 

Attachments

AllyCat

Senior Member
Hi,
..do not use the GOTO command and everything will be fine...
Better to "ban" the use of "GOSUB" (and the stack can't overflow). :)

A "bad" programmer can use GOSUBs in place of GOTOs (to get the same effect) which may soon "overflow the stack" but probably not actually cause any "problems", until they try to use some RETURNs ! So start with GOTOs to teach the basics and when you want to introduce the concept of Subroutines, then use the CALL .. RETURN structure (which IMHO is more explicit terminology).

Remember that at the Assembler / Machine Code level, the "GOTO" (in the form of Jump, Branch, etc.) is the ONLY method of flow control that exists in some micros like the PIC.

Cheers, Alan.
 

tmfkam

Senior Member
Oh dear :(
I had thought that Subroutines were 'better' than coding in a linear fashion, where the program simply ran from top to bottom requiring the use of jumps to branch execution. Early Psion OPL was done thus, large programs using that were tricky at times to follow. A semi relational database written in OPL wasn't easy.

I then moved to Delphi where everything was placed into procedures. So much easier to follow.

Then to PicAxe (and PICs) where I use subroutines like confetti, any code repeated more than twice is placed into a sub. I'll have to rethink my *style*.!

Of course, the trick is not to nest too many subroutines. Recursion is out, but otherwise I like the structure tha subroutines give the program.
 

inglewoodpete

Senior Member
Hi,

Better to "ban" the use of "GOSUB" (and the stack can't overflow). :)

A "bad" programmer can use GOSUBs in place of GOTOs (to get the same effect) which may soon "overflow the stack" but probably not actually cause any "problems", until they try to use some RETURNs ! So start with GOTOs to teach the basics and when you want to introduce the concept of Subroutines, then use the CALL .. RETURN structure (which IMHO is more explicit terminology).

Remember that at the Assembler / Machine Code level, the "GOTO" (in the form of Jump, Branch, etc.) is the ONLY method of flow control that exists in some micros like the PIC.

Cheers, Alan.
Stirring the pot Alan? My suggestion would be to adhere to the rules of the chosen programming language and limitations of the hardware and learn, learn, learn from your mistakes, mistakes, mistakes! ;)
 

premelec

Senior Member
I don't know what materials are available for beginners - I think perhaps street directions mazes could sensitize, by analogy, to some of the pitfalls of going without returning or jumping into dead end... could have student having to stop by various 'stores' in predetermined order to purchase things with limited $ [only so many $ or returns!]. Could be a game that teaches in a more familiar manner some of the ways of the code... Put some fun into it... ;-0
 

BESQUEUT

Senior Member
Hi,

Better to "ban" the use of "GOSUB" (and the stack can't overflow). :)

A "bad" programmer can use GOSUBs in place of GOTOs (to get the same effect) which may soon "overflow the stack" but probably not actually cause any "problems", until they try to use some RETURNs ! So start with GOTOs to teach the basics and when you want to introduce the concept of Subroutines, then use the CALL .. RETURN structure (which IMHO is more explicit terminology).

Remember that at the Assembler / Machine Code level, the "GOTO" (in the form of Jump, Branch, etc.) is the ONLY method of flow control that exists in some micros like the PIC.

Cheers, Alan.
I do notre agree.
Are you able To explain to a beginner what is a stack overflow ? Not me ...
When I explain what is a loop structure, it seems more readable To write:
Do
...
Loop
Than
Main:
...
Goto Main
 

AllyCat

Senior Member
Hi,

Ah, as "Sir Hippy" wrote in post #12 of a thread yesterday (with an explanation why). ;)
Code:
......
GOTO PowerOnReset
SendByte:
......
Of course we all know that what he really should have written is : :)
Code:
GOSUB PowerOnReset
End
Cheers, Alan.
 

hippy

Technical Support
Staff member
Of course we all know that what he really should have written is : :)
Code:
GOSUB PowerOnReset
End
That's an interesting point. And I would agree you are correct.

I would however argue it would be even better to have started with -
Code:
PowerOnReset:
  Gosub TheActualProgram
  End
Seeing as the "PowerOnReset" label should identify the place the PICAXE starts at when power is turned on or the PICAXE resets. And that would technically apply even with my GOTO version; any "PowerOnReset" label must be before the first line of executable code.

From a purist perspective it would be hard to argue you are wrong, so one would have to accept it is right.

The best argument for what I had, perhaps the only one, is what was written was 'purist code' but optimised. The counter would be that the compiler should be left to do the optimisation, a programmer should not take it upon themselves to optimise.

And the counter there is; "true, but we know it doesn't. If one wants that kind of optimisation one has to do it oneself".

So, accepting that purist code is best, where does that leave us when less than purist code is actually better ?

I think it comes down to how one measures it, what one's criteria is for best or better, that there's no absolute there.
 

BESQUEUT

Senior Member
AllyCat said:
Of course we all know that what he really should have written is : :)
Code:
GOSUB PowerOnReset
End
That's an interesting point. And I would agree you are correct.
He should...
But the fact is that he did not... because he is a beginner,
and probably he started with :
Main
GOTO Main

a programmer should not take it upon themselves to optimise.

And the counter there is; "true, but we know it doesn't. If one wants that kind of optimisation one has to do it oneself".

So, accepting that purist code is best, where does that leave us when less than purist code is actually better ?

I think it comes down to how one measures it, what one's criteria is for best or better, that there's no absolute there.
As a "purist" I agree that it can be a very interesting challenge to optimize size and/or speed...
A challenging code can be unreadable.
A professionnal code should be readable.
And if I really need speed, I can use a T4...
 
Top