Identify a patch at preload textures

kb1 said:

You might be able to hide certain classes of crashes behind doors. That would actually be kinda neat - have a hallway with doors, each one concealing a different potential run-time renderer crash. More scary than a archvile behind the door, there's an actual crash instead :)

That could actually be useful in a lot of ways.

Didn't The Sky May Be do something like that? A door with a warning that it's dangerous to open it, and the game crashes when you do?

Megamur said:

Didn't The Sky May Be do something like that? A door with a warning that it's dangerous to open it, and the game crashes when you do?

Yep, and it even used dehacked to change the error message into "Told you so!"

wesleyjohnson said:

Beware that what crashes an engine only when you look at it, will crash other engines at load time.
An example is this is this crash of DoomLegacy. Legacy precaches all textures used in the wad, even if they are not visible by any path the player could take.

Not to be dickish, but, yeah, it did crash Legacy...until you fixed it :) Which is kinda the point.

But, yeah, you're right - that would suck, but it makes it easy for port authors to debug. In other words, fix the startup crash, then the room behind the door works too, making the demo wad serve it's purpose, more or less.

Other ideas:
. Bad reject lump, missing, or too small
. lump entries with trash in the name after the \0
. lower vs uppercase names
. too wide/tall hud patches
. 2S textures missing columns
. bad blockmap, blockmap too large, map too large

Man, there's lots of stuff that can crash a Doom engine!

Megamur said:

Didn't The Sky May Be do something like that? A door with a warning that it's dangerous to open it, and the game crashes when you do?

Gez said:

Yep, and it even used dehacked to change the error message into "Told you so!"

That's just wrong - heh. Unfortunately, it's just not practical to fix every possible bug. If someone is clearly trying to make a wad crash the port, they have the upper hand. Personally, I do not want a huge amount of run-time checking going on in my port - it slows things down all the time, to catch a rare possibility for things to go wrong, once in a blue moon.

I'd say that if someone is deliberately trying to make the game crash, let it crash. But if someone is simply trying to make an interesting wad, doing things that ought to work, I should support them by hardening my port against certain obvious, known constructs.
In the Legacy wad we were discussing, the author was clearly trying to use the namespace feature in way that makes sense, and was reasonable - even though the Boom implementation was incomplete. My point is that, we should construct the "compliance test" demo wads with features that should work, even if they don't work in most ports. Not to sneak new features in, but to make problems like this one go away.

If my wad library has 50,000 wads, I would love to say that my port of choice can handle, say, 20,000 of them. And, if we gain some momentum with the "compliance demo wad" idea, maybe a handful of demo wads prompts me to add some compliance into my port. Then, maybe I can run 25,000 of the wads, which is a big improvement.

Maybe my idea of multiple doors is bad. Better would be having many small demo wads - one problem in each.

Having multiple crash sources in a wad makes it impossible to debug.
A person cannot single step through everything a wad is loading.
The first step to debugging a wad crash is to minimize the wad to the smaller version that still crashes.
Once the crash is identified with a particular linedef, then I mark that linedef with a TAG (like 1201 or something).
Then I can instrument the code with tests for that linedef tag, and single step through the code only when that linedef is being handled.
It still takes a dozen replays to see what is going wrong and where.

Therefore:
Could have an all inclusive wad for regression testing. This should NOT be the wad that has normal tests. If port crashed on any one of the crash sources they would not be able to use any of the rest of the test wad either.
But really need the one crash per wad versions for actually debugging anything.

Fully agree. It's going to take me a while to accumulate a set of these, but I'll give it a try. I guess my first step is to put crashing wads in a folder, and work from there, vs. trying to make crashing wads. That can come later.

Gez said:

wesleyjohnson said:

Legacy, even now in 1.44 alpha5, is still very close to PrBoom.
Even PrBoom mishandles this lump.

But PrBoom+ doesn't.

I ran legacy_3ddemo.wad (I assume that's what "this lump" in wesleyjohnson's post refers to - the two BLUMAPs in said wad) in both PrBoom and PrBoom+.

