FloodFill Routine keeps Freezing
» > >
»
» View previous topic :: View next topic  
  • FloodFill Routine keeps Freezing
  • 11 May 2011 07:57:49 am
  • Last edited by ZippyDee on 11 May 2011 04:13:53 pm; edited 3 times in total
Hi, I'm quite new to ASM, and I finally finished this floodfill routine that uses no stack whatsoever...or so I thought. It seems to not be working as smoothly as I planned. It keeps freezing, and when I debug in WabbitEmu it seems that it's freezing at $0CAF, on the line "jp $0B65"

Here's my hopefully-not-too-hard-to-read code:

Code:

   #include ti83plus.inc
   #define ProgStart $9D95
   #define BUFF1 plotSScreen      ; Location of drawing buffer 1
   #define BUFF2 0               ; Location of drawing buffer 2 (for grayscale implementation)
   .org ProgStart-2
   .db $BB, $6D

InitTestData:
   ;; INIT DATA FOR TESTING
      ld hl, 20
         push hl
            push hl
            ld hl, 1
   
PROGRAM_START:
   ;; L contains the fill color
   ;; stack:
   ;;      [0]: y-coordinate
   ;;      [1]: x-coordinate
   
   
      ; Get the fill color and save it to (color)
         ld a, l
         ld (color), a
   
      ; Calculate the byte address for the pixel
      ;   and save it to (addr)
      pop hl
      ld a, 64
      cp l
   pop de
   ret c
      push de
      ld d, 0
      ld e, l
      add hl, hl
      add hl, de
      add hl, hl
      add hl, hl
   pop de
   ld a, 96
   cp e
   ret c
   ld d, 0
   srl e
   srl e
   srl e
   ld a, e
   ld (xbyte), a   ;save the byte column to (xbyte)
   add hl, de
   ld (addr), hl
   
      ; Calculate the bitmask for the pixel
      ;   and save it to (mask)
   and 7
   ld b, a
   ld a, $80
   jr z, ___skiploop
___loop:
   rrca
   djnz ___loop
___skiploop:
   ld (mask), a
   
      ; make sure the starting color is not the fill color
   ld de, BUFF1
   add hl, de
   and (hl)
   cp 0
   jr z, ___zero   
   ld a, 1
___zero:
   ld (icolor), a
   ld b, a
   ld a, (color)
   cp b
   ret z   ; return if the starting point is the fill color
   call TurnByRule
   call Loop
      bcall(_getkey) ;just to pause it...
   ret
   
   
Loop:
   call GetBoundsPainted
   ld a, b
   cp 1
   jp nz, _1bound
   cp 2
   jp nz, _2bounds
   cp 3
   jp nz, _3bounds
   cp 4
   jp nz, _4bounds
_0bounds:
   call Paint
   jp EndLoop
_4bounds:
   call Paint
   ret
_3bounds:
   call GetAddr_Mask
   or (hl)
   ld (hl), a
      ;remove the mark, and reset rule and findpassage to defaults
   xor a
   ld (m_mask),a
   ld (bool), a
   ld a, $0F
   jp EndLoop
_2bounds:
   ; jesus, this one will be tough...
   ld a, (m_mask)
   cp 0
   jr nz, ___skip_place_mark
   ld a, (bool)
   and 1
   cp 0
   jr nz, ___skip_place_mark
   ld (findpassage), a
   ld a, (mask)
   ld (m_mask), a
   ld hl, (addr)
   ld (m_addr), hl
   ld a, (dir)
   ld (m_dir), a
___skip_place_mark:
   call MoveByRule
   ld a, (m_mask)
   cp 0
   jr nz, ___null_mark
   ld b, a
   ld a, (mask)
   cp b
   jp nz, Loop
   ld hl, (m_addr)
   ld a, h
   ld b, l
   ld hl, (addr)
   cp h
   jp nz, Loop
   ld a, b
   cp l
   jp nz, Loop
   ld a, (dir)
   ld b, a
   ld a, (m_dir)
   cp b
   jr z, ___null_mark
   ld (dir), a
   ld a, (bool)
   xor 1
   ld (bool), a
   xor a
   ld (findpassage), a
