dimanche 23 février 2020

Microcode Optimization: IMEM (Part3)

G_TEXTURE

This command simply set the parameters related to textures (texture off/on, tile, level and scale).
The code related to the immediate is the following:

0x2A0    SW    T9, 0x0010(SP)
0x2A4    SW    T8, 0x0014(SP)
0x2A8    LH    V0, 0x0006(SP)
0x2AC    ANDI    V0, V0, 0xFFFD
0x2B0    ANDI    V1, T9, 0x0001
0x2B4    SLL    V1, V1, 0x1
0x2B8    OR    V0, V0, V1
0x2BC    J    0x0A8
0x2C0    SH    V0, 0x0006(SP)

Command example:

0xBB000101 (loaded in T9)
0xFFFFFFFF (loaded in T8)

Let’s analyze quickly the code:

0x2A0    SW    T9, 0x0010(SP)
0x2A4    SW    T8, 0x0014(SP)

The two words of the command is stored in a specific place in DMEM.
0x2A8    LH    V0, 0x0006(SP)

We load the lower bytes of the geometry mode in register V0. Here the related geometry flags as per gbi.h:

#define G_ZBUFFER            0x00000001
#define G_SHADE            0x00000004   
# define G_TEXTURE_ENABLE        0x00000002     /* Microcode use only */
# define G_SHADING_SMOOTH    0x00000200   
# define G_CULL_FRONT        0x00001000
# define G_CULL_BACK        0x00002000
# define G_CULL_BOTH        0x00003000   

0x2AC    ANDI    V0, V0, 0xFFFD

The code simply “clears” G_TEXTURE_ENABLE” flag (it simply becomes 0) potential set in the last byte of register V0.

0x2B0    ANDI    V1, T9, 0x0001

The code takes very last byte of the first word of the command in register V1.

0x2B4    SLL    V1, V1, 0x1

V1 is multiplied by 2.

0x2B8    OR    V0, V0, V1
       
Register V0, containing the cleared lower bytes of the geometry mode, is ORed by V1, containing the last byte of the 1st command multiply by 2.

0x2BC    J    0x0A8
0x2C0    SH    V0, 0x0006(SP)

Before exiting the command, the lower bytes of the geometry mode is stored back in DMEM.
Now some may say: what would be the underlying reasons to have the texture flag set in the last byte of the geometry mode?

Technically speaking when 3 transformed vertex are turned into an actual triangle RDP commands, this byte is used to construct the command header of such a command.

Let’s check out gbi.h:

#define G_TRI_FILL            0xc8 /* fill triangle:           
#define G_TRI_SHADE        0xcc /* shade triangle:          
#define G_TRI_TXTR            0xca /* texture triangle:        
#define G_TRI_SHADE_TXTR        0xce /* shade, texture triangle: 
#define G_TRI_FILL_ZBUFF        0xc9 /* fill, zbuff triangle:    
#define G_TRI_SHADE_ZBUFF        0xcd /* shade, zbuff triangle:   
#define G_TRI_TXTR_ZBUFF        0xcb /* texture, zbuff triangle: 
#define G_TRI_SHADE_TXTR_ZBUFF    0xcf /* shade, txtr, zbuff trngl:

For instance OR 0x02 (G_TEXTURE_ENABLE)  by 0xCC (G_TRI_SHADE) you get 0xCE, which is G_TRI_SHADE_TXTR, the textured version of  G_TRI_SHADE.

Now why not simply using the geometry mode flag? I would widely guess to for consistency purpose the intention was to keep texture parameters in the G_TEXTURE command. Nevertheless technically it does not make any sense! So let’s use as from now on the geometry mode flag for enabling/disabling textures. It would mean a tiny change for programmers.

Doing so would lead to all the below code to be useless:

0x2A8    LH    V0, 0x0006(SP)
0x2AC    ANDI    V0, V0, 0xFFFD
0x2B0    ANDI    V1, T9, 0x0001
0x2B4    SLL    V1, V1, 0x1
0x2B8    OR    V0, V0, V1
0x2BC    J    0x0A8
0x2C0    SH    V0, 0x0006(SP)

What remains would be:

0x2A0    SW    T9, 0x0010(SP)
0x2A4    SW    T8, 0x0014(SP)

It is simply storing two words in DMEM. We do have already a command to do so, G_MOVEWORD.

We simply have to have gSPTexture macro sending to two G_MOVEWORD commands. It does mean of course to create a new moveword indice, G_MW_TEXTURE.

#define G_MW_TEXTURE    0x120

#define gSPTexture(pkt, s, t, level, tile, on)   
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL((G_MW_TEXTURE), 0, 16);       
                                           
    _g->words.w1 = _SHIFTL(0x0000,16,16) | _SHIFTL((level),11,3) | _SHIFTL((tile),8,3)| _SHIFTL(0x00,0,8);       
};                                               
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL(((G_MW_TEXTURE) + 4), 0, 16);   
                                               
    _g->words.w1 = _SHIFTL((s),16,16) | _SHIFTL((t),0,16);                           
};                                               
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_CLEARGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16);   

    _g->words.w1 = (unsigned int)(0xFFFFFFFD);   
};                                               
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_SETGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16);   

    _g->words.w1 = (unsigned int)((on)<<1);       
};

