Scanning tables

There are several ways to scan a table that is 256 bytes or smaller, thanks to the many indexed addressing modes available (for larger tables, see Scanning Large Tables). Scanning could be reading values looking for a particular one, writing multiple values, copying, etc. Some are more efficient than others, or simpler to code.

Common approaches

For example, this code fills a table of size bytes with 0, from beginning to end:

<source lang="6502">

       lda #0
       ldy #0

loop: sta table,y  ; Y = 0 through size-1

       iny
       cpy #size
       bne loop

</source>

It's often more efficient to scan backwards, since DEY and similar instructions implicitly compare the decremented value with zero. Since it doesn't matter which direction we fill a table, backwards is preferable:

<source lang="6502">

       lda #0
       ldy #size

loop: dey  ; decrement BEFORE sta

       sta table,y       ; Y = size-1 through 0
       bne loop

</source>

Note how the DEY is before the STA. If it were after, once Y reached 0, the loop would end, even though the STA would never have been executed with Y=0.

If we're doing something besides simply filling, we might not be able to put the DEY before the table operation. For example, if we're finding the sum of all values in the table using ADC, the ADC will alter flags. We could add a CPY #0 just before the branch, but then we're back with code similar to the original code. If the table is 128 bytes or smaller, we can instead use the BPL instruction:

<source lang="6502">

       lda #0
       ldy #size - 1     ; size must be 128 or less

loop: clc

       adc table,y       ; Y = size-1 through 0
       dey
       bpl loop

</source>

Once DEY decrements Y to 0, BPL still branches, since 0 is considered positive. The loop then executes a final time, with Y=0. Then DEY decrements it to $FF (-1), and BPL falls through.

If the table is more than 128 bytes, we can still use BNE, and adjust the table address to compensate:

<source lang="6502">

       lda #0
       ldy #size

loop: clc

       adc table-1,y     ; Y = size through 1
       dey
       bne loop

</source>

Efficient forwards scanning

Sometimes a table must be scanned forwards, not backwards. For example, we might want to find the first occurrence of a particular byte equal to A:

<source lang="6502">

       ldy #0

loop: cmp table,y  ; Y = 0 through size-1

       beq found
       iny
       cpy #size
       bne loop
       

found: ... </source>

The original approach works, but there is one as efficient as the backwards approach. First, consider scanning a 256-byte table forwards. We don't need a compare since Y will wrap around to 0 on the 256th iteration. So this is as fast as the backwards version:

<source lang="6502">

       ldy #0

loop: cmp table,y  ; Y = 0 through $FF

       beq found
       iny
       bne loop

</source>

Now, let's say we only want to scan the last 3 bytes of table. We would simply start the loop with Y set to $FD rather than 0. It would scan entries $FD, $FE, and $FF, then end (or find what it was looking for):

<source lang="6502">

       ldy #$FD

loop: cmp table,y  ; Y = $FD through $FF

       beq found
       iny
       bne loop

</source>

Since we can use the above loop to scan the last 3 bytes of table, we can use it to scan any three bytes of memory; it doesn't matter whether they are the last 3 bytes of a 256-byte table, or a table that's only 3 bytes long. But it does add $FD to whatever table address we use, so we'll need to subtract that. The following scans a 3-byte table forwards for a value:

<source lang="6502">

       ldy #$FD

loop: cmp table - $FD,y  ; Y = $FD through $FF

       beq found
       iny
       bne loop

</source>

The general pattern is to load Y with the $100-size, and subtract that same value from table:

<source lang="6502">

       ldy #$100-size

loop: cmp table - ($100-size),y  ; Y = $100-size through $FF

       beq found
       iny
       bne loop

</source>

There is a slight introduced by this approach: since most indexed instructions take an extra cycle if the low byte of the address added to the index exceeds $FF, this is likely to introduce an extra cycle. Using the 3-byte table example, if table's address were $10ED, the compare would assemble to CMP $0FF0,Y. Then, with Y=$FD, there would be a page crossing, adding an extra cycle. Since this approach uses the upper portion of Y's range, rather than the lower portion, it's more likely to cause page crossings. However, one cycle due to a page crossing is less than two cycles due to an immediate compare.

This approach has the efficiency of the decrement approach while avoiding accessing the table in reverse. One downside is that finding the actual index of the current byte requires some calculation. Also, since it's somewhat tricky to code, backwards is still preferred where the access order doesn't matter.