Reverse engineering PDP-11 BASIC: Part 17

This post will take a look at some more floating point manipulation TRAPs; TRAP 26 (floating point division) and TRAP 34 (floating point comparison). TRAP 54, which is used by TRAP 34, is also described, along with TRAP 32.

For context and a list of other posts on this topic, see the PDP-11 BASIC reverse engineering project page.

TRAP 26

TRAP 26 is used for dividing the floating point number pointed to by R0 by the floating point number pointed to by R1.

The general approach to floating point division is to divide the significands and subtract the exponents. This is actually quite similar to the multiplication code described in the last post.

Here's the code:

012550 010546 MOV R5, -(SP)
012552 010046 MOV R0, -(SP)
012554 005046 CLR -(SP)
012556 012105 MOV (R1)+, R5
012560 012104 MOV (R1)+, R4
012562 005704 TST R4
012564 001477 BEQ 12764
012566 002004 BGE 12600
012570 005404 NEG R4
012572 005405 NEG R5
012574 005604 SBC R4
012576 005216 INC (SP)
012600 012003 MOV (R0)+, R3
012602 012002 MOV (R0)+, R2
012604 001563 BEQ 13154
012606 003004 BGT 12620
012610 005402 NEG R2
012612 005403 NEG R3
012614 005602 SBC R2
012616 005316 DEC (SP)
012620 011101 MOV (R1), R1
012622 005401 NEG R1
012624 061001 ADD (R0), R1
012626 006001 ROR R1
012630 006101 ROL R1
012632 102054 BVC 12764
012634 062701 ADD #100000, R1
012640 010146 MOV R1, -(SP)
012642 010301 MOV R3, R1
012644 010200 MOV R2, R0
012646 005002 CLR R2
012650 005003 CLR R3
012652 006000 ROR R0
012654 006001 ROR R1
012656 006002 ROR R2
012660 104464 TRAP 64
012662 005404 NEG R4
012664 005405 NEG R5
012666 005604 SBC R4
012670 006301 ASL R1
012672 006100 ROL R0
012674 060501 ADD R5, R1
012676 005500 ADC R0
012700 060400 ADD R4, R0
012702 002403 BLT 12712
012704 062703 ADD #1, R3
012710 005502 ADC R2
012712 000241 CLC
012714 006002 ROR R2
012716 006003 ROR R3
012720 005216 INC (SP)
012722 005766 TST 2(SP)
012726 001403 BEQ 12736
012730 005402 NEG R2
012732 005403 NEG R3
012734 005602 SBC R2
012736 016600 MOV 4(SP), R0
012742 010320 MOV R3, (R0)+
012744 010220 MOV R2, (R0)+
012746 012610 MOV (SP)+, (R0)
012750 022626 CMP (SP)+, (SP)+
012752 012605 MOV (SP)+, R5
012754 024040 CMP -(R0), -(R0)
012756 010001 MOV R0, R1
012760 000167 JMP 13202
012764 022626 CMP (SP)+, (SP)+
012766 104773 TRAP 373
012770 012605 MOV (SP)+, R5
012772 000262 SEV
012774 000207 RTS PC

There's quite a lot of code here, but it's actually very similar to the multiplication code, described in the last post.

012550 010546 MOV R5, -(SP)
012552 010046 MOV R0, -(SP)
012554 005046 CLR -(SP)

Firstly, R5 and R0 are pushed onto the stack. A zero word is then pushed onto the stack. This is used to indicate the sign of the result.

012556 012105 MOV (R1)+, R5
012560 012104 MOV (R1)+, R4

The significant of the divisor is moved from R1 into R5 (low word) and R4 (high word).

012562 005704 TST R4
012564 001477 BEQ 12764
012566 002004 BGE 12600
012570 005404 NEG R4
012572 005405 NEG R5
012574 005604 SBC R4
012576 005216 INC (SP)

The value at R4 is tested, as a test of whether the divisor is zero. Obviously, we cannot divide by zero, so if this value is zero, control branches to 12764 to set the overflow flag and return.

Otherwise, if the value in R4 is negative, it is negated to give its positive value. The value at the top of the stack is incremented to indicate that one of the operands is negative. If the value of R4 is positive, the negation code is skipped and control branches directly to 12600.

012600 012003 MOV (R0)+, R3
012602 012002 MOV (R0)+, R2

Next, the significand of the dividend is moved into R3 (low word) and R2 (high word).

012604 001563 BEQ 13154
012606 003004 BGT 12620
012610 005402 NEG R2
012612 005403 NEG R3
012614 005602 SBC R2
012616 005316 DEC (SP)

If R2 equals zero then the dividend is zero. In this case, control jumps to address 13154, which is the location of the bit of the multiplication code that is used to return a zero value. In other words, if the dividend is zero then the result is zero, so a zero value is returned.

