samedi 3 avril 2021

Microcode Optimization: IMEM (Part8)

Today I am very happy to give you finally news on the recent developments on the microcode. In the last months, as previously underlined, I tackled lighting and reflection mapping. I am not yet totally done with it but with all the changes already carried out, it is worthwhile to share the current status.

 I)             Change the way to load in RSP the inverse of transpose of the 3x3 part of the model matrix

In order to compute lighting, you have to use the inverse of transpose of the 3x3 part of the model matrix (which I will call 3x3 matrix as from now)  to get the light direction in model coordinates.

a)            In Fast3D, the model matrix is first loaded and then data are changed by using some special RSP (LTV, STV) instructions which should help to do so. It requires some scratch DMEM space to do so and about 16 instructions to have in the RSP one 3x3 matrix.

           b)           In F3DEX2, the 3x3 matrix is loaded directly from DMEM where the model matrix is stored. There is no need to load the model matrix and then transpose it and no scratch DMEM space is necessary. It provides again one 3x3 matrix.

My implementation is different as my goal is also to implement point lighting which is totally missing in the original F3D. In order to do point lighting, it is required to have the model matrix and the 3x3 matrix and thus for each vertex to be processed.

I do underline “for each vertex” as with directional lighting, till you got a new matrix or new lights, you may use the same computed light directions in model coordinates for each vertex to be processed, meaning that the 3x3 matrix would have to be used only once for doing such computations.

So point lighting requires to have the model matrix and the 3x3 matrix at the same time. On top of it, the RSP vector instructions (VU) can hold 8 16 bits lanes, which is used to processed two vertex at once. If for F3D, one 3x3 matrix was sufficient to compute a limited number of light directions in model coordinates, it cannot be the case when processing point lighting per vertex. So it does mean that the VU must hold two model matrix and 3x3 matrix, duplicated on the same vectors.

It took me a significant time to find a good solution for those requirements. After loading the model matrix twice (as for Fast3D), I take me only 22 instructions to get the two 3x3 matrix as desired. In this respect I used a RSP instruction in a different way than usually intended, VMRG and register VCC.

Additionally I have replicated the way the normalization of the light direction in model coordinates as in F3DEX2, more efficient than Fast3D.

II)            Separate lighting computations from vertex processing

As explained, lighting/reflection mapping computations is done per vertex. If it may be fine with directional light, with point lighting it would mean reloading over and over, for each vertex, the model and 3x3 matrix as the RSP is unable to hold all those data and performing the rest of vertex processing tasks (i.e. multiply vertices with ModelViewProjection (MVP) matrix, clipping, fog, etc.). In order to do so, lighting computations has to be done separately. It does mean to break the Vtx structure as per gbi.h where vertex coordinates, colors/normals and textures coordinates were tied together.

There is many advantages to do so: 

          You may load with flexibility vertices, colors/normals and texture coordinates, in separated buffers. 

         You may avoid duplications of data (same color, same normal, same texture coordinates)

You can do computations more efficiently for/on those buffers.

There is of course some inconveniences:

You need to have new structures for colors/normals and texture coordinates. As the vectors in RSP are 8 lanes of 16 bits, structures will have to hold 2 colors/normals or textures coordinates. It is also required to have those structure 64 bits aligned due to the RSP DMA engine.

      GBI compatibility is broken. N64 programmers have to rewrite a portion of their code.

Flexibility comes with more complexity for the programmers (multiplication of the GBI macros)

Many customized microcodes has done, at least partially, such a change (i.e. Perfect Dark or Indiana Jones)

So I got to create a new command to compute lighting and texture coordinates, along with multiple GBI macros.

I took advantages of having two 3x3 matrix (instead of 1) to compute lighting directions in model coordinates nearly 2 times faster. I separated directional lighting computation from texture coordinates computation entirely in order to avoid many unnecessary computations done by F3D. If the computation speed on lighting should remain more or less the same, the one on S&T for reflection mapping has been improved.

Of course I have considered as well to optimize the DMEM space used for those computations.

In the original Fast3D, each light structure used 32 bits. In F3DX2, it uses 24 bits. In my implementation, it uses only 16 bits. In this respect I got to change the way some libultra functions were returning data (guLookAtHilite, guLookAtReflect,  guPosLight, guPosLightHilite). I could notice something which could be optimized in those functions (and some others as well) and which I have implemented. According to the MIPS 4200 documentation, SQRT and DIV CPU instructions are slow so where possible it is better to use an inverse fast square root instead. (Thinking about it, it is noticeable that reflection mapping was not used in a lot of games, likely because reflection mapping was actually too demanding).

Now obviously you have to link vertex, output colors and output texture coordinates. I could have decided to use the 2 remaining byte of the vertex structure, currently padding, to do so. However I took the approach to do so at triangle level as it is at this level that the control should be given to the graphic designer. It also helps to avoid unnecessary duplications of data in buffers. However a careful approach have to be taken when some advanced lighting features will be used, as reflection mapping or point lighting, where all is interdependent at vertex level and not triangle level.

It means that I got to rewrite entirely the G_TRI command. Additionally G_VTX commands got to be adapted as lighting and texture coordinates computations are not done anymore with this command.

And voila!

Now I will focus on point lighting and what I wanted to create from the very beginning of this project: implement a circular buffer to store transformed vertex and generate strip triangles.

Side note:  I will update soon my previous article as I continued to do some interesting changes for G_BRANCH_Z and G_CULLDL.

HELP NEEDED: After implementation of point lighting, triangle strips and optimizing DMEM, it will be time to test the microcode. In this respect I am calling for people (with sufficient programming skills of course) to help out in this respect. It can be done in different ways: adapt SDK N64 demos, adapt already written homebrew games, write new test demos using the new features of the microcode, etc.  Contact me on N64brew discord channel in this respect. Thanks!

mercredi 30 décembre 2020

