Re: filling area by color atack safety - worst memory size

On Sat, 20 Apr 2024 21:10:23 +0300
Michael S <already5chosen@yahoo.com> wrote:

On Fri, 19 Apr 2024 14:59:20 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

 
Did you mean you some algorithms whose worst case memory
behavior is strictly less than O( total number of pixels )?
 
I think it would be helpful to adopt a standard terminology
where the pixel field is of size M x N, otherwise I'm not
sure what O(N) refers to.
 

 
No, I mean O(max(M,N)) plus possibly some logarithmic component that
loses significance when images grow bigger.
More so, if bounding rectangle of the shape is A x B then I'd like
memory requirements to be O(max(A,B)), but so far it does not appear
to be possible, or at least not possible without significant
complications and further slowdown. So, as an intermediate goal I am
willing to accept that allocation would be O(max(M,N)). but amount of
touched memory is O(max(A,B)).
 

but so
far they are all unreasonably slow - ~5 times slower than
the best.   

 
I'm no longer working on the problem but I'm interested to
hear what you come up with. 

 
 

Here is what I had in mind.
I tried to optimize as little as I can in order to make it as simple
as I can. Unfortunately, I am not particularly good at it, so, code
still contains few unnecessary "tricks" that make understanding a
little harder.
The code uses VLA and recursion for the same purpose of making it less
tricky.
If desired, the memory footprint could be easily reduced by factor of 8
through use of packed bit arrays instead arrays of _Bool.

Even in this relatively crude form for majority of shapes this code is
blazingly fast.
Unfortunately, in the worst case (both 'slalom' shapes) an execution
time is O(max(A,B)**3) which makes it unfit as general-purpose routine.
At the moment I don't see a solution for this problem. Overall, it's
probably a dead end.

#include <stddef.h>
#include <string.h>

typedef unsigned char Color;

struct floodfill4_state {
  Color*    image;
  ptrdiff_t width;
  _Bool *l_todo,  *r_todo,  *u_todo,  *d_todo;
  int nx, ny;
  int x,  y;
  Color old_color, new_color;
};

enum {
  more_r = 1, more_l = 2, more_d = 4, more_u = 8,
  more_lr = more_r+more_l, more_ud=more_u+more_d,
};

static
int floodfill4_expand_lr(struct floodfill4_state* s, int exp_x,
  _Bool* src_todo, _Bool* exp_todo, int lr);
static
int floodfill4_expand_ud(struct floodfill4_state* s, int exp_x,
  _Bool* src_todo, _Bool* exp_todo, int ud);

int floodfill4(Color* image, int width, int height, int x, int y,
  Color old_color, Color new_color)
{
  if (width <= 0 || height <= 0)
    return 0;

  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  Color* beg = &image[(size_t)width*y+x];
  if (*beg != old_color)
    return 0;

  *beg = new_color;
  // Color* last_row = &image[(size_t)width*(height-1)];
  _Bool lr_todo[2][height];
  _Bool ud_todo[2][width];

  struct floodfill4_state s = {
    .image = beg,
    .width = width,
    .l_todo = &lr_todo[0][y],
    .r_todo = &lr_todo[1][y],
    .u_todo = &ud_todo[0][x],
    .d_todo = &ud_todo[1][x],
    .x = 0, .y = 0, .nx = 1, .ny = 1,
    .old_color = old_color,
    .new_color = new_color,
  };
  *s.l_todo = *s.r_todo = *s.u_todo = *s.d_todo = 1;

  // expansion loop
  for (int more = more_lr+more_ud; more != 0;) {
    if (more & more_lr) {
      _Bool exp_todo[s.ny];
      do {
        if (more & more_r) {
          while (x+s.nx != width) {
            // try to expand to the right
            s.x = s.nx-1;
            int ret = floodfill4_expand_lr(&s, s.nx, s.r_todo,
  exp_todo, more_r);
            if (!ret)
              break;
            more |= ret;
            ++s.nx;
          }
          more &= ~more_r;
        }
        if (more & more_l) {
          while (x != 0) {
            // try to expand to the left
            s.x = 0;
            int ret = floodfill4_expand_lr(&s, -1, s.l_todo, exp_todo,
  more_l);
            if (!ret)
              break;
            more |= ret;
            ++s.nx;
            --s.image;
            --s.u_todo;
            --s.d_todo;
            --x;
          }
          more &= ~more_l;
        }
      } while (more & more_lr);
    }

    if (more & more_ud) {
      _Bool exp_todo[s.nx];
      do {
        if (more & more_d) {
          while (y+s.ny != height) {
            // try to expand down
            s.y = s.ny-1;
            int ret = floodfill4_expand_ud(&s, s.ny, s.d_todo,
    exp_todo, more_d);
            if (!ret)
              break;
            more |= ret;
            ++s.ny;
          }
          more &= ~more_d;
        }
        if (more & more_u) {
          while (y != 0) {
            // try to expand up
            s.y = 0;
            int ret = floodfill4_expand_ud(&s, -1, s.u_todo, exp_todo,
    more_u);
            if (!ret)
              break;
            more |= ret;
            ++s.ny;
            s.image -= s.width;
            --s.l_todo;
            --s.r_todo;
            --y;
          }
          more &= ~more_u;
        }
      } while (more & more_ud);
    }
  }
  return 1;
}