It appears there is a single linedef (211) that has BLUMAP on a sidedef (322), in a control sector (52). I see both engines drawing a solid blue wall if I noclip into that sector. The linedef doesn't have a special number or a tag which I believe means the colormap is not being used anywhere.

Could someone tell me what I'm supposed to be seeing? I feel so stupid...

You're supposed to see a solid blue wall (if it tried to use the colormap as a patch, it wouldn't look like a solid blue wall), so PrBoom handles the lump correctly as well.

I found odd the claim it didn't, but I didn't bother verify it since I had already verified PrBoom+ was correct.

I have to retract that previous statement about PrBoom mishandling the lump. That appeared to be the case when I could not find any code that would stop it, and it appeared that if the texture was actually visible that I expected PrBoom to crash too. Since then kb1 has shown the code in PrBoom that accomplishes namespaces. I have since found how PrBoom actually does get the patch. What PrBoom+ does is unknown to me as I am looking at PrBoom_2.5.0 because of its similarity to Doom Legacy.
The same functions can be compared side by side.

Sorry, I did not think to walk out there with NOCLIP and verify it with PrBoom until late in making my own patch. After kb1 showed that PrBoom had some namespace code, I had to check it myself too.

I had been half expecting that someone would prove otherwise from the first post. I am still waiting for another shoe to drop on the issue of searching within a wad in a particular direction, and whether it is important (not to be confused with search wads in a particular order).
Unless there were two BLUMAP patches in any one wad it should not make any difference what direction lumps were searched in that one wad.
Any wads out there that would actually make this an issue.

wesleyjohnson said:

I am still waiting for another shoe to drop on the issue of searching within a wad in a particular direction, and whether it is important (not to be confused with search wads in a particular order).

Why are you so persistent? It's a known fact that Doom searches backwards. All compliant ports also search backwards so if you deviate from that you do not comply with how Doom is expected to work.

As soon as some mod comes along that got the one bad stray lump hanging around - and these do exist - you get bad behavior. But if you do not change the rules, don't worry, you only get a bad lump if others do so, too.

wesleyjohnson said:

I am still waiting for another shoe to drop on the issue of searching within a wad in a particular direction, and whether it is important (not to be confused with search wads in a particular order).
Unless there were two BLUMAP patches in any one wad it should not make any difference what direction lumps were searched in that one wad.
Any wads out there that would actually make this an issue.

All I can say is the same thing I've already said:

Gez said:

You can then try 1 Monster MAP07. See if you get "Shawn's Got the Shotgun" or Descent's Lunar Military Base theme.

I gotta go with Graf here: You have to search lumps like everyone else does - backwards, within each wad, across all wads. Otherwise, you're creating an incompatibility, and allowing "only works with Legacy" wads to be created, tested, and distributed.

I'm going to sound like a broken record, but here goes:

Killough's hash code is designed to find the lumps in the proper order, and it's extremely fast. Having said that:

I am asking you to take 20 minutes, and give this shot. If you hate it, rip it out! I will not talk about it again. I am only being persistent, because I know this will be a good thing for Legacy: Please try it, and give it an honest evaluation:

1. Make a fork (copy) of your project. Do this work in the copy:
2. Add a global counter to your lump search routine that increments for each lump searched. Print the results of this counter to the screen.
3. Find a demo that Legacy plays well. Let it play for 1 minute, and take note of the counter at the end of that minute.
4. Implement the code listed below, modifying it as necessary.
5. In the while clause of W_CheckNumForName, add code to increment that same counter.
6. Make sure your source calls W_InitLumpHash at startup, after initializing the lumps.
7. Make sure your source calls the new W_CheckNumForName.
8. Run the same 1 minute test, and see the difference.
9. Bonus points: Replace the _strnicmp with your 64-bit comparison for an even faster search!

Implement this properly, and you'll get lumps searched in the proper order, with one of the fastest possible searches available. The counter will show you the difference. It's almost magic.

Anyway, good luck! I won't mention it again :)

