This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

"Mapper 1" emulation & extension

"Mapper 1" emulation & extension
by on (#69985)
The wiki page about iNES mapper 1 says emulating mapper 1 is problematic for games with more than 8KB of SRAM or more than 256 KB of PRG ROM.

Also, Neil Baldwin has encountered many problems when he was willing to use such a configuration. Even if he did an iNES 2.0 header and using Nestopia, you can't always get the amount of SRAM you'd specify in the header. And since Nestopia, the only emulator who supports iNES 2.0, has no debugger you'd want to be able to debug your programs with Nintendulator and FCEUltra.

However, because it's simple and available at RetroZone, using Mapper 1 even for larger/complex games is a very good option.

On the Wiki page about mapper 1, I proposed an algorithm that supposedly emulates proprely all MMC1 games that doesn't rely on memory mirroring.

However I'd ask myself, while Nintendo made CNROM boards can only allow 32kb of CHR-ROM, it's iNES counter part, mapper 3, can allow up to 1MB of CHR-ROM (in fact you could even have 255 CHR banks and have almost 2MB, but non power of two sizes aren't recommanded).

So why not go a step further and recreate something similar for mapper 1, which could even include boards that "were never made", with an algorithm that, if followed stricly, would allow to accurately emulate all commercial MMC1 games that doesn't rely on memory mirroring, and to emulate all future MMC1 homebrewn games as long as they don't rely on memory mirroring (no matter if they fit a Nintendo made board or not).

Because even on SXROM, there is still one bit unused for the CHR Registers, maybe it should "officially" be assigned for an additional SRAM banking bit (in a similar fashion as the additional CHR banking bits of mapper 2 or 3) ?
This has the disadvantage of not allowing more than 512kb of PRG ROM, but with so much RAM at your disposal, you could heavily compress a lot of things, allowing in theory really large games.

Also, there should be a way to determine which banks are saved and which aren't, that englobes Nintendo made boards but allow for future expansion.

Of course a game that would write something to SRAM, write something to the CHR registers and exept the SRAM to *NOT* be bankswitched will not work with such a system. Is there any commerical NES/FC games who did that ?

by on (#69986)
So when do we move to the "what wire goes where" system of specifying mappers in the rom's header?

by on (#69987)
Dwedit wrote:
So when do we move to the "what wire goes where" system of specifying mappers in the rom's header?

That's something I've been waiting for a while...

by on (#69988)
Wouldn't the easiest fix be for emulators to actually use the information in the header properly? There already is a PRG-RAM size field. If the emulator is just ignoring it, it should be fixed. No reason to try to go about fixing it another way.

by on (#69989)
I want to make a game tat will be 1MB in size. But one problem is testing. Burning a cart for every test is not plausible, and emulation won't happen because of it being not released. I love this idea and hope ALOT that it happens somehow! :D

by on (#69992)
You could do a MMC5 game with 512kb PRG + 512kb CHR like Metal Slader Glory. Of course you'd have to burn ROMs to test it, but it would be emulable and you don't have to make your own board.
Or heavily compress everything in 512kb PRG and decompress in a crazily large SRAM (it's what I was talking about above).

Quote:
Wouldn't the easiest fix be for emulators to actually use the information in the header properly? There already is a PRG-RAM size field. If the emulator is just ignoring it, it should be fixed. No reason to try to go about fixing it another way.


Mmh yeah I guess you're right...
Yet there is nothing that "officially" specify what to do if you input amount of PRG-RAM that doesn't exist in existing Nintendo games...
I was just under the impression that having a third bit for SRAM banking would make sense... but the problem is to know what is battery backed and what is not. iNES 2.0 allows you to specify the quantity of battery backed SRAM and non-battery backed SRAM. However, it doesn't allow you to specify HOW it's mapped.

Also maybe emulator authors would be more prone to simply fix a few things in a mapper than fully implement iNES 2.0 that no ROM uses ?

by on (#69993)
65024U wrote:
I want to make a game tat will be 1MB in size. But one problem is testing. Burning a cart for every test is not plausible, and emulation won't happen because of it being not released. I love this idea and hope ALOT that it happens somehow! :D

Since 1MB is a lot of space, I bet that a lot of it is data, not code, so I suggest that you get the game working in a smaller ROM size with some of the data missing, but make it easily expandable so that you can later include the rest of the data, which you'll do once the code is done. At that point, your game will be practically ready, and emulator authors will have a motivation to support it.

by on (#69997)
My NSF Player on SNES was 4Mbytes, and I had to test it using floppy disks. But echoing what tokumaru said, I had made a cut-down version of it that was easier to test, using some conditional assembly commands (if, else) to simply not include the massive loads of data (just empty labels pointing to the same thing).

by on (#69998)
Bregalad wrote:
Nestopia, the only emulator who supports iNES 2.0

The beta version of Nintendulator can load NES 2.0 images.

Quote:
On the Wiki page about mapper 1, I proposed an algorithm that supposedly emulates proprely all MMC1 games that doesn't rely on memory mirroring.

Interesting.

Quote:
Because even on SXROM, there is still one bit unused for the CHR Registers, maybe it should "officially" be assigned for an additional SRAM banking bit

Unless Memblers is about to make some IRQ circuitry that can be added to any MMC1 + CHR RAM board, and it wants a bit to control IRQ generation and acknowledgment.

Quote:
This has the disadvantage of not allowing more than 512kb of PRG ROM, but with so much RAM at your disposal, you could heavily compress a lot of things, allowing in theory really large games.

There are things that won't fit into even 512 KiB. For example, most of the data in Big Bird's Hide and Speak (384 KiB) is Carroll Spinney's voiceover, including much of the CHR ROM. And if you want a lot of voice acting in a game, or a lot of prerecorded music (say for something like Dance Dance Revolution), you'll need lots of space, though like tokumaru said you can test it with less data (in DDR's case three songs at a time). It has uses even other than audio: consider that the HKO port of Final Fantasy VII to Famicom is four times this 512 KiB.

65024U wrote:
emulation won't happen because of it being not released.

The two most accurate NES emulators are both free software. You can take one of the existing emulators and hack your preferred mapper to allow a 1024 KiB PRG ROM.

by on (#69999)
The Final Fantasy VII port is a horrible example because it goes down to 467KB when compressed with APLIB, and 347KB when compressed with 7-zip. Look at that file in a tile editor, lots of blank space, and lots of repeated two byte sequences spanning kilobyte after kilobyte.

by on (#70007)
Yeah thats true, but it's 1MB ROM, 8K CHR-RAM :/ And I could cut it down to 512K, but that will only support it upto halfway into development IMO. :/ Could Luascripts be used to increase the bank switching to what I need? I've never used them or used them but I've heard of them alot.....

by on (#70009)
65024U wrote:
Yeah thats true, but it's 1MB ROM, 8K CHR-RAM :/ And I could cut it down to 512K, but that will only support it upto halfway into development IMO. :/

I think the idea is to split it up into multiple "discs", each with a part of the game, during development. That way, you have one ROM until Aeris dies, one ROM for most of the second half of the game until Batman pees, and one ROM just to put swords in my knees. The programming techniques to split it up could also be used to make a 1-chapter demo if you plan on selling copies of the whole thing.

by on (#70011)
Yeah, but all the banks will be needed...atleast 256K just for the graphics. The game won't be complex, just....alot of graphics. XD

by on (#70017)
If you use CHR-RAM, graphics is usually an element that can compress well.
If you don't mind using CHR-ROM, MMC3 has support for up to 256k of CHR-ROM, and I think MMC5 can even allow up to 1MB.

You could also distribute it in FDS format, using as many disk sides as you want (although I suspect the Power Pak to only support 2 disk sides so far, but in theory it could load 8 disk sides at a time, and even have support for more, loading them from the CF cart whenever needed, which would probably be about as slow as the real FDS).

(This FF7 pirate is a terrible example as the game was terribly ported. It's a plain insult to one of my favourite games so I don't like it being mentioned. Is's just a bunch of pirate crap.) Anyway, a game that fits ~300k compressed could be put in a 512 k ROM, and being decompressed into 32 or 64k of SRAM at a time, kinda like FDS disk sides once again :) (64k is the size of one FDS disk side).

Quote:
Unless Memblers is about to make some IRQ circuitry that can be added to any MMC1 + CHR RAM board, and it wants a bit to control IRQ generation and acknowledgment.

Cool but then it probably shouldn't be assigned to mapper 1 anymore, as it's definitely more than just a simple extension.

EDIT : Oh an my algorithm still won't work for FF1+2... as the multicart uses bank 0 for FF1 and bank 2 for FF2, it will "think" the cart is SOROM and will save only bank 2. I'm short of ideas here... realying on the PRG size for this (if it's 512k it can't be SOROM) is NOT a good idea.... yet the only way to tell FF1+2 apart from SOROM games in the iNES 1.0 header.

by on (#70023)
How about we make a standard where if the PRG size is bigger then what is supported via the PRG-ROM bank switching bits, the CHR-ROM bank switching character bits are used from MSB to LSB on the PRG-ROM. So the 512K ROM would be used with the most significant CHR line, while the 1MB bit would be the 2nd most significant CHR-ROM bit available, and so on. I think thats something we should consider maybe getting added to emulators for support of 1MB and bigger ROM's automatically without hacking.


And also, the game I want to do is the pokemon game with 256 pokemon with two 32x32 images for each, so CHR-ROM is out of question, like the battle screens, the pokemon change every time and you just can't use CHR-ROM at all, that'd make the 256K of graphics take up ALOT more in CHR-ROM. Way more then can be used....Thats what I need the 1MB cart for with the CHR-RAM. :)

by on (#70029)
65024U wrote:
And also, the game I want to do is the pokemon game with 256 pokemon with two 32x32 images for each, so CHR-ROM is out of question

Can you mock up a screenshot of your Pokemon clone so that I can see how things would look? If it's an over-the-shoulder view like that in Pokemon for Game Boy, it could use CHR ROM and bankswitch CHR on a scanline between the opponent's gamecock and your gamecock.

by on (#70032)
Bregalad wrote:
EDIT : Oh an my algorithm still won't work for FF1+2... as the multicart uses bank 0 for FF1 and bank 2 for FF2, it will "think" the cart is SOROM and will save only bank 2. I'm short of ideas here... realying on the PRG size for this (if it's 512k it can't be SOROM) is NOT a good idea.... yet the only way to tell FF1+2 apart from SOROM games in the iNES 1.0 header.


Why not just save all of PRG-RAM? Sure the real cart only keeps one chip's contents alive, but the emulation can just keep all of it intact and the game shouldn't be negatively impacted. It's not like harddrive space is an issue.

by on (#70034)
Scanline changing might be okay to do but I really don't want to use any tricks like that to add to the confusion of making a game of this size. The program won't be hard, it's just gotta handle a huge chunk of data in images and other stuff later on. :)


My mockup on the NES emulator is basically a recreated gameboy R/Y/B version battle screen. Pretty much the same thing. I guess interrupts might work but....eh...It's not needed, and I have 8K SRAM's, but not anything over a 256K ROM so just to stick a single 1MB rom on there instead of two 512K's is cheaper, also.


Anyone else think that solution for the PRG-ROM will be good to have added to the standard?

by on (#70037)
65024U wrote:
I want to do is the pokemon game with 256 pokemon with two 32x32 images for each

OK, that's 32 tiles per Pokemon, with 256 of them that's a total of 8192 tiles. Each tile is 16 bytes, which means you need 131072 bytes, or 128KB, for the Pokemon graphics. Saying you need 1MB just because of that is a bit of a stretch. Even if you used 128KB for the rest of the graphics, a 512KB ROM would have plenty of room left for code and data. Also, CHR data can be easily compressed to about 70% of its size if you are using CHR-RAM.

65024U wrote:
the pokemon change every time and you just can't use CHR-ROM at all

But you always have only 2 of them in the same screen, right? The MMC3 allows you to bankswitch CHR-RAM in 1KB or 2KB pieces, so you can easily combine different Pokemons at will without needing any extra space.

by on (#70039)
Bregalad wrote:
Quote:
Unless Memblers is about to make some IRQ circuitry that can be added to any MMC1 + CHR RAM board, and it wants a bit to control IRQ generation and acknowledgment.

Cool but then it probably shouldn't be assigned to mapper 1 anymore, as it's definitely more than just a simple extension.


Yeah that's true, at first I looked at a sorta stand-alone IRQ add-on, but the most effective way I came up has the most interesting parts being done inside the CPLD (with a cheap single NAND gate outside to do the boring stuff). The rest of the mapper outclasses MMC1, IMHO (and perhaps MMC2 as well). So far my mapper seems almost too good to be true (for it's low cost), but it does compile, synthesize, and fit. I'll know for sure pretty soon. I still have a couple ideas to make it more flexible, that I'll check into before prototyping the board.

by on (#70053)
Quote:
How about we make a standard where if the PRG size is bigger then what is supported via the PRG-ROM bank switching bits, the CHR-ROM bank switching character bits are used from MSB to LSB on the PRG-ROM. So the 512K ROM would be used with the most significant CHR line, while the 1MB bit would be the 2nd most significant CHR-ROM bit available, and so on. I think thats something we should consider maybe getting added to emulators for support of 1MB and bigger ROM's automatically without hacking.
Why not just save all of PRG-RAM? Sure the real cart only keeps one chip's contents alive, but the emulation can just keep all of it intact and the game shouldn't be negatively impacted. It's not like harddrive space is an issue.
That's a good idea but it will conflict about SRAM selection bits.
Then, a table for all SRAM size and ROM sizes available on iNES 2.0 and what bits select what should be created.

About 65024U's game, I can't juge whenever it's true the CHR-RAM is absolute need or not. CHR-RAM is an absolute need if
1) You want to modify graphics manually in real time by a program
2) The tileset should be highly customizable and can't be made with sets of 1KB (4KB in MMC1's case)

2) isn't even true in MMC5's case, as when you use EXRAM you can acess a whole 256KB set for your background.

I don't think any of those is an absolute need for a Pokemon game so I might be wrong (also Pokemon is a copyrighted product BTW).
I guess a "forward" and "backwards" pic should be made for each pokemon, so in regard to what Tokumaru said it would end up 256KB. However, if you use CHR-RAM, once compressed it could end up much smaller. If you use CHR-ROM, you'd effectively need MMC5 to get 512 KB of CHR.

Quote:
Why not just save all of PRG-RAM? Sure the real cart only keeps one chip's contents alive, but the emulation can just keep all of it intact and the game shouldn't be negatively impacted. It's not like harddrive space is an issue.

That's a good point. Just that you want to keep compatibility with 8kb .sav files from older emulators. So I'll change the algorithm on the wiki, that will save useless data for SOROM but work fine in all cases.

by on (#70058)
Bregalad wrote:
Quote:
How about we make a standard where if the PRG size is bigger then what is supported via the PRG-ROM bank switching bits, the CHR-ROM bank switching character bits are used from MSB to LSB on the PRG-ROM. So the 512K ROM would be used with the most significant CHR line, while the 1MB bit would be the 2nd most significant CHR-ROM bit available, and so on. I think thats something we should consider maybe getting added to emulators for support of 1MB and bigger ROM's automatically without hacking.
Why not just save all of PRG-RAM? Sure the real cart only keeps one chip's contents alive, but the emulation can just keep all of it intact and the game shouldn't be negatively impacted. It's not like harddrive space is an issue.
That's a good idea but it will conflict about SRAM selection bits.
Then, a table for all SRAM size and ROM sizes available on iNES 2.0 and what bits select what should be created.


You could always extend the 5-bit register then the MMC1 supports on the MMC1 board so after 5 writes to a port, if any more writes are taken to that port after that (Which would be unnecessary), make it go to a new 8-bit mode that homebrew developers could use as with standard MMC1 cart and add 3 more PRG-ROM select lines to the cart. Sure you'd have to get Bunnyboy to agree and sell it, but this could be made in small batches by the community if more people would be interested in such a cart.


And those 256K of graphics are JUST the pokemon. (Not going to call the game or them that, BTW) I'd need probably 32K more for the other graphics I would use, characters, backgrounds, etc.

by on (#70060)
Bregalad wrote:
Sure the real cart only keeps one chip's contents alive, but the emulation can just keep all of it intact and the game shouldn't be negatively impacted.

The emulator should behave like the hardware wherever feasible. Otherwise, you get into the early NES scene, where games depended on the quirks of Nesticle because they had been tested only on the emulator. Even nowadays, games might start depending on PowerPak mapper quirks, such as MMC3 bankswitching the PRG RAM whenever it bankswitches the PRG ROM, causing problems when someone tries to make a repro of a homebrew game. (Versions of PowerPak MMC3 with this problem already cause visual artifacts in M.C. Kids and Crystalis.)

Quote:
(also Pokemon is a copyrighted product BTW)

But Nintendo's copyright appears to be narrow enough that Digimon, Dragon Quest/Warrior Monsters, Telefang, and Robopon don't infringe. Any similarity among them likely qualifies as scenes a faire in the genre of cockfighting RPGs.

by on (#70061)
65024U wrote:
And those 256K of graphics are JUST the pokemon. (Not going to call the game or them that, BTW) I'd need probably 32K more for the other graphics I would use, characters, backgrounds, etc.

So that'd be about 288KB, with the simplest compression schemes you can get that down to at least 80%, or 230KB (but there are better schemes that can compress up to 65%). In a 512KB ROM you'd still have 282KB left for all the code and data. Is that really not enough?

In a Pokemon game, I imagine that the next big thing after Pokemon graphics are the maps, But I believe that if you use metatiles slightly larger than usual (say, 32x32 pixels) and a decent compression scheme, you could put a lot of maps in there.

by on (#70069)
65024U wrote:
You could always extend the 5-bit register then the MMC1 supports on the MMC1 board so after 5 writes to a port, if any more writes are taken to that port after that (Which would be unnecessary), make it go to a new 8-bit mode that homebrew developers could use as with standard MMC1 cart and add 3 more PRG-ROM select lines to the cart.


Interesting idea, but why still call it the MMC1? Personally, I don't see a use for MMC1 compatibility unless it's for making repro/bootleg/pirate carts (which is not something I'm interested in selling..). It's the only mapper (AFAIK) that takes serial input, and probably for a good reason - it's a kinda crappy way to do it (and on a CPLD, inputs are "free", they don't use up any internal resources, just the physical pin itself).

The mapper that I'm working on, that I mentioned in my previous post could use a 1MB ROM. But the version of the board that I'm planning is 512kB max. I'm still skeptical that anyone will need that much ROM so soon. That would be the biggest single (not multicart) NES game ever made.

If I end up using a DIP ROM package on the prototype board, I suppose I could look into make a switch to allow a 1MB EPROM to be used (my first Squeedo board could take a 1MB EPROM, BTW). But you'd have to sacrifice a feature. What would you rather have, less CHR-RAM banks or less WRAM banks?

by on (#70071)
Quote:
You could always extend the 5-bit register then the MMC1 supports on the MMC1 board so after 5 writes to a port, if any more writes are taken to that port after that (Which would be unnecessary), make it go to a new 8-bit mode that homebrew developers could use as with standard MMC1 cart and add 3 more PRG-ROM select lines to the cart. Sure you'd have to get Bunnyboy to agree and sell it, but this could be made in small batches by the community if more people would be interested in such a cart.

Then it will not be MMC1 any longer. What I had in mind is extensions of carts that could have been made with a true MMC1, but haven't.

DW4 was ovedrumped with the assumption that D5 of Reg1 is the 256kb switch (which is true) and that D5 of Reg2 is the 512kb swich (which is false). That idea is interesting, but not feasible with a real MMC1 (at least not without a second circuit that'd monitor writes), so it's out of the way.

by on (#70072)
65024U wrote:
Yeah thats true, but it's 1MB ROM, 8K CHR-RAM :/ And I could cut it down to 512K, but that will only support it upto halfway into development IMO. :/ Could Luascripts be used to increase the bank switching to what I need? I've never used them or used them but I've heard of them alot.....

Why does it need to be MMC1? For the time being, increase the amount of UxROM banking bits in an emulator, make your game and come back when it's ready. :) It could very well be that some emulators already support all 8 bits (for 4MB of PRG-ROM).

by on (#70074)
Memblers wrote:
Interesting idea, but why still call it the MMC1? Personally, I don't see a use for MMC1 compatibility unless it's for making repro/bootleg/pirate carts (which is not something I'm interested in selling..). It's the only mapper (AFAIK) that takes serial input, and probably for a good reason - it's a kinda crappy way to do it (and on a CPLD, inputs are "free", they don't use up any internal resources, just the physical pin itself).


I agree with you that if you make changes that essentially make it not an MMC1 anymore, you shouldn't call it that. And if you do make those changes, it's silly not to go the extra distance to dump the slow serial access all together. MMC1's serial access was some cost saving measure from what I heard and while it works it's somewhat annoying and very slow.

It's much nicer when mappers either use a 2 register setup like FME7 with a Register Select and Data Port, or have each register right on the bus so just writes to say $8000 would switch an 8K section beginning at $8000. It's alot faster and much more simple to use that way. But the Select and Data port can work too. MMC1's serial is by far the worst for speed and code size/simplicity.

If someone were to create a new general purpose mapper today I would hope they wouldn't do any silly serial stuff. I'd hope they'd make it to more or less match the MMC3 in features for PRG and CHR banking and have an IRQ for raster effects.

by on (#70076)
tokumaru wrote:
I imagine that the next big thing after Pokemon graphics are the maps, But I believe that if you use metatiles slightly larger than usual (say, 32x32 pixels)

Pokemon uses 32x32 pixel MTs.

Memblers wrote:
I don't see a use for MMC1 compatibility unless it's for making repro/bootleg/pirate carts

Other than that 1. it's emulated, which makes starting a test run as easy as Ctrl+R in my editor, and 2. it's available on boards for sale now, unlike the mapper you're working on.

Memblers wrote:
It's the only mapper (AFAIK) that takes serial input, and probably for a good reason - it's a kinda crappy way to do it (and on a CPLD, inputs are "free", they don't use up any internal resources, just the physical pin itself).

I imagine that saving three physical pins was a big thing back then. The PPU uses a multiplexed address and data bus (in much the same manner as the GBA cart bus), and Nintendo went to custom 28-pin pinouts for certain ROM sizes instead of using 32-pin JEDEC pinouts for probably the same reason.

thefox wrote:
For the time being, increase the amount of UxROM banking bits in an emulator, make your game and come back when it's ready.

I chose SNROM (mapper 1) instead of UxROM (mapper 2) for a game whose state won't fit in the 32 bits of a password because bunnyboy's UxROM clone board has no PRG RAM.

by on (#70078)
In fact I heard that Nintendo originally planned the MMC1 to be entierely serial, where the 2 register bits would be after (or before ?) the 5 data bits.
But since A13 and A14 had to be present on the MMC1 to enable SRAM anyways, they might as well use them to decode writes too (which is what they did).

It's fun all the possibilities there is for mapper writes, and all of them were used at some point :
- The data written to is the data written to the mapper, the adress writeen is the adress in the mapper (most common)
- Part of the adress written to is mapper's registers, other part of it is data written to it (common on pirate carts)
- Part of the data written is the mapper register, other part is the data (was planned for MMC1)

One could even go insane and make a system where the adress written to is the data loded into the mapper while the data you write correspond to a register in the mapper.

As tepples said, pin save might have been important, but On the SL1ROM board they used CHR-ROM with 4 less pins, only to add a 74HC32 with 14 pins on the board, that's an overall +10 pins..
Also everyone has to agree that the MMC1 is amazing seeing how small of a chip it is. Most other mappers with comparable features are either much larger chips, or surface mounted stuff.

by on (#70079)
Yeah, true, you could use it with any other mapper, I was just using MMC1 as example because it's what I am probably going to use and it available and has no quirks on repro boards I think. Plus it's simple, but the 8 bit mode was just an idea, well it wouldn't be an MMC1 anymore, but just MMC1 compatible I guess. It's be nice so even if homebrewers don't use it, people can still use it to make MMC1 repro's with it? :)


And thats interesting....Yeah I am going to use CHR-RAM for ease of use of animation, and compression might be bad since I am using the 32x32 tiles 2 per pokemon front back as I said before, but finding the pokemon tiles in ROM would be very difficult for high numbers as it'd have to run the numbers all the way up to until it hits that tile, so I think I'll pass on that. And also, sounds for each pokemon possibly, too, so it will take up some space if so and I am going to add those in if this gets done. I just want to make sure I have that space and have no worries.


These are all ideas, even the pokemon game, but I am going to put serious time into it when I get to.

by on (#70083)
65024U wrote:
...but finding the pokemon tiles in ROM would be very difficult for high numbers as it'd have to run the numbers all the way up to until it hits that tile, so I think I'll pass on that.

Are you crazy? You don't have to compress the whole thing as a single block, that'd be stupid. You can compress each individual 32x32 square, so you have direct access to them.

Quote:
I just want to make sure I have that space and have no worries.

I still think 1MB is a pretty high estimate, and since there are no boards available for ROMs that large you are just getting yourself in trouble. Why don't you start with 512KB and if that turns out to not be enough you can expand it to 1MB and convince emulator authors and cart makers to support your game.

by on (#70085)
65024U wrote:
Yeah I am going to use CHR-RAM for ease of use of animation, and compression might be bad since I am using the 32x32 tiles 2 per pokemon front back as I said before, but finding the pokemon tiles in ROM would be very difficult for high numbers as it'd have to run the numbers all the way up to until it hits that tile

How so? If you have a whole bunch of data blocks of different length, you use some sort of directory to reach them all. For 256 different gamecocks each with a front and back image, we have 512 different 16-bit start addresses, or 1024 bytes. I can think of ways to pack the directory tighter if need be, such as sharing the high-order byte among several in a row.

Quote:
And also, sounds for each pokemon possibly, too

Say the distinctive cry of a gamecock species can be expressed as a stream of (pitch, volume) commands for two channels and lasts roughly a second. Then say each cry can be encoded as "frames", each consisting of two pitches, two volumes, and a length in vblanks. This would take 4 bytes, and on average there might be 20 frames in a cry. So 4 * 20 * 256 = 20 KiB for cries.

But one unown factor remains in this business plan: Where do you plan to find artists to draw your 256 gamecocks, plus their trainers?

by on (#70086)
Since we were talking about Pokemon and tile compression, maybe you'll find this article about Pokemon art compression.

He starts out with a simple pixel-based RLE compression and progressively makes it more complex and more efficient. But the techniques he uses are very clear and the whole thing is easy to follow. By the end he reaches a very impressive compression ratio (he compresses the image down to, like, 55% of it's original size).

One of the reasons the scheme worked so well was because the image was compressed as a whole, instead of being divided into individual tiles. So if you are up to the task you could implement something like that for your game. If you are not, even some generic tile/data compression is better than nothing.

by on (#70088)
tepples wrote:
gamecocks

I know you are using that word because of the similarities between Pokemon and cockfights, but I can't avoid imagining some sort of porn game when I read that...

by on (#70091)
Haha! Lets make it for Atari ;)


Well I guess it would be better, and the 2 sounds (with fadout so it sounds okay like a dying down war call) is a good idea for each one. Wouldn't take up too much space. I don't know. I guess I will start with 512K first....

by on (#70092)
One thing that's interesting with my mapper too, I'm actually finding a lot of cool hacks that I can fit in there all at once. But this is a CPLD, which is reprogrammable, and it would be easy enough for me to supply different versions that cut out some of the features, so that others can be improved. Just depends what a project calls for. It's nothing like an ASIC, which is set in stone (er, silicon). The config I'm writing makes every function of it usable, but it is a little bit on the hacky side in this mode.

I don't think emulation support matters much, it is using FlashROM and the NES is the best place to test code anyways.

by on (#70094)
tokumaru wrote:
tepples wrote:
gamecocks

I know you are using that word because of the similarities between Pokemon and cockfights

That and to emphasize what Nintendo doesn't own.

Quote:
but I can't avoid imagining some sort of porn game when I read that...

If you're looking for Pokemon rule 34, you can find it elsewhere.

Back to the tech discussion: The "predictive RLE" reminds me of the Codemasters codec that you tore apart.

Memblers wrote:
I don't think emulation support matters much, it is using FlashROM and the NES is the best place to test code anyways.

If a bit hard to carry along with my laptop when I get an itch to code on the bus. And I'm still waiting for blargg to finish that MMC1 cart supporting in-circuit flash programming, which would make it as easy as using GBA multiboot as opposed to finding someone to solder together a CopyNES.

by on (#70096)
tepples wrote:
If you're looking for Pokemon rule 34, you can find it elsewhere.

I think that most of the porn related to Pokemon exists because of the anime, not the games. I was actually linking porn to the NES, not to Pokemon.

Quote:
The "predictive RLE" reminds me of the Codemasters codec that you tore apart.

True. But the Codemasters one only made predictions based on the pixel to the left, while this one also uses the one from above. Also, while Codemasters was apparently interested in encoding colors more likely to follow in less bits, this codec appears to replace colors with their frequencies given the context, in an attempt to group similar frequencies and generate longer RLE runs. Pretty clever.

EDIT: Another very interesting thing I learned from this article was the auto-trigger RLE. When you work with low-color images that use only 1 or 2 bits per pixel, traditional ways of defining the repeat count would be very wasteful, so I really liked the idea of checking for runs only if the same pixel is used twice in a row.

by on (#70101)
Thats very interesting.... :P Codemaster made some awesome games. Dizzy and Firehawk are great! :D


And thats interesting....I bet that was a mess to find and disassemble! :P



Could a MMC1 (Or any other extended serial mapper) be made compatible and extend it into 8 bit mode too for ease of use with bigger ROM images with the 5 writes to register, any more sets to 8-bit mode kinda thing?

by on (#70110)
Memblers wrote:
I don't think emulation support matters much, it is using FlashROM and the NES is the best place to test code anyways.


Emulation support provides better debugging support though.

65024U wrote:
Could a MMC1 (Or any other extended serial mapper) be made compatible and extend it into 8 bit mode too for ease of use with bigger ROM images with the 5 writes to register, any more sets to 8-bit mode kinda thing?


I don't think there are any other serial mappers like MMC1. You could make your own MMC1-like mapper that uses 8bit shift register instead of 5bit I suppose. But it wouldn't be compatible with MMC1. You could probably make it like you suggested to have some sort of 8bit mode unlock, but that's silly.

If you want to develop a game to use a MMC1 but 8bits type thing an emulator could easily be adjusted to do this, but you'd need someone to program a CPLD for you if you wanted to make carts.

With MMC1 as-is, if you use CHR-RAM, you can change the wiring so that CHR-RAM is not bankable, just static 8Kb block. Then you can take the 5bit CHR register to control the PRG-ROM lines, allowing for something like 4 or 8 megabytes. It would function like MMC1 boards that have 512kb though. The upper 5 bits would be switching 256kb sections. So you'd have to duplicate code/data or something with that setup. It'd be easier if you could select any 16KB section from the total ROM but the way MMC1 works what I described would be the best you would get. Still, something like 4 or 8 megabytes if my math is right is a ton of ROM space.

Just to mention it one more time, there is no reason to do a 8bit MMC1. What I suggested would work with the real thing (I think) and if that's not enough features for you, make a new mapper or use a better one, don't alter the operation of the MMC1 as that's pointless.

by on (#70112)
If you were to take the SUROM superbank concept up to 11, you'd only get 4 MiB because the lowest bit of CHR bank register is busy switching between the first and second banks of CHR RAM.
Code:
43210  $A000: CHR bank in $0000
|||||
||||+- Choose lower or upper half of CHR RAM (ignored in 8 KiB mode)
++++-- Choose superbank of PRG ROM

It'd be possible to take it to 8 MiB, but then you could use only 4 KiB of the CHR RAM. But then even SNES and GBC games rarely exceeded 4 MiB.

by on (#70114)
Yeah to use the lower bit not only it would have to be disconnected from the CHR-RAM, but also you'd have to use "4kb switching mode" and to have both CHR registers loaded with the exact same value. If you use the 8kb switching mode, CHRA12 will simply pass through, and the latched value will be ignored.

I agree that there is no point in expanding the MMC1 by adding more bits, and that wasn't the point of my original post. There is however points in expanding it to support more RAM/ROM at least with iNES 2.0 additional flags. As long as the thing is possible with a real MMC1 by altering a real MMC1 board.

EDIT : I am reading that article about compression right now and it's fairly interesting. I think information about compression methods is definitely lacking on NESdev... maybe I/we should work on that ?

by on (#70115)
Bregalad wrote:
I think information about compression methods is definitely lacking on NESdev... maybe I/we should work on that ?

To me it seems like people here are afraid of compression or something... Rarely does anyone use anything beyond simple LZ or RLE. And a lot of people seem to think that you need lots of RAM in order to use compression, which is not true, since there are many ways to perform decompression "on the fly".

Maybe we could "wikify" the compression schemes we have personally researched, and also offer downloads of the compressors and decompressors we have coded. I have C encoders (with poor error handling, as they are supposed to "do the job" rather than babysit the user) and 6502 decoders for that slightly modified Codemasters codec and for my own byte-oriented LZ scheme. If anyone wants to use those I can dig up the most recent versions.

by on (#70116)
Yeah we should definitely share the results of our researches.
Personally I made a RLE-like compression for maps in my game, and that's about all. It is fairly good, and allows me to compress it "by hand" (without a tool). However maybe something better could be made up.

I also investigated the huffman algorithm and made an encoder native to the NES but it REALLY sucks, I should port it to C or Java and re-realase it so it's effectively usable by people (including me haha).

by on (#70122)
Yeah, I agree it is kinda pointless but meh....whatever. It's not worth making. :P



And yeah, more compression would be good. :)

by on (#70128)
tokumaru wrote:
To me it seems like people here are afraid of compression or something... Rarely does anyone use anything beyond simple LZ or RLE. And a lot of people seem to think that you need lots of RAM in order to use compression, which is not true, since there are many ways to perform decompression "on the fly".

I think this has something to do with the fact that DEFLATE, an LZ77+Huffman family codec invented by Phil Katz that has since become one of the most widely used, uses a 32768-byte window. Even the version of LZSS used by the Allegro library and the GBA BIOS needs a 4096-byte window. I guess that in those cases where an LZ77-family codec with a 256-byte window would perform well, a game could freeze sprites during decompression and stick the window in the shadow-OAM buffer.

Quote:
Maybe we could "wikify" the compression schemes we have personally researched

Great idea. I could polish up a toolkit out of the Golomb, exp-Golomb, and Canonical Huffman codes that I had been working on in the process of making that e-book reader. Golomb and exp-Golomb don't need a lot of memory to decode, and Canonical Huffman needs only a few tiny tables in ROM (one for each code length and one to translate ranked frequencies to entries), not a bunch of RAM like LZ77 family does.

by on (#70130)
tepples wrote:
Even the version of LZSS used by the Allegro library and the GBA BIOS needs a 4096-byte window.

Do LZ77 and its relatives really need that much memory? AFAIK, the sliding window slides over the data that has already been decompressed, so you can read directly from the output area when copying strings. At least that's how the LZSS variants I coded for the NES work.

I imagine that if you use another layer of compression (such as huffman), then you'd need more memory. Also, LZ78 and its relatives need a dedicated dictionary instead of a sliding window, so they also need more memory... But basic LZ77 by itself? I don't see why you'd need a lot of RAM besides the area you are decompressing to.

My original comment was not that people think that compression schemes need a lot of work RAM, I meant that they think that a lot of RAM is necessary to hold the decompressed data. The general impression is that you can only compress level maps if you have 8KB of RAM to decompress the whole map at once, but this is not true, as there are many ways to decompress the data progressively, using small amounts of RAM.

by on (#70133)
I'm not an expert of LZ-ish compression, but as far as I understand, it relies on the same strings of data to be present multiple times in a file to compress it. If you use a 256-byte window, the probability you have a string of the same data of a decent length is low (if the string is like 3 bytes and that you can compress it as a 2-byte reference, you don't gain MUCH from it). So I suspect you won't compress data very well in a randomly given case. I might be totally wrong, it probably depends on the kind of data, you can't know without trying.

The problem is that in a NES game you don't want to compress a large file as a whole, but to access parts of this file at this time. Typically the case where you decode individual screens in a compressed map. This makes most info you find about compression on the net almost useless because they assume you have much more RAM at your disposal, and that you are compressing large chunks of data.
Even the C64 has a ridiculous amount of RAM compared to the NES !

It is however I guess possible to decode all the data from the whole "file" into a circular 256-byte buffer (overwriting history longer than 256 bytes ago), and stop decompressing when the part of it you want to acess (the screen) has just been decompressed. Needless to say, this will be slow, but it'll work. Then you'd probably want to shift data so that it starts at the start of your 256-byte cicrular buffer, or else it'll be needed to check for overflow each time you want to acess data in it for future use.

For Huffman, its completely different. It relies on the fact some bytes are more probable than other to compress data. If that's not the case then you shouldn't even be considering huffman compression as it'll expand the data.

However, if this is the case, all you'll need is a table, and some code to use it, which will take some ROM space but hopefully not too much. You don't have random acess to data, but it's possible for example to "stop" the compressed stream, and have it restart anywhere else without loosing efficiency of compression (at worst you'll loose 7 bits).
So you could compress each map in a level or each sentence in a dialog separately, have pointers to each, but use the same table to decompress everything.
You only need a buffer of the size of one map/one sentence to store the decompressed data. No need for a 256-byte circular buffer or anything.

In this regard, it is more like RLE, and this is a huge advantage over LZ. No need to "redecompress everything from the start" every time.

Apparently there also exists some sort of arithmetic coding that is an improvement of Huffman (also based on the probability stuff). As far I know it works on a theory with fractional numbers, I'd have to see an implementation of it in binary to judge how well it could perform on the NES, but it sounds like it could be quite an optimal algorithm.

The "redecompress everyting from the start" and the 256-byte circular buffer on LZ compressions is probably the main problem, but if it compress well it's without a doubt worth implementing.

by on (#70137)
tokumaru wrote:
tepples wrote:
Even the version of LZSS used by the Allegro library and the GBA BIOS needs a 4096-byte window.

Do LZ77 and its relatives really need that much memory? AFAIK, the sliding window slides over the data that has already been decompressed, so you can read directly from the output area when copying strings.

If the output area is VRAM, then reading from the output area can be done only during vertical or forced blanking, and use of audio channel 5 makes it occasionally skip a byte. Double-clock errors can even compound themselves if the erroneous data is itself referenced by a later run.

Quote:
The general impression is that you can only compress level maps if you have 8KB of RAM to decompress the whole map at once, but this is not true, as there are many ways to decompress the data progressively, using small amounts of RAM.

Many of which invite destructibility tradeoffs, which an article about compression might have to mention.

Arithmetic coding gives about a 5 percent improvement over Huffman. For a period of time, it was thought to be patented until someone discovered a "range coder" that predated IBM's "Q-coder" patent application. During this time, JPEG included both Huffman and arithmetic coding options, but this improvement wasn't considered to warrant paying royalties. In addition, bit-oriented methods such as Huffman have better random access and error recovery than arithmetic coding.

by on (#70138)
tepples wrote:
If the output area is VRAM, then reading from the output area can be done only during vertical or forced blanking

Well, the same goes for writing, which means that the need to buffer the data is a limitation of the system, not the compression scheme.

But yeah, if you want to decompress tiles without turning rendering off you will need to buffer the data. This is not something I would recommend in a game with a lot of frame processing, it would be wasteful. If you do need to update tiles during gameplay, I suggest you keep them uncompressed.

by on (#70139)
tepples wrote:
If you were to take the SUROM superbank concept up to 11, you'd only get 4 MiB because the lowest bit of CHR bank register is busy switching between the first and second banks of CHR RAM.

It'd be possible to take it to 8 MiB, but then you could use only 4 KiB of the CHR RAM. But then even SNES and GBC games rarely exceeded 4 MiB.


Well I would figure you'd disconnect any control to the CHR-RAM from the MMC1 so it would appear as it does on a UNROM board. Then you'd have all 5bits free for PRG-ROM. 8MiB would be massive, and as you said even 4MiB would match late SNES games.

But you see my point that you could just take the same idea of reusing the CHR register a bit further. You could use 16KB switching mode and duplicate the fixed bank into each 256K section so that you have 7680K +16K (fixed) of ROM space. More than most developers would have time to efficiently fill I think. Even if you don't take the one CHR line you said would need to be disconnected you could still get around 3584K + 16K out of MMC1.

by on (#70140)
tokumaru wrote:
tepples wrote:
If the output area is VRAM, then reading from the output area can be done only during vertical or forced blanking

Well, the same goes for writing, which means that the need to buffer the data is a limitation of the system, not the compression scheme.

The idea with a 256-byte window is to use the same buffer for LZ77 history and preparing a copy to VRAM.

by on (#70142)
So overall the RAM memory requirement are :
- RLE : Just a few pointers & counters, memory to hold a portion decompressed data
- Huffman : Just a few pointers & counters, memory to hold a portion of decompressed data
- LZ : A few pointers&counters, A 256-byte (or larger) circular buffer (which includes memory to hold a portion of decompressed data)

Random acess :
- RLE : Can be simulated with pointers anywhere in the compressed stream
- Huffman : Can be simulated with pointers anywhere in the compressed stream (at worst there is a 7-bit loss)
- LZ : You need to start decompression from the very start to access data.

ROM memory requirements (w/o code to handle decompression) :
- RLE : Compressed stream, pointers to part of compressed data
- LZ : Compressed stream, offset/lenght info for parts of compressed data
- Huffman : Compressed steram, pointers to part of compressed data, lockup table for binary tree

Anyone who knowns more about other algorithms is welcome.
I'll probably port my huffman stuff to C and release it to the public so that it could be taken advantage off... the most algorithm we known and we try to implement on the NES, the best ! This make it more likely to compress data as efficiently as possible.

by on (#70145)
tepples wrote:
The idea with a 256-byte window is to use the same buffer for LZ77 history and preparing a copy to VRAM.

Yeah, I get that. But the only reason you need that window/buffer is because the NES won't let you write freely to VRAM, hence it's a limitation of the console, not the compression scheme.

by on (#70146)
Let's go split the Data Compression discussion out of this thread.

by on (#70170)
I was thinking of splitting it here, but I found too many posts that talked about both the compression and other space-related aspects of a Pokemon clone. Feel free to PM me the exact split point(s).

by on (#70175)
I have implemented the compression algorithms found on that page. I also implemented another filter, where it also uses the Top-Left pixel in addition to the top and left pixels.

I also made a major change, when doing RLE on the prediction images, the value 0 appears far more often than any other, which makes sense because these low numbers come from sort order on how popular certain patterns are. So I boosted 0 values, encoding them in just 1 bit. In 2bpp mode, a value of 1 is second place, so it gets 2 bits. Values 2 and 3 get 3 bits.
I am not using this scheme on the regular RLE that is run on the original image, just the prediction images which have more 0 and 1 pixels.

Note that when you use the predictors, you need to save which permutation of the color values was used. For 2bpp data, one possible way to store a permutation takes up 5 bits. Looking at 2 pixels with at 2bpp, that's 16 possible entries in the lookup table, and can be encoded in 10 bytes.

The second prediction method I used looks at 3 pixels, so there's 64 possible entries, for 40 bytes, far more overhead.

For 1bpp data, you don't need to store as much extra overhead data, 4 bits for the 2-pixel predictor, and 8 bits for the 3-pixel predictor.

These are illustrations of what the prediction images look like.

First: Original Image
Second: Predicted Image using Top and Left
Third: Predicted Image using Top, Left and Top-Left.


Bubble Bobble TI83 Title screen:
Image Image Image
Raw: 768
RLE: 669
2-pixel filter + RLE: 600 (+1)
3-pixel filter + RLE: 642 (+1)

Chu Chu Rocket Title:
Image Image Image
Raw: 15360
RLE: 8073
2-pixel filter + RLE: 7845 (+10)
3-pixel filter + RLE: 5702 (+40)

Pokemon:
Image Image Image
Raw: 784
RLE: 473
2-pixel filter + RLE: 437 (+10)
3-pixel filter + RLE: 457 (+40)

Dur Butter:
Image Image Image
Raw: 5408
RLE: 1623
2-pixel filter + RLE: 1440 (+10)
3-pixel filter + RLE: 1470 (+40)

Donkey Kong Land:
Image Image Image
Raw: 5760
RLE: 3647
2-pixel filter + RLE: 3110 (+10)
3-pixel filter + RLE: 3078 (+40)


The RLE specified on that page isn't good for long runs greater than 63 pixels long, the Chu Chu Rocket Title picture has lots of those.

Looks like the 3-pixel filter only really helped with the "Chu Chu Rocket Title Screen" image, since it eliminated the vertical gridlines.

by on (#70179)
Yeah, lets keep it here, it's interesting to see how all these work, and for the 2 pixel compression, I was thinking of it using one byte from CHAR and then repeating that X times in a new byte, but using the MSB's for the pixel and then the repetition bits is a great idea, and the obvious one. But I am probably going to mess with some RLE compression now that it's making sense amd justified. It'll save enough space for the 1K lookup table, so it's definitly something I am going to do. Compression isn't so bad, it's using it and justifying the lookup table space you need to create to keep the speed of processing as low as before and completely understanding it.


Thanks for the idea guys.

by on (#70193)
Well, tools are definitely badly lacking when it comes to compression.

A great thing would be a tool that takes a .bin file or even a .asm file parsing .db statements (and ignoring everything else), compressing the deal with a couple of algorithms which are feasible on the NES, and display the results. Then the user is free to use data from the most efficient compression method (or the one he feels more implementing).

But usability for a game developement case should be kept in mind. Typically for storing text or maps, you'd have the following :
Code:
TextPointers
  .dw Text1
  .dw Text2
  .dw Text3

Text1
  .asc "Hello guys !"
Text2
  .asc "I will dominate the world!"
Text3
  .asc "All oposition is futile"


Having this compressed in a single .bin file is completely unusable.
So a tool that would parse the original data, compress it, and re -output it keeping the labels but replace .asc or .db statements with compressed data would be amazing. So it would be like that :

Code:
TextPointers
  .dw Text1
  .dw Text2
  .dw Text3

Text1
  .db $64, $06, $1a, $2b, $6c   ;"Random" compressed data comes here
Text2
  .db  $1a, $7b, $84, $9a
Text3
  .db $9c, $5d, $4e, $8a, $9c, $1a



Having every text / screen in a separate file is not practical, you don't want 100+ tiny files in your folder to be compressed.

Of course if anyone has a better idea, this is welcome.

I'll try to make a tool like that for RLE and huffman coding (the only codings I actually understand fully... so far) but since I'm not a PHD in non-Nesdev computer science and because I'm busy those times it will take ages for me to get something decent. I could probably get something done slightly faster using Java but I bet people would rather see it being made in C(++) compilable into an .exe file which doesn't need JRE.

There is lot of C++ sources for Romhacking oriented (de)compression here but I don't know how to use that !

by on (#70194)
Then don't store the original text in ASM source files. Create your own file format and write a quick tool in C, perl or python to compress it and emit temp .s, .inc files. This is easy to handle with Makefiles or whatever your favorite build system is.

by on (#70212)
Quote:
Then don't store the original text in ASM source files.

What about if I already had data made that way before I even planned to have it compressed ?
Otherwise you're right, you'd want it in plain text with marker for end of every message/map that the compressor should use to make a "break".

It's this "break" ability, necessary for any practical use, that all compressing tools so far lacks badly.

by on (#70217)
Bregalad wrote:
Typically for storing text or maps, you'd have the following :
Code:
TextPointers
  .dw Text1
  .dw Text2
  .dw Text3

Text1
  .asc "Hello guys !"
Text2
  .asc "I will dominate the world!"
Text3
  .asc "All oposition is futile"


Having this compressed in a single .bin file is completely unusable.
So a tool that would parse the original data, compress it, and re -output it keeping the labels but replace .asc or .db statements with compressed data would be amazing.

That or it'd take something like wiki markup and make a label for each level-(something) heading. That's what I had planned for an e-book reader: write the book in something much like MediaWiki markup, and the converter would paginate it, compress it, and make the needed address tables.

Quote:
I could probably get something done slightly faster using Java but I bet people would rather see it being made in C(++) compilable into an .exe file which doesn't need JRE.

For me, it's not the JRE (I could just as easily apt-get install openjdk) as much as Oracle v. Google. A lot of my tools are written in Python nowadays; it's easier to get data structures such as a hash table built and unbuilt in that than in C and the like.

by on (#70224)
You could also compress text down to 6 bits for the value, since there's a total of 96 needed values for text, so you can cut out the 128th value bit for it and compress is and save 1 bit per letter.

by on (#70229)
Most English text contains enough entropy to compress it down to 5% of its original size. Striping the top two bits only gains you 25% bit savings. One can do much better....

by on (#70230)
Yeah, and my point was that's why we need tools to do this.
The only compression method that can be done without any tools is RLE (unlike you're a superhuman or something).

by on (#70231)
Someone could probably to huffman on paper. Maybe a savant could do it in his or her head. Just saying...

But seriously, do and experiment. Create a simple, custom file format and write a compression tool in your favorite qucik+dirty language. I like C/C++ and perl. Tepples like Python. One of my coworkers writes simulation software in BASH (slower than sh*t though).

Do you store your (raw) strings in Pascal format (first byte = strlen), or in C format (terminates on NULL)?

Have your tool compute how many bytes would be consumed by the raw text + lsm/msb pointers. Have it compute the byte size of the output and compare to get a "percent space saved".

Then figure out how many bytes are taken up by the decompresser in 6502.

This could make for an interesting competition...

Bregalad, I don't need text compression at this time. However, if you come up with something easy to invoke from a Linux tool build chain (ie, works well with Make and runs on the Linux CLI), then I would be happy to consider it when the time comes for me to use compressed text.

However, I think that if you were making a tool for the "community" then you should consider that some people develop on Macs, some on Linux/bsd/solaris and some on Winblows. "EXEs" are probably not the best bet. Perl and Python are portable (enough) and writing parsers in them is sooo much easier than in C/C++. Java seems like overkill to me. I don't even have a jre/jdk on my dev box, and hope to avoid needing it.

EDIT: Another consideration for NES text compression is decompression speed and code size.

Also, in my reverse engineering of Crystalis I noticed (but never fully delved into) that the text is largey dictionary compressed. There is a dictionary of sorts. (from memory, so I may be wrong): Certain words were stored in plain text. Some were only represented by a token, and some were mixes of tokens (word fragments) and normal letters.

One would want to extract individual sentences from a corpus of text. But compressing each sentence / paragraph on its own would be inefficient. Personally, I think that NES text compression would be best with a global word + word fragment dictionary (like Crystalis), and then compress that token stream with something else.

by on (#70559)
The way old Infocom text adventures (best known for the Zork series) encoded text may be of interest here. http://www.inform-fiction.org/zmachine/ ... ect03.html

Basically, they used three five-bit characters per two bytes, with an indicator bit left over that marked the end of words. Dictionary compression was also used, if my memory serves right. These games had absolutely massive amounts of text and achieved a relatively impressive text compression (obviously nothing as efficient as DEFLATE or something like that, but still very nice) that could be implemented with minimal computational power. It's worth giving a read, at least.

by on (#70560)
Thanks for the post. What I find interesting is the use of escape codes embedded in the compressed text to signal a change in fonts / decodings.

by on (#70561)
I saw the Zelda Oracles games using LZ78 for the level compression for dungeons. LZ78 is random access, so you can start from anywhere, and your dictionary is just a page in ROM somewhere else, instead of a sliding window.
I just wonder if there is a better way to encode LZ78 so it isn't so big.

I hope I'm not jumbling terms here, I'm just referring to all explicit dictionary-type compression as LZ78.

by on (#70562)
Dwedit wrote:
I'm just referring to all explicit dictionary-type compression as LZ78.

I don't think this is LZ78... to my knowledge, LZ78 starts with a dictionary with only the basic character set, and adds entries to it as the data is decompressed. It certainly doesn't allow random access, because of how the dictionary is generated from character combinations that are found along the way.

I think LZ78 would be a bad choice for the NES, because for it to be efficient a large dictionary has to be used, possibly needing more RAM than the NES has.

What you described is a generic dictionary compression, that uses pointers to strings defined in ROM, right?

by on (#70580)
Dwedit: I saw your post in the talk page for Wikipedia's article about LZ77 and LZ78. Something about it looked dubious.

tokumaru wrote:
to my knowledge, LZ78 starts with a dictionary with only the basic character set, and adds entries to it as the data is decompressed. It certainly doesn't allow random access, because of how the dictionary is generated from character combinations that are found along the way.

Correct. The basic LZ78 algorithm is to take the most recent dictionary word and add a character to produce the next dictionary word, and LZW uses the first character of the next word for this.

Quote:
I think LZ78 would be a bad choice for the NES, because for it to be efficient a large dictionary has to be used, possibly needing more RAM than the NES has.

What you described is a generic dictionary compression, that uses pointers to strings defined in ROM, right?

In other words: "tepples, get back to work on that Huffword implementation."

by on (#70582)
tepples wrote:
tokumaru wrote:
What you described is a generic dictionary compression, that uses pointers to strings defined in ROM, right?

In other words: "tepples, get back to work on that Huffword implementation."


Interesting. If by "huffword" you mean: Huffman compression where bit combinations could represent single characters or word fragments or entire words.

I was thinking of developing the above algorithm, but with a single global dictionary.

We should probably split this thread, as it is now about text compression and not "Mapper #1".
Split where?
by on (#70583)
It morphed from 1. MMC1 to 2. someone's cockfighting game on an MMC1 board to 3. data compression for a cockfighting game. There are replies discussing both 1 and 2 and replies discussing both 2 and 3. I can't split whole posts from one topic to a new topic, but I can't split a single reply into two replies. So please answer this post.