Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Michael S Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety Date: Sat, 30 Mar 2024 21:26:57 +0300 Organization: A noiseless patient Spider Lines: 261 Message-ID: <20240330212657.000066e1@yahoo.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <20240319191859.00004bc8@yahoo.com> <86bk79m10l.fsf@linuxsc.com> <20240324202758.00001b75@yahoo.com> <86frwfjs0n.fsf@linuxsc.com> <20240325012844.0000685b@yahoo.com> <20240326185218.00005397@yahoo.com> <86ttkoi28k.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Injection-Date: Sat, 30 Mar 2024 18:27:05 +0100 (CET) Injection-Info: dont-email.me; posting-host="aeee1c39536db793850074caaed802ee"; logging-data="1188437"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18C0X8wF3cWUhdmlgqxd35dPClLv82FmsE=" Cancel-Lock: sha1:2yQyCjMPEjp8TCo2X/jZ/S0E5dc= X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32) Bytes: 9285 On Sat, 30 Mar 2024 00:54:19 -0700 Tim Rentsch wrote: > Michael S writes: > > [...] > > > The most robust code that I found so far that performs well both > > with small pictures and with large and huge, is a variation on the > > same theme of explicit stack, may be, more properly called trace > > back. It operates on 2x2 squares instead of individual pixels. > > > > The worst case auxiliary memory footprint of this variant is rather > > big, up to picture_size/4 bytes. The code is *not* simple, but > > complexity appears to be necessary for robust performance with > > various shapes and sizes. > > > > [...] > > I took a cursory look just now, after reading your other later > posting. I think I have a general sense, especially in conjunction > with the explanatory comments. > > I'm still hoping to find a method that is both fast and has > good memory use, which is to say O(N) for an NxN pixel field. > > Something that would help is to have a library of test cases, > by which I mean patterns to be colored, so that a set of > methods could be tried, and timed, over all the patterns in > the library. Do you have something like that? So far all > my testing has been ad hoc. > I am not 100% sure about the meaning of 'ad hoc', but I'd guess that mine are ad hoc too. Below are shapes that I use apart from solid rectangles. I run them at 5 sizes: 25x19, 200x200, 1280x720, 1920x1080, 3840x2160. That is certainly not enough for correction tests, but feel that it is sufficient for speed tests. static void make_standing_snake( unsigned char *image, int width, int height, unsigned char background_c, unsigned char pen_c) { for (int y = 0; y < height; ++y) { unsigned char* p = &image[y*width]; if (y % 2 == 0) { memset(p, pen_c, width); } else { memset(p, background_c, width); if (y % 4 == 1) p[width-1] = pen_c; else p[0] = pen_c; } } } static void make_prostrate_snake( unsigned char *image, int width, int height, unsigned char background_c, unsigned char pen_c) { memset(image, background_c, sizeof(*image)*width*height); // vertical bars for (int y = 0; y < height; ++y) for (int x = 0; x < width; x += 2) image[y*width+x] = pen_c; // connect bars at top for (int x = 3; x < width; x += 4) image[x] = pen_c; // connect bars at bottom for (int x = 1; x < width; x += 4) image[(height-1)*width+x] = pen_c; } static void make_slalom( unsigned char *image, int width, int height, unsigned char background_c, unsigned char pen_c) { const int n_col = width/3; const int n_row = (height-3)/4; // top row // P B B P P P for (int col = 0; col < n_col; ++col) { unsigned char c = (col & 1)==0 ? background_c : pen_c; image[col*3] = pen_c; image[col*3+1] = c; image[col*3+2] = c; } for (int x = n_col*3; x < width; ++x) image[x] = image[n_col*3-1]; // main image: consists of 3x4 blocks filled by following pattern // P B B // P P B // B P B // P P B for (int row = 0; row < n_row; ++row) { for (int col = 0; col < n_col; ++col) { unsigned char* p = &image[(row*4+1)*width+col*3]; p[0] = pen_c; p[1] = background_c; p[2] = background_c; p += width; p[0] = pen_c; p[1] = pen_c; p[2] = background_c; p += width; p[0] = background_c; p[1] = pen_c; p[2] = background_c; p += width; p[0] = pen_c; p[1] = pen_c; p[2] = background_c; p += width; } } // near-bottom rows // P B B for (int y = n_row*4+1; y < height-1; ++y) { for (int col = 0; col < n_col; ++col) { unsigned char* p = &image[y*width+col*3]; p[0] = pen_c; p[1] = background_c; p[2] = background_c; } } // bottom row - all P // P P P P B B unsigned char *b_row = &image[width*(height-1)]; for (int col = 0; col < n_col; ++col) { unsigned char c = (col & 1)==1 ? background_c : pen_c; b_row[col*3+0] = pen_c; b_row[col*3+1] = c; b_row[col*3+2] = c; } for (int x = n_col*3; x < width; ++x) b_row[x] = b_row[n_col*3-1]; // rightmost columns for (int x = n_col*3; x < width; ++x) { for (int y = 1; y < height-1; ++y) image[y*width+x] = background_c; } } static void make_slalom90( unsigned char *image, int width, int height, unsigned char background_c, unsigned char pen_c) { const int n_col = (width-3)/4; const int n_row = height/3; // leftmost column // P // B // B // P // P // P for (int row = 0; row < n_row; ++row) { unsigned char c = (row & 1)==0 ? background_c : pen_c; image[(row*3+0)*width] = pen_c; image[(row*3+1)*width] = c; image[(row*3+2)*width] = c; } for (int y = n_row*3; y < height; ++y) image[y*width] = image[(n_row*3-1)*width]; // main image: consists of 4x3 blocks filled by following pattern // P P B P // B P P P ========== REMAINDER OF ARTICLE TRUNCATED ==========