How do ca65 structs/unions work?

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Post Reply
stan423321
Posts: 43
Joined: Wed Sep 09, 2020 3:08 am

How do ca65 structs/unions work?

Post by stan423321 » Mon Mar 01, 2021 2:24 pm

I was looking at ca65 manual while trying to get hang of its support for computing offsets and sizes for structs and unions. After reading through that, I'm not sure if I learned anything other than that I was wrong.

The programming language I find most comprehensible is C++. My initial assumption was that ca65 stuff works the same, except for all the missing features. But then there's the example at the bottom of section 15.2 (S. & u. / Declaration).

Code: Select all

.struct Circle
    .struct Point
        .word 2 ; Allocate two words
    .endstruct
    Radius .word
.endstruct
Why is this supposed to take 6 bytes while there is no tag for the inner struct? Do they automatically get an instance of some sort? Is it a nested struct specific thing, and if not so, can I skip it? What would be the least ugly way to do it?

I understand that 6502 is not particularly happy to process arrays of structs, for what it's worth. What I wanted to do with them is grouping variables from a code block in a struct and laying those structs out in unions in other structs to get something along the lines of unrolled stack. If I'm missing something related to such a setup, I'd like to hear about that too. I find loss of direct recursion acceptable, though.

yaros
Posts: 47
Joined: Mon Jul 27, 2020 1:14 pm

Re: How do ca65 structs/unions work?

Post by yaros » Mon Mar 01, 2021 2:37 pm

These are not c/c++ structs. They do not store the data, they just calculate offsets, and essentially fancy labels.

So Circle::Point equals 0 and Circle::Radius equals 4 (in bytes). And you use them appropriately, as offsets, e.g.

Code: Select all

	lda variableAddress+Circle::Radius
That's why the following code makes sense:

Code: Select all

.struct ACIA            ; Asynchronous Communications Interface Adapter
        .org    $031C
DATA    .byte
STATUS  .byte
CMD     .byte           ; Command register
CTRL    .byte           ; Control register
.endstruct
It calculates offsets of bytes in that particular order starting at the address $031C.

Structs are mostly useless, but what they do is to allow to have complex .byte/.word/etc offsets precalculated and avoid human errors. Otherwise you'd have to do the that by hand.

Code: Select all

CIRCLE_POINT = 0
CIRCLE_RADIUS = 4
edit:

And the reason you don't need to tag it, is because it's already inside the definition, and
"allocates" the space. You would tag it if you have two structs declared side by side.

stan423321
Posts: 43
Joined: Wed Sep 09, 2020 3:08 am

Re: How do ca65 structs/unions work?

Post by stan423321 » Tue Mar 02, 2021 2:43 am

Okay. Can I get automatic computation of struct offsets or union size without allocating the bytes for the "default instance" of the struct/union?

yaros
Posts: 47
Joined: Mon Jul 27, 2020 1:14 pm

Re: How do ca65 structs/unions work?

Post by yaros » Tue Mar 02, 2021 9:00 am

stan423321 wrote:
Tue Mar 02, 2021 2:43 am
Okay. Can I get automatic computation of struct offsets or union size without allocating the bytes for the "default instance" of the struct/union?
Yes? Simply declaring struct or union does not reserve any memory in any segment.

Code: Select all

; 0 bytes reserved
.struct Circle
    .struct Point
        .word 2 ; Allocate two words
    .endstruct
    Radius .word
.endstruct
To actually reserve 6 bytes you need to do

Code: Select all

labelName: .tag Circle
; OR
labelName2: .res .sizeof(Circle)

stan423321
Posts: 43
Joined: Wed Sep 09, 2020 3:08 am

Re: How do ca65 structs/unions work?

Post by stan423321 » Tue Mar 02, 2021 12:03 pm

So the top-level structs and unions just set up offsets and sizes, but nested ones put themselves in enclosing struct or union, then?

yaros
Posts: 47
Joined: Mon Jul 27, 2020 1:14 pm

Re: How do ca65 structs/unions work?

Post by yaros » Tue Mar 02, 2021 12:12 pm

These three are doing exactly the same thing. They calculate offsets for labels like Circle or Circle2::Point. Nested structs or unions still just calculate offsets. Using .tag inside the .struct only used to calculate offset.

