Re: filling area by color atack safety

On Mon, 25 Mar 2024 01:28:44 +0300
Michael S <already5chosen@yahoo.com> wrote:

On Sun, 24 Mar 2024 13:26:16 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

Michael S <already5chosen@yahoo.com> writes:
 

On Wed, 20 Mar 2024 07:27:38 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
  

Michael S <already5chosen@yahoo.com> writes:
  

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
[...]
The nice thing about Tim's method is that we can expect that
performance depends on number of recolored pixels and almost
nothing else.   

>
One aspect that I consider a significant plus is my code never
does poorly.  Certainly it isn't the fastest in all cases, but
it's never abysmally slow.   

>
To be fair, none of presented algorithms is abysmally slow.  When
compared by number of visited points, they all appear to be within
factor of 2 or 2.5 of each other.   

 
Certainly "abysmally slow" is subjective, but working in a large
pixel field, filling the whole field starting at the center,
Malcolm's code runs slower than my unoptimized code by a factor of
10 (and a tad slower than that compared to my optimized code).
 

Some of them for some patterns could be 10-15 times slower than
others, but it does not happen for all patterns and when it
happens it's because of problematic implementation rather because
of differences in algorithms.   

 
In the case of Malcolm's code I think it's the algorithm, because
it doesn't scale linearly.  Malcolm's code runs faster than mine
for small colorings, but slows down dramatically as the image
being colored gets bigger.
 

The big difference between algorithms is not a speed, but amount
of auxiliary memory used in the worst case.  Your algorithm
appears to be the best in that department, [...]   

 
Yes, my unoptimized algorithm was designed to use as little
memory as possible.  The optimized version traded space for
speed:  it runs a little bit faster but incurs a non-trivial cost
in terms of space used.  I think it's still not too bad, an upper
bound of a small multiple of N for an NxN pixel field.
 

But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than
difference between algorithms.   

 
If I am not mistaken the original naive recursive algorithm has a
space cost that is O( N**2 ) for an NxN pixel field.  The big-O
difference swamps everything else, just like the big-O difference
in runtime does for that metric.
 
 

For example, solid 200x200 image with starting point in the corner
[...]   

 
On small pixel fields almost any algorithm is probably not too
bad.  These days any serious algorithm should scale well up
to at least 4K by 4K, and tested up to at least 16K x 16K.
Tricks that make some things faster for small images sometimes
fall on their face when confronted with a larger image.  My code
isn't likely to win many races on small images, but on large
images I expect it will always be competitive even if it doesn't
finish in first place. 

 
You are right. At 1920*1080 except for few special patterns, your
code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K.
Auxiliary memory arrays of Malcolm are still quite small at these
image sizes, but speed suffers.
I wonder if it is a problem of algorithm or of implementation. Since I
still didn't figure out his idea, I can't improve his implementation
in order check it.
 
One thing that I were not expecting at this bigger pictures, is good
performance of simple recursive algorithm. Of course, not of original
form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite that
it is not slow. Probably the stack has very good locality of
reference.
 
Here is the code:
<snip>

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.

Todo queue based variants have very low memory footprint and perform
well for as long as recolored shape fits in the fast levels of
cache hierarchy, but suffer sharp slowdown when shape grows beyond
that. It seems, the problem of this algorithms is that the front
of recoloring is interleaved and focus of processing jumps randomly
across the front which leads to poor locality and to trashing of the
cache. May be, for huge pictures some sort of priority queue will
perform better than simple FIFO ? May be, implemented as binary heap?
https://en.wikipedia.org/wiki/Binary_heap

Thought are interesting, but it's unlikely that it could lead to faster
code than one presented below.

#include <stdlib.h>
#include <stddef.h>

typedef unsigned char Color;

static __inline
unsigned check_column(Color *row, size_t x, size_t w, Color *end_image,
Color old)
{
  unsigned b = row[x+0] == old ? 1<<0 : 0;
  if (row+w != end_image && row[x+w] == old)
    b |= 1 << 2;
  return b;
}

static __inline
unsigned check_row(Color *row, size_t x, size_t w, Color old)
{
  unsigned b = row[x+0] == old ? 1<<0 : 0;
  if (x+1 != w && row[x+1] == old)
    b |= 1 << 1;
  return b;
}

