Re: filling area by color atack safety

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
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm