SPC7110 Reverse Engineering Project

Discussion of hardware and software development for Super NES and Super Famicom.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Wed Jul 16, 2008 4:26 am

Andreas Naive wrote:Exactly. I'm not only suggesting it. It is clearly described in IBM's documents.
The representation for 1 is 0xaaaaaaaaa... If they use 0x5a instead 0x 0x55 (as an aproximation to 0x55555555...) is because they applied a probability estimation technique over real data based on Markov chain to adjust those values.
Sorry, I really didn't know.
Thanks for taking the time to explain.
;---------------------


Well I'm giving up on the data for tonight...
I really am stumped here. The fifth pixel has all reference pixels as 00. The second pixel had this same exact reference data, and while an lps occurred in that pixel, the .invert of the context was not changed. Yet the order of predicted values changes heavily for these pixels.

Even if we let it update the order when the .invert of the context was not changed, it moves the last obtained pixel value for this context DOWN in probability to be the least likely of all values in the table. Not only that, at this point in decompression that pixel value is actually the most frequent value of all.

What is going on?
Not only does it not makes sense at the moment, it seems to be doing the exact opposite of what it should if it wants to do any compression.

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Wed Jul 16, 2008 3:07 pm

I'm starting to see the light...

The reference pixels are clearly related to the selected ordering for the 4 pixel values. I have found some remarkable regularities (indeed, for one of the 10 contexts i think i'm able to predict the content of one of the positions of the ordering), but most refer to only one context and need further study. (I'm very tired now, so i could easily have made errors).

However, to proof the fact that the reference pixels are essential here, i will comment which is probably the most significative fact i have found:

for the 6 (3*2) contexts corresponding to the cases where 2 of the reference pixels are equal and the third one is distinct, those two values are ALWAYS selected by the same first symbol. I mean, or they are selected with MPS/MPS and MPS/LPS or they are selected with LPS/MPS and LPS/LPS. I have checked this for all the file.

As said, i have found some other "second order" regularities but, as they refer to specific contexts and i should check them more exhaustively, i will just stop here today. I'm exhausted.

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Thu Jul 17, 2008 3:39 am

I took another look at the patent, and it seems i had missed the discussion about the "color rank". It says the rearrangement of the color order is "flexible through the learning of the ocurrence probability of each color". In the embodiment it describe, it's simlply putting the last generated pixel in the top of the rank and shifting the other values 1 unit.

