SPC7110 Reverse Engineering Project

neviksti · Post by **neviksti** » Thu Jul 10, 2008 4:27 pm

Andreas Naive wrote:I have figured out how the 2 contexts of bitplane #5 are selected.

I don't think that is quite right yet.

Look at these parts:

...
56
		47
41 **
56
3c **
4f
		41
47 **
56
4f **
4f
56
4f 
		56
47
...

Code: Select all

...
47
		47
4f ** 
56 **
41
3c
41
		56
56 **
4f **
47 **
41
41
3c
3c
37
41 **
3c
37
47 **
34
34
4f **
4f **
56 **
4f **
34
47 **
		41
41
...

Code: Select all

Code: Select all

The evolution doesn't make sense.

EDIT:
Based purely on the sequences presented here (ie. not going back to the data and looking at shifts,etc.) I marked possible "wrong collumn" entries which would make the evolution fit the state table I posted above. Of course there are other possible markings as well.

Due to the bizarre jumps in prob, yet familiar prob values, I think it is the de-interleaving of these states and not the state table itself that needs to be changed.

Post by **tepples** » Thu Jul 10, 2008 4:28 pm

jolly_codger wrote:Never seen that patent before.
http://www.mediafire.com/?xsrub3f1jgi

In case that disappears, here's another source:
http://pics.pineight.com/nes/US5859926.pdf

kammedo · Post by **kammedo** » Thu Jul 10, 2008 10:13 pm

tepples wrote:
jolly_codger wrote:Never seen that patent before.
http://www.mediafire.com/?xsrub3f1jgi
In case that disappears, here's another source:
http://pics.pineight.com/nes/US5859926.pdf

Wow. Very nice find

. How the hell did you get to it?

neviksti · Post by **neviksti** » Thu Jul 10, 2008 10:21 pm

Yes!

I can track all the probabilities now. Now I just need to finish filling out the prediction tables.

The following part of the evolution table needs changing.
{0x05, 31, 34,0}, //33 l,m <--- changed lps

Then the contexts are selected as follows:

at the end of each bit (before updating context),
lps = (lps<<1) + flag_lps;
inverts = (inverts<<1) + bitinvert;

where flag_lps=1 if the bit was a LPS (and zero if bit was MPS)
bitinvert=1 if the context is inverting the output of the prediction table.

There are thirty contexts, which are selected as follows

bitplane0 ... 0 + 0 + ((lps&0)^(inverts&0))
bitplane1 ... 0 + 1 + ((lps&1)^(inverts&1))
bitplane2 ... 0 + 3 + ((lps&3)^(inverts&3))
bitplane3 ... 0 + 7 + ((lps&7)^(inverts&7))
bitplane4 ... 15 + 0 + ((lps&0)^(inverts&0))
bitplane5 ... 15 + 1 + ((lps&1)^(inverts&1))
bitplane6 ... 15 + 3+ ((lps&3)^(inverts&3))
bitplane7 ... 15 + 7 + ((lps&7)^(inverts&7))

there are nicers way to write that, but I put it in that form to help make it clear what is going on.

neviksti · Post by **neviksti** » Thu Jul 10, 2008 10:47 pm

Done!
There is no prediction table. It is always just the previous 16th bit.

Now I can match both the mps and prob values for all of input_7030_an1.bin

Yeah! I knew we were close.
I'll write up a proper decompressor now.

There are still untested entries in the state evolution table. We should probably come up with some tests for that.

kammedo · Post by **kammedo** » Thu Jul 10, 2008 11:10 pm

neviksti wrote:Done!
There is no prediction table. It is always just the previous 16th bit.

Now I can match both the mps and prob values for all of input_7030_an1.bin

Yeah! I knew we were close.
I'll write up a proper decompressor now.

There are still untested entries in the state evolution table. We should probably come up with some tests for that.

Yahoo ^^

Andreas Naive · Post by **Andreas Naive** » Thu Jul 10, 2008 11:48 pm

Done!
There is no prediction table. It is always just the previous 16th bit.

Nice! I'm guessing that that prediction is the only part that will change when studying the "first byte" = 1 & 2 cases. Just a wild guess.

neviksti · Post by **neviksti** » Fri Jul 11, 2008 3:19 am

Bleh. I'm having trouble figuring out what to trust now.

I took the FEoEZ files here to test with:
http://caitsith2.net/spc7110/
In the root directory of that, I put the following:
http://neviksti.com/SPC7110/DecompTest.exe

and a batch file to test all the 00 encoded entries

Code: Select all

