Speed-coding for the 6502 – a simple example

Summary

Usually clocked at 1MHz, with no hardware support for multiplication or division, and limited support for bit shifting, it is often important to take a step back from an algorithm in order to make it do the same thing, hundreds of times faster. Note: this article doesn’t describe any technological breakthrough or extremely clever new way of doing things. It’s just a real-life example using a little part of an algorithm I made, and where at first, I stopped at step 2 instead of going all the way to the last step. In this example, we want to scale down a 256×192 bitmap down to 192×144, which means the scaling factor is 3/4. We’re going to have to apply this factor to every one of the 192 lines, and for each line, for every one of the 256 pixels composing the line. This means we’ll have to apply our factor (192*256)+192 times, 49344 times in total. We can also note that the numbers we want to scale are 8 bits, but at first, it looks like we’ll need to do 16 bits math, as 256*3 is greater than 256. The first, naive way is to do scaled_value = value*3/4: lda value ; load the value ldx #3 ; load the multiplicator jsr mult_a_x ; jump to the multiplication function ; which returns a 16-bit number in A and X ldy #4 ; load the divisor jsr div_ax_y ; jump to the division function sta scaled_value; we have our result! Given that multiplication and division is made via software, and each one takes about 200 cycles (approximately), our image scaling will require about 20 million cycles, aka 20 seconds at 1MHz! So let’s try to avoid multiplication and division. Notice our formula can also be written as scaled_value = (value*2 + value)/4, and as we know, multiplying by 2 is shifting left, and dividing by 4 is shifting right twice: scaled_value = (value<<1 + value) >> 2, which in assembly, translates to: lda value ; load the value ldx #$00 ; init the high byte of the multiplication to zero stx tmp1_zp ; store it in a variable, as the 6502 can't bit- ; shift the X or Y registers asl ...