Of course, that is not what we have here, but maybe that is what is done instead of with the last pixel with the reference pixels (i'm guessing in some cases those values could be put at top of the rank and in others at bottom). Furthermore, i have suddenly make sense of why they aren't using the pixel to the left as reference pixel: by using the second one, they can know two contexts in advance so, while a pixel is being calculated/outputted, the color rank for the next one is probably being generated... Hardware parallelization, that is the explanation for that.

neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Thu Jul 17, 2008 5:01 am

Yeah, I need to go back and read the patent again myself. I keep meaning to, but it was so boring the first time through and their repeated generic phrases were confusing me about whether I missed something or they were just saying "junk" to make the patent have wider coverage.

Okay, some more data:
Here's what the input file looks like
00 00 00 00
7F FF FF FF
80 00 00 00
FF FF FF FF
00 00 00 00
7F FF FF FF
80 00 00 00
FF FF FF FF

Here's the output:
http://neviksti.com/SPC7110/output1_0F0F.dat2

My first impression is that it looks like the table of "likely pixel values" doesn't rearrange unless an LPS is received when .invert of the context can change.

I still think the 5th pixel in output1_7030_an1.dat2 is a very very important clue. The reference pixels are exactly the same as for the second pixel, and while no .invert change occured on that pixel, the pixel order still changed for the 5th pixel.

So it appears that the "pixel likelyhood order" is shared between contexts. Further more, it is shared between different "reference pixel" data. The details of this second "sharing" is making it very difficult to figure out how it evolves. We need a more appropriate set of test data for this. I'll try to put something together.


Oh, and to try to convince myself beyond a doubt that the "pixel likelyhood order" is not based on the current state, but on the history of all the data, I tried the following:
make a table which stores the "pixel likelyhood order" for each case of (previous pixel data, previous 2nd pixel data, previous 8th pixel data, previous 9th pixel data, .invert for first symbol context and .invert bit the two possible contexts of the second symbol, and which "Bell number" the reference pixel data gave us)
Even with all that, it easily found many (_many_) cases where all those things were the same for a given pixel yet the "pixel likelyhood order" is different. I am pretty darn convinced now that the history matters.

EDIT: In case I forgot to mention this earlier, if you are making a test case, because I need to see the transitions of _both_ pixel bits while stepping though the prob values, if the probability for the first symbol ever reaches 1, the program will screw up. This of course hasn't been a problem yet, and since we don't care about the probability values now anyway, just remember to not have long sequences of repeated pixel values.

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Thu Jul 17, 2008 5:41 am

previous pixel data, previous 2nd pixel data, previous 8th pixel data, previous 9th pixel data
Why haven't you included the 7th pixel? From the point of view of the drawings, it has the same importance than the 9th.

neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Thu Jul 17, 2008 4:14 pm

Andreas Naive wrote:
previous pixel data, previous 2nd pixel data, previous 8th pixel data, previous 9th pixel data
Why haven't you included the 7th pixel? From the point of view of the drawings, it has the same importance than the 9th.
I tried that now, and same thing.
Actually, I was a bit quick to judge since there were so many "mismatches". On closer inspection, this works fine for the a!=b!=c!=a case.

So all four entries in the "pixel likelyhood order" table are predictable for that case. As you mentioned, two entries in that table are always predictable for the "two reference pixels are the same" case. The other entries require some kind of history data.

I keep "seeing" patterns. Maybe I'm close, but it's probably a sign I'm just too tired to think straight. I'll give it a bit more today and get some rest.

neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Thu Jul 17, 2008 4:45 pm

Okay, I can follow the "pixel likelyhood order" evolution now. So everything for mode 1 should be done. I'll write up a test decompressor now. The idea turns out to be fairly simple (but kind of hard to describe precisely, so it will be best to just read the code). Due to this simplicity I have a feeling we can just guess mode 2 on the first try after this.

One thing at a time though.

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Thu Jul 17, 2008 4:48 pm

OK. I *believe* i have figured it out. Please take into account i'm even more tired than yesterday, and i haven't had time to test exhaustively this, but it seems to work for all the data i have tried (though, as i say, i haven't driven any automatic validation, and i bet i'm not in the best conditions to do this today...)

But, if i'm right, it works this way.

It's storing internally a rank ordering, which start with {00,01,10,11}

Then, for every pixel (independently of the context), you take the three reference bits (B9,B8 & B2) and do the following:

- In that rank, take B9 and put it in the first position, shifting the other values if needed.
-Then, take B8 and put it in the first position, shifting the other values if needed.
-Finally, take B2 and put it in the first position, shifting the other values if needed.

The result is the new rank order you are going to use to output the current pixel. But the point is that the index to use in that table is not given by the MPS-LPS symbols, but for the "output" of the decoders (i mean, the symbols after XORing them with the "invert" thing).

And, if i haven't missed anything... that's all.

Random comments:
1) At this point, seeing how type 0 and type 1 seems to work, i'm guessing that the context manager of the chip hasn't access, indeed, to the individual MPS/LPS symbols, but probably only to the XORing with the "invert" values (as that is to be considered the "output" of the decoder as an independent part of the hardware).

