Path: ...!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 Date: Tue, 19 Mar 2024 21:40:22 -0700 Organization: A noiseless patient Spider Lines: 96 Message-ID: <86o7b9ms7d.fsf@linuxsc.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="7a780175fd21d30328a8a78d1217a04c"; logging-data="1393396"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/P9VrgtG8dH8gUyLB5ITzK5h6AunJ34wQ=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:ERN0vL/FWgwOVvHbui0aUPd/H+w= sha1:H4odZi+3AZLY7Hq7uQJybszm6dQ= Bytes: 4463 Michael S writes: > On Mon, 18 Mar 2024 22:42:14 -0700 > Tim Rentsch wrote: > >> Tim Rentsch 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. Slower with some shapes, faster in others. In any case the code was written for clarity of presentation, with no attention paid to low-level performance. > Is it the same algorithm? Sorry, the same algorithm as what? The same as Malcolm's? Definitely not. The same as my other posting that does not do dynamic reallocation? Yes in the sense that if the allocated array is large enough to begin with then no reallocations are needed. > 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++. The code uses a variably modified type, not a variable length array. Again, the choice is for clarity of presentation. If someone wants to get rid of the variably modified types, it's very easy to do, literally a five minute task. Anyway the interface is poorly designed to start with, there are bigger problems than just whether a variably modified type is used. (I chose the interface I did to approximate the interface used in Malcolm's code.) If someone wants to use the functionality from C++, it's easy enough to write a C wrapper function to do that. IMO C++ has diverged sufficiently from C so that there is little to be gained by trying to make code interoperable between the two languages.