Path: csiph.com!news.swapon.de!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 22:42:14 -0700
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <865xxiok09.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="098ab4a777b232b781bcababf6a04f60"; logging-data="717773"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1931tgXXeetEsSA5aU0KlU6JXZ3K0fgvSk="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:ZYkU+PYcNko0ymjxLbhM/Vs664M= sha1:S7WrDr+F7cqO/i6LaUDgIrJXAlk=
Xref: csiph.com comp.lang.c:383732

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[...]

Here is the refinement that uses a resizing rather than
fixed-size buffer.


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},  };
  UI     k      =  0;
  UI     n      =  17;
  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;
                todo[ k++ ] = q;
            }

            if(  j-k < 3  ){
                Index new_n = n+n/4;
                Index new_j = new_n - (n-j);
                Point *t = realloc( todo, new_n * sizeof *t );
                if(  !t  ){  k = 0;  break;  }
                memmove( t + new_j, t + j, (n-j) * sizeof *t );
                todo = t,  n = new_n,  j = new_j;
            }
        }
    }

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