+  RHDN Forum Archive
|-+  Romhacking
| |-+  ROM Hacking Discussion
| | |-+  Upgrading DTE hack to true dictionary compression
Pages: [1]
Author Topic: Upgrading DTE hack to true dictionary compression  (Read 2 times)
Kagemusha
Guest
« on: February 20, 2008, 09:16:00 pm »
What the subject says is exactly what I need to do for a NES game I'm working on. A while ago I was told a few things that would be necessary which were:

Quote
When the code runs through the DTE path (flag2), read the byte. Check if the value is $FF - do not return byte and go 'normal' path if so.


The bigger problem is how to index your dictionary - it isn't fixed size of 2 anymore.

(1) Count the # of <$FF> strings. This is slow.

ex.
50=ab<$FF>
51=a<$FF>
52=this<$FF>

$52-$50 = $02.
- Read 'ab' <FF>.
- Read 'a' <FF>.
- Set your dictionary cursor here.

(2) Use a table of 8/16-bit index positions.
50 = [00]
51 = [03]
52 = [05]

Dictionary + $05 = text cursor.
This uses MORE space. Which is less practical on the NES (can be space unfriendly).

Well I guess it's a matter of understanding how I go about coding which ever method I choose. I don't really understand them except for the first part. So can anyone provide some insight on this stuff? Even source code/sample code would probably do and space is not an issue as there is a ton of free space in RAM and the PRG ROM.
« Last Edit: February 20, 2008, 09:24:04 pm by Pennywise »
RedComet
Guest
« Reply #1 on: February 20, 2008, 09:32:27 pm »
The way I did it in DBZ3 and DBZ Gaiden (the source code is available on my site and here at RHDN) is by setting aside an unused hex byte that would serve as a trigger byte. Then a second byte would determine which substring to load. For example, let's say you have $FF as your trigger byte and you want the fourth substring. In ROM it would be stored as $FF04. The dictionary contains a pointer table with pointers to each substring.

First you want to check for the trigger byte after you've read the byte from the string. If you don't have a trigger byte on your hand, process the data like any other. If you do, however, you need to load the substring. So you get the second byte and use that to load the pointer to the string.

Reading the substring really depends on how your game is set up. You can store the pointer in RAM and read it the substring indirectly or you can read it directly from the ROM.  DBZ3/Gaiden already had dictionary compression, so I was able to make use of the area of memory it had already set aside to store the pointer for the extra compression I added.

Alternatively to the above two byte scheme, you could set aside a range of bytes to use. Say, $80-$C0. Then you would need to subtract $80 from each value to get the correct string number.

Hope that helps.
Kagemusha
Guest
« Reply #2 on: February 20, 2008, 09:41:27 pm »
That does help me. I'll have to check out your source code. Thanks.
Nightcrawler
Guest
« Reply #3 on: February 21, 2008, 08:59:51 am »
Quote from: Pennywise on February 20, 2008, 09:41:27 pm
That does help me. I'll have to check out your source code. Thanks.

Don't over complicate it. It's really a very minor change from DTE. It probably won't take more than a few of lines of code. Think it through before you jump into it. The only thing you're actually changing is allowing the entries to be variable length rather than fixed.

I agree with Red. You'll want to end your entries with $FF. (Though alternatives are to store length bytes as the first byte in each entry, or even keep a table of lengths.) That solves problem 1. The only other problem is accessing the correct entry. Again, you'll have your control code trigger and the next byte can be the index to the dictionary string in question. That can be an entry counter where you need to count $ff bytes OR if your total dictionary is less than 256bytes (which is a good possibility on NES), you can have that byte be an actual pointer to the entry table, no counting involved. Alternatively, you could offer a 16-bit pointer for a huge dictionary, but it both increases complexity and negates some space savings.

It's really very minor. Two small changes.  A few lines of code. It's for this reason I have no idea why anyone does DTE when the differences are so minor and the extra space savings can be significant.

If there's any other specifics we can help with, feel free. Smiley
KingMike
Guest
« Reply #4 on: February 21, 2008, 10:39:04 am »
I'm in the process of commenting a disassembly of my Dragon Scroll DTE+dictionary hack.
I'll post it when I'm finished.

