Talk:Reject

From DoomWiki.org

When you extract the packed reject table into a file, using a program like DETH, it pads the hex output to the next highest multiple of 16 bytes.  For instance, the table for E1M1 is 968 = 16 × 60.5 bytes long, so 8 extra bytes are added to the dump.  I managed to figure out (using RMB) that they were all at the end.  They aren't zero.  They don't duplicate the first 8 bytes.  What are they?  Are they, for example, the first 8 bytes of the next lump?  (If so, does that mean that some of the padding occurs at the beginning of the list for other levels, depending on the absolute starting address of the reject lump?  Sheesh.)    Ryan W 21:16, 25 August 2007 (UTC)

Loading of reject from file is in lxdoom-1.10 p_setup.c:660
rejectmatrix = W_CacheLumpNum (lumpnum+ML_REJECT,PU_LEVEL);
W_CacheLumpNum allocates memory for a lump equal to the size of the lump as specified in the wad, and loads the lump into that memory. So this code doesn't care how much padding is on reject, or even if the reject table is at all properly sized for the wad.
Using of reject is in p_sight.c:294-348. excerpt:
s1 = (t1->subsector->sector - sectors);
s2 = (t2->subsector->sector - sectors);
pnum = s1*numsectors + s2;
bytenum = pnum>>3;
bitnum = 1 << (pnum&7);

// Check in REJECT table.
if (rejectmatrix[bytenum]&bitnum)
{
  sightcounts[0]++;

  // can't possibly be connected
  return false;	
}
This code simply calculates which which bit the desired reject result ought to be in, and reads that far into the table for the result. No padding anywhere inside the table is allowed. Padding at the end is ignored. If the reject table is too short, the function will simply read off the end into whatever garbage is in memory next. So the only nessecary padding is to fill up the last byte if numsect * numsect is not divisible by 8.
ZenNode 1.21 does the following. ZenReject.cpp:248-252
int noSectors  = level->SectorCount ();
int rejectSize = (( noSectors * noSectors ) + 7 ) / 8;

