numContacts overflow bug?

[slbsoft]

I think there is a bug in nextContactPoint, in cpCollision.c.

The code will increment *numPtr until it is equal to CP_MAX_CONTACTS_PER_ARBITER. Then, on the next call, it will return &arr[CP_MAX_CONTACTS_PER_ARBITER] - which is 1 beyond what it should be. If this is the last cpContact in the cpContactBuffer, it can cause a crash or other serious failures.

The fix is simple: change

Code: Select all

	if(num < CP_MAX_CONTACTS_PER_ARBITER)
		(*numPtr) = num + 1;

to

Code: Select all

	if(num + 1 < CP_MAX_CONTACTS_PER_ARBITER)
		(*numPtr) = num + 1;

-chris

[slbsoft]

Hmm. That fix might suck: it will cause findVerts to return 1 too few.

Perhaps

Code: Select all

static cpContact *
nextContactPoint(cpContact *arr, int *numPtr)
{
	int num = *numPtr;

	if(num < CP_MAX_CONTACTS_PER_ARBITER)
		(*numPtr) = ++num;

	return &arr[num - 1];
}

?

[slembcke]

It seems that you are correct. CP_MAX_CONTACTS_PER_ARBITER is defined to be 6, so it would allow each collision to write a 7th contact point. If that 7th contact point was beyond the end of the contact buffer it could crash, otherwise it would just get overwritten by the next contact set. This is pretty unlikely to happen as a contact set with more than 4 points is pretty rare unless you are using lots of polys with lots of vertexes each, and it wouldn't cause a crash unless it was the very last contact point added to the buffer (~250 per buffer iirc).

The intended behaviour is to make sure it keeps at least the first and last point found as they tend to be the most important. Your fix would cause it to keep overwriting the 6th contact point, but then report only 5 points back to the buffer. I think the following is correct though. It should increment the count to 6, but overwrite the 6th if additional points are encountered.

Code: Select all

static cpContact *
nextContactPoint(cpContact *arr, int *numPtr)
{
	int index = *numPtr;
	
	if(index < CP_MAX_CONTACTS_PER_ARBITER){
		(*numPtr) = index + 1;
		return &arr[index];
	} else {
		return &arr[CP_MAX_CONTACTS_PER_ARBITER - 1];
	}
}

[slembcke]

Seems you beat me with a reply. Your fixed version has a bug too. If it's the first contact in the set, num will be 0, then you later subtract 1 and use it as an index.

I hate fiddly array index math. It seems like there is never an elegant way to do what you want. :-\

[slbsoft]

If num is 0, it will pass (num < CP_MAX_CONTACTS_PER_ARBITER) and so will be incremented to 1 by (*numPtr) = ++num;

[slbsoft]

I see from the comment how nextContactPoint came to be, but it seems to me that it no longer fits its current usage very well - it is trying to handle the conflicting goals of filling up a small fixed-size buffer, and always returning a pointer to good storage.

Wouldn't it be better to discard nextContactPoint and just check for a full array in the callers,

Code: Select all

	for(int i=0; i<poly1->numVerts; i++){
		cpVect v = poly1->tVerts[i];
		if(cpPolyShapeContainsVertPartial(poly2, v, cpvneg(n))) {
			cpContactInit(arr + num, v, n, dist, CP_HASH_PAIR(poly1->shape.hashid, i));
			if(++num == CP_MAX_CONTACTS_PER_ARBITER)
				return num;
		}
	}

It is a bit more typing and some code duplication, but it will terminate faster, write to less memory, and the array indexing is simpler.

[slembcke]

Well, yeah as the comment suggested it used to allocate and resize the buffer as needed. Later when I changed Chipmunk to use big linear buffers to make the cache happier, I just changed that function a little bit.

It is a bit more typing and some code duplication, but it will terminate faster, write to less memory, and the array indexing is simpler.

It's very very unlikely to end up with more than 4 contacts per contact set. Given that, it's very unlikely to terminate faster or write to less memory. If you do end up having more, the most important points are the first and the last one (generally), so I'd prefer it to keep last one found. The only case where this will make a difference is when you have a large number of poly shapes that have a large number of vertexes. Not something you are likely to do in a game, and not something that will be fast to begin with.

I personally would rather avoid the code duplication than micro-optimize for a specific and uncommon use case.