Math/array question - emulation related

Discuss emulation of the Nintendo Entertainment System and Famicom.

Moderator: Moderators

thebigkahuna
Posts: 2
Joined: Tue Nov 09, 2010 12:58 pm

Math/array question - emulation related

Post by thebigkahuna »

Apologies if this is in the wrong section, please move it if it is.

I'm struggling to understand some concepts. I understand bit masking, but how does the following work? 16 4k pages for PRG-ROM was suggested to make the math easier somehow...

Code: Select all

/* uint8_t *prg_page[16]; */

value = prg_page[addr >> 12][addr & 0x0FFF];
Let's say addr == 0x8123:

Code: Select all

value = prg_page[8][123]; 
How does [8][123] map to one of the 16 pages? :? I'm really not grasping something here, any help would be great!
User avatar
MottZilla
Posts: 2837
Joined: Wed Dec 06, 2006 8:18 pm

Post by MottZilla »

I'm not sure what you mean or where you got that code.

You can use the calculator that comes with windows to do Hex and operations like AND and OR. The idea behind masking in your suggested usage is to make off bits higher or lower than a desired range. For example if you are masking the bottom twelve bits off by ANDing with 0xFFF that means you know the number left over won't be higher than that.

Since you seem to have arrays or pointers cut into smaller pieces (which you should, the address space shouldn't be one big array) when you access an address in these small windows you need only the address bits that apply to your window size. So you are taking the low bits to address the memory in that window, and the higher bits are being used to figure out which window to fetch from.

Hopefully that helps.
User avatar
kyuusaku
Posts: 1665
Joined: Mon Sep 27, 2004 2:13 pm

Re: Math/array question - emulation related

Post by kyuusaku »

Shifting right by 12 gets you the 4k bank being accessed. ANDing the address by 0xFFF gets the 4k offset.

From this code one can assume prg_page is an array of pointers to 4k segments of memory.

So for example:

prg_page[8] = pointer to $8000 bank
prg_page[9] = pointer to $9000 bank etc

The bankswitch routine would thus do something like this (UNROM):

offset = &ROM[writeval << 4];
prg_page[0x8] = offset;
prg_page[0x9] = offset + 0x1000;
prg_page[0xA] = offset + 0x2000;
prg_page[0xB] = offset + 0x3000;

Personally I don't see the need for this kind of simplified addressing... I decode stuff in functions (function pointers are great) so there's only as much pointer arithmetic as necessary and everything can be easily hooked without hacky code.
3gengames
Formerly 65024U
Posts: 2284
Joined: Sat Mar 27, 2010 12:57 pm

Post by 3gengames »

I am probably just saying stuff others have but....


The left value is 4 bits. That equals a page number from the code. In this case, $8, which should be bank 8 of the 4K banks you have in your program. The value A would be bank 10, 2 bank 2, and so on.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Yeah, as kyuusaku says, get it working before you try to optimize it. Bit shifting and page pointers is optimization. Actually, you don't need any bit shifting; just use / and %. If having a divide is unbearable, make addr an unsigned int and the compiler will convert the / and % into a right shift and mask.

Code: Select all

#define BANK_SIZE 4096
uint8_t* banks [65536 / BANK_SIZE];

uint8_t* memory( int addr )
{
    return &banks [addr / BANK_SIZE] [addr % BANK_SIZE];
}
thebigkahuna
Posts: 2
Joined: Tue Nov 09, 2010 12:58 pm

Post by thebigkahuna »

That's great, thanks guys, I understand it now. And blargg, you're right, premature optimization on my part wasn't doing me any favours, I'll take that on board :)

Thanks again.
User avatar
Jarhmander
Formerly ~J-@D!~
Posts: 568
Joined: Sun Mar 12, 2006 12:36 am
Location: Rive nord de Montréal

Post by Jarhmander »

blargg wrote:Yeah, as kyuusaku says, get it working before you try to optimize it. Bit shifting and page pointers is optimization. Actually, you don't need any bit shifting; just use / and %. If having a divide is unbearable, make addr an unsigned int and the compiler will convert the / and % into a right shift and mask.

Code: Select all

#define BANK_SIZE 4096
uint8_t* banks [65536 / BANK_SIZE];

uint8_t* memory( int addr )
{
    return &banks [addr / BANK_SIZE] [addr % BANK_SIZE];
}
I don't agree with your point here. Bit shifting isn't that much of an optimisation, it is just the proper way of manipuling bits because it is its purpose, and using those bitwise operators makes code clearer when it's used right. For example, [var = val / 16;] makes me think the programmer wanted to do some arithmetics with a variable, while [var = val>>4;] clearly makes me thinks the programmer wanted to get the upper part of the integer, above the first 4 bits. If val and var are [unsigned int], my two examples yields the same results, but there is a difference in the intend in the code.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Good point about intention; code should reflect that, and any optimization should avoid disturbing that, if possible. If you've got some hardware that's specified to use the upper 4 bits of a byte, you should write b>>4, not b/16. If you're dividing the address space into 4096-byte banks, and you want the bank index and offset, you should use addr/4096 and addr%4096, not addr>>12 and addr&0xFFF.
User avatar
Zepper
Formerly Fx3
Posts: 3262
Joined: Fri Nov 12, 2004 4:59 pm
Location: Brazil
Contact:

Post by Zepper »

blargg wrote:Good point about intention; code should reflect that, and any optimization should avoid disturbing that, if possible. If you've got some hardware that's specified to use the upper 4 bits of a byte, you should write b>>4, not b/16. If you're dividing the address space into 4096-byte banks, and you want the bank index and offset, you should use addr/4096 and addr%4096, not addr>>12 and addr&0xFFF.
- Yes, but I bet you suppose a value that's power of 2..? I don't know if the compiler rounds a division or takes the integer part only. Anyway, an obvious thing: do not use shifts with signed numbers.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

I don't understand your comment about a power of 2. / and % work regardless of the divisor, with / yielding the quotient and % the remainder. For positive values, this works as expected, for example 15/8=1 and 15%8=7.

Right shifting is fine on positive signed values, it's just negative values which yield an implementation-defined result. If you're reserving right shift for bit operations only, you'll never have to worry about a negative value in the first place.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

blargg wrote:If you're dividing the address space into 4096-byte banks, and you want the bank index and offset, you should use addr/4096 and addr%4096, not addr>>12 and addr&0xFFF.
Unless you're thinking of it as separating the address bus into A15-A12 and A11-A0, and then treating A15-A12 as the input to a decoder and/or a register file.
Zepper wrote:I don't know if the compiler rounds a division or takes the integer part only.
In C, integer / integer rounds toward 0. This is true of both signed and unsigned integer arithmetic.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Only C99 specifies rounding towards zero; C89 and C++ leave it up to the implementation. It's unfortunate that algebraic rounding was chosen for C99, as it's the less-useful of the two possible approaches. From the respective language standards, in order of publication:
C89 wrote:When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.
C++98 wrote:The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined*.
* According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.
C99 wrote:When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded*. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

* This is often called "truncation toward zero".
User avatar
Zepper
Formerly Fx3
Posts: 3262
Joined: Fri Nov 12, 2004 4:59 pm
Location: Brazil
Contact:

Post by Zepper »

- addr/4096 -> 4096 is 2^12.
- addr/8 -> 8 is 2^3.

- This is easily translated with shifts. What about addr/7 ? Got it?
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

So you're talking about optimization by the compiler? I'm just not clear of your point, and where it fits in with things. I'd like to understand, but your terseness is making that difficult.
User avatar
Dwedit
Posts: 4922
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Post by Dwedit »

You also sometimes have the other scenario, where your shifts aren't constant. Then you can't simply use division or multiplication and rely on magic that makes the compiler turn them into shifts.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
Post Reply