Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Wed, 20 Mar 2024 10:26:58 -0700
Organization: A noiseless patient Spider
Lines: 71
Message-ID: <86v85glspp.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <utbuk3$qed7$1@dont-email.me> <20240319191859.00004bc8@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="7a780175fd21d30328a8a78d1217a04c";
	logging-data="1703655"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18C3EqQSUanv0Lj1N/umR1ClmL6vKQJ9tc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:4+qIAp48Hx1hiRmF1JIJMyvnZN8=
	sha1:TMtkPCrCoPx4CfGTZpfLjK5dIWg=
Bytes: 3342

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