Software Divide

Just as early PDP-11 models had no hardware multiplication support, division routines also had to be provided in software.

The algorithm for division is similar to the "long division" technique done by hand. In code, this is a series of shifts and subtracts. As with multiplication, we can create an unsigned variant of the routine, and use it to create a signed variant.

The divide routine will take a dividend and a divisor as input, and return a quotient and remainder as the output. The quotient and remainder start at zero. For each bit, the quotient and dividend are shifted left. The carry flag is set to the high bit of the dividend when it was shifted. The remainder is rotated left, so any carry value is placed into its low bit. If the divisor is less than the remainder, it is subtracted from the remainder and the low bit of the quotient is set. This is repeated for each bit.

As an example, here are the steps to divide 19394 by 273. The numbers in the example are represented in binary, so we have

dividend:  0100 1011 1100 0010
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0000 0000
quotient:  0000 0000 0000 0000

After the first iteration, the only change is that the dividend is shifted left. Since the divisor is not less than the remainder, the quotient is left alone.

dividend:  1001 0111 1000 0100
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0000 0000
quotient:  0000 0000 0000 0000

At the second iteration, the dividend is shifted left. Since the high bit was set, the carry bit is set. This causes the remainder to shift left, setting its low bit to one, since the carry bit was set. The divisor is still less than the remainder:

dividend:  0010 1111 0000 1000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0000 0001
quotient:  0000 0000 0000 0000

At the third iteration, the dividend is shifted left, and the carry bit is cleared, since the hi bit of the dividend was zero. The remainder is shifted left, as well, but it's still less than the divisor:

dividend:  0101 1110 0001 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0000 0010
quotient:  0000 0000 0000 0000

This repeats, effectively rotating the top bits of the dividend into the remainder.. Six steps later:

dividend:  1000 0100 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 1001 0111
quotient:  0000 0000 0000 0000

At the tenth itertion, the dividend is shifted left, the remainder rotated left. At this point, the remainder is no longer less than the divisor, so the divisor is subtracted from the remainder, and the low bit of the quotient is set:

dividend:  0000 1000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0001 1110
quotient:  0000 0000 0000 0001