// floodfill4_core - floodfill4 recursively in divide and conquer
fashion
// s.*-todo arrays initialized by caller. floodfill4_core sets values
// in that indicate need for further action, but never clears values
// that were already set
static void floodfill4_core(const struct floodfill4_state* arg)
{
  const int nx = arg->nx;
  const int ny = arg->ny;
  if (nx+ny == 2) { // nx==ny==1
    *arg->l_todo = *arg->r_todo = *arg->u_todo = *arg->d_todo = 1;
    *arg->image = arg->new_color;
    return;
  }

  struct floodfill4_state args[2];
  args[0] = args[1] = *arg;
  if (nx > ny) {
    // split vertically
    _Bool todo[2][ny];
    const int hx = nx / 2;

    args[0].r_todo = todo[0];
    args[0].nx = hx;

    args[1].image += hx;
    args[1].l_todo = todo[1];
    args[1].u_todo += hx;
    args[1].d_todo += hx;
    args[1].nx = nx-hx;

    int todo_i;
    int x0 = arg->x;
    if (x0 < hx) { // update left field
      memset(todo[0], 0, ny*sizeof(todo[0][0]));
      floodfill4_core(&args[0]);
      todo_i = 0;
    } else       { // update right field
      memset(todo[1], 0, ny*sizeof(todo[0][0]));
      args[1].x = x0 - hx;
      floodfill4_core(&args[1]);
      todo_i = 1;
    }

    args[0].x = hx-1;
    args[1].x = 0;
    for (;;) {
      // look for contact points on destination edge
      _Bool  *todo_src = todo[todo_i];
      Color *edge_dst = &arg->image[hx-todo_i];
      int y;
      for (y = 0; y < ny; edge_dst += arg->width, ++y) {
        if (todo_src[y] && *edge_dst == arg->old_color) // contact found
          break;
      }
      if (y == ny)
        break;

      todo_i = 1 - todo_i;
      memset(todo[todo_i], 0, ny*sizeof(todo[0][0]));
      do {
        args[todo_i].y = y;
        floodfill4_core(&args[todo_i]);
        edge_dst += arg->width;
        for (y = y+1; y < ny; edge_dst += arg->width, ++y) {
          if (todo_src[y] && *edge_dst == arg->old_color) // contact
      found
            break;
        }
      } while (y < ny);
    }
  } else { // ny >= nx
    // split horizontally
    _Bool todo[2][nx];
    const int hy = ny / 2;
    Color* edge = &arg->image[arg->width*hy];

    args[0].d_todo = todo[0];
    args[0].ny = hy;

    args[1].image = edge;
    args[1].u_todo = todo[1];
    args[1].l_todo += hy;
    args[1].r_todo += hy;
    args[1].ny = ny-hy;

    int todo_i;
    int y0 = arg->y;
    if (y0 < hy) { // update up field
      memset(todo[0], 0, nx*sizeof(todo[0][0]));
      floodfill4_core(&args[0]);
      todo_i = 0;
    } else       { // update down field
      args[1].y = y0 - hy;
      memset(todo[1], 0, nx*sizeof(todo[0][0]));
      floodfill4_core(&args[1]);
      todo_i = 1;
    }

    args[0].y = hy-1;
    args[1].y = 0;
    for (;;) {
      // look for contact points on destination edge
      _Bool *todo_src = todo[todo_i];
      Color *edge_dst = todo_i ? edge - arg->width : edge;
      int x;
      for (x = 0; x < nx; ++x) {
        if (todo_src[x] && edge_dst[x] == arg->old_color) // contact
    found
          break;
      }
      if (x == nx)
        break;

      todo_i = 1 - todo_i;
      memset(todo[todo_i], 0, nx*sizeof(todo[0][0]));
      do {
        args[todo_i].x = x;
        floodfill4_core(&args[todo_i]);
        for (x = x+1; x < nx; ++x) {
          if (todo_src[x] && edge_dst[x] == arg->old_color) // contact
      found
            break;
        }
      } while (x < nx);
    }
  }
}


