Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
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: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<utbuk3$qed7$1@dont-email.me>
	<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 <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> 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 ==========