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)
``````

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
``````

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
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