___null_mark:
   xor a
   ld (m_mask), a
   ld a, (bool)
   and 1
   cp 0
   call nz, Paint
   jp Loop
_1bound:
   ld a, (bool)
   and 1
   jr z, __1bound_else
   ld a, 1
   ld (findpassage), a
   jr EndLoop
__1bound_else:
   ; get opposite corners...
   ; if both are open
   ld a, (dir)
   ld b, 4
   dec a
      push af
___find_bound:
   pop af
   inc a
      push af
         push bc
         call GetPixelInDir
         ld b, a
         ld a, (icolor)
         cp b
      pop bc
      jr nz, ___found
      djnz ___find_bound
   pop af
   xor a
   ret
___found:
   pop af
   inc a
   inc a
   call GetDirOffset
      push af
         push de
         ex de, hl
         dec a
         call GetDirOffset
         ld a, h
         or d
         ld d, a
         ld a, l
         or e
         ld e, a
         call GetPixel
         ld b, a
         ld a, (icolor)
         cp b
      pop hl
   pop af
   jr nz, EndLoop
   inc a
   call GetDirOffset
   ld a, h
   or d
   ld d, a
   ld a, l
   or e
   ld e, a
   call GetPixel
   ld b, a
   ld a, (icolor)
   cp b
   call z, Paint
EndLoop:
   call MoveByRule
   jp Loop
   
   
Paint:
   ;;##################
   ;;################## This routine is never called for some reason
   ;;##################
   ;; Paints the current pixel the fill color
   ld a, (color)
   cp 0
   ;jr z, __paint_off
   call GetAddr_Mask
   or (hl)
   ld (hl), a
   bcall(_GRBufCpy)   ; just for testing purposes.
   ret
__paint_off:
   call GetAddr_Mask
   xor $FF
   and (hl)
   ld (hl), a
   bcall(_GRBufCpy)   ; again just for testing purposes.
   ret


MoveByRule:
   ;; Move to next location based on rule
   ;; OUT:
   ;;   B is 0 if no tile was found to move to. Otherwise, non-zero.
   call GetCurPixel
   ld b, a
   ld a, (icolor)
   cp b
   jr nz, ___move_dir   ; if the current pixel is filled, just move foward
   ld a, (dir)
   call GetPixelInDir
   ld b, a
   ld a, (icolor)
   cp b
   jr nz, ___no_move   ; if the pixel at dir is filled, don''t move
      ; check the corner between the pixel at dir and the pixel to the side specified by rule
      ; if the pixel is on, just move forward
      ; otherwise move to that pixel
   ld a, (bool)
   and 1
   ld c, a
   ld a, (dir)
   call GetDirOffset
      push de
      inc a
      sub c
      sub c
      call GetDirOffset
   pop hl
      push af
      ld a, h
      or d
      ld d, a
      ld a, l
      or e
      ld e, a
         push de
         call GetPixel
         ld b, a
         ld a, (icolor)
         cp b
      pop de
   pop af
   jr nz, ___move_dir
      push af
      call GetPixelAddr
      ld (mask), a
      ld a, d
      ld (xbyte), a
      ld (addr), hl
   pop af
   ld (dir), a
   call TurnByRule
   ld b, 1
   ret
___move_dir:
   ld a, (dir)
   call GetDirOffset
   call GetPixelAddr
   ld (mask), a
   ld a, d
   ld (xbyte), a
   ld (addr), hl
   ld a, (bool)
   and 1
   ld b, a
   ld a, (dir)
   inc a
   sub b
   sub b
   call remap_dir
   ld (dir), a
   call TurnByRule
   ld b, 1
   ret
___no_move:
   ld b, 0
   ret
   

