a pointerarray library

Por hit9918

Prophet (2927)

imagem de hit9918

01-09-2011, 02:00

I think I should post the code for array add and remove functions.
Writing them was the only inconvenient thing about pointerarrays ever.

Once getting used to it, it is more like comfort programming than trickery programming - while heading for Aleste speed LOL!

Pointerarrays can be made from your existing things.
From whatever scattered things you get a linear view to walk thru without checks.
An array of addresses - simple and powerful.

The array descriptor (called "struct Arr" in the code) :

16bit address of the array
16bit size of the array, the amount of things added
16bit capacity (max size) of the array

The size values are the amount of things, and as the array contains 16bit pointers, the array takes twice the space as the size values. Before using arradd/arrremove, in the descriptor set the address, set the size to 0, set the capacity.

Walking a pointerarray with z80 stackpointer, comfortable and fast:

	DI
	ld iy,0
	add iy,sp
	
	ld sp,(array)  ;SP points to array
	ld a,(array+2) ;the size word. only loading 8bit, max 256 things, 
                               ;while add remove functions work up to 64k.
	ld b,a		;maybe add some check in case zero, nothing in the array
loop:
	pop HL ;next thing gotten in 11 cycles

	;now HL points to thing. do something.

	djnz loop
	
	ld sp,iy
	EI


Add your things to the array. And whenever a thing dies, remove it from the array. Doing that you can walk an array free of holes.

Specialize at will. For example have an array "scrollable" where you add sprites that get moved by the scroller. Register the address of the Y of all sprites in question. Then, walking thru the "scrollable" pointerarray, you move the right sprites without hole checks and without ID checks.

Generally recommended is an object pool with slots of e.g. 32 byte size. And that pool is the place where you get the holes from allocation/deallocation.

The objects may look like this, e.g. some two sprites object:

ID, Y,X,P,C , Y2,X2,P2,C2, direction

registering e.g. the turtle that scrolls with the background:

register Y and Y2 in "RAMSAT" and "scrollables". all sprites of the turtle to be scrolled and dumped to SAT.
register Y in "enemy bounding boxes": only register one sprite of a colorsprite (maybe. depends on your patterns).

Knowing the base address of the pool and having ID bytes, you also can do things without pointerarrays. Pointerarrays easily co-exist, get added to existing projects.

In below code, _R1 and _R2 are RAM variables (I got _R0 to _R7 in my projects).
And "error" does enter a loop that toggles border color between H and L.

	
	;hl: struct Arr , de:pointer to thing to add
	.globl arradd
arradd:
	ld iy,0
	add iy,sp

	ld sp,hl	;->struct
	pop hl		;array
	pop bc		;length

	add hl,bc
	add hl,bc

	ld (hl),e
	inc hl
	ld (hl),d

	inc bc

	push bc		;store back length
	pop bc
	pop hl		;capacity

	and a
	sbc hl,bc
	jr c,arradderr

	ld sp,iy
	ret
arradderr:
	ld hl,0x0a08
	jp error




	;R1: struct Arr, R2: pointer to thing
	;run with disabled interrupt
arrremove:
	ld iy,0
	add iy,sp
		
	ld sp,(_R1)
	pop hl	;array content
	pop bc  ;array length

	ld a,b
	or c
	jr z,armnullexit
	
	ld sp,hl

	ld a,b
	ld b,c
	ld c,a

	inc b
	dec b
	jp z,armincskip
	inc c		;double jp nz . c is counter hi byte
armincskip:

	ld de,(_R2)
	ld a,e
arml:
	pop hl
	cp l
	jr z,armlofound
armnotfound:
	djnz arml
	dec c
	jp nz,arml
armnullexit:
	scf ;set carry flag if not found
	ld sp,iy
	ret

armlofound:
	ld a,d
	cp h
	ld a,e
	jp nz,armnotfound
	
	;move tail up 2 bytes
	push af		;2x dec sp, overwriting what is to be killed anyways.
	ld hl,0
	add hl,sp
	ex de,hl
	ld hl,2
	add hl,de

	inc b
	dec b
	jp z,armdecskip
	dec c		;bc back to normal
armdecskip:
	ld a,b
	ld b,c
	ld c,a
	
	sla c
	rl b		;length x 2 : pointers

	ldir			;todo bc = 0 ?
	
	;dec array.length
	ld sp,(_R1)
	pop hl
	pop bc
	dec bc
	push bc

	and a   ;clear carry
	ld sp,iy
	ret

Entrar ou registrar-se para comentar

Por retrocanada76

Hero (542)

imagem de retrocanada76

01-09-2011, 05:54

Ok I understood the message. Aleste has tons of objects. My mario still doesn' t need it for now, I think its an overkill Smile If I face problems i might take a look on it on future. Thanks for the code.

Por wouter_

Champion (508)

imagem de wouter_

01-09-2011, 11:48

Once getting used to it, it is more like comfort programming than trickery programming - while heading for Aleste speed LOL!
Hi hit9918,
Thanks for posting these routines, there are some useful ideas in them. Though I believe when speed is important (as you seem to suggest with 'Aleste speed'), it's very hard to provide routines that can be reused without modification in other projects. In the comments below I'll list some alternatives for several aspects of these routines. It really depends on the details of the project whether your original code or the alternative(s) are better.

The array descriptor (called "struct Arr" in the code):
16bit address of the array
16bit size of the array, the amount of things added
16bit capacity (max size) of the array