#define gsSPTexture(s, t, level, tile, on)   
{{                                           
    (_SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL((G_MW_TEXTURE), 0, 16)),                   
    (_SHIFTL(0x0000,16,16) | _SHIFTL((level),11,3) | _SHIFTL((tile),8,3)| _SHIFTL(0x00,0,8))   
}},                                           
{{                                           
    (_SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL(((G_MW_TEXTURE) + 4), 0, 16)),                   
    (_SHIFTL((s),16,16) | _SHIFTL((t),0,16))                                                   
}},                                           
{{                                           
    (_SHIFTL(G_CLEARGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16)),               
    (unsigned int)(0xFFFFFFFD)               
}},                                           
{{                                           
    (_SHIFTL(G_SETGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16)),                   
    (unsigned int)((on)<<1)                   
}}

What does that mean? The complete G_TEXTURE is useless and can be scrapped, meaning that we get rid of 9 RSP instructions.

Finally we can create separate macros to update separately the 1st and the 2nd word of the gSPTexture.

#define gSPSetTextureTile(pkt, level, tile)       
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL((G_MW_TEXTURE), 0, 16);                                                           
    _g->words.w1 = _SHIFTL(0x0000,16,16) | _SHIFTL((level),11,3) | _SHIFTL((tile),8,3)| _SHIFTL(0x00,0,8);
 }   

#define gSPSetTextureScale(pkt, s, t)           
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL(((G_MW_TEXTURE) + 4), 0, 16);   
                                               
    _g->words.w1 = _SHIFTL((s),16,16) | _SHIFTL((t),0,16);                           
}   

#define gsSPSetTextureTile(level, tile, on)       
{{                                               
    (_SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL((G_MW_TEXTURE), 0, 16)),                   
    (_SHIFTL(0x0000,16,16) | _SHIFTL((level),11,3) | _SHIFTL((tile),8,3)| _SHIFTL(0x00,0,8))   
}}

#define gsSPSetTextureScale(s, t)               
{{                                               
    (_SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL(((G_MW_TEXTURE) + 4), 0, 16)),                   
    (_SHIFTL((s),16,16) | _SHIFTL((t),0,16))                               
}}   

Finally we can notice that storing the tile and the level of the texture requires only a mere byte. When we will start optimizing the DMEM, this point will have to be checked out.

RDRAM  <-> DMEM

The next step of our IMEM optimization concerns way the code moves data from RDRAM to DMEM or from DMEM to RDRAM. In order to do so, the code set a flag in a mere RSP register to inform in which the direction the data is moved from/to.

Let’s see a little bit how it works:

0x148    MTC0    S4, SP memory address
0x14C   BGTZ     S1, 0x015C
0x150   MTC0    S3, SP DRAM DMA address
0x154   JR            RA
0x158   MTC0    S2, SP read DMA length
0x15C   JR            RA
0x160   MTC0    S2, SP write DMA length

The above code is called as a subroutine in various part of the code.

Register S4 becomes in COP0 the DMEM address from which/where to the data are to be retrieved.
Register S3 becomes in COP0 the RDRAM address from which/where to the data are to be retrieved
Register S2 becomes in COP0, depending on whether S1 is or not greater than 0, the length from which is read/write from/to S4 the data.

Some may say it is an efficient code. Not really…

The issue is that you have to set register S1, depending on the direction of the data, as 0 or 1. Doing so requires an instruction before calling the subroutine so it is not really an efficient solution as it is of course possible to set the direction immediately after the return from the subroutine.

The code could be changed simply to:

0x148    MTC0    S4, SP memory address
0x14C   JR            RA
0x150   MTC0    S3, SP DRAM DMA address

On top on saving 4 instructions and free a register, it prepares the ground for some deeper future changes in the code.

And voila!

We will next time start working on the matrix related immediate commands :)
 

samedi 8 février 2020

Microcode Optimization: IMEM (Part2)

G_MOVEWORD

This immediate command simply stores a word in a specific DMEM address, which will be use as parameters for other commands. For instance such a command may be used to store the address of a segment, the number of lights, etc.


Hereby the original code managing such a command:

0x288    LBU    AT, 0xFFFB(K1)
0x28C    LHU    V0, 0xFFF9(K1)
0x290    LH    A1, 0x030E(AT)
0x294    ADD    A1, A1, V0
0x298    J    0x0A8
0x29C    SW    T8, 0x0000(A1)

0xBC000406 (loaded in register T9)
0x002D4CD0 (loaded in register T8)

It takes only 6 instructions, which is relatively reasonable. Let’s then go through the code step by step:

0x288    LBU    AT, 0xFFFB(K1)
0x28C    LHU    V0, 0xFFF9(K1)

The first instruction loads a byte in register AT and the second a half word in register V0 from the current command, meaning in our example AT = 0x06 and V0 = 0x0004 (half word).

0x290    LH    A1, 0x030E(AT)

The code then load from DMEM a half word in the register A1 which will be actually another DMEM address where the base address of the word to be stored.

0x294    ADD    A1, A1, V0

The offset AT is added to the base address A1.

0x29C    SW    T8, 0x0000(A1)

Finally the word of the command is stored at the proper DMEM address. In this respect it must be noticed that only the lower12 bits (due to the size of the memory) are considered by the SW instruction.

Let’s try to reduce the code necessary to perform this mere action. In this respect, the exact same trick used for G_TRI1 can be used actually, meaning that the adequate DMEM address could inserted directly in the command.

The moveword indices (AT) and offset (V0) are included in gbi.h, yet not the base DMEM address. Consequently it is necessary to list such DMEM address in order to include them as well. In order to do so, it is necessary to determine them by checking out the “mapping” of the DMEM memory for Fast3D in a microcode source file called GDMEM.H.

Having dressed all the base address related to G_MOVEWORD, we can simply add them to gbi.h and adapt the macros used such an immediate command (as for instance gSPSegment).

/* MOVEWORD indices */

