Re: filling area by color atack safety - worst memory size

Michael S <already5chosen@yahoo.com> writes:

(I'm replying in pieces.)

On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>

Before I do anything else I should correct a bug in my earlier
FIFO algorithm.  The initialization of the variable jx should
read
>
    Index const jx =  used*3 < open  ? k  : j+open/3 &m;

>
I lost track, sorry.  I can not find your code that contains line
similar to this.
Can you point to specific post?

Easier for me just to repost the corrected algorithm.  The
type UC is an unsigned char, the types Index and Count are
size_t (or maybe unsigned long long), the type U32 is a
32-bit unsigned type.

Please excuse any minor glitches, I have done some hand
editing to take out various bits of diagnostic code.

extern Count
fifo_fill( UC *field, Index w, Index h, Point p0, UC old, UC new ){
  Index  const   xm     =  w-1;
  Index  const   ym     =  h-1;

  Index          j      =  0;
  Index          k      =  0;
  Index          n      =  1u << 10;
  Index          m      =  n-1;
  U32           *todo   =  malloc( n * sizeof *todo );
  Index          x      =  p0.x;
  Index          y      =  p0.y;

    if(  !todo || x >= w || y >= h || field[ x+y*w ] != old  )  return  0;

    todo[ k++ ] = x<<16 | y;

    while(  j != k  ){
        Index used  =  j < k  ? k-j  : k+n-j;
        Index open  =  n - used;
        if(  open < used/16  ){
            Index new_n =  n*2;
            Index new_m =  new_n-1;
            Index new_j =  j < k  ? j  : j+n;
            U32 *t      =  realloc( todo, new_n * sizeof *t );
            if(  ! t  )  break;
            if(  j != new_j  )  memcpy( t+new_j, t+j, (n-j) * sizeof *t );
            todo = t,  n = new_n,  m = new_m,  j = new_j,  open = n-used;
        }
        assert(  (k-j&m) == used  &&  open+used == n  );

        Index const jx =  used*3 < open  ? k  : j+open/3 &m;   // here it is!
        while(  j != jx  ){
            if(  (k-j&m) > mm  )  mm = k-j&m;
            U32 p = todo[j];  j = j+1 &m;
            x = p >> 16,  y = p & 0xFFFF;
            if(  x > 0   &&  field[ x-1 + y*w ] == old  ){
                todo[k] = x-1<<16 | y, k = k+1&m, field[ x-1 + y*w   ] = new;
            }
            if(  y > 0   &&  field[ x + (y-1)*w ] == old  ){
                todo[k] = x<<16 | y-1, k = k+1&m, field[ x + (y-1)*w ] = new;
            }
            if(  x < xm  &&  field[ x+1 + y*w ] == old  ){
                todo[k] = x+1<<16 | y, k = k+1&m, field[ x+1 + y*w   ] = new;
            }
            if(  y < ym  &&  field[ x + (y+1)*w ] == old  ){
                todo[k] = x<<16 | y+1, k = k+1&m, field[ x + (y+1)*w ] = new;
            }
        }
    }

    return  free( todo ),  0;
}