Code: Select all

.struct Circle
    .struct Point
        .word 2
    .endstruct
    Radius .word
.endstruct

.struct Point2
    .word 2
.endstruct
.struct Circle2
    Point .tag Point2
    Radius .word
.endstruct

.struct Circle3
    Point .word 2
    Radius .word
.endstruct
The similar (!) C code would be this. Also doesn't allocate anything.

Code: Select all

struct Point {
    unsigned char data[2]; // "field" doesn't have a name in ca65 example, we just define size of the shole Point struct
};

struct Circle {
    struct Point point;
    unsigned short radius;
};
To reserve the space size of Circle you would use also use .tag, but outside the .struct definition. E.g.

Code: Select all

label: .tag Circle
// similar in C "struct Circle label;"
edit:
But also not that ca65 structs are still not C structs, even though they have the same name and could be represented similarly in both languages. Structs in ca65 have no compilation type checks.

stan423321
Posts: 43
Joined: Wed Sep 09, 2020 3:08 am

Re: How do ca65 structs/unions work?

Post by stan423321 » Tue Mar 02, 2021 12:33 pm

The lack of checking is completely understandable. The other part is a little harder to grasp for me because C has some other constructs, and C++ adds even more. The docs example is most reminiscent in its looks of something like this, where Circle is two bytes until you explicitly add a Point inside:

Code: Select all

struct Circle {
   struct Point {
      uint16_t coord[2];
   };
   uint16_t radius;
};
But you can also put one in place, if you want to. The notation for that is, however, not specific to nesting:

Code: Select all

struct Circle {
   struct {
      uint16_t coord[2];
   } centre;
   uint16_t radius;
};

struct {
   uint16_t test;
} this_gets_global;
So to be clear, does ca65 pick something closer to one or the other based on whether the struct is top level?

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

Re: How do ca65 structs/unions work?

Post by rainwarrior » Tue Mar 02, 2021 12:52 pm

stan423321 wrote:
Mon Mar 01, 2021 2:24 pm
I understand that 6502 is not particularly happy to process arrays of structs...
It does relatively well with a struct of arrays, though, e.g.

Code: Select all

struct {
    char a[25];
    char b[25];
} soa;

turboxray
Posts: 155
Joined: Thu Oct 31, 2019 12:56 am

Re: How do ca65 structs/unions work?

Post by turboxray » Thu Mar 04, 2021 5:49 pm

stan423321 wrote:
Mon Mar 01, 2021 2:24 pm
I understand that 6502 is not particularly happy to process arrays of structs, for what it's worth.
It's not really any worse than any other processor. Though if you index with a direct value instead of a variable, then there's no indirect translations. It's just an address offset at that point; lda #baseStructArray+(sizeof(subStructs) * directValue)),y etc. Which is pretty fast.

lidnariq
Posts: 10456
Joined: Sun Apr 13, 2008 11:12 am
Location: Seattle

Re: How do ca65 structs/unions work?

Post by lidnariq » Thu Mar 04, 2021 6:09 pm

Fast indexing of arrays of structs requires fast muiltiplication. And even if your struct is a power of two in length, bit rotation on the 6502 isn't particularly fast.

You can use an array of pointers to structs, but it involves a lot of extra copying because 6502 doesn't have a (zp,x),y addressing mode.

Other data structures (trees, linked lists, &c) aren't really any worse on 6502 than other designs.

Tangentially, I randomly encountered this blog post from one of the authors of X-plane about how memory latency is high enough on modern CPUs (CPU speed has been continuing to get faster and faster, but DRAM random access latency has hardly improved at all) that AoS or LLoS memory layouts really hurt performance: https://hacksoflife.blogspot.com/2021/0 ... rable.html

Oziphantom
Posts: 1115
Joined: Tue Feb 07, 2017 2:03 am

Re: How do ca65 structs/unions work?

Post by Oziphantom » Fri Mar 05, 2021 6:39 am