int floodfill4(
  Color *image,
  int    width,
  int    height,
  int    x0,
  int    y0,
  Color  old,
  Color  new)
{
  if (width <= 0 || height <= 0)
    return 0;

  if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
    return 0;

  const size_t w  = width;

  size_t col0 = x0;
  Color* row0 = &image[w * y0];
  if (row0[col0] != old)
    return 0;

  int offs = 0;
  if (y0 & 1) {
    row0 -= w;
    offs = 2;
  }
  if (col0 & 1) {
    col0 -= 1;
    offs |= 1;
  }

  Color* end_image = &image[w * height];

  const ptrdiff_t INITIAL_STACK_SZ = 256;
  unsigned char* stack = malloc(INITIAL_STACK_SZ*sizeof(*stack));
  if (!stack)
    return -1;
  unsigned char* sp = stack;
  unsigned char* end_stack = &stack[INITIAL_STACK_SZ];

  enum {
    // state
    ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN,
    ST_BEG,
    STATE_BITS = 3,
    // mask
    MSK_B00 = 1 << 2, MSK_B01 = 1 << 3,
    MSK_B10 = 1 << 4, MSK_B11 = 1 << 5,
    MSK_B0x = MSK_B00 | MSK_B01,
    MSK_B1x = MSK_B10 | MSK_B11,
    MSK_Bx0 = MSK_B00 | MSK_B10,
    MSK_Bx1 = MSK_B01 | MSK_B11,
    MSK_Bxx = MSK_Bx0 | MSK_Bx1,
    MSK_BITS = MSK_Bxx,
    // from
    FROM_LEFT  = 0 << 6,
    FROM_RIGHT = 1 << 6,
    FROM_UP    = 2 << 6,
    FROM_DOWN  = 3 << 6,
    FROM_BITS  = 3 << 6,
  };

  unsigned bit_mask0 = check_row(row0, col0, w, old)*MSK_B00;
  if (row0+w != end_image)
    bit_mask0 |= check_row(row0+w, col0, w, old)*MSK_B10;
  static const unsigned char kill_diag_tab[4][2] = {
    {MSK_B01 | MSK_B10, ~MSK_B11},
    {MSK_B00 | MSK_B11, ~MSK_B10},
    {MSK_B00 | MSK_B11, ~MSK_B01},
    {MSK_B01 | MSK_B10, ~MSK_B00},
  };
  if ((bit_mask0 & kill_diag_tab[offs][0])==0)
    bit_mask0 &= kill_diag_tab[offs][1];

  for (int rep = 0; rep < 2; ++rep) {
    unsigned bit_mask = bit_mask0;
    Color* row = row0;
    size_t x = col0;
    unsigned from = rep == 0 ? FROM_DOWN : FROM_LEFT;

    recursive_call:
    if (bit_mask & MSK_B00) row[x+0] = new;
    if (bit_mask & MSK_B01) row[x+1] = new;
    if (bit_mask & MSK_B10) row[x+w+0] = new;
    if (bit_mask & MSK_B11) row[x+w+1] = new;

    if (sp==end_stack) {
      ptrdiff_t size = sp - stack;
      ptrdiff_t new_size = size+size/2;
      unsigned char* new_stack = realloc(stack, new_size *
    sizeof(*stack));
      if (!new_stack) {
        free(stack);
        return -1;
      }
      stack = new_stack;
      sp = &stack[size];
      end_stack = &stack[new_size];
    }

    for (unsigned state = ST_BEG;;) {
      switch (state) {
        case ST_BEG:

        if (from != FROM_RIGHT && bit_mask & MSK_Bx1) { // look right
          x += 2;
          if (x != w) {
            unsigned bx0 = check_column(row, x, w, end_image, old);
            if (bx0 & (bit_mask/MSK_B01)) {
              // recursive call
              *sp++ = bit_mask | from | ST_RIGHT;
              bit_mask = bx0*MSK_B00;
              x += 1;
              if (x != w) {
                unsigned bx1 = check_column(row, x, w, end_image, old);
                if (bx0 & bx1)
                  bit_mask |= bx1*MSK_B01;
              }
              x -= 1;
              from = FROM_LEFT;
              goto recursive_call;
            }
          }
          case ST_RIGHT:
          x -= 2;
        }

        if (from != FROM_LEFT && bit_mask & MSK_Bx0) { // look left
          if (x > 0) {
            unsigned bx1 = check_column(row, x-1, w, end_image, old);
            if (bx1 & (bit_mask/MSK_B00)) {
              // recursive call
              *sp++ = bit_mask | from | ST_LEFT;
              bit_mask = bx1*MSK_B01;
              x -= 2;
              unsigned bx0 = check_column(row, x, w, end_image, old);
              if (bx0 & bx1)
                bit_mask |= bx0*MSK_B00;
              from = FROM_RIGHT;
              goto recursive_call;
              case ST_LEFT:
              x += 2;
            }
          }
        }

        if (from != FROM_UP && bit_mask & MSK_B0x) { // look up
          if (row != image) {
            row -= w;
            unsigned b1x = check_row(row, x, w, old);
            row -= w;
            if (b1x & (bit_mask/MSK_B00)) {
              // recursive call
              *sp++ = bit_mask | from | ST_UP;
              bit_mask = b1x*MSK_B10;
              unsigned b0x = check_row(row, x, w, old);
              if (b0x & b1x)
                bit_mask |= b0x*MSK_B00;
              from = FROM_DOWN;
              goto recursive_call;
              case ST_UP:
            }
            row += w*2;
          }
        }

        if (from != FROM_DOWN && bit_mask & MSK_B1x) { // look down
          row += w*2;
          if (row != end_image) {
            unsigned b0x = check_row(row, x, w, old);
            if (b0x & (bit_mask/MSK_B10)) {
              // recursive call
              *sp++ = bit_mask | from | ST_DOWN;
              bit_mask = b0x*MSK_B00;
              row += w;
              if (row != end_image) {
                unsigned b1x = check_row(row, x, w, old);
                if (b0x & b1x)
                  bit_mask |= b1x*MSK_B10;
              }
              row -= w;
              from = FROM_UP;
              goto recursive_call;
            }
          }
          case ST_DOWN:
          row -= w*2;
        }
        break;
      }

      if (sp == stack)
        break;

      unsigned stack_val = *--sp; // pop stack (back to caller)
      state    = stack_val & STATE_BITS;
      bit_mask = stack_val & MSK_BITS;
      from     = stack_val & FROM_BITS;
    }
  }

  free(stack);
  return 1; // done
}