Microcode Optimization: IMEM (Part7) - Updated

It has been quite long that I did not share any update on the project. I must admit that for the last six months, I could not find enough time and motivation to focus on it. I do not impose on myself any pressure or deadline when it comes to a hobby. Yet I am quite perseverant so be reinsured that I will finish what I have started 😀

 Let’s try to summarize the achievements of the recent weeks:

G_GL  & G_ENDDL

I have significantly changed the code related to the way the display lists are managed. Even though command G_GL in the original Fast3D microcode is quite efficient in this respect, there were few points which, at least from my point of view, could be improved.

First of all, 3 general registers of the RSP were exclusively dedicated to the display lists in original Fast3D microcode:

K0 ($26) for the place in RDRAM of the next command to be executed in the current running display list

K1 ($27) for the place in DMEM of the next command to be executed in the current running display list

GP ($28) used a counter to ensure that the space dedicated in DMEM for running display list was not exceeded.

I came to the conclusion that K0 and GP were not really necessary. With K1 we can determine whether the limit of the place allocated in DMEM for the display list. As well with K1, it is possible to compute at any time the RDRAM address of the next command in the current running display list by simply using the base address of the segment used by such a display list.

Though it took me quite a while to find the right way to do it, my new implementation does not require at all the usage of K0 and GP. However as a side effect, the command ending a display list (G_ENDDL) has been merged with G_GL.

G_SETGEOMETRYMODE, G_CLEARGEOMETRYMODE

Having freed 2 registers, I decided, as it is done for the microcode of Factor 5 used by Indiana Jones and the Infernal Machine, to use one of them to hold the current geometry mode. It does mean that there is no necessity to load or store such a geometry mode from/to DMEM. Doing so saves 3 IMEM instructions, one word in DMEM but more importantly allows various parts of the microcode to access immediately the current geometry mode.

Commands of 4 words

In Fast3D, every command is composed of 2 words. I do understand the underlying reason of SGI/Nintendo in this respect: RDP commands are usually 2 words and the DMA engine of the N64 is 64 bits. With a fixed size, managing memory is much easier than with a size that may change for each command. As some commands may be composed of 4 words, I circumvented this this limitation by simply adding at the end of the displaylist a scratch space for the potential two additional words of the commands. I use this feature for textured rectangles for the time being.

Meanwhile I got rid of G_RDPHALF_1, G_RDPHALF_2 and G_RDPHALF_CONT as they became completely useless.

"New" commands

 
G_BRANCH_Z has been implemented by in a completed different way than F3DEX2. Actually I renamed the command to G_COMPARE as it is now not only Z than you may compare by any information stored in DMEM with the data provided by the programmers. Such comparison can be done for a byte, a half word or a word.

Additionally on the contrary of G_BRANCH_Z which is limited to branch to another displaylist, the programmer can decide what he want to set as result of the command. It is simply done by the way of skipping or not the following commands in the displaylist, depending on the results of the G_COMPAREcommand.

For instance you may deactivate point lighting when the vertex dealt with are too far away from the camera.

I also created a new command which can be very useful with this  G_COMPARE, G_SKIP.

G_SKIP is very simple, it skips a number of commands in the displaylist. For instance you want not only to deactivate point lighing but actually you want to skip the activation of the lighting, the action of texturing, the RDP commands loading textures in TMEM, etc.

I cannot imagine all the possibilities with those two commands but I feel that you may play a lot with those :)

G_CULLDL, still inspired from F3DEX2, have exactly the same feature than G_COMPARE. You don't automatically close the displaylist. it will skip or not the following command. It can be indeed closing the displaylist but it can branching to another one, etc.

All the above changes took a very limited number instructions compared to my previous update. At current stage my customized Fast3D microcode has now more features than F3DEX microcode and I have still numerous ideas which I would like to implement.

I hope next time to be able to update the lighting part of the microcode, even if it is quite a challenge.

Finally I would like to wish you a happy new year 2021!!! 😋

jeudi 30 avril 2020

Microcode Optimization: IMEM (Part6)

As from now on I will not explained  in details the code. It is extremely cumbersome, both to write and to read. I will take a more high level approach to describe the current Fast3D implementation and the improvements which I have implemented.

G_MTX


This command is used in the original code to:

1)    Potentially push a matrix
2)    Potentially load a matrix
3)    Potentially multiply a matrix

The command always ends up by multiplying the ModelView matrix with the Projection matrix, resulting into a ModelViewProjection matrix.

In my opinion, the code has many flaws to perform those tasks.

As explained in my previous article, data are retrieved from RDRAM to scratch area which has to be moved to right place in DMEM. A simple loading of a matrix requires many unnecessary instructions to do so.

Also multiplying a matrix requires using scratch buffers to store results which are then moved to the right place in DMEM. Fact is that the code was written very effectively, using the so accumulator of the Vector Unit of the RSP to perform addition at the same time than the multiplication BUT the source data of the original matrix part of the multiplication was overwritten by the partial results along the execution of the code, leading to the need to use scratch buffers.

Overhaul the G_MTX code in FAST3D takes 67 IMEM instructions.

My implementation is dramatically smaller. In order to do so, the push matrix, load and multiply are separated functions, both in microcode and in gbi.h. In order to ensure compatibility with Fast3D, emulation macros in gbi.h has been implemented.

We already discussed in my previous article of the new push matrix code.

When it comes to load a matrix, the code simply uses the G_MOVEMEM command, directing the matrix directly to the right place in DMEM.

Finally for the matrix multiplication, I reused what has been developed for F3DEX2. This code is slightly less efficient than the one of Fast3D but it has an enormous advantage: the source of the matrix data is not overwritten by results before the end of the multiplication, avoiding to move around data in DMEM.

All in one, G_MTX as such is now only about 30 instructions!

G_VTX


This is the core of the Fast3D microcode. This function performs the following:

