Mancubus
Register | User Profile | Member List | F.A.Q | Privacy Policy | New Blog | Search Forums | Forums Home
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 10:35. Post New Thread    Post A Reply
entryway
Forum Staple


Posts: 2740
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

Old Post 12-06-05 15:16 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
Kristian Ronge
Senior Member


Posts: 1977
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)

Old Post 12-06-05 18:40 #
Kristian Ronge is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
Szymanski


Posts: 1017
Registered: 08-00


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

Old Post 12-06-05 19:03 #
Szymanski is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
entryway
Forum Staple


Posts: 2740
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

Old Post 12-06-05 19:26 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
DaniJ
Senior Member


Posts: 2148
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?

Old Post 12-06-05 22:41 #
DaniJ is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
Grazza
Let's try Caesium


Posts: 12512
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.

Old Post 12-06-05 22:47 #
Grazza is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
DaniJ
Senior Member


Posts: 2148
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.

Old Post 12-06-05 23:30 #
DaniJ is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
Grazza
Let's try Caesium


Posts: 12512
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.

Old Post 12-07-05 01:34 #
Grazza is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
entryway
Forum Staple


Posts: 2740
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); ...

Old Post 12-07-05 07:56 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
entryway
Forum Staple


Posts: 2740
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; } } }

Old Post 12-07-05 09:56 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
andrewj
Senior Member


Posts: 1641
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.

Old Post 12-07-05 10:39 #
andrewj is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
DaniJ
Senior Member


Posts: 2148
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.

Old Post 12-07-05 11:24 #
DaniJ is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
entryway
Forum Staple


Posts: 2740
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

Old Post 12-07-05 11:32 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
andrewj
Senior Member


Posts: 1641
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

Old Post 12-07-05 13:17 #
andrewj is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
entryway
Forum Staple


Posts: 2740
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)

Old Post 12-07-05 13:57 #
entryway is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
andrewj
Senior Member


Posts: 1641
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.

Old Post 12-07-05 14:56 #
andrewj is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
Grazza
Let's try Caesium


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

Old Post 12-18-05 11:32 #
Grazza is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
myk
volveré y seré millones


Posts: 15231
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.

Old Post 12-18-05 17:35 #
myk is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
Linguica


Posts: 4091
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!

Old Post 12-18-05 17:53 #
Linguica is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
Grazza
Let's try Caesium


Posts: 12512
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.

Old Post 12-18-05 17:57 #
Grazza is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
myk
volveré y seré millones


Posts: 15231
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?

Old Post 12-18-05 19:03 #
myk is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
Graf Zahl
Why don't I have a custom title by now?!


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

Old Post 12-18-05 19:14 #
Graf Zahl is online now Profile || Blog || PM || Email || Search || Add Buddy IP || Edit || Quote
Linguica


Posts: 4091
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?

Old Post 12-19-05 00:19 #
Linguica is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
Grazza
Let's try Caesium


Posts: 12512
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.

Old Post 12-19-05 01:11 #
Grazza is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit || Quote
andrewj
Senior Member


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

Old Post 12-19-05 01:21 #
andrewj is offline Profile || Blog || PM || Search || Add Buddy IP || Edit || Quote
Jonathan
I am not a leet hax0r :(


Posts: 763
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...

Old Post 02-08-07 00:34 #
Jonathan is offline Profile || Blog || PM || Email || Search || Add Buddy IP || Edit || Quote
Linguica


Posts: 4091
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?"

Old Post 02-08-07 01:27 #
Linguica is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
fraggle
Filled with the code of Doom


Posts: 7830
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.

Old Post 02-08-07 09:21 #
fraggle is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
Quasar
Moderator


Posts: 6175
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

Old Post 02-08-07 20:20 #
Quasar is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit || Quote
All times are GMT. The time now is 10:35. Post New Thread    Post A Reply
 
Doomworld Forums : Powered by vBulletin version 2.2.5 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 >

Powered by: vBulletin Version 2.2.5
Copyright ©2000, 2001, Jelsoft Enterprises Limited.