Re: filling area by color atack safety

Michael S <already5chosen@yahoo.com> writes:

[...]

I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...]

Here is a rendition of my latest and fastest refinement.

#include <stdlib.h>

typedef unsigned char UC;
typedef unsigned UI;
typedef unsigned U32;
typedef unsigned long long U64;
typedef struct { UI x, y; } Point;

void
faster_fill( UI w0, UI h0, UC pixels[], Point p0, UC old, UC new ){
  U64   const    w      =  w0;
  U64   const    h      =  h0;
  U64   const    xm     =  w-1;
  U64   const    ym     =  h-1;

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

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

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

    while(  j != k  ){
        U64 used =  j < k  ? k-j  : k+n-j;
        U64 open =  n - used;
        if(  open < used / 16  ){
            U64 new_n = n*2;
            U64 new_m = new_n-1;
            U64 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;
        }

        U64 const jx =  used <= 3*open  ? k  : j+open/3 &m;
        while(  j != jx  ){
            UI p = todo[j];  j = j+1 &m;
            x = p >> 16,  y = p & 0xFFFF;
            if(  x > 0   &&  pixels[ x*h-h + y ] == old  ){
                todo[k] = x-1<<16 | y, k = k+1&m, pixels[ x*h-h +y ] = new;
            }
            if(  y > 0   &&  pixels[ x*h + y-1 ] == old  ){
                todo[k] = x<<16 | y-1, k = k+1&m, pixels[ x*h +y-1 ] = new;
            }
            if(  x < xm  &&  pixels[ x*h+h + y ] == old  ){
                todo[k] = x+1<<16 | y, k = k+1&m, pixels[ x*h+h +y ] = new;
            }
            if(  y < ym  &&  pixels[ x*h + y+1 ] == old  ){
                todo[k] = x<<16 | y+1, k = k+1&m, pixels[ x*h +y+1 ] = new;
            }
        }
    }

    free( todo );
}