At the eleventh iteration, the quotient is shifted left (which is now useful since it's no longer zero), the divident is shifted left, the remainder rotated left, and is less than the divisor:

dividend:  0001 0000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0011 1100
quotient:  0000 0000 0000 0010

After two more iterations:

dividend:  0100 0000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 1111 0000
quotient:  0000 0000 0000 1000

At the next iteration, the remainder again becomes greater than the divisor, so the divisor is subtracted from the remainder, and the low bit of the quotient is set:

dividend:  1000 0000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 1100 1111
quotient:  0000 0000 0001 0001

And the next iteration again causes the remainder to become greater than the divisor:

dividend:  0000 0000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 1000 1110
quotient:  0000 0000 0010 0011

With the sixteenth and final iteration, the remainder is again greater than the divisor, and we end up with

dividend:  0000 0000 0000 0000
divisor:   0000 0001 0001 0001
remainder: 0000 0000 0000 1011
quotient:  0000 0000 0100 0111

Thus, dividing 19394 by 273 gives a quotient of 71 and a remainder of 11.

This algorithm can be used to make an unsigned word division routine:

; DIVWU (DIVIDEND, DIVISOR) -> R0: QUOTIENT, R1: REMAINDER
;
; UNSIGNED 16-BIT DIVISION
;

First, we check if we're trying to divide by zero. If so, we set the overflow flag and immediately return: this is an error.

DIVWU:  TST     4(SP)           ; CHECK THE DIVISOR
        BNE     DD1             ; IF NOT ZERO, CONTINUE
        SEV                     ; SET OVERFLOW (ERROR)
        RTS     PC              ; RETURN TO CALLER

Then, we stash some registers. Since there are so many shift operations, these should be done in registers for better performance.

DD1:    MOV     R2,-(SP)        ; SAVE R2
        MOV     R3,-(SP)        ; SAVE R3
        MOV     R4,-(SP)        ; SAVE R4

The registers are initialized.

        CLR     R0              ; R0 <- QUOTIENT
        CLR     R1              ; R1 <- REMAINDER
        MOV     10(SP),R2       ; R2 <- DIVIDEND
        MOV     12(SP),R3       ; R3 <- DIVISOR
        MOV     #20,R4          ; R4 <- COUNTER

Now, the iterations can begin. Shift the quotient left, shift the dividend left, rotate the carry into the remainder, check to see if it's equal than or greater than the divisor, and if so, subtract the divisor from the remainder and increment the quotient, setting its low bit

DD2:    ASL     R0              ; SHIFT QUOTIENT LEFT
        ASL     R2              ; SHIFT DIVIDEND LEFT
        ROL     R1              ; ROTATE REMAINDER LEFT, WITH CARRY
        CMP     R1,R3           ; IS DIVISOR <= REMAINDER?
        BMI     DD3             ; NO, CONTINUE
        SUB     R3,R1           ; REMAINDER -= DIVISOR
        INC     R0              ; SET LOW BIT IN QUOTIENT

Decrement the counter, and if it's not yet zero, iterate.

DD3:    DEC     R4              ; DEC COUNTER
        BNE     DD2             ; IF NOT ZERO, REPEAT

When we're done, restore the registers, indicate there's no error, and return.

        MOV     (SP)+,R4        ; RESTORE R4
        MOV     (SP)+,R3        ; RESTORE R3
        MOV     (SP)+,R2        ; RESTORE R2
        CLV                     ; INDICATE NO ERROR
        RTS     PC              ; RETURN TO CALLER

One optimization is to use the same register for the dividend and the quotient: since these are both shifted to the left, and the quotient starts as zero, in effect, the dividend slides out of the left side of the register as the quotient slides into the right side. In the above code, R0 can be initialized to hold the dividend, and the main loop would become

DD2:    ASL     R0              ; SHIFT DIVIDEND AND QUOTIENT LEFT
        ROL     R1              ; ROTATE REMAINDER LEFT, WITH CARRY
        CMP     R1,R3           ; IS DIVISOR <= REMAINDER?
        BMI     DD3             ; NO, CONTINUE
        SUB     R3,R1           ; REMAINDER -= DIVISOR
        INC     R0              ; SET LOW BIT IN QUOTIENT

Like multiplication, the division routine can be enhanced to support signed division, by checking the signs of the input. The definition of integer division specifies that the remainder is between zero and the absolute value of the divisor. This means if the dividend is negative, the quotient should be incremented, and the remainder should have the absolute value of the divisor added to it. If the sign of the dividend and divisor differ, the quotient should be negative:

dividend = divisor * quotient + remainder
dividenddivisorquotientremainder
193942737111
19394-273-7111
-19394273-72262
-19394-27372262

As with multiplication, we will create a new entry point for the signed division routine, set some flags depending on the input, and call the unsigned routine to iterate through the bits. The unsigned routine will be modified to check the flags and update the signs and values of the quotient and remainder if necessary. The optimization described above will free up the R2 register for the flags.

Here are the complete routines, with the modifications:

; DIVWS (DIVIDEND, DIVISOR) -> R0: QUOTIENT, R1: REMAINDER
;
; SIGNED 16-BIT DIVISION
;
DIVWS:  MOV     R2,-(SP)        ; SAVE R2
        MOV     R3,-(SP)        ; SAVE R3
        MOV     R4,-(SP)        ; SAVE R4

        CLR     R2              ; CLEAR FLAGS REGISTER
        MOV     10(SP),R0       ; R0 <- DIVIDEND
        MOV     12(SP),R3       ; R3 <- DIVISOR

        TST     R3              ; CHECK DIVISOR
        BPL     DIVWS0          ; IF POSITIVE, SKIP AHEAD
        INC     R2              ; FLIP FLAG BIT 0 (SIGNS DIFFER)
        NEG     R3              ; MAKE DIVISOR POSITIVE
DIVWS0: TST     R0              ; CHECK DIVIDEND
        BPL     DIVWU0          ; IF POSITIVE, SKIP TO UNSIGNED DIVIDE
        INC     R2              ; FLIP FLAG BIT 0 (SIGNS DIFFER)
        BIS     #4,R2           ; SET FLAG BIT 2 (DIVIDEND NEGATIVE)
        NEG     R0              ; MAKE DIVIDEND POSITIVE
        BR      DIVWU0          ; UNSIGNED DIVIDE LOOP

; DIVWU (DIVIDEND, DIVISOR) -> R0: QUOTIENT, R1: REMAINDER
;
; UNSIGNED 16-BIT DIVISION
;
DIVWU:  MOV     R2,-(SP)        ; SAVE R2
        MOV     R3,-(SP)        ; SAVE R3
        MOV     R4,-(SP)        ; SAVE R4

        CLR     R2              ; R2 <- FLAGS
        MOV     10(SP),R0       ; R0 <- DIVIDEND
        MOV     12(SP),R3       ; R3 <- DIVISOR
DIVWU0: TST     R3              ; CHECK THE DIVISOR
        BNE     DIVWU1          ; IF NOT ZERO, CONTINUE
        SEV                     ; ERROR: SET OVERFLOW
        BR      DIVWU9          ; CLEAN UP AND EXIT
DIVWU1: CLR     R1              ; R1 <- REMAINDER
        MOV     #20,R4          ; R4 <- COUNTER

DIVWU2: ASL     R0              ; SHIFT DIVIDEND AND QUOTIENT LEFT
        ROL     R1              ; ROTATE REMAINDER LEFT, WITH CARRY
        CMP     R1,R3           ; IS DIVISOR <= REMAINDER?
        BMI     DIVWU3          ; NO, CONTINUE
        SUB     R3,R1           ; REMAINDER -= DIVISOR
        INC     R0              ; SET LOW BIT IN QUOTIENT
DIVWU3: DEC     R4              ; DEC COUNTER
        BNE     DIVWU2          ; IF NOT ZERO, REPEAT
        CLV                     ; INDICATE NO ERROR

        BIT     #4,R2           ; CHECK THE DIVIDEND NEGATIVE FLAG
        BEQ     DIVWU8          ; IF NOT SET, SKIP AHEAD
        INC     R0              ; INCREMENT THE QUOTIENT
        SUB     R3,R1           ; SUBTRACT DIVISOR FROM REMAINDER
        NEG     R1              ; MAKE REMAINDER POSITIVE
DIVWU8: BIT     #1,R2           ; CHECK THE QUOTIENT NEGATIVE FLAG
        BEQ     DIVWU9          ; IF NOT SET, SKIP AHEAD
        NEG     R0              ; MAKE QUOTIENT NEGATIVE

DIVWU9: MOV     (SP)+,R4        ; RESTORE R4
        MOV     (SP)+,R3        ; RESTORE R3
        MOV     (SP)+,R2        ; RESTORE R2
        RTS     PC              ; RETURN TO CALLER

This same method can be extended for use with 32-bit (double word) integers.