CHIP-8 for Gamebuino

[wuuff]

I have ported a CHIP-8 interpreter. It can load CHIP-8 roms off the SD card, and controls can be configured to play most CHIP-8 games. Unfortunately the performance is too slow to be all that usable.

The ram of the CHIP-8 is 4kb, while the Gamebuino only has 2kb. This means that I had to swap out CHIP-8 ram to SD constantly, and keep a tiny buffer on the Gamebuino for that ram. The SD library and screen buffer together take up about half the available ram, and the other globals, plus extra space for stack variables, means that there is very little room for the buffer. I started with the smallest buffer I was comfortable with using at 156 bytes. This translates to 26 "pages" of memory, which I wrote out to up to 26 separate files on the SD card, each indexed by a different letter (hence 26). This kept the code for swapping to and from the SD card very simple. I tried increasing the buffer size, but performance actually appeared to be worse (perhaps because of the increased cost of reading and writing a larger buffer). Therefore, I don't think there is an easy way to improve performance much without redesigning the way I swap the ram. I know I could do a read-only buffer for code, but I would need to have room for two buffers, and I can't increase the size of the existing buffer very much before it starts to corrupt ram. If anybody has any other ideas about improving performance, I would be glad to hear them.

The way roms are selected to be loaded from the SD card is by using a modified version of the Gamebuino menu library function that displays strings stored in ram instead of progmem. I actually reuse the buffer for the CHIP-8 memory for the strings, so there is not that much space for them. I wouldn't put more than 10 roms on the Gamebuino at a time, because it will start corrupting data after about 10 full-length filenames. This file selector menu might be useful if it could be made more generic, and I might try to use it for my AttoTracker if I can get it working. Reading and writing to the SD card is frustrating because of how many resources it uses...

Since the CHIP-8 has 16 keys, and the Gamebuino only has 7, I knew that not all CHIP-8 games would work on the Gamebuino, but most games seem to use a small subset of the keys. I decided to make it so that the key bindings can be chosen before loading a game, reserving C for the menu. The current set of bindings is saved in EEPROM.

While somebody has already started work on a CHIP-8 interpreter for the Gamebuino previously, I was interested in the challenge of being able to support loading roms from the SD and supporting the full address range of the CHIP-8. I guess I succeeded in everything except it being usable for anything...

Download binary: CHIP8.zip
Source code: https://github.com/wuuff/chip-8-gamebuino

[naed]

Nice work

[rodot]

Wow, I never thought of using the SD card for paging RAM like this. Impressive work!

[Sorunome]

This is looking quite awesme!

Also, just a suggestion about the speed:

Reading the wikipedia article about CHIP-8 it seems like the 4K is not all ram, so you could maybe load the program to flash and then use the ram only for the dynamic stuff?

EDIT: since CHIP-8 is interpreted that would actually be really simple, except if CHIP-8 allowed self-modifying code. But if it doesn't, just load the program into flash and fetch the bytes from there to read from.

Also, your loading code seems very....sub-optimal.
https://github.com/wuuff/chip-8-gamebui ... no#L90-L97
You only load memory stuff 20 times a second, to greatly increase that just do that updating still inside of the while-loop but outside of the gb.update() if-condition!

EDIT2:
For writing to flash you basically do

Code: Select all

write_flash_page((const char*)ADDRESS_IN_FLASH, rambuffer);


where ADDRESS_IN_FLASH is 128-bytes alligned and rambuffer is a 128-bytes buffer. That will be stored to flash there then. You could e.g. reserve the 4k of flash right before the bootloader for that, starting at 0x6800. Just make sure that your compiled arduino program won#t be larger than 0x6800 = 26624 bytes and then you are good to go!
Reading a byte would be then with like

Code: Select all

uint8_t b = pgm_read_byte(ADDRESS_IN_FLASH);


[wuuff]

Everyone, thanks for the comments and feedback!

Wow, I never thought of using the SD card for paging RAM like this. Impressive work!

Thanks. That means a lot coming from you.

Reading the wikipedia article about CHIP-8 it seems like the 4K is not all ram, so you could maybe load the program to flash and then use the ram only for the dynamic stuff?

EDIT: since CHIP-8 is interpreted that would actually be really simple, except if CHIP-8 allowed self-modifying code. But if it doesn't, just load the program into flash and fetch the bytes from there to read from.

The CHIP-8 does support self-modifying code, because all ROM data is loaded starting at memory address 0x200 at the start of execution, and there is no separation between code and data address spaces. However, I think that there aren't very many ROMS that rely on this, and the performance benefit might make it worth not supporting self-modifying code. Thanks for the info on writing to flash. I didn't really consider this a valid possibility before because I wanted to support everything, but I think it might be a good trade-off.

Also, your loading code seems very....sub-optimal.
https://github.com/wuuff/chip-8-gamebuino/blob/master/memory.ino#L90-L97
You only load memory stuff 20 times a second, to greatly increase that just do that updating still inside of the while-loop but outside of the gb.update() if-condition!

You're right, my loading code is terrible. I basically just got lazy and didn't want to do the basic calculations about loading pages of memory at a time. I think it tries to do it more than 20 times a second because I set the FPS to 120 at the start, but you're right that loading it a byte at a time is really inefficient.

[Myndale]

This is terrific work!

I had a play with the code myself today and managed to find a few easy to implement optimizations. As others have noted the game loading doesn't have to be that slow, it's actually waiting for a complete screen refresh (1/60th of a second) for every byte. I had to remove that loop for other reasons, but doing so caused games to load almost instantaneously.

Gamebuino uses 504 bytes for its backbuffer but chip8 needs only 256. I modified the Gamebuino library to accept a ptr to the backbuffer at runtime and I modified the display and flip routines to work with a 256-byte buffer...that's bought you another 248 precious bytes of working space.

The main performance issue, as far as I can tell, is due to chip8_execute() only being run twice per game loop. That's a huge amount of overhead per instruction. Increasing it to something higher (I used 16) gets you pretty-much up to full speed.

The other main change I made was combining all the buffers (display, cache, rom table etc) into a single block. That seems to let you push the overall size a bit higher, probably because of reduced memory fragmentation.

I did have a go at implementing a basic 2-way set associative cache like what you see on things like the PSP/MIPS platforms etc but it added significant complexity for not very much gain. My guess is the 512-byte buffer in the SD card library is effectively caching memory to begin with.

I've committed my changes to a fork at https://github.com/Myndale/chip-8-gamebuino, they're in the "optimizations" branch. I've also added a pull request to make it easier if you want to take a look.

[wuuff]

This is terrific work!

I had a play with the code myself today and managed to find a few easy to implement optimizations. As others have noted the game loading doesn't have to be that slow, it's actually waiting for a complete screen refresh (1/60th of a second) for every byte. I had to remove that loop for other reasons, but doing so caused games to load almost instantaneously.

Gamebuino uses 504 bytes for its backbuffer but chip8 needs only 256. I modified the Gamebuino library to accept a ptr to the backbuffer at runtime and I modified the display and flip routines to work with a 256-byte buffer...that's bought you another 248 precious bytes of working space.

The main performance issue, as far as I can tell, is due to chip8_execute() only being run twice per game loop. That's a huge amount of overhead per instruction. Increasing it to something higher (I used 16) gets you pretty-much up to full speed.

The other main change I made was combining all the buffers (display, cache, rom table etc) into a single block. That seems to let you push the overall size a bit higher, probably because of reduced memory fragmentation.

I did have a go at implementing a basic 2-way set associative cache like what you see on things like the PSP/MIPS platforms etc but it added significant complexity for not very much gain. My guess is the 512-byte buffer in the SD card library is effectively caching memory to begin with.

I've committed my changes to a fork at https://github.com/Myndale/chip-8-gamebuino, they're in the "optimizations" branch. I've also added a pull request to make it easier if you want to take a look.

Wow, thanks for the improvements! Now the games run much faster, to the point that some of them are very playable! I didn't think of recycling some of the screen buffer, but it makes a lot of sense since the CHIP-8 doesn't need all of it. Now page sizes can be huge, relatively speaking. This seems to result in some smaller games not having to swap at all, allowing them to run blazing fast. In fact, some run so fast (such as BLITZ.ch8) that they run too fast, making them unplayable.

There are a few reasons I didn't originally run chip8_execute more than twice per frame. One thing I noticed is that running it 16 times per frame means it ends up having a frame skipping effect, because any changes to the display made in the last 16 frames appear all at once. For loops with less than 16 instructions this can be quite noticable. That's why I originally just set the framerate higher instead (but the overhead from gb.update() really does seem to take a toll!). The other reason is because when I first increased the number of instructions executed I didn't notice much performance improvement, but I think I tested it with the Trip8.ch8 rom, which doesn't improve much from this. The bottleneck in that rom is still the paging. Since some of the roms run way too fast when running at 16 instructions per frame, I decreased it back to 2 and many games are much more playable at this speed, although this seems like something that could be adjusted (perhaps by the player to suit each game?). For example, at 16 instructions per frame, some games run extremely fast for certain parts of the game, but much slower in others (for example, the aliens in INVADERS.ch8 move extremely fast as long as the player doesn't shoot or move, the pieces in TETRIS.ch8 fall almost instantly, while the code to check whether a line has been completed is much slower, and the ball in BRIX.ch8 is so fast it almost seems to teleport until it collides with a brick, at which point it pauses for the collision). This is clearly caused by some parts of the code not needing to swap, while others do. I think just having the much larger page size gives a great performance boost, but increasing the number of instructions executed per frame causes some problems.

Another thing I noticed is that in the optimized version, the built in (loaded into the bottom bytes of CHIP-8 ram at startup) CHIP-8 font of hex digits does not display in games anymore. I'm not sure what happened there, but I'll have to investigate that.

I like how you centered the CHIP-8 screen instead of leaving it at the top left. I had been thinking that it should be eventually centered, but I never bothered to do it. I think the most exciting thing about your optimizations is that they show that arbitrary CHIP-8 games may actually be loaded from the SD card and run on the Gamebuino at playable framerates!

I tried to merge your changes, but I accidentally merged with my master branch instead of a separate optimizations branch, and now I have made it so that I reverted the merge and can't re-merge your pull request, so could you issue another pull request? Sorry, I don't have much experience with pull requests and I didn't realize that Github would make them irreversible.

[Sorunome]

What about instead of calling chip8_execute you do it like every n milliseconds and to update the gamebuino screen you just call whatever. That would look like

Code: Select all

while (true) {
    cip8_execute();
    gb.update(); // make sure that the screen gets updated at 20FPS or whatever you set it to
    delay(20); // pause for 20 milliseconds
}


[Sorunome]

Also, when you feel this is ready, don't forget to add it to the Games Library! ^.^

[wuuff]

Also, when you feel this is ready, don't forget to add it to the Games Library! ^.^

I think it still requires some polish before I would post it on there. I actually hadn't thought of putting it on the games page because it didn't really feel like a "game", and I have posted a few ports of other games in the forums that I wasn't sure about posting on the gallery either. I know that there is also a tag for games still in alpha, but I hadn't been comfortable posting incomplete or derivative projects onto the games page. I'll think about posting this onto the gallery now that you mentioned it.