UINT8 *reject = new UINT8 [ rejectSize ];
memset ( reject, 0, rejectSize );
The code then proceeds to fill all bits corresponding to sector lookups with the calculated reject data, while leaving all other bits zero. The only padding ZenNode applies is the + 7, which simply rounds up to the next byte; if numsect * numsect is not divisible by 8, the division by 8 would truncate and leave no room for the spillovers into the last byte.
As far as your example case goes, I'd have to chalk it up to an error in Deth (which uses an earlier version of zennode I believe). The idbsp generated rejects in the original iwad also don't contain any extra padding. 71.58.109.233 21:53, 18 September 2007 (UTC)
Wow!
I only understand about a third of that, but I think it means "the padding is at the end", which is what I asked.  :>   The nodes I used are the OEM nodes, not built by DETH or any other program after the fact — sorry if that was unclear, and hopefully that doesn't change your whole line of reasoning (although IMHO this is a valuable posting and should be kept here in any case).
Realistically, if the padding were anywhere except the end, whereas my spreadsheet assumes that it is at the end, the unpacked file would be overflowing with garbage which was flatly contradicted by playtesting.  After 4 levels, so far so good, however.    Ryan W 00:00, 19 September 2007 (UTC)
Sorry about the verbosity; my idea is with a lot of code references, anyone who is inclined can pick this up and try to figure out something from where I left off. The short version is that if there is any padding in a reject lump, it MUST be at the end, and that the one example node builder I looked at, ZenNode 1.21, inserts no padding other than to the nearest byte (which is the minimun nessecary). When you say "The nodes I used are the OEM nodes" though, I don't quite get you; I'm showing the following numbers for ultimate doom e1m1 (my iwad matches the md5 given somewhere else at this site): NumSectors = 88; RejectSize = 968. This fits exactly with zero padding. 71.58.109.233 00:12, 19 September 2007 (UTC)
Nothing wrong with verbosity if you're trying to help someone out, especially when it's plaintext and someone you don't know (therefore very easy to misinterpret terseness as an insult.  :>   The E1M1 lump in my IWAD is 968 bytes as well; however, DETH exports the following.
Contents of entry REJECT (size = 968 bytes):
0000:  00 00 00 02 00 00 04 00 45 02 D2 00 00 00 00 00           E Ò     
0010:  00 00 00 04 80 C1 00 00 00 00 00 00 02 00 47 02       €Á        G 
0020:  D3 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00   Ó               
0030:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0040:  00 00 00 80 20 9B 00 02 0C 22 04 00 C0 00 00 00      € ›   "  À   
0050:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0060:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0070:  00 00 00 00 00 00 00 00 00 00 00 00 02 00 00 DC                  Ü
0080:  24 04 02 D2 00 00 00 03 00 00 CC 20 47 00 D0 00   $  Ò      Ì G Ð 
0090:  00 00 03 00 00 DC 24 47 00 D1 00 00 00 00 00 82        Ü$G Ñ     ‚
00A0:  00 00 47 02 D3 40 00 00 00 00 00 00 00 44 82 43     G Ó@       D‚C
00B0:  00 00 00 18 00 02 CE 22 45 82 D3 00 00 00 00 00         Î"E‚Ó     
00C0:  00 00 00 00 00 00 00 00 00 80 01 87 80 00 47 82            € ‡€ G‚
00D0:  D3 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00   Ó               
00E0:  00 00 00 00 00 00 00 40 00 00 00 00 02 00 00 44          @       D
00F0:  80 43 00 00 00 00 00 87 80 00 47 02 D3 00 00 00   €C     ‡€ G Ó   
0100:  00 00 02 00 00 47 02 D3 40 30 00 00 00 02 10 80        G Ó@0     €
0110:  47 82 D3 41 38 00 80 00 02 80 80 47 82 D3 00 00   G‚ÓA8 €  €€G‚Ó  
0120:  00 00 00 00 00 00 00 00 00 40 00 01 00 00 00 42            @     B
0130:  00 47 82 D2 40 00 01 00 00 00 42 00 47 82 D2 00    G‚Ò@     B G‚Ò 
0140:  00 00 00 00 00 00 00 04 02 D2 00 00 00 00 00 00            Ò      
0150:  00 00 00 00 00 40 00 04 02 00 00 42 10 07 82 D2        @     B  ‚Ò
0160:  00 00 04 00 00 00 42 00 04 02 D2 00 00 00 00 00         B   Ò     
0170:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0180:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0190:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
01A0:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
01B0:  00 00 00 00 00 00 00 00 00 00 44 00 00 00 40 00             D   @ 
01C0:  04 02 D2 40 40 E5 03 00 00 C6 30 47 82 D2 00 00     Ò@@å   Æ0G‚Ò  
01D0:  44 00 00 00 40 00 04 02 D2 00 00 00 00 00 00 00   D   @   Ò       
01E0:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
01F0:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0200:  00 00 00 00 00 00 40 44 00 00 00 42 20 04 02 D2         @D   B   Ò
0210:  00 00 00 00 00 00 00 00 00 00 00 04 00 01 98 01                 ˜ 
0220:  82 00 00 00 80 40 41 38 01 00 00 02 00 00 00 82   ‚   €@A8       ‚
0230:  42 40 38 01 00 00 00 20 34 00 00 C0 00 28 00 01   B@8     4  À (  
0240:  00 00 00 30 00 00 C0 00 00 00 00 00 00 08 00 00      0  À         
0250:  00 00 00 38 01 98 01 87 00 80 44 00 00 00 38 45      8 ˜ ‡ €D   8E
0260:  02 00 02 00 80 47 00 10 00 00 00 00 00 00 00 00       €G          
0270:  40 00 40 40 00 01 00 00 00 00 00 40 00 40 00 28   @ @@       @ @ (
0280:  00 00 00 00 08 00 04 00 00 00 00 00 00 00 00 00                   
0290:  00 00 00 00 00 00 00 80 00 02 18 80 47 82 D3 40          €   €G‚Ó@
02A0:  38 01 00 00 82 18 80 47 82 53 00 00 00 00 00 00   8   ‚ €G‚S      
02B0:  00 00 00 00 00 00 00 00 03 00 00 C0 30 47 00 D1              À0G Ñ
02C0:  05 70 C5 9B 00 02 80 B0 40 02 42 04 70 C4 9B 00    pś  €°@ B pě 
02D0:  02 80 B0 00 00 00 47 F8 E5 BB 01 87 C0 B4 00 82    €°   Gøå» ‡ÀŽ ‚
02E0:  C3 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00   Ã               
02F0:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0300:  00 00 05 F0 E5 1B 00 02 C0 B3 01 02 C2 00 00 00      ðå   À³     
0310:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0320:  00 00 00 05 C8 C5 BB 01 87 04 30 45 00 D0 00 00       ÈÅ» ‡ 0E Ð  
0330:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0340:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0350:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00                   
0360:  00 00 00 00 00 02 80 25 9B 00 02 06 30 04 00 C0         €%›   0  À
0370:  06 E0 E5 03 00 00 00 B0 04 00 C0 05 C8 E5 BB 01    àå    °  À Èå» 
0380:  87 04 30 45 00 C0 00 00 00 00 00 00 00 00 00 00   ‡ 0E À          
0390:  00 00 00 00 00 00 00 00 00 00 00 00 05 78 C5 BB                xÅ»
03A0:  01 87 80 B0 00 02 00 00 00 00 00 00 00 00 00 00    ‡€°            
03B0:  00 00 47 F8 E5 BB 01 87 1E B3 45 82 03 47 78 C5     Gøå» ‡ ³E‚ GxÅ
03C0:  BB 01 87 18 90 44 82 03 F8 FC F8 EC 24 00 17 00   » ‡ D‚ øüøì$   
See, 8 extra bytes.    Ryan W 02:40, 19 September 2007 (UTC)
Found it. Deth 4.24, wads.c:569+; as best as I can tell this should occur when using the dump feature for any lump; it will always round up to the next 16 bytes. Extra bytes read will be whatever comes right after the entry in the wad file; if it was the end of the wad file, the program should crash gracefully with a read error. 71.58.109.233 03:06, 19 September 2007 (UTC)
Wow again!
if it was the end of the wad file, the program should crash gracefully   Which is probably a bug if it doesn't actually dump anything first (DETH seems not to be under development anymore, however, so we'll have to live with that one).
If the reject table is too short, the function will simply read off the end   Which, as even I know, can have some of the most bizarre and convoluted side effects known to man.  I remember this being discussed on the Doomworld forums also: there are apparently established WADs with faulty REJECT tables, and the question was, can Chocolate Doom emulate all the crashes and so forth, as well as not desyncing whenever DOS would unethically have allowed some demo to play correctly?
In any case, I'm now quite satisfied that my unpacking procedure was correct, and now I just have to wait a few years until Wikia decides whether my hex post should be deleted as a copyvio.   :>     Ryan W 14:15, 19 September 2007 (UTC)