#define G_MW_MATRIX        0x3E0   
#define G_MW_NUMLIGHT        0x12C
#define G_MW_CLIP            0x074
#define G_MW_SEGMENT        0x160
#define G_MW_FOG            0x330
#define G_MW_LIGHTCOL        0x1F0
#define    G_MW_PERSPNORM        0x110


#define gSPSegment(pkt, segment, base)       
{                                           
    Gfx *_g = (Gfx *)(pkt);                   
                                           
    _g->words.w0 = _SHIFTL(G_MOVEWORD , 24, 8) | _SHIFTL((G_MW_SEGMENT+((segment)*4)), 0, 16);

    _g->words.w1 = (unsigned int)(base);       
}

#define gsSPSegment(segment, base)       
{{                                       
    (_SHIFTL(G_MOVEWORD, 24, 8) | _SHIFTL((G_MW_SEGMENT+((segment)*4), 0, 16)),       
    (unsigned int)(base)                   
}}


In this example we have of course to multiply by 4 the segment number to align the DMEM address to a word :)

From there the command could structure as follow:

0xBC000AAA
0xBBBBBBBB

AAA is the DMEM address where the word should be stored and BBBBBBBB is the word to be stored.

The command can be reduced to only two simple instructions!!!! :)

J    0x0A8
SW    T8, 0x0000 (T9)

AAA being 12 bits, the higher bits of T9 are ignored.

And voila! We reduce the size of the code from 6 instructions to 2 instructions.

G_SETGEOMETRYRMODE/ G_CLEARGEOMETRYMODE

The code of G_SETGEOMETRYRMODE is the following:

0x348    LW    V0, 0x0004(SP)
0x34C    OR    V0, V0, T8
0x350    J    0x0A8
0x354    SW    V0, 0x0004(SP)

Here an example of a command:

0xB7000000 (loaded in T9)
0x00020000 (loaded in T8)

The code of G_CLEARGEOMETRYMODE is the following:

0x358    LW    V0, 0x0004(SP)
0x35C    ADDI    V1, R0, 0xFFFF
0x360    XOR    V1, V1, T8
0x364    AND    V0, V0, V1
0x368    J    0x0A8
0x36C    SW    V0, 0x0004(SP)

Here an example of a command:

0xB6000000 (loaded in T9)
0x001F3204 (loaded in T8)

Both commands together take 10 instructions. Let’s go quickly through the code of those commands.

G_SETGEOMETRYRMODE

0x348    LW    V0, 0x0004(SP)

The code loads from a specific place in DMEM the current graphic geometry mode (i.e. fog, lighting, etc.). It must be noticed that the SP register holds constantly a base DMEM address.

0x34C    OR    V0, V0, T8
0x350    J    0x0A8
0x354    SW    V0, 0x0004(SP)

The current geometry mode is then ORed by the bits set in the command before being stored back.

G_CLEARGEOMETRYMODE

0x35C    ADDI    V1, R0, 0xFFFF
0x360    XOR    V1, V1, T8
0x364    AND    V0, V0, V1
0x368    J    0x0A8
0x36C    SW    V0, 0x0004(SP)

After loading the current graphic geometry mode, the code will do something XOR the bits to be cleared contained in the second word of the command (0x loaded in T8) by 0xFFFFFFFF. So actually the code applies a NOR, which exists in the set of instructions for RSP!!!  Fun fact is that this “mistake” was noticed and in F3DEX the code uses as it should be NOR

But even with the NOR, it should be possible to do much better. I arrived to the following solution:

0x348    LW    V0, 0x004(SP)
0x34C    J    0x35C
0x350    AND     T8, V0, T8
0x354    LW    V0, 0x004(SP)
0x358    OR    T8, V0, T8
0x35C    J    0x0A8
0x360    SW    T8, 0x000(T9)

It looks like it takes now 7 instructions, which is already 3 instructions less. Now you may notice something interesting. The two last instructions are the one of the G_MOVEWORD, meaning that the actual implementation takes only 5 instructions!

The structure of the command would be as follow:

0xCC000DDD
0xAAAAAAAA

CC would be the command header.

DDD would be the DMEM address where the current geometry mode is stored.

AAAAAAAA would be the bits to be set or cleared by the command.   

How would all of this would then works?

G_CLEARGEOMETRYMODE

0x348    LW    V0, 0x004(SP)
0x34C    J    0x35C
0x350    AND     V0, V0, V1

It is not unnecessary to NOR the bits by the microcode as it can be achieved in gbi.h. By the way the DMEM address of the geometry mode has also to be included in the first word of the command in gbi.h

Then the code will then load the current graphic geometry mode, AND the already NORed bits to be cleared in register T8 and jump to 0x35C, which is the G_MOVEWORD code. And as the DMEM address of the geometry mode has been included in the first of the command.

G_SETGEOMETRYRMODE

0x354    LW    V0, 0x004(SP)
0x358    OR    T8, V0, T8
0x35C    J    0x0A8
0x360    SW    T8, 0x000(T9)

The current graphic geometry mode is loaded, then OReds by the bits to be set and will then naturally continue into the instructions of G_MOVEWORD.

Now of course we can create a macro to emulate gSPGeometryMode from F3DEX2 by sending both G_CLEARGEOMETRYMODE and G_SETGEOMETRYRMODE consecutively:

#define gSPGeometryMode(pkt, c, s)              
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_CLEARGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16);           
    _g->words.w1 = (~((unsigned int)(c)));       
};                                               
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_SETGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16);           
    _g->words.w1 = (unsigned int)(word);       
};

