It is currently Sat Dec 16, 2017 6:18 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Tue Nov 09, 2010 1:31 pm 
Offline

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]; */

value = prg_page[addr >> 12][addr & 0x0FFF];


Let's say addr == 0x8123:

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
 Profile  
 
 Post subject:
PostPosted: Tue Nov 09, 2010 1:40 pm 
Offline
User avatar

Joined: Wed Dec 06, 2006 8:18 pm
Posts: 2806
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
 Profile  
 
PostPosted: Tue Nov 09, 2010 2:25 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 2:13 pm
Posts: 1667
Location: .ma.us
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
 Profile  
 
 Post subject:
PostPosted: Tue Nov 09, 2010 2:42 pm 
Offline
Formerly 65024U

Joined: Sat Mar 27, 2010 12:57 pm
Posts: 2257
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
 Profile  
 
 Post subject:
PostPosted: Tue Nov 09, 2010 5:02 pm 
Offline
User avatar

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];

uint8_t* memory( int addr )
{
    return &banks [addr / BANK_SIZE] [addr % BANK_SIZE];
}


Top
 Profile  
 
 Post subject:
PostPosted: Wed Nov 10, 2010 5:33 am 
Offline

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
 Profile  
 
 Post subject:
PostPosted: Wed Nov 10, 2010 6:20 pm 
Offline
Formerly ~J-@D!~
User avatar

Joined: Sun Mar 12, 2006 12:36 am
Posts: 445
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];

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.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 10:13 am 
Offline
User avatar

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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 2:20 pm 
Offline
Formerly Fx3
User avatar

Joined: Fri Nov 12, 2004 4:59 pm
Posts: 3076
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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 3:07 pm 
Offline
User avatar

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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 3:32 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 5:24 pm 
Offline
User avatar

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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 6:09 pm 
Offline
Formerly Fx3
User avatar

Joined: Fri Nov 12, 2004 4:59 pm
Posts: 3076
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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 6:39 pm 
Offline
User avatar

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
 Profile  
 
 Post subject:
PostPosted: Thu Nov 11, 2010 7:46 pm 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 3969
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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: creaothceann, Google Adsense [Bot] and 6 guests


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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group