1)    Multiply vertices with ModelViewProjection matrix
2)    Perform lightings and texture coordinates transformation tasks.
3)    Determine the outcodes of the vertex for clipping (https://en.wikipedia.org/wiki/Cohen-Sutherland_algorithm)
4)    Normalized device coordinates (divide everything by W)
5)    Transform clip coordinates to screen coordinates, including perspective correction (viewport transformation)
6)    Calculate fog where necessary
7)    Store results in the DMEM vertex buffer

The codes does all of this in quite efficient way, yet few things can be either optimized or improved.

I improved the code as follow:

1)    Save DMEM space used by the Newton division algorithm

The division by W to normalize to device coordinates is done by the support of a Newton division algorithm. (https://en.wikipedia.org/wiki/Division_algorithm#Newton-Raphson_division), the RSP division instruction being not accurate enough.

Weirdly enough the code uses 8 half words of the very same constant (0x0002) in DMEM and loaded in a vector of the RSP.

With my implementation the code simply adds such this constant to a whole nullified vector.

2)    Change slightly the viewport structure to save DMEM space and IMEM instructions

As per gbi.h, the viewport structure is as follow:
typedef struct {
    short    vscale[4];  /* scale, 2 bits fraction */
    short    vtrans[4];  /* translate, 2 bits fraction */
    /* both the above arrays are padded to 64-bit boundary */
} Vp_t;

 vscale: (SCREEN_WD/2)*4, (SCREEN_HT/2)*4, G_MAXZ, 0,
 vtrans: (SCREEN_WD/2)*4, (SCREEN_HT/2)*4, 0, 0,

When the viewport structure is loaded, the code actually multiplies by -1 (SCREEN_HT/2)*4. To do so it uses 4 words of constants in DMEM which have to be loaded and then multiply against the all elements of viewport structure!!!!

As you can imagine, it is absurd to do this instead of changing the structure code as follow:

vscale: (SCREEN_WD/2)*4, -(SCREEN_HT/2)*4, G_MAXZ, 0,
vtrans: (SCREEN_WD/2)*4, -(SCREEN_HT/2)*4, 0, 0,

This change is very straight forward and it was used by Seta (i.e. Eikou No St Andrews) or Factor 5 (Star Wars Rogue Squadron).

3)    Using freed parameters of the G_VTX command.

As the loading of the vertices is managed by the G_MOVEMEM command, G_VTX command can now hold other parameters that does not have to be computed by the code, as for instance the place in the scratch buffer where the new vertex are to be stored. Of course gSPVertex has to be emulated to keep compatibility with Fast3D.

4)    Loading various parameters into a single RSP vector

Many parameters related to the G_VTX commands are to be loaded in various RSP vectors where a mere change in DMEM data structure can allow getting them loaded into a single one, which of course requires only one IMEM instruction instead of several.

5)    Optional Near clipping on and off

In the original Fast3D, near clipping is off (.NON) with the usage of a slightly different microcode. I decided that it should be an option. A mere gbi.h macro command can activate or deactivate the near clipping now. Now of course it must be understood that vertexes processed with one near clipping mode should generate triangles in the same mode (programmers should not switch mode between G_VTX and related TRI commands).

6)    Precise Clip Ratio

The Clip Ratio is an interesting feature of the original Fast3D microcode where triangles are not clipped till they are not beyond a clipping area which is determined as a multiple of the viewport area. Such a feature has been implemented due to the fact that clipping triangles takes a significant time for the RSP to perform and that rasterizing 1 big triangle instead of 2 small triangles can be actually faster.

However the Fast3D implementation only considers the clipping area between X1 and X6. I have decided to implement a more precise clip ratio, in S15.16 format, allowing a multiplication for instance like 1,4 or 2,6.

I also noticed something which I cannot really grasp: when clipping is performed, it is done against the clipping area instead of the viewport area. Why doing so is a mystery to me. If a triangle have to  be clipped, why not clipping it against the right minimum, meaning what can be seen on the screen? I changed this fact and clipping will be now performed against the viewport area.

And voila! Next time I will focus on improving lighting and fog. Keep tuned!

lundi 6 avril 2020

Microcode Optimization: IMEM (Part5)

G_MOVEMEM

This immediate command is used to retrieve data from RDRAM to DMEM, which can then be further used by other immediate commands. It must be noticed that other immediate commands retrieve data from RDRAM to DMEM, G_VTX and G_MTX.

The way that Fast3D microcode manages the process to move data from RDRAM to DMEM is, at least from my point of view, messy and inefficient. In order to amend the situation, we will have to carry out some serious changes.

Let’s go through G_MOVEMEM code and thus as from the beginning of the execution of the command.

0x03800010 (register T9)
0x00220D40 (register T8)

First of all any immediate command goes through a code which dispatches the command to another place in IMEM from where it is actually executed. Where some data must be retrieved from RDRAM, such an operation is carried out before such a dispatch occurs.

Let’s analyze shortly this dispatch code therefore:

0x060    LW         T9, +0x0000(K1)
0x064    LW         T8, +0x0004(K1)
0x068    SRL        AT, T9, 0x1D
0x06C    ANDI    AT, AT, 0x0006
0x070    ADDI     K0, K0, 0x0008
0x074    ADDI     K1, K1, 0x0008
0x078    ADDI     GP, GP, 0xFFF8
0x07C    BGTZ    AT, 0x09C
0x080    ANDI     S2, T9, 0x01FF
0x084    ADDI     S6, R0, 0x7E0
0x088    JAL       0x11C
0x08C    ADD     S3, T8, R0
0x090    ADD     S4, R0, S6
0x094    JAL       0x13C
0x098    ADDI    S1, R0, 0x0000
0x09C    LH       V0, +0x00BC(AT)
0x0A0    JR        V0
0x0A4    SRL     V0, T9, 0x17

0x060    LW    T9, +0x0000(K1)
0x064    LW    T8, +0x0004(K1)

