Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
6595 | serge | 1 | /******************************************************************************* |
2 | * |
||
3 | * Module Name: utmath - Integer math support routines |
||
4 | * |
||
5 | ******************************************************************************/ |
||
6 | |||
7 | /* |
||
8 | * Copyright (C) 2000 - 2015, Intel Corp. |
||
9 | * All rights reserved. |
||
10 | * |
||
11 | * Redistribution and use in source and binary forms, with or without |
||
12 | * modification, are permitted provided that the following conditions |
||
13 | * are met: |
||
14 | * 1. Redistributions of source code must retain the above copyright |
||
15 | * notice, this list of conditions, and the following disclaimer, |
||
16 | * without modification. |
||
17 | * 2. Redistributions in binary form must reproduce at minimum a disclaimer |
||
18 | * substantially similar to the "NO WARRANTY" disclaimer below |
||
19 | * ("Disclaimer") and any redistribution must be conditioned upon |
||
20 | * including a substantially similar Disclaimer requirement for further |
||
21 | * binary redistribution. |
||
22 | * 3. Neither the names of the above-listed copyright holders nor the names |
||
23 | * of any contributors may be used to endorse or promote products derived |
||
24 | * from this software without specific prior written permission. |
||
25 | * |
||
26 | * Alternatively, this software may be distributed under the terms of the |
||
27 | * GNU General Public License ("GPL") version 2 as published by the Free |
||
28 | * Software Foundation. |
||
29 | * |
||
30 | * NO WARRANTY |
||
31 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
||
32 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
||
33 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR |
||
34 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
||
35 | * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
||
36 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
||
37 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
||
38 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
||
39 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING |
||
40 | * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
||
41 | * POSSIBILITY OF SUCH DAMAGES. |
||
42 | */ |
||
43 | |||
44 | #include |
||
45 | #include "accommon.h" |
||
46 | |||
47 | #define _COMPONENT ACPI_UTILITIES |
||
48 | ACPI_MODULE_NAME("utmath") |
||
49 | |||
50 | /* |
||
51 | * Optional support for 64-bit double-precision integer divide. This code |
||
52 | * is configurable and is implemented in order to support 32-bit kernel |
||
53 | * environments where a 64-bit double-precision math library is not available. |
||
54 | * |
||
55 | * Support for a more normal 64-bit divide/modulo (with check for a divide- |
||
56 | * by-zero) appears after this optional section of code. |
||
57 | */ |
||
58 | #ifndef ACPI_USE_NATIVE_DIVIDE |
||
59 | /* Structures used only for 64-bit divide */ |
||
60 | typedef struct uint64_struct { |
||
61 | u32 lo; |
||
62 | u32 hi; |
||
63 | |||
64 | } uint64_struct; |
||
65 | |||
66 | typedef union uint64_overlay { |
||
67 | u64 full; |
||
68 | struct uint64_struct part; |
||
69 | |||
70 | } uint64_overlay; |
||
71 | |||
72 | /******************************************************************************* |
||
73 | * |
||
74 | * FUNCTION: acpi_ut_short_divide |
||
75 | * |
||
76 | * PARAMETERS: dividend - 64-bit dividend |
||
77 | * divisor - 32-bit divisor |
||
78 | * out_quotient - Pointer to where the quotient is returned |
||
79 | * out_remainder - Pointer to where the remainder is returned |
||
80 | * |
||
81 | * RETURN: Status (Checks for divide-by-zero) |
||
82 | * |
||
83 | * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) |
||
84 | * divide and modulo. The result is a 64-bit quotient and a |
||
85 | * 32-bit remainder. |
||
86 | * |
||
87 | ******************************************************************************/ |
||
88 | |||
89 | acpi_status |
||
90 | acpi_ut_short_divide(u64 dividend, |
||
91 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
||
92 | { |
||
93 | union uint64_overlay dividend_ovl; |
||
94 | union uint64_overlay quotient; |
||
95 | u32 remainder32; |
||
96 | |||
97 | ACPI_FUNCTION_TRACE(ut_short_divide); |
||
98 | |||
99 | /* Always check for a zero divisor */ |
||
100 | |||
101 | if (divisor == 0) { |
||
102 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
||
103 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
||
104 | } |
||
105 | |||
106 | dividend_ovl.full = dividend; |
||
107 | |||
108 | /* |
||
109 | * The quotient is 64 bits, the remainder is always 32 bits, |
||
110 | * and is generated by the second divide. |
||
111 | */ |
||
112 | ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor, |
||
113 | quotient.part.hi, remainder32); |
||
114 | ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor, |
||
115 | quotient.part.lo, remainder32); |
||
116 | |||
117 | /* Return only what was requested */ |
||
118 | |||
119 | if (out_quotient) { |
||
120 | *out_quotient = quotient.full; |
||
121 | } |
||
122 | if (out_remainder) { |
||
123 | *out_remainder = remainder32; |
||
124 | } |
||
125 | |||
126 | return_ACPI_STATUS(AE_OK); |
||
127 | } |
||
128 | |||
129 | /******************************************************************************* |
||
130 | * |
||
131 | * FUNCTION: acpi_ut_divide |
||
132 | * |
||
133 | * PARAMETERS: in_dividend - Dividend |
||
134 | * in_divisor - Divisor |
||
135 | * out_quotient - Pointer to where the quotient is returned |
||
136 | * out_remainder - Pointer to where the remainder is returned |
||
137 | * |
||
138 | * RETURN: Status (Checks for divide-by-zero) |
||
139 | * |
||
140 | * DESCRIPTION: Perform a divide and modulo. |
||
141 | * |
||
142 | ******************************************************************************/ |
||
143 | |||
144 | acpi_status |
||
145 | acpi_ut_divide(u64 in_dividend, |
||
146 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
||
147 | { |
||
148 | union uint64_overlay dividend; |
||
149 | union uint64_overlay divisor; |
||
150 | union uint64_overlay quotient; |
||
151 | union uint64_overlay remainder; |
||
152 | union uint64_overlay normalized_dividend; |
||
153 | union uint64_overlay normalized_divisor; |
||
154 | u32 partial1; |
||
155 | union uint64_overlay partial2; |
||
156 | union uint64_overlay partial3; |
||
157 | |||
158 | ACPI_FUNCTION_TRACE(ut_divide); |
||
159 | |||
160 | /* Always check for a zero divisor */ |
||
161 | |||
162 | if (in_divisor == 0) { |
||
163 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
||
164 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
||
165 | } |
||
166 | |||
167 | divisor.full = in_divisor; |
||
168 | dividend.full = in_dividend; |
||
169 | if (divisor.part.hi == 0) { |
||
170 | /* |
||
171 | * 1) Simplest case is where the divisor is 32 bits, we can |
||
172 | * just do two divides |
||
173 | */ |
||
174 | remainder.part.hi = 0; |
||
175 | |||
176 | /* |
||
177 | * The quotient is 64 bits, the remainder is always 32 bits, |
||
178 | * and is generated by the second divide. |
||
179 | */ |
||
180 | ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo, |
||
181 | quotient.part.hi, partial1); |
||
182 | ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo, |
||
183 | quotient.part.lo, remainder.part.lo); |
||
184 | } |
||
185 | |||
186 | else { |
||
187 | /* |
||
188 | * 2) The general case where the divisor is a full 64 bits |
||
189 | * is more difficult |
||
190 | */ |
||
191 | quotient.part.hi = 0; |
||
192 | normalized_dividend = dividend; |
||
193 | normalized_divisor = divisor; |
||
194 | |||
195 | /* Normalize the operands (shift until the divisor is < 32 bits) */ |
||
196 | |||
197 | do { |
||
198 | ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi, |
||
199 | normalized_divisor.part.lo); |
||
200 | ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi, |
||
201 | normalized_dividend.part.lo); |
||
202 | |||
203 | } while (normalized_divisor.part.hi != 0); |
||
204 | |||
205 | /* Partial divide */ |
||
206 | |||
207 | ACPI_DIV_64_BY_32(normalized_dividend.part.hi, |
||
208 | normalized_dividend.part.lo, |
||
209 | normalized_divisor.part.lo, |
||
210 | quotient.part.lo, partial1); |
||
211 | |||
212 | /* |
||
213 | * The quotient is always 32 bits, and simply requires adjustment. |
||
214 | * The 64-bit remainder must be generated. |
||
215 | */ |
||
216 | partial1 = quotient.part.lo * divisor.part.hi; |
||
217 | partial2.full = (u64) quotient.part.lo * divisor.part.lo; |
||
218 | partial3.full = (u64) partial2.part.hi + partial1; |
||
219 | |||
220 | remainder.part.hi = partial3.part.lo; |
||
221 | remainder.part.lo = partial2.part.lo; |
||
222 | |||
223 | if (partial3.part.hi == 0) { |
||
224 | if (partial3.part.lo >= dividend.part.hi) { |
||
225 | if (partial3.part.lo == dividend.part.hi) { |
||
226 | if (partial2.part.lo > dividend.part.lo) { |
||
227 | quotient.part.lo--; |
||
228 | remainder.full -= divisor.full; |
||
229 | } |
||
230 | } else { |
||
231 | quotient.part.lo--; |
||
232 | remainder.full -= divisor.full; |
||
233 | } |
||
234 | } |
||
235 | |||
236 | remainder.full = remainder.full - dividend.full; |
||
237 | remainder.part.hi = (u32) - ((s32) remainder.part.hi); |
||
238 | remainder.part.lo = (u32) - ((s32) remainder.part.lo); |
||
239 | |||
240 | if (remainder.part.lo) { |
||
241 | remainder.part.hi--; |
||
242 | } |
||
243 | } |
||
244 | } |
||
245 | |||
246 | /* Return only what was requested */ |
||
247 | |||
248 | if (out_quotient) { |
||
249 | *out_quotient = quotient.full; |
||
250 | } |
||
251 | if (out_remainder) { |
||
252 | *out_remainder = remainder.full; |
||
253 | } |
||
254 | |||
255 | return_ACPI_STATUS(AE_OK); |
||
256 | } |
||
257 | |||
258 | #else |
||
259 | /******************************************************************************* |
||
260 | * |
||
261 | * FUNCTION: acpi_ut_short_divide, acpi_ut_divide |
||
262 | * |
||
263 | * PARAMETERS: See function headers above |
||
264 | * |
||
265 | * DESCRIPTION: Native versions of the ut_divide functions. Use these if either |
||
266 | * 1) The target is a 64-bit platform and therefore 64-bit |
||
267 | * integer math is supported directly by the machine. |
||
268 | * 2) The target is a 32-bit or 16-bit platform, and the |
||
269 | * double-precision integer math library is available to |
||
270 | * perform the divide. |
||
271 | * |
||
272 | ******************************************************************************/ |
||
273 | acpi_status |
||
274 | acpi_ut_short_divide(u64 in_dividend, |
||
275 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
||
276 | { |
||
277 | |||
278 | ACPI_FUNCTION_TRACE(ut_short_divide); |
||
279 | |||
280 | /* Always check for a zero divisor */ |
||
281 | |||
282 | if (divisor == 0) { |
||
283 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
||
284 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
||
285 | } |
||
286 | |||
287 | /* Return only what was requested */ |
||
288 | |||
289 | if (out_quotient) { |
||
290 | *out_quotient = in_dividend / divisor; |
||
291 | } |
||
292 | if (out_remainder) { |
||
293 | *out_remainder = (u32) (in_dividend % divisor); |
||
294 | } |
||
295 | |||
296 | return_ACPI_STATUS(AE_OK); |
||
297 | } |
||
298 | |||
299 | acpi_status |
||
300 | acpi_ut_divide(u64 in_dividend, |
||
301 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
||
302 | { |
||
303 | ACPI_FUNCTION_TRACE(ut_divide); |
||
304 | |||
305 | /* Always check for a zero divisor */ |
||
306 | |||
307 | if (in_divisor == 0) { |
||
308 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
||
309 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
||
310 | } |
||
311 | |||
312 | /* Return only what was requested */ |
||
313 | |||
314 | if (out_quotient) { |
||
315 | *out_quotient = in_dividend / in_divisor; |
||
316 | } |
||
317 | if (out_remainder) { |
||
318 | *out_remainder = in_dividend % in_divisor; |
||
319 | } |
||
320 | |||
321 | return_ACPI_STATUS(AE_OK); |
||
322 | } |
||
323 | |||
324 | #endif> |