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
dividend | divisor | quotient | remainder |
---|---|---|---|
19394 | 273 | 71 | 11 |
19394 | -273 | -71 | 11 |
-19394 | 273 | -72 | 262 |
-19394 | -273 | 72 | 262 |
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.