We load in T9 and T8 the two words composing the command. K1 is the pointer where such a command is in the displaylist which has been previously stored in DMEM.

0x068    SRL      AT, T9, 0x1D
0x06C   ANDI    AT, AT, 0x0006
0x070    ADDI    K0, K0, 0x0008
0x074    ADDI    K1, K1, 0x0008
0x078    ADDI    GP, GP, 0xFFF8
0x07C   BGTZ    AT, 0x09C

By doing a shift right by 0x1D of T9, it is possible to assess whether the header (the fist byte) of the command is below or above 0x20. In case it is above 0x20, the code jumps to 0x09C. Indeed in gbi.h you may see that DMA commands (commands retrieving data from RDRAM to DMEM) are as follow:

* The command format is
*
*    |00xxxxxx| = DMA        0,..,127

So if it is above 0x20 we are in presence of a command which does need to get data from RDRAM.

The rests of the instructions are just to move some registers containing counters/pointers, as for instance the one related to the displaylist, K1.

0x080    ANDI    S2, T9, 0x01FF
0x084    ADDI    S6, R0, 0x7E0
0x088    JAL      0x11C
0x08C   ADD     S3, T8, R0
0x090    ADD    S4, R0, S6
0x094    JAL      0x13C
0x098    ADDI   S1, R0, 0x0000

S2 is the number of bytes to be retrieved from RDRAM.
S3 is the RDRAM address or a segment number and an offset from where the data are to be retrieved from.
S4, which gets the same value than S6, is the address in DMEM where such data are to be stored.
S1 sets the direction of the data, meaning from or to RDRAM.

There is however two sub-routines called, which have as well to be apprehended:

0x11C    LW        T3, +0x00B8(R0)
0x120    SRL       T4, S3, 0x16
0x124    ANDI    T4, T4, 0x003C
0x128    AND     S3, S3, T3
0x12C    ADD    T5, R0, T4
0x130    LW       T4, +0x0160(T5)
0x134    JR         RA
0x138    ADD    S3, S3, T4

This routine mainly manages the memory segmentation.

0x11C    LW    T3, +0x00B8(R0)

T3 = 0x00FFFFFF. Such a value is used as a mask to get rid of the 1st byte of the T8, which contains the RDRAM address.

0x120    SRL       T4, S3, 0x16
0x124    ANDI     T4, T4, 0x003C
0x128    AND      S3, S3, T3

The first byte of the RDRAM address set in the second word of the command may contain a value corresponding to the number of the segment where the data is located, the lower bytes of the command containing only the offset. By doing a shift right of S3 we get in register T4 this number multiply by 4. As there is only 16 segments, the code limits such a value to 0x0F*0x04 = 0x3C

Note that where an actual RDRAM address is set in the second word of the command, the fist byte would be then 0x00, which is for the physical addressing (see 11.1.2 Segmented Memory and the RSP Memory Map in the N64 Programming Manual).

The first byte of S3 is set to 0x00 thanks to the mask loaded in T3.

0x12C    ADD    T5, R0, T4
0x130     LW    T4, +0x0160(T5)

From there the segment is loaded in T4. Those are located in DMEM as from address 0x160. As you certainly understand it is normal that actually the segment number is multiplied by 4 as a word is composed of 4 bytes :) As you may imagine, the value of the 1st segment for physical addressing is 0x00000000.

0x134    JR    RA
0x138    ADD    S3, S3, T4

The subroutine is exited, but before the S3 gets the RDRAM computed with as segment + offset. In case of physical addressing, it is simply what the address set in the second word of the command.

The second subroutine was already explained in my previous article. It runs the DMA processing from/to RDRAM from/to DMEM.

Finally the dispatch code continues.

0x09C    LH      V0, +0x00BC(AT)
0x0A0    JR       V0
0x0A4    SRL    V0, T9, 0x17

Register V0 gets the IMEM address of the immediate commands to run. There is indeed in DMEM a table containing such addresses which is set at the loading of the microcode in the RSP. The code jumps then to this IMEM address.

In case of G_MOVEMEM or any DMA immediate commands, the code goes to PC 0x3C4.

0x3C4    ANDI    V0, V0, 0x01FE
0x3C8    LH         V0, +0x00C4(V0)
0x3CC    JAL       0x164
0x3D0    LBU      AT, -0x0007(K1)
0x3D4    JR          V0
0x3D8    ANDI    A2, AT, 0x000F

Without going to details, the code called a subroutine ensured that all data were retrieved from RDRAM, sets some registers with a value part of the processed immediate command and jump to another part of IMEM, following another table stored in DMEM.

In case of G_MOVEMEM, the code goes to PC 0x558.

0x558    LQV    $v0[0], +0x000(S6)
0x55C    LH    A1, +0x0270(AT)
0x560    J    0x10A8
0x564    SQV    $v0[0], +0x000(A1)

Without going to details, the code loads four words at once from the scratch buffer and stores them to DMEM according to a table stored in DMEM.

As you can see, in order to move 4 words to RDRAM to DMEM, a lot of RSP instructions have to be executed!!! It may be worth noticing that it is  even worth for G_MTX.

After investigations, I came to the conclusion that the whole code explained above has to be severely revised. The main idea is to direct the data to the right place in DMEM at once, avoiding to first move data to a scratch buffer to then move it back to the right place.

We will start by changing the way the code dispatches its execution in IMEM. As we have just seen, it is done by the way of tables stored in DMEM at the initialization of the microcode. Those tables are located in gdmem.h, at the JUMP TABLES section.

For unknown reasons, the structure of those jump tables is messy, with many comments stating “not implemented" but yet still using space in DMEM.

I changed such a section of gdmem.h as follow:

#====================================================================
 # setup a jump table
 #====================================================================

JMP_OFFSET:

