PDP-11 Integer Divide Instruction "Div", To: General Discussion: On-Topic and Off-Topic Post
Don North
ak6dn at mindspring.com
Wed Feb 15 00:14:23 CST 2006
Don North wrote:
> Jerome H. Fine wrote:
>> >Johnny Billquist wrote:
>>
>>> >"Jerome H. Fine" wrote:
>>> > I have noticed what may be an interesting result when I use the
>>> > PDP-11 Integer Divide Instruction "Div". Since I have noticed
>>> > at least one individual who worked on the microcode for the
>>> > PDP-11, perhaps there is an explicit "Yes / No" answer to my
>>> > question:
>>> Since this actually have nothing to do with the microcode, and
>>> actually is nothing specific with the PDP-11 DIV instruction, just
>>> about anyone should be able to answer definitely.
>>
>> Jerome Fine replies:
>>
>> I suggest that you might not be aware of the exact implementation
>> of the PDP-11 integer "Div" instruction when an overflow occurs.
>>
>
> Please be aware there is no one "PDP-11 microcode". The internals and
> microflows of each machine are different, except for the 11/45-55 and
> 11/70 which are very closely related implementations (same basic core
> CPU). Some of the VLSI CPUs also tend to behave the same as they are
> based on the same core CPU (F11, J11, etc).
>
> How the DIV instruction behaves in boundary conditions (ie, when the
> true quotient can not be represented in 16b) can, but may not, be CPU
> specific. Some CPUs may generate the correct 16 LSB of the 32b
> quotient. Others may not. The PDP-11 programmers guide for various
> CPUs indicates that the only affect one can count on is that the 'V'
> bit is set.
>
> In practice, given the standard shift/subtract algorithms for binary
> division, it is probably the case that the 16b quotient is a true
> subset of the 32b quotient. However, there is no easy way to prove
> this without examining the microcode on each machine, or writing a
> test program and running it on each machine.
>
> SIMH implements PDP-11 DIV as:
>
> case 1: /* DIV */
> if (!CPUO (OPT_EIS)) {
> setTRAP (TRAP_ILL);
> break;
> }
> src2 = dstreg? R[dstspec]: ReadW (GeteaW (dstspec));
> src = (((uint32) R[srcspec]) << 16) | R[srcspec | 1];
> if (src2 == 0) {
> N = 0; /* J11,11/70
> compat */
> Z = V = C = 1; /* N = 0, Z = 1 */
> break;
> }
> if ((src == 020000000000) && (src2 == 0177777)) {
> V = 1; /* J11,11/70
> compat */
> N = Z = C = 0; /* N = Z = 0 */
> break;
> }
> if (GET_SIGN_W (src2)) src2 = src2 | ~077777;
> if (GET_SIGN_W (R[srcspec])) src = src | ~017777777777;
> --> dst = src / src2;
> N = (dst < 0); /* N set on 32b
> result */
> if ((dst > 077777) || (dst < -0100000)) {
> V = 1; /* J11,11/70
> compat */
> Z = C = 0; /* Z = C = 0 */
> ====>> break;
> }
> --> R[srcspec] = dst & 0177777;
> --> R[srcspec | 1] = (src - (src2 * dst)) & 0177777;
> Z = GET_Z (dst);
> V = C = 0;
> break;
>
> which would appear that the 16b quotient returned is the 16 LSB of the
> correct 32b quotient.
Actually I read the C code wrong. If overflow is detected, the 'break;'
jumps out of the code and no registers are modified.
So SIMH does NOT modify any registers if the V-bit has been set.
I checked the 11/34 MAINDEC EIS diagnostic. For the DIV tests, the
result registers are NOT checked if the Vbit is set.
The diagnostic does not verify that the registers are unchanged; it
assumes the registers are UNDEFINED if V is set.
I ran some simple DIV tests on a real 11/44:
>>>s 1000
(Program)
DIV Test of 'div r2,r0'
..R0.. ..R1.. ..R2.. ....NUM... ..DEN.. => ..R0.. ..R1.. ..R2.. NZVC
..QUO.. ..REM..
000003 000004 000003 196612. 3. => 000003 000004 000003
0010 3. 4.
000000 000000 000000 0. 0. => 000000 000000 000000
0011 0. 0. <-- Zbit clear
000001 000001 000000 65537. 0. => 000001 000001 000000
0011 1. 1. <-- Zbit clear
000000 001000 000010 512. 8. => 000100 000000 000010
0000 64. 0.
000000 001234 000021 668. 17. => 000047 000005 000021
0000 39. 5.
000010 001234 005432 524956. 2842. => 000270 003754 005432
0000 184. 2028.
012345 012345 054321 350557413. 22737. => 036071 051134 054321 0000
15417. 21084.
012345 012345 000005 350557413. 5. => 012345 012345 000005 0010
5349. 5349.
000000 040000 000002 16384. 2. => 020000 000000 000002 0000
8192. 0.
000000 100000 000002 32768. 2. => 040000 000000 000002 0000
16384. 0.
000001 000000 000002 65536. 2. => 100000 000000 000002 0010
-32768. 0. <-- R0 changed, Vbit set
000002 000000 000002 131072. 2. => 000002 000000 000002
0010 2. 0.
Goodbye
(Console)
Halted at 165146
and an 11/44 under the latest SIMH:
local[625] pdp11 divtest.ini
PDP-11 simulator V3.5-0
DIV Test of 'div r2,r0'
..R0.. ..R1.. ..R2.. ....NUM... ..DEN.. => ..R0.. ..R1.. ..R2.. NZVC
..QUO.. ..REM..
000003 000004 000003 196612. 3. => 000003 000004 000003
0010 3. 4.
000000 000000 000000 0. 0. => 000000 000000 000000
0111 0. 0. <-- Zbit set
000001 000001 000000 65537. 0. => 000001 000001 000000
0111 1. 1. <-- Zbit set
000000 001000 000010 512. 8. => 000100 000000 000010
0000 64. 0.
000000 001234 000021 668. 17. => 000047 000005 000021
0000 39. 5.
000010 001234 005432 524956. 2842. => 000270 003754 005432
0000 184. 2028.
012345 012345 054321 350557413. 22737. => 036071 051134 054321 0000
15417. 21084.
012345 012345 000005 350557413. 5. => 012345 012345 000005 0010
5349. 5349.
000000 040000 000002 16384. 2. => 020000 000000 000002 0000
8192. 0.
000000 100000 000002 32768. 2. => 040000 000000 000002 0000
16384. 0.
000001 000000 000002 65536. 2. => 000001 000000 000002
0010 1. 0. <-- R0 unchanged, Vbit set
000002 000000 000002 131072. 2. => 000002 000000 000002
0010 2. 0.
Goodbye
HALT instruction, PC: 000010 (000012)
Goodbye
local[626]
the interesting case is the (65536. / 2.) computation where the real
11/44 generates the correct unsigned quotient in R0, but also sets the Vbit.
In most cases however it appears that if DIV overflows the quo and rem
registers are unaltered and the Vbit is set.
SIMH and a real 11/44 (mostly) behave this way. The behavior below found
by Jerome may be an anomaly seen in E11.
>
>> Please see below!
>>
>>> > If I divide 196612 by 3 - i.e. "Div (R2),R0" where R0 = 3, R1 = 4,
>>> (R2) = 3
>>> > the result (in addition to the condition bits) is R0 = 1, R1 = 1
>>> which is
>>> > exactly correct if the quotient is regarded as a 32 bit result
>>> with R0 being
>>> > the low order 16 bits of that result and the high order 32 bits are
>>> somewhere
>>> > else - probably inaccessible as far as programming is concerned,
>>> but easily
>>> > obtained by:
>>> > Mov R1-(SP) ; Save low order 16 bits of dividend
>>> > Mov R0,R1 ; Divide high order 16 bits
>>> > Clr R0 ; of dividend
>>> > Div (R2),R0 ; by the divisor
>>> > Mov R0,R3 ; Save high order 16 bits of quotient
>>> > Mov R1,R0 ; Divide the remainder
>>> > Mov (SP)+,R1 ; of the dividend
>>> > Div (R2),R0 ; by the divisor
>>> > i.e. R3 now contains the high order 16 bits of the 32 bit quotient
>>> > with R0 holding the low order 16 bits of the 32 bit quotient
>>> What you have implemented here, as well as described, is the exact
>>> way you should have been taught how to do division on paper in
>>> elementary school.
>>> Yes, that algorithm is valid, and can be extended to arbitrary
>>> sizes, as long as you remember the full method.
>>
>> I agree that the above code is the "correct" method to ensure
>> a valid result. BUT, that is NOT what I am attempting to determine.
>>
>> Specifically, I have found that the following code also works:
>> Mov R0,R3
>> Div (R2),R0 ; First Divide Instruction
>> Tst R1
>> Bne Somewhere - since the quotient is not of interest when a
>> non-zero remainder
>> Mov R0,-(SP)
>> Mov R3,R1
>> Clr R0
>> Div (R2),R0 ; Second Divide Instruction
>> Mov (SP)+,R1
>> At this point, R0 / R1 now contains 32 bit quotient IF the first
>> "Div" instruction places the low order 16 bits of the 32 bit
>> quotient into R0. I have found this result in practice and since
>> there is a VERY HIGH probability that the remainder is NOT
>> zero, the above code is MUCH faster.
>>
>> Again, the specific question is IF the quotient of the "Div" instruction
>> is the low order 16 bits of a 32 bit quotient all of the time or just
>> when the high order 16 bits are all zero????????
>>
>>> > Can anyone confirm what I have found in practice?
>>> Certainly. It's basic math, the way it's taught in elementary school.
>>> That was atleast the first way I was taught how do do divides on big
>>> numbers on paper.
>>
>> I learned that also, but the observation is not relevant
>> to my question.
>>
>> I realize that the DEC manual description of the "Div" instruction
>> does not address the situation when the quotient exceeds 65535
>> (decimal) or 16 bits, but again, perhaps someone who knows
>> the microcode might have an answer.
>>
>>> > Even better would be a method of retrieving the high
>>> > order 16 bits of the quotient in a manner which takes
>>> > fewer instructions and without a second divide instruction!
>>>
>>> I doubt you'll find it.
>>
>> I AGREE!! It would have been "nice" though if
>> DEC knew where the value was and made that high
>> order 16 bits available via the next instruction
>> if the user needed it. That information would
>> also have exactly defined whether or not the low
>> order 16 bits of the quotient and the remainder
>> were correct all of the time. Any comments on these
>> TWO observations?
>>
>> I realize that the instruction set is long past being
>> subject to change in DEC hardware, but that does not
>> mean that an emulator could not manage to make a few
>> small but vital improvements. And certainly, at least
>> in SIMH, it is possible to examine the code to determine
>> the answer to my original question. Does anyone have
>> the code for the "Div" emulation in SIMH and what does
>> happen when the high order 16 bits of the quotient are
>> non-zero?
>>
>> Sincerely yours,
>>
>> Jerome Fine
>> --
>> If you attempted to send a reply and the original e-mail
>> address has been discontinued due a high volume of junk
>> e-mail, then the semi-permanent e-mail address can be
>> obtained by replacing the four characters preceding the
>> 'at' with the four digits of the current year.
>>
>>
>
>
More information about the cctech
mailing list