SPC7110 Reverse Engineering Project

[neviksti]

Bleh, I tried an all $FF's test and it failed miserably. I'll try to fix this up, so I'll be up a little longer tonight.

If you post a binary file you want me to use, I'll run that once everything is working correctly.

[kammedo]

So... how are we supposed to make new tests? Should i pass you a binary file with the desired 256 bytes?

At this point, i'm only interested in making some statistical analysis, so a random input (50%-50% distribution for 0's and 1's) would be fine for me.


EDITED: Ummm, i changed my mind: a 70%-30% distribution would be better.

How about a
000000
000001
000002
.
.
etc
test first?

[neviksti]

I'm too tired to debug effectively right now.
I updated the file:
http://neviksti.com/SPC7110/testcode.asm

Can someone please look over the code and give it a sanity check?
Here's the output I'm getting for all FF's as the input file.
http://neviksti.com/SPC7110/outputFFFF.bin

Code: Select all

5A 5A 5A 5A 5A 5A 5A 5A 
A5 A5 A5 A5 A5 A5 A5 A5 
25 DA DA DA 09 DA AD AD 
17 A5 DA 93 2B A1 A5 A5
...

Check out that bizarre 09 case. Also notice the prob=2D cases.

These can be easily explained if there was supposed to be an extra shift (so the prob values are actually $08.8 *2 ==> $11 and $2D *2 ==> $5A).

But I can't find the error in the code at the moment. With plenty of debug output, the program seems to be working okay, and span > $80 ... so it is not clear how another shift would even be allowed.

--------------------
EDIT: Doh! Found a stupid little error. But there is still something else wrong.
(Updated files again)

Code: Select all

5A 5A 5A 5A 5A 5A 5A 5A 
A5 A5 A5 A5 A5 A5 A5 A5 
25 DA DA DA 11 DA DA DA 
5A A5 DA A5 2C A5 A5 A5
BF A5 A5 A5 3A A5 91 A5
...

What the heck is the 2C now?
And then things get screwy after that (3F, 3A, etc.)

Maybe it will make more sense after some sleep. That's all for now.

[Andreas Naive]

5A 5A 5A 5A 5A 5A 5A 5A
A5 A5 A5 A5 A5 A5 A5 A5
25 DA DA DA 11 DA DA DA
5A A5 DA A5 2C A5 A5 A5
BF A5 A5 A5 3A A5 91 A5
...

Yes! That's it. There are no errors.
You definitively want to take a look at the evolution table of the 16-bits QM-coder. (You have it, by example, in page 31 of the ITU recommendation that jolly_codger posted above)

0 5a1d 1 1
1 2586 14 2
2 1114 16 3
3 080b 18 4
....
14 5a7f 15 15
15 3f25 36 16
16 2cf2 38 17
...
till index 112.

So this is definitively a 8-bits version of the QM-coder. If we had previously only observed the 0x5a, 0x25, etc, values, is because they are the "initial state" values of the evolution table (if you take a look at the evolution table of the 15-bits version, you will see states 0 to 8 can only be reached at the start of the evolution.) Then, if you only find MPS, you will evolve through those initial state values but, when reaching the first LPS, the wild word awaits for you.

Now i wonder how many states will have our evolution table; it can not have the 113 values of the 16 bits version, as some values in that table are less than 0x0100 (till reaching 0x0001 indeed) so you cannot convert that table to 8 bit just by masking off the low byte.

Well, i have to say i'm in a better state of mind now. I was wondering how the hell they could use a so discretizated set of values. This now makes much more sense...

[Andreas Naive]

Here you have my first test:

http://andreasnaive.en.eresmas.com/SPC7 ... 30_an1.bin

[Andreas Naive]

I'm seeing it... I'm seeing how it evolves.
As this seems just a version of the 16-bits one, i though it would be enough to take that as initial point and start to make changes. Though i know some values (the ones 0x0100) should be erased from the table, to maintain the order and make things easier to follow, i will retain 113 values.