// W_LumpNameHash, W_InitLumpHash, W_CheckNumForName
//
//  Rewritten by Lee Killough to use hash table for performance. Significantly
//  cuts down on time -- increases Doom performance over 300%. This is the
//  single most important optimization of the original Doom sources, because
//  lump name lookup is used so often, and the original Doom used a sequential
//  search. For large wads with > 1000 lumps this meant an average of over
//  500 were probed during every search. Now the average is under 2 probes per
//  search. There is no significant benefit to packing the names into longwords
//  with this new hashing algorithm, because the work to do the packing is
//  just as much work as simply doing the string comparisons with the new
//  algorithm, which minimizes the expected number of comparisons to under 2.
//
//  killough 4/17/98: add namespace parameter to prevent collisions
//  between different resources such as flats, sprites, colormaps

// W_LumpNameHash
//  Hash function used for lump names. Must be mod'ed with table size.
//  Can be used for any 8-character names by Lee Killough
//
unsigned int W_LumpNameHash (const char *s)
{
	unsigned int hash;

	(void)	((hash =			toupper(s[0]), s[1]) &&
			 (hash = hash * 3 + toupper(s[1]), s[2]) &&
			 (hash = hash * 2 + toupper(s[2]), s[3]) &&
			 (hash = hash * 2 + toupper(s[3]), s[4]) &&
			 (hash = hash * 2 + toupper(s[4]), s[5]) &&
			 (hash = hash * 2 + toupper(s[5]), s[6]) &&
			 (hash = hash * 2 + toupper(s[6]),
			  hash = hash * 2 + toupper(s[7])));

	return hash;
}

// W_InitLumpHash
//  Initializes the lump hash lookup.
//
static void W_InitLumpHash(void)
{
	int i;
	
	// mark slots empty
	for (i = 0; i < numlumps; i++)
		lumpinfo[i]->index = -1;

	// Insert nodes to the beginning of each chain, in first-to-last
	// lump order, so that the last lump of a given name appears first
	// in any chain, observing pwad ordering rules. killough

	for (i = 0; i < numlumps; i++)
    {
		// hash function:
		int j = W_LumpNameHash(lumpinfo[i]->name) % (unsigned) numlumps;
		
		// Prepend to list
		lumpinfo[i]->next = lumpinfo[j]->index;
		lumpinfo[j]->index = i;
  
	}
}

///////////////////////////////
// Lump name search routines //
///////////////////////////////
// killough:
//  Hash function maps the name to one of possibly numlump chains.
//  It has been tuned so that the average chain length never exceeds 2.
//
//  We search along the chain until end, looking for case-insensitive
//  matches which also match a namespace tag. Separate hash tables are
//  not used for each namespace, because the performance benefit is not
//  worth the overhead, considering namespace collisions are rare in
//  Doom wads.

// [kb] Made separate routines for each namespace lookup, for clarity.

// W_CheckNumForName
//  Searches for any lump type.
//  Returns the matching lump, or -1 if none found.
//
int W_CheckNumForName(register const char *name)
{
	register int i = lumpinfo[W_LumpNameHash(name) % (unsigned) numlumps]->index;

	while (i >= 0 && _strnicmp(lumpinfo[i]->name, name, 8))
		i = lumpinfo[i]->next;

	return i;
}

(If you remember, I had multiple search functions, but that's not really necessary. But, they also implemented the namespace stuff, whereby this CheckNumForName does not).

I couldn't agree more. Hashing the lumps is an incredible performance boost. No tinkeing with the comparison function can compensate that.

Just one minor thing: The LumpNameHash Killough used is very, very poor. I have encountered fringe cases where it created some bad hash chains. If you got access to some CRC32 code use that. Or use the same alorithm as ZDoom. It's probably better than CRC32 because it's only one function:

/* ======================================================================== */

/* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh derivative 
   license. See: 
   http://www.azillionmonkeys.com/qed/weblicense.html for license details.

   http://www.azillionmonkeys.com/qed/hash.html */

/* A modified version to do a case-insensitive hash */

#define get16bits(d) ((((DWORD)tolower(((const BYTE *)(d))[1])) << 8)\
                       +(DWORD)tolower(((const BYTE *)(d))[0]) )

DWORD SuperFastHashI (const char *data, size_t len)
{
	DWORD hash = 0, tmp;
	size_t rem;

	if (len <= 0 || data == NULL) return 0;

	rem = len & 3;
	len >>= 2;

	/* Main loop */
	for (;len > 0; len--)
	{
		hash  += get16bits (data);
		tmp    = (get16bits (data+2) << 11) ^ hash;
		hash   = (hash << 16) ^ tmp;
		data  += 2*sizeof (WORD);
		hash  += hash >> 11;
	}

	/* Handle end cases */
	switch (rem)
	{
		case 3:	hash += get16bits (data);
				hash ^= hash << 16;
				hash ^= tolower(data[sizeof (WORD)]) << 18;
				hash += hash >> 11;
				break;
		case 2:	hash += get16bits (data);
				hash ^= hash << 11;
				hash += hash >> 17;
				break;
		case 1: hash += tolower(*data);
				hash ^= hash << 10;
				hash += hash >> 1;
	}

	/* Force "avalanching" of final 127 bits */
	hash ^= hash << 3;
	hash += hash >> 5;
	hash ^= hash << 4;
	hash += hash >> 17;
	hash ^= hash << 25;
	hash += hash >> 6;

	return hash;
}

And thanks to Gez for pointing out the 'mod with the one stray lump'.

To summarize:

Do not make any changes to how Doom works unless you precisely know why you are doing them and can justify the change. I had my share of these with ZDoom, too, but fortunately was able to get most of them addressed.

Oh, yes, Killough said himself that he just empirically devised his hash scheme, to "work pretty good" with a few choice wads.

That's quite an interesting hash function you posted - I'll have to run that through some tests. The funny thing is, unless your hash function is really bad, just about anything will do a decent job, and will almost always be many times better than linear lookup.

I have a keen interest in hash algorithms, so I'll have to check this one out. It claims to be super fast at building the hash - I wonder how evenly distributed the hash actually is.

There's something incredibly neat about hashes - they are basically magic - they almost give you "something for nothing" :)

DoomLegacy Version 1.45 binaries have gone out and are in the process of being released on SourceForge.

I am going to save this forum for future reference.
There are probably a dozen ways to hash that are going to work.
DoomLegacy already uses index table lookup so much that the only place to gain a visible improve would be the preload. This is not something that I will modify in haste. I have no idea if those index tables have the lumps in forward or reverse order, all I know right now is that the index tables are searched in the forward direction.
The search is just a for loop running through the indexes. Easy enough to reverse the direction of a for loop once I have verified that it is necessary, more correct, and does not introduce any new bugs.

That test would not work well in DoomLegacy because of the indexed lookup bypasses lump lookup entirely (as long as memory is large enough to hold the entire texture cache). Recording the time to preload all textures is easier and requires no code changes.

Going to look at that wad. If those lumps are music, I am not going to be able to tell one from the other. I usually played with music turned off.

Understood. I had no idea that Legacy's texture pre-load was mandatory, and that indexes were used exclusively. That's a unique approach. Taking care of textures up front probably does solve a lot of messy issues.

For example, texture caching using vanilla's zmalloc stuff was great...until you fill up the cache, then it degrades horribly!

Good job, and good luck on the new version.

wesleyjohnson said:

Going to look at that wad. If those lumps are music, I am not going to be able to tell one from the other. I usually played with music turned off.

Turn it on for testing.

Got my memory stick to my work machine and discovered that all I got was a Wiki page describing the wad. A megawad will take a while to download, I got dial-up modem, and I cannot tie up the phone this weekend.
Give me a couple days.

I can try it in PrBoom and in DoomLegacy and listen for the same music.

How do they manage to make a buggy wad ??
Maybe I can make a wad. Maybe wadcat two wads together will do it.
I do not think that Deutex can be made to put two BLUMAP patches in the same file.

Got a new bug. No problems with Linux and xfce4. But the KDE window manager returns from DoomLegacy with the Shell window expanded to fullscreen, and it stays that way. The xfce4 window manager does not do this. The KDE on Linux 2.4 did not behave this way. I am still in the process of checking programs for using Linux 2.6 for everyday business, and am still finding some problems (mostly with KDE).