(yes, might be the stupid way, but I've gotten use to inserting NES ASM hacks by typing the hex. I write some ASM first to plan it out, but I of course make lots of mistakes, and too often I'm too lazy to fix the "source")
Bongo`
Guest
« Reply #5 on: February 21, 2008, 11:53:49 am »
Quote from: KingMike on February 21, 2008, 10:39:04 am
I'm in the process of commenting a disassembly of my Dragon Scroll DTE+dictionary hack.
I'll post it when I'm finished.

(yes, might be the stupid way, but I've gotten use to inserting NES ASM hacks by typing the hex. I write some ASM first to plan it out, but I of course make lots of mistakes, and too often I'm too lazy to fix the "source")

  Wow! Why don't you use xKas to compile to code for you? Smiley For any NES hacks, xKas is the way for me. Smiley
I have a program with source and an example of how I did / do it all if you would lke to see it.
Gemini
Guest
« Reply #6 on: February 21, 2008, 12:37:22 pm »
Totally agree with NC: the process to make DTE evolve into MTE is pretty simple. My method is to use 3 variables in ram to keep track of your dirty stuff:
- DTE flag: 0 if nothing is to be processed, otherwise contains the DTE second character;
- MTE pointer: 0 if there is no MTE to process, otherwise contains the offset to the mte string;
- Original string seek: to restore the original pointer when the MTE string encounter a NULL;

The algorithm uses a function to read a character, instead of a simple load byte instruction to load a character, so that you won't have to change much within the code and have a general routine for everything. I use an AND $80 to determine if the character is a DTE or not ($80~$FF), and some unused control code for MTE with a 2 byte index after it.
As for DTE: If the character to read is >=$80 or <=$FF the procedure does all the usual DTE stuff to determine where to read from the dual char table, reads the second character and stores it into the DTE flag, then returns the first character to the string father routine. When it will be called again, it will check the DTE flag, which will contain the second DTE char, return that and clear the DTE flag.
As for MTE: When the routine encounters a MTE flag, it saves the current string seek into the Original string seek variable, determines the MTE string address and saves that into the MTE pointer, then starts reading from that pointer. When you call again the routine, it will check for the MTE pointer, and if it is set will read from there. When a NULL is found (end of the string), it will clear the MTE pointer and restore the original string pointer.

To make it clearer, let's go for some C code:
Code:
#define MTE_CODE 0x02 // example value

BYTE* original_seek;
BYTE dte_flag;
BYTE* mte_pointer;

BYTE* string;
BYTE dte_table[256][2];
BYTE** mte_table;

BYTE ReadCharacter()
{
BYTE c;
if(dte_flag!=0)
{
c=dte_flag;
dte_flag=0;
return c;
}
else if(!mte_pointer)
{
c=mte_pointer[0];
mte_pointer++;
if(c!=NULL) return(c);
else
{
mte_pointer=NULL; // turn off the mte
string=original_seek; // restore the original seek
return ReadCharacter(); // read next char from mte, CAUTION: don't call a mte when one is already being processed
}
}
else
{
c=string[0]; // read the next char
string++;
if(c&0x80) // call dte
{
c-=0x80;
dte_flag=dte_table[c][1]; // second char from dte table
return dte_table[c][0]; // return the first char from dte table
}
else if(c==MTE_CODE)
{
original_seek=string+2; // skip the mte stuff
mte_pointer=mte_table[*((USHORT*)string)]; // set mte pointer
return ReadCharacter(); // read next char from mte, CAUTION: don't call a mte when one is already being processed
}
else return c;
}
}
KingMike
Guest
« Reply #7 on: February 21, 2008, 01:01:00 pm »
Alright. Here's my code.

Copy and paste link
http://www.geocities.com/newkingmike/dictionary_dte.txt
(I'll sumbit it once I get to my other PC and can upload to my other site, which allows hotlinking)

(on a side note, I do plan to get the game out soon. Probably the most likely candidate for my annual site-birthday release in April. Cheesy )

Yeah, it can probably be optimized a bit, but it gives you the idea.

If you want to give me some info, Bongo`, sure. Doesn't xkas kinda blow up on branches?
I suppose NESASM could work too.
(I used it to hack in a save/load screen for Stargazers, writing a test ROM with my hack in, then use a hex editor to copy and paste the code into the actual game.)
But that's probably not so great for small hacks where it's impractical to write a test situation.
Bongo`
Guest
« Reply #8 on: February 21, 2008, 05:13:14 pm »
Quote from: KingMike on February 21, 2008, 01:01:00 pm
Alright. Here's my code.

Copy and paste link
http://www.geocities.com/newkingmike/dictionary_dte.txt
(I'll sumbit it once I get to my other PC and can upload to my other site, which allows hotlinking)

(on a side note, I do plan to get the game out soon. Probably the most likely candidate for my annual site-birthday release in April. Cheesy )

Yeah, it can probably be optimized a bit, but it gives you the idea.

If you want to give me some info, Bongo`, sure. Doesn't xkas kinda blow up on branches?
I suppose NESASM could work too.
(I used it to hack in a save/load screen for Stargazers, writing a test ROM with my hack in, then use a hex editor to copy and paste the code into the actual game.)
But that's probably not so great for small hacks where it's impractical to write a test situation.

Here is a zip file. Sorry I didn't comment enough but I'm in a rush. If you feel you would like to know more about it then let me know and I can explain everything!

http://stealth.romhack.net/xKas2NES.zip
Nightcrawler
Guest
« Reply #9 on: February 22, 2008, 10:50:47 am »
If you get some time to fix it up, perhaps it would be useful to add here for other people? Or maybe it's not necessary depending on when xkas 2 is capable to be used for NES. Just a thought.
Bongo`
Guest
« Reply #10 on: February 22, 2008, 01:21:42 pm »
Quote from: Nightcrawler on February 22, 2008, 10:50:47 am
If you get some time to fix it up, perhaps it would be useful to add here for other people? Or maybe it's not necessary depending on when xkas 2 is capable to be used for NES. Just a thought.

 Yeah I was gonna fix it up but I figured Byuu was gonna add support for NES in xKas 2.
I was actually working on the NES assembler, for hacking mainly, but I thought I saw that he was gonna add support so I decided agianst it. Smiley
Pages: [1]  


Powered by SMF 1.1.4 | SMF © 2006-2007, Simple Machines LLC