Well, looks like I’m late again!

I haven’t been posting as much as I wished lately because studies got in the way, but I still did some cool stuff out of this blog, being a video explaining current object recognition in AI or a KH2 Model importer (this time fixed and working!)
Since I wanted to avoid posting a rant here and just fill my blog with “useless” content I’m going to write an article about the latter but I’m still doing other stuff outside of the public scope, and even planning for even bigger stuff publically (hint: Linux Foundation) ! But anyways let’s get started with a quick backstory about KH2 hacking.

Kingdom Hearts 2 Overview

Kingdom Hearts 2 is a once-in-a-lifetime experience. Remember how Earthbound was overengineered by sides in, for example, its text engine? Well KH2 is exactly that, except on EVERYTHING. ON AN OVER-ENGINEERED CONSOLE. Ohhhhhhhhh boi.

As KH2 was once a game before being a piece of scrutinized technology, once upon a time we had an ISO of this game. Which contained files. Let us look at them:

➜  KH2FM isoinfo -l -i KH2FM.ISO 
Setting input-charset to 'UTF-8' from locale.
**BAD RRVERSION (0) in '  ' field 00 00.

Directory listing of /
dr-xr-xr-x   1    0    0        968 Feb 16 2007 [    261 02] . 
dr-xr-xr-x   1    0    0        968 Feb 16 2007 [    261 02] .. 
-r-xr-xr-x   1    0    0         54 Feb 16 2007 [    284 00] SYSTEM.CNF;1 
-r-xr-xr-x   1    0    0    2629364 Feb 16 2007 [    285 00] SLPM_666.75;1 
-r-xr-xr-x   1    0    0     278305 Feb 16 2007 [   1569 00] IOPRP300.IMG;1 
-r-xr-xr-x   1    0    0       6641 Feb 16 2007 [   1705 00] SIO2MAN.IRX;1 
-r-xr-xr-x   1    0    0      11289 Feb 16 2007 [   1709 00] SIO2D.IRX;1 
-r-xr-xr-x   1    0    0      15653 Feb 16 2007 [   1715 00] DBCMAN.IRX;1 
dr-xr-xr-x   1    0    0        154 Feb 16 2007 [    262 02] PAD2 
-r-xr-xr-x   1    0    0      96181 Feb 16 2007 [   1729 00] MCMAN.IRX;1 
-r-xr-xr-x   1    0    0       7385 Feb 16 2007 [   1776 00] MCSERV.IRX;1 
-r-xr-xr-x   1    0    0      30085 Feb 16 2007 [   1780 00] LIBSD.IRX;1 
-r-xr-xr-x   1    0    0      91949 Feb 16 2007 [   1795 00] LIBSSL.IRX;1 
-r-xr-xr-x   1    0    0      82548 Feb 16 2007 [   1840 00] KH2.IDX;1 
-r-xr-xr-x   1    0    0        276 Feb 16 2007 [   1881 00] OVL.IDX;1 
-r-xr-xr-x   1    0    0 1371772928 Feb 16 2007 [   1882 00] OVL.IMG;1 
-r-xr-xr-x   1    0    0 2933575680 Feb 16 2007 [ 671693 00] KH2.IMG;1 

Directory listing of /PAD2/
dr-xr-xr-x   1    0    0        154 Feb 16 2007 [    262 02] . 
dr-xr-xr-x   1    0    0        968 Feb 16 2007 [    261 02] .. 
-r-xr-xr-x   1    0    0      10973 Feb 16 2007 [   1723 00] DS2O.IRX;1 

Fine, we get several files. Let us then list the files used by the PS2 itself then:

• SYSTEM.CNF is what the PS2 looks up to boot the game; specifies the ELF and stuff
• SLPM_666.75 is the ELF of the game, the main executable
• IOPRP300.IMG is a cdvd module used to load the game
• SIO2MAN.IRX is a module which… is used to load other modules
• SIO2D.IRX is a module which handles memory cards
• DBCMAN.IRX is a remote manager for DBC, whatever that is (SQEX lib?)
• PAD2/DS2O.IRX Seems like some sort of dualshock library for PAD 2…?
• MCMAN.IRX is the memory card manager
• MCSERV.IRX is the memory card server, allowing you to control remotely MCMAN(WHY IS THIS ON RETAIL ???)
• LIBSD.IRX is the sound library
• LIBSSL.IRX is “Square’s Sound Library”, used for KH2 BGM, SEB, etc

And then we have four files, KH2.IDX, KH2.IMG, OVL.IDX and OVL.IMG, this is where the real fun begins.

As a side note before continuing both KH RECOM and KH1(which were released on the PS2 as well) had a special LBA INSIDE the ISO which told you offsets as of where the files in the ISO where used as both an obfuscation mechanism and a quicker way to read files, so we had it easy on this game.

To get back on topic those files contains all the assets the game uses, and after some reverse engineering we can conclude they use this format, written using the beautiful Kaitai Struct which I encourage you to check out:

meta:
  id: kh2_idx 
  endian: le
seq:
  - id: num_files
    type: u4
  - id: files
    type: file_entry
    repeat: expr
    repeat-expr: num_files
types:
  file_entry:
    seq:
      - id: main_hash 
        type: u4
      - id: second_hash 
        type: u2 
      - id: flags 
        type: u2
        doc: |
            & 0x8000: Verify secondary hash
            & 0x4000: Is compressed
            & 0x3FFF: Compressed size = (flags + 1) * 2048            
      - id: offset
        type: s4
        doc: offset in the IMG
      - id: size 
        type: s4

And the IMG files are just a bunch of data you read using the IDX files. So niiiiiiice. We got some hashed files, you know what a hash is, right? In a nutshell it basically converts the filename of the file into a number, using the following formula:

$$ h = \sum (c \ll 24) \oplus max$$ where max is 0xFFFFFFFF and c is a character of the filename and

$$\sum_{i=0}^9 (h \ll 1) \oplus magic$$ where magic is 0x04C11DB7 if h & 0x80000000 or 0 if that isn’t the case

The hashing algorithm for the secondary hash is the following: $$ h = \sum (c \ll 8) \oplus max$$ where max is 0xFFFF and c is a character of the filename and

$$\sum_{i=0}^9 (h \ll 1) \oplus magic$$ where magic is 0x1021 if h & 0x8000 or 0 if that isn’t the case

After boring you with all those maths the main idea to remember is that this is one way. I repeat ONE WAY. You CANNOT retrieve the filenames out of the number. What does this mean for us? We have a bunch of files which have filenames as helpful as 83021632 !

To retrieve those files we had several choices but we took the least effort path: the game was calculating on-the-fly the filename hashes using the real names. Say the game tries to load the file obj/P_EX120.mdlx ? it goes this way:
load_file(hash_name(name)); So we did what any sane person would do and made the game print out the used files!
Below is a pnach code to be used with PCSX2 that does just that, courtesy of Crazycatz00.

// SLPM-66675 [FM]
2010001c 0804004a
20100024 808f0000
20100028 0806b886
2010002c 00805821
20100030 3c0a0000
20100034 254a0000
20100038 11400002
2010003c 00402821
20100040 1542000d
20100044 3c040038
20100048 27bdfff0
2010004c ffbf0000
20100050 ffa20008
20100054 0c0bf7f2
20100058 24848ab0
2010005c 01602821
20100060 3c040037
20100064 0c0bf7f2
20100068 2484e9b0
2010006c dfbf0000
20100070 dfa20008
20100074 27bd0010
20100078 03e00008
2010007c 00000000
201ae210 08040009
201ae260 0804000c

Fine, now we have a more or less complete list of files with their original names, and brute forced some others, so we have access to the assets the game use! Before going further though, the game contained inside the IMG some other idx files, which contained more entries inside the IMG. This is to take into account if you want a complete list!

We then began reverse engineering randomly some asset files and we saw there was a pattern: most files were actually packed as BAR containers(supposedly Binary ARchives), so a container in a container in a container? Suuuuuure.

The BAR format is defined below as another Kaitai Struct:

meta:
  id: kh2_bar
  endian: le
seq:
  - id: magic
    contents: [0x42, 0x41, 0x52, 0x01]
  - id: num_files
    type: s4
  - id: padding
    size: 8
  - id: files
    type: file_entry
    repeat: expr
    repeat-expr: num_files
types:
  file_entry:
    seq:
      - id: type
        type: u2
      - id: duplicate
        type: u2 
      - id: name
        type: str
        size: 4
        encoding: UTF-8
      - id: offset
        type: s4
      - id: size 
        type: s4
    instances:
      file:
        io: _root._io
        pos: offset
        size: size

The format seems basic enough, alright, there is a type value which can(and does) have a lot of different types which would be a pain in the ass to all reverse but w\e, that seems ok with me.

Now what I forgot to tell you is that some kh2 files are NOT BARs. Because why not. So we end up with custom formats inside BARs and custom formats. Great, just what I needed, spend more time reversing stuff.

But anyways, today is not the day to dive deep into all of those fancy other formats, so let us just focus on…

The MDLX Format

The first thing we notice with the MDLX format is that it’s a BAR(phew) with a variable number of items but it rarely goes below 3. The main format we will focus on today though is the format of type 0x04 inside a BAR file, as other types are usually object definitions(which bone to lock on, etc), textures, AI and other stuff. And this is where I’ll kindly ask you to read back this nice article of mine to give you an idea of PS2 3D development.

You’re back? Great now we can go on.
So as you’ve read KH2 splits models in what we calls subparts, which are mainly just assembly code.

But let’s get back to an higher level overview of the format, stealing my documentation from my model importer:

         BAR
|-------------------|
|        0x04       |
| |---------------| |
| |               | |
| |     MDL_H     | |
| |   |-------|   | |
| |   |MDL_P_H|   | |
| |   |MDL_P_H|   | |
| |   | ...   |   | |
| |   |-------|   | |
| |     ?????     | | <- unused in KH2, used in KH1
| |     MDL_P     | |
| | |-----------| | |
| | |   BONES   | | |
| | | |-------| | | |
| | | |  BONE | | | |
| | | |  BONE | | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |    SUBP   | | |
| | | |-------| | | |
| | | | VIFPKT| | | |
| | | | VIFPKT| | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |    DMA    | | |
| | | |-------| | | |
| | | |DMA_VIF| | | |
| | | | MAT_I | | | |
| | | | MAT_I | | | |
| | | |  ...  | | | |
| | | |DMA_VIF| | | |
| | | |  ...  | | | |
| | | --------- | | |
| | |    MAT    | | |
| | | |-------| | | |
| | | | MAT_I | | | |
| | | | MAT_I | | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |-----------| | |
| |     MDL_P     | |
| | |-----------| | |
| | |   BONES   | | |
| | | |-------| | | |
| | | |  BONE | | | |
| | | |  BONE | | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |    SUBP   | | |
| | | |-------| | | |
| | | | VIFPKT| | | |
| | | | VIFPKT| | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |    DMA    | | |
| | | |-------| | | |
| | | |DMA_VIF| | | |
| | | | MAT_I | | | |
| | | | MAT_I | | | |
| | | |  ...  | | | |
| | | |DMA_VIF| | | |
| | | |  ...  | | | |
| | | --------- | | |
| | |    MAT    | | |
| | | |-------| | | |
| | | | MAT_I | | | |
| | | | MAT_I | | | |
| | | |  ...  | | | |
| | | |-------| | | |
| | |-----------| | |
| |      ...      | |
| |---------------| |
|                   |
|-------------------|
|        0x07       |
|    |---------|    |
|    |  TIM_0  |    |
|    |  TIM_1  |    |
|    |  .....  |    |
|    |---------|    |
|                   |
|-------------------|
|       0x17        |
|-------------------|

In a nutshell the Model Header(MDL_H) contains Model Part Headers(MDL_P_H) for each mesh of the given model(a mesh per texture), which themselves contain Model SubParts, listed in the DMA section, as the DMA_VIF entries. MAT contains the index of bones used by the current model subpart, referenced by its header, and the bone list is contained for a Model part and not SubPart.
And there’s even more! Usually we have at the very least TWO models inside one because one of them have to be the model shadow, of fricking course, which have a slightly different format than the original one. GREAT.

Let us view each part of a model subpart by increasing order of difficulty, to make all of this easier:

• MAT basically contains a list of Matrix Indices, followed by an array delimitator. Easy.
• DMA Contains operations which are going to be executed by the VU1: it transfers the VIF microcode(the model subpart) followed by the matrix indices for this model subpart, the same ones as MAT.
• BONE contains a list of BONES for the COMPLETE Model Part, and not SubPart, all of which containing an SRT matrix and a bone hierarchy
• a VIFPKT contains assembly code which is going to write to memory the wanted informations for the model.

As explaining VIF packets KH2 uses would take an entire article by itself I’ll effectively link you to a tool I made that generates VIF packets if you want to understand them, as this is waaaay out of scope for this article.

But why did I talk about those matrix indices when it is effectively the same as a bone and what is a Quartenion? Well, to answer such questions I’ll have to guide you through a…

Quick intro to the world of 3D

The most basic thing every one of you should know about 3D is that models are composed of vertices, which are points in 3D space. When linking 3 vertices or more together you create what is known as a face, in that case a triangle face. Quick advance and we’re now realizing animations are cool. So we want to animate stuff. So we make something called a skeleton, to animate parts of each mesh.
A skeleton is in effect a bunch of bones which single-handedly affect a pair of vertices, each of them weighted(ie this vertex will move much more than this other one assigned to the same bone depending of the w value).
And sure enough, we soon get…

That is all nice and fun but now we need to talk a bit about Skeletal animations to understand the MDLX Format. Now that we have our skeleton, one would think that you would actually just parse the vertices at their position in space and forget about it? Well KH2 does something else: it stores a “bind position” which, to quote internet, is “The only pose that does not cause deformations to the skin is the bind pose”. The T-pose basically.
KH2 store this bind pose as an SRT matrix per bone, which stands for Scale, Rotate, Translate. To visualize, such datas would look like this:

$$\begin{pmatrix} Sx & Sy & Sz \cr Rx & Ry & Rz \cr Tx & Ty & Tz \end{pmatrix}$$ So to get our final vertices value we should basically do this:

$$\begin{pmatrix} Sx & Sy & Sz \cr Rx & Ry & Rz \cr Tx & Ty & Tz \end{pmatrix} \Rrightarrow \begin{pmatrix}x & y & z \end{pmatrix}$$ Where \(\Rrightarrow\) represents the operations applied, which are the SRT, in order, in 3d space.

Now that is NOT how modern 3D formats deal with this issue, this is how 10years old softwares, such as KH2, used to. You see, KH2 doesn’t have a bone space and a mesh space, they’re the same. In a nutshell modern formats bones only influence the movement of the vertices, not their position, which KH2 of course does.
KH2 will be a pain until the end of times.
But now that we got this matrix, Scaling and Translating operations seems to be trivial to apply mathematically wise, but what about rotations? And this is where comes in play Quaternions.

Rotations in the 3D world are quite cumbersome to program, and the old Euler representation of rotation got excluded fairly quickly because of the gimbal lock it produced during rotations and its speed, as it was taking a 3x3 matrix all by itself, so we decided to move on to another representation of rotations, with complex numbers called Quaternions because why not?

Complex numbers, aren’t they confusing? that \(i=\sqrt{-1}\) is already a pain for some to understand, but quaternions are fun little things, and so, using the Quaternion notation noted above, \(x^2 = y^2 = z^2 = -1\). This part should really come confusing to some as why would we dive into something as complex as complex numbers for computer graphics, don’t we want to simplify the calculations? And as unintuitive as it seems to be we are indeed limiting calculations, thanks to some properties of the Quaternion. As this is going to become quite a heavy post if I explain all 3d transformations I’m just going to link you to a neat 3D visualization of quaternion rotations but this allows us to make scalar multiplications( 4 numbers) instead of matrices(3x3, 9 numbers), and prevents what we called gimbal lock.

But TOO MUCH MATHS. So let’s just do some more reversing now that we understand fairly enough 3d graphics.

Back to the MDLX

Now that we understood the basics of the bone organization we can try to get a grip at how to import them!
As modern formats have vertices position which aren’t related to bone position we first need to get those from an absolute position into a relative one, which would be linked to relative bones and so on, fun. So you need to recalculate the bone positions to be relative to the vertices, and recalculate the Quaternion rotations, scaling and translating operations.
But the fun doesn’t stop there of course, since we need to build those VIF packets now! So after fixing the bone table you need to fix the vertices position and be sure that the VIF packets, splitted for the VU1 memory, are actually correct! The rest is fairly easy though, you just put the DMA tags, containing the address of the VIF packets and the matrices, follow by the matrix indexes and boom, you’re pretty much done.

Now then we’re still missing the texture data, fortunately those are using a pretty common format for the PS2, TIM2, and we can build custom ones easily, hence I will skip this part and just show you the result:

Conclusion

Since we pretty much understand the complete MDLX format what are we currently missing? Well not a lot actually, the only real “missing” things we have are dependant on the object type, we do not support vertex weighting yet for example, as they are not supported in simpler models, nor bone-less models, such as maps, even though maps are pretty similar.

But other than that the current model importer imports successfully bones, faces, vertices and UVs! (except bone hierarchy but shhhh)

Also while most of the research on the game was already done a while ago reversing this game is no simple task, for several reasons but you will notice one of them quite easily.

Yup, no easy way to view and edit VU1 memory, nor trace operations and reads on the VU1 mem. Which is fun as all subpackets are of course ran on the VU1.
But that’s by no means where pcsx2 stops being shitty, this debugger is horrendous for pretty much every non basic operation(any break breaks all CPUs, register access is wonky, no access to CPUs other than the EE). So usually we all end up hacking our way through pcsx2 to have something more or less working, hell we even worked on a gdb stub at some point.
So with that out of the way our models are supposedly working so far, (can be viewed in all our, both public and private, model viewers) but for some reason one viewer and the game still doesn’t like it, and nobody have had the time to debug this issue so far. So all we need to do is fix that crash and add support for other model types, so we can support, say, custom maps!

3D wise I skipped a bunch of stuff such as normals at the very least so don’t take this as an intro to 3D in itself, especially when it comes to quaternions. I know I might have sounded like a know-all on that part and just that it’s too simple to explain but it’s just that all we really care about for quaternions is that they’re easier to process, and their properties are mostly useless when it comes to actual rotation in 3D space.

I’m writing this 2 days after having posted the article and of course I manage to successfully import models in the game and make them load in all the viewers that we previously failed to get any result out of, so here you go, here’s the first “real” in-game model we imported