2) In case you don't see why it's reasonable to use the output of the decoder instead of the MPS-LPS symbols (after all, as the rank is supposed to be ordered in most probable to less probable order, isn't it obvious that the MPS/MPS to LPS/LPS range should be used as index? Well, not.): What they are doing is to use a predictor to take adventage of the structure of the plain data. So, if you are going to compress data with a structure like you are expecting in your prediction model (in our case, 8*8 tiles with 2 bit depth), the prediction model will convert the original probability distribution into a distribution with a "natural" ordering (in our case, after using the prediction model, you expect that the most frequent data is 00, then 01, then 10, etc). So, as you have now data whose frequency is ordered following the natural order, you can use a encoder to code it and, when decoding that same data, the result outputted by the decoder will be ordered in a "natural" way going from higher probabilities to lower ones. That's why it's reasonable to use that output from the decoder as the index to the table. ;) Well, i expect not to confuse you more. :P

If i have made any errors, i will check it tomorrow. Now i'm unable to think with clarity.

EDITED: i have seen your new post now. Nice.

neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Thu Jul 17, 2008 7:07 pm

Andreas Naive wrote:It's storing internally a rank ordering, which start with {00,01,10,11}

Then, for every pixel (independently of the context), you take the three reference bits (B9,B8 & B2) and do the following:

- In that rank, take B9 and put it in the first position, shifting the other values if needed.
-Then, take B8 and put it in the first position, shifting the other values if needed.
-Finally, take B2 and put it in the first position, shifting the other values if needed.

The result is the new rank order you are going to use to output the current pixel. But the point is that the index to use in that table is not given by the MPS-LPS symbols, but for the "output" of the decoders (i mean, the symbols after XORing them with the "invert" thing).

And, if i haven't missed anything... that's all.
I had a more complicated method, and at first thought that you found a way to simplify it all down (gah, I really need sleep too... but we're so close). However I see now that they are distinct (originally my code was organized quite different and made comparison a bit difficult, I like your layout better). Anyway...

Consider for example the a!=b!=c!=a reference pixels context. With your suggestion above, this would completely rearrange the pixel ordering... that doesn't really make sense since that table should be roughly the order of most frequent pixel values. In fact, since that context is completely fixed by the reference pixels, it should have no effect on the "global" pixel likelyhood order at all.

What I came up with is this:

- shift the 2nd previous pixel value to the "most likely" part of the table

- now, take a temporary copy of that table:
do the same shifts you mentioned above, but only in this temporary table


This makes it so each pixel value only affects the "global" pixel likelyhood order exactly once.


Here's some code. My cludge method for handling pixel values -> bitplane values will definitely need to be made better for mode 2. I'll try to write something up for that next.
http://neviksti.com/SPC7110/DecompTest1.c
It passes everything except the underdumps (which are plentiful, so it could probably use more testing).

EDIT: I'm just going to throw together a test for mode2. In case it works and I need to share the code, what is the "standard" way to specify 64bit integers in C? long long doesn't seem to work with the compiler I have here, but __int64 does.

EDIT(2): Oh screw it. I'll just use two 32bit integers.

caitsith2
Posts: 74
Joined: Mon May 26, 2008 11:41 pm

Post by caitsith2 » Thu Jul 17, 2008 7:46 pm

I will run the tests on all of the Mode 1 portion of the RAW gfx packs now.

caitsith2
Posts: 74
Joined: Mon May 26, 2008 11:41 pm

Post by caitsith2 » Thu Jul 17, 2008 8:22 pm

Testing complete Mode 1 decompression is BIT PERFECT on all cases of SPL4 and MDH, on 100% of the overdumped gfx data.

Code: Select all

// feoez.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char uint8;

uint8 SeenEvolution[53][2]=
{
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0}
};

uint8 EvolutionTable[53][4]=
{
	//prob, nextlps, nextmps, toggle invert
	{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, 30, 33,0}, //32 l,m 
	{0x05, 31, 34,0}, //33 l,m  <--- changed lps 
	{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 l,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 
};

#define PROB(x) EvolutionTable[Contexts[x].index][0]
#define NEXT_LPS(x) EvolutionTable[Contexts[x].index][1]
#define NEXT_MPS(x) EvolutionTable[Contexts[x].index][2]
#define TOGGLE_INVERT(x) EvolutionTable[Contexts[x].index][3]

typedef struct {
	uint8 index;
	uint8 invert;
} context_state;

#define NUM_CONTEXTS 30
context_state Contexts[NUM_CONTEXTS];

#define BIT(x,y) ((x>>y)&1)

void DecompressMode0(uint8 *datain, uint8 *dataout, int len)
{
	uint8 top,val;
	uint8 con,mps,prob;
	uint8 flag_lps,shift,mask;

	int out=0;
	int inverts=0;
	int lps=0;

	unsigned char in;
	int in_count;

	int i,bit;

	//setup 
	top=0xFF;

	val=*datain;
	datain++;

	in=*datain;
	datain++;
	in_count=8;

	//reset context states
	for(i=0;i<NUM_CONTEXTS;i++)
	{
		Contexts[i].index=0;
		Contexts[i].invert=0;
	}

	for(i=0;i<len;i++)
	{
		if(i==-1800)
		{
			int k;
			printf("\nEvolution table:\n");
			for(k=0;k<53;k++)
				printf("  %d,%d //%d\n",SeenEvolution[k][0],SeenEvolution[k][1],k);
		}

		
		for(bit=0;bit<8;bit++)
		{
			//get context
			mask = (1<<(bit&3)) - 1;
			con = mask + ((inverts&mask)^(lps&mask));
			if(bit>3)
				con+=15;
			
			//get PROB and MPS
			prob = PROB(con);
			mps  = (BIT(out,15) ^ Contexts[con].invert);

			if(i>=15 && i<=18 && 0)
				printf("byte %d bit %d: val=%.2X top=%.2X prob=%.2X mps=%d   con=%d state=%d\n",
					i,bit,val,top,prob,mps,con,Contexts[con].index); 

			//get bit
			if (val <= top-prob)
			{
				//mps
				top = top - prob;
				out = (out << 1) + mps;

				flag_lps=0;
			}
			else
			{
				//lps
				val = val - (top - (prob - 1));
				top = prob - 1; 
				out = (out << 1) + 1-mps;
			
				flag_lps=1;
			}

			// renormalize
			shift=0;
			while(top<0x7F) // NOTE: not 0x80, it's a strange border case 
			{
				shift++;

				top = (top<<1)+1;
				val = (val<<1)+(in>>7);

				in = (in<<1);
				if(--in_count==0)
				{
					in=*datain;
					datain++;
					in_count=8;
				}
			}

			//update processing info
			lps = (lps<<1) + flag_lps;
			inverts  = (inverts<<1) + Contexts[con].invert;

			//update context state
			if(flag_lps & TOGGLE_INVERT(con))
				Contexts[con].invert ^= 1;

			if(flag_lps)
			{
				SeenEvolution[Contexts[con].index][0]=1;
				Contexts[con].index = NEXT_LPS(con);
			}
			else if(shift)
			{
				SeenEvolution[Contexts[con].index][1]=1;
				Contexts[con].index = NEXT_MPS(con);
			}
		}

		//save byte
		*dataout = (out & 0xFF);
		dataout++;
	}
}

int DecompressMode1(uint8 *datain, uint8 *dataout, int len)
{
	int pixelorder[4]={0,1,2,3};
	int realorder[4];
	int a,b,c;
	int m,n;

	uint8 top,val;
	uint8 con,prob;
	uint8 flag_lps,shift;

	int out=0;
	int inverts=0;
	int lps=0;

	unsigned char in;
	int in_count;
	int in_len=0;

	int i,j,pixel;

	//setup 
	top=0xFF;

	val=datain[in_len++];

	in=datain[in_len++];
	in_count=8;

	//reset context states
	for(i=0;i<NUM_CONTEXTS;i++)
	{
		Contexts[i].index=0;
		Contexts[i].invert=0;
	}

	for(i=0;i<len;i+=2)
	{
		if(i!=0)
		{
			//turn pixel data into bitplanes
			//and save as output
			*dataout = (BIT(out,15)<<7) + (BIT(out,13)<<6) + (BIT(out,11)<<5) + (BIT(out,9)<<4)
					+ (BIT(out,7)<<3) + (BIT(out,5)<<2) + (BIT(out,3)<<1) + BIT(out,1);
			dataout++;
			*dataout = (BIT(out,14)<<7) + (BIT(out,12)<<6) + (BIT(out,10)<<5) + (BIT(out,8)<<4)
					+ (BIT(out,6)<<3) + (BIT(out,4)<<2) + (BIT(out,2)<<1) + BIT(out,0);
			dataout++;
		}
		
		for(pixel=0;pixel<8;pixel++)
		{
			//get first symbol context
			a = ((out >> (1*2)) & 0x3);
			b = ((out >> (7*2)) & 0x3);
			c = ((out >> (8*2)) & 0x3);
			if(a==b && b==c)
				con=0;
			else if (a==b && b!=c)
				con=1;
			else if (a!=b && b==c)
				con=2;
			else if (a==c && b!=c)
				con=3;
			else
				con=4;

			//update pixel order
			for(m=0;m<4;m++)
				if(pixelorder[m]==a)
					break;
			for(n=m;n>0;n--)
			{
				j=pixelorder[n-1];
				pixelorder[n-1]=pixelorder[n];
				pixelorder[n]=j;
			}


			//get PROB
			prob = PROB(con);

			//get symbol
			if (val <= top-prob)
			{
				//mps
				top = top - prob;
				flag_lps=0;
			}
			else
			{
				//lps
				val = val - (top - (prob - 1));
				top = prob - 1; 
				flag_lps=1;
			}

			// renormalize
			shift=0;
			while(top<0x7F)
			{
				shift++;

				top = (top<<1)+1;
				val = (val<<1)+(in>>7);

				in = (in<<1);
				if(--in_count==0)
				{
					in=datain[in_len++];
					in_count=8;
				}
			}

			//update processing info
			lps = (lps<<1) + flag_lps;
			inverts  = (inverts<<1) + Contexts[con].invert;

			//update context state
			if(flag_lps & TOGGLE_INVERT(con))
				Contexts[con].invert ^= 1;
			if(flag_lps)
				Contexts[con].index = NEXT_LPS(con);
			else if(shift)
				Contexts[con].index = NEXT_MPS(con);

			//get context of second symbol
			con = 5 + con*2 + ((lps^inverts)&1);

			//get PROB
			prob = PROB(con);

			//get symbol
			if (val <= top-prob)
			{
				//mps
				top = top - prob;
				flag_lps=0;
			}
			else
			{
				//lps
				val = val - (top - (prob - 1));
				top = prob - 1; 
				flag_lps=1;
			}

			// renormalize
			shift=0;
			while(top<0x7F)
			{
				shift++;

				top = (top<<1)+1;
				val = (val<<1)+(in>>7);

				in = (in<<1);
				if(--in_count==0)
				{
					in=datain[in_len++];
					in_count=8;
				}
			}

			//calculate the real pixel order
			for(m=0;m<4;m++)
				realorder[m]=pixelorder[m];
			//shift refence pixel c value to top
			for(m=0;m<4;m++)
				if(realorder[m]==c)
					break;
			for(n=m;n>0;n--)
			{
				j=realorder[n-1];
				realorder[n-1]=realorder[n];
				realorder[n]=j;
			}
			//shift refence pixel b value to top
			for(m=0;m<4;m++)
				if(realorder[m]==b)
					break;
			for(n=m;n>0;n--)
			{
				j=realorder[n-1];
				realorder[n-1]=realorder[n];
				realorder[n]=j;
			}
			//shift refence pixel a value to top
			for(m=0;m<4;m++)
				if(realorder[m]==a)
					break;
			for(n=m;n>0;n--)
			{
				j=realorder[n-1];
				realorder[n-1]=realorder[n];
				realorder[n]=j;
			}

			
			//update processing info
			lps = (lps<<1) + flag_lps;
			inverts  = (inverts<<1) + Contexts[con].invert;

			//update context state
			if(flag_lps & TOGGLE_INVERT(con))
				Contexts[con].invert ^= 1;
			if(flag_lps)
				Contexts[con].index = NEXT_LPS(con);
			else if(shift)
				Contexts[con].index = NEXT_MPS(con);

			//get pixel
			b=realorder[(lps^inverts)&3];
			out = (out<<2) + b;
		}
	}

	//turn pixel data into bitplanes
	//and save as output.. BUT don't save second byte unless asked to
	*dataout = (BIT(out,15)<<7) + (BIT(out,13)<<6) + (BIT(out,11)<<5) + (BIT(out,9)<<4)
			+ (BIT(out,7)<<3) + (BIT(out,5)<<2) + (BIT(out,3)<<1) + BIT(out,1);
	dataout++;
	if((len&1)==0)
	{
		*dataout = (BIT(out,14)<<7) + (BIT(out,12)<<6) + (BIT(out,10)<<5) + (BIT(out,8)<<4)
				+ (BIT(out,6)<<3) + (BIT(out,4)<<2) + (BIT(out,2)<<1) + BIT(out,0);
		dataout++;
	}

	if(in_count==8)
		in_len--;
	//printf("Used %d bytes of input.\n",in_len);
	return in_len;
}



// I'm lazy, so here's static allocation
//plenty of room for all the files we'll be looking at
uint8 datain[0x10000];
uint8 dataout[0x10000];
uint8 realout[0x10000];

uint8 datarom[0x400000];

int htoi(char *str)
{
	int i=0,j=0;
	while(str[i]!=0)
	{
		j<<=4;
		if((str[i]>='0')&&(str[i]<='9'))
			j+=str[i]-'0';
		if((str[i]>='A')&&(str[i]<='F'))
			j+=str[i]-'A'+10;
		if((str[i]>='a')&&(str[i]<='f'))
			j+=str[i]-'a'+10;
		i++;
	}
	return j;
}


int main(int argc, char* argv[])
{
	FILE *fp;
	char filename[260];
	int i,j,k,l=0,m=0,len,count;

	//for(i=0;i<0x10000;i++)
	//	datain[i]=0xFF;
	//datain[0x2000]=0x7F;
	//DecompressMode0(datain,dataout,0x10000);

	
	sprintf(filename,"%s",argv[2]);
	fp=fopen(filename,"rb");
	if(fp==NULL)
	{
		printf("ERROR: Can't open file [%s] for reading.\n",filename);
		return 1;
	}
	fread(datarom,1,0x400000,fp);
	fclose(fp);
	fp=NULL;

	sprintf(filename,"%s.bin",argv[1]);
	fp=fopen(filename,"rb");
	if(fp==NULL)
	{
		printf("ERROR: Can't open file [%s] for reading.\n",filename);
		return 1;
	}
	
	fseek(fp,0,SEEK_END);
	len=ftell(fp);
	fseek(fp,0,SEEK_SET);
	printf("File [%s] opened\n",filename);
	printf("%d entries in Table\n",len / 0x8000);
	len = 0x8000;	//All Raw GFX pack decompressions are 0x8000 bytes in size.
	
	k=0;

	i=0;
	while(filename[i++]!='/');	//Extract Table Address from bin file name.
	filename[i+6]=0;
	j=htoi(&filename[i]);
	sprintf(filename,"%s.bin",argv[1]);

	while(fread(realout,1,0x8000,fp)==0x8000)	//For each full readout,  decompress the data, and compare.
	{
		printf("Table %.6X-%.2X-%d read --- ",j,k,datarom[j+(k*4)]&3);
		if((datarom[j+(k*4)]&2)==2)	//Decompression type 2 not supported, Type 3 is invalid.
		{
			printf("Skipped\n",datarom[j+(k*4)]);
			k++;
			continue;
		}
		
		l=datarom[j+(k*4)+1]<<16;
		l+=datarom[j+(k*4)+2]<<8;
		l+=datarom[j+(k*4)+3];		//Get pointer to compressed data.

		if((datarom[j+(k*4)]&3)==0)
			DecompressMode0(&datarom[l],dataout,len);
		else if ((datarom[j+(k*4)]&3)==1)
			DecompressMode1(&datarom[l],dataout,len);
		//else if ((datarom[j+(k*4)]&3)==2)
		//	DecompressMode2(&datarom[l],dataout,len);

		//compare
		for(i=0;i<len;i++)
		{
			if(dataout[i]!=realout[i])
				break;
		}

		if(i==len)
			printf("Success! No mismatches.\n");
		else
		{
			printf("****FAIL**** mismatch on byte %d - ",i);
			int j=i;
			for(;i<len;i++)
			{
				if(realout[j]!=realout[i])
					break;
			}
			if(i==len)
				printf("Real Decompressor crashed\n");
			else
				printf("Error in either decompressor or Raw Data\n");
			/*
			int j;

			printf("****FAIL**** mismatch on byte %d\n",i);

			j=i-3;
			if(j<0)
				j=0;
			
			for(;j<=i;j++)
				printf("byte %d: decomp[%.2X]->real[%.2X]\n",j,dataout[j],realout[j]);

			if(0)
			{
				printf("\nEvolution table:\n");
				for(i=0;i<53;i++)
					printf("  %d,%d //%d\n",SeenEvolution[i][0],SeenEvolution[i][1],i);
			}*/
		}
		k++;
	}
	fclose(fp);

	


	return 0;
}

Now just waiting for Mode 2 to be figured out, so that it can be dropped into the above code, and completely tested.

neviksti
Posts: 205
Joined: Thu Jun 22, 2006 11:39 pm

Post by neviksti » Thu Jul 17, 2008 11:19 pm

First guess attempts at mode 2 have failed.
I modified the snes code for the prob calculator to work with mode 2. It is much slower now. It hasn't finished running an input file yet, but I've looked at preliminary results and it appears that the first symbol for the pixel is always the same context. And the next symbol appears to only have two contexts.

The next symbol appears to have at least eight contexts? What? I'll have to wait for the prob calculator to finish running to see this better.

I'm way too tired to think straight at the moment. So that's enough for now. Hopefully the prob calculator will successfully finish running while I sleep.

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Thu Jul 17, 2008 11:31 pm

This makes it so each pixel value only affects the "global" pixel likelyhood order exactly once.
Well, as i said i did'nt run automatic checks, so it's easy i missed that. :P

Andreas Naive
Posts: 104
Joined: Mon Nov 26, 2007 2:06 am
Location: Madrid, Spain
Contact:

Post by Andreas Naive » Thu Jul 17, 2008 11:36 pm

first symbol for the pixel is always the same context. And the next symbol appears to only have two contexts.

The next symbol appears to have at least eight contexts? What?
If this worked like mode1, you would see 5+10+20+40=75 contexts. But the patent describe how it "degenerate" the possible 75 contexts to only 31.
Basicly, as you have 75=5*15, what it does is to "collapse" 11 of the 15 "states" to not take into account the SX signal, so you finally got 5*4+11=31 contexts. If i didn't failed to follow it, you should see 1 context for bitplane #0, 2 contexts for bitplane #1, 8 contexts for bitplane #2 (3+5*1) and 20 for bitplane #3 (5+5*3).

So all makes perfect sense. ;)

EDITED: Of course, i meant 8 for bitplane #2. Text corrected.
Last edited by Andreas Naive on Fri Jul 18, 2008 12:12 am, edited 1 time in total.

byuu
Posts: 1539
Joined: Mon Mar 27, 2006 5:23 pm
Contact:

Post by byuu » Fri Jul 18, 2008 2:24 pm

In case it works and I need to share the code, what is the "standard" way to specify 64bit integers in C? long long doesn't seem to work with the compiler I have here, but __int64 does.
You're using Visual C++ 6.0? Why? >_<

Neither C99 nor C++98 specify either __int64 or long long, but all modern compilers support the latter. It's likely long long will be in C++0X. Of course, char/short/int/long/long long do not guarantee size.

I'd suggest including <stdint.h>, and using uint64_t. Visual C++ lacks the header, but you can get a drop-in version here: http://msinttypes.googlecode.com/svn/trunk/stdint.h
Testing complete Mode 1 decompression is BIT PERFECT on all cases of SPL4 and MDH, on 100% of the overdumped gfx data.
Hoorah!! neviksti, you are a hero! :D
So close, so close ...

Post Reply