Re: filling area by color atack safety

fir <fir@grunge.pl> writes:

i was writing simple editor (something like paint but more custom for
my eventual needs) for big pixel (low resolution) drawing
>
it showed in a minute i need a click for changing given drawed area of
of one color into another color (becouse if no someone would need to
do it  by hand pixel by pixel and the need to change color of given
element is very common)
>
there is very simple method of doing it - i men i click in given color
pixel then replace it by my color and call the same function on
adjacent 4 pixels (only need check if it is in screen at all and if
the color to change is that initial color
>
int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
unsigned new_color)
{
  if(old_color == new_color) return 0;
>
  if(XYIsInScreen( x,  y))
  if(GetPixelUnsafe(x,y)==old_color)
  {
    SetPixelSafe(x,y,new_color);
    RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
    RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
    RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
    RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
    return 1;
  }
>
  return 0;
}
>
it work but im not quite sure how to estimate the safety of this  -
incidentally as i said i use this editor to low res graphics  like
200x200 pixels or less, and it is only a toll of private use,
yet i got no time to work on it more than 1-2-3 days i guess but still
>
is there maybe simple way to improve it?

As others have explained using simple recursion like this
runs the risk of producing a stack overflow.

Here is a short routine that uses allocated memory rather than
recursion, and so does not have the stack overflow risk that
the above recursive routine does.

The code below uses a slightly different interface to access
the pixel field but I expect you can see how to adapt it to
your interface.

Also the code uses a variably modified type in two places.  It
should be easy to change the code to use ordinary types rather
than variably modified types if it's important to do that in
your environment.  And it may be the case that changing to use
a different interface to access and change the pixel field will
get rid of the variably modified types so that they wouldn't be
needed anyway.

Oh, before I forget.  If someone doesn't like using a single
fixed-size allocated area, it isn't hard to change the code
so that the allocated area grows as needed (and starting with
a smaller size, presumably).  I leave doing that as an
exercise.

The code:

#include <assert.h>

typedef     unsigned char               Color;
typedef     unsigned int                UI;
typedef     struct { UI x, y; }         Point;
typedef     unsigned int                Index;

static  _Bool  change_it( UI w, UI h, Color [w][h], Point, Color, Color );

void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color new ){
  static const Point deltas[4] =  {  {1,0}, {0,1}, {-1,0}, {0,-1},  };
  Index  k      =  0;
  Index  n      =  (w+h) *17 /16 +10;
  Point *todo   =  malloc( n * sizeof *todo );

    if(  todo && change_it( w, h, pixels, p0, old, new )  )  todo[k++] = p0;

    while(  k > 0  ){
        Index j = n-k;
        memmove( todo + j, todo, k * sizeof *todo );
        k = 0;

        while(  j < n  ){
            Point p = todo[ j++ ];
            for(  Index i = 0;  i < 4;  i++  ){
                Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
                if(  ! change_it( w, h, pixels, q, old, new )  )  continue;
                assert(  j > k  );
                todo[ k++ ] = q;
            }
        }
    }

    free( todo );
}

_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color new ){
    if(  p.x >= w  ||  p.y >= h  ||  pixels[p.x][p.y] != old  )  return  0;
    return  pixels[p.x][p.y] = new,  1;
}