#define    gsSPGeometryMode(c, s)              
{{                                               
    (_SHIFTL(G_CLEARGEOMETRYMODE, 24, 8) | _SHIFTL(G_MW_GEOMODE, 0, 16)), (~((unsigned int)(c)))   
}},                                               
{{                                               
    (_SHIFTL(G_SETGEOMETRYMODE, 24, 8)| _SHIFTL(G_MW_GEOMODE, 0, 16)), (unsigned int)(s)           
}}


Bonus:

Let’s also implement the macro gSPModifyVertex and thus more efficiently than F3DEX, without a single RSP instruction or a dedicated immediate command as Nintendo did.

What this macro does? It simply replace a word in a selected transformed vertex data, which is composed of 40 bytes as already explained in my previous article.

We have already the code to replace a word. We just need to get the required DMEM address where the word has to be stored. This can be easily compute in gbi.h, as below:

# define gSPModifyVertex(pkt, vtx, where, val)   
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
    _g->words.w0 = (_SHIFTL(G_MOVEWORD,24,8)| _SHIFTL(((INPUTBUFFER) + ((vtx)*40) + (where)),0,16));   
    _g->words.w1 = (unsigned int)(val);           
}
# define gsSPModifyVertex(vtx, where, val)       
{{                                               
    _SHIFTL(G_MOVEWORD,24,8)| _SHIFTL(((INPUTBUFFER) + ((vtx)*40) + (where)),0,16),   
    (unsigned int)(val)                           
}}


And voila!

We will next time continue by optimizing further immediate commands. Stay tuned! :)

samedi 1 février 2020

Microcode Optimization: IMEM (Part1)

Before implementing new features, it is necessary to ensure that the current microcode is optimized in a way that it uses as less as possible RSP cycles. On top on accelerating the RSP processing, that would save space of a very limited size of the IMEM (only 4kb!), the cache memory where its runs.

As previously announced the original Fast3D code (the one used by Super Mario 64) is not very optimized, most likely because its development was somehow rushed to provide as soon as possible developers the necessary graphic library to build their game.

In this part, we will focus on one of the so called “immediate” RSP graphic commands, G _TRI1 (0xBF).

I will first explain the current code and its purpose and then present the way I took to improve it. Obviously it may occur that some of the readers of this blog may have even better ideas, for which I would really be happy to discover and discuss.

G_TRI1 is a command (gSP1Triangle) which simply picks up three transformed vertex into a buffer stored in DMEM (the 4kb cache memory from which the IMEM works) to turned them in a format readable by the RDP, which is the graphic rasterizer of the N64. Additionally the command has a flag which states which of those three vertexes contain the color or the normal of the triangle.
Here the original Fast3D code:

 0x20C    LBU      A1, 0xFFFC(K1)
 0x210    LBU      AT, 0xFFFD(K1)
 0x214    LBU      V0, 0xFFFE(K1)
 0x218    LBU      V1, 0xFFFF(K1)
 0x21C    SLL      A1, A1, 0x2
 0x220    SLL      AT, AT, 0x2
 0x224    SLL      V0, V0, 0x2
 0x228    SLL      V1, V1, 0x2
 0x22C    ADDI    AT, AT, 0x0420
 0x230    ADDI    V0, V0, 0x0420
 0x234    ADDI    V1, V1, 0x0420
 0x238    SW      AT, 0x0DE0(R0)
 0x23C    SW     V0, 0x0DE4(R0)
 0x240    SW     V1, 0x0DE8(R0)
 0x244    LW     A0, 0x0DE0(A1)
 0x248    J         0x998
 0x24C    LH     S8, 0x00BE(R0)

It takes 17 instructions to process a single G_TRI1 command. For such a basic function, it is relatively long.

Let’s go through the code steps by steps:

0x20C    LBU    A1, 0xFFFC(K1)
0x210    LBU    AT, 0xFFFD(K1)
0x214    LBU    V0, 0xFFFE(K1)
0x218    LBU    V1, 0xFFFF(K1)

In registers A1, AT, V0 and V1 are loaded a mere bytes backwards (due to the negative offset) from base K1. K1 is actually the place in DMEM of the next command in the display list to be executed. So actually the bytes are loaded from the current command to be executed.

Hereby an example of a G_TRI1 command:

DATA COUNTER    DATA
   
0x760    0xBF000000
0x764    0x00284632

As you certainly understood, in this case K1 would be equal to 0x768 and A1 =0x 00, AT = 0x28, V0 = 0x46, V1 = 0x32. A1 is the color/normal flag, AT is the first vertex, V0 the second one and V1 and the last one.

Now due to an “optimization” for the microcode, which will explain a little further on,  please note that  the number of the vertex to be picked up in the buffer is multiply by 10 (0x0A). The actual numbers of our three vertexes are therefore 0x28/0xA = 4, 0x46/0x0A= 7 and, 0x32/0A = 5.

The code then continues and shifts left by 2 all the values.

0x21C    SLL    A1, A1, 0x02
0x220    SLL    AT, AT, 0x02
0x224    SLL    V0, V0, 0x02
0x228    SLL    V1, V1, 0x02

A1 = 0x00
AT = 0xA0
V0 = 0x118
V1 = 0xC8

The reason of doing so is pretty simple: each vertex stored in DMEM takes a space of 40 bytes. In order to locate the actual place of a vertex in DMEM, you must calculate its address by adding from the base of the buffer 40 bytes per vertex. As the value from the command are already multiply by 10, you simply have to multiply them by 4, which is exactly what the shift left by 2 does!

0x22C    ADDI    AT, AT, 0x0420
0x230    ADDI    V0, V0, 0x0420
0x234    ADDI    V1, V1, 0x0420

The vertex values are then added to 0x420. It is very simple: 0x420 is the DMEM address of the start of the buffer.

