Small C for NES: A Curious Journey

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Small C for NES: A Curious Journey

Post by rainwarrior »

Well, I'm not the one who is demanding it fit in NROM. ;) I have advocated AxROM elsewhere, and I think a dedicated 32k for C code is a pretty reasonable amount of space.
User avatar
qbradq
Posts: 972
Joined: Wed Oct 15, 2008 11:50 am

Re: Small C for NES: A Curious Journey

Post by qbradq »

Wow, some really great discussion on this topic! Let me be clear that I think cc65 is a great C compiler, it's just that some of the idioms of C are not efficient on the 6502. Seriously, think about a three-dimensional array. It's a pointer to an array of pointers to arrays of pointers to arrays. How is that going to be efficient on any platform?

Personally I want a language that cooperates well with assembly, that is easy to read and maintain and that leverages the advantages of the platform. Honestly I don't understand the portability concerns. If I wanted to port a game from NES to another platform I'd want to re-code it. Finally, code (and compilers) that are cross-platform have more difficulty leveraging the platform they are targeted for.

So this curious journey is now leading to the idea of a language that implements one or more design patterns for banked execution. Here are the patterns I am aware of. If someone is aware of others, please let me know.

Banked Data
In this model a fixed segment contains all executable code and banked segment contains static data, which is either referenced in-place or moved to RAM. This is very easy to implement but is limited in executable code size.

Banked Contiguous
This model is what Metroid uses. The common code is stored in a fixed segment. All data and code required for a given area of the game is stored on a separate banked segment. In any given area of the game, the full program code is present in a contiguous address space. This works well for medium-sized project as Metroid demonstrates, but influences the design of the game.

Banked Data with Trampoline
I am not aware of any game that uses this, but I haven't' studied many. This is the scheme I came up with for my MMC1 projects. 32K of program space is available, and routines in the fixed segment read data from banked segments and copy it to RAM, then restore the banked segment back to program space. Works pretty well but still limits executable code size.

Banked Library and Data
This is what SMB3 uses. All common code lives in two fixed segments. Another segment is used to dynamically bank in data tables as needed, and a fourth used to dynamically bank in program code as needed. Program code is organized into several libraries with a consistent header or entry point method, and contain any data tables that might be specific to that library.

Program Banking
Software is segregated into separate self-contained programs. A small fixed ROM or RAM-loaded trampoline is then used to swap between programs.

Out of all of these, I like the idea of banked libraries as found in SMB3. Let me know what other banking strategies you may have in mind!
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Small C for NES: A Curious Journey

Post by tepples »

Almost all multicarts, except CNROM multis such as Donkey Kong Classics, use Program Banking to launch the selected activity.

In addition, Action 53 uses Banked Data with Trampoline to pull lines of instruction text and compressed screenshot tiles out of their hiding places in other banks. At power-on and reset, it copies an "interbank fetch" subroutine into RAM that copies a block of data starting at a given 24-bit address to a fetch buffer in RAM. (Bit 15 of these addresses is always 1, as in Super NES LoROM.)

I imagine that Metroid's use of Banked Contiguous comes from its FDS heritage, as bank switching is extremely slow on that mapper.

Are SMB3's DPCM samples in the fixed bank or in a switchable bank? If they're in a switchable bank, it can't really use the full Banked Library and Data except in scenes whose music uses no samples.

The best compromise I can think of is a subset of Banked Library and Data. The ROM is divided into a 16K fixed bank and a 16K or 8K switchable bank. Routines that need less than 16K of data go in their own bank. Routines that need to access data in more than one 16K bank go in the fixed bank, as do interrupt handlers and routines called by routines in multiple banks.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Small C for NES: A Curious Journey

Post by Bregalad »

Seriously, think about a three-dimensional array. It's a pointer to an array of pointers to arrays of pointers to arrays. How is that going to be efficient on any platform?
Really ? I thought arrays were "flattened" to a single dimentional arrays like in my previous example. However now I am not too sure. The confusion between arrays and pointers in C has always puzzled me to be honest. It's just one of the bad things about the language. I admit that C is not a very good language technically, it is just that it is a standard, and that it is extremely portable.

