Re: [AD] bugfix in floodfill()

[Sven Sandberg <svens@xxxxxxxxxx>]

Eric Botcazou wrote:
> > the following program exploits a bug in floodfill.
>
> Is it remotely exploitable? ;-)

OK, the program may look a bit strained, but it is very natural as a 
test case for floodfill :-)

> The mere use of short ints in the structure is evil, but I'm not sure that I 
> want to double the memory footprint so let's go for the status quo.

Yeah, I think it is necessary to keep the other fields as shorts, 
because the algorithm uses a huge array of this struct. I was even 
thinking of incorporating the flags field in the top two bits of next, 
but that would only reduce the size from 12 to 10 bytes, which is not 
that useful and could even give speed penalties.

> Do you think it could be worth while to switch to 'unsigned int'?

Probably not: this is merely an array index, which we usually keep as a 
signed int. But it does make sense for lpos, rpos and y, in case someone 
floodfills really big bitmaps (but note that in general, we assume 
bitmaps can be addressed with fixed point coordinates, i.e., <32768). In 
floodfill it can't hurt supporting up to 65535-sized bitmaps, so I 
attach an updated patch.

> And you could put an ASSERT at the critical point.

Sorry, what should be ASSERTed and where is the critical point?

--
Sven

--- src/flood.c	Sat Oct 11 18:24:22 2003
+++ src/flood.c.~1.4.~	Tue Oct  1 11:07:41 2002
@@ -26,9 +26,9 @@
 typedef struct FLOODED_LINE      /* store segments which have been flooded */
 {
    short flags;                  /* status of the segment */
-   unsigned short lpos, rpos;    /* left and right ends of segment */
-   unsigned short y;             /* y coordinate of the segment */
-   int next;                     /* linked list if several per line */
+   short lpos, rpos;             /* left and right ends of segment */
+   short y;                      /* y coordinate of the segment */
+   short next;                   /* linked list if several per line */
 } FLOODED_LINE;