If the dividend is not zero, then if it is negative, the value is negated to give its positive value and the value at the top of the stack is decremented to indicate that one of the operands was negative and therefore the result should be negative. Note that if both operands were negative, the increment of the value at the top of the stack and decrement of the value at the top of the stack will cancel, because the result should be positive.

012620 011101 MOV (R1), R1
012622 005401 NEG R1
012624 061001 ADD (R0), R1

Next the exponents are subtracted from each other. The exponent of the first number is moved from the memory address contained in R1 into R1. This value is then negated and added to the exponent of the other number, stored at the memory address contained in R0. The resulting value will be stored in R1.

012626 006001 ROR R1
012630 006101 ROL R1
012632 102054 BVC 12764
012634 062701 ADD #100000, R1
012640 010146 MOV R1, -(SP)

The value in R1 is then rotated to the right and then immediately rotated to the left again. The overflow flag is set by the ROL (and indeed the ROR) instruction to be the XOR of the N flag (set if the result is negative, i.e. highest bit is 1) and the C flag (set if the rotation results in a 1 being rotated into the carry flag, i.e. we just rotated a 1 out of the highest bit position).

In other words, this code is testing whether the resulting value in R1 has the highest bit set (or, alternatively, if the addition caused an overflow into the carry flag). If the overflow flag is not set then control jumps to 12764, which sets the overflow flag and returns. In this case we are dealing with two exponents, which are of the form "100017" (in binary that's 1 000 000 000 001 111).

If we imagine, for example, that we are subtracting the value "100015" (binary 1 000 000 000 001 101) from this what we are going to do is negate this value (which in two's complement binary will be 0 111 111 111 110 011). When we add this value to, for example, 100017, we are going to get 200002 ( 1 (carry bit) + (result) 0 000 000 000 000 010), which causes the carry bit to be set, and therefore the overflow flag to be set.

Next, 100000 is added to the result, so now we will have the value 100002 in our example above. This value is then pushed onto the stack.

That completes the subtraction of the exponents. We now move on to dividing the significands:

012642 010301 MOV R3, R1
012644 010200 MOV R2, R0
012646 005002 CLR R2
012650 005003 CLR R3
012652 006000 ROR R0
012654 006001 ROR R1
012656 006002 ROR R2
012660 104464 TRAP 64

The significand of the dividend is moved into R0/R1/R2/R3 (with R2 and R3 being cleared). The entire value is rotated to the right by one bit and then TRAP 64 is used to divide the value in R0/R1/R2/R3 by the significand of the dividend, contained in R4/R5.

The result of division is stored in R2/R3 with any remainder stored in R0/R1. I'm not sure why the values are rotated in advance because it seems that the result needs to be corrected with the code below by carrying out one additional iteration of the division loop implemented in TRAP 64.

012662 005404 NEG R4
012664 005405 NEG R5
012666 005604 SBC R4

Firstly, the significand of the divisor is negated.

012670 006301 ASL R1
012672 006100 ROL R0
012674 060501 ADD R5, R1
012676 005500 ADC R0
012700 060400 ADD R4, R0

The value in R1 is shifted left (which will carry the highest bit into the carry flag) and the value of R0 is rotated left (which will set the lowest bit of R0 to be the value of the carry flag set when shifting R1 to the left). The value in R4/R5 (the negated value of the divisor) is then added to R0/R1.

012702 002403 BLT 12712
012704 062703 ADD #1, R3
012710 005502 ADC R2

If the resulting addition causes the value in R0 to be negative, then control jumps to 12712. Otherwise, 1 is added to R3 and if this addition causes the carry flag to be set, the carry bit is added to R2.

012712 000241 CLC
012714 006002 ROR R2
012716 006003 ROR R3
012720 005216 INC (SP)

In any case (whether the result of addition is positive or negative), the carry flag is cleared and R2/R3 are rotated right by one bit. The value at the top of the stack (which is the exponent of the result) is incremented.

This concludes the division of the significands and now we move on to final preparations before returning.

012722 005766 TST 2(SP)
012726 001403 BEQ 12736
012730 005402 NEG R2
012732 005403 NEG R3
012734 005602 SBC R2

The value at SP+2 is tested. This is the flag that is used to indicate whether one or other (but not both) of the operands were negative. If the value is zero that means the result is positive, with a non-zero value representing a negative result.

If the value is non-zero R2 and R3 are negated, with appropriate management of the carry bit to treat the two registers as a single 32 bit value.

012736 016600 MOV 4(SP), R0
012742 010320 MOV R3, (R0)+
012744 010220 MOV R2, (R0)+
012746 012610 MOV (SP)+, (R0)

The value from SP+4, which was the original value of R0 pushed onto the stack at the beginning of the TRAP, is moved back into R0. The values from R3 and R2 are then moved into successive memory locations at R0. The exponent value is popped off the stack into the memory location at R0.

In other words, the floating point result of the division is moved into the memory address of the floating point number that was passed into this TRAP in R0.

012750 022626 CMP (SP)+, (SP)+
012752 012605 MOV (SP)+, R5

Two values are popped off the stack and discarded and then the value of R5 is restored from the stack.

012754 024040 CMP -(R0), -(R0)
012756 010001 MOV R0, R1
012760 000167 JMP 13202

The value of R0 is decremented twice, so that R0 now points at the beginning of the floating point result. The value of R0 is also copied into R1.

Control now jumps to address 13202, which is part of TRAP 36. This code is used to normalise the result, which in practical terms means removing any leading zeros (in the case of a positive value) or ones (in the case of a negative number) and adjusting the exponent accordingly.

Once the result value has been normalised, control will return to the calling code.

012764 022626 CMP (SP)+, (SP)+
012766 104773 TRAP 373
012770 012605 MOV (SP)+, R5
012772 000262 SEV
012774 000207 RTS PC

In case of errors, such as trying to divide by zero, this code is executed. Two values are popped off the stack and then the non-fatal TRAP 373 is invoked. When this returns the value of R5 is restored from the stack, the overflow flag is set and then control returns to the calling code.

TRAP 54

This is a simple TRAP that is used to copy a floating point value from R0 onto the stack. Here it is:

013354 012602 MOV (SP)+, R2
013356 062700 ADD #6, R0
013362 014046 MOV -(R0), -(SP)
013364 014046 MOV -(R0), -(SP)
013366 014046 MOV -(R0), -(SP)
013370 010207 MOV R2, PC

The return address is popped from the stack and stored in R2. Then, six is added to the memory location at R0, which means that R0 will point at the word after the floating point number. Then, three MOVs are used to move the floating point number onto the stack. In each case, the value in R0 is pre-decremented, along with the stack pointer, and then the value pointed to by R0 is moved to the stack.

The words of the floating point number are moved onto the stack in reverse order but because the stack grows downwards the upshot is that the floating point number is correctly arranged in memory.

Finally, the return address, stored in R2, is moved to the program counter which means execution will resume immediately at the return address.

TRAP 32

TRAP 32 is another very simple TRAP, used for copying a float from the memory location pointed to by R1 to the memory location pointed to by R0.

Here's the code:

013310 010102 MOV R1, R2
013312 010004 MOV R0, R4
013314 012224 MOV (R2)+, (R4)+
013316 012224 MOV (R2)+, (R4)+
013320 012224 MOV (R2)+, (R4)+
013322 000207 RTS PC

Firstly, presumably to preserve their values, R1 is copied to R2 and R0 is copied to R4. Three words are then copied from the location pointed to by R2 to the location pointed to by R4. Control then returns to the calling code.

TRAP 34

Next we have TRAP 34, which is used for comparing two floating point numbers. The two numbers are pointed to by R0 and R1 and the result is that the flags are set the same as for the CMP instruction.

Here's the code:

013324 010146 MOV R1, -(SP)
013326 104454 TRAP 54
013330 010600 MOV SP, R0
013332 016601 MOV 6(SP), R1
013336 104422 TRAP 22
013340 016601 MOV 2(SP), R1
013344 062706 ADD #10, SP
013350 005401 NEG R1
013352 000207 RTS PC

Let's see how it works.

013324 010146 MOV R1, -(SP)

Firstly R1 is pushed onto the stack.

013326 104454 TRAP 54
013330 010600 MOV SP, R0

The floating point number pointed to by R0 is pushed onto the stack. The stack pointer, which now points at the copied floating point number on the stack, is then moved to R0.

013332 016601 MOV 6(SP), R1

The value at SP+6 (which is the original value of R1 pushed onto the stack) is then moved into R1.

013336 104422 TRAP 22

TRAP 22 (described in Part 15) is used to subtract the value pointed to by R1 from the value pointed to by R0, with the result stored in R0.

013340 016601 MOV 2(SP), R1

The second word (i.e. the high word of the significand) of the resulting value is moved into R1.

013344 062706 ADD #10, SP

Ten is added on to the stack pointer, which removes four words from the stack and discards them. These are the three words of the floating point result of subtracting R1 from R0, and the memory location of the floating point number originally stored in R1.

013350 005401 NEG R1

The value in R1 is negated, which will set the PSW flags according to the difference between the two numbers. For example, if after negation the value in R1 is negative, that means that the original value was positive, which means that when R1 was subtracted from R0 the remainder was greater than zero, which means that the value in R0 was greater than the value in R1.

013352 000207 RTS PC

Control then returns to the calling code.

Conclusion

This concludes the analysis of the core floating point computation code, at least all of the floating point computation code that I have been able to identify so far!

All of the floating point code analysis over the past few posts has been laying the groundwork to be able to perform an analysis of the ASCII-to-floating point number code, which will be the subject of the next post.

Thanks for reading!