// return value
// 0 - not expanded
// 1 - expanded, no bounce back
// 2 - expanded, possible bounce back
static
int floodfill4_expand(
  Color*    pixels, // row or column
  ptrdiff_t incr,   // distance between adjacent points of pixels
  int       len,
  Color     old_color,
  Color     new_color,
  _Bool*    src_todo,
  _Bool*    dst_todo,
  _Bool     first)
{
  for (int i = 0; i < len; pixels += incr, ++i) {
    if (src_todo[i] && *pixels == old_color) {
      // contact found
      if (first)
        memset(dst_todo, 0, len*sizeof(*dst_todo));
      *pixels = new_color;
      dst_todo[i] = 1;
      Color* p = pixels - incr;
      int k;
      for (k = i-1; k >= 0 && *p == old_color; p -= incr, --k) {
        *p = new_color;
        dst_todo[k] = 1;
      }
      _Bool more = k != i-1;
      for (;;) {
        pixels += incr;
        for (i = i+1; i < len && *pixels == old_color; pixels += incr,
++i) {
          *pixels = new_color;
          dst_todo[i] = 1;
          more |= src_todo[i] ^ 1;
        }
        if (i >= len)
          break;
        pixels += incr;
        for (i = i+1; i < len && (!src_todo[i] || *pixels !=
old_color); pixels += incr, ++i);
        if (i >= len)
          break;
        *pixels = new_color;
        dst_todo[i] = 1;
        Color* p = pixels - incr;
        for (k = i-1; *p == old_color; --k, p -= incr) {
          *p = new_color;
          dst_todo[k] = 1;
        }
        more |= k != i-1;
      }
      return more ? 2 : 1;
    }
  }
  return 0; // not expended
}

// return value - more code
static
int floodfill4_expand_lr(struct floodfill4_state* s, int exp_x, _Bool*
src_todo, _Bool* exp_todo, int lr)
{
  // try to expand to the right or left
  const int ny = s->ny;
  int ret = floodfill4_expand(&s->image[exp_x], s->width, ny,
s->old_color, s->new_color, src_todo, exp_todo, 1);
  if (!ret)
    return 0;

  int result = lr;
  while (ret == 2) {
    Color* p = &s->image[s->x];
    _Bool contact = 0;
    for (int y = 0; y < ny; p += s->width, ++y) {
      if (exp_todo[y] && *p == s->old_color) {
        if (!contact)
          memset(src_todo, 0, ny*sizeof(*src_todo));
        s->y = y;
        floodfill4_core(s);
        contact = 1;
      }
    }
    if (!contact)
      break;
    result = more_lr+more_ud;
    ret = floodfill4_expand(&s->image[exp_x], s->width, ny,
  s->old_color, s->new_color, src_todo, exp_todo, 0);
  }

  if ((s->u_todo[exp_x] = exp_todo[0]))    result |= more_u;
  if ((s->d_todo[exp_x] = exp_todo[ny-1])) result |= more_d;
  memcpy(src_todo, exp_todo, ny*sizeof(*src_todo));
  return result;
}

// return value - more code
static
int floodfill4_expand_ud(struct floodfill4_state* s, int exp_y, _Bool*
src_todo, _Bool* exp_todo, int ud)
{
  // try to expand up or down
  const int nx = s->nx;
  int ret = floodfill4_expand(&s->image[s->width*exp_y], 1, nx,
s->old_color, s->new_color, src_todo, exp_todo, 1);
  if (!ret)
    return 0;

  int result = ud;
  while (ret == 2) {
    Color* p = &s->image[s->width*s->y];
    _Bool contact = 0;
    for (int x = 0; x < nx; ++x) {
      if (exp_todo[x] && p[x] == s->old_color) {
        if (!contact)
          memset(src_todo, 0, nx*sizeof(*src_todo));
        s->x = x;
        floodfill4_core(s);
        contact = 1;
      }
    }
    if (!contact)
      break;
    result = more_lr+more_ud;
    ret = floodfill4_expand(&s->image[s->width*exp_y], 1, nx,
  s->old_color, s->new_color, src_todo, exp_todo, 0);
  }

  if ((s->l_todo[exp_y] = exp_todo[0]))    result |= more_l;
  if ((s->r_todo[exp_y] = exp_todo[nx-1])) result |= more_r;
  memcpy(src_todo, exp_todo, nx*sizeof(*src_todo));
  return result;
}