TurnByRule:
   ;; OUT:
   ;;   B is 0 if no tile was found to turn to. Otherwise non-zero.
   ld b, 4
___turn_loop:
      push bc
      ld a, (dir)
      call GetPixelInDir
      ;if pixel is on, dec
      ld b, a
      ld a, (icolor)
      cp b
      jr z, __chk_side_turn
      ld a, (bool)
      and 1
      ld b, a
      ld a, (dir)
      dec a
      add a, b
      add a, b
      call remap_dir
      ld (dir), a
   pop bc
   djnz ___turn_loop
   ret
__chk_side_turn:
   ;jump from push bc
      ld a, (bool)
      and 1
      ld b, a
      ld a, (dir)
      inc a
      sub b
      sub b
      call remap_dir
         push af
         call GetPixelInDir
         ld b, a
         ld a, (icolor)
         cp b
      pop af
   pop bc
   ret nz
   ld (dir), a
   djnz ___turn_loop
   ret
   
   
remap_dir:
   ;; Maps the value in A to the range of 0 <= A < 4
   cp 4
   ret nc
   cp 128
   jr c, ___add
   sub 4
   jr remap_dir
___add:
   add a, 4
   jr remap_dir
   
   
GetDirOffset:
   ;; IN:
   ;;   A contains the direction
   call remap_dir
   ld b, a
   xor a
   cp b
   jr z, __dir_right
   inc a
   cp b
   jr z, __dir_down
   inc a
   cp b
   jr z, __dir_left
__dir_up:
   ld a, b
   ld de, $0100
   ret
__dir_right:
   ld a, b
   ld de, $0001
   ret
__dir_down:
   ld a, b
   ld de, $FF00
   ret
__dir_left:
   ld a, b
   ld de, $00FF
   ret
   
   
GetPixelInDir:
   ;; IN:
   ;;   A contains the direction
   call GetDirOffset
   jp GetPixel


GetAddr_Mask:
   ;; OUT:
   ;;   HL contains the addr of the pixel
   ;;   A contains the mask of the pixel
   ld hl, (addr)
   ld de, BUFF1
   add hl, de
   ld a, (mask)
   ret


GetBoundsPainted:
   ;; OUT:
   ;;   B contains the number of painted boundaries
   ;;   bits 0-3 of C contain which bounds are painted (0:right,1:left,2:top,3:bottom)
   ld bc, 0
      push bc
      ld de, $0001
      call GetPixel
      ld b, a
      ld a, (icolor)
      cp b
      jr nz, ___skip1
   pop bc
   inc b
   ld a, 1
   or c
   ld c, a
      push bc
___skip1:
      ld de, $00FF
      call GetPixel
      ld b, a
      ld a, (icolor)
      cp b
      jr nz, ___skip2
   pop bc
   inc b
   ld a, 2
   or c
   ld c, a
      push bc
___skip2:
      ld de, $0100
      call GetPixel
      ld b, a
      ld a, (icolor)
      cp b
      jr nz, ___skip3
   pop bc
   inc b
   ld a, 4
   or c
   ld c, a
      push bc
___skip3:
      ld de, $FF00
      call GetPixel
      ld b, a
      ld a, (icolor)
      cp b
   pop bc
   ret nz
   inc b
   ld a, 8
   or c
   ld c, a
   ret
   
   
GetCurPixel:
   ;; OUT:
   ;;   A contains the color of the current pixel
   ld hl, (addr)
   ld de, BUFF1
   add hl, de
   ld a, (mask)
   and (hl)
   cp 0
   ret z
   ld a, 1
   ret


GetPixelAddr:
   ;; IN:
   ;;    D contains y offset
   ;;    E contains x offset
   ;; OUT:
   ;;   HL contains the addr of the pixel
   ;;   A contains the mask for the pixel, or 0 if the pixel is off screen
   ;;   D contains the xbyte for the pixel
   ld hl, (addr)
