Overflow of array of the crossed special lines

[entryway]

If you wish to make your wad fully compatible with vanilla doom and with limit-removing ports - do not do similarly to below:

Alien Vendetta\MAP05


Hell Revealed\MAP18


In these cases the "spechit" array overflow occurs in vanilla engine (always in the second example) and the further behaviour of a demo cannot be predicted unequivocally and will be desyn with a high probability. Crossing only eight or less lines per tic can be correctly processed by the original engine. And this overflow can't be emulated in ports in general case.

[Kristian Ronge]

Interesting stuff! But I don't fully understand. Do you mean, that if >8 tagged linedefs are crossed, by monsters and/or the player, in a single gametic, there's a risk of de-synching demos?

(By the way, this should explain why HR map 18 has always had problems with de-synching demos in various source ports' compatibility modes)

[Szymanski]

Interesting. It's pretty easy to exceed 8 tagged linedefs, especially with 'fail-safe' teleporters.

[entryway]

Kristian Ronge said:

I don't fully understand. Do you mean, that if >8 tagged linedefs are crossed, by monsters and/or the player, in a single gametic, there's a risk of de-synching demos?

Just to be sure you got it, the limit of 8 linedefs exists for every monster or/and the player independently.

P.S.
Last version of Prboom-plus can detect this overflow and inform the player:

glboom.exe -iwad doom2.wad -file av.wad -playdemo av01-738.lmp -warp 5

---------------------------
PrBoom-Plus
---------------------------
Spechits overflow has been detected but it not supported for this map. The demo can be desync soon. The list of LinesID leading to overrun: 2265, 2266, 2269, 2270, 2281, 2284, 2305, 2306, 2309. You can disable this warning through: "Ingame Menu\Options\Setup\Status Bar / HUD\Warn If Can't Be Emulated"
---------------------------
OK
---------------------------

[DaniJ]

And this overflow can't be emulated in ports in general case.

I'm not sure this is entirely true. I think it might be possible to emulate the overflow as the order in which items are added to the spechits is always the same if a) the wad is the same as the one used to record the demo b) the order in which traversal of the relevant arrays doesn't change in the code.

My understanding of this is that any hit event that happens above the original hardcoded limit is simply not executed. Could this behaviour not be emulated by simply processing the spechits array upto item 8?

[Grazza]

Just to check I've understood this right:

On STRAIN map07 (a nice example as the difference is immediately apparent), in order to reach the exit linedef, the player needs to cross a large number (up to 16) of special linedefs (scrolling walls).

In Doom2.exe, once it has detected 8 special linedefs that the player is attempting to cross, it will stop detecting any further attempts to cross linedefs (special or otherwise). It then decides on an action (i.e. that the player can pass through). As a result, the player then crosses the exit line, and exits the map. The fact that the player has gone through an impassable linedef in the process is not relevant, because it wasn't even detected.

In most ports, the engine will detect all the special linedefs being crossed, decide they don't block the player, but then notice the impassable linedef just behind the exit. As a result, the player will never reach the exit linedef.

[DaniJ]

Exactly.

So really it should be possible to emulate the overflow behaviour as the events in spechits should be the same as long as the order of which items are added hasn't changed and the events are added at the same rate-per-tic (player movement speed is but one influencing factor). Then its a case of disabling the addtional checks once the limit has been breached.

[Grazza]

DaniJ said:

So really it should be possible to emulate the overflow behaviour as the events in spechits should be the same as long as the order of which items are added hasn't changed and the events are added at the same rate-per-tic (player movement speed is but one influencing factor). Then its a case of disabling the addtional checks once the limit has been breached.

One of Andrey's test versions of Prboom-plus 2.2.6.22 did, I believe, attempt to emulate it in the general case, but he later changed it to make it map-specific. I don't know if this was due to some horrible problem, or just because in the general case demo compatibility could not necessarily be retained after the overrun.

I still have the binaries for that version, but not the source.

Kristian Ronge said:

(By the way, this should explain why HR map 18 has always had problems with de-synching demos in various source ports' compatibility modes)

Yes, that's where this all started off from.

[entryway]

DaniJ said:

I'm not sure this is entirely true. I think it might be possible to emulate the overflow as the order in which items are added to the spechits is always the same if

It is impossible, because depends on the client parameters.
To emulate it - it is necessary to know value returned by Z_Malloc in a code below, as the spechit array is overflown by addresses of crossed lines.

void P_LoadLineDefs (int lump)
{
  numlines = W_LumpLength (lump) / sizeof(maplinedef_t);
  lines = Z_Malloc (numlines*sizeof(line_t),PU_LEVEL,0);
  ...

[entryway]

Grazza said:

Just to check I've understood this right:
In Doom2.exe, once it has detected 8 special linedefs that the player is attempting to cross, it will stop detecting any further attempts to cross linedefs

No. I cannot explain in English how it works, but I think Graf Zahl (or someone else) can. Some technical details are described below.

from IdaPro

.bss:00483710 spechit       dd 8 dup(?)   ; 0 ; DATA XREF: P_Move+D8^r
.bss:00483710                             ; PIT_CheckLine+DC^w ...
.bss:00483730 tmbbox        dd 4 dup(?)   ; 0 ; DATA XREF: P_TeleportMove+33^w
.bss:00483730                             ; P_TeleportMove+EE^r ...
.bss:00483740 crushchange   dd ?          ; DATA XREF: PIT_ChangeSector+67^r
.bss:00483740                             ; sub_423F50+7^w
.bss:00483744 nofit         dd ?          ; DATA XREF: PIT_ChangeSector+6D^w
.bss:00483744                             ; sub_423F50+15^w ...

from Doom sources

boolean PIT_CheckLine (line_t* ld)
{
  ...
  spechit[numspechit++] = ld;
  CheckForSpechitsOverrun(ld);//e6y
}

void CheckForSpechitsOverrun(line_t* ld)
{
  if (numspechit>8) {
    int addr = DOOM_runtime_lines_address + (ld - lines) * sizeof(DOOM_line_t);
  
    switch(numspechit) {
      case 9: 
      case 10:
      case 11:
      case 12:
        tmbbox[numspechit-9] = addr;
        break;
      case 13:
        crushchange = addr;
        break;
      case 14:
        nofit = addr;
        break;
      ...
      default:
        Warning("Too big spechits overflow for emulation was detected.");
        break;
    }
  }
}

[andrewj]

DaniJ said:

My understanding of this is that any hit event that happens above the original hardcoded limit is simply not executed. Could this behaviour not be emulated by simply processing the spechits array upto item 8?

The original does not check the 8 limit, so it writes the lines into a "bad place" (overwriting something) but it still processes all the lines (counting backwards).

I'm assuming that the space past the end is some other variables in p_map.c which sometimes get changed and sometimes don't, hence affecting how the spechits are handled in an unpredictable way.

[DaniJ]

The original does not check the 8 limit, so it writes the lines into a "bad place" (overwriting something) but it still processes all the lines (counting backwards).

Ah.

If it doesn't check the limit (how careless is that!) then yeah, you've got pretty much zero chance of emulating what happens when the limit is breached.

[entryway]

DaniJ said:

If it doesn't check the limit (how careless is that!) then yeah, you've got pretty much zero chance of emulating what happens when the limit is breached.

I know what happens and what data have been overwritten, but it is actually impossible to get the dynamic address of a lines array in general case, but it is necessary for full emulation.

[andrewj]

[QUOTE]entryway said:

.bss:00483710 spechit       dd 8 dup(?)   ; 0 ; DATA XREF: P_Move+D8^r
.bss:00483710                             ; PIT_CheckLine+DC^w ...
.bss:00483730 tmbbox        dd 4 dup(?)   ; 0 ; DATA XREF: P_TeleportMove+33^w
.bss:00483730                             ; P_TeleportMove+EE^r ...
.bss:00483740 crushchange   dd ?          ; DATA XREF: PIT_ChangeSector+67^r
.bss:00483740                             ; sub_423F50+7^w
.bss:00483744 nofit         dd ?          ; DATA XREF: PIT_ChangeSector+6D^w
.bss:00483744                             ; sub_423F50+15^w ...

Is that from the DOS EXE, or Doom95? It is possible that the variables which follow spechit in memory are different, because a different compiler may have been used. For example, the layout in chocolate doom under Linux is like this:

080b1e20 B spechit
080b1e40 B crushchange
080b1e44 B slidemo
080b1e48 B numflats
080b1e4c B texturecolumnlump
080b1e50 B texturecolumnofs
080b1e54 B textureheight
080b1e58 B numpatches

I think I'm understanding your fix better now. It is the other variables (like tmbbox and crushchange) that are responsible for the de-syncing.

Edit: I think it is possible to figure out DOOM_runtime_lines_address (for the DOS DOOM.EXE) by using a debugger. It will be different for every version of the EXE. For Doom95 it is impossible, which means any demos recorded with Doom95 and overflowed spechit almost certainly would never playback correctly, even with Doom95, and maybe even on the same machine.

[entryway]

Ajapted said:

Is that from the DOS EXE, or Doom95?

From the Doom95, but it's identical in the DOS EXE

Edit: I think it is possible to figure out DOOM_runtime_lines_address (for the DOS DOOM.EXE) by using a debugger.

Yes of course

buf_overrun_item_t overrun_data[] = 
{
// wadname;        map; address;
  {"HR.WAD",        18, 0x01C09C98},
  {"STRAIN.WAD",    07, 0x01D6CF98},
  {NULL,            00, 0x00000000},
};

But it is not possible generally because it depends on client parameters such as with or without a sound the demo was recorded (additional memory allocations)

[andrewj]

I see. Looks like tmbbox is the big problem (crushchange and nofit are boolean, hence any address will be considered 'true'). tmbbox is very nasty because it affects how future lines are handled by PIT_CheckLine.

[Grazza]

Another map where you can get a spechits overrun is Memento Mori map08. Prboom 2.2.6.23 provided the following information:

The list of LinesID leading to overrun: 711, 723, 728, 733, 734, 738, 715, 727, 737.

However, it didn't cause a desync in the demo that I was watching (mm08-233). I haven't checked it with other demos on this map (though I don't recall any problems in the past with mm08 demos either - maybe this one is largely benign for some reason).

[myk]

If PrBoom plus can detect the lines that can cause the error, couldn't a command line parameter with variables be added so users can make the engine emulate the bug per map and line manually? Such as:

PrBoom -file mm mmmus -playdemo mmmovie -specbug 08 723

(That would be applying the bug on line 723 in map08 but you could add more maps with corresponding error-causing lines.)

If this were possible, with a bit of testing a player could make demos synch, helping debugging and not having to depend on the internal list for every map out there.

[Linguica]

Sure you could hardcode certain demos to screw up at certain times I guess, but that's pretty hacky.

In other news, it's too bad that Doom demos can never be fully emulated in a source port, goodbye everyone! Last one out turn off the light!

[Grazza]

myk said:

If PrBoom plus can detect the lines that can cause the error

It reports the lines responsible when an overrun occurs; it doesn't detect potential problems in advance.

myk said:

, couldn't a command line parameter with variables be added so users can make the engine emulate the bug per map and line manually? ... If this were possible, with a bit of testing a player could make demos synch, helping debugging and not having to depend on the internal list for every map out there.

Andrey did mention that he planned to implement a feature of that type, though it sounds like it is a little more complex to provide the engine with the "magic number" that it requires.

I agree that this feature together with an internal list sounds like the best fix we're likely to get, barring some breakthrough in emulating the general case.

Linguica said:

Sure you could hardcode certain demos to screw up at certain times

This would be map-specific info, rather than demo-specific. Once it is in the exe or the command-line, other demos recorded or played back on the map in question should be OK. It's not necessarily a case of them "screwing up" either - STRAIN map07 is a map where the overrun is necessary for the map to work (you can't exit without it), and in other cases it normally manifests itself as just a small change in behaviour due to the lost information - you don't start noclipping through walls or whatever.

[myk]

Grazza said:
It reports the lines responsible when an overrun occurs; it doesn't detect potential problems in advance.

Yeah, that's why I thought first you'd get the report and then you'd have to specify some info (not sure exactly what, so I made a guess above) to play it back properly.

I still don't understand why Doom95 is compatible with Doom while any other engine can't be. Is it because the code released is different than the one used by id and by Microsoft?

[Graf Zahl]

myk said:

I still don't understand why Doom95 is compatible with Doom while any other engine can't be. Is it because the code released is different than the one used by id and by Microsoft?

It depends how the variables are sorted in the data segment. Doom95 has it identical to Doom.exe for the really important ones. Modern compilers tend to optimize their internal data which can result in a different memory layout. Of course this only applies unless the variables are changed completely (as is necessary for removing such a limit.)

[Linguica]

Out of curiosity, could this be the reason why multiplayer games have that extremely rare error where suddenly people start clipping through walls?

[Grazza]

I don't know of any instances of a spechits overrun leading to effects such as that - the effects are normally a lot less obvious.

If you have any demos of the type you describe, you could run them through Prboom 2.2.6.23, and see if it comes up with the spechits overrun message.

I've tested Ledmeister's weird blackbug and manorbug demos, and they are not due to this effect (no spechits overrun message, at any rate). This post sheds light on what causes that.

[andrewj]

myk said:

I still don't understand why Doom95 is compatible with Doom while any other engine can't be. Is it because the code released is different than the one used by id and by Microsoft?

I doubt it. My guess is that the same compiler was used.

If PrBoom plus can detect the lines that can cause the error, couldn't a command line parameter with variables be added so users can make the engine emulate the bug per map and line manually?

The bug is demo dependent. It depends on how much memory (in the zone) is allocated, and that is affected by what command-line parameters were used to record the demo (and probably other stuff like how many sectors in the map).

The magic value is a 32-bit address, but even if only 20 or 24 bits are significant, that's still too many for a user to manually try out the possibilities. And it's not like you can do a binary search on it :).

[Jonathan]

Couldn't you use a disassembler to produce a memory map of the original executable data segment, showing what data is stored where. Then have your port detect when overflows would have occurred, use the map to determine what data would have been overwritten and make corresponding changes in the port's data?

Edit: Fuck, I followed a link to this thread from the demos forum and didn't realise it was this old. Oh well...

[Linguica]

ROFL, I had completely forgotten this thread and didn't notice the date until I got down to a post I wrote and was like "uhh what?"

[fraggle]

Jonathan said:

Couldn't you use a disassembler to produce a memory map of the original executable data segment, showing what data is stored where. Then have your port detect when overflows would have occurred, use the map to determine what data would have been overwritten and make corresponding changes in the port's data?

The value that should be written depends on where allocated things are placed on the heap, so no.

[Quasar]

xl = (tmbbox[BOXLEFT]   - bmaporgx - MAXRADIUS) >> MAPBLOCKSHIFT;
xh = (tmbbox[BOXRIGHT]  - bmaporgx + MAXRADIUS) >> MAPBLOCKSHIFT;
yl = (tmbbox[BOXBOTTOM] - bmaporgy - MAXRADIUS) >> MAPBLOCKSHIFT;
yh = (tmbbox[BOXTOP]    - bmaporgy + MAXRADIUS) >> MAPBLOCKSHIFT;

What tmbbox does is record the extents of an mobj_t during a clipping operation (it is a nasty global variable). If it gets overwritten by a spechit overflow, it has the effect of moving the object currently being considered. However, before use it is always scaled down drastically in order for the positions to be used as blockmap indices. This means that in a large number of circumstances, most of the number is insignificant.

BTW, I have also verified that all the other variables overwritten by larger spechit overflows are insignificant, because the game engine will always overwrite them again with valid values before using them between the time a spechit overflow occurs and the next clipping operation starts. They are all static globals defined in p_map.c