It is currently Sat Sep 21, 2019 4:32 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Sun May 12, 2019 1:29 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
I'm in the process of optimizing some of my C code with inline Assembly. And I'm struggling with the proper way of assigning a pointer variable by taking a value from an array that contains pointers.

Here is the relevant data:
Code:
typedef unsigned char byte;

const byte Data1[] = { 1, 2, 3 };
const byte Data2[] = { 4, 5, 6, 7 };
const byte Data3[] = { 8, 9, 10, 11, 12 };

const byte *const AllData[1000] = { Data1, Data2, Data3, /* ... */ };

const byte *CurrentData;
unsigned int CurrentDataIndex;


And I want to do this:
Code:
CurrentData = AllData[CurrentDataIndex];


So, not only does the array that I try to access have more than 256 (or 128) entries, so the access doesn't work with a simple
Code:
LDY Index
LDA (Array), Y
since the index can definitely be in the range of a two bytes value.

It's also the case that the values inside the array aren't simple single-byte values, but pointers, i.e. also two bytes big.


The code that is generated by cc65 doesn't help that much since it uses some internal functions like aslax1 and ldaxi.
If I replace these functions with their actual contents, the generated code is 22 lines long.
I assume the "canonical" manually-written way of doing this kind of array access is shorter.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sun May 12, 2019 2:46 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
I don't see many solutions besides creating a pointer using the base address of the array plus the offset, and using that to copy the final pointer to ZP, where you can use it:

Code:
clc
lda #<AllData
adc Offset+0
sta ArrayPointer+0
lda #>AllData
adc Offset+1
sta ArrayPointer+1
ldy #$0
lda (ArrayPointer), y
sta FinalPointer+0
iny
lda (ArrayPointer), y
sta FinalPointer+1

Not a quick procedure by any means...

I don't know what you need this for, but if speed is important here, maybe you should consider a more efficient data structure, or think of a different way to implement the functionality this is related to.

How frequently do you think you'll be running this code?


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:07 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
tokumaru wrote:
Not a quick procedure by any means...

Well, at least it looks quicker than the one generated by cc65.
I'll try it out.

tokumaru wrote:
I don't know what you need this for, but if speed is important here, maybe you should consider a more efficient data structure, or think of a different way to implement the functionality this is related to.

How frequently do you think you'll be running this code?

Speed isn't really that relevant here since this code is used rarely.

Although this is supposed to be a general purpose function for this kind of array access, so I'm of course looking for the best method regardless.


The reason why I need this:

My game has screen by screen scrolling.
Every screen is an array of byte values that are the data values for this screen.
So far, so good. A single screen can be accessed easily because it only has byte values and no screen will have more than 256 bytes.
So, as soon as my pointer to a single screen is set, I can do the simple [tt]LDA (Screen), Y[tt] stuff to get single items within the screen, like background or enemy placement.

But of course I have to be able to get the correct screen in the first place.
So, I need an array that stores the address to every screen, i.e. an array with two-byte pointer values.
And since I'll have more than 256 screens, the index variable for this array is also a two byte value.

Same situation for in-game texts: I have a whole bunch of arrays with the actual dialogs. But to be able to access dialog number 375, I need an array that has the addresses of all the dialog arrays.

So, what other data structure would you suggest?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:13 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
tokumaru wrote:
Code:
clc
lda #<AllData
adc Offset+0
sta ArrayPointer+0
lda #>AllData
adc Offset+1
sta ArrayPointer+1
ldy #$0
lda (ArrayPointer), y
sta FinalPointer+0
iny
lda (ArrayPointer), y
sta FinalPointer+1

Are you sure this is correct? You take the value from AllData, add the offset and store it to ArrayPointer.
However, since AllData contains pointers, i.e. two-byte values, the offset has to be doubled first:

AllData[25] in C is actually AllData + 50 in assembly because each entry in AllData is two bytes.

