Some pointers for beginners – Decisions!

Easy – Deciding yes/no

This is (should be) usually a decision between 0 (zero) and 1 (or non zero).
A code like:

   lda value
beq oneDecision
otherDecision
...
bra continue
oneDecision
...
continue:

or “reverse”

   lda value
bne oneDecision
otherDecision
...
bra continue
oneDecision
...
continue

The only thing that might be unefficient is the compare part. Optimally you do it like above.
(if there is an even distribution, if you KNOW one case happens more often, than take the branch with that one, since it ultimatley is 3 cycles faster (the bra continue takes 3 cycles).

The less optimal version would be:


lda value
cmpa #0 ; <------ not needed
beq oneDecision
otherDecision
...
bra continue
oneDecision
...
continue

Or even:

   lda value
cmpa #0 ; <------ not needed
beq oneDecision
bra otherDecision ; <------ one branch to many
oneDecision
...
bra continue
otherDecision
...
continue

Still Easy: Deciding yes/no/perhaps

Optimally this should be a decision between 0 (zero), a negative value, and a positive value.

   lda value
bmi firstDecision
beq secondDecision
thirdDecision
...
bra continue
firstDecision
...
bra continue
secondDecision
...
continue

Deciding between “n” continuous values

These decisions should be made with a value between 0 and “n”. Depending on the “n” the best way to do this is a jump table. The good thing about jump tables is, that the cycle usage of each value is constant and not to high. Whereas if do a compare strategy like:

  lda value
beq firstCase
cmpa #1
beq secondCase
cmpa #2
beq thirdCase
...
bra defaultCase

firstCase
...
secondCase
...
thirdCase
...
defaultCase
..

You can easily see, the further “down” you get in your scenario – the more cycles are “wasted” on comparissons.

Here we use a technique called jumptables. A jumptable basically is a collection of pointers to the desired location of each comparisson. The jump pointer to take can be calculated (rather then gotten via comparisson).
Example:
(Note: example only value up to 63 values, higher values must not use register A, but rather 16 bit (D) )

jumpTable
dw firstCase
dw secondCase
dw thirdCase
dw fourthCase
dw fifthCase
...

lda value
lsla ; double the value, since the pointers are WORDS not BYTES
ldx #jumpTable
jmp [a,x]
...
firstCase
...
secondCase
...
thirdCase
...
fourthCase
...
fifthCase
...

Deciding between “n” random values

For all previous types there was only one “good” implementation. For random values you have to decide between two variants.
a) less memory usage
b) higher (constant) speed

Variant a) “less memory usage”
a straight forward compare:

   lda value
cmpa #10
blo lower10
cmpa #20
blo between10And20
cmpa #30
blo between20And30
...
lower10
...
between10And20
...
between20And30
...

As you see – the cycles used grow linear the higher the value gets.

Note:
If you compare more than about 35-40 values – the higher speed variant shown below also uses less memory!

Variant b) higher /constant speed:
This variant has a constant (high) memory imprint – but also constant cycles to do your decision.
The implementation is a variation of the jump table.
Example:

 
; load a random value to "a" (0-255) -
; can be optimized using a random_b function

jsr random_a
tfr a,b
clra

; now register D contains a 16 bit value between 0 - 255
; extending the value is neccessary, since values above 127
; are taken as negative values ***NOTE BELOW***

ldx #valueTable
lda d,x

; get the value
; again, this works for values between 0-63,
; for higher values some adjustments must be made

lsla ; double the value, since the pointers are WORDS not BYTES
ldx #jumpTable
jmp [a,x]
...

firstCase
...
secondCase
...
thirdCase
...
fourthCase
...
fifthCase
...


; note below values are "ordinary" bytes, if the values range from 0-63
; the "lsla" above can be left out, and the values below
; than must be doubled

valueTable
db 0 ; range 0 - 4 have the value 0
db 0
db 0
db 0
db 0
db 1 ; range 5 - 9 have the value 1
db 1
db 1
db 1
db 1
...
; up to 255 "db" statements for each of
; the possible 0-255 values one data

jumpTable
dw firstCase
dw secondCase
dw thirdCase
dw fourthCase
dw fifthCase

***NOTE:
The 16bit part can be left out if you create a valueTable in two directions.
Than all “positve” values must be located “after” the valueTable, and all “negative” values must be located “before” the valueTable. But I left this optimization out, because it gets more confusing!)

One thought on “Some pointers for beginners – Decisions!

  1. Peer

    Oh great, these are also topics / tricks which we touch in my Vectrex C programming class, in C and from the C programmer’s point of view. Mostly in the context of how to write efficient implementations of state machines in C. I will use this here as well as a reference and as recommend readings, as this explains it all from an assembly lanugae programmer’s point of view. It perfectly complements the things we do in class. Once more thanks for writing this up.

Leave a Reply to Peer Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.