turboxray wrote:
Thu Mar 04, 2021 5:49 pm
stan423321 wrote:
Mon Mar 01, 2021 2:24 pm
I understand that 6502 is not particularly happy to process arrays of structs, for what it's worth.
It's not really any worse than any other processor. Though if you index with a direct value instead of a variable, then there's no indirect translations. It's just an address offset at that point; lda #baseStructArray+(sizeof(subStructs) * directValue)),y etc. Which is pretty fast.
If you are getting a fixed param of a struct in a fixed array number then sure. But as soon as any of those number become dynamic, lots of pain.
say directValue becomes a number, then you have to do a 8x8=16 multiply then add it to the baseStructArray and then look it up.
now if your base struct array is a pointer well then you have some maths to add a predetermined offset to it, not so bad.
if you base struct array is a pointer and directValue is a number, now you are doing an 8x8=16 multiply, then adding the base, storing it in the ZP and accessing it. Then each time you want to change the offset you want, you have to load Y, thus you loose Y as something you can use as it will always be constantly being reloaded with an Offset value. 68K, x86, MIPS, ARM all have a mul instruction which solves the maths problem. then you can do an lookup with a fixed offset so basically you do

mul a,sizeof(subStructs)
lda (a)+#5
and you get to keep Y active.
Then if you want to access 2 structs, you have more registers to hold the base pointers to, and you can offset with # const offsets.

turboxray
Posts: 155
Joined: Thu Oct 31, 2019 12:56 am

Re: How do ca65 structs/unions work?

Post by turboxray » Fri Mar 05, 2021 11:49 am

lidnariq wrote:
Thu Mar 04, 2021 6:09 pm
Fast indexing of arrays of structs requires fast muiltiplication. And even if your struct is a power of two in length, bit rotation on the 6502 isn't particularly fast.
You can use an array of pointers to structs..
This is how I usually handle it; so while the memory might be contiguous - an array of addresses is the equivalent. If you don't have fast multiply, that's the typical approach. Yeah you might have to copy the address from the indexed pointer, but copying bytes anyway at some point (even if you had hardware multiple unit on the 6502, you still need to copy bytes in and out of whatever hardware interfacing unit like on the snes) and you still need that to end up in ZP for indirection.

Oziphantom wrote:
Fri Mar 05, 2021 6:39 am

If you are getting a fixed param of a struct in a fixed array number then sure.
That's why I pre-fixed my sentence with "Though". I never said the two were equivalent - just that there is a circumstance where an array of structures requires no indirection.
Oziphantom wrote:
Fri Mar 05, 2021 6:39 am
if you base struct array is a pointer and directValue is a number, now you are doing an 8x8=16 multiply, then adding the base, storing it in the ZP and accessing it. Then each time you want to change the offset you want, you have to load Y, thus you loose Y as something you can use as it will always be constantly being reloaded with an Offset value. 68K, x86, MIPS, ARM all have a mul instruction which solves the maths problem. then you can do an lookup with a fixed offset so basically you do
Why are you bringing up those processors? MIPS and ARM definitely have no place in this context. My statement about other processors was in relation to the class of the CPU. The 6809, the z80, the 8080, GBz80, the 65x series - etc. I mean, you probably include the 8088 as it's pretty crippled. Even the original 8086 maybe to make a case specific point.

If you're going the multiplication route, the 6502 already has a fast 8x8=>16bit routine (the quarter square table method). And since it's an array of of structs, the distance between each struct entry is constant.

You can literally take this, which is already fast:

Code: Select all

    	LDY #$66    ;factor 1 in y
    	LDA #$12    ;factor 2 in a

    	STA zp1     ;set zp adresses
    	STA zp2
    	EOR #$ff
    	STA zp3
    	STA zp4

    	SEC
    	LDA (zp1),y
    	SBC (zp3),y
    	TAX         ;product lo in x
    	LDA (zp2),y
        SBC (zp4),y ;product hi in a
And just use this:

Code: Select all

    	SEC
    	LDA abs1,y
    	SBC abs3,y
    	TAX         ;product lo in x
    	LDA abs2,y
        SBC abs4,y ;product hi in a
Where Y is the var. There's no need to use indirection on the LUTs here, because the base is always fixed (the size of the struct). Assuming all missaligned page boundaries, that's 24 cycles for an 8x8=>16 operation and all you need is Y. Just to put things into perspective; since you brought up 68k, its MUL is at minimum 38cycles if var value was 0, and up to 70 cycles if all bits are set.

Post Reply