Or am I overlooking something here?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:14 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
Wait... You're using a 2-byte index to look-up a 2-byte value? Why not store the 2-byte value (pointer) directly and get rid of the array of pointers altogether? I assume that you're not using all 16 bits to index the array, is that it?


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:18 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
If you have a good way of doing this, sure.

Here's the data again:
Code:
const byte Screen1[] = { 1, 2, 3 };
const byte Screen2[] = { 4, 5, 6, 7 };
const byte Screen3[] = { 8, 9, 10, 11, 12 };
/* ... (more screens) */

How do I get the address of any of these arrays into a pointer without using this:
Code:
const byte *const AllScreens[1000] = { Screen1, Screen2, Screen3, /* ... */ };
?

How do I manage to get my const byte *CurrentScreen pointer to point to the start address of, for example, the 87th screen?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Last edited by DRW on Sun May 12, 2019 3:22 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:22 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
DRW wrote:
However, since AllData contains pointers, i.e. two-byte values, the offset has to be doubled first

Yeah, I assumed it'd be doubled in advance, or already stored doubled. If you have to double it on the fly, you'll need more code.

If this index comes from a place where it's mixed with other bit fields, you could make it so it starts from bit 1 up, with some other kind of information using bit 0, so a simple AND operation could be used to mask off the irrelevant bits and result in an already doubled offset. It it isn't mixed with bit fields and uses the whole 16 bits, you can store the value however you want.


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:31 pm 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4211
Where are your (16-bit?) screen numbers coming from? The only way to avoid an array to go from Screen Number to Address of Screen is to use a direct pointer everywhere.

But how often are you converting from screen number to screen address anyway? If there's anything I learned from optimization, it's that there is Fast Code and Slow Code. Fast code is code that absolutely needs to be fast, and is found inside a loop that executes thousands of times. Slow Code is code that executes less frequently, such as only once, or once per level, or something like that. I'd just eat the cost of a lookup if it's not something done at least once per frame.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!


Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:32 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
DRW wrote:
How do I manage to get my const byte *CurrentScreen pointer to point to the start address of, for example, the 87th screen?

How are you piecing these 1000 screens together? Do you have a game map made of indices between 0 and 999? What I'm suggesting is, instead of building the map with 16-bit screen indices, build it with 16-bit screen pointers, and get rid of the AllScreens array altogether. There's no need to order the screens if you're referencing them directly.


Last edited by tokumaru on Sun May 12, 2019 3:37 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sun May 12, 2019 3:37 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
Dwedit wrote:
I'd just eat the cost of a lookup if it's not something done at least once per frame.

If you're not using all 16 bits for indexing, sure, I agree, but if you are, it makes absolutely no sense to index something that's as big as the index itself! You'd just be wasting time (with the unnecessary indirection) and space (with the unnecessary list of pointers).


Top
 Profile  
 
PostPosted: Sun May 12, 2019 4:02 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
tokumaru wrote:
Yeah, I assumed it'd be doubled in advance, or already stored doubled.

Doubling the index is one of the things that makes the code bigger. Since the index is an uint, it's not just a simple ASL.

That's why I posted this single line of C code:
Code:
CurrentData = AllData[CurrentDataIndex];

I need to do whatever this code is accomplishing. This includes doubling the value of CurrentDataIndex because that's what C does here.

