From:	"Kenneth F. Henderson Jr." <KenH AT Hughes DOT Net>
Newsgroups:	comp.os.msdos.djgpp
Subject:	qsort() bug? Or invalid usage???
Lines:	102
Message-ID:	<R0Gh4.2371$Ll5.3502@news2.randori.com>
Date:	Thu, 20 Jan 2000 15:41:37 GMT
NNTP-Posting-Host:	206.97.42.111
X-Trace:	news2.randori.com 948382897 206.97.42.111 (Thu, 20 Jan 2000 07:41:37 PST)
NNTP-Posting-Date:	Thu, 20 Jan 2000 07:41:37 PST
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp
Reply-To:	djgpp AT delorie DOT com

 I think I may have found a bug in qsort().  I'm porting the Descent 2 (a game)
source code to DJGPP, and qsort is passing the address of element -1 to the
sort function occationally when the list of objects to render is sorted.  It
looks to be either a bug in qsort() or the D2 programmers providing an
illegal(???) sort_func (it depends on which 2 specific elements are compared as
to what the function returns... is this legal?  If not, any advice on what to
do about it?).  I think this construct is legal (although it's not surefire to
produce the desired sort order, but that isn't absolutely critical - being fast
and not clobbering memory is) - at the very least, can it be made to not try to
compare/sort non-existant elements...?
 Please email a copy of replies directly to kenh AT hughes DOT net.

 I'm using the following packages (info from the relevant .ver files):
djdev201 Development Kit and Runtime
gcc281b.zip GNU C compiler version 2.8.1, binaries and documentation
bnu281b GNU binutils 2.8.1 for DJGPP V2   (binaries and docs)

 Here's a code sample that produces the bug (compile with "gcc qsortbug.c"):
//Start qsortbug.c
#include <stdio.h>

//Data given to qsort
typedef struct
{
	int	objnum;
	int	dist;	//fixed-point 16:16
} sort_item;

sort_item	sort_list[] =
{/*0*/{31,647424},/*1*/{29,869248},/*2*/{28,1010176},/*3*/{27,1185984},/*4*/{26,1327808},/*5*/{25,2518400},/*6*/{0,0},/*7*/{30,756352}};
int		n_sort_items = sizeof(sort_list)/sizeof(*sort_list);

//Data used by sort_func
#define	OBJ_FIREBALL		1
#define	OBJ_WEAPON		5
#define	VCLIP_AFTERBURNER_BLOB	95

typedef struct
{
	unsigned char	type;
	unsigned char	id;
	int		size;	//fixed-point 16:16
} object;

object Objects[] =
{/*0*/{4,0,310325},/*1*/{1,88,196608},/*2*/{1,88,196608},/*3*/{1,88,196608},/*4*/{1,12,131072},/*5*/{1,88,196608},/*6*/{1,88,196608},/*7*/{1,88,196608},/*8*/{5,31,11883},/*9*/{5,31,11883},/*10*/{9,3,748295},/*11*/{5,6,65536},/*12*/{2,30,736493},/*13*/{1,2,276184},/*14*/{1,2,276184},/*15*/{1,2,276184},/*16*/{1,2,276184},/*17*/{5,31,11883},/*18*/{5,31,11883},/*19*/{7,42,262144},/*20*/{5,6,65536},/*21*/{5,48,85196},/*22*/{5,31,11883},/*23*/{5,31,11883},/*24*/{5,31,11883},/*25*/{5,6,65536},/*26*/{1,88,196608},/*27*/{1,88,196608},/*28*/{1,88,196608},/*29*/{1,88,196608},/*30*/{1,5,458752},/*31*/{1,88,196608},/*32*/{5,6,65536},/*33*/{5,6,65536},/*34*/{5,6,65536},/*35*/{2,30,736493}};

//The comparison function
int sort_func(const sort_item *a,const sort_item *b)
{
	int	delta_dist;
	object	*obj_a,*obj_b;

//Debugging code
	printf("Comparing %d%s and %d%s.\n",
((int)a-(int)sort_list)/(int)sizeof(*sort_list),
( (a<(&(sort_list[0]))) || (a>=(&(sort_list[n_sort_items]))) )?" (BUG)":"",
((int)b-(int)sort_list)/(int)sizeof(*sort_list),
( (b<(&(sort_list[0]))) || (b>=(&(sort_list[n_sort_items]))) )?" (BUG)":""
	);

	if(	(a<(&(sort_list[0		])))	||
		(b<(&(sort_list[0		])))	||
		(a>=(&(sort_list[n_sort_items	])))	||
		(b>=(&(sort_list[n_sort_items	])))	)
	{	//We have hit the bug.
		//Return 0 in the hopes that qsort won't trash memory,
		// and also so we don't try to look at objects that aren't there
		return 0;
	}

//Actual comparision code
	delta_dist= a->dist - b->dist;

	obj_a = &Objects[a->objnum];
	obj_b = &Objects[b->objnum];

	if (abs(delta_dist) < (obj_a->size + obj_b->size)) {
		if (obj_a->type == OBJ_WEAPON || (obj_a->type == OBJ_FIREBALL && obj_a->id != VCLIP_AFTERBURNER_BLOB))
		{
			if (!(obj_b->type == OBJ_WEAPON || obj_b->type == OBJ_FIREBALL))
				return -1;
			else;
		}
		else
			if (obj_b->type == OBJ_WEAPON || (obj_b->type == OBJ_FIREBALL && obj_b->id != VCLIP_AFTERBURNER_BLOB))
				return 1;
	}

	return delta_dist;
//
}

main()
{
	printf("n_sort_items = %d\n",n_sort_items);
	qsort(sort_list,n_sort_items,sizeof(*sort_list),(void *)sort_func);
}
//End qsortbug.c

 Thanks in advance for any help/fixes

- Raw text -