Re: filling area by color atack safety

On Sun, 17 Mar 2024 13:19:29 -0700
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote:

On 3/16/2024 1:29 PM, Chris M. Thomasson wrote:

On 3/16/2024 1:02 PM, Malcolm McLean wrote: 

On 16/03/2024 18:21, Scott Lurndal wrote: 

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: 

On 16/03/2024 13:55, Ben Bacarisse wrote: 

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
 

Recursion make programs harder to reason about and prove
correct. 

>
Are you prepared to offer any evidence to support this
astonishing statement or can we just assume it's another
Malcolmism?

>
Example given. A recursive algorithm which is hard to reason
about and 

>
Perhaps hard for _you_ to reason about.  That doesn't
generalize to every other programmer that might read that
code.
>
 

 From experience this one blows the stack, but not always.
Sometimes it's OK to use. 

 
Blowing the stack is not good at all. However, sometimes, I
consider a recursive algorithm easier to understand. So, I build it
first... Get it working, _then_ think about an iterative
solution... 

 
Gaining the iterative solution from a working recursive solution is
the fun part!
 
:^)
 

I did.
After a bit of polish applied to corners (on x86-64) it consumes
approximately 60 times less extra memory than recursive variant of
Malcolm and is approximately 2.5 faster than non-naive recursion.
But it still decisively slower than Malcolm's non-recursive code:
~4x for 'snake' shape, ~2x for solid rectangle.
Malcolm's algorithm is simply better than recursive one.
Most likely because it visits already re-colored pixels less often.

For those interested, here is 'explicit stack' variant of recursive
algorithm:


int floodfill_r_explicite_stack(
  unsigned char *grey,
  int width, int height,
  int x, int y,
  unsigned char target, unsigned char dest)
{
  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;
  if (grey[y*width+x] != target)
    return 0;

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

  enum { ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN, };
  for (;;) {
    do {
      if (grey[y*width+x] != target)
        break; // back to caller

      grey[y*width+x] = dest;
      x -= 1;
      // push state to stack
      if (sp == end_stack) { // allocate more stack space
        ptrdiff_t old_sz = sp-stack;
        ptrdiff_t new_sz = old_sz + old_sz/2;
        stack = realloc(stack, new_sz*sizeof(*stack));
        if (!stack)
          return -1;
        sp = &stack[old_sz];
        end_stack  = &stack[new_sz];
      }
      *sp++ = ST_LEFT; // recursive call
    } while (x >= 0);

    for (;;) {
      if (sp == stack) { // we are back at top level
        free(stack);
        return 1; // done
      }

      char state = *--sp; // pop stack (back to caller)
      switch (state) {
        case ST_LEFT:
          x += 2;
          if (x < width) {
            *sp++ = ST_RIGHT; // recursive call
            break;
          }
          // fall throw

        case ST_RIGHT:
          x -= 1;
          y -= 1;
          if (y >= 0) {
            *sp++ = ST_UP; // recursive call
            break;
          }
          // fall throw

        case ST_UP:
          y += 2;
          if (y < height) {
            *sp++ = ST_DOWN; // recursive call
            break;
          }
          // fall throw

        case ST_DOWN:
          y -= 1;
          continue;  // back to caller
      }
      break;
    }
  }
}