This post is about multiplication. There are three different multiplication TRAPs found in the PDP-11 BASIC code, with a different one being used depending on the type of numbers that need to be multiplied together. TRAP 62 is used for multiplying 32-bit values together, TRAP 16 is used for multiplying 16-bit values together and TRAP 30 is used for multiplying floating point numbers together.
For context and a list of other posts on this topic, see the PDP-11 BASIC reverse engineering project page.
TRAP 62 (32-bit integer multiplication)
TRAP 62 is used to multiple two 32-bit integer values together. The 32-bit value in R2/R3 is multiplied by the 32-bit value in R4/R5 and the result as a 64-bit value in R0/R1/R2/R3.
Here's the code:
011776 005000 CLR R0
012000 005001 CLR R1
012002 012746 MOV #41, -(SP)
012006 006000 ROR R0
012010 006001 ROR R1
012012 006002 ROR R2
012014 006003 ROR R3
012016 103003 BCC 12026
012020 060501 ADD R5, R1
012022 005500 ADC R0
012024 060400 ADD R4, R0
012026 005316 DEC (SP)
012030 001366 BNE 12006
012032 005726 TST (SP)+
012034 000207 RTS PCLet's see how this works.
011776 005000 CLR R0
012000 005001 CLR R1
012002 012746 MOV #41, -(SP)First R0 and R1 are cleared and the value 41 (33 in decimal) is pushed onto the stack.
012006 006000 ROR R0
012010 006001 ROR R1
012012 006002 ROR R2
012014 006003 ROR R3The values in R0, R1, R2 and R3 are all rotated to the right. In each case, the lowest bit of the rotated value is shifted into the carry bit, and the value of the carry bit is shifted into the upper position. So, for example, when R0 is rotated right, the lowest bit will move into the carry flag. Then, when R1 is rotated right, the bit from the carry flag (just rotated out of R0) will be rotated in as the highest bit in R1. The lowest bit from R1 is rotated out into the carry flag, and so on for the other two registers.
Remember that the value to be multiplied is stored in registers R3 and R2, and registers R1 and R0 are both zero at the beginning of the execution.
012016 103003 BCC 12026
012020 060501 ADD R5, R1
012022 005500 ADC R0
012024 060400 ADD R4, R0
012026 005316 DEC (SP)
012030 001366 BNE 12006If the bit rotated out of R3 was a zero, then the carry flag will be clear, so control jumps to 12026, where the counter (on the stack) is decremented and control jumps back up to perform the next series of rotations.
Otherwise, if the bit rotated out of R3 was a one, then R5 is added to R1 and, if this causes a carry, the carry bit is added to R0. R4 is also added to R0 to add in the higher word of the value being multiplied in, if present. Then the counter on the stack is decremented and control jumps to 12006 to perform the next series of rotations.
What this, in effect does, is add R4/R5 to R0/R1 for every set bit in R2/R3, with the running value being shifted right (i.e. progressively further into R2/R3 as the rotation progresses).
012032 005726 TST (SP)+
012034 000207 RTS PCOnce the counter on the stack has decremented to zero, the value at the top of the stack is popped off and discarded. Control then returns to the calling code.
The value left in R0/R1/R2/R3 is the result of multiplying the value in R2/R3 by the value in R4/R5.
TRAP 16 (16-bit integer multiplication)
TRAP 16 is a slight variation on TRAP 62, just described. In this case, the 16-bit values in R0 and R1 are multiplied together and the result is returned in the 32-bit value R0/R1.
Here's the code:
011752 010546 MOV R5, -(SP)
011754 010003 MOV R0, R3
011756 010105 MOV R1, R5
011760 005002 CLR R2
011762 005004 CLR R4
011764 104462 TRAP 62
011766 010300 MOV R3, R0
011770 010201 MOV R2, R1
011772 012605 MOV (SP)+, R5
011774 000207 RTS PC It's quite simple but let's see how it works.
011752 010546 MOV R5, -(SP)Firstly R5 is pushed onto the stack.
011754 010003 MOV R0, R3
011756 010105 MOV R1, R5
011760 005002 CLR R2
011762 005004 CLR R4Then, the first number to be multiplied is moved into R3 and the second number to be multiplied is moved into R5. R2 and R4 are cleared.
011764 104462 TRAP 62TRAP 62 is then used to multiple two integer values together. The 32-bit value in R2/R3 is multiplied by the value in R4/R5 and the result is returned in R0/R1/R2/R3.
011766 010300 MOV R3, R0
011770 010201 MOV R2, R1Since only the lowest 16 bits of each argument are in use, the result will be stored in the lowest 32 bits (i.e. R2 and R3). Therefore, the lowest 32 bits of the resulting value are moved from R3/R2 into R0/R1.
011772 012605 MOV (SP)+, R5
011774 000207 RTS PC R5 is restored from the stack and then control returns to the calling code.
TRAP 30 (floating point multiplication)
The last TRAP we'll be looking at in this post is TRAP 30, which is used for multiplication of floating point numbers. How is floating point multiplication done? It's basically a two step process:
add the exponents
multiply the significands
TRAP 30 multiplies the floating point number pointed to by the memory address in R0 by the floating point number pointed to by the memory address in R1. The result is stored in the memory address in R0.
Here's the code:
012776 010546 MOV R5, -(SP)
013000 010046 MOV R0, -(SP)
013002 012105 MOV (R1)+, R5
013004 012104 MOV (R1)+, R4
013006 011101 MOV (R1), R1
013010 005046 CLR -(SP)
013012 005704 TST R4
013014 001457 BEQ 13154
013016 100004 BPL 13030
013020 005404 NEG R4
013022 005405 NEG R5
013024 005604 SBC R4
013026 005316 DEC (SP)
013030 012003 MOV (R0)+, R3
013032 012002 MOV (R0)+, R2
013034 001447 BEQ 13154
013036 100004 BPL 13050
013040 005402 NEG R2
013042 005403 NEG R3
013044 005602 SBC R2
013046 005216 INC (SP)
013050 061001 ADD (R0), R1
013052 006001 ROR R1
013054 006101 ROL R1
013056 102342 BVC 12764
013060 062701 ADD #100000, R1
013064 010146 MOV R1, -(SP)
013066 104462 TRAP 62
013070 005216 INC (SP)
013072 006102 ROL R2
013074 006101 ROL R1
013076 006100 ROL R0
013100 102402 BVS 13106
013102 005316 DEC (SP)
013104 000772 BR 13072
013106 006000 ROR R0
013110 006001 ROR R1
013112 005501 ADC R1
013114 005500 ADC R0
013116 102002 BVC 13124
013120 005216 INC (SP)
013122 000771 BR 13106
013124 012602 MOV (SP)+, R2
013126 005726 TST (SP)+
013130 001403 BEQ 13140
013132 005400 NEG R0
013134 005401 NEG R1
013136 005600 SBC R0
013140 012603 MOV (SP)+, R3
013142 010123 MOV R1, (R3)+
013144 010023 MOV R0, (R3)+
013146 010213 MOV R2, (R3)
013150 012605 MOV (SP)+, R5
013152 000207 RTS PC
013154 005000 CLR R0
013156 005001 CLR R1
013160 005002 CLR R2
013162 005726 TST (SP)+
013164 000765 BR 13140There's a lot there but hopefully it will all make sense when we walk through it. Let's get started.
012776 010546 MOV R5, -(SP)
013000 010046 MOV R0, -(SP)Firstly, R5 and R0 are pushed onto the stack.
013002 012105 MOV (R1)+, R5
013004 012104 MOV (R1)+, R4
013006 011101 MOV (R1), R1Now, the floating point number pointed to by R1 is moved into registers. The significand is moved into R4/R5 and the exponent is moved into R1.
013010 005046 CLR -(SP)A zero word is now pushed onto the stack. This will be used to record the sign of the numbers being multiplied, so that the appropriate sign can be applied to the result in due course.
013012 005704 TST R4
013014 001457 BEQ 13154
013016 100004 BPL 13030The value in R4, which is the high word of the significand of the first floating point number is tested. If it is equal to zero, it is presumed that the number is zero, and when you multiply anything by zero you get zero, therefore control jumps to 13154 to return a zero value. If the value in R4 is positive, control jumps to 13030.
013020 005404 NEG R4
013022 005405 NEG R5
013024 005604 SBC R4
013026 005316 DEC (SP)Otherwise the value at R4 is negated, the value at R5 is negated and any carry bit is subtracted from R4. In other words, if the value was negative it is negated into a positive value.
The value at the top of the stack is decremented, to indicate that one of the numbers being multiplied was negative.
013030 012003 MOV (R0)+, R3
013032 012002 MOV (R0)+, R2
013034 001447 BEQ 13154
013036 100004 BPL 13050The significand of the other floating point number is moved into R3 and R2. If the value in R2 was zero then it is again presumed we are dealing with a negative number, in which case we jump to 13154 to return a zero result. If the result is positive jump to 13050.
013040 005402 NEG R2
013042 005403 NEG R3
013044 005602 SBC R2
013046 005216 INC (SP)If the value in R2 was negative, then we negate R2 and R3, subtracting any carry bit from R2, to obtain the positive value.
Then, the value at the top of the stack pointer is incremented to indicate that one of the numbers being multiplied is negative. Note that if both numbers are negative, we expect the result to be positive, and accordingly the decrement of (SP) when the first number is negative is cancelled out by the increment of (SP) here, leaving (SP) with a value of zero. So, in summary if (SP) has a zero value it means that the result is positive, otherwise if (SP) is nonzero it means the result should be negative.
013050 061001 ADD (R0), R1
013052 006001 ROR R1
013054 006101 ROL R1
013056 102342 BVC 12764
013060 062701 ADD #100000, R1
013064 010146 MOV R1, -(SP)Now the exponents are added together. One exponent is stored in (R0) and the other one is stored in R1. The result will be stored in R1.
Remember that exponents are of the form "100017". If you add two numbers of this form together you'll get a value like "200020" which cannot fit in 16 bits and will therefore cause an overflow and the result stored in R1 will be, for example, 20. The value in R1 is rotated right, which will roatate the carry bit into the top bit of R1 and the lowest bit will be rotated into the carry flag.
The value in R1 is then rotated left again. This should cause the carry flag (but not the negative flag) to be set, which will cause the overflow flag to be set. If the overflow flag is clear, control jumps to 12764 which will cause the overflow flag to be set and then return.
The value in R1 is the sum of the two exponents, but missing the 1 at the beginning of the number is missing, so 100000 is added to the value in R1. This will mean that the sum of the exponents is now contained in R1. The value in R1 is pushed onto the stack.
013066 104462 TRAP 62TRAP 62 is now used to multiply the value in R2/R3 by the value in R4/R5. The result is stored in the 64-bit value R0/R1/R2/R3.
In due course we will discard most of the lowest significance bits, contained in R2 and R3.
013070 005216 INC (SP)
013072 006102 ROL R2
013074 006101 ROL R1
013076 006100 ROL R0
013100 102402 BVS 13106
013102 005316 DEC (SP)
013104 000772 BR 13072This next series of instructions removes any leading zeros from the result. The values in R2, R1 and R0 are rotated left until the value in R0 causes an overflow. This will happen the first time a 1 bit moves into the sign bit in R0. The exponent is decremented for each leading zero bit in the number. When the overflow flag is set, control jumps to 13106.
At this point we discard the remainder of R2 and R3.
013106 006000 ROR R0
013110 006001 ROR R1
013112 005501 ADC R1
013114 005500 ADC R0
013116 102002 BVC 13124
013120 005216 INC (SP)
013122 000771 BR 13106When the code to remove the leading zeros was run, it left the sign bit of R0 set, in other words it left R0 with a negative value. Therefore R0 and R1 are rotated right once to restore the value to the correct sign. If rotating R1 to the right caused the carry bit to be set, the carry value is added to R1. Adding this carried bit might cause a carry bit from R1 to R0, so the carry flag is added to R0.
If adding the carry flag to R0 causes an overflow, then the exponent is incremented and the process is repeated. Otherwise if the overflow flag is clear, we have finished calculating the significand, and control jumps to 13124 to start making arrangements to return from the TRAP.
013124 012602 MOV (SP)+, R2The exponent of the resulting number is popped from the stack into R2.
013126 005726 TST (SP)+
013130 001403 BEQ 13140
013132 005400 NEG R0
013134 005401 NEG R1
013136 005600 SBC R0The sign flag is popped off the stack and tested. If the value equals zero, that means the result is positive, so control jumps to 13140. Otherwise, if the value is non-zero it means that one of the numbers being multiplied was negative (but not both) so the result is negative. In that case, the resulting value is negated by negating the value in R0 and then negating the value in R1, with the carry flag being subtracted from R0.
013140 012603 MOV (SP)+, R3
013142 010123 MOV R1, (R3)+
013144 010023 MOV R0, (R3)+
013146 010213 MOV R2, (R3)
013150 012605 MOV (SP)+, R5
013152 000207 RTS PCThe value from the top of the stack, is popped into R3. This is the memory location that was originally passed into the TRAP in R0, that was pushed onto the stack at the very beginning of the code.
The value from R1 is moved to the memory location in R3, and then R3 is incremented. Then the value from R0 is moved to the memory location in R3 and R3 is incremented again. Finally R2 is moved to the memory location at R3. We have now moved the floating point result of multiplication into the memory location of the floating point number originally passed in R0.
R5 is popped from the stack and control returns to the calling code.
013154 005000 CLR R0
013156 005001 CLR R1
013160 005002 CLR R2
013162 005726 TST (SP)+
013164 000765 BR 13140Finally, this extra bit of code is used when we want to return a zero value (i.e. when one of the values passed in was zero). In this case R0, R1 and R2 are cleared. A value is popped from the top of the stack and discarded. Control then jumps to the code above for moving the result into the memory location of the floating point number originally passed in R0 and then returning control to the calling code.
Conclusion
We've talked through three different multiplication TRAPs, used for multiplying 16 bit numbers, 32 bit numbers and floating point numbers.