AT = 0x4C0
V0 = 538
V1 = 0x4E8

This is the exact address in DMEM of our 3 vertex.

0x238    SW    AT, 0x0DE0(R0)
0x23C    SW    V0, 0x0DE4(R0)
0x240    SW    V1, 0x0DE8(R0)
 0x244    LW    A0, 0x0DE0(A1)

The obtained address of the 3 vertexes are then consecutively stored at DMEM address 0xDE0, 0xDE4 and 0xDE8. Such DMEM address is part of a scratch buffer. Then is loaded in register A0 the data located at DMEM 0xDE0 offset A1. It seems odd at first glance but actually the flag is multiply by 4 in previous step. If the original flag is 0, it is still 0, if the original flag is 1, it is now 4 and if the original flag is 2, then it is now 8. And what if you do load the data stored in at 0xDE0 offset A1? The address of the vertex for the color or the normal of the surface!

0x248    J    0x998
0x24C    LH    S8, 0x00BE(R0)

Those 2 less instructions will not be commented much. The code jumps to the part which transforms the 3 vertex in a triangle primitive, where S8 will be used a “return” register to execute the next command in the display list.

Here for the explanations, without too much intricate details of how G_TRI1 works.

Now can we do better than this? Of course it is possible!

First of all, it is very important to understand how the data of the immediate command are generated: it is done by the mean of the header called gbi.h when compiling a rom with the official N64 SDK. This file contains all the graphic command macros/functions useable by a user in the development of its N64 program.

I believe you do remember that the number of the vertexes is multiplied by 10. It is actually something managed through gbi.h:

#  define __gsSP1Triangle_w1f(v0, v1, v2, flag)           
     (_SHIFTL((flag), 24,8)|_SHIFTL((v0)*10,16,8)|       
      _SHIFTL((v1)*10, 8,8)|_SHIFTL((v2)*10, 0,8))

Being able to modify what the user keyed as arguments before being included in the display list to be executed by the RSP is a very useful matter, which will be use as much as possible to avoid having the RSP playing unnecessarily with data.

You may also have noticed that the first line of the command (0xBF000000) is complete empty. Why not using it?

After quite some reflections I came to the following solution (inspired from Factor5 microcode): storing directly the DMEM address of the vertex in the immediate command by calculating through gbi.h (meaning the CPU at the end, much more powerful than the RSP for this type of activities).
The command could actually look like this:

0xBFAABBBB
0xCCCCDDDD

0xBF: COMMAND HEADER     AA: FLAG    BBBB: DMEM ADDR OF 1ST VERTEX
CCCC: DMEM ADDR OF 2nd VERTEX         DDDD: DMEM ADDR OF 3rd  VERTEX

Doing this would mean to change few changes in gbi.h, meaning doing the following change:

Let’s first create a new constant, which will hold the DMEM address of transformed vertex buffer.

#define INPUTBUFFER         0x420

Then the triangle macro can be changed as follow:

#define gSP1Triangle(pkt, v0, v1, v2, flag)               
{                                                        \
    Gfx *_g = (Gfx *)(pkt);   
                                                        \
    _g->words.w0 = _SHIFTL(G_TRI1, 24, 8) | _SHIFTL(flag, 16, 8) | _SHIFTL((((v0)*40) + INPUTBUFFER), 0, 16);
                                                        \
    _g->words.w1 = _SHIFTL((((v1)*40) + INPUTBUFFER), 16, 16)| _SHIFTL((((v2)*40) + INPUTBUFFER), 0, 16);    
}

#define gsSP1Triangle(v0, v1, v2, flag)                   
{{                                                        \
    (_SHIFTL(G_TRI1, 24, 8) | _SHIFTL(flag, 16, 8) | _SHIFTL((((v0)*40) + INPUTBUFFER), 0, 16)),(_SHIFTL((((v1)*40) + INPUTBUFFER), 16, 16)| _SHIFTL((((v2)*40) + INPUTBUFFER), 0, 16))    
}}

Finally the G_TRI1 code can be reduced to the following:

0x208    LB         A1, -0x007(K1)
0x20C    LH        AT, -0x006(K1)
0x210    LH        V0, -0x004(K1)
0x214    LH        V1, -0x002(K1)
0x218    SLL      A1, A1, 0x1
0x21C    ADD    A1, A1, K1
0x220    LH       A0, -0x006(A1)
0x224    J          0x968
0x228    LH       S8, +0x0BE(R0)

And voilà!

The DMEM address is immediately loaded in registers AT, V0, V1 from the command. The flag is now used to compute where within the command itself the DMEM address for the color/normal surface is located, taking in account the each DMEM address is a half word (2 bytes)!

We started with 17 instructions and for the same exact result we reduce the code to 9 instructions!!!

Now remain the main question: does it indeed work? Of course, as you can see in this compiled sample from the SDK with such an implementation.



Next time I will continue on focusing on other immediate command(s)! :)

dimanche 26 janvier 2020

Microcode Customization: Planning



As finally it is now possible to create or modify a microcode fully compatible with the Nintendo SDK, I started considering what would be the best approach to tame further the N64 RSP.

For the time being it is quite obvious that starting from scratch an entire new graphic microcode is still beyond my skills so I decided that optimizing and enhancing the original Fast3D microcode would be a good exercise.

So for the last two months, I changed a bit of the Fast3D source code here and there and learnt various things about the organization of code and the way to program the RSP. 

It quickly appeared that the microcode was written with a very theoretically approach, meaning without having in mind to optimize the limited resources of the RSP. 

Few ideas came also to me about what could be implemented differently and from there I set up finally a high level plan.

The philosophy behind it would be as follow: 

