forums.ps2dev.org Forum Index forums.ps2dev.org
Homebrew PS2, PSP & PS3 Development Discussions
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Stack Size / Recursive scripts

 
Post new topic   Reply to topic    forums.ps2dev.org Forum Index -> PSP Development
View previous topic :: View next topic  
Author Message
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Fri Aug 14, 2009 12:52 pm    Post subject: Stack Size / Recursive scripts Reply with quote
Hi Guys,
I'm trying to implement a 2D recursive flood fill algo found on Wikipedia
in the first example here:
http://en.wikipedia.org/wiki/Flood_fill

I think I've implemented it right for the PSP, but it crashes when this function is called.
I call it with image coordinates well inside the image area, and expect it
to fill the area outside of a wire polygon.

Code:

void floodfill(int x, int y, u32 target, u32 new_color) {

if (getPixelImage(x, y, polygon) != target) {return;}
if (getPixelImage(x, y, polygon) == new_color) {return;}
putPixelImage(new_color, x, y, polygon);

if (x > 1 && x < 479) {
if (y > 1 && y < 271) {
floodfill(x-1, y, 0, 0xFFABCDEF);
floodfill(x+1, y, 0, 0xFFABCDEF);
floodfill(x, y+1, 0, 0xFFABCDEF);
floodfill(x, y-1, 0, 0xFFABCDEF);
}}

}



I assume from what I read on the net that this is because of stack overflow.

When I add this to my main.c file:
PSP_MAIN_THREAD_STACK_SIZE_KB(sizeinkb); // sizeinkb = 1024, 2048, etc.
The program won't run at all, no matter what value I use.
Could this be used in a thread or am I barking up the wrong tree?

Cheers, Art.
_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Fri Aug 14, 2009 3:56 pm    Post subject: Reply with quote
Your recursion is infinite - look at these two lines:

Code:
floodfill(x-1, y, 0, 0xFFABCDEF);
floodfill(x+1, y, 0, 0xFFABCDEF);


A recursion on the first line there when it causes a recursion on the second line is the exact same pixel as you started with... meaning you're recursion generated the original pixel, which is then fed back in for recursion.
Back to top
View user's profile Send private message AIM Address
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Fri Aug 14, 2009 5:38 pm    Post subject: Reply with quote
J.F. wrote:
Your recursion is infinite - look at these two lines:


I don't follow why you say it is infinite.
I forgot I hard coded the colour in those lines though.. so:
Code:
floodfill(x-1, y, 0, new_color);
floodfill(x+1, y, 0, new_color);


Before it makes it to the same pixel again,
the function should have already returned because a prior IF statement checks if
the colour was already changed for that pixel.

Code:

if (getPixelImage(x, y, polygon) == new_color) {return;}

_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Sat Aug 15, 2009 12:39 am    Post subject: Reply with quote
Yes, if the get pixel check does work, that should keep the recursion from being infinite. Better check those routines... maybe the alpha is getting stripped or something similar, which would then make the color check fail which would then allow infinite recursion.
Back to top
View user's profile Send private message AIM Address
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Tue Aug 18, 2009 10:30 am    Post subject: Reply with quote
I pretty much narrowed it down to stack overflow by limiting the number of times the function can call itself.

If I limit it to 1000 times, it works, and partialy fills the screen
(although 1000 pixels is less than three lines on the PSP screen).

Now since I can't add this line:
Code:

PSP_MAIN_THREAD_STACK_SIZE_KB(fnhuge);


without breaking it, I wonder where the stack size is defined in the first place so I can change it there?
and what is the limit it can be set to?
Art.
_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Tue Aug 18, 2009 12:12 pm    Post subject: Reply with quote
Are you also setting the heap size? You might be using heap size max, which would prevent you from making the stack size larger. Leave enough free memory where you can increase the stack appropriately.
Back to top
View user's profile Send private message AIM Address
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Tue Aug 18, 2009 1:56 pm    Post subject: Reply with quote
I'm not using anything to adjust the heap size.
Should it handle up to 130560 (480x272) recursions?

I found this:
http://psp.jim.sh/pspsdk-doc/pspmoduleinfo_8h.html

Where it looks like this:
Code:

PSP_MAIN_THREAD_STACK_SIZE_KB(size_kb)   unsigned int sce_newlib_stack_kb_size = (size_kb)
PSP_HEAP_SIZE_KB(size_kb)   int sce_newlib_heap_kb_size = (size_kb)

