Re: filling area by color atack safety

On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

On 16/03/2024 15:09, Malcolm McLean wrote:

On 16/03/2024 14:40, David Brown wrote: 

On 16/03/2024 12:33, Malcolm McLean wrote:
 

And here's some code I wrote a while ago. Use that as a pattern.
But not sure how well it works. Haven't used it for a long time.
>
https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
 

>
Your implementation is a mess, /vastly/ more difficult to prove
correct than the OP's original one, and unlikely to be very much
faster (it will certainly scale in the same way in both time and
memory usage).
 

Now is this David Brown being David Borwn, ot its it actaully ture?
 

 

And I need to run some tests, don't I?
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
int floodfill_r(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;
    grey[y*width+x] = dest;
    floodfill_r(grey, width, height, x - 1, y, target, dest);
    floodfill_r(grey, width, height, x + 1, y, target, dest);
    floodfill_r(grey, width, height, x, y - 1, target, dest);
    floodfill_r(grey, width, height, x, y + 1, target, dest);
 
    return 0;
}
 
/**
   Floodfill4 - floodfill, 4 connectivity.
 
   @param[in,out] grey - the image (formally it's greyscale but it
could be binary or indexed)
   @param width - image width
   @param height - image height
   @param x - seed point x
   @param y - seed point y
   @param target - the colour to flood
   @param dest - the colur to replace it by.
   @returns Number of pixels flooded.
*/
int floodfill4(unsigned char *grey, int width, int height, int x, int
y, unsigned char target, unsigned char dest)
{
   int *qx = 0;
   int *qy = 0;
   int qN = 0;
   int qpos = 0;
   int qcapacity = 0;
   int wx, wy;
   int ex, ey;
   int tx, ty;
   int ix;
   int *temp;
   int answer = 0;
 
   if(grey[y * width + x] != target)
     return 0;
   qx = malloc(width * sizeof(int));
   qy = malloc(width * sizeof(int));
   if(qx == 0 || qy == 0)
     goto error_exit;
   qcapacity = width;
   qx[qpos] = x;
   qy[qpos] = y;
   qN = 1;
 
   while(qN != 0)
   {
     tx = qx[qpos];
     ty = qy[qpos];
     qpos++;
     qN--;
 
     if(qpos == 256)
     {
       memmove(qx, qx + 256, qN*sizeof(int));
       memmove(qy, qy + 256, qN*sizeof(int));
       qpos = 0;
     }
     if(grey[ty*width+tx] != target)
       continue;
     wx = tx;
     wy = ty;
     while(wx >= 0 && grey[wy*width+wx] == target)
       wx--;
     wx++;
     ex = tx;
     ey = ty;
     while(ex < width && grey[ey*width+ex] == target)
       ex++;
     ex--;
 
 
     for(ix=wx;ix<=ex;ix++)
     {
       grey[ty*width+ix] = dest;
       answer++;
     }
 
     if(ty > 0)
       for(ix=wx;ix<=ex;ix++)
       {
    if(grey[(ty-1)*width+ix] == target)
    {
           if(qpos + qN == qcapacity)
      {
             temp = realloc(qx, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qx = temp;
             temp = realloc(qy, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qy = temp;
             qcapacity += width;
      }
           qx[qpos+qN] = ix;
           qy[qpos+qN] = ty-1;
           qN++;
    }
       }
     if(ty < height -1)
       for(ix=wx;ix<=ex;ix++)
       {
         if(grey[(ty+1)*width+ix] == target)
    {
           if(qpos + qN == qcapacity)
      {
             temp = realloc(qx, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qx = temp;
             temp = realloc(qy, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qy = temp;
             qcapacity += width;
      }
           qx[qpos+qN] = ix;
           qy[qpos+qN] = ty+1;
           qN++;
    }
       }
   }
 
   free(qx);
   free(qy);
 
   return answer;
  error_exit:
   free(qx);
   free(qy);
   return -1;
}
 
int main(void)
{
    unsigned char *image;
    clock_t tick, tock;
    int i;
 
    image = malloc(100 * 100);
    tick = clock();
    for (i = 0 ; i < 10000; i++)
    {
       memset(image, 0, 100 * 100);
       floodfill_r(image, 100, 100, 50, 50, 0, 1);
    }
    tock = clock();
    printf("floodfill_r %g\n", ((double)(tock -
tick))/CLOCKS_PER_SEC);
 
    tick = clock();
    for (i = 0 ; i < 10000; i++)
    {
       memset(image, 0, 100 * 100);
       floodfill4(image, 100, 100, 50, 50, 0, 1);
    }
    tock = clock();
    printf("floodfill4 %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);
 
    return 0;
}
 
 
Let's give it a whirl
 
malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
malcolm@Malcolms-iMac cscratch % ./a.out
floodfill_r 1.69274
floodfill4 0.336705
 
 

I find your performance measurement non-decisive for two reasons:
(1) because your test case is too trivial and probably uncharacteristic
and
(2) because recursive variant could be trivially rewritten in a way
that reduces # of stack memory accesses by factor of 2 or 3.
Like that:

struct recursive_context_t {
 unsigned char *grey;
 int width, height;
 unsigned char target, dest;
};

static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
  if (x < 0 || x >= context->width || y < 0 || y >= context->height)
    return;
  if (context->grey[y*context->width+x] == context->target) {
    context->grey[y*context->width+x] = context->dest;
    floodfill_r_core(context, x - 1, y);
    floodfill_r_core(context, x + 1, y);
    floodfill_r_core(context, x, y - 1);
    floodfill_r_core(context, x, y + 1);
  }
}

int floodfill_r(
  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;
  struct recursive_context_t context = {
    .grey = grey,
    .width = width,
    .height = height,
    .target = target,
    .dest = dest,
  };
  floodfill_r_core(&context, x, y);
  return 1;
}