The part about "idioms" might be true, but I think it is possible to do a clever analyzis and re-organize the data in order to be efficient on 6502 : Auto variables becomes static, index values to array are placed in X and Y registers, and strength reduction is always applied whenever possible. There is another million of optmisation steps that can make code better each time, and turn horrible code into good code. That's how modern compiler works (I guess).
The tricky part is what I'll call "stack deletion" optimisation. However SDCC already does something like this. Now the question is if it is better to add 6502 to SDCC, or to modify CC65 in order to apply stack deletion, or to continue to code games in assembly or extremely poor generated code from C.
Personally I want a language that cooperates well with assembly,
C cooperates extremely well with assembly. The usage of asm() statmens can inline assembly code, and with separate compiling and linking it is possible to mix portions of C and assembly (plus a ton of other languages, but that would not apply in our case).
Honestly I don't understand the portability concerns. If I wanted to port a game from NES to another platform I'd want to re-code it.
Oh, really ?
Well, I'm not the one who is demanding it fit in NROM. I have advocated AxROM elsewhere, and I think a dedicated 32k for C code is a pretty reasonable amount of space.
I get your point. However it is a shame to be limited to make games where few realtime action takes place AND small games that uses a large mapper, isn't it ? What if you actually wanted to make a large game, that would "normally" fit in AOROM for instance (256kb) ? Would you have to use MMC5 with 1MB PRG-ROM just because you used CC65 ?
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Small C for NES: A Curious Journey

Post by tepples »

Bregalad wrote:What if you actually wanted to make a large game, that would "normally" fit in AOROM for instance (256kb) ?
It takes a lot of art to fill that much space. If you have a Rareware budget for artists, you can probably get a Rareware budget for programmers too.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Small C for NES: A Curious Journey

Post by Bregalad »

I'll meditate on this. However, my former goal was to make some simple games to proof to people I'm a serious programmer, and that way artists and other people would joint, and we'd be able to make bigger / better games.

However, sounds like for now I just proved that I am a good programmer but I can't keep focus on one project without immediately moving to another, etc... I think it's my nature to be like this ^^ Wonder what would have happened to me if I was born back when computers didn't exist.
zzo38
Posts: 1096
Joined: Mon Feb 07, 2011 12:46 pm

Re: Small C for NES: A Curious Journey

Post by zzo38 »

tepples wrote:
Bregalad wrote:What if you actually wanted to make a large game, that would "normally" fit in AOROM for instance (256kb) ?
It takes a lot of art to fill that much space. If you have a Rareware budget for artists, you can probably get a Rareware budget for programmers too.
There may be things other than graphics in there, though. Maybe you will fill up a lot of space with the level data if your game has a lot of level data? (However, depending on the game, this might not be necessary: MATCHNUM uses the level number as a random number seed, and then start from a solved state and makes random backwards moves until a solvable level is generated. KNAR does something similar. Depending on the game, though, this might not be appropriate, or even if it normally is, the Famicom might be too slow or too less RAM. Therefore, you still might want to fill up a lot of ROM space with level data.)
(Free Hero Mesh - FOSS puzzle game engine)
slobu
Posts: 276
Joined: Tue Jul 12, 2011 10:58 am

Re: Small C for NES: A Curious Journey

Post by slobu »

We've heard from the experts coming from a low level background. Now let's hear from a fool tumbling down from high level languages :)

Yet another C compiler will be just a curiosity. I don't see the experts using it and the fools still wont know what to do with it.

The most successful higher level language implementations have been parsers for BASIC that output assembly. Usually using "kernels" that are used as templates for certain game features. These are NOT runtime engines. They do not run BASIC code in some HAL.

I'm thinking batari BASIC as a prime example:
http://bataribasic.com/
http://www.randomterrain.com/atari-2600 ... mands.html
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Small C for NES: A Curious Journey