.half   GfxDone                     #G_MOVEMEM
.half   GfxDone                     #G_SPNOOP
.half   case_G_MTX
.half   case_G_VTX
.half   case_G_TRI1
.half   case_G_CULLDL
.half   case_G_PMTX
.half   case_G_MOVEWORD     
.half   case_G_DL   
.half   case_G_SETOTHERMODE_H
.half   case_G_SETOTHERMODE_L
.half   case_G_ENDDL
.half   case_G_SETGEOMETRYMODE
.half   case_G_CLEARGEOMETRYMODE
.half   case_G_RDPHALF_2
.half   case_G_RDPHALF_1

There is only one jump table, with no distinction as such between DMA command and immediate commands.

Doing such a cleanup has as consequence to reduce the size in DMEM of the jump tables, which is always nice. However the structure of the DMEM is impacted, meaning that the DMEM address in gbi.h may have to be changed.

The header of the command has been changed to the following:

#define    G_MOVEMEM                                  0x00
#define    G_SPNOOP                                      0x02
#define    G_MTX                                              0x04
#define    G_VTX                                               0x06
#define    G_TRI1                                              0x08
#define    G_CULLDL                                        0x0A
#define    G_PMTX                                            0x0C
#define    G_MOVEWORD                                0x0E
#define    G_DL                                                0x10
#define    G_SETOTHERMODE_H                    0x12
#define    G_SETOTHERMODE_L                    0x14
#define    G_ENDDL                                        0x16
#define    G_SETGEOMETRYMODE                0x18
#define    G_CLEARGEOMETRYMODE           0x1A
#define   G_RDPHALF_1                                0x1C
#define   G_RDPHALF_2                                0x1E


You may notice that the commands are only even number. It is because each address stored in DMEM as jump table takes two bytes.

Here the related implementation of the dispatch code.

0x05C    ADDI       K1, R0, 0x06A0
0x060    LW           T9, +0x0000(K1)
0x064    LW           T8, +0x0004(K1)
0x068    SRL          AT, T9, 0x18
0x06C    ADDI       K0, K0, 0x0008
0x070    ADDI        K1, K1, 0x0008
0x074    BLTZ        T9, 0x0330
0x078    ADDI        GP, GP, 0xFFF8
0x07C    ADDI       V0, AT, 0xFFFE
0x080    BGEZ       V0, 0x00A0
0x084    NOP
0x088    JAL           0x1124
0x08C    SLL          V0, AT, 0x1F
0x090    JAL           0x1140
0x094    ANDI        AT, AT, 0x00FE
0x098    MTC0       S2, SP read DMA length
0x09C    BGEZAL  V0, 0x0164
0x0A0    LH           AT, +0x00C0(AT)
0x0A4    JR           AT
0x0A8    NOP

The RDP commands are dispatched thanks to their sign, being all negative.

0x074    BLTZ        T9, 0x0330

Then as all DMA transfers (except for G_PMTX) are to be managed by G_MOVEMEM (even for case G_VTX and G_MTX), where the command is equal or above 0x02, the command skips the DMA process and goes to the appropriate IMEM address provided by the jump table .

0x068    SRL        AT, T9, 0x18                 # AT=header of the command

0x07C    ADDI        V0, AT, 0xFFFE        # V0 = AT - 2
0x080    BGEZ        V0, 0x00A0               # If equal or above 0, go to 0x0A0
0x084    NOP

0x0A0    LH        AT, +0x00C0(AT)      # load the IMEM address from the jump table
0x0A4    JR        AT                             # jump to such an IMEM address
0x0A8    NOP

If the command is 0x00 or 0x01, meaning G_MOVEMEM, then the code jumps to the segmentation code which has been completely revised.

0x088    JAL        0x1124

0x124    SLL      S3, T8, 0x4               
0x128    SRL      S3, S3, 0x1A
0x12C    LW       S3, +0x0160(S3)
0x130    SLL      T8, T8, 0x8
0x134    SRL      T8, T8, 0x8
0x138    JR         RA
0x13C    ADD     S3, T8, S3

First we get rid of the higher 4 bits of the command in case the address contained in the second word of the command would be a physical one (0x80XXXXXX)

0x124    SLL    S3, T8, 0x4

The highest 4 bits is then multiplied by 4 and then the segment address from DMEM is loaded.
           
0x128    SRL    S3, S3, 0x1A   
0x12C    LW    S3, +0x0160(S3)

We get rid then of the highest byte of the second word of the command.

0x130    SLL    T8, T8, 0x8
0x134    SRL    T8, T8, 0x8

Finally the actual RDRAM address is obtained by adding the segment by the offset set in the lower bytes of the second word of the command.

The code goes then to a second subroutine.

0x090    JAL        0x1140

0x140    LH         S4, -0x0007(K1)
0x144    SRL       S4, S4, 0x4
0x148    ANDI    S2, T9, 0x03FF
0x14C    MFC0   T3, SP DMA full
0x150    BNE      T3, R0, 0x014C
0x154    NOP
0x158    MTC0    S4, SP memory address
0x15C    JR          RA
0x160    MTC0    S3, SP DRAM DMA address

Only the 3 first instructions are new, the rest having been explained in previous articles.

Any command retrieving data will have to be structured in this way:

0xCCAAABBB
0xSSRRRRRR

CC: header of the command
AAA: DMEM address where data are to be processed to/from
BBB: size of the transfer
SS: segment number
RRRRRR: physical RDRAM address or offset.

As you already understand the DMEM address is set in register S4:

0x140    LH      S4, -0x0007(K1)
0x144    SRL    S4, S4, 0x4

And the size of the transfer in S2:

0x148    ANDI    S2, T9, 0x03FF

Finally the DMA transfer starts by the following command

0x098    MTC0        S2, SP read DMA length
Finally remains few instructions unexplained

0x08C    SLL                 V0, AT, 0x1F
0x094    ANDI               AT, AT, 0x00FE
0x09C    BGEZAL        V0, 0x0164

