Difference between revisions of "Paging and Subsystem Initialization"

From Crash Bandicoot Hacking Wiki
Jump to navigation Jump to search
Line 55: Line 55:
  
 
[[File:Hash2-0.png|left|thumb|635x635px]]                 
 
[[File:Hash2-0.png|left|thumb|635x635px]]                 
 
  
  
 
The universe of keys in the entry hash table is composed of all possible EIDs [of entries] from the NSF file. Initially, each slot in the table pairs an EID (key) with the CID (value) of the chunk that contains the entry with that EID. Thus, the table initially associates each entry with its parent chunk.
 
The universe of keys in the entry hash table is composed of all possible EIDs [of entries] from the NSF file. Initially, each slot in the table pairs an EID (key) with the CID (value) of the chunk that contains the entry with that EID. Thus, the table initially associates each entry with its parent chunk.
  
<p></p><p>Eventually, a request will be made to page an entry's content into main memory. Throughout the game, this is done by specifying the EID of an entry with desired content as the argument in a call to the entry paging routine. The entry paging routine ultimately pages the <i>chunk</i> that contains the entry, rather than the entry alone. It accomplishes this by:&nbsp;</p>
+
<p>Eventually, a request will be made to page an entry's content into main memory. Throughout the game, this is done by specifying the EID of an entry with desired content as the argument in a call to the entry paging routine. The entry paging routine ultimately pages the <i>chunk</i> that contains the entry, rather than the entry alone. It accomplishes this by:&nbsp;</p><li>Calculating the EID's hash with the hash function: <code data-rte-washtml="1">(EID &lt;&lt; 15) &amp; 0xFF</code></li><li>Using the hash as an index into the <code>entryhashbuckets</code>&nbsp;pointer array to locate the associated bucket</li><li>Starting the search for the pair with key <code>EID</code> at the pointed index</li><li>Obtaining the accompanying <code>CID</code> value for the pair upon finding a match</li><li>Using the NSD to determine the sector position and/or size of the chunk with that CID</li><li>Reading from disc at the corresponding sector position to a free page    </li>
<li>Calculating the EID's hash with the hash function: <code data-rte-washtml="1">(EID &lt;&lt; 15) &amp; 0xFF</code></li><li>Using the hash as an index into the <code>entryhashbuckets</code>&nbsp;pointer array to locate the associated bucket</li><li>Starting the search for the pair with key <code>EID</code> at the pointed index</li><li>Obtaining the accompanying <code>CID</code> value for the pair upon finding a match</li><li>Using the NSD to determine the sector position and/or size of the chunk with that CID</li><li>Reading from disc at the corresponding sector position to a free page    </li>
 
 
<p>With the chunk contents in main memory, the entry paging routine then locates the requested entry [within the chunk data] and returns a pointer.</p>
 
<p>With the chunk contents in main memory, the entry paging routine then locates the requested entry [within the chunk data] and returns a pointer.</p>
<li><h3 data-rte-new-node="true"> </h3><p>
+
 
</p></li>
+
=== Record NSF Location ===
 +
At this point the level id is used as an index into the filesystem map at <code>0x5E03C</code> to determine the sector location of the current NSF file, and this is recorded in <code>NSFlocation</code> of the paging system structure.
 +
 
 +
=== Initialize Page Map ===
 +
At this point, space is allocated for <code>chunkcount</code> pointers to pageinfo structures with malloc, and a pointer to the newly allocated space is stored in <code>pagemap</code> of the paging system structure. Each of these pointers is then initialized with the value <code>0xFFFFFFEE</code>, a constant identified as the ''null pageinfo pointer''. The page map, indexed by index of chunks in the NSF file (chunk index = <code>(CID >> 1)</code>), will eventually be used to map chunks to their associated pageinfo structures (once created.) 
 +
 
 +
 </p>

Revision as of 23:16, 26 July 2015

In the Crash games, Paging and Subsystem Initialization is the process of readying the system to transfer (page) game content from a specified NSF file on disc into main memory. Using the NSF file's paired NSD file or index, the process occupies a structure with all the information needed to effectively page its content.

Paging System Structure

The Paging and Subsystem Initialization routine requires as its second argument a pointer to the resultant 'paging system structure'. As a result of the routine's execution, this structure is occupied with all the information needed to effectively page content from an NSF file. (The NSF file used is that of the level with ID specified in the first argument to the routine.)

Crash 1

In Crash 1, a pointer to the 'global paging system structure'-located at 0x5C528-is passed as the second argument in each call to the Paging and Subsystem Initialization routine.

Format

TBD

Structure

