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

File:Hash2-0.png

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.

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

Initialize Subsystems

Next, the game's subsystems are initialized by iterating through the subsystem table and calling the init 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 physicalpagecount.

Initialize Pages

Physical Pages

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

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 data field, initialization for each physical page structure also involves appropriately initializing the state, rw, index, and requests fields: 

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

Virtual Pages (?)

The routine then sets virtualpagecount to 38, and initializes all 38 reserved virtual page structures (virtualpages) in the paging system structure. These are initialized differently from physical page structures: 

• data is set to 0; this indicates that the page structure does not reference a physical page of memory and consequently describes a virtual page
• rw is set to 0; this indicates some sort of page replacement mode and is different for virtual pages
• index 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. printf("Inited and Allocated %d pages\n", NSD.physicalpagecount); 

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.