14 Feb
2006
14 Feb
'06
11:17 a.m.
Jerome H. Fine wrote:
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.
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. Please see below!
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????????
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.
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.
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. 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. 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.