struct pagingsystem
{
  bool inited;                     // 0x5C528
  unsigned long levelid;           // 0x5C52C
  void **entryhashindices;         // 0x5C530
  struct hashpair *entryhash;      // 0x5C534
  unsigned long ???;               // 0x5C538
  void *levelheader;               // 0x5C53C
  struct NSD *NSD;                 // 0x5C540
  unsigned long ???;               // 0x5C544
  unsigned long NSFlocation;       // 0x5C548
  unsigned long flag;              // 0x5C54C
  unsigned long physicalpagecount; // 0x5C550
  struct page physicalpages[22];   // 0x5C554
  unsigned long virtualpagecount;  // 0x5C91C
  struct page virtualpages[38];    // 0x5C920
  unsigned long pagecount;         // 0x5CFA8
  struct page *currentlypaging;    // 0x5CFAC
  void *itemlist;                  // 0x5CFB0
  struct page *mostrecent8;        // 0x5CFB4
  unsigned long CIDpaging;         // 0x5CFB8
  struct page **pagemap;           // 0x5CFBC
};

Operation

The inited flag is first checked to determine whether the paging system has previously been initialized (by this routine). If so, a success code is returned, for the paging system has already been successfully initialized. If not, the routine proceeds to initialize the paging system.

Locate and Load NSD file

At this point, a string for the specified level id's corresponding NSD filename is constructed by concatenating "S00000", the level id, and ".NSD".

A filesystem map exists, which maps NSD files, indexed by level id, to their corresponding sector position and file size on disc; this map has been created by the hardware initialization routine. The level id is used as an index into this table and the malloc routine is used to allocate space of the corresponding file size. The system then begins reading from disc at the corresponding sector position to the newly allocated space. A pointer to this data is saved in the NSD field of the paging system structure.

Record Entry Hash Pointers 

With the NSD contents in main memory, pointers to its entryhashoffsets and entryhash arrays, respectively, are recorded in entryhashbuckets and entryhash of the paging system structure.

Record Level Header Pointer

At this point, a pointer to the NSD's levelheader must also be calculated since the preceding block of data in the file structure (i.e. the entry hash table) is of variable size. This pointer is calculated by adding the size of the entry hash table (entryhashcount) to its location (entryhash), and stored in levelheader of the paging system structure. [calculated without pointer arithmetic this is entryhash+(8*entryhashcount)]. The NSD's levelheader is a structure that specifies its corresponding level ID, the EID of the level's first zone(T7) entry and the index of the first camera path in that zone, an unknown value, and execeidmap-an array that maps object types to GOOL executable entries.

Initialize Entry Hash Table

The entryhash array, or entry hash table, is a list of key-value pairs. The entryhashoffsets array is a list of relative offsets into the entryhash array. Each offset locates the beginning (first pair) of a bucket in the open-addressing based entry hash table. At this point the routine calculates the corresponding absolute pointers by iterating through the 256 offset values and replacing them with &entryhash[entryhashoffset[c]] (where c is an iterator). entryhashbuckets of the paging system structure now refers to the updated array of pointers. 

                 


The universe of keys in the entry hash table is composed of all possible EIDs [of entries] from the NSF file. Initially, each slot in the table pairs an EID (key) with the CID (value) of the chunk that contains the entry with that EID. Thus, the table initially associates each entry with its parent chunk.

Eventually, a request will be made to page an entry's content into main memory. Throughout the game, this is done by specifying the EID of an entry with desired content as the argument in a call to the entry paging routine. The entry paging routine ultimately pages the chunk that contains the entry, rather than the entry alone. It accomplishes this by: 

  • Calculating the EID's hash with the hash function: (EID << 15) & 0xFF
  • Using the hash as an index into the entryhashbuckets pointer array to locate the associated bucket
  • Starting the search for the pair with key EID at the pointed index
  • Obtaining the accompanying CID value for the pair upon finding a match
  • Using the NSD to determine the sector position and/or size of the chunk with that CID
  • Reading from disc at the corresponding sector position to a free page    
  • With the chunk contents in main memory, the entry paging routine then locates the requested entry [within the chunk data] and returns a pointer.

    Record NSF Location

    At this point the level id is used as an index into the filesystem map at 0x5E03C to determine the sector location of the current NSF file, and this is recorded in NSFlocation of the paging system structure.

    Initialize Page Map

    At this point, space is allocated for chunkcount pointers to pageinfo structures with malloc, and a pointer to the newly allocated space is stored in pagemap of the paging system structure. Each of these pointers is then initialized with the value 0xFFFFFFEE, a constant identified as the null pageinfo pointer. The page map, indexed by index of chunks in the NSF file (chunk index = (CID >> 1)), will eventually be used to map chunks to their associated pageinfo structures (once created.)