Borland BGI floodfill bug

Borland's BGI graphics library (GRAPHICS.LIB, GRAPHICS.TPU) has a bug
which can cause the floodfill routine to crash. It's most likely to occur in C
applications when compiled using the small data (64K) memory models.

To see the bug in action, compile the C demo program supplied below. Make
sure the target is set for DOS and the small or medium memory model is used.

For floodfill to crash requires two conditions be met:
- the fill is complex enough that it fills the flood stack
- the pointer returned when free memory is allocated (usually a
segment/offset pair) does not have the "offset" value = 0.

The first condition can occur in any target (e.g. by doing an 'outside fill' on a
screen that has many objects).

The second condition typically occurs on small memory models. I've yet
to find Pascal or the C large memory models crashing which suggests their
memory allocation schemes returns a pointer with offset = 0. But whether
this is *always* the case is the question (?)

Why the bug happens is as follows. When a graphic mode is initiated, it allocates
a 4096 byte "graphics buffer" from the heap. Prior to doing a floodfill, the stack
is switched to the graphics buffer. The relevent library code (module graph.obj) is:

_floodfill:
...
les si, dword_10025
mov di, es:[si+0Ch] ; buffer addr (offset)
mov dx, es:[si+0Eh] ; buffer addr (segment)
add di, es:[si+10h] ; buffer size default = 4096
sub di, 2
cli
xchg sp, di
mov bp, ss
mov ss, dx
sti
push di
push bp
mov si, 44
call dword ptr ds:__DDO_ADD ; do floodfill
pop bx
pop ax
cli
mov ss, bx
mov sp, ax
sti
...

The actual floodfill is done in the BGI driver. The flood stack builds downwards
as items are added. Floodfill assumes that memory extends down to SSEG:0000.
Given the stack initialization routine above, this can only be true if the offset part
of graphics buffer pointer is 0000h. In small memory models that's rarely the
case, resulting in floodfill overflowing its bounds and corrupting other allocated
memory (hence the crash).

The fix is to make SSEG:0000 always reside within the graphics buffer.
Suitable code might be:

; mov di, es:[si+0Ch]
; mov dx, es:[si+0Eh]
; add di, es:[si+10h]
; sub di, 2

mov dx, es:[si+0Ch]
shr dx,1
shr dx,1
shr dx,1
shr dx,1
inc dx ; round up to be safe
add dx, es:[si+0Eh]
mov di, es:[si+10h]
sub di, 16+2 ; adjust for roundup

It should be said that while the bug exists, it doesn't necessarily need fixing.
The bug's effect only occurs once the graphics buffer has filled up.
Having a full buffer is a fatal condition anyway. So whether floodfill
results in an out of memory error message or a crash, it's warning the
programmer to increase the graphics buffer size.

Below is the floodfill test program I used (versions in C and Pascal).

Good luck.

----------------------------------------------------------------------

/* Demonstrate floodfill and out-of-memory condition */

/* needs EGAVGA.BGI */

int svga = 0; /* BGI driver: 0=EGAVGA, 1=SVGA */

int size = 16; /* making this smaller results in more objects
on the screen */

#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

void box(x1,y1,x2,y2)
int x1,y1,x2,y2;
{
moveto(x1,y1);
lineto(x1,y2); lineto(x2,y2);
lineto(x2,y1); lineto(x1,y1);
}

int main(void)
{

int gdriver, gmode, errorcode;
int maxx, maxy, i, j, wid, dia, offs;

if (svga)
{ gdriver = (installuserdriver("SVGA", NULL)); gmode = 1; } /* SVGA.BGI */
else
{ gdriver = 9; gmode = 2; } /* use EGAVGA.BGI */
;

initgraph(&gdriver, &gmode, "");

/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk)
/* an error occurred */
{
printf("Graphics init error\n");
getch();
exit(1);
/* terminate with an error code */
}

maxx = getmaxx(); maxy = getmaxy();

setcolor(1);

wid = size*2;
dia = (wid/2)-2;
offs = (wid/2)-dia;

for( j=0; j<(maxy-wid+1); j=j+wid){
for( i=0; i<(maxx-wid+1); i=i+wid){
/* circle(wid/2+i, wid/2+j, dia); */
box(i+offs, j+offs, i+offs+dia, j+offs+dia);
}
}
getch();

setfillstyle(1,3);

/* fill in bounded region */
floodfill(0, 0, 1);
if (graphresult() != grOk) {
setcolor(15);
outtextxy(0,0,"Error: Out of flood memory!");
}
getch();

closegraph();
return 0;
}

----------------------------------------------------------------------
(* Demonstrate floodfill and out-of-memory condition *)

(* needs EGAVGA.BGI *)

program Floodtest;

uses Graph, Crt;

procedure BOX (var x1,y1,x2,y2: integer);
begin
moveto(x1,y1);
lineto(x1,y2); lineto(x2,y2);
lineto(x2,y1); lineto(x1,y1);
end;

var gdriver, gmode: integer;
var errorcode, maxx, maxy, i, j, wid, dia, offs, a, b, c, d: integer;
var svga, size: integer;
var ch: char;

begin

svga := 0; (* BGI driver: 0=EGAVGA, 1=SVGA *)

size := 16; (* making this smaller results in more objects
on the screen *)

wid := size*2;
dia := (wid div 2)-2;
offs := (wid div 2)-dia;

if (svga<>0) then
begin
gdriver := (installuserdriver('SVGA', nil)); gmode := 1; (* SVGA.BGI *)
end
else
begin gdriver := 9; gmode := 2; end; (* use EGAVGA.BGI *)

initgraph(gdriver, gmode, ' ');
errorcode := GraphResult;
if errorcode <> grOk then
begin
WriteLn('Graphics init error');
ch := Readkey;
exit;
end;

maxx := getmaxx; maxy := getmaxy;

setcolor(1);

j := 0;
while j < (maxy-wid) do
begin
i := 0;
while i < (maxx-wid) do
begin
a := (wid div 2)+i; b := (wid div 2)+j;
a := i+offs; b := j+offs; c := i+offs+dia; d := j+offs+dia;
box(a, b, c, d);
i := i+wid;
end;
j := j+wid
end;

ch := Readkey;

setfillstyle(1,3);

FloodFill(0,0,1);
if GraphResult <> grOk then
begin
setcolor(15);
outtextxy(0,0,'Error: Out of flood memory!');
end;
ch := Readkey;

CloseGraph;
end.

----------------------------------------------------------------------

anon wrote:
> Borland's BGI graphics library (GRAPHICS.LIB, GRAPHICS.TPU) has a bug
> which can cause the floodfill routine to crash. It's most likely to occur in C
> applications when compiled using the small data (64K) memory models.
>
comp.lang.c isn't the appropriate forum for this, try a group the deals
with your environment.


--
Ian Collins.

"anon" <anon@invalid.com> wrote:

[asking for help om BGI (borland graphics C stuff)]

have a look at: http://info.borland.com/newsgroups/

Server:
newsgroups.borland.com

It depends on your version:
groups for the current (and older) versions of C++ Builder have
"cppbuilder" in their name, for the old compilers (3.1 ... 5.02) it is
borland.public.cpp.borlandcpp.

Have fun. Join the off-topic group there. Great people and lots of
fun.
--
regards
John

Hello,

cool analyses.

Greetings

Markus
>