Let's start with the array descriptor:

  • The capacity field: this field is only used to detect errors in the array-add routine. This can be very useful when you're still developing/debugging the code. But once the code gets stable, you often don't need this.
  • The size field: depending on whether you more often loop over the array or more often add/remove elements, it may be faster to store:
    1) number of elements (current situation)
    2) number of used bytes in the array (2 x num elements)
    3) address of the first free position in the array
    In some cases it may even be faster to not have a size field at all. For example a fixed-size array or an array with a sentinel element at the end. See also the remark below about looping over the array.
  • The start address field. This may be useful in some cases, but I think often it's possible to let the array start directly after the last field in the array descriptor. In that case this field can be removed.

So in some situations it's possible to get rid of the array descriptor completely. This is also how I've seen the 'use-SP-as-data-pointer'-trick been used most often in existing code. And having no explicit array descriptor also often results in the fastest code.

Walking a pointerarray with z80 stackpointer, comfortable and fast:
First a detail:

	ld iy,0         ; 16 cycles
	add iy,sp       ; 17 cycles
	...
	ld sp,iy        ; 12 cycles

You need to store/restore the SP in all routines, currently this takes 45 cycles.

	ld (save_sp),sp ; 22 cycles
	...
	ls sp,(save_sp) ; 22 cycles

This alternative takes 1 cycle less. And as a bonus it keep the IY register free for other uses (though in general you should try to avoid using IX/IY).

Now about the loop itself

	...
	ld sp,(array)  ; SP points to array
	ld a,(array+2) ; the size word. only loading 8bit, max 256 things, 
	ld b,a         ; maybe add some check in case zero, nothing in the array
	; need to check for b=0? 
loop:	pop hl         ; next thing gotten in 11 cycles
	; now HL points to thing. do something.
	djnz loop
	...

A potential problem in this routine is that at the point where it says 'do something', there aren't that many free registers. And the stack isn't available to temporarily push/pop some stuff. In certain cases this alternative may be better:

	...
	ld sp,(array)  ; SP points to array
	jp start       ; if there's at least 1 element, replace this with 'pop hl'
loop:   ; do something with HL
start:	pop hl         ; next thing gotten in 11 cycles
	ld a,h
	or l
	jp nz,loop     ; HL=0 -> exit loop
	...

Compared to the routine above, the B register is now free to do stuff. Though the loop-exit-test is 7 cycles slower.

arradd:


As already mentioned above, in some cases it may be possible to remove the check for capacity. And if array-add is a very frequent operation it may be better to instead of storing the length of the array, store a pointer to the first free position.

arrremove:


This routine is quite complex, I didn't look at all the details, but some possible things to investigate:

  • If the order of the elements doesn't matter, it may be faster to swap the to-be-removed element with the last element in the array instead of shifting all tail elements 1 position to the front.
  • I didn't check, but it _might_ be faster to search the to-be-removed element using the CPIR instruction
  • Of course if the array can never contain more than 256 elements (like the original loop-over-elements code assumed) this routine can be simplified quite a bit.
  • In some cases you know the to-be-removed element must be present in the array. That also allows to simplify some things.

As I said above, not all suggested alternatives are always better than the original code. It really depends on the details of the project. I just hope these alternatives encourage other people to not blindly copy the code, but instead cherry-pick the desired features and end up with something better suited for their specific needs.

Por hit9918

Prophet (2927)

imagem de hit9918

01-09-2011, 18:24

@wouter_ , cool stuff!


ld (save_sp),sp ; 22 cycles
...
ls sp,(save_sp) ; 22 cycles

I am surprised by this. I think I used a register because of wanting to write multitasking safe functions - but that is a thought error, because stackpointer usage must disable interrupts anyway.


Though I believe when speed is important (as you seem to suggest with 'Aleste speed'), it's very hard to provide routines that can be reused without modification in other projects.

The idea is that these functions get only called when an enemy is created or dies. This is extremely rare compared to all the action done every frame. And for this special job, "remove one single thing out of an array, close the hole and then walk away", I think the speed is very good.

In spritesort, I use compatible descriptors, but of course it never does call add/remove. As I take all things from an array to distribute to two others, I just POP along it. And at the end set array size to 0. I did not think of doing "removes" on this array, because the need of collapsing a single hole did not occur.

In my "shoot 64 sprites" demo, as long as nothing is shot, the whole thing runs permanently with zero calls to arradd or arrremove. Still arradd and arrremove are the basis for the existance of these arrays that I am walking without checking holes.

The only other thing I can imagine for fast remove is linked lists.
I again got in mind the special usage mentioned above.

To be able to register any sub-part of an object, the link pointers got to be allocated in a separate pool. If they would be in the object, they would cause additional INC HL to walk over them in objects, a bad permanent load every frame.

link structure: 16 bit next, 16bit object, 16 bit previous

The typical walking:

	pop hl ;hl points to next
	pop de ;de points to object
	ld sp,hl ;sp points to next

Extra instructions and needing the valuable DE, external link structs too cause bad permanent load.


loop: ; do something with HL
start: pop hl ; next thing gotten in 11 cycles
ld a,h
or l
jp nz,loop ; HL=0 -> exit loop

This can be used with existing pointerarray code, poking two 0 bytes at the end of the array. If the array is fully filled to capacity, you get an array overrun. So if one intends this usage, initialize the capacity field decremented by 2.

Por hit9918

Prophet (2927)

imagem de hit9918

01-09-2011, 20:56


I just hope these alternatives encourage other people to not blindly copy the code

But ironically this is the usage I posted it for, to blindly copy this code Big smile

The idea was not the best code for everything, but for projects that run checks on dead enemies.
When I talk about how nice the pointerarray is, what would be the first step in actually trying it out, write that itching remove code.