Fibonnacci sequence in 6502 assembler

Question

I am trying to build a Fibonacci sequence in a 6502 assembler. It needs at least one add function, a least one branch function, and at least one compare function. I know how to add and store integers, but I am confused by branch and compare functions.

I use this instruction set below.

Answer 1

I assume you are limited to using the instructions mentioned in the table. So you have CPX and you have BNE.

CPX compares the content of the X register with its operand. It does this by subtracting the operand from X and then setting some flags accordingly.

The 6502 has a status register containing a number of flags i.e. one bit values which represent "true" or "false". The flags are:

• N: "negative" is 1 if the result of the operation is negative in a 2's complement sense. e.g. if X contains $01 and you do CPX #$03 the result would be $fe which is -2 in 2's completement and the N flag will be set.
• Z: "zero" is 1 if the result of the operation is 0, so CPX #$01 would set Z if X contains 1, or clear Z if X contains any other value.
• C: "Carry" this can be a bit confusing, but in the context of a compare like CPX it will be set if X is greater than the operand (interpreting both as unsigned). CPX #1 will set C for any value in X except 0 or 1.

There are several other flags, but we can ignore them because they are unaffected by CPX.

The branches in the 6502 work by inspecting one of the flags and then performing the jump, or not performing the jump depending on its value. There are two branches associated with each flag, one to jump if the flag is set and one to jump if the flag is clear.

For the C flag we have:

• BCS jump if the carry flag is set
• BCC jump if the carry flag is clear

For the N flag we have:

• BMI jump if the negative flag is set
• BPL jump if the negative flag is clear

The "MI" stands for "minus" and the "PL" stands for "plus"

For the Z flag, we have:

• BEQ jump if the zero flag is set
• BNE jump if the zero flag is clear

"EQ" means "equal to zero" and "NE" means "not equal to zero". These two opcodes could have been BZS and BZC respectively.

So, restricting yourself to the instructions in your list, If you have a loop counter at address loopCounter and the number of times you want to loop at address maxCount you could implement your loop as follows.

    lda #0
    sta loopCounter
loop:
    ; Do all the stuff you want to do for an iteration
    inc loopCounter
    ldx loopCounter
    cpx maxCount       ; sets Z if x and maxCount contain the same number
    bne loop           ; branches if Z not set i.e. x != maxCount

Note that the above always executes the loop code at least once and setting maxCount to zero will cause the loop to execute 256 times.

If you have the full 6502 instruction set you can make the above loop much more efficient. Even with just the DEX instruction (decrement X) you can store the count in X and count downwards. DEX is much faster than INC and DEX also affects the Z flag, so you don't need the CPX.

---

Addendum:

Not relevant to the question but I can't resist this, but the 14th Fibonacci number is 377 which doesn't fit in eight bits. If you want a really fast way to calculate any Fibonacci number that does fit in 8 bits, you can just do a lookup.

calculate8bitFibo:
     ; On entry X contains the zero based index of the number we want
     ; on exit A contains the Fibonacci number
     ; It is the caller's responsibility to make sure the index is in range
     lda fiboTable,x
     rts
fiboTable:
     .db 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 237

Answer 2

but I am confused by branch and compare functions

In C code we might use a structured statement, here a while loop:

count = -n;
do {
    // loop body
   count++;
} while ( count != 0 );
// more code

whereas using what can be called if-goto-label, the same (still in C) :

count = -n;
Loop1:
   // loop body
   count++;
   if ( count != 0 ) goto Loop1;
   // more code

So, hopefully you see that these two constructions are equivalent and identical and will thus run the same, even though the latter is a bit more verbose.  Both will run the same loop body for the same number of iterations.

The latter form, however, is much closer to assembly language, which also uses if-goto-label.

Key to assembly, then, is how the C-statement if ( count != 0 ) goto Loop1; is performed.  The issue with an if-goto-label statement in C is that there are generally too many operands for the processor to work with in one machine code instruction (here, those operands are count, !=, 0, Loop1 and we can imagine each of those operands, in the general case, will need to vary.)

So, the solution in many instruction sets is to split the if-goto-label construct into two instructions by connecting them using condition codes.  Here, the first is would be a compare of count and 0 that sets the condition codes, and the second is a branch using condition != and label target Loop1 that reads the condition codes.

These two instructions communicate via the condition codes, but you can read them as performing the if-goto-label construct via a two instruction sequence (here an extra instruction to clear the X register for the later cpx):

ldx #$0
cpx count
bne Loop1

the above is then the assembly pseudo-code translation for the C-based if-goto-label construct if ( count != 0 ) goto Loop1;.

Each processor's operation and assembly language varies a bit, so one general idea that works well is to:

• write algorithms in terms of control structures using C structured statements
• translate control structures to if-goto-label form, still in C
• translate if-goto-label statements to specific assembly