64-bit math on 68000

The 68000 is a 16-bit CPU that can do operations on 32-bit numbers. That usually should be enough, but in rare cases (e.g. a game with ultra-inflated scoring) you may want even larger and use 64-bit numbers. Luckily, the 68000 has some provisions to work with numbers of arbitrary sizes.

Yes, this is a 16-bit CPU with 32-bit instructions working with 64-bit numbers, because why not?

The Extend flag

Most 68000 instructions set the condition flags, which are used by branch instructions and such. One of those flags however is to allow working with large numbers: the Extend flag holds the carry or borrow of the last operation (note that this is not the same thing as the Carry or Overflow flags).

There are also a few "extended" instructions to go with it: addx, subx, etc. The way it works is that you start the operation with the "normal" instruction (e.g. add) on the lower bits, then execute the "extended" instructions (e.g. addx) on the higher bits. The Extend flag is used to pass carry from the lower to the higher bits. You can perform operations on numbers with arbitrary sizes this way.

Note that the Extend and Carry flags are not the same, and a few instructions will affect them differently (e.g. move will clear Carry but not touch Extend). Extend is used for working with large numbers, Carry is used for comparisons.

Addition

To add two 64-bit numbers, you need two instructions: first do add.l on the low halves of both operands, then addx.l on the high halves. The addx instruction resumes the last addition (in particular moving the carry from the low half to the high half). Flags will be set accordingly after both instructions are executed.

Since registers are only 32-bit, we need to use two registers to hold a single 64-bit value. In this case, d0 and d1 hold the upper and lower halves of the destination operand, while d2 and d3 hold the source operand: 

    add.l   d3, d1
    addx.l  d2, d0

Most of the time you'll do the above.

You can also use addx when both operands are in memory, in this case two address registers hold pointers to the end of the numbers (i.e. first byte after each of them). Numbers must be stored big endian for this to work. See the example below — note that we need to reset the flags manually since the add instruction doesn't support an operand combination like this: 

    lea     8(a0), a0
    lea     8(a1), a1
    
    and.b   #$00, ccr
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)

One big problem is that there's no immediate form for the addx instruction, so if you have to add a fixed value you'll need to store it in registers or memory. Note that the move and moveq instructions don't change the Extend flag, so it's safe to use between the two additions: 

    ; Add 100 to 64-bit value in d1:d0
    ; Assumes that d2 is free to use
    moveq   #100, d2
    add.l   d2, d1
    moveq   #0, d2
    addx.l  d2, d0

Substraction

Substraction is similar to addition, but using sub and subx instead: 

    sub.l   d3, d1
    subx.l  d2, d0

Same limitations as addx apply.

Negation (flip sign)

Negation is also similar to addition, but using neg and negx instead: 

    neg.l   d1
    negx.l  d0

For the record, unlike addx and subx, you can actually use negx with just about every valid operand (except a0-a7).

Comparison

Here we run into a problem: there is not a cmpx instruction, so the obvious approach doesn't work. If you want to do a comparison, you'll need to waste a couple of registers (or 8 bytes in memory) to do a substraction and ignore its result: 

    ; assume d4-d5 are free
    move.l  d1, d5
    move.l  d0, d4
    sub.l   d3, d5
    subx.l  d2, d4
    ; flags will be set here

If you can discard at least one of the operands then you could instead store the result of the substraction there and avoid wasting anything else.

Another thing you can do if you need to jump away when both values are different, you may be able to get away by checking if either pair of halves is different: 

    cmp.l   d3, d1
    bne     Different
    cmp.l   d2, d0
    bne     Different

You can't do the reverse to check if they're identical (because one pair could be but not the other), but you could instead check if they're different to hop over the actual jump: 

    cmp.l   d3, d1
    bne.s   Different
    cmp.l   d2, d0
    bne.s   Different
    bra     Identical
Different:

If you can get away with just checking if a 64-bit number is positive or negative, you can test the sign of the upper half: 

    tst.l   d0
    bpl     Positive
    tst.l   d0
    bmi     Negative

Boolean operations

Boolean operations (and, or, eor, not) are not affected across bits, so you can apply them directly on the individual halves. Just bear into mind that the flags will only reflect the result of the last half you touch, so you may need to compare the values manually if that's relevant. 

    and.l   d3, d1
    and.l   d2, d0
    or.l    d3, d1
    or.l    d2, d0
    eor.l   d3, d1
    eor.l   d2, d0
    not.l   d1
    not.l   d0

Extend 32-bit to 64-bit

Even when working with 64-bit values, it's likely that most of the time you'll be dealing with 32-bit ones. This means that sooner or later you'll find yourself wanting to use a 32-bit number in a 64-bit operation which means you'll need to convert it to 64-bit. These examples assume that the value is in d1 and will be extended to the d0/d1 pair.

For unsigned numbers the upper half will be always 0, so: 

    moveq   #0, d0

For signed numbers it's trickier: you need to make the upper half 0 if it's positive or -1 if it's negative. One way to do this would be to check the sign flag, then use the smi instruction (which sets a register to 0 when sign is positive or -1 when negative), then extend the value into a longword. 

    tst.l   d1
    smi.b   d0
    ext.w   d0
    ext.l   d0

To extend from 8-bit or 16-bit to 64-bit, first extend them to 32-bit as usual then do one of the above.

Even larger values

Do you need even larger values? In theory, you can use these instructions to work with arbitrarily large numbers (though the number of registers may be a problem, so you may need to work off memory).

The following adds two 128-bit numbers (one in d0-d3 and the other in d4-d7): 

    add.l   d7, d3
    addx.l  d6, d2
    addx.l  d5, d1
    addx.l  d4, d0

The following adds two 256-bit numbers in memory (pointed by a0 and a1, respectively), since there's no way to fit both of them in registers. Note that we need to clear the flags manually because the add instruction doesn't take this operand combination. 

    lea     32(a0), a0
    lea     32(a1), a1
    
    and.b   #$00, ccr
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)
    addx.l  -(a1), -(a0)

Finally, remember that these "extended" instructions come in byte, word and long variants, so you aren't restricted to sizes multiple of 32-bit.