koitsu wrote:
I will try to type these up this weekend. They're long -- usually 1-3 pages. They're commented, but if I was to provide "just a snippet" it wouldn't provide enough useful educational context.
As promised, I took a look at these in detail this weekend. The book (
"Programming the 6502" by
Rodnay Zaks, 1983, 4th edition, ISBN 0-89588-135-7) has an entire chapter on data structures. This includes linked lists, binary trees, sorting algorithms, overall data structure creation/organisation, etc.. They're long and include descriptions as well as flow chart diagrams to help with comprehension. The code is commented, though sparsely (normal for the time, given screen widths).
The code is written for
ASM 65 from Rockwell, which was a 6502 assembler written in BASIC for HP 2000F computers. Younger folks unfamiliar with some of the more "arcane" assembler syntaxes of the 80s might not comprehend the syntactical sugar. For example:
* refers to the current PC at assemble-time, so something like
* = $0 sets the PC to $0000, hence any variables/labels you define there get assembled starting with a base address of $0000 (i.e. zero page) (and, of course, it's still your own responsibility to populate zero page with actual data);
.WORD declares an explicit 16-bit value (e.g.
.dw $1234 or
.db $34, $12 in more common-day assemblers). Furthermore, the code is not intended for the NES, but should work given that RAM in the NES resides from $0000 to $07FF.
I would prefer to scan these pages and put them up somewhere, especially since flow chart diagrams are heavily used, except as is common with most reference books, the content is copyrighted ((C) 1983 SYBEX Inc. 2344 Sixth Street, Berkeley, CA 94710; founded by Dr. Zaks); the code would not OCR well given the font, size, and weight. So what I've typed up below is indeed a copyright violation; I'm hoping SYBEX will allow me a bit of leeway.
Here are the general examples in book, all from Chapter 9, which use indexed indirect (
(foo,x)) addressing:
1. A hashing algorithm (8 pages; 2 pages of code; long)
2. Bubble sort (5 pages; 1 page of code; short)
3. A merge algorithm (4 pages; 1 page of code; semi-long)
The short of it: in all 3 cases, indexed indirect addressing is used to reference a 16-bit pointer (or series of pointers) which are used to point to one or more data structures.
I'll include the code from #2 above, since it's the shortest:
Fig. 9-48: Bubble-Sort: Memory Map
Code:
+-------------+
0000 | | -----+
|- TABLE PTR -| |
0001 | | |
+-------------+ |
| | |
| | |
| | |
+-------------+ |
0200 | | |
| PROGRAM | |
| | |
+-------------+ |
| | |
| | |
| | |
+-------------+ |
| NUMBER n | <----+
+-------------+
| ELEMENT 1 |
+-------------+
| ELEMENT 2 |
+-------------+
| | Y X
+-------------+ +-------------+ +-------------+
| | <----| PTR | | EXCHANGED? |
+-------------+ +-------------+ +-------------+
| | CURRENT ELEMENT
+-------------+
| |
+-------------+
| ELEMENT n |
+-------------+
What's omitted in the description (which I've also omitted, because it's an entire page) is what the value of $0600 is that
TAB contains. This is the actual address in RAM that contains the data structure described (i.e. the actual data to sort). In other words
NUMBER n is at $0600,
ELEMENT 1 is at $0601, etc.. This data must reside in RAM because the routine actually modifies the RAM area it's reading from. I feel all that's pretty important to know. :-)
Fig. 9-49: Bubble-Sort Program
Code:
* = $0
TAB .WORD $600
* = $200
SORT LDX #0 ;SET EXCHANGED TO 0
LDA (TAB,X)
TAY ;NUMBER OF ELEMENTS IS IN Y
LOOP LDA (TAB),Y ;READ ELEMENT E(I)
DEY ;DECREMENT NUMBER OF ELEMENTS TO READ.
BEQ FINISH ;END IF NO MORE ELEMENTS
CMP (TAB),Y ;COMPARE TO E'(I)
BCS LOOP ;GET NEXT ELEMENT IF E(I)>E'(I)
EXCH TAX ;EXCHANGE ELEMENTS
LDA (TAB),Y
INY
STA (TAB),Y
TXA
DEY
STA (TAB),Y
LDX #1 ;SET EXCHANGED TO 1
BNE LOOP ;GET NEXT ELEMENT
FINISH TXA ;SHIFT 'EXCHANGED' TO A REG. FOR COMPARE...
BNE SORT ;IF SOME EXCHANGES MADE, DO ANOTHER PASS.
RTS
P.S. -- There's actually a checksum routine in this book that looks neat/useful too, but it doesn't use the discussed addressing mode, so it's off-topic.