Scanning tables

There are several ways to scan a table that is 256 bytes or smaller, thanks to the many indexed addressing modes available. 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.

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

        lda #0
        ldy #0
loop:   sta table,y       ; Y = 0 through size-1
        iny
        cpy #size
        bne loop

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:

        lda #0
        ldy #size
loop:   dey               ; decrement BEFORE sta
        sta table,y       ; Y = size-1 through 0
        bne loop

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:

        lda #0
        ldy #size - 1     ; size must be 128 or less
loop:   clc
        adc table,y       ; Y = size-1 through 0
        dey
        bpl loop

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:

        lda #0
        ldy #size
loop:   clc
        adc table-1,y     ; Y = size through 1
        dey
        bne loop

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:

        ldy #0
loop:   cmp table,y       ; Y = 0 through size-1
        beq found
        iny
        cpy #size
        bne loop
        
found:  ...

The original approach works, but there is one as efficient as the backwards approach. The idea is to start the loop with the Y equal to the negative of size, then increment it until it reaches zero. We adjust the table address to compensate, so that when it starts, it access the first byte of the table:

        ldy #-size
loop:   cmp table - (<-size),y     ; Y = -size through -1
        beq found
        iny
        bne loop
        
found:  ...

This is somewhat tricky. Consider operation when size is 3. The negative of that is $FD in two's complement. So Y starts out with the value $FD. Then, subtract $FD from the table address. The first time through the loop, it accesses table-$FD+$FD, that is, table+0, as desired. Then it increments Y to $FE, and accesses table-$FD+$FE, that is, table+1, also as desired. It increments Y to $FF, accesses table+2, then increments Y to 0 and exits the loop.

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.