Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 13:09:08 -0700
Organization: A noiseless patient Spider
Lines: 111
Message-ID: <86h6h3nvyz.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="392b353a6389bc0498ba35815d55dc9d";
	logging-data="387851"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19tnj7cJSUhJZN78pvJXcIp+SHwaIArn3o="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:EWcGZ0TOlAPdy6Y6aZnE/qLYwLQ=
	sha1:h44xnAkcmuFifIBHKThXFYrAWzM=
Bytes: 4904

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