Post by rainwarrior »

qbradq wrote:Seriously, think about a three-dimensional array. It's a pointer to an array of pointers to arrays of pointers to arrays. How is that going to be efficient on any platform?
No, this is incorrect, and these are not the same thing in C, and even though you can often implicitly convert an array to a pointer, you cannot always do this. (Other languages, like Java, are a different story.)

To create a three dimensional array, you do something like:

int x[2][2][2] = {{{1,2},{3,4}},{{1,2},{3,4}}};

In memory, this will be represented as data only, which looks like: 1,2,3,4,1,2,3,4

To create arrays of pointers, you must do this differently:

int* yyy0 = {1,2};
int* yyy1 = {3,4};
int* yyy2 = {1,2};
int* yyy3 = {3,4};
int** yy0 = {yyy0,yyy1};
int** yy1 = {yyy2,yyy3};
int*** y = {yy0,yy1}


In memory is very different. (Looks like how it is defined.)

To access data in both of these structures, this is the same syntax: x[1][1][1] and y[1][1][1] are the same. The underlying implementation for fetching these, however, is different. When fetching from x, it knows the dimensions of each part of the array, so there are no "arrays of pointers" that need to be involved. For y it is a different story. The type of y[1] is an int**, so it fetches that int** to evaluate y[1][1] which fetches the next pointer, etc. The types of these things are known at compile time, so even though the syntax is the same the compiler knows how they are different and will generate very different machine code.

The difference becomes very much apparent when you want to implicitly cast a multidimensional array to an array of pointers (i.e. you can't do this). Trying to pass x[1] as an int** will correctly generate an error, because there is no pointer data in x[1].

Anyhow, my criticism of CC65's performance on multidimensional arrays was referring to its treatment of arrays specifically. Pointers are not the issue, here, but the very inefficient manner in which it will access data in multidimensional arrays vs. rolling the same thing by hand as a single dimensional array.
User avatar
infiniteneslives
Posts: 2104
Joined: Mon Apr 04, 2011 11:49 am
Location: WhereverIparkIt, USA
Contact:

Re: Small C for NES: A Curious Journey

Post by infiniteneslives »

qbradq wrote:Out of all of these, I like the idea of banked libraries as found in SMB3. Let me know what other banking strategies you may have in mind!
I think so too. A structure like that can be made fairly bankswitching freindly with HLL if limited properly I think. So you basically have the fixed bank, and atleast a library bank. You may have a separate Data bank or something but that can be ignored for now.

If you set up these rules I think it would make things much simpler for the compiler to handle banking:

1) The library banks can ONLY call functions within it's own library and the fixed bank. It operates as if there is no banking. The functions in a given library bank assume it's felow library functions are always there.

2) The fixed bank contains the code that handles all bankswitching commands before it calls functions that are in the library. Segregate high level tasks into separate banks, to make things simpler.

To start the compiler wouldn't have to figure out how to follow these rules, you could compile each bank separately based on how you manually seggregated functions into the fixed bank or library bank #n using separate files or something. Eventually you could get fancy enough to compile the entire thing in a large linear virtual space, and then determine what functions can fit together in which library banks and the compiler could handle everything ensuring it would follow the rules above.

Interupts make this a little more tricky, but if the interupt handlers are always available in the fixed bank it's not too hard to keep track of what's going on and keep the banks straight and still follow these rules.
If you're gonna play the Game Boy, you gotta learn to play it right. -Kenny Rogers
User avatar
qbradq
Posts: 972
Joined: Wed Oct 15, 2008 11:50 am

Re: Small C for NES: A Curious Journey

Post by qbradq »

batari Basic looks very interesting. It has a number of limitations similar to what I'm talking about. For one there's no parametrized subroutines or functions. Another thing is all math is 8-bit, which works out pretty OK for the 2600. It looks like the final version uses a program-at-a-time banking method, which fits the 2600's limitations.

The compiler I've been working on is similar to batari Basic, but has parameterized subroutines, n-byte math and a more modern syntax.

I like the idea of offering game "kernels" to end users to allow rapid development of pet projects. Sounds pretty awesome really!

Thank you all again for your input. This has given me a lot of perspective.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Small C for NES: A Curious Journey

Post by tokumaru »

qbradq wrote:I like the idea of offering game "kernels" to end users to allow rapid development of pet projects. Sounds pretty awesome really!
I guess the NES version of this would be selectable/configurable VBlank handlers. Depending on the type of game people are making, they might need to favor some types of VRAM updates over others.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Small C for NES: A Curious Journey

Post by rainwarrior »

Bregalad wrote:I get your point. However it is a shame to be limited to make games where few realtime action takes place AND small games that uses a large mapper, isn't it ? What if you actually wanted to make a large game, that would "normally" fit in AOROM for instance (256kb) ? Would you have to use MMC5 with 1MB PRG-ROM just because you used CC65 ?
I don't think that's a fair assumption to make at all. In my experience, as games get larger, the bulk of space is used by data, not code. (It depends what kind of game you're making, there is no one-size-fits-all rule, but this is my general experience.) I actually think 32kb dedicated to C code could be enough to make even large-scope NES games like Master Blaster or SMB3 (though DPCM may be out of the question), though like any limited space there's always a way to fill it up if you want.

Also, if it isn't enough space, as shiru mentioned before, it's really easy to convert offending bits from C to ASM. A lot easier than developing them as ASM from scratch. The ability to prototype and tune in C alone is a big productivity booster even if you have to recode some of it later (by then you already have done the hard work of tweaking and reworking in the easier language).

It's a really tight squeeze to fit a C game into NROM when you have to put code and data all together. Once you get them out of that bank how much more space have you made for code? Probably at least 2x, maybe 4x! This doesn't scale up when you're making a bigger game, eventually it becomes about making more levels and more music, etc. and a lot less about adding more code.

So, in short, no, if I was trying to make a game that would "normally" fit in AOROM 256k, but with CC65, I suspect I would complete the coding part about 5x faster by using C, and waste maybe at most an extra 30k of space due to C bloat by the end maybe. (These are completely spurious ballpark numbers, but if I had to guess this is what I'd guess.) I would certainly NOT need 4x the space because of C, not on those scale. On a 32k game yes maybe, but not on a 256k game.
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: Small C for NES: A Curious Journey

Post by Shiru »

Speaking of programming a large game in C with a mapper, for now I think I'd go with 8+24 PRG and CHR RAM configuration, i.e. first 8K of PRG with bankswitching for all kinds of large data (music, level maps, graphics), top 24K fixed for C code, vectors, maybe a bit of DPCM. Too bad that to my knowledge there are no discrete logic mappers that allow this configuration, and MMC3 probably would be an overklll.
User avatar
infiniteneslives
Posts: 2104
Joined: Mon Apr 04, 2011 11:49 am
Location: WhereverIparkIt, USA
Contact:

Re: Small C for NES: A Curious Journey

Post by infiniteneslives »

qbradq wrote:The compiler I've been working on is similar to batari Basic, but has parameterized subroutines, n-byte math and a more modern syntax.

I like the idea of offering game "kernels" to end users to allow rapid development of pet projects. Sounds pretty awesome really!

Thank you all again for your input. This has given me a lot of perspective.
I'm just glad someone's working on this instead of us just debating about it! ;) Even better that the debate is providing useful input on your efforts.

Shiru wrote:Too bad that to my knowledge there are no discrete logic mappers that allow this configuration, and MMC3 probably would be an overklll.
You could do it with discrete logic but it's going to be more than two chips worth, and no, there aren't any current discrete mappers like that. As for the MMC3 choice you're only using a very small subset of what the MMC3 has to offer. So you could simplify the MMC3 down to something that'd fit in the smallest CPLDs on the market. You'd still have MMC3 compatibility for emus, but not the overkill on the hardware.
If you're gonna play the Game Boy, you gotta learn to play it right. -Kenny Rogers
Post Reply