PDP-11 Integer Divide Instruction "Div" - test-drb@ccmp.vtda.org

14 Feb 2006

"Jerome H. Fine" <jhfinedp3k at compsys.to> 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. 
But the algorithm can't produce an overflow. However, it requires that 
the math be unsigned. Herein lies a problem; the DIV instruction is 
signed, so the result cannot be allowed to be > 32767. Afraid that 
problem really kicks butt. Oh well, you cannot use the DIV instruction then.
Interestingly enough, it seems as if atleast E11 don't work the same way 
as a real PDP-11 in this case. I really need to check this more. It 
might be neccesary to report this to John Wilson.

In E11, the V flag is still set, but it also actually performs the 
division. The J11 does not.

What have you tried your code on?
I believe it shouldn't have produced correct results for you on a real 
PDP-11, but I believe it would on E11. Don't know about SIMH, or other 
PDP-11 emulators (and I've only tested a real J11 so far, I'll try to 
check on a real 11/70 tomorrow).

...
 Please see below! 
Happy to.

...
 >>> > 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: 
[...]

Well, now that I'v actually tested this, I can tell you that this works 
in E11, but does not work on a J11. If you load R0=3, R1=4, R2=3 and do 
a DIV R2,R0, the only thing that happens is that the V-bit of the PSW is 
set, and the registers remain unchanged.

...
 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. 
Well, what we now know is that the piece of code you have will not 
actually produce correct results on a real PDP-11, since we have a 
overflow into the sign bit, which aborts the DIV instruction.

...
 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. 
And this will totally fail on atleast a J11, and probably all other 
"real" PDP-11s. At overflow, nothing gets computed. The register remain 
unchanged.

...
 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???????? 
Basically never. It the quotient can't be expressed in *15* bits, the 
registers will remain unchanged.

...
   > > 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. 
True. The algorithm is correct, but the PDP-11 DIV instruction have more 
limitations. You could use it if you played with smaller quantities. 
Easiest would be to work at 8 bits at a time instead of 16. However, 
that also requires the divisor to only be 8 bits, which might be a bit 
limiting. If you do 15 bits at a time, you're at the limit of the DIV 
instuction, but still working. You have to do the bit packing and 
unpacking though.
And all that will probably take much more time than just implementing a 
DIV yourself.

...
 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. 
Uh. My processor handbooks actually do address the situation, but it's 
actually when it exceeds 32767.
And I have three different processor handbooks here.
(1977-1978 pdp11/70 processor handbook, 1979-1980 pdp11 processor 
handbook for pdp11/04/34a/44/60/70, and 1983-1984 PDP-11 Architecture 
Handbook).

Look in any processor handbook you have at the DIV instruction, and the 
V condition.

...
   > > 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? 
Unfortunately, the DIV instruction is explicitly a 16-bit signed divide. 
They actually don't do a 32-bit divide, so there aren't any upper 16 
bits to tell about somehow.

...
 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? 
Afraid I haven't looked at simh in a while, and I also apologize for my 
previous answer. I was just observing the algorithm, and not how the 
PDP-11 DIV instruction actually worked.
I should have looked in the processor handbook, which I did this time. 
But then again, since you observed that your code worked, then I had no 
reason to doubt it.
But in fact, it will not work on a real PDP-11.

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at update.uu.se           ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol