It is currently Sat Aug 18, 2018 3:26 am

 All times are UTC - 7 hours

 Page 1 of 2 [ 20 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Math/array question - emulation relatedPosted: Tue Nov 09, 2010 1:31 pm

Joined: Tue Nov 09, 2010 12:58 pm
Posts: 2
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:
/* uint8_t *prg_page[16]; */

Code:
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!

Top

 Post subject: Posted: Tue Nov 09, 2010 1:40 pm

Joined: Wed Dec 06, 2006 8:18 pm
Posts: 2827
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.

Top

 Post subject: Re: Math/array question - emulation relatedPosted: Tue Nov 09, 2010 2:25 pm

Joined: Mon Sep 27, 2004 2:13 pm
Posts: 1668
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.

Top

 Post subject: Posted: Tue Nov 09, 2010 2:42 pm
 Formerly 65024U

Joined: Sat Mar 27, 2010 12:57 pm
Posts: 2262
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.

Top

 Post subject: Posted: Tue Nov 09, 2010 5:02 pm

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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:
#define BANK_SIZE 4096
uint8_t* banks [65536 / BANK_SIZE];

{
}

Top

 Post subject: Posted: Wed Nov 10, 2010 5:33 am

Joined: Tue Nov 09, 2010 12:58 pm
Posts: 2
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.

Top

 Post subject: Posted: Wed Nov 10, 2010 6:20 pm
 Formerly ~J-@D!~

Joined: Sun Mar 12, 2006 12:36 am
Posts: 453
Location: Rive nord de Montréal
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:
#define BANK_SIZE 4096
uint8_t* banks [65536 / 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.

Top

 Post subject: Posted: Thu Nov 11, 2010 10:13 am

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.

Top

 Post subject: Posted: Thu Nov 11, 2010 2:20 pm
 Formerly Fx3

Joined: Fri Nov 12, 2004 4:59 pm
Posts: 3140
Location: Brazil
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.

Top

 Post subject: Posted: Thu Nov 11, 2010 3:07 pm

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.

Top

 Post subject: Posted: Thu Nov 11, 2010 3:32 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20413
Location: NE Indiana, USA (NTSC)
blargg wrote:

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.

Top

 Post subject: Posted: Thu Nov 11, 2010 5:24 pm

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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".

Top

 Post subject: Posted: Thu Nov 11, 2010 6:09 pm
 Formerly Fx3

Joined: Fri Nov 12, 2004 4:59 pm
Posts: 3140
Location: Brazil
- addr/4096 -> 4096 is 2^12.
- addr/8 -> 8 is 2^3.

- This is easily translated with shifts. What about addr/7 ? Got it?

Top

 Post subject: Posted: Thu Nov 11, 2010 6:39 pm

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.

Top

 Post subject: Posted: Thu Nov 11, 2010 7:46 pm

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4067
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!

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 20 posts ] Go to page 1, 2  Next

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki