1 |
25 |
wfjm |
$Id: ECO-026-div.txt 579 2014-08-08 20:39:46Z mueller $
|
2 |
|
|
|
3 |
|
|
Scope:
|
4 |
|
|
Introduced in release w11a_V0.61
|
5 |
|
|
Affects: all w11a systems
|
6 |
|
|
|
7 |
|
|
Symptom summary:
|
8 |
|
|
The div instruction gave wrong results in some corner cases when either
|
9 |
|
|
divisor or quotient were the largest negative integer (100000 or -32768):
|
10 |
|
|
1. wrong q and r when dd=n*(-32768), dr=-32768 with n even
|
11 |
|
|
2. V=1 set when division solvable and proper result is q=-32768
|
12 |
|
|
|
13 |
|
|
Background:
|
14 |
|
|
The PDP-11/70 (KB11-C) and the w11a use very different division algorithms.
|
15 |
|
|
Both use a non-restoring divide.
|
16 |
|
|
- The KB11-C uses a straight forward 2 quadrant core algorithm for positive
|
17 |
|
|
dividends and positive or negative divisors. Negative dividends are first
|
18 |
|
|
converted to positive, the results later corrected. This leads to quite
|
19 |
|
|
complex implementation with 35 micro states.
|
20 |
|
|
- The w11a uses a 4 quadrant algorithm which directly allows positive and
|
21 |
|
|
negative dividends and divisors. The qbit logic is much more complex in
|
22 |
|
|
this case. Advantage is that the whole divide algorithm can be implemented
|
23 |
|
|
with only 6 states in the main sequencer.
|
24 |
|
|
|
25 |
|
|
In twos complement integer arithmetic, as used in the pdp11 and almost all
|
26 |
|
|
contemporary computers, the range of positive and negative numbers is
|
27 |
|
|
different, for 16 bit for example
|
28 |
|
|
oct 100000 to 077777
|
29 |
|
|
dec -32768 to +32767
|
30 |
|
|
so the smallest negative number has no positive counterpart. Trying to negate
|
31 |
|
|
the smallest negative number leads to the same number
|
32 |
|
|
mov #100000, r0
|
33 |
|
|
neg r0 --> r0 = 100000; V=1
|
34 |
|
|
|
35 |
|
|
These special properties of the largest negative number easily lead to corner
|
36 |
|
|
cases which require special treatment, both the KB11-C and the w11a divide
|
37 |
|
|
algorithms need special rules and checks for this.
|
38 |
|
|
|
39 |
|
|
Summary of issues:
|
40 |
|
|
1. when dividend was dd=n*(-32768) with an even n and the divisor was
|
41 |
|
|
dr=-32768 the old w11a algorithm returned wrong quotient and remainder
|
42 |
|
|
values and V=0 status.
|
43 |
|
|
2. for all divisions which result in a quotient of -32768 the old w11a
|
44 |
|
|
algorithm set the overflow (V=1) condition. Since in this case the
|
45 |
|
|
destination registers were not updated and still contained the
|
46 |
|
|
dividend, software not checking the V code saw wrong quotient and
|
47 |
|
|
remainder values.
|
48 |
|
|
|
49 |
|
|
Fixes:
|
50 |
|
|
- Issue 1: wrong q and r for dd=n*(-32768), dr=-32768 with n even.
|
51 |
|
|
- the corner case is detected in state s_opg_div by testing that divisor
|
52 |
|
|
is 0100000 and low order part of dividend is zero. When detected, the
|
53 |
|
|
qbit logic is modified and quotient and remainder corrections are done
|
54 |
|
|
unconditionally.
|
55 |
|
|
|
56 |
|
|
- Issue 2: V=1 set when division solvable and proper result is q=-32768.
|
57 |
|
|
The divide core algorithm calculates the correct q and r, only the
|
58 |
|
|
overflow testing was incorrect.
|
59 |
|
|
The old algorithm had two overflow abort conditions
|
60 |
|
|
- a check that bit 31 and 30 of the dividend are equal
|
61 |
|
|
- a check after the first division cycle
|
62 |
|
|
The new algorithm now has three overflow abort conditions
|
63 |
|
|
- the bit 31/30 check on the dividend was too restrictive. Valid divisions
|
64 |
|
|
with dd=(-32768)*(-32768)+n and dr=-32768 giving q=-32768 and r=n would
|
65 |
|
|
be rejected. The 31/30 check is now only applied when the divisor is not
|
66 |
|
|
equal 0100000
|
67 |
|
|
- the division abort condition in the first division cycle was completely
|
68 |
|
|
revised, this avoids that solvable divisions are aborted at this stage
|
69 |
|
|
- the first two conditions don't catch all overflow situations. The
|
70 |
|
|
remaining ones all have after the quotient correction stage q>0 when
|
71 |
|
|
a negative quotient is expected. A third overflow check was added to
|
72 |
|
|
s_opg_div_sr to handle these cases.
|
73 |
|
|
|
74 |
|
|
Side effects:
|
75 |
|
|
- the old implementation guaranteed that the destination registers were
|
76 |
|
|
unchanged in case of overflow. The new does not, the overflow check in
|
77 |
|
|
s_opg_div_sr is done after the quotient is stored, and storing remainder
|
78 |
|
|
is not suppressed in case of overflow. So both q and r regs are changed.
|
79 |
|
|
- with additional states it could be guaranteed that destination registers
|
80 |
|
|
are never updated in case of overflow. See proviso below.
|
81 |
|
|
- the pdp-11/70 KB11-C in most cases keeps destination registers unchanged
|
82 |
|
|
in case of overflow, but also has a late check after one register has
|
83 |
|
|
been modified.
|
84 |
|
|
- the J11 never updates registers in case of overflow. A case like
|
85 |
|
|
0,177777 / 177777 were w11a now updates regs is known from J11
|
86 |
|
|
diagnostics to not update in J11.
|
87 |
|
|
- simh always preserves the destination registers in case of overflow.
|
88 |
|
|
|
89 |
|
|
!! the pdp11 processor handbook considers the destination registers as !!
|
90 |
|
|
!! undefined in case of division overflow, so the w11a behavior is OK. !!
|
91 |
|
|
|
92 |
|
|
Provisos:
|
93 |
|
|
- the behavior after V=1 aborts of a div instruction is now different in
|
94 |
|
|
- w11a --> regs updated under some rare conditions
|
95 |
|
|
- KB11-C --> regs updated under some rare conditions
|
96 |
|
|
but in cases different from w11a
|
97 |
|
|
- 11/44 --> regs updated under some conditions (see v7_longdivide_bug.txt)
|
98 |
|
|
- J11 --> regs never updated
|
99 |
|
|
- simh --> regs never updated
|
100 |
|
|
--> that can lead to spurious failures in original DEC diagnostics when
|
101 |
|
|
they test the complete response
|
102 |
|
|
--> even though the current w11a behavious is full within specs it is unclear
|
103 |
|
|
whether all software tolerates this, especially non-DEC OS. Unix V7 is
|
104 |
|
|
known to have an issue with ldiv and CPUs not preserving regs, see
|
105 |
|
|
http://minnie.tuhs.org/PUPS/v7_longdivide_bug.txt
|
106 |
|
|
--> Only further studes can show whether it is worth the effort and the
|
107 |
|
|
slow down of 1-2 cycles to guarantee preserved registers.
|
108 |
|
|
|