Path: ...!weretis.net!feeder6.news.weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Tue, 19 Mar 2024 11:57:53 +0000
Organization: A noiseless patient Spider
Lines: 94
Message-ID: <utbuk3$qed7$1@dont-email.me>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com>
 <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 19 Mar 2024 11:57:55 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="7afaabf9fdb4883652af28e583b6382d";
	logging-data="866727"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/xtae04aVcvRLxLimG4EFeDoKY6VH9hgo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:b8yS5hpbXSE7/phVCZTF7z7M1Xw=
In-Reply-To: <20240319131842.00002138@yahoo.com>
Content-Language: en-GB
Bytes: 4487

On 19/03/2024 11:18, Michael S wrote:
> 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.
> Is it the same algorithm?
> 

No. Mine takes horizontal scan lines and extends them, then places the 
pixels above and below in a queue to be considered as seeds for the next 
scan line. (It's not mine, but I don't know who invented it. It wasn't me.)

Tim, now what does it do? Essentially it's the recursive fill algorithm 
but with the data only on the stack instead of the call and the data. 
And todo is actually a queue rather than a stack.

Now why would it be slower? Probaby because you usually only hit a pixel 
three times with mine - once below, once above, and once for the scan 
line itself, whilst you consider it 5 times for Tim's - once for each 
neighbour and once for itself. Then horizontally adjacent pixels are 
more likely to be in the same cache line than vertically adjacent 
pixels, so processing images in scan lines tends to be a bit faster.



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

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm