Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #384296

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

Show key headers only | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:01 -0700
  Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 19:33 +0300
    Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 10:24 -0700
      Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:04 +0300
      Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-05 17:30 +0300
        Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-10 19:47 -0700
          Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-11 15:20 +0300
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:06 -0700
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:55 -0700
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:09 -0700
              Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-12 11:13 +0300
                Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 08:30 -0700
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:38 -0700
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:43 -0700
            Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-12 11:59 -0700
              Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 20:26 +0300
                Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 10:54 -0700
                Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 23:11 +0300
              Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-17 10:47 -0700
                Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-17 22:41 +0300
                Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-19 14:59 -0700
                Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-20 21:10 +0300
                Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-25 17:56 +0300
                Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-05-03 18:33 +0300
                Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-15 09:57 -0700

csiph-web