@echo off
For %%k in (00/*.compressed) do DecompTest 00/%%~nk

Here's the output:
http://neviksti.com/SPC7110/testresults.txt

As you can see, it matches files all the way through and many many bytes. But still fails quite a few files eventually. It is very very difficult to figure out which state evolution is wrong by looking at only this data. So I took some that failed early enough that it would be feasible to run them through our "prob calculator" on the real hardware. This helped me find some mistakes in my evolution table.

But I haven't been able to find any more mistakes for awhile.
And even worse, found a case that the real hardware test produced prob tables that I matched, yet I still didn't get the correct decompression. (2AE432-09.compressed ... fails 18 bytes in)

So maybe these files can't be trusted? But look how many files don't fit. Wouldn't people have noticed graphics glitches if the gfx packs were bad?

It is very possible that I don't have the evolution table worked out yet. But second guessing the data itself is driving me nuts. Can someone devise a test set which would go through every transition in the table? Then I can run that several times and make sure it is right and trust it.

Here's the decompressor test code if you want to play with it:
http://neviksti.com/SPC7110/DecompTest.c
(there's remanent junk in there from tests i was running)

Andreas Naive · Post by **Andreas Naive** » Fri Jul 11, 2008 4:31 am

Well, i'm in a hurry and i don't expect to have time to work seriously in this till sunday, so i will just kick in an idea: are you maybe hitting the carry-over problem? At this point i'm not sure how this QM reduced version manage that, so it could be a possibility. Take a look at the points where the fails appear: if you see a good amount of consecutive 1's in the stream, maybe this could be the problem. Just an idea; i don't have time to give a good thought at anything right now, so ignore me if i'm saying nonsenses.

caitsith2 · Post by **caitsith2** » Fri Jul 11, 2008 9:33 am

It does match every 00 decompression for MDH completely. There are 405 of them.

Near · Post by **Near** » Fri Jul 11, 2008 10:39 am

caitsith2, is there any possibility whatsoever that the 00 data was overdumped?

I have looked through all of the uncompressed files in the 00 folder for FEoEZ, and none of it appears to be graphical tiledata. Honestly, none of it even looks like tilemap or script data. I really can't imagine what that data could be useful for in-game. But certainly, even if it were dumped wrong, it wouldn't manifest itself in-game as corrupted graphics. I would be surprised if the game actually even used much of this data.

All of the graphics appear to be in the 01 and 02 folders.

neviksti, thank you for posting your decompressor code. I'm not so sure it's necessarily a problem with the evolution table entries.

Since I'm too stupid to do anything useful, I tried rigging up a test that iterates over all possible nextlps / nextmps entries for each table entry, trying all 53 possible values. No pattern seems to allow 2AE432-09 to decompress properly. I'm currently trying this with all 256 possible prob tests, as well as all all possible nextlps / nextmps values. About 20% done with no matches.

Obviously, there are caveats with brute forcing. I can't test moving around the toggle due to complexity, and I can't test modifying more than one evolution table entry at a time, again due to complexity. The tests would never finish. But we'd be really, really unlucky to be hitting multiple table errors in this file, yet still managing to complete decompression on ~80% of the other data, no?

Perhaps try running 2AE432-09.compressed through your FIFO cart? Does the data match caitsith2's test data, or your decompressor data, then?

EDIT:

Code: Select all

    for(unsigned tbl = 0; tbl < 53; tbl++) { printf("table = %d\n", tbl);
    for(unsigned a = 0; a < 256; a++) { printf("%0.2x  ", a);
    for(unsigned b = 0; b <  54; b++) {
    for(unsigned c = 0; c <  54; c++) {
      memcpy(&EvolutionTable, &EvolutionTableBase, sizeof(EvolutionTableBase));
      EvolutionTable[tbl][0] = a;
      EvolutionTable[tbl][1] = b;
      EvolutionTable[tbl][2] = c;

... no matches.

neviksti · Post by **neviksti** » Fri Jul 11, 2008 1:43 pm

Caitsith2,
I have no working FEoEZ cart (I accidentally rendered one cart unusable when trying to make my FIFO mod... good thing I bought a spare). Redumping some of the data is much easier with the old "use the original cartridge and .loc file" setup. Since you're the only one with a working cart as well as a stable copier, could you try redumping some of those files? Definitely start with 2AE432-09.compressed

If you're busy that's all right, as I can do it with the FIFO mod'ed cart, it'll just take longer.

neviksti · Post by **neviksti** » Fri Jul 11, 2008 1:58 pm

I found what was causing the majority of problems.

Here's some example output which should clarify the situation

Code: Select all

...
Read 994 bytes from [feoez-shounen/00/0981DF-00-00.compressed]
Read 2048 bytes from [feoez-shounen/00/0981DF-00-00.uncompressed]
Used 1007 bytes of input.
byte 1529: decomp[4C]->real[49]
byte 1531: decomp[4C]->real[49]
byte 1533: decomp[4C]->real[49]
byte 1534: decomp[CC]->real[FC]
byte 1535: decomp[4C]->real[39]
byte 1536: decomp[CC]->real[F4]
byte 1537: decomp[4C]->real[39]
byte 1538: decomp[CC]->real[F4]
byte 1539: decomp[4C]->real[38]
byte 1540: decomp[CC]->real[F4]
byte 1541: decomp[4C]->real[38]
****FAIL**** mismatch detected
Read 651 bytes from [feoez-shounen/00/0981DF-01-00.compressed]
Read 2048 bytes from [feoez-shounen/00/0981DF-01-00.uncompressed]
Used 671 bytes of input.
byte 924: decomp[72]->real[F2]
byte 925: decomp[35]->real[D5]
byte 926: decomp[72]->real[F3]
byte 927: decomp[35]->real[C5]
byte 928: decomp[72]->real[F3]
byte 929: decomp[35]->real[C5]
byte 930: decomp[72]->real[73]
byte 931: decomp[35]->real[C5]
byte 932: decomp[72]->real[73]
byte 933: decomp[35]->real[C5]
byte 934: decomp[72]->real[73]
****FAIL**** mismatch detected
Read 1290 bytes from [feoez-shounen/00/0981DF-02-00.compressed]
Read 2048 bytes from [feoez-shounen/00/0981DF-02-00.uncompressed]
Used 1302 bytes of input.
byte 1851: decomp[15]->real[45]
byte 1853: decomp[15]->real[45]
byte 1855: decomp[15]->real[55]
byte 1857: decomp[15]->real[55]
byte 1858: decomp[6E]->real[3E]
byte 1859: decomp[15]->real[6F]
byte 1860: decomp[6E]->real[34]
byte 1861: decomp[15]->real[6F]
byte 1862: decomp[6E]->real[34]
byte 1863: decomp[15]->real[63]
byte 1864: decomp[6E]->real[37]
****FAIL**** mismatch detected
Read 766 bytes from [feoez-shounen/00/0981DF-03-00.compressed]
Read 2048 bytes from [feoez-shounen/00/0981DF-03-00.uncompressed]
Used 787 bytes of input.
byte 1078: decomp[00]->real[01]
byte 1079: decomp[30]->real[3C]
byte 1080: decomp[00]->real[01]
byte 1081: decomp[30]->real[3C]
byte 1082: decomp[00]->real[01]
byte 1083: decomp[30]->real[3C]
byte 1084: decomp[00]->real[01]
byte 1085: decomp[30]->real[6C]
byte 1086: decomp[00]->real[06]
byte 1087: decomp[30]->real[6C]
byte 1088: decomp[00]->real[06]
****FAIL**** mismatch detected
...

Yep. The .compressed files are sometimes under-dumped.

caitsith2 · Post by **caitsith2** » Fri Jul 11, 2008 2:00 pm

Do you think you could port your decompressor to the snes, then I could specify locations and sizes, and have the decompression compared to real hardware right then and there. This could potentially work for the FIFO cart as well.

neviksti · Post by **neviksti** » Fri Jul 11, 2008 3:35 pm

Wow, do I have some strange luck or what?
I only chose literally a couple files to focus on when I was trying to figure out what was wrong with my evolution table last night. It appears that probably the only actual bad decompression-dump is the confusing 2AE432-09.compressed file.

All other mismatches for 00 decompression (I checked the data supplied for all three games) can be explained by underdumps of the .uncompressed file.

I believe it is a bad dump since, as explained, running the prob calculator on the real hardware matched my code. And because only that one byte in the data doesn't match. If this was truely a decompressor problem, and the states were wrong, there should be no real recovery from a mistake.

Here's an output listing ALL mismatches

Code: Select all

Read 186 bytes from [feoez/00/2AE432-09.compressed]
Read 406 bytes from [feoez/00/2AE432-09.uncompressed]
byte 18: decomp[7E]->real[72]
****FAIL**** mismatch detected

It is really just one byte.

caitsith2 wrote:Do you think you could port your decompressor to the snes, then I could specify locations and sizes, and have the decompression compared to real hardware right then and there. This could potentially work for the FIFO cart as well.

That's a possibility, and could be useful in the future.
At the moment though, since it looks like only one file actually needs to be redumped, it doesn't seem worth it. I'd prefer to focus my time on starting to play with the mode 01 (or 02?) data.

I'll start by running some prob calculations for mode 1 and 2. (hopefully the evolution is the same and only the mps prediction changes)

In the mean time, can you redump that one file using the .loc code?

And to delegate a bit, can someone else write a little program to grab data out of the roms for the two FEoEZ games in order to make all the .compressed files have more data (say prehaps, the same length as the .uncompressed files as that should be more than enough data) and run the decomp tests again with the new data? It would be comforting to know we truely match all the data in the "graphics packs".