__x_offset:
   ld a, (mask)
   ld b, e
   ld e, a
   ld a, b
   cp 0
   jr z, __y_offset
   cp 1
   ld a, (xbyte)
   jr z, __shiftRight
   rlc e
   jr nc, __chk_side
   dec a
   jr __chk_side
__shiftRight:
   rrc e
   jr nc, __chk_side
   inc a
__chk_side:
   cp 12
   jr c, __edgeaddr
__y_offset:
   push af
      ld a, d
      cp 0
      jr z, __return_addr
      cp 1
      jr z, __shiftUp
      ld bc, -24
      add hl, bc
      jr __chk_top
__shiftUp:
      ld bc, 12
      add hl, bc
__chk_top:
         push hl
         ld bc, -768
         add hl, bc
      pop hl
   pop af
   jr c, __edgeaddr
__return_addr:
      push af
      ld a, e
   pop de
   ret
__edgeaddr:
   ld a, 0
   ret
   
   
GetPixel:
   ;; IN:
   ;;    D contains y offset
   ;;    E contains x offset
   ;; OUT:
   ;;   A contains the color of the pixel (1 or 0)
   call GetPixelAddr
   cp 0
   jr z, __edgepxl
__getpxl:
   ld de, BUFF1
   add hl, de
   and (hl)
   ret
__edgepxl:
   ld a, (color)      ; pixel is off-screen, so return (color)
   ret


addr:      ; Initial address (no buffer address added) of the byte containing the current pixel (Y*12+X/8)
   .dw 0
mask:      ; Bitmask for the current pixel
   .db 0
xbyte:      ; The byte column containing the pixel (basically X/8)
   .db 0
dir:
   .db 0

m_addr:
   .dw 0
m_mask:
   .db 0   ;0 means no mark
m_xbyte:
   .db 0
m_dir:
   .db 0
   
bool:   ; bit 0=rule ;;;;;I dunno why but I had this and findpassage as the same thing before. I still haven''t taken all the "and 1" lines out from when I was testing rule...
   .db 0
findpassage:
   .db 0
color:      ; The fill color (currently 0 or 1. If I implement grayscale it will be 0-3)
   .db 1
icolor:
   .db 0   ; The color of the starting fill point
   
.end


I wouldn't be surprised if it's something reeeeeally stupid. I'm new to ASM, so I'm sure I made multiple mistakes.

Thanks so much in advance!
-Zippy Dee


EDIT: I edited the code to what I have now. The "Paint" routine is never called, and I'm not sure why...
There's something about Tuesday...

Pushpins 'n' stuff...
Oops, please put your code in code tags. also, please tab your code.
EDIT: I cee, done Smile
Sorry, I mistyped the code tag. Fixed now.

Edit: I think I found one mistake already... I think in the GetBoundsPainted routine the jr nz, $+9 should be jr nz, $+7. But that still doesn't fix it...
There's something about Tuesday...

Pushpins 'n' stuff...
A few things bother me here:

1) You should always use labels instead of PC-indexed local jumps; your assembler knows what they are for a reason, and can save you the trouble of miscounting opcode bytes. Plus, I find that well-named labels act as a great guide to understanding program flow when I come back to my code later, as a bit of a second set of comments.

2) Regarding "$0CAF, on the line "jp $0B65": TI-83+/84+ programs are executed at $9D95 and up, so do you mean $0CAF+$9D95? Or is it somehow getting into the TI-OS code within $0000-$3FFF and getting stuck there?

3) The labels even for small jumps again. Smile Another tip that has made my code so, so much more readable and has helped me avoid infinite stack issues is to indent further and further as I push, one extra tab per push, then unindent (one fewer tab) as I pop.

4) Use Doors CS. You could cut out some code there with the iGetPixel routine. Also, you could then use the iFastCopy routine, which is oh so much faster than GrbufCpy_V.

I haven't spotted your problem, but I haven't gone through your code thoroughly yet.
Thanks for all the suggestions!

