Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety - worst memory size Date: Thu, 11 Apr 2024 21:06:38 -0700 Organization: A noiseless patient Spider Lines: 78 Message-ID: <86zftzz0kx.fsf@linuxsc.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com> <86jzlrk0f6.fsf@linuxsc.com> <20240405173033.00006145@yahoo.com> <868r1k1uq8.fsf@linuxsc.com> <20240411152033.00007173@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 12 Apr 2024 06:06:41 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c97bd3546ab5d223656b076d0b7c627f"; logging-data="2281593"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ebzAURzLqGmFCp9xpLCMAN2rXshh69/w=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:xcvx529gBNR8LEyHM1BUM3q9eyE= sha1:JKiUBgrAXffYJqCtYS192rurUMM= Xref: csiph.com comp.lang.c:384296 Michael S writes: (I'm replying in pieces.) > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch 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; }