Re: filling area by color atack safety

On 19/03/2024 11:18, Michael S wrote:

On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

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

 This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Is it the same algorithm?
 

No. Mine takes horizontal scan lines and extends them, then places the pixels above and below in a queue to be considered as seeds for the next scan line. (It's not mine, but I don't know who invented it. It wasn't me.)
Tim, now what does it do? Essentially it's the recursive fill algorithm but with the data only on the stack instead of the call and the data. And todo is actually a queue rather than a stack.
Now why would it be slower? Probaby because you usually only hit a pixel three times with mine - once below, once above, and once for the scan line itself, whilst you consider it 5 times for Tim's - once for each neighbour and once for itself. Then horizontally adjacent pixels are more likely to be in the same cache line than vertically adjacent pixels, so processing images in scan lines tends to be a bit faster.

Besides, I don't think that use of VLA in library code is a good idea.
VLA is optional in latest C standards. And incompatible with C++.
 

--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm