Author Topic: CHRONO CROSS FILE EXPLORATION THREAD  (Read 22324 times)

MDenham

  • CC:DBT Dream Team
  • Chronopolitan (+300)
  • *
  • Posts: 330
  • Glowsticks are not a weapon.
    • View Profile
    • Java IRC - konata.echoes-online.com
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #300 on: December 20, 2007, 12:30:15 am »
Nah, I see OTag references in KID.exe too, just like in the SLUS executable. Interesting. M, what Zeality posted is probably worth a look too, from what I can tell. I wonder why KID.exe is so much larger than the final SLUS?
I'll take a look at it sometime tomorrow, probably, though I imagine that KID.exe is larger because either Square hadn't stripped the symbols out yet or because of extra debugging code that was still in there.

I'm pretty sure the function we'd be looking for, if we had the original C source, would be Kz_modelGetNormalPolygon(), but tracking it down is a whole other kettle of fish.  :(

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #301 on: December 20, 2007, 12:32:59 am »
Ah, I do remember seeing things like that in another completely unrelated game's executable. It looks familiar. I'll go back to that game (it was Ogre Battle PSX, btw) and see if I find it again, then I'll check it against Cross' SLUS executable. Maybe that way I can cut down some of the busywork for ya.

MDenham

  • CC:DBT Dream Team
  • Chronopolitan (+300)
  • *
  • Posts: 330
  • Glowsticks are not a weapon.
    • View Profile
    • Java IRC - konata.echoes-online.com
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #302 on: December 20, 2007, 01:22:41 am »
Well, right about now I'm ready to beat things with pointy sticks. :D I am NOT a fan of the whole MIPS "yeah, we'll execute the command immediately AFTER a jump in your program, just to mess with people reading a disassembly" thing.

It also doesn't help that immediate operands are limited to 16-bit quantities...  that get sign-extended out.  :?

I'm going to have to actually try and do some kind of live trace on it and see when it finally loads in a vertex to get any sort of information this way, unfortunately.  Ah, well.

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #303 on: December 20, 2007, 04:50:47 pm »
I had high hopes we'd be able to develop a general Pointer Theory without having to dive into the assembly language, but here's another monkey wrench for us to deal with:

You know the positive pointers? The ones in the form of byte pairs 5808 (for value 0x0858) and the like? Their meaning may be situationally dependent in some way.

Allow me to illustrate such an instance. First off, I believe Quad "B" in the above examples should have pointer info of the following: 8008 5808 B008 8808. I'll get around to presenting graphical evidence later -- in any case, M's mathematical scheme may lead us to the same conclusion.

For now, let's focus on the first byte pair pointer in quad B's non-UV data. This is what happens when I change the first pointer to the 8008 (for value 0x0880):


It would appear that changing the pointer as such makes the texture try to map to a vertex on Serge's elbow. We can test the location of the vertex it's pointing to by radically altering the vertex's 3D coordinates. A value of 0x0880 would point to address 0x3168 in the vertex pool (0x28E8 + 880).

But here's what happens when we change the vertex at address 0x3168:


What the!? That was the vertex we were trying to map to in the first place! The proper vertex moved! But when Quad B's pointer is changed so that it points to that vertex mathematically, it doesn't point to that vertex!!

The proper vertex moved, but that UV coordinate in Quad B still tries to map to Serge's elbow. This means one thing: when address 0x18E6 (the "end" address in the back-pointer loop) reads 8008, the machine reads it as 0x0880 pointing to 0x3168. But when address 0x1950 reads 8008, the machine interprets it as something entirely different.

I'm going to double-check my experimental results just to be sure, and to see if this sort of thing occurs elsewhere. I should point out that I've seen other positive pointers that don't "work," yet in this case the 8008 at address 0x18E6 does work -- just not at address 0x1950. Double confuzzlement!
« Last Edit: December 20, 2007, 09:41:02 pm by FaustWolf »

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #304 on: December 20, 2007, 07:41:15 pm »
Here's what I've got for the byte pairs Quad B's pointers should point to: 8008 5808 B008 8808

The last two byte pairs work perfectly, the first two suffer from the problem I noted above, so I may still not have things right -- MDenham, see if you agree with these values for the byte pairs. I'll reproduce some code from this section of the model:

The highlighted section at the bottom is Quad B's non-UV data. Pointers and the byte pairs I believe they point to are in color-coded boxes, so the red pointer points to the other red box, etc.

Here's why I believe 8008 and 5808 are the pointers to the correct vertices in Section 1-3. The value 0x0880 points to the vertex at address 0x3168, and the value 0x0858 points to the vertex at address 0x3140. Below you can see the results of changing the 3D coordinates of both vertices; quad B, which I've blacked out, appears to map to both!


Now, is there some way we can get from Quad B's non-UV data (0x1950 ~ 0x1958) to the color-boxed addresses mathemagically? One consideration is that the value 0xFFE0 works best if divided by 8 for the section of data pertaining to Serge's belt buckle.

- - - - -

Another ominous sign: when I direct Quad B's first pointer to Serge's belt buckle via changing the byte pair to 6809, Serge's sock texture tries to stab Glenn in the leg:
http://img266.imageshack.us/img266/3197/pointedtobeltwl4.gif

So obviously something's weird with the address 0x1950. But on the upside, if we can figure out the mathematics behind the pointers indicated above, we'll know what's going on with the negative pointers at least!
« Last Edit: December 20, 2007, 10:06:23 pm by FaustWolf »

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #305 on: December 21, 2007, 01:44:34 am »
Okay, I think I've divined the rules by which these negative pointers should be interpreted. Judging from everything I've seen so far, the rule set is:

*If the pointer value ends in an 8, divide by 8 to get the number of positions backward in the non-UV data
*If the pointer value ends in B0, divide by 16.

*If the pointer value ends in D0, divide by 16.
*If the pointer value ends in E0, divide by 8.
*If the pointer value ends in F0, divide by 16.

I suppose we could insert "If the pointer value ends in C0, divide by 8" into the blank line to fill in a pattern. But does anyone have a guess as to why this is so? Are these rules based on a mathematical principle of some sort, or does it have something to do with the way the GPU/GTE processes information?

Anyway, let's run through Quad B's first two pointers based on these rules.

First Pointer: address 0x1950, value 0xFFD0.
0xFFD0 = -48, /16 = 3 positions back...
->address 0x1942, value 0xFED0 = -304, /16 = 19 positions back...
-->address 0x18F4, value 0xFFE8 = -24, /8 = 3 positions back...
--->address 0x18E6, value 0x0880. Just what we want! Yay!

Second Pointer: address 0x1952, value 0xFEB0.
0xFEB0 = -336, /16 = 21 positions back...
->address 0x1900, value 0xFFF0 = -16, /16 = 1 position back...
-->address 0x18F6, value 0xFF58 = -168, /8 = 21 positions back...
--->address 0x18A4, value 0x0858. Just what we want! Yay!

It doesn't show up in this example, but we need to interpret 0xFFE0 as being divisible by 8 in order to preserve the functionality of the belt buckle pointer we saw at address 0x10E4 here: http://img339.imageshack.us/img339/3926/bucklepointersor4.gif

If others can help me theoretically determine why the negative pointers may function this way (some divisble by 16, others by 8 ), we'll be ready to move onto the search for bone data soon. I'm not sure what the heck we're going to do with the positive pointers, because those seem to be going even more haywire.
« Last Edit: December 22, 2007, 12:56:37 am by FaustWolf »

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #306 on: December 21, 2007, 02:40:01 am »
Next up, for M or anyone else interested in diving into the executable's assembly code, here's my cursory findings via hex editor:

First, the function kzModelGetNormalPolygon() occurs as an ASCII tag around 0x7EEE0.

0x46D40: some commands, e.g., SetDrawEnv, appear in ASCII around here.
0x48310: a long section of gibberish starts here; maybe others will get more out of it than I.
0x52AF0: Some more "interesting stuff" according to my notes. I forget what's in here specifically.
0x52CF0: I see the ASCII tag vertex tras around here. Not sure if that'll be useful at all.
0x53AF0: Some more functions here it seems. I see something about setting camera projection.

That's just in the hex editor. I'll have to see what shows up in PS2Dis tomorrow and record those offsets. But M, there's your kzModelGetNormalPolygon() anyway.

MDenham

  • CC:DBT Dream Team
  • Chronopolitan (+300)
  • *
  • Posts: 330
  • Glowsticks are not a weapon.
    • View Profile
    • Java IRC - konata.echoes-online.com
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #307 on: December 21, 2007, 03:04:07 am »
Okay, I think I've divined the rules by which these negative pointers should be interpreted. Judging from everything I've seen so far, the rule set is:

*If the pointer value ends in an 8, divide by 8 to get the number of positions backward in the non-UV data
*If the pointer value ends in B0, divide by 16.

*If the pointer value ends in D0, divide by 16.
*If the pointer value ends in E0, divide by 8.
*If the pointer value ends in F0, divide by 16.

I suppose we could insert "If the pointer value ends in C0, divide by 8" into the blank line to fill in a pattern. But does anyone have a guess as to why this is so? Are these rules based on a mathematical principle of some sort, or does it have something to do with the way the GPU/GTE processes information?
Well, the simplified way to handle it would be like this (note that this probably isn't quite correct, for reasons that I'll state later):

Put P[ix] into VP.
HEAD:
If (VP < 0) jump to A.
(do some processing on VP)
Jump to END.
A: If (VP & 0x08), change VP to P[ix + VP/8] and jump to HEAD.
If (VP & 0x10), change VP to P[ix + VP/16] and jump to HEAD.
Change VP to P[ix + VP/8] and jump to HEAD.
END:
(return)

This is, of course, assuming that the pattern holds true for 0xFFA0, 0xFF80, etc. as well.

As far as what's going on with the positive pointers: well, it seems we've figured out why there's so many backwards references for the first two vertices. :D  Something is being done with these vertices in the process of tracing the pointers backwards - most likely the references are to a post-processed vertex array, NOT[/i] the vertex pool!  Also note that every vertex that isn't a backwards reference in the first or second slot that I've seen so far is at least 0x1000.  This brings me back to my note about the pseudo-code for the vertex reader.

Quite possibly, every entry in the first two columns is divided by 2 initially.  Then, anything that still ends in 0 afterwards (which were multiples of 32 to begin with) is divided by 4, while everything else now ends in an 8 and can be handled in one step.  (References in columns 3 and 4 are simply divided by 8.)  Easy check on this would be to take, say, poly 0x17A8 (as all four of its pointers are "normal") - the first two vertices read as 0x1240 and 0x1260.  Change vertices 0x0920 and 0x0930 and see what the effect is on this poly.  We should actually get a useful result from this - either confirmation that there's something weird-but-stupid going on, or confirmation that things are a LOT weirder than I expect.

And now for my minor nitpick of the day: 0xFFD0 is -48. :D

(As far as the whole ASCII tags and such, I noticed them when running through the hex editor myself, which is why I commented on them, especially because they seem to be discarded by PS2Dis, while the error messages for these functions are retained.)

yaz0r

  • Architect of Kajar
  • Porrean (+50)
  • *
  • Posts: 65
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #308 on: December 21, 2007, 09:55:06 am »
KID.Exe doesn't seems to have any debugging symbols. It's bigger mostly because it's a flat binary and all the additional space is filled with 00.
Anyway, I remember FFX using a similar system for the indices. Some vertex indices were actualy negative values, and in that case it was used as on offset to point to previous indices. That seems close to what you are seeing.

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #309 on: December 21, 2007, 11:52:08 am »
M, I've corrected my error. Thanks! Whew, at least I got the result right.

Thanks for the experimental suggestion and the pseudocode. I'll get on the experiments today, and we'll see what's up. I'd like to mention as well that, in the belt buckle experiment (seen here: http://img339.imageshack.us/img339/3926/bucklepointersor4.gif), when I input the pointer byte pair 6809 into address 0x10E4, everything behaves normally. No change in the model because the next quad is still pointing at the right place.

yaz0r, it's good to know a similar scheme is used in FFX -- development of that began in 1999 if I'm not mistaken, so it makes sense for Square to re-use some of their modeling techniques. Do you remember how positive pointers were handled in FFX? Maybe we can glean some knowledge from that. The documentation on the FFIX models doesn't go so deep; but we DO need to know this stuff to view the models, right?

Sora

  • Chronopolitan (+300)
  • *
  • Posts: 362
  • The Terror Of Death
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #310 on: December 21, 2007, 03:20:47 pm »
are they still on Namick?

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #311 on: December 21, 2007, 03:25:58 pm »
The latest experiment M suggested turned out to be really interesting. Here's a snippet of hex code starting at address 0x17A8 in Serge's battle model:

We notice something right of the bat: the UV map section of the code refers to a single point on Serge's texture, (65,89) or (101,137) in decimal, which is a point on the bottom of Serge's shoe.

So, given that this coordinate on the texture maps to a single point, it's awfully weird that the non-UV data look like positive pointers to widely different vertices. The vertices being pointed to, from left to right, are at addresses 0x3B28; 0x3B48; 0x31F8; and 0x3210. Let's test them out to see which of these vertices is correctly given in the non-UV pointers...

First up is the vertex at address 0x3B28. Nope, it's nowhere close to Serge's shoe, so the value given in the first pointer position isn't interpreted "normally."


Next up is the vertex at address 0x3B48. Same deal:


Now for 0x31F8. Looks like we might have a winner.


But 0x3210 is also plausible:


Now for the final test -- If I black out all the UV map data, which vertex is affected? Clearly the vertex at 0x31F8:
http://img147.imageshack.us/img147/9315/31f8proofzu7.gif

This is an extraordinary case, because it's the first time we've been able to pin down the differences between the values a pointer actually has and the value it's supposed to have if it's a working positive pointer. Let''s take a look at these differences byte pair by byte pair. Here's the values the "quad" at address 0x17A8 ~ 0x17B8 actually has:

0x1240 0x1260 0x0910 0x0928

The bolded pointer can be read literally as a positive pointer into the vertex pool. It leads to the vertex starting at 0x31F8. Now, if the machine is able to get to that vertex from each of these pointers somehow, then we have to discount the values by certain amounts. So here goes:

-0x930  -0x950  -0x00  -0x18

But I don't think that means the machine discounts positive pointer values by these amounts in each column.. M, does this exercise provide us any more insight into the way the pointers are working?
« Last Edit: December 21, 2007, 08:11:11 pm by FaustWolf »

MDenham

  • CC:DBT Dream Team
  • Chronopolitan (+300)
  • *
  • Posts: 330
  • Glowsticks are not a weapon.
    • View Profile
    • Java IRC - konata.echoes-online.com
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #312 on: December 21, 2007, 09:51:45 pm »


(...snip...)

The bolded pointer (0x0910) can be read literally as a positive pointer into the vertex pool. It leads to the vertex starting at 0x31F8. Now, if the machine is able to get to that vertex from each of these pointers somehow, then we have to discount the values by certain amounts. So here goes:

-0x930  -0x950  -0x00  -0x18

But I don't think that means the machine discounts positive pointer values by these amounts in each column.. M, does this exercise provide us any more insight into the way the pointers are working?
Mostly this just confirms what we already know - the first two columns aren't working in the same manner as the last two, and I think I know why - it's to provide a simple means to distinguish between triangles and quads (which was something we were having a slight issue with ourselves.

New model of the vertex reader, in pseudo-code and designed to handle triangles (sort of):

Code: [Select]
Read first four bytes of non-UV data (VS[ix..ix+3]) and put them as appropriate into VP[0] and VP[1].
If ( !!! SOME CONDITION HERE !!! ) jump to READ_TRIANGLE.

READ_QUAD:
Read the next four bytes of non-UV data and put them as appropriate into VP[2] and VP[3].
***Divide VP[0] and VP[1] by 2.***
Over (x=0, 1) {
* If (VP[x] > 0), store the actual vertex in the quads' vertex buffer and advance x.
* If (VP[x] & 0x08), set VP[x] = VS[ix - VP[x]/8) and retry with x the same.
* Otherwise, set VP[x] = VS[ix - VP[x]/4) and retry with x the same.
}
Over (x=2, 3) {
* If (VP[x] > 0), store the actual vertex in the quads' vertex buffer and advance x.
* Set VP[x] = VS[ix - VP[x]/8) and retry with x the same.
}
Return to calling procedure.

READ_TRIANGLE:
?????

The reason I can't say how it's handling triangles yet, or exactly how it's distinguishing between triangles and quads, is because I haven't had a chance to look at any of the sections with triangle data yet (it's all been quads to date in the thread).  I suspect triangles only have the first vertex's pointer multiplied by 2, and as with a quad, the last two are used directly.

Anyway, to summarize: I'm almost certain at this point that, for the polygon you were referring to, the first two vertices are, instead of using 0x1240 and 0x1260 for pointers, using 0x0920 and 0x0930 - putting them at 0x3208 and 0x3218 respectively.  Call this the "Rule of One-Half".

I'm a little surprised that nobody else seemed to have noticed that the first two columns for every quad's vertices to date have been multiples of 16, when they seem to be evenly dispersed between xxx0h and xxx8h for the third and fourth vertices.
« Last Edit: December 21, 2007, 09:54:13 pm by MDenham »

FaustWolf

  • Guru of Time Emeritus
  • Arbiter (+8000)
  • *
  • Posts: 8974
  • Fan Power Advocate
    • View Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #313 on: December 22, 2007, 12:14:27 am »
We now have the General Theory of Chrono Cross Model Pointers!!

M's absolutely correct; there's a "rule of one-half" for the negative pointers analogous to the rule for positive pointers illustrated earlier. Here's some pseudo-English to match MDenham's pseudocode:

Rule for Positive Pointers
*If you're in one of the first two columns, divide the byte pair value by 2. This value is the positive pointer into the vertex pool.
*If you're in one of the last two columns, the byte pair value is the positive pointer into the vertex pool.

Rule for Negative Pointers
*If you're in one of the first two columns, divide the byte pair value by 16. Go backward that number of positions into the non-UV data.
*If you're in one of the last two columns, divide the byte pair value by 8. Go backward that number of positions into the non-UV data.

 :lee: We've got all quad pointers figured out, folks!  :lee:

Supercalafradulistic-expialodocious THANK YOU to MDenham!!

I now leave you with the coolest pic I could find to celebrate.

[attachment deleted by admin]

ZeaLitY

  • Entity
  • End of Timer (+10000)
  • *
  • Posts: 10593
  • Spring Breeze Dancin'
    • View Profile
    • My Compendium Staff Profile
Re: CHRONO CROSS FILE EXPLORATION THREAD
« Reply #314 on: December 22, 2007, 12:26:54 am »
The revolution continues!

[attachment deleted by admin]