View source for Paging and Subsystem Initialization

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.

== Routine Location ==
The Paging and Subsystem Initialization routine is located at the following addresses in each of the Crash games:
* Crash 1 - 0x15B58

== 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 <code>0x5C528-</code>is passed as the second argument in each call to the Paging and Subsystem Initialization routine.

==== Format ====
TBD

==== Structure ====
<syntaxhighlight lang="cpp">
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
};
</syntaxhighlight>

== Operation ==
The <code>inited</code> 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 <code>NSD</code> field of the paging system structure.

=== Record Entry Hash Pointers  ===
With the NSD contents in main memory, pointers to its <code>entryhashoffsets</code> and <code>entryhash</code> arrays, respectively, are recorded in <code>entryhashbuckets</code> and <code>entryhash</code> of the paging system structure.

=== Record Level Header Pointer ===
At this point, a pointer to the NSD's <code>levelheader</code> 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 (<code>entryhashcount</code>) to its location (<code>entryhash</code>), and stored in <code>levelheader</code> of the paging system structure. [calculated without pointer arithmetic this is entryhash+(8*entryhashcount)]. The NSD's <code>levelheader</code> 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 <code>execeidmap</code>-an array that maps object types to GOOL executable entries.

=== Initialize Entry Hash Table ===
The <code>entryhash</code> array, or entry hash table, is a list of key-value pairs. The <code>entryhashoffsets</code> array is a list of relative offsets into the <code>entryhash</code> 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 <code>&entryhash[entryhashoffset[c]]</code> (where c is an iterator). <code>entryhashbuckets</code> of the paging system structure now refers to the updated array of pointers. 

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

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

=== 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 page 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 page 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 page structures (once created.) 

=== Initialize Subsystems ===
Next, the game's subsystems are initialized by iterating through the subsystem table and calling the <code>init</code> callback of each subsystem.

=== Allocate Pages ===
A physical page of memory is 64kb (0x10000 bytes) in size. At this point, the routine attempts to allocate space for at most 22 physical pages (22 x 0x10000 bytes) of memory-if there is not enough space then it continues to try for 21 pages, 20, and so on. The total number of physical pages allocated is then stored in <code>physicalpagecount</code>. 

=== Initialize Pages ===

==== Physical Pages ====
The routine then initializes <code>physicalpagecount</code> of the reserved/statically allocated physical page structures (i.e. <code>physicalpages</code>) in the paging system structure. For each of the <code>physicalpagecount</code> structures, the <code>data</code> field is pointed to its own successively contiguous 64kb physical page of memory from the block allocated. 

</p>Each physical page structure now refers to its own 64kb physical page of memory, and each referenced physical page will eventually be used to contain a 64kb chunk for paging in from the NSF file. 

In addition to determining the location of the physical page for the <code>data</code> field, initialization for each physical page structure also involves appropriately initializing the <code>state</code>, <code>rw</code>, <code>index</code>, and <code>requests</code> fields: 

* <code>state</code> is set to 1; this is the initial state for the page structure and indicates that its page is a clean, blank slate page.
* <code>rw</code> is set to 1; this indicates some sort of page replacement mode
* <code>index</code> is set to the index of the physical page allocated to the page structure
* <code>requests</code> is set to 0; this indicates the number of unprocessed requests to read from the structure's page

==== Virtual Pages (?) ====
The routine then sets <code>virtualpagecount</code> to 38, and initializes all 38 reserved virtual page structures (<code>virtualpages</code>) in the paging system structure. These are initialized differently from physical page structures: 

* <code>data</code> is set to 0; this indicates that the page structure does not reference a physical page of memory and consequently describes a virtual page 
* <code>rw</code> is set to 0; this indicates some sort of page replacement mode and is different for virtual pages
* <code>index</code> is set to 0; this field is unused and therefore zeroed because the index of a physical page is irrelevant when no physical page has been allocated for this (virtual) page

=== Print Debug Message ===
When all pages have been allocated and initialized, the game writes to standard output a confirmation message with the number of physical pages allocated, i.e. <code>printf("Inited and Allocated %d pages\n", NSD.physicalpagecount);</code> 

=== Initialize Texture and Wavebank Page Structures ===
At this point the game initializes 16 texture page structures and 8 wavebank page structures. These differ from normal physical page structures in that the memory they reference is located in video or sound hardware.

This section is TBD.