If the code doesn't become much smaller than the C implementation, I can just leave it in C.
But I was thinking that the cc65 compiler maybe bloats the code and a handwritten version is much smaller.
(Just like the compiler needlessly copies your pointer to ptr1 whenever you try to access an array through a pointer, even if your own pointer is already in the zeropage.
Or if you access two arrays one after another with the same index variable: The compiler will not notice that it doesn't need to do another LDY Index again if Index still has the same value as before.)

tokumaru wrote:
If you have to double it on the fly, you'll need more code.

Yeah, it has to be doubled on the fly. After all, this is the screen ID, a dedicated piece of information that controls the bank switching and which little square on the map is blinking etc.
I wouldn't want it doubled in advance just to acommodate to some array storage internals.
The ID belongs to the actual game logic: "This is screen number 439."
That the start address for this screen is stored in AllScreens + 878 should only come into play when AllScreens is actually used, but CurrentScreenIndex shouldn't hold the value 878 natively.

Dwedit wrote:
Where are your (16-bit?) screen numbers coming from?

The screen numbers come from their position in the pointer array:

Code:
const byte Screen0[] = { 1, 2, 3 };
const byte Screen1[] = { 4, 5, 6, 7 };
const byte Screen2[] = { 8, 9, 10, 11, 12 };
const byte Screen3[] = { /* ... */ };
const byte Screen4[] = { /* ... */ };
const byte Screen5[] = { /* ... */ };
/* ... (more screens) */

const byte *const AllScreens[1000] = { Screen0, Screen1, Screen2, Screen3, Screen4, Screen5, /* ... */ };

In this example, if the index is 4, then AllScreens[Index] will load Screen4 simply because that's the address stored at position 4.

How do I know which screen to load when the hero leaves the current screen? Simple:
If he goes right, then CurrentScreenIndex = CurrentScreenIndex + 1.
Left: -1.
Down: +20.
Up: -20.

Dwedit wrote:
The only way to avoid an array to go from Screen Number to Address of Screen is to use a direct pointer everywhere.

I don't know what you mean. I cannot write CurrentScreen = Screen487 (or CurrentScreen = ScreenKingsCastle) unless I make a switch statement with a few hundred cases.

Dwedit wrote:
But how often are you converting from screen number to screen address anyway?

It's not that important in my current case. But it's a general purpose question, so I'm curious about it anyway.

If you have issues with the pointers, just imagine that I have an array of unsigned integers and the array can be larger than 256 bytes:
How would I access the array in an efficient way?

Here, this example is basically the same thing from an assembly code point of view:
Code:
enum EnemyType { Slime, Spider, Bat, Golem, Medusa ... /* 300 more enemy types */ };

const uint EnemyMaxEnergies[] =
{
    50, /* Slime */
    100, /* Spider */
    120, /* Bat */
    500, /* Golem */
    2000, /* Medusa */
    ... /* 300 more */
};

void ProcessEnemy(byte enemiesSlot)
{
    static uint enemyType;
    static uint maxEnergy;

    enemyType = AllActiveEnemies[enemiesSlot].Type;
    maxEnergy = EnemyMaxEnergies[enemyType];
}


How would one implement
Code:
maxEnergy = EnemyMaxEnergies[enemyType]

in Assembly if maxEnergy is a two byte unsigned integer value, but the number of enemies is also larger than 256, so the array index is also unsigned int?

tokumaru wrote:
What I'm suggesting is, instead of building the map with 16-bit screen indices, build it with 16-bit screen pointers, and get rid of the AllScreens array altogether. There's no need to order the screens if you're referencing them directly.

I'm still curious how you would actually accomplish this. How shall I access the pointer directly? Let's say I have a screen named ScreenTown. Then I have a screen named ScreenTownEntrance.
When I'm in ScreenTownEntrance and I walk right, how exactly shall the program know that it has to load the ScreenTown pointer now? Where is this information stored?

In my case: It is stored in an AllScreens array. The screens in this array are laid out like in a rectangle. The top left screen is the first entry, the bottom right screen is the last entry.
When I move up, down, left right along the screens, I simply change my index to -20, +20, -1 or +1 respectively.


As far as I see, accessing pointers directly only works in two cases:

1. All screen data has the same size. Then you can add and subtract the screen size to the pointer. But my screens have a variable size.
2. If each screen stores the addresses of the four neighboring screens. Which is a total waste of space since the screens are laid out in a rectangle anyway.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sun May 12, 2019 4:34 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
Quote:
The screen numbers come from their position in the pointer array

I know what the numbers *mean*, my question was "where are you using them"? Where you get these numbers from right before having to use them as offsets to look screen pointers up. Do they come from a level/world map? My suggestion is to change the level/world map so it doesn't use these indices, but the screen pointers directly. I'm not very good with C, so pardon me if something is really wrong, but I mean something like this:

Code:
//instead of this:
const unsigned int WorldMap[] = {0, 4, 33, 999, 48, 17 /*...*/};
//do this:
const byte *const WorldMap[] = {Screen0, Screen4, Screen33, Screen999, Screen48, Screen17 /*...*/}


Top
 Profile  
 
PostPosted: Sun May 12, 2019 4:40 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
tokumaru wrote:
Code:
//instead of this:
const unsigned int WorldMap[] = {0, 4, 33, 999, 48, 17 /*...*/};
//do this:
const byte *const WorldMap[] = {Screen0, Screen4, Screen33, Screen999, Screen48, Screen17 /*...*/}

Erm, that's exactly what I'm doing, right from the very first post:
Code:
const byte *const AllData[1000] = { Data1, Data2, Data3, /* ... */ };

You see that I do not have an unsigned int array? I do have an array of pointers (const byte *const), just like you suggested.

Also, my screen numbers aren't arbitrary like in your first example. In my case, screen number 25 means the 25th entry in the const byte *const AllData[] array.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Last edited by DRW on Sun May 12, 2019 4:44 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sun May 12, 2019 4:44 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11412
Location: Rio de Janeiro - Brazil
Yeah, I first thought that AllScreens was just a means of ordering the screens for indexing in the world map, but I read your post again and it turns out that AllScreens *IS* your world map (the array name didn't make this very clear)... In that case, my suggestion is you don't calculate the pointer from scratch each time. Calculate the value of the pointer when the level starts, then, as the player moves, just add -2 (moving left), 2 (moving right), -40 (moving up) or 40 (moving down). If that's not possible, due to having to mimic exactly what the C code would do, then yeah, there's not much to gain if you have to calculate the whole thing every time. Since this is not done often, i'd just use C.

Sometimes, the speed of assembly doesn't come from the fact that you can do the exact same calculations using less instructions, but from the fact that you can cache and reuse partial results due to not being constrained by the constructs of a high level language.


Top
 Profile  
 
PostPosted: Sun May 12, 2019 5:02 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
tokumaru wrote:
In that case, my suggestion is you don't calculate the pointer from scratch each time. Calculate the value of the pointer when the level starts, then, as the player moves, just add -2 (moving left), 2 (moving right), -40 (moving up) or 40 (moving down).

I don't think this will gain a lot.

When I increment my CurrentScreen pointer, this wouldn't move the pointer from Screen25 to Screen26, it would simply move the pointer from Screen25 to two bytes after Screen25.

Therefore, I'd have to use an in-between pointer that points to the address of AllScreens + an offset.

And then I'd have to let CurrentScreen point to the value of this in-between pointer.

I doubt that this would really be much less code. And even if it was, that's too much of a hassle.


But let's forget about the pointers.

Since the whole pointer stuff seems to be a bit confusing, let's do the example again that sounds a bit simpler, but that would be exactly the same code in assembly:


I have an array of unsigned integers.
(In assembly: I have an array of words.)

This array has, let's say, 300 entries, i.e. it's 600 bytes large:
Code:
In C:
const unsigned int Data[300] = { 25, 375, 89, 500, 1099 ... };

In Assembly:
Data: .word 25, 375, 89, 500, 1099 ...


I have two variables:
Code:
In C:
unsigned int Value;
unsigned int Index;

In Assembly:
Value: .res 2
Index: .res 2


How do I do this in Assembly?
Code:
Value = Data[Index];

I assume this shouldn't be too much of an unusual situation, right? Reading a number from an array and, unfortunately, the number itself as well as the array offset can be larger than 255.

So, what's the way to do this?

(And no, you cannot pre-buffer the current (array + offset) address and then simply increment and decrement from this position. The index variable can be a new arbitrary value each time the array is accessed.)

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 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