Those instructions are used to implement the optional double DMA transfer.

G_MOVEMEM is normally 0x00. In such a case it means that DMA transfer must be completed before continuing the execution of the command. Where it is 0x01, the codes continues without checking that the DMA transfer is indeed completed (note: may be it would be worth creating a DMAWAIT command)

0x08C    SLL        V0, AT, 0x1F

Register V0 will be 0x80000000 in case the command is 0x01 and 0x00000000 in case the command is 0x00.

0x09C    BGEZAL        V0, 0x0164

In case register V0 is not negative, the code goes to a part of the code to wait that DMA transfer is completed.

0x094    ANDI        AT, AT, 0x00FE

We have to ensure that the code fetches the appropriate IMEM address in the jump table so we do have to even the header of the command (0x01 becomes 0x00).

G_MOVEMEM is actually over so the jump table simply routes the code to the next command to be executed!

With this approach of having only one command to move data from/to RDRAM, G_MTX and G_VTX are impacted and we have to emulate those commands in gbi.h.

For instance gSPVertex:

#define D_SCRATCH     0x7E0    (0x7E0 is the place in DMEM of the scratch buffer).

# define    gSPVertex(pkt, v, n, v0)
       
{                                           
  Gfx *_g = (Gfx *)(pkt);                  
                                           
    _g->words.w0 = _SHIFTL(G_MOVEMEM, 24, 8) | _SHIFTL(D_SCRATCH, 12, 12) | _SHIFTL(((n*0x10)-1), 0, 12);   
                                          
    _g->words.w1 = (unsigned int)(v);      
};                                           
{                                           
  Gfx *_g = (Gfx *)(pkt);               
                                           
    _g->words.w0 = _SHIFTL(G_VTX, 24, 8) | _SHIFTL(0x000000, 0, 24);                                       
                                              _g->words.w1 = _SHIFTL((n), 16, 16) | _SHIFTL(((INPUTBUFFER) + ((v0) * 0x28)), 0, 16);
}               

Obviously we should create new macros as for instance

