There's a couple of ways to look at it, and I think White Flames post is spot on. It's spot on because the technique he demonstrates is not intuitive to someone used to working in a high level language. Its exhibits some architecture dependency as well (as to the reasoning behind choosing the representation).

Here's the two ways to manage this kind of table structure.

The first is more akin to how a C programmer may look at it, as a contiguous block of memory with a structure overlaid on top of it.



This defines the four fields of the sprite table first as simple offsets, then as we create starting points for each of the fields in the table.

Given something like this, if you wanted to work with a Sprite, you could would put the Sprite number TIMES 4 (SPRITE_SIZE) in to X, and then you can use the index address modes to get the individual elements.

So, something like this:


If you were to do this is C code, it would look something like this:


The basic advantage of this representation is that all of the constructs elements are together, the entire sprite is located in a contiguous block of ram.

The down side is that you have to multiply the offset by the sprite size (here we used shifts), and you are limited to a sprite table that is no larger than 256 bytes total, since the X register is 8 bits. So, that would be a total of 64 sprites.

White Flames technique is essentially like this in C:



In assembly, it looks like this:



The primary disadvantage is simply that the sprite values are not contiguous. So, you can't use simple block move logic to move sprites around, you have to move them field by field. But the advantages are that you can have up to 256 sprites, and you can have as many fields as you like (not, simply 4, or powers of two, but you can have 7,19, or 347 fields).

So, different needs have different techniques. Depends on the specific use case of each structure.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

BDD,

What I meant by ASM is just assembly. Pardon the newbie slang...

I have spent a great deal of time trying to understand your last post. I feel like I'm getting there.
Here are a few questions I have for you:

When you wrote:


What did the ex2_x3 mean exactly? I get that it is a "power of 2" which allows you to ASL,
but what is the literal definition. Is it contingent on the the size of the table?

Also, when you wrote:


Am I to understand that s_sd_tab is the size of the slot times the id? I'm sorry, I don't see where
the n_scsiid was defined in your code.

And finally, when you wrote:


Is this saying that sd_tab is the initial pointer to the entire table? As long as I know the
exact size of the table in bytes, I can use the *=*+ idiom and reserve that chunk of space?

Thanks so much for your input. I have printed it and I'm sure I will use it for reference in the future.

_________________
http://www.thestarrlab.com

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Yeah, I accidentally used the wrong assembler directive in my first example. I generally use ca65, which doesn't seem very well represented in this forum; it uses ".res" for this purpose. Here's a C port of what I was trying to get at, as whartung has described already:



Here's an example of using a singly-linked free list to do allocation and deallocation. We'll have the spriteX of unused sprites hold a 'next' pointer, and use 255 as the magic end-of-list marker. In 6502, you could also try passing end-of-list in processor flags (C, N, or Z).



I haven't done C in a very long time, so excuse any dumb errors. However, all of this should be very semantically close to the exact steps you'd do in 6502, with all indexing being just 0-31 and fitting nicely in index registers without doing any pointer arithmetic.

There are a few of advantages to laying out the tables in this fashion above ("column-based") as opposed to the SCSI table example ("row-based", analogous to an array of C structs). The primary one is how big the index register needs to be. Using 4 bytes per structure, you'd be constrained to a maximum of 64 entries in your table before you'd need indexing bigger than 0-255; even fewer if your structures got bigger. With column-based tables, you can always go up to 256 entries with just a byte offset for an index. Also is the fact that you can adjust to adjacent entries with INX/INY or DEX/DEY instead of shifting the offset to .A and performing "real" math, though that's not really applicable in a dynamically allocated scenario like this sprite usage.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

@BDD,

Well I have to admit that I did skim a bit.
Your reply was very informative, however a bit pedantic
for my taste.

I think what threw me off was trying to decipher what was SCSI specific.

I would like to ask yet another question:

When using [asl a], it translates to "A = A * 2". As long as 'a' is a power of 2.

But what if each "record" in the table is 8 bytes long, couldn't you just [adc #8]

Meaning, if 'a' was #8 and i did [asl a] 'a' would now = #16. But If i shifted again,
instead of being #24 it would be #32 right? And the next iteration would be #64.

_________________
http://www.thestarrlab.com

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I would like to use this approach as well for my sprite table.
Each sprite "record" is 4 bytes long. 4 being a power of two, I could iterate
over the table and access each sprite at the 0th byte.

However, does this mean that I have to store each record exactly in bytes apart
that make up what the ASL would be?

For example:



If that is the right way, what about the data inbetween? How much slower is ADC?

_________________
http://www.thestarrlab.com

Most of this topic (C and sprites) is outside my areas of expertise, but once the number is in the accumulator, ADC and ASL both take two clocks. ADC however involves the carry flag; so if you can't be sure it has the right value to start (usually meaning 0), you have to add a CLC in front of ADC, adding another two clocks.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Johnny: The ASL isn't used to move from one record to another. It's to convert a record number into a pointer offset.

Each record is 4 bytes, so multiply your record number by 4 (ASL twice) to convert to a pointer offset. e.g., if you want to point at entry 10 in the table, you want to use offset 10*4 = (10<<1)<<1 = 40 into the table.


To go from one record to the next, add or subtract 4 from the offset (4x INX or DEX, smaller than transferring to .A and ADC/SBC, using the same number of clock cycles). All 4-byte structures are completely adjacent in memory.

Or, you could use the column-based approach from my example and skip all this hassle.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

When you use a row-based approach to array layout every record, no matter what its size, is stored consecutively in memory. That implies that to get the base address of an arbitrary element N, you have perform a multiplication.

ASL is equivalent to multiplying by two, so ASL is a handy way to access elements in row-based arrays whose record size is a power of two. Sometimes it's even worth wasting a little space - if the 'natural' record size is, say, seven bytes, it might pay to start each record on an eight-byte boundary and use three ASL instructions to convert from an element number to an offset. That would be the equivalent of 'structure padding' in C.

For non-power-of-two record sizes which are known to be fixed, it's also reasonably easy to combine ASL and ADC to multiply an index by that fixed value rather than use a slower general-purpose multiplication routine. Using a record size of ten and assuming a zero-based index of no more than 25 records total:



Note that each ASL clears the carry bit in this example (top three bits of the index are always clear), so there's no need to set its state explicitly.

Another approach is to have the assembler "pre-calculate" part or all of the possible multiplications and store the results in a table. When accessing a particular bit in the 8K of hi-res graphics memory in a C64 with its unusual cell-based layout, for example, you'd often see code like this:



This stores pointers to the first 8x8 pixel cell in a row of 40 of them (25 rows * 40 cols = 1000 cells of eight bytes each). Obviously this isn't going to fit into a single byte offset in the X- or Y-register!

The table would be used like this:



The code would go on to add the X position to the looked-up start address of any row. The point is the multiplication was done at assembly time, rather than run time.