Overflow of array of the crossed special lines

Doomworld Forums : Powered by vBulletin version 2.2.5

Doomworld Forums > Classic Doom > WADs & Mods > Overflow of array of the crossed special lines

Author

All times are GMT. The time now is 11:48.

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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
http://prboom-plus.sourceforge.net/temp/spechit_av05.gif

Hell Revealed\MAP18
http://prboom-plus.sourceforge.net/temp/spechit_hr18.gif

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.

Last edited by entryway on 12-06-05 at 15:37

12-06-05 15:16 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Kristian Ronge
Senior Member

Posts: 1929
Registered: 11-03

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)

12-06-05 18:40 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Szymanski

Posts: 995
Registered: 08-00

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

12-06-05 19:03 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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:

code:
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
---------------------------

Last edited by entryway on 12-06-05 at 19:46

12-06-05 19:26 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

DaniJ
Senior Member

Posts: 1958
Registered: 08-03

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?

12-06-05 22:41 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Grazza
Inventor of "Y Y" to quit

Posts: 11784
Registered: 07-02

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.

12-06-05 22:47 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

DaniJ
Senior Member

Posts: 1958
Registered: 08-03

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.

12-06-05 23:30 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Grazza
Inventor of "Y Y" to quit

Posts: 11784
Registered: 07-02

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.

12-07-05 01:34 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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.

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

12-07-05 07:56 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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.

code:
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;
    }
  }
}

12-07-05 09:56 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

andrewj
Senior Member

Posts: 1518
Registered: 04-02

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.

12-07-05 10:39 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

DaniJ
Senior Member

Posts: 1958
Registered: 08-03

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.

12-07-05 11:24 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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.

Last edited by entryway on 12-07-05 at 11:38

12-07-05 11:32 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

andrewj
Senior Member

Posts: 1518
Registered: 04-02

[QUOTE]entryway said:

code:.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:

code: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.

Last edited by andrewj on 12-07-05 at 13:23

12-07-05 13:17 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

entryway
Forum Staple

Posts: 2666
Registered: 01-04

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

code: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)

12-07-05 13:57 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

andrewj
Senior Member

Posts: 1518
Registered: 04-02

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.

12-07-05 14:56 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Grazza
Inventor of "Y Y" to quit

Posts: 11784
Registered: 07-02

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).

12-18-05 11:32 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

myk

Posts: 14809
Registered: 04-02

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.

12-18-05 17:35 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Linguica

Posts: 3700
Registered: 05-00

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!

12-18-05 17:53 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Grazza
Inventor of "Y Y" to quit

Posts: 11784
Registered: 07-02

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.

12-18-05 17:57 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

myk

Posts: 14809
Registered: 04-02

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?

12-18-05 19:03 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Graf Zahl
Why don't I have a custom title by now?!

Posts: 7451
Registered: 01-03

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.)

12-18-05 19:14 #

Profile || Blog || PM || Email || Search || Add Buddy

IP || Edit/Delete || Quote

Linguica

Posts: 3700
Registered: 05-00

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

12-19-05 00:19 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Grazza
Inventor of "Y Y" to quit

Posts: 11784
Registered: 07-02

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.

12-19-05 01:11 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

andrewj
Senior Member

Posts: 1518
Registered: 04-02

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 :).

12-19-05 01:21 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Jonathan
I am not a leet hax0r :(

Posts: 692
Registered: 05-00

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...

02-08-07 00:34 #

Profile || Blog || PM || Email || Search || Add Buddy

IP || Edit/Delete || Quote

Linguica

Posts: 3700
Registered: 05-00

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?"

02-08-07 01:27 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

fraggle
Super Moderator

Posts: 6568
Registered: 07-00

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.

02-08-07 09:21 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 5154
Registered: 08-00

code:
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

02-08-07 20:20 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

All times are GMT. The time now is 11:48.

Doomworld Forums > Classic Doom > WADs & Mods > Overflow of array of the crossed special lines

Show Printable Version |

Email this Page |

Subscribe to this Thread

Forum Rules:

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

HTML code is OFF
vB code is ON
Smilies are OFF
[IMG] code is ON

< Contact Us - Doomworld >