| blob | 7a26c295cb1d8da21044c258243ca332835b6d4d |
1 /*
2 * Unsigned multiply. Returns %o0 * %o1 in %o1%o0 (i.e., %o1 holds the
3 * upper 32 bits of the 64-bit product).
4 *
5 * This code optimizes short (less than 13-bit) multiplies. Short
6 * multiplies require 25 instruction cycles, and long ones require
7 * 45 instruction cycles.
8 *
9 * On return, overflow has occurred (%o1 is not zero) if and only if
10 * the Z condition code is clear, allowing, e.g., the following:
11 *
12 * call .umul
13 * nop
14 * bnz overflow (or tnz)
15 */
17 #include "DEFS.h"
18 FUNC(.umul)
19 or %o0, %o1, %o4
20 mov %o0, %y ! multiplier -> Y
21 andncc %o4, 0xfff, %g0 ! test bits 12..31 of *both* args
22 be Lmul_shortway ! if zero, can do it the short way
23 andcc %g0, %g0, %o4 ! zero the partial product and clear N and V
25 /*
26 * Long multiply. 32 steps, followed by a final shift step.
27 */
28 mulscc %o4, %o1, %o4 ! 1
29 mulscc %o4, %o1, %o4 ! 2
30 mulscc %o4, %o1, %o4 ! 3
31 mulscc %o4, %o1, %o4 ! 4
32 mulscc %o4, %o1, %o4 ! 5
33 mulscc %o4, %o1, %o4 ! 6
34 mulscc %o4, %o1, %o4 ! 7
35 mulscc %o4, %o1, %o4 ! 8
36 mulscc %o4, %o1, %o4 ! 9
37 mulscc %o4, %o1, %o4 ! 10
38 mulscc %o4, %o1, %o4 ! 11
39 mulscc %o4, %o1, %o4 ! 12
40 mulscc %o4, %o1, %o4 ! 13
41 mulscc %o4, %o1, %o4 ! 14
42 mulscc %o4, %o1, %o4 ! 15
43 mulscc %o4, %o1, %o4 ! 16
44 mulscc %o4, %o1, %o4 ! 17
45 mulscc %o4, %o1, %o4 ! 18
46 mulscc %o4, %o1, %o4 ! 19
47 mulscc %o4, %o1, %o4 ! 20
48 mulscc %o4, %o1, %o4 ! 21
49 mulscc %o4, %o1, %o4 ! 22
50 mulscc %o4, %o1, %o4 ! 23
51 mulscc %o4, %o1, %o4 ! 24
52 mulscc %o4, %o1, %o4 ! 25
53 mulscc %o4, %o1, %o4 ! 26
54 mulscc %o4, %o1, %o4 ! 27
55 mulscc %o4, %o1, %o4 ! 28
56 mulscc %o4, %o1, %o4 ! 29
57 mulscc %o4, %o1, %o4 ! 30
58 mulscc %o4, %o1, %o4 ! 31
59 mulscc %o4, %o1, %o4 ! 32
60 mulscc %o4, %g0, %o4 ! final shift
63 /*
64 * Normally, with the shift-and-add approach, if both numbers are
65 * positive you get the correct result. With 32-bit two's-complement
66 * numbers, -x is represented as
67 *
68 * x 32
69 * ( 2 - ------ ) mod 2 * 2
70 * 32
71 * 2
72 *
73 * (the `mod 2' subtracts 1 from 1.bbbb). To avoid lots of 2^32s,
74 * we can treat this as if the radix point were just to the left
75 * of the sign bit (multiply by 2^32), and get
76 *
77 * -x = (2 - x) mod 2
78 *
79 * Then, ignoring the `mod 2's for convenience:
80 *
81 * x * y = xy
82 * -x * y = 2y - xy
83 * x * -y = 2x - xy
84 * -x * -y = 4 - 2x - 2y + xy
85 *
86 * For signed multiplies, we subtract (x << 32) from the partial
87 * product to fix this problem for negative multipliers (see mul.s).
88 * Because of the way the shift into the partial product is calculated
89 * (N xor V), this term is automatically removed for the multiplicand,
90 * so we don't have to adjust.
91 *
92 * But for unsigned multiplies, the high order bit wasn't a sign bit,
93 * and the correction is wrong. So for unsigned multiplies where the
94 * high order bit is one, we end up with xy - (y << 32). To fix it
95 * we add y << 32.
96 */
97 #if 0
98 tst %o1
99 bl,a 1f ! if %o1 < 0 (high order bit = 1),
100 add %o4, %o0, %o4 ! %o4 += %o0 (add y to upper half)
101 1: rd %y, %o0 ! get lower half of product
102 retl
103 addcc %o4, %g0, %o1 ! put upper half in place and set Z for %o1==0
104 #else
105 /* Faster code from tege@sics.se. */
106 sra %o1, 31, %o2 ! make mask from sign bit
107 and %o0, %o2, %o2 ! %o2 = 0 or %o0, depending on sign of %o1
108 rd %y, %o0 ! get lower half of product
109 retl
110 addcc %o4, %o2, %o1 ! add compensation and put upper half in place
111 #endif
113 Lmul_shortway:
114 /*
115 * Short multiply. 12 steps, followed by a final shift step.
116 * The resulting bits are off by 12 and (32-12) = 20 bit positions,
117 * but there is no problem with %o0 being negative (unlike above),
118 * and overflow is impossible (the answer is at most 24 bits long).
119 */
120 mulscc %o4, %o1, %o4 ! 1
121 mulscc %o4, %o1, %o4 ! 2
122 mulscc %o4, %o1, %o4 ! 3
123 mulscc %o4, %o1, %o4 ! 4
124 mulscc %o4, %o1, %o4 ! 5
125 mulscc %o4, %o1, %o4 ! 6
126 mulscc %o4, %o1, %o4 ! 7
127 mulscc %o4, %o1, %o4 ! 8
128 mulscc %o4, %o1, %o4 ! 9
129 mulscc %o4, %o1, %o4 ! 10
130 mulscc %o4, %o1, %o4 ! 11
131 mulscc %o4, %o1, %o4 ! 12
132 mulscc %o4, %g0, %o4 ! final shift
134 /*
135 * %o4 has 20 of the bits that should be in the result; %y has
136 * the bottom 12 (as %y's top 12). That is:
137 *
138 * %o4 %y
139 * +----------------+----------------+
140 * | -12- | -20- | -12- | -20- |
141 * +------(---------+------)---------+
142 * -----result-----
143 *
144 * The 12 bits of %o4 left of the `result' area are all zero;
145 * in fact, all top 20 bits of %o4 are zero.
146 */
148 rd %y, %o5
149 sll %o4, 12, %o0 ! shift middle bits left 12
150 srl %o5, 20, %o5 ! shift low bits right 20
151 or %o5, %o0, %o0
152 retl
153 addcc %g0, %g0, %o1 ! %o1 = zero, and set Z