Re: filling area by color atack safety

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