]>
Commit | Line | Data |
---|---|---|
e9d07601 FP |
1 | /* |
2 | * 128-bit division and remainder for compilers not supporting __int128 | |
3 | * | |
4 | * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr> | |
5 | * | |
6 | * Permission is hereby granted, free of charge, to any person obtaining a copy | |
7 | * of this software and associated documentation files (the "Software"), to deal | |
8 | * in the Software without restriction, including without limitation the rights | |
9 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
10 | * copies of the Software, and to permit persons to whom the Software is | |
11 | * furnished to do so, subject to the following conditions: | |
12 | * | |
13 | * The above copyright notice and this permission notice shall be included in | |
14 | * all copies or substantial portions of the Software. | |
15 | * | |
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
19 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
20 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
21 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
22 | * THE SOFTWARE. | |
23 | */ | |
24 | ||
25 | #include "qemu/osdep.h" | |
26 | #include "qemu/host-utils.h" | |
27 | #include "qemu/int128.h" | |
28 | ||
29 | #ifndef CONFIG_INT128 | |
30 | ||
31 | /* | |
32 | * Division and remainder algorithms for 128-bit due to Stefan Kanthak, | |
33 | * https://skanthak.homepage.t-online.de/integer.html#udivmodti4 | |
34 | * Preconditions: | |
35 | * - function should never be called with v equals to 0, it has to | |
36 | * be dealt with beforehand | |
37 | * - quotien pointer must be valid | |
38 | */ | |
39 | static Int128 divrem128(Int128 u, Int128 v, Int128 *q) | |
40 | { | |
41 | Int128 qq; | |
42 | uint64_t hi, lo, tmp; | |
43 | int s = clz64(v.hi); | |
44 | ||
45 | if (s == 64) { | |
46 | /* we have uu÷0v => let's use divu128 */ | |
47 | hi = u.hi; | |
48 | lo = u.lo; | |
49 | tmp = divu128(&lo, &hi, v.lo); | |
50 | *q = int128_make128(lo, hi); | |
51 | return int128_make128(tmp, 0); | |
52 | } else { | |
53 | hi = int128_gethi(int128_lshift(v, s)); | |
54 | ||
55 | if (hi > u.hi) { | |
56 | lo = u.lo; | |
57 | tmp = u.hi; | |
58 | divu128(&lo, &tmp, hi); | |
59 | lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s)); | |
60 | } else { /* prevent overflow */ | |
61 | lo = u.lo; | |
62 | tmp = u.hi - hi; | |
63 | divu128(&lo, &tmp, hi); | |
64 | lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s)); | |
65 | } | |
66 | ||
67 | qq = int128_make64(lo); | |
68 | ||
69 | tmp = lo * v.hi; | |
70 | mulu64(&lo, &hi, lo, v.lo); | |
71 | hi += tmp; | |
72 | ||
73 | if (hi < tmp /* quotient * divisor >= 2**128 > dividend */ | |
74 | || hi > u.hi /* quotient * divisor > dividend */ | |
75 | || (hi == u.hi && lo > u.lo)) { | |
76 | qq.lo -= 1; | |
77 | mulu64(&lo, &hi, qq.lo, v.lo); | |
78 | hi += qq.lo * v.hi; | |
79 | } | |
80 | ||
81 | *q = qq; | |
82 | u.hi -= hi + (u.lo < lo); | |
83 | u.lo -= lo; | |
84 | return u; | |
85 | } | |
86 | } | |
87 | ||
88 | Int128 int128_divu(Int128 a, Int128 b) | |
89 | { | |
90 | Int128 q; | |
91 | divrem128(a, b, &q); | |
92 | return q; | |
93 | } | |
94 | ||
95 | Int128 int128_remu(Int128 a, Int128 b) | |
96 | { | |
97 | Int128 q; | |
98 | return divrem128(a, b, &q); | |
99 | } | |
100 | ||
101 | Int128 int128_divs(Int128 a, Int128 b) | |
102 | { | |
103 | Int128 q; | |
104 | bool sgna = !int128_nonneg(a); | |
105 | bool sgnb = !int128_nonneg(b); | |
106 | ||
107 | if (sgna) { | |
108 | a = int128_neg(a); | |
109 | } | |
110 | ||
111 | if (sgnb) { | |
112 | b = int128_neg(b); | |
113 | } | |
114 | ||
115 | divrem128(a, b, &q); | |
116 | ||
117 | if (sgna != sgnb) { | |
118 | q = int128_neg(q); | |
119 | } | |
120 | ||
121 | return q; | |
122 | } | |
123 | ||
124 | Int128 int128_rems(Int128 a, Int128 b) | |
125 | { | |
126 | Int128 q, r; | |
127 | bool sgna = !int128_nonneg(a); | |
128 | bool sgnb = !int128_nonneg(b); | |
129 | ||
130 | if (sgna) { | |
131 | a = int128_neg(a); | |
132 | } | |
133 | ||
134 | if (sgnb) { | |
135 | b = int128_neg(b); | |
136 | } | |
137 | ||
138 | r = divrem128(a, b, &q); | |
139 | ||
140 | if (sgna) { | |
141 | r = int128_neg(r); | |
142 | } | |
143 | ||
144 | return r; | |
145 | } | |
146 | ||
b959822c RH |
147 | #elif defined(CONFIG_TCG_INTERPRETER) |
148 | ||
149 | Int128 int128_divu(Int128 a_s, Int128 b_s) | |
150 | { | |
151 | Int128Alias r, a, b; | |
152 | ||
153 | a.s = a_s; | |
154 | b.s = b_s; | |
155 | r.u = a.u / b.u; | |
156 | return r.s; | |
157 | } | |
158 | ||
159 | Int128 int128_remu(Int128 a_s, Int128 b_s) | |
160 | { | |
161 | Int128Alias r, a, b; | |
162 | ||
163 | a.s = a_s; | |
164 | b.s = b_s; | |
165 | r.u = a.u % b.u; | |
166 | return r.s; | |
167 | } | |
168 | ||
169 | Int128 int128_divs(Int128 a_s, Int128 b_s) | |
170 | { | |
171 | Int128Alias r, a, b; | |
172 | ||
173 | a.s = a_s; | |
174 | b.s = b_s; | |
175 | r.i = a.i / b.i; | |
176 | return r.s; | |
177 | } | |
178 | ||
179 | Int128 int128_rems(Int128 a_s, Int128 b_s) | |
180 | { | |
181 | Int128Alias r, a, b; | |
182 | ||
183 | a.s = a_s; | |
184 | b.s = b_s; | |
185 | r.i = a.i % b.i; | |
186 | return r.s; | |
187 | } | |
188 | ||
e9d07601 | 189 | #endif |