Extended Precision Arithmetic

From Intellivision Wiki
Revision as of 00:22, 12 January 2005 by Mr z (talk | contribs) (Comparison)
Jump to: navigation, search


Sometimes programs need to operate on numbers longer than 16 bits. Common operations include addition, subtraction, comparison and shifting. (Shifting is important for implementing more complicated operations, such as multiplication and division.) The Carry Flag and occasionally the Overflow Flag serve an important role in implementing extended precision arithmetic.


Addition and Subtraction

To add two 32-bit numbers, one must connect two ADDs with an ADCR. The following example illustrates adding the 32 bit number in R1:R0 to R3:R2. The upper halves of the numbers are in R1 and R3. The lower halves are in R0 and R2.

  ADDR R0, R2    ; Add lower halves.  This may result in a carry
  ADCR R3        ; Add the carry into R3
  ADDR R1, R3    ; Add the upper halves.

Things get slightly more complicated if you try to add numbers longer than 32 bits. This is because ADCR itself may generate a carry. The following example illustrates adding two 64 bit numbers. This time, the first number is stored in memory pointed to by R4, and the sum is held in R3:R2:R1:R0. The most significant portion is in R3, and the least significant portion is in R0.

  ADD@ R4, R0    ; Add bits 0..15 together.
  ADCR R1        ; propagate the carry to bits 16..31 
  ADCR R2        ; propagate the carry to bits 32..47
  ADCR R3        ; propagate the carry to bits 48..63
  ADD@ R4, R1    ; Add bits 16..31 together.
  ADCR R2        ; propagate the carry to bits 32..47
  ADCR R3        ; propagate the carry to bits 48..63
  ADD@ R4, R2    ; Add bits 32..47 together.
  ADCR R3        ; propagate the carry to bits 48..63
  ADD@ R4, R3    ; Add bits 48..63 together.

Subtraction is similar to addition. When subtracting two numbers that are larger than 16 bits, it's important to realize that all the "internal" portions of the subtract are effectively "unsigned." Thus, the Carry Flag can be thought of as a "Not Borrow" bit for the lower order terms. To subtract two extended precision numbers, one must include one additional step to correctly handle borrowing.

The following example illustrates subtracting the 32 bit number in R1:R0 from R3:R2. The upper halves of the numbers are in R1 and R3. The lower halves are in R0 and R2.

  SUBR R0, R2    ; Subtract the lower halves.  This may "borrow" from the upper half
  ADCR R3        ; \_ Subtract 1 if we need to borrow, otherwise leave R3 alone.
  DECR R3        ; /  (ADCR and DECR cancel in the not-borrow case.)
  SUBR R1, R3    ; Subtract the upper halves.

If you're feeling hackish, you can speed this up in the non-borrowing case like so:

  SUBR R0, R2    ; Subtract the lower halves.  This may "borrow" from the upper half
  ADCR PC        ; Skip next instruction if we did not borrow
  DECR R3        ; Decrement R3 if we borrowed
  SUBR R1, R3    ; Subtract the upper halves.

Subtracting longer numbers has the same complications as adding longer numbers. The following example illustrates subtracting two 64 bit numbers. This time, the first number is stored in memory pointed to by R4, and the difference is held in R3:R2:R1:R0. The most significant portion is in R3, and the least significant portion is in R0. This code moves all the DECRs to a set of subtracts up front.

  DECR R1        ;\
  SUBI #2, R2    ; |- precompensate for not-borrows.
  SUBI #3, R3    ;/
  SUB@ R4, R0    ; Subtract bits 0..15 from each other.
  ADCR R1        ; propagate the not-borrow to bits 16..31 
  ADCR R2        ; propagate the not-borrow to bits 32..47
  ADCR R3        ; propagate the not-borrow to bits 48..63
  SUB@ R4, R1    ; Subtract bits 0..15 from each other.
  ADCR R2        ; propagate the not-borrow to bits 32..47
  ADCR R3        ; propagate the not-borrow to bits 48..63
  SUB@ R4, R2    ; Subtract bits 0..15 from each other.
  ADCR R3        ; propagate the not-borrow to bits 48..63
  SUB@ R4, R3    ; Subtract bits 0..15 from each other.

Comparison

For Addition and Subtraction, one works from the low end of the number towards the high end. For comparison, the opposite is true. To compare two large numbers, one first compares the most significant words. If they compare as equal, the process moves to the next most significant words. The process continues until two corresponding words miscompare—at which point the program has established one number as larger than the other—or the program reaches the end of both numbers, indicating they are equal.

The process works identically regardless of whether the two numbers are signed or unsigned. The only difference between signed and unsigned comparison is whether one uses BGT/BLT (signed numbers) or BNEQ/BNC (unsigned numbers).

The following example compares the signed 32-bit number in R1:R0 to the signed 32-bit number in R3:R2. R1 and R3 hold the upper 16 bits. R0 and R2 hold the lower 16 bits.

    CMPR R3, R1   ; is R1 greater, equal-to or less than R3?
    BLT  lesser
    BGT  greater
    CMPR R2, R0   ; Upper halves tie, so check lower halves
    BLT  lesser
    BGT  greater
    ; If we get here, R1:R0 = R3:R2
equal:

Here's the same example, using unsigned arithmetic. Recall that BNC is the unsigned variation of "branch if less than".

    CMPR R3, R1   ; is R1 greater, equal-to or less than R3?
    BNC  lesser
    BNEQ greater
    CMPR R2, R0   ; Upper halves tie, so check lower halves
    BNC  lesser
    BNEQ greater
    ; If we get here, R1:R0 = R3:R2
equal:

Notice that the unsigned example uses BNEQ, since the CP1610 lacks a conditional branch that's the unsigned equivalent of "branch if greater than."

Shifting

To do.