Re: filling area by color atack safety

Michael S <already5chosen@yahoo.com> writes:

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.

Slower with some shapes, faster in others.  In any case
the code was written for clarity of presentation, with
no attention paid to low-level performance.

Is it the same algorithm?

Sorry, the same algorithm as what?  The same as Malcolm's?
Definitely not.  The same as my other posting that does
not do dynamic reallocation?  Yes in the sense that if the
allocated array is large enough to begin with then no
reallocations are needed.

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++.

The code uses a variably modified type, not a variable length
array.  Again, the choice is for clarity of presentation.  If
someone wants to get rid of the variably modified types, it's
very easy to do, literally a five minute task.  Anyway the
interface is poorly designed to start with, there are bigger
problems than just whether a variably modified type is used.
(I chose the interface I did to approximate the interface
used in Malcolm's code.)

If someone wants to use the functionality from C++, it's
easy enough to write a C wrapper function to do that.
IMO C++ has diverged sufficiently from C so that there
is little to be gained by trying to make code interoperable
between the two languages.