1. Save a maximum space in IMEM/DMEM with little impact on the performances.

2. Implement unavailable features to match them with some slightly more "modern" versions of OpenGL from which Fast3D seems somehow to be inspired from.

After some investigations, I came up with the following:

1. Texture Rectangle RDP command being composed of 4 words, it would be normal that such command is included in the display list without being splitted into 3 commands as in Fast3D.

2. In order to save DMEM space, either get rid of some constants (i.e opengl offset, Newton's iteration constants, dram address mask, "reserved" DMEM space, include DMEM address directly into GBI commands rather than loading them from a DMEM address etc.) or reduce their size (i.e segments, light data structure, etc).

3. Implement an optional double DMA buffer for some immediate commands. Data would be retrieved from RDRAM where RSP would deal with another DMEM buffer.

4. Implement a circular buffer to store transformed vertex and generate strip triangle, with a primitive restart function. It would be possible to also use triangle list, triangle fans or where possible quads.As the vertex buffer would be reduced dramatically in size, the number of vertices contained in the buffer should be normally high. It would still be good where possible to keep indexed triangle implementation where possible.

5. Save IMEM used as some commands could be implemented differently (set/cleargeometry mode, moveword, movemem, etc.)

For a first customization, it seems ambitious enough but having done various tests, I clearly hope that it can be achieved successfully.

Next step will be much more concrete, directly into the intricate details of the microcode.

Finally feel free to share other ideas you may have as comments, yet please understand that no extreme severe modifications are to be done (i.e. Z sorting, involvement of CPU in the tasks, etc.). Thanks!


The masterpiece graphic microcode behind the Nintendo 64 version of Indiana Jones and the Infernal Machine and Star Wars Episode I: Battle for Naboo

 

Introduction 

 

Factor 5 used to be one of the best game development studio at the very end of the 90’s/early 2000’s. Its programmers, coming from the German hacking and demo scene, were very talented and, thanks to a collaboration with both Nintendo and LucasArts, were able to deliver stunning graphic achievements on the N64 and GameCube. (https://en.wikipedia.org/wiki/Factor_5)

After the success of the Star Wars: Rogue Squadron in 1998, Factor 5 started to work two new games, Indiana Jones and the Infernal Machine and Star Wars Episode I: Battle for Naboo, with the intention to squeeze the Nintendo 64 to its best. In order to do so, Factor 5 decided to develop a “new” graphic microcode (and optimize its audio microcode called Musyx). (https://www.ign.com/articles/2000/11/10/bringing-indy-to-n64) (https://www.ign.com/articles/2000/11/11/interview-battling-the-n64)

At the very end of the commercial life of the N64, both games were released, too late to attract the favor of the critics and a public already focused on the next generation of consoles, meaning the technical achievements injected of those games went unfortunately unnoticed.

GlideN64, as its predecessor Glide64, has mainly been developed as a High Level Emulation (HLE) plugin. A microcode is a library of high level macro commands (high level in compare with processor op-codes). LLE way is to run these commands as actual hardware would do, instruction by instruction. HLE implements what commands in that library do as fast as possible without running actual command’s code.

As explained by Sergey in his blog few years ago (http://gliden64.blogspot.com/2014/11/a-word-for-hle.html), few games could not be emulated graphically in HLE as the documentation necessary to do so was unavailable. Yet few years ago Sergey and I started on reverse engineering and implementing customs graphic microcodes.

When we started our journey to decipher the one used by Indiana Jones and the Infernal Machine and Star Wars Episode I: Battle for Naboo, we could only be impressed on how well written and optimized it was and though we are unable to understand its intricacy in details, we do believe that its prowess deserves to be documented for the posterity.

Please note that in order to understand the below documentation, you must be familiar with graphic programming (OpenGL), N64 hardware and the Fast3D microcode. (https://en.wikipedia.org/wiki/Nintendo_64_technical_specifications) (https://en.wikipedia.org/wiki/Reality_Coprocessor)

On the contrary of what could be suggested by Factor5, the graphic microcode of both Indiana Jones and Battle of Naboo was NOT developed from scratch. It was obviously developed with the source code of the F3DEX microcode supplied by Nintendo in its SDK, which is just an optimized version of the Fast3D microcode used by Super Mario 64. Of course most of the graphic commands were rewritten along with many major additions (the size of the microcode is about twice as large as the other ones) but its core is quite similar with the very first game of the console.

What remains mainly is the way to transform input vertices into a specific output data structure stored into a buffer within Data Memory (DMEM) of the RSP (Reality Signal Processor). Those structures may be then selected by a triangle command, formatted into a low level triangle command and then used by the Reality Display Processor (RDP). The code used in this respect is comparable to the code used in the F3DEX microcode where there is no correspondence with the code of other types of microcode (Turbo3D, ZSort) to do such an operation.

Another evidence in this respect is that the header of the command (i.e. 0xBC for the MoveWord command, 0xBF for the TRI1 triangle command, etc.) are the same than the F3DEX microcode.

As an interesting consequence, it means that actually none of the N64 microcodes were ever written from scratch by 3rd party developers but only by SGI or by Nintendo. However it is true that only around 20% of the code is somehow related to F3DEX, meaning that this latter was used as a workable environment to develop the new commands filled with plenty of unique features.

I/ Few outstanding features compared to F3DEX microcode

A. DMEM address is directly integrated into the graphic command

 

DMEM is a small 4kb memory which the RSP microcode uses to store the data retrieved from RDRAM. The data is used by the RSP to do the computations according to the specification of a command.

In the F3DEX microcode, the DMEM address is not part of the command itself but it is rather an index. The actual DMEM address used by this index is stored in DMEM itself at the boot of the microcode, hidden to end users. In this so called Indy/Naboo microcode, the DMEM address is set directly in the command. This unique feature which helps to save some space in DMEM for other purpose.

Let’s take a simple example:
0xBC command is a MoveWord command, which simply store a 32 bits words in DMEM. As you may be aware of, moved words will be used later by other commands as parameters.

0xBC00014C
0x00000715

0xBC is the header of the command, 0x14C is the DMEM address and 0x00000715 is the word stored at this address. For comparison, in F3DEX:

0xBC000406
0x002D4CD0

0x06 is a mere flag which is used by the microcode to locate in DMEM a base DMEM address. Such a flag can vary depending on the type of word to be stored (i.e. a segment RDRAM address). 0x0004 is added to this base DMEM address. In our example base DMEM address is 0x160 + 0x004 = 0x164. So the word 0x002D4CD0 will be stored at DMEM address 0x164.

B. Geometry mode is a mere RSP register

 

In the F3DEX microcode, the Geometry mode is stored in DMEM and each time it has to be checked out or changed, it has to be loaded in a RSP register, changed and then stored back. In the Indy/Naboo microcode, there is simply an entire RSP register dedicated to the geometry mode. It does mean that you have one register less but an easy way to manage the geometry mode and as well saving a bit of space in DMEM.

C. Playing with display lists

 

In Indy/Naboo microcode, the way the display lists are managed are relatively different than in F3DEX.
  1. Execution of multiple display lists at the same hierarchical level
In the original F3DEX display lists are relatively straight forward, in a way that they are, as in OpenGL, managed hierarchically. You first call a new display list, then a nested display lists, which can as well call a nested display lists.
As for Star Wars: Rogue Squadron, a clever mechanism was developed to “jump” from a display list to another display list. At the beginning of the each display list, instead of having the first immediate command to be executed, you have simply a RDRAM address which may be called at the end of the display list by the immediate command 0xB5. In such a case, a display list will be retrieved from specified RDRAM address. This loaded display list also contains a RDRAM address at its start. So instead of nesting the display lists, you move from one display list to another display list at the same level of hierarchy.
  1. Execution of a display list under condition
This mechanism is incredible. MoveWord command (0xBC00058C) may provide a RDRAM address. When running some immediate commands which may lead to draw some graphics (textured rectangles, triangles), BEFORE being actually drawn, a nested display list is retrieved and executed from such a RDRAM address. It is the case for the immediate RDP command 0xE4/0xE5, for non-rejected triangles, for particles. Such a mechanism links the actual drawing a RDP primitive to a display lists which set the parameters of such drawing (i.e. Combine Mode, Other Modes, Texture Image, Tile, etc.). And such a mechanism occurs ONLY when the primitive is to be indeed drawn. So for instance If a triangle is out of viewport and thus rejected, this display list for pixel pipeline setup will not be executed. In this way the N64 RDP is only used where necessary!

D. Clever memory segmentation

 

In F3DEX, the code manages the segmentation of the memory through the usage of the MoveWord command. With this method, the number of segments is limited to 16 and requires to store the words in DMEM. In the Indy/Naboo microcode, the segmentation of the memory is managed differently and somehow as the “jump” mechanism, already explained for the display list. At first immediate command 0x02 provides a RDRAM address. This is the RDRAM address of the first segment. The very first word at this RDRAM address is the RDRAM address of the following segment. The size of each segment is limited to 0x100 bytes and when an immediate command requests data beyond the segment, the remaining data is retrieved from the following segment where again the first word provides the RDRAM address of the following segment.

E. Intricate command structure

 

In F3DEX the size of the command is fixed to two mere 32 bits words with the same exact purpose. In Indy/Naboo, the size of a command can be much larger. For instance the biggest ever immediate command of the microcode, which is used to generate the terrain polygons from a height map, is composed of 16 32 bits words!!!!

0x05000000
0x217A800F
0x045ED4E3
0x00000000
0x000001E4
0xD642FE9B
0x00000000
0x00000000
0x00000000
0x00000000
0xFF000000
0xFF000000
0x00000000
0x00000000
0x00000000
0xEF5B0017

The very same immediate command may have its size varying according to a flag within such a command. For instance the TRI command 0xB4 for textured polygons is larger than the one for shaded polygons
.
TEXTURED TRIANGLES

0xB4000600
0x06000628
0x0C000408
0x06500678
0x07DD062C
0x07DD062C
0x0787062C
0x07DD062C

SHADED TRIANGLES

0xB4000400
0x06000628
0x0C000408
0x06500678

Command’s flag also may change its behavior. For example, TRI command 0xB4 with flag 0x06 is used for textured triangles with regular textures, but flag 0x0E turns on texture coordinates generation for reflective textures.

0xB4000E00
0x099809C0
0xACA0A4A8
0x09700948
0x7F0000B8
0x7F0000C0
0x7F0000B0
0x7F0000A8

Sometimes the same command may have completely different purpose. For instance command 0x05 can be used to generate texture rectangles, generate particles, generate terrain from a height map, generate specific vertex. Except for generating graphics, there is nothing in common between those immediate commands actually.

II/ Listing of the commands with high level explanation

 

Even if we were able to decipher the microcode, it does not mean that all parameters of those commands were fully apprehended. Some, of course, are quite obvious but some are used in very large and complex commands and therefore abstruse.

Command 0x01

 

The main purpose of this immediate command is to retrieve data from RDRAM and potentially use such data to compute new data.
The structure of the command is the following:

0x01ODDDLL
0xBBAAAAAA

0x01 Header of the command
O Option of the command: for the same DDD, the option can lead to other part of code
DDD DMEM address where the data will be stored. ALSO the code will check it and depending on it, will route the code to a specific portion of code, which will then route again by O.
LL number of bytes to be retrieve from memory
BB it is a mere byte which can be used according to the route the command will take after having retrieving the data (i.e. For the number of lights)
AAAAAA When is not zero, data is retrieved from this RDRAM memory, when there is only 0x000000, data is retrieved from a segment.

Therefore the very same command 0x01 can be used for numerous scenarios, such as:

When O is 0, the command is as the F3DEX command MoveMem, meaning that it simple retrieve data from RDRAM and store them in DMEM.

When O is 1, the command is like the F3DEX VTX command, meaning that vertices are retrieved from RDRAM to DMEM, transformed and then stored into a buffer.

When O is 2, lighting calculations performed. The command retrieves data from RDRAM and computes colors for vertices. The colors are stored into a buffer from where the triangle commands retrieve them later. The lighting system is very complex, with many options.

When O is 3, the command sets the number of light and potentially retrieves the light structure.

When O is 5, the command retrieve vertices from RDRAM in a specific way to DMEM, transformed them and then stored them into a buffer. Such an option concerns 2D graphic where triangles are used.

Command 0x02

 

It set the RDRAM address of the 1st segment usable by command 0x01. As already explained the RDRAM address of the next segment is the 1st word of the RDRAM address of the previous segment.

Command 0x05

 

This command generates primitives in various way (from a mere texture rectangle to particles to triangles used for field, etc.). The last byte of the second word determines command’s mode.

0x18 (2 words)

0x05XXXXXX
0xXXXXXX18

This sub-command transforms selected vertices by Modelview matrix (0x010E403F) and store them into a vertex buffer.

0x27 (6 words)

0x05XXXXXX
0xXXXXXX27

The sub-command generates vertices and some flags used by another 0x05 sub-command.

0x24 (10 words)

0x05XXXXXX
0xXXXXXX24

The sub-command generates particles (actually small texture rectangles) from the vertices/flags obtained by previous 0x05 sub-command.

0x15 (8 words)

0x05XXXXXX
0xXXXXXX15

The sub-command generates a mere texture rectangle using a vertex as center of such a rectangle. It is mainly used for explosions.

0x4F (2 words)

0x05XXXXXX
0xXXXXXX4F
Such a sub-command is a mere flag used by sub-command 0x0F to switch it between its short (4 words and long version (16 words)

0x0F (4 or 16 words)

0x05XXXXXX
0xXXXXXX0F

Such a sub-command is used to set parameters for sub-command 0x09 and 0x0C. There is a short and long version, activated by the above sub-command.
0x09 and 0x0C (6 words)

0x05XXXXXX
0xXXXXXX0C

0x05XXXXXX
0xXXXXXX09

Both sub-commands generate the triangles for the ground in Star Wars Episode I: Battle for Naboo (up to 32 per sub-commands). It seems to be generated from a colored height map.
As you understand, command 0x05 is a set of 8 sub-commands!

Command 0x06

 

This command is the same than gSPDisplayList command in F3DEX.

Command 0x07

 

This command is the same than gSPBranchList command in F3DEX.

Command 0xB4 (4 or 8 words)

 

It is similar to the TRI2 command in F3DEX, except that texture coordinates and indices in the colors buffer provided as command’s parameters.

Command 0xB5

 

This command triggers a “jump” to another display list previously set as the first word of the current display list.

Command 0xB6

 

This command is the same than gSPClearCeometryMode command in F3DEX.

Command 0xB7

 

This command is the same than gsSPSetGeometryMode command in F3DEX.

Command 0xB8

 

This command ends a display list.

Command 0xB9

 

This command is similar to gSPSetOtherMode command in F3DEX (lower half)

Command 0xBA

 

This command is similar to gSPSetOtherMode command in F3DEX (higher half)

Command 0xBB

 

This command is similar to gSPTexture command in F3DEX.

Command 0xBC

 

This command is similar to the Moveword command in F3DEX.

Command 0xBD

 

Only used in Battle of Naboo. It sets the OtherModes for the triangles used by the commands generating the ground.

Command 0xBE

 

Only used in Battle of Naboo. It sets the OtherModes (along with immediate command 0xBD) and texture coordinates for each triangle generating the ground. In conjunction with parameters set by sub-commands 0x05 -0x09 and 0x0C, it can also generate such triangles (up to 32 of them).

Command 0xBF (4 or 8 words)

 

It is similar to the TRI1 command in F3DEX, except that texture coordinates and indices in the colors buffer provided as command’s parameters.

Conclusion:

With such an advanced microcode it is clear that not a lot of N64 games can compete graphically with Indiana Jones and Star Wars Episode I: Battle for Naboo.
As pictures speak louder than words, here some stunning examples of the outstanding graphic exploit.

The lighting is absolutely splendid in Indiana Jones and the Infernal Machine.
 For instance at the start of level named Volcano, 12 lights are used at the same time!!



In another level called Palawan Temple, splendid point lights are displayed.



Particles are used in many places without any slowdown in both Indiana Jones and the Infernal Machine and Star Wars Episode I: Battle for Naboo. One example, between many, would be the snow.




The terrain in Star Wars Episode I: Battle for Naboo is huge and without any fog.



Some great explosions effects are often shown in Star Wars Episode I: Battle for Naboo.



Splendid reflection mapping effects are sometimes used.



As you may see, both games are simply amazing for a Nintendo 64. Having in mind that the games uses as well the Musyx audio microcode, the console has most likely shown with them the best of what it could offer. As well it proves that skilled programmers can overcome limitation of a machine far beyond expectations!!!