# define gSPLoadVertices(pkt, v, n, d)     
{                                         
  Gfx *_g = (Gfx *)(pkt);                
                                         
    _g->words.w0 = _SHIFTL(((G_MOVEMEM) + (DMAWAIT_##d)), 24, 8) | _SHIFTL(D_SCRATCH, 12, 12) | _SHIFTL(((n*0x10)-1), 0, 12); 

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

# define gsSPLoadVertices(v, n, d)

{{
  (_SHIFTL(((G_MOVEMEM) + (DMAWAIT_##d)), 24, 8) | _SHIFTL(D_SCRATCH, 12, 12) | _SHIFTL(((n*0x10)-1), 0, 12)), ((unsigned int)(v))
}}

# define gSPTransformVertices(pkt, n, v0)
{                                          
  Gfx *_g = (Gfx *)(pkt);                  
                                          
    _g->words.w0 = _SHIFTL(G_VTX, 24, 8) | _SHIFTL(0x000000, 0, 24);                                      
                                            
    _g->words.w1 = _SHIFTL((n), 16, 16) | _SHIFTL(((INPUTBUFFER) + ((v0) * 0x28)), 0, 16);                   
}

# define gsSPTransformVertices(n, v0)
{{                                        
  (_SHIFTL(G_VTX, 24, 8) | _SHIFTL(0x000000, 0, 24)), (_SHIFTL((n), 16, 16) | _SHIFTL(((INPUTBUFFER) + ((v0) * 0x28)), 0, 16))                   
}}

Of course all gbi macros doing DMA transferred had to be changed to match with this new implementation.

Thanks to those changes 20 IMEM instructions were saved but much more will come in the next phase.. :)

As well some changes in the microcode for G_MTX and G_VTX have been necessary to manage such an implementation, on top other interesting changes which I will explain in my next article.

Stay tuned!

samedi 14 mars 2020

Microcode Optimization: IMEM (Part4)

G_POPMTX

This command pops a matrix which has been previously pushed to a stack in RDRAM by command G_MTX.

0xBD000000 (register T9)
0x00000000 (register T8)

In its original version, there is no parameter for this command.

The related code in the Fast3D microcode is the following:

0x24C    SBV    v31[6], 0x01C (SP)
0x250    LW    S3, 0x0024(SP)
0x254    LW    V1, 0x004C(SP)
0x258    ADDI    S4, R0, 0x0360
0x25C    ADDI    S2, R0, 0x003F
0x260    SUB    V1, V1, S3
0x264    ADDI    V1, V1, 0xFD80
0x268    BGEZ    V1, 0x0A8
0x26C    ADDI    S3, S3, 0xFFC0
0x270    JAL    0x13C
0x274    ADDI    S1, R0, 0x0000
0x278    JAL    0x164
0x27C    ADDI    V1, R0, 0x03E0
0x280    J    0x444
0x284    SW    S3, 0x0024(SP)

Let’s go through the code quickly.

0x24C    SBV    v31[6], 0x01C (SP)

The instruction resets a flag used for lighting and stored in DMEM.

0x250    LW    S3, 0x0024(SP)
0x254    LW    V1, 0x004C(SP)

In register S3 is loaded the current RDRAM address of the stack (pointer).
In register V1 is loaded the RDRAM address of the stack when it is full.

0x258    ADDI    S4, R0, 0x0360
0x25C    ADDI    S2, R0, 0x003F

Register S4 gets as value 0x0360, which is the DMEM address for the modelview matrix. Registers gets as value 0x3F, which is actually the size of the matrix (64 bytes as when data are moved from/RDRAM, 0 counts as well so 0x40 -0x01 = 0x3F).

0x260    SUB    V1, V1, S3

Doing so provides the remaining bytes available in the stack.

0x264    ADDI    V1, V1, 0xFD80

When the stack is empty, the maximum number of bytes available in the stack is supposedly 640 bytes (0x280). When subtracting the remaining bytes available in the stack with the size in bytes of the stack (0x0000-0x0280 = 0xFD80) it is possible to check out whether there is still a matrix to pop. Indeed, would the stack be empty, the remaining bytes available in the stack and the size in bytes of such a stack would be equal.

0x268    BGEZ    V1, 0x0A8

By this instruction, in case there would be no matrix to pop, the code exits the command.

0x26C    ADDI    S3, S3, 0xFFC0

The RDRAM address is reduced by 64 bytes (0x0000 – 0x0040 = 0xFFC0). It will be the base address from which the matrix data will have to be retrieved from RDRAM.

0x270    JAL    0x13C

This instruction calls a subroutine, which is used to retrieve/store data from/to RDRAM.

0x274    ADDI    S1, R0, 0x0000

As you may remember from my previous article, S1 sets the direction from or to RDRAM the data is about to move.

0x278    JAL    0x164

This instruction calls a subroutine for DMA processing, from or to RDRAM.

0x27C    ADDI    V1, R0, 0x03E0

V1 gets its value set to 0x3E0. This is where the modelview projection matrix (modelview x projection matrix) is stored in DMEM.

0x280    J    0x444

This instruction jumps to a part of the G_MTX command in order to get the popped modelview matrix multiplied with the projection matrix and stored in DMEM at 0x3E0 as per previous instruction.

0x284    SW    S3, 0x0024(SP)

Before doing so S3, the new stack pointer, is stored back in DMEM.

From my point of view, as such this command is both too limited in its feature and in its scope. After investigations, I came to the conclusion that it would be better to reuse the code to pop a matrix in order to push a matrix as well. Additionally we will implement a stack not only for modelview matrix but also for the projection matrix. It does mean that the part of the code for pushing a matrix in G_MTX should be either rerouted to G_POPMTX (which will be renamed G_PMTX) or emulated through gbi.h.

Here my implementation in this respect.

0x21C    SBV    $v31[6], +0x01C(SP)
0x220    LH    AT, -0x0004(K1)
0x224    BGTZ    AT, 0x240
0x228    LH    V0, +0x0000(T8)
0x22C    LH    V1, -0x0002(K1)
0x230    BGTZ    V1, 0x23C
0x234    ORI    A0, R0, 0x0300
0x238    ORI    A0, R0, 0x0100
0x23C    BEQ    V0, A0, 0x0A8
0x240    SUB    A1, V0, AT
0x244    BLTZ    A1, 0x0A8
0x248    LW    A2, +0x0024(SP)
0x24C    BGTZ    AT, 0x258
0x250    ADD    S3, A2, A1
0x254    ADD    S3, A2, V0
0x258    BGTZ    V1, 0x264
0x25C    LH    S4, -0x0007(K1)
0x260    ADDI    S3, S3, 0x0300
0x264    SRL    S4, S4, 0x04
0x268    JAL    0x13C
0x26C    ANDI    S2, T9, 0x0FFF
0x270    BGTZ    AT, 0x280
0x274    SH    A1, +0x0000(T8)
0x278    J    0x0A8
0x27C    MTC0    S2, SP read DMA write
0x280    JAL    0x154
0x284    MTC0    S2, SP read DMA length
0x288    J    0x400
0x28C    ADDI    V0, R0, 0x03E0

As you may see, the size of the command has doubled. Actually taking in accounting the fact that the push matrix code of G_MTX uses some instructions as well, the actual increase is only about 30%, which is totally justified by the fact that the code has to manage two stacks and not only one.
The structure of the command is the following:

0xCCAAABBB
0xDDDDEEEE

CC is the command header, meaning 0xBD.

AAA is the place in DMEM of the matrix from which the command will pop or push the data from/to RDRAM. It is 0x360 for the modelview matrix and 0x3A0 for the projection matrix.

BBB is the size of the matrix to be retrieve or store from/to RDRAM.

DDDD is the number of bytes either to pop or to push. For a push it is 0xFFC0 and for a pop it is 0x0040.
 
EEEE is the place in DMEM where is store the current number of bytes used in the stack. It is 0x015C when it is for the modelview matrix and 0xF15E for the projection matrix.

So let’s go through the new code.

0x21C    SBV    $v31[6], +0x01C(SP)

The instruction resets a flag used for lighting and stored in DMEM, as before.

0x220    LH    AT, -0x0004(K1)
0x224    BGTZ    AT, 0x240
0x228    LH    V0, +0x0000(T8)

This code loads DDDD in register AT and in case AT is positive, so 0x0040 for pop case, jumps to 0x240. The code loads in register V0 the delay slot a half word located DMEM 0x000 offset T8, so actually at the DMEM address at EEE. It must be noticed that DMEM addresses are only 12 bits so the rest of the word is ignored. So V0 has for values the size in bytes of the stack pointed by the command.

0x22C    LH    V1, -0x0002(K1)
0x230    BGTZ    V1, 0x23C
0x234    ORI    A0, R0, 0x0300
0x238    ORI    A0, R0, 0x0100
0x23C    BEQ    V0, A0, 0x0A8

The code loads EEEE in register V1 and in case it would be negative jumps to 0x23C. So register A0 becomes 0x300 in case the stack pointed by the push is the modelview matrix (0x015C) or 0x100 in case the stack pointed by the push is the projection matrix (0xF15E). A0 has for value the maximum size that each stack may have. As you can understand, the modelview stack is 12 levels deep (0x40 * 12 = 0x300) and the projection stack is 4 levels deep (0x40 * 4 = 0x100). In total the combined stacks can hold 0x10, so 16 matrixes.

Finally in case the current size of the stack pointed by the command (V0) is equal to the maximum size of the stack (A0), it is impossible to push more and the command has to be skipped.

0x240    SUB    A1, V0, AT
0x244    BLTZ    A1, 0x0A8

Register A1 has for value the difference between the current size of the stack pointed by the command (V0) and DDDD. In case we would pop the matrix, AT would be 0x0040 so the current size of the matrix would be increased by 0x40. Additionally in case the pointed stack would be empty, A1 would become negative and the command has to be skipped. In case we would push the matrix, as AT would be 0xFFC0, the current size of the matrix would be increased by 0x40 (0x00000000 – 0xFFFFFFC0 = 0x00000040). As you may understand, A1 is actually the size of the stack after execution of the current command.
       
0x248    LW    A2, +0x0024(SP)
0x24C    BGTZ    AT, 0x258
0x250    ADD    S3, A2, A1
0x254    ADD    S3, A2, V0

Register A2 loads from DMEM the RDRAM address at the bottom of BOTH stacks. In this respect it must be noticed that the projection matrix is piled up on the modelview matrix in RDRAM.

In case we would pop the matrix (AT being positive), register S3 would be equal to be RDRAM address at the bottom of both stacks + the size of the stack pointed after execution of the command. Indeed the RDRAM address from which the data must be retrieved are 40 bytes below the current RDRAM address of the pointed stack.

In case we would push the matrix (AT being negative), S3 would be equal to RDRAM address at the bottom of both stacks + the size of the current size of pointed stack. Indeed the matrix data is to be stored in RDRAM from the top of the stack, where there is still available space in memory.

0x258    BGTZ    V1, 0x264
0x25C    LH    S4, -0x0007(K1)
0x260    ADDI    S3, S3, 0x0300
0x264    SRL    S4, S4, 0x04

If V1, so EEEE, is positive, then jump to 0x264. In such a case it would mean that the stack pointed is the modelview matrix, otherwise add to RDRAM address 0x300 contained in S3. Indeed as the stacks are piled up, from the very bottom of the two stacks, you need to add 0x300 to reach the bottom of the projection matrix. In both case register S4 becomes 0xAAA.

0x268    JAL    0x13C
0x26C    ANDI    S2, T9, 0x0FFF

The first instruction calls a subroutine, which is used to retrieve/store data from/to RDRAM. In the second one, S2 gets as value the number of bytes to be popped or pushed from/to RDRAM.

0x270    BGTZ    AT, 0x280
0x274    SH    A1, +0x0000(T8)
0x278    J    0x0A8
0x27C    MTC0    S2, SP read DMA write
0x280    JAL    0x154
0x284    MTC0    S2, SP read DMA length
0x288    J    0x400
0x28C    ADDI    V0, R0, 0x03E0

 The new size of the pointed stack (register A1) is stored in DMEM.

Depending where AT (DDDD) is positive or negative (so a pop or a push), the code either write data to RDRAM or read data from RDRAM. The code ensures that the data are indeed retrieved from RDRAM to DMEM thanks to a subroutine (JAL 0x154). In case the matrix would be pop, the code jumps to a part of the G_MTX command in order to get the new modelview projection matrix and stored in DMEM at 0x3E0.

Finally we have to adapt the macros in gbi.h.

#define SZ_G_MTX_MODELVIEW           0x015C                           
#define SZ_G_MTX_PROJECTION           0xF15E
#define D_G_MTX_MODELVIEW             0x360
#define D_G_MTX_PROJECTION             0x3A0

#define gSPPopMatrix(pkt, n)                   
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12);   
                                               
    _g->words.w1 = _SHIFTL(0x0040, 16, 16) | _SHIFTL(SZ_##n, 0, 16);                       
}

#define gsSPPopMatrix(n)                       
{{                                               
    (_SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12)),               
    (_SHIFTL(0x0040, 16, 16) | _SHIFTL(SZ_##n, 0, 16))                                       
}}

#define gSPPopMatrixN(pkt, n, num)               
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12);   
                                               
    _g->words.w1 = _SHIFTL((0x0040 * (num)), 16, 16) | _SHIFTL(SZ_##n, 0, 16);               
}

#define gsSPPopMatrixN(n, num)                   
{{                                               
    (_SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12)),               
    (_SHIFTL((0x0040 * (num)), 16, 16) | _SHIFTL(SZ_##n, 0, 16))                           
}}

#define gSPPushMatrix(pkt, n)                   
{                                               
    Gfx *_g = (Gfx *)(pkt);                       
                                               
    _g->words.w0 = _SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12);   
                                               
    _g->words.w1 = _SHIFTL(0xFFC0, 16, 16) | _SHIFTL(SZ_##n, 0, 16);                       
}

#define gsSPPushMatrix(n)                       
{                                               
    (_SHIFTL(G_PMTX, 24, 8) | _SHIFTL(D_##n, 12, 12) | _SHIFTL(0x03F, 0, 12)),               
    (_SHIFTL(0xFFC0, 16, 16) | _SHIFTL(SZ_##n, 0, 16))                                       
}

gSPPopMatrixN is a macro which can pop n number of matrix.

And voila! :)

Finally one little comment on the number of matrix in the original code: I do believe that there has been an error in this respect by the microcode developers. In ucode.h you may find that there is 1024 bytes is allocated for the matrix stack.

* This is the recommended size of the SP DRAM stack area, used
 * by the graphics ucode. This stack is used primarily for the
 * matrix stack, so it needs to be AT LEAST (10 * 64bytes) in size.
 */
#define    SP_DRAM_STACK_SIZE8    (1024)
#define    SP_DRAM_STACK_SIZE64    (SP_DRAM_STACK_SIZE8 >> 3)

10 * 64 = 640 bytes, not 1024!

1024 bytes corresponds to 16 matrix, which is … 0x10 matrix!

So I would guess there has been a mix up between 10 and 0x10… !!!

The original Fast3D microcode limited indeed the size of the matrix stack to 10 but as from F3DEX this limitation has been actually removed… :)

Next time we will tackle G_MOVEMEM which does require some major changes in the code to become much more efficient than current implementation. Stay tuned!