is what you're talking about. What should I set the heap size to?
I find that my programs usually have about 24Mb to play with on a fat
would 20Mb do it?

or to quote yourself
Quote:

I normally use something like "PSP_HEAP_SIZE_KB(-256);", which means gimme everything except for 256 KB.


EDIT.. bummer, it seems it crashes the app if I include these lines with any value in them.

Art.
_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Tue Aug 18, 2009 3:51 pm    Post subject: Reply with quote
You should be able to use those lines... if you can't, there's something wrong, possibly with your toolchain. How old is the toolchain/where did you get it/how are you running the app?
Back to top
View user's profile Send private message AIM Address
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Tue Aug 18, 2009 4:23 pm    Post subject: Reply with quote
Old :)

But I tried it on a 2008 version and it compiled and ran ok,
then did this:
Code:


PSP_MODULE_INFO("AVec", 0x1000, 1, 0);
PSP_MAIN_THREAD_ATTR(0);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024);


and it breaks it :(
It still compiles, but doesn't run.

If I comment out this line
PSP_MAIN_THREAD_ATTR(0);
it runs until it crashes at some stage.
_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Wed Aug 19, 2009 2:06 am    Post subject: Reply with quote
Art wrote:

Code:

PSP_MODULE_INFO("AVec", 0x1000, 1, 0);
PSP_MAIN_THREAD_ATTR(0);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024);



That's old kernel mode homebrew... it should be

Code:

PSP_MODULE_INFO("AVec", 0, 1, 0);
PSP_MAIN_THREAD_ATTR(PSP_THREAD_ATTR_USER);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024);


and if you want to use the extra memory in the Slim, you need to add to the makefile

Code:
BUILD_PRX = 1
PSP_LARGE_MEMORY = 1
Back to top
View user's profile Send private message AIM Address
Jim



Joined: 02 Jul 2005
Posts: 487
Location: Sydney
PostPosted: Wed Aug 19, 2009 6:45 am    Post subject: Reply with quote
Thought experiment:
If you wanted to fill the entire screen, starting bottom right, then following the recursion in my head I see it first drawing all the way to the left, 480 pixels, then moving up 1 line, then drawing all the way to the right, then repeating. Each time it draws a pixel it puts (at least) 5 words on the stack (params+return address). So that would be 480x272x5x4 bytes needed to do the fill. That's about 2.6Mb of stack space.

The problem is that it's just not a very good algorithm. You need to do more than one pixel per recursion.

Jim
_________________
http://www.dbfinteractive.com
Back to top
View user's profile Send private message Visit poster's website
J.F.



Joined: 22 Feb 2004
Posts: 2906
PostPosted: Wed Aug 19, 2009 6:58 am    Post subject: Reply with quote
Or perhaps more constraints on the recursion - maybe only have it recurse over a line at a time. In the end, I think Jim's right - recursion is a bad way to do a flood fill. You might get away with it on a PC where you have nearly infinite memory and a stupidly fast CPU, but such things shouldn't be done on the PSP where you have neither of those.
Back to top
View user's profile Send private message AIM Address
Art



Joined: 09 Nov 2005
Posts: 647
PostPosted: Wed Aug 19, 2009 10:19 am    Post subject: Reply with quote
Quote:

If you wanted to fill the entire screen, starting bottom right, then following the recursion in my head I see it first drawing all the way to the left, 480 pixels, then moving up 1 line, then drawing all the way to the right, then repeating.

Yes, I started at 0,0 and it looked to do that from the top when I limited it to work for only 1000 recursions.
Quote:

Or perhaps more constraints on the recursion - maybe only have it recurse over a line at a time.

If I'm understanding that right, I think there's an answer there somewhere, but you can't make a line independent.
The algo wouldn't get to the end of a line if it crashed into another color,
and you can't make any judgement about a polygon by looking at it one
line at a time.
One line of a sideways number "9" for example doesn't show you which
part you shouldn't fill.

both of you wrote:

That way sux

Yeah I know that's about the dumbest way to do it.
I've tried a few other things though,
the queue method and circular buffer in a while loop I couldn't get working.
This is one I like the look of:
http://alienryderflex.com/polygon_fill/
because I could gather the data as the lines for the wire polygon are drawn.
_________________
If not actually, then potentially.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    forums.ps2dev.org Forum Index -> PSP Development All times are GMT + 10 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group