Now, look at bitplane #4 in neviksti's outputffff.bin. The evolution goes this way:
index 0(5A) + LPS -> 1 with change of MPS
index 1(25) + MPS -> 2 with change of MPS (i don't understand why the change of MPS here, as that should only happen after a LPS, so i suppose the surrounding pixels have an effect on this)
2(11) + LPS -> 16
16(2C) + LPS -> 38
38(3A) + LPS -> 65
65(4D) + LPS -> 95 (this differs from the 16 bits version, so i change the state 65 to reflect this)
95(56) + LPS -> 95 with change of MPS
95(56) + MPS -> 96
96(4F) + MPS -> 97
97(47) + MPS -> 98
98(41) + MPS -> 99
99(3C) + MPS -> 100
100(37) + MPS -> 84 (this differs from the 16 bits version, so i change the state 100 to reflect this)
84(34) + MPS -> 85
85(2E) + MPS -> 86
86(29) + MPS -> 87
87(25) + MPS -> 41 (this differs from the 16 bits version, so i change the state 87 to reflect this)
41(1F) + MPS -> 42
42(19) + MPS -> 43
43(15) + MPS -> 44
44(11) + MPS -> 45
45(0E) + MPS -> 46
46(0B) + MPS -> 47
47(09) + MPS -> 48
48(08 ) + MPS -> 49
49(07) + MPS -> 50
50(05) + MPS -> 51
51(04) + MPS -> 52
52(03) + MPS -> I lack data to know this.

Do you see it? In this way, by studying bitplanes #0 and #4, i guess we will be able to reproduce the full evolution table after just studying some examples. Now i have to leave or my wife will kill me. Have fun.

[Andreas Naive]

I'm back. As i was in a hurry in my last post, i didn't included this: i had converted the 16-bits QM table to 8 bits (simply by getting the 8 higher bits of every value). I will post it here (this is before doing any modification as i commented before) for the shake of using common terminology. As said, while there are values that obviously won't be used (as they are 0), i prefer to maintain the same ordering than the original at this point. We always can simplify it when all be understood.

Code: Select all

struct evolution_node
{
    uint8 Qe;
    uint8 nextLps;
    uint8 nextMps;
    uint8 mpsExch;
};

struct evolution_node evolution_table[] = {
{0x5a,  1,  1,1},  //0
{0x25, 14,  2,0},  //1
{0x11, 16,  3,0},  //2
{0x08, 18,  4,0},  //3
{0x03, 20,  5,0},  //4
{0x01, 23,  6,0},  //5
{0x00, 25,  7,0},  //6
{0x00, 28,  8,0},  //7
{0x00, 30,  9,0},  //8
{0x00, 33, 10,0},  //9
{0x00, 35, 11,0},  //10
{0x00,  9, 12,0},  //11
{0x00, 10, 13,0},  //12
{0x00, 12, 14,0},  //13
{0x5a, 15, 15,1},  //14
{0x3f, 36, 16,0},  //15
{0x2c, 38, 17,0},  //16
{0x20, 39, 18,0},  //17
{0x17, 40, 19,0},  //18
{0x11, 42, 20,0},  //19
{0x0c, 43, 21,0},  //20
{0x09, 45, 22,0},  //21
{0x07, 46, 23,0},  //22
{0x05, 48, 24,0},  //23
{0x04, 49, 25,0},  //24
{0x03, 51, 26,0},  //25
{0x02, 52, 27,0},  //26
{0x01, 54, 28,0},  //27
{0x01, 56, 29,0},  //28
{0x00, 57, 30,0},  //29
{0x00, 59, 31,0},  //30
{0x00, 60, 32,0},  //31
{0x00, 62, 33,0},  //32
{0x00, 63, 34,0},  //33
{0x00, 32, 35,0},  //34
{0x00, 33,  9,0},  //35
{0x5a, 37, 37,1},  //36
{0x48, 64, 38,0},  //37
{0x3a, 65, 39,0},  //38
{0x2e, 67, 40,0},  //39
{0x26, 68, 41,0},  //40
{0x1f, 69, 42,0},  //41
{0x19, 70, 43,0},  //42
{0x15, 72, 44,0},  //43
{0x11, 73, 45,0},  //44
{0x0e, 74, 46,0},  //45
{0x0b, 75, 47,0},  //46
{0x09, 77, 48,0},  //47
{0x08, 78, 49,0},  //48
{0x07, 79, 50,0},  //49
{0x05, 48, 51,0},  //50
{0x04, 50, 52,0},  //51
{0x04, 50, 53,0},  //52
{0x03, 51, 54,0},  //53
{0x02, 52, 55,0},  //54
{0x02, 53, 56,0},  //55
{0x01, 54, 57,0},  //56
{0x01, 55, 58,0},  //57
{0x01, 56, 59,0},  //58
{0x01, 57, 60,0},  //59
{0x00, 58, 61,0},  //60
{0x00, 59, 62,0},  //61
{0x00, 61, 63,0},  //62
{0x00, 61, 32,0},  //63
{0x5b, 65, 65,1},  //64
{0x4d, 80, 66,0},  //65
{0x41, 81, 67,0},  //66
{0x37, 82, 68,0},  //67
{0x2f, 83, 69,0},  //68
{0x29, 84, 70,0},  //69
{0x23, 86, 71,0},  //70
{0x1e, 87, 72,0},  //71
{0x1a, 87, 73,0},  //72
{0x17, 72, 74,0},  //73
{0x14, 72, 75,0},  //74
{0x11, 74, 76,0},  //75
{0x0f, 74, 77,0},  //76
{0x0d, 75, 78,0},  //77
{0x0b, 77, 79,0},  //78
{0x0a, 77, 48,0},  //79
{0x58, 80, 81,1},  //80
{0x4d, 88, 82,0},  //81
{0x43, 89, 83,0},  //82
{0x3b, 90, 84,0},  //83
{0x34, 91, 85,0},  //84
{0x2e, 92, 86,0},  //85
{0x29, 93, 87,0},  //86
{0x25, 86, 71,0},  //87
{0x55, 88, 89,1},  //88
{0x4c, 95, 90,0},  //89
{0x44, 96, 91,0},  //90
{0x3e, 97, 92,0},  //91
{0x38, 99, 93,0},  //92
{0x32, 99, 94,0},  //93
{0x2e, 93, 86,0},  //94
{0x56, 95, 96,1},  //95
{0x4f,101, 97,0},  //96
{0x47,102, 98,0},  //97
{0x41,103, 99,0},  //98
{0x3c,104,100,0},  //99
{0x37, 99, 93,0},  //100
{0x52,105,102,0},  //101
{0x4c,106,103,0},  //102
{0x46,107,104,0},  //103
{0x41,103, 99,0},  //104
{0x56,105,106,1},  //105
{0x50,108,107,0},  //106
{0x4b,109,103,0},  //107
{0x55,110,109,0},  //108
{0x50,111,107,0},  //109
{0x5a,110,111,1},  //110
{0x55,112,109,0},  //111
{0x59,112,111,1},  //112
};

The suggested modifications to this table, by now, are:
65+LPS->95
100+MPS->84
87+MPS->41

EDITED:
Bitplane #0 in the "all 1's" example can be understood without further changes. However, the same change of MPS unrelated to the evolution appear when passing from the 2nd to the 3rd bit (in this case it's more clear that it's independent from the evolution, as there is no renormalization at that point.). The states it use are: 0-1-14 and all the way down to 25.

It seems that 0x100 bytes are a little too few bytes to follow even this to the end (it doesn't reach the saturation state) so maybe it could be worthwhile to bigger that limit if possible.

Now it's late and i'm tired, so i will just stop here. A last observation, however: in bitplane #1 it's clear how at least 2 different contexts are being used.

[neviksti]

Here you have my first test:

http://andreasnaive.en.eresmas.com/SPC7 ... 30_an1.bin

I appear to still have a problem in my code (or there is something else weird going on here). I run your input and the program quits on bit 4F, saying "ERROR: Prob overflow". You can see in the code where this occurs, it is when the tested Prob reaches $80, it stops.

Here's the pertinent output:

Code: Select all

5A 5A 5A 5A 5A 5A 5A 5A 
A5 A5 5A 5A A5 5A 5A 5A 
25 DA 5A DA 5A A5 DA 5A 
5A DA 25 A5 3F 5A 25 25 
3F BF A5 5A AC 25 A5 DA 
BF 25 A5 5A 3A 25 DA 25 
DA A5 5A DA 4D BF 11 A5 
48 DA A5 A5 C3 BF 08 5A 
3A 3F 25 DA 3B 2C A5 5A 
3A DA A5 DA B4 3A 08 FF
... code crash

It seems that 0x100 bytes are a little too few bytes to follow even this to the end (it doesn't reach the saturation state) so maybe it could be worthwhile to bigger that limit if possible.

I can add a check in the code that the compressed data offset never goes past $400. Then you can use larger files without problems, as it will safely halt if it runs out of room. Please limit the input files to $300 bytes though if you can, as this makes everything fit in memory easier.

If need be I can enlarge the buffer sizes, but please realize that as is, when the prob is ~ $5A, the SNES already takes about 15 seconds per byte (roughly an hour for $100 bytes of input). Most of this time is dealing with transferring the large compressed data buffer, increasing it 2 fold will increase the time roughly 2 fold. There's nothing wrong with a test taking several hours. I just want everyone to understand why I hesitate to increase that buffer length.

Of course we need to figure out the other problem first before the code is useable anyway...

EDIT:
Found the error. Amazingly that particular case was never reached before, and a mistake with the accumulator state incorrectly let everything through a particular if statement.

Code on website is now updated,
will upload output when it finishes running.

[jolly_codger]

What if the MPS interval < LPS interval some time before the span collapse? Then we'd have to exchange the two comparison codes (maybe this can never happen though).

(Update read)
Oops. Never mind.

[neviksti]

Alright, here's the output.
http://neviksti.com/SPC7110/output_7030_an1.bin

EDIT:
Just in the off chance there were any problems with the setup, I ran the test again. It just finished and the results were exactly the same.

Yeah! Now I get to relax and read those documents you suggested.

[neviksti]

I'm almost positive the bitplanes use the previous 16th bit as part of the context.

all $FF's for half the file, one nibble of 0, then the remaining as $FF
Here's the files:
http://neviksti.com/SPC7110/inputFFFF0FFF.bin
http://neviksti.com/SPC7110/outputFFFF0FFF.bin

Code: Select all

by the $80'th byte, the mps/prob have evolved to:
85 81 81 81 84 81 81 81 
...
then the 0 nibble hits:
85 11 25 25 84 81 81 81 
88 81 81 81 84 81 81 81
08 91 91 A5 84 81 81 81 
8B 81 81 81 84 81 81 81 
8B 81 81 81 84 81 81 81 
8B 81 81 81 84 81 81 81

EDIT:
At this point I think the contexts are:

bitplanes1-3,5-7
previous 16th bit and preceding bits in the current nibble

bitplanes0,4
these bitplanes have two "contexts" (the previous 16th bit) which each track the current mps BUT only 1 prob state each. They also seem to change the mps "immediately".

We're so close...

EDIT(2):
Looking at the FF...FF0F...FF file, mps update for bitplanes0,4 does seem to wait for the "switch" parameter in the table. But when a switch occurs, it updates BOTH stored mps for that particular bitplane (and updates it to the actual bits each context saw last ... ie. the current bit and the 16th previous bit).

EDIT(3):
Bleh, there are examples where the mps update is more complicated. Still not sure about this.

[neviksti]

Because bitplane0 seems to only have one saved probability state, this makes it easy to use to try to map out the probability evolution table. I did many runs, and while I haven't seen every possible transition, I have seen a large majority. (Although I haven't checked this with Andreas' run yet.)

Here's what I believe to be the table (using the notation from above):

Code: Select all

{0x5a,  1,  1,1},  //0   l,m
{0x25,  6,  2,0},  //1   l,m
{0x11,  8,  3,0},  //2   l,m
{0x08, 10,  4,0},  //3    ,m
{0x03, 12,  5,0},  //4    ,m
{0x01, 15,  5,0},  //5    ,m


{0x5a,  7,  7,1},  //6   l, 
{0x3f, 19,  8,0},  //7   l,m
{0x2c, 21,  9,0},  //8   l,m
{0x20, 22, 10,0},  //9    ,m
{0x17, 23, 11,0},  //10   ,m
{0x11, 25, 12,0},  //11   ,m
{0x0c, 26, 13,0},  //12   ,m
{0x09, 28, 14,0},  //13   ,m
{0x07, 29, 15,0},  //14   ,m
{0x05, 31, 16,0},  //15   ,m
{0x04, 32, 17,0},  //16   ,m
{0x03, 34, 18,0},  //17   ,m
{0x02, 35,  5,0},  //18   ,m


{0x5a, 20, 20,1},  //19  l,m 
{0x48, 39, 21,0},  //20  l,m
{0x3a, 40, 22,0},  //21  l,m
{0x2e, 42, 23,0},  //22  l,m
{0x26, 44, 24,0},  //23  l,m
{0x1f, 45, 25,0},  //24  l,m
{0x19, 46, 26,0},  //25  l,m
{0x15, 25, 27,0},  //26  l,m
{0x11, 26, 28,0},  //27  l,m
{0x0e, 26, 29,0},  //28  l,m
{0x0b, 27, 30,0},  //29   ,m
{0x09, 28, 31,0},  //30   ,m
{0x08, 29, 32,0},  //31  l,m
{0x07, 31, 33,0},  //32  l,m
{0x05, 32, 34,0},  //33   ,m
{0x04, 33, 35,0},  //34   ,m    ... this is NOT skipped
{0x04, 33, 36,0},  //35   ,m
{0x03, 34, 37,0},  //36   ,m
{0x02, 35, 38,0},  //37   ,m    ... this is NOT skipped
{0x02, 36,  5,0},  //38   ,m


{0x58, 39, 40,1},  //39  l,m
{0x4d, 47, 41,0},  //40   ,m
{0x43, 48, 42,0},  //41   ,m
{0x3b, 49, 43,0},  //42   ,m
{0x34, 50, 44,0},  //43  l,m
{0x2e, 51, 45,0},  //44  l,m
{0x29, 44, 46,0},  //45  l,m
{0x25, 45, 24,0},  //46   ,m


{0x56, 47, 48,1},  //47  l,m
{0x4f, 47, 49,0},  //48  l,m
{0x47, 48, 50,0},  //49  l,m
{0x41, 49, 51,0},  //50  l,m
{0x3c, 50, 52,0},  //51  l,m
{0x37, 51, 43,0},  //52   ,m

The l,m are just remarks about whether I've seen data which shows the lps or mps path at that point. A lot of the unchecked stuff looked like it would match perfectly with the implied values from the q-coder document.

The last entry "mps switch", is just a left over from the original table... I didn't check it, and this doesn't seem to be how the mps evolves anyway.



If someone can write a program to give me data to verify this table completely, that would be great. At the moment though, I'm tired (its 6am) and I'm going to bed.

Here's something to scratch your head at though.

Code: Select all

all 80's the prob values converge to:
01 01 01 01 01 01 01 01 
...

then abruptly change to all 00's, the prob values do this:
01 11 25 25 01 01 01 01 
05 08 25 25 01 01 01 01 
08 01 01 01 01 01 01 01 
08 01 01 01 01 01 01 01 
08 01 01 01 01 01 01 01 
08 01 01 01 01 01 01 01 
08 01 01 01 01 01 01 01
07 01 01 01 01 01 01 01
07 01 01 01 01 01 01 01

What in the world? Somehow the bit0 context only matters for 2 bytes... then the probabilities go back to what they were. VERY strange, but probably an important clue.

Maybe it only matters if bits in the context were an MPS or LPS, and not necessarily its actual value?

Good luck everyone and goodnight.

EDIT: Had typos in the table. Should be fixed now.

EDIT: Doh! I meant it changed from all $80's (not $FF's) to all $00's in example above.

[jolly_codger]

There's some odd things happening.
Began running a PROB checker and this came up.

output_7030_an1.bin

bitplane 5:
[00] 5A -> 5A [0,-,*]
[00] 5A -> 25 [1,L,*]
[01] 25 -> 5A [0,L,-]
ERROR = 1D
[14] 5A -> 25 [0]


Real pattern:
[00] 5A -> 5A
[00] 5A -> 25
[01] 25 -> 5A
[??] 5A -> 25
[??] 25 -> 25

---------------

[15] 3F -> 3F [1,-,-]
[15] 3F -> 2C [0,M,-]
[16] 2C -> 3A [0,L,-]
[38] 3A -> 2E [0,M,-]
[39] 2E -> 26 [1,M,-]
[40] 26 -> 1F [1,M,-]
[41] 1F -> 29 [0,L,-]
[69] 29 -> 29 [1,-,-]
ERROR = 75
[69] 29 -> 25 [0]

NOTE: 41 -> 86

That gets:
[40] 26 -> 1F [1,M,-]
[41] 1F -> 29 [0,L,-]
[86] 29 -> 29 [1,-,-]
[86] 29 -> 25 [0,M,-]
[87] 25 -> 5A [1,?,-]
[??] 5A (1) [#]
[??] 29 (0)
[15] 3F (1)
[??] 29 (1)
[??] 2E (1)
[99] 3C (1)
[104] 41 (1) [# No path to 97]
[97] 47 (1)


The [??] don't follow any visible way.
There's lots of state hops.

Going to try some other paths.

============
============

UPDATE:
Actually there is something odd.

If we take this:
{0x3a, 65, 39,0}, //38 (L), Original

Then this happens:
//{0x4d, 80, 66,0}, //65, Original
{0x4d, 95, 66,0}, //65 (x -> 56[95] )
{0x4d, 82, 66,0}, //65 (x -> 43[82] )


Else if we try this:
{0x3a, 81, 39,0}, //38 (L)

Then this occurs:
{0x4d, 88, 82,0}, //81, Original
{0x4d, 95, 82,0}, //81


Maybe that nybble patent needs another reading. :squeezes head:

[Andreas Naive]

OK. It's clear now how the MPS thing evolves for bitplanes #0 and #4. What is happening is this: we have a normal QM-coder tracking a "mps" value, which i will better call "prediction change" and a prediction table acting on the previous bits. In code:

Code: Select all

    const uint8 mpsPrediction[4] = {0,0,1,1};
    uint8 predChange=0;

To all effects, predChange is the value tracked by the QM-coder, while the prediction table is fixed and is used with the previous bits for the bitplane. That way, if a MPS event occur, mpsPrediction[lastBits&3]^predChange is outputted, while if a LPS event occur, mpsPrediction[lastBits&3]^predChange^1 is outputted. As simple as that.

EDITED:
jolly_codger,
Unless i be misunderstanding you, i believe you are missing the point here. bitplane #5 is clearly not composed of one only context, so you cannot expect to see only one evolution, but (at least) two evolutions interweaved.

[Andreas Naive]

I have figured out how the 2 contexts of bitplane #5 are selected.

It is decided when outputting the previous bit (i mean, the last bit from the bitplane #4) in the following way:
When, in bitplane #4, the 'predChange' variable is 0 and we are outputting a LPS, a certain context will be selected for bitplane #5. In other case, the other one will be selected. (So the context selected only depends on the evolution of the context of bitplane #4).

By separating the Qe's for bitplane #5 in output_7030_an1.bin in two groups using this method, i get:

Code: Select all

		5a
5a
25
5a
		25
		25
3f
3f
2c
3a
2e
26
1f
29
29
		25
		5a
29
		3f
29
2e
3c
41
47
		5a
4f
56
56
56
56
56
56
		48
4f
47
4f
		58
47
		4d
4f
56
56
56
56
56
		43
4f
		3b
47
41
47
4f
		47
		4f
		56
		56
		56
4f
56
56
		47
41
56
3c
4f
		41
47
56
4f
4f
56
4f
		56
47
		4f
4f
47
4f
		56
47
		56
4f
56
		56
		4f
56
		47
4f
		4f
		56
47
41
		4f
47
		47
4f
		41
47
		47
41
41
47
		41
		3c
41
		37
47
4f
47
4f
		34
		41
		41
		3c
47
4f
47
47
4f
56
56
56
		37
4f
		34
56
56
56
		2e
4f
		3c
		41
47
		3c
		37
4f
		3c
		41
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
		47
47
		4f
41
47
4f
		56
47
		4f
		56
4f
		4f
56
56
56
		56
		4f
		56
		56
4f
47
4f
41
56
47
4f
56
56
4f
47
41
56
47
56
4f
56
56
56
56
4f
56
4f
56
56
56
56
56
4f
47
		56
		4f
47
		47
4f
56
56
56
56
56
4f
47
41
41
		41
3c
		47
		47
41
		41
41
47
		47
41
		4f
41
		56
		4f
		47
41
3c
3c
41
37
34
		47
2e
		4f
29

where the evolution of the 2 contexts can be seen. Time for sleeping.