Although all the routines Doors CS offers are almost undoubtedly much better than anything I could write, I've been trying to write as much of the code from scratch as I can just so I can get used to the mindset required for ASM. It can be quite overwhelming at times, and I'd like to get past that. For me, the only way to accomplish that is to learn to do it myself.

As for jumping to $0CAF, it's going into the OS code somehow and freezing on that line. I have no idea what could be causing that...
There's something about Tuesday...

Pushpins 'n' stuff...
I notice that your only bcalls seem to be the grbufcpy_v's, which I hope you'll change into call ifastcopy's. I'd definitely first switch your jr $+N to jr labelname, since an incorrectly-aligned relative jump could turn into an accidental jump or call far away. Is it possible you're pushing and popping unevenly, thus ending up returning with one or more too few items popped? That can be a classic cause of suddenly executing in the wrong place. I'd try the indentation and see if it helps you track something like that down. If you're still struggling this evening when I finish my work for the semester, I'd be happy to help you look for it.
I'll make those changes and I'll look at all my pushes and pops. That does sound like a likely cause.

My only question about indenting comes in when I have multiple labels that are popping the same pushed item in different conditions? What's a good way to deal with that?


EDIT: This could possibly help anyone else understand my code. Here's my pseudocode that I wrote this based off of:

Code:


This algorithm:
http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29

RULE = right
MARK = null
MARKDIR = null
FINDPASSAGE = false
-----

if 4 bounds painted
        paint cur
        stop
else if 3 bounds painted
        MARK = null
        FINDPASSAGE = false
        RULE = right
        paint cur
        move to open bound
       
//#######################   
else if 2 bounds painted
        if MARK == null && RULE == right
                MARK = cur
                MARKDIR = dir
                FINDPASSAGE = false
        move based on RULE               //after moving
                                        //set "dir" to the next direction
                                        //according to RULE (right hand rule or left hand rule)
        if cur == MARK
                if dir == MARKDIR
                        MARK = null
                else
                        RULE = left
                        dir = MARKDIR
                        MARK = null
                        FINDPASSAGE = false
                       
        if MARK == null && RULE == right
                paint cur
//######################
               
else if 1 bound painted
        if RULE == left  //then we''re in a loop, and this triggers the second stage
                FINDPASSAGE = true
        else
                if both opposite corners are open && MARK == null
                        paint cur
        move base on RULE
else if 0 bounds painted
        if RULE == left
                FINDPASSAGE = true
        paint cur
        move anywhere :P
       
       
        //_0_            how do you follow the right hand rule? Which is next?
        //_#_
        //___
//first way
        //_#0        //If the current pixel is painted before moving, move here
        //_#_
        //___
//second way
        //___        //but if the pixel is NOT painted before moving, move around to the
        //_#0        //next edge because going to the corner would make it now have
        //___        //no borders.


In my actual code, "mark == null" is true if (m_mask) == 0.
There's something about Tuesday...

Pushpins 'n' stuff...
Have you tried tracing it out with breakpoints in WabbitEmu to try to narrow it down further?
I've tried a bit, but it's really hard to place breakpoints without seeing labels to tell me which part I'm placing the breakpoint in. Also, the mac version of wabbitemu doesn't allow you to see all of the disassembly, so I can only look at a few lines at a time without using the GOTO feature...
There's something about Tuesday...

Pushpins 'n' stuff...
If you're at least using the Doors CS SDK, it generates a listing file with full addresses that you can use to goto and set breakpoints as necessary.
Oh? Well I haven't set up DCS SDK yet, but I'll do that now! I didn't know it had that feature built in! That will certainly help for debugging.
There's something about Tuesday...

Pushpins 'n' stuff...
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
FloodFill Routine keeps Freezing
»
» View previous topic :: View next topic  
Page 1 of 1
» All times are UTC - 5 Hours
 
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

 

Advertisement