1 | // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0 |
2 | /******************************************************************************* |
3 | * |
4 | * Module Name: utmath - Integer math support routines |
5 | * |
6 | ******************************************************************************/ |
7 | |
8 | #include <acpi/acpi.h> |
9 | #include "accommon.h" |
10 | |
11 | #define _COMPONENT ACPI_UTILITIES |
12 | ACPI_MODULE_NAME("utmath" ) |
13 | |
14 | /* Structures used only for 64-bit divide */ |
15 | typedef struct uint64_struct { |
16 | u32 lo; |
17 | u32 hi; |
18 | |
19 | } uint64_struct; |
20 | |
21 | typedef union uint64_overlay { |
22 | u64 full; |
23 | struct uint64_struct part; |
24 | |
25 | } uint64_overlay; |
26 | |
27 | /* |
28 | * Optional support for 64-bit double-precision integer multiply and shift. |
29 | * This code is configurable and is implemented in order to support 32-bit |
30 | * kernel environments where a 64-bit double-precision math library is not |
31 | * available. |
32 | */ |
33 | #ifndef ACPI_USE_NATIVE_MATH64 |
34 | |
35 | /******************************************************************************* |
36 | * |
37 | * FUNCTION: acpi_ut_short_multiply |
38 | * |
39 | * PARAMETERS: multiplicand - 64-bit multiplicand |
40 | * multiplier - 32-bit multiplier |
41 | * out_product - Pointer to where the product is returned |
42 | * |
43 | * DESCRIPTION: Perform a short multiply. |
44 | * |
45 | ******************************************************************************/ |
46 | |
47 | acpi_status |
48 | acpi_ut_short_multiply(u64 multiplicand, u32 multiplier, u64 *out_product) |
49 | { |
50 | union uint64_overlay multiplicand_ovl; |
51 | union uint64_overlay product; |
52 | u32 carry32; |
53 | |
54 | ACPI_FUNCTION_TRACE(ut_short_multiply); |
55 | |
56 | multiplicand_ovl.full = multiplicand; |
57 | |
58 | /* |
59 | * The Product is 64 bits, the carry is always 32 bits, |
60 | * and is generated by the second multiply. |
61 | */ |
62 | ACPI_MUL_64_BY_32(0, multiplicand_ovl.part.hi, multiplier, |
63 | product.part.hi, carry32); |
64 | |
65 | ACPI_MUL_64_BY_32(0, multiplicand_ovl.part.lo, multiplier, |
66 | product.part.lo, carry32); |
67 | |
68 | product.part.hi += carry32; |
69 | |
70 | /* Return only what was requested */ |
71 | |
72 | if (out_product) { |
73 | *out_product = product.full; |
74 | } |
75 | |
76 | return_ACPI_STATUS(AE_OK); |
77 | } |
78 | |
79 | /******************************************************************************* |
80 | * |
81 | * FUNCTION: acpi_ut_short_shift_left |
82 | * |
83 | * PARAMETERS: operand - 64-bit shift operand |
84 | * count - 32-bit shift count |
85 | * out_result - Pointer to where the result is returned |
86 | * |
87 | * DESCRIPTION: Perform a short left shift. |
88 | * |
89 | ******************************************************************************/ |
90 | |
91 | acpi_status acpi_ut_short_shift_left(u64 operand, u32 count, u64 *out_result) |
92 | { |
93 | union uint64_overlay operand_ovl; |
94 | |
95 | ACPI_FUNCTION_TRACE(ut_short_shift_left); |
96 | |
97 | operand_ovl.full = operand; |
98 | |
99 | if ((count & 63) >= 32) { |
100 | operand_ovl.part.hi = operand_ovl.part.lo; |
101 | operand_ovl.part.lo = 0; |
102 | count = (count & 63) - 32; |
103 | } |
104 | ACPI_SHIFT_LEFT_64_BY_32(operand_ovl.part.hi, |
105 | operand_ovl.part.lo, count); |
106 | |
107 | /* Return only what was requested */ |
108 | |
109 | if (out_result) { |
110 | *out_result = operand_ovl.full; |
111 | } |
112 | |
113 | return_ACPI_STATUS(AE_OK); |
114 | } |
115 | |
116 | /******************************************************************************* |
117 | * |
118 | * FUNCTION: acpi_ut_short_shift_right |
119 | * |
120 | * PARAMETERS: operand - 64-bit shift operand |
121 | * count - 32-bit shift count |
122 | * out_result - Pointer to where the result is returned |
123 | * |
124 | * DESCRIPTION: Perform a short right shift. |
125 | * |
126 | ******************************************************************************/ |
127 | |
128 | acpi_status acpi_ut_short_shift_right(u64 operand, u32 count, u64 *out_result) |
129 | { |
130 | union uint64_overlay operand_ovl; |
131 | |
132 | ACPI_FUNCTION_TRACE(ut_short_shift_right); |
133 | |
134 | operand_ovl.full = operand; |
135 | |
136 | if ((count & 63) >= 32) { |
137 | operand_ovl.part.lo = operand_ovl.part.hi; |
138 | operand_ovl.part.hi = 0; |
139 | count = (count & 63) - 32; |
140 | } |
141 | ACPI_SHIFT_RIGHT_64_BY_32(operand_ovl.part.hi, |
142 | operand_ovl.part.lo, count); |
143 | |
144 | /* Return only what was requested */ |
145 | |
146 | if (out_result) { |
147 | *out_result = operand_ovl.full; |
148 | } |
149 | |
150 | return_ACPI_STATUS(AE_OK); |
151 | } |
152 | #else |
153 | |
154 | /******************************************************************************* |
155 | * |
156 | * FUNCTION: acpi_ut_short_multiply |
157 | * |
158 | * PARAMETERS: See function headers above |
159 | * |
160 | * DESCRIPTION: Native version of the ut_short_multiply function. |
161 | * |
162 | ******************************************************************************/ |
163 | |
164 | acpi_status |
165 | acpi_ut_short_multiply(u64 multiplicand, u32 multiplier, u64 *out_product) |
166 | { |
167 | |
168 | ACPI_FUNCTION_TRACE(ut_short_multiply); |
169 | |
170 | /* Return only what was requested */ |
171 | |
172 | if (out_product) { |
173 | *out_product = multiplicand * multiplier; |
174 | } |
175 | |
176 | return_ACPI_STATUS(AE_OK); |
177 | } |
178 | |
179 | /******************************************************************************* |
180 | * |
181 | * FUNCTION: acpi_ut_short_shift_left |
182 | * |
183 | * PARAMETERS: See function headers above |
184 | * |
185 | * DESCRIPTION: Native version of the ut_short_shift_left function. |
186 | * |
187 | ******************************************************************************/ |
188 | |
189 | acpi_status acpi_ut_short_shift_left(u64 operand, u32 count, u64 *out_result) |
190 | { |
191 | |
192 | ACPI_FUNCTION_TRACE(ut_short_shift_left); |
193 | |
194 | /* Return only what was requested */ |
195 | |
196 | if (out_result) { |
197 | *out_result = operand << count; |
198 | } |
199 | |
200 | return_ACPI_STATUS(AE_OK); |
201 | } |
202 | |
203 | /******************************************************************************* |
204 | * |
205 | * FUNCTION: acpi_ut_short_shift_right |
206 | * |
207 | * PARAMETERS: See function headers above |
208 | * |
209 | * DESCRIPTION: Native version of the ut_short_shift_right function. |
210 | * |
211 | ******************************************************************************/ |
212 | |
213 | acpi_status acpi_ut_short_shift_right(u64 operand, u32 count, u64 *out_result) |
214 | { |
215 | |
216 | ACPI_FUNCTION_TRACE(ut_short_shift_right); |
217 | |
218 | /* Return only what was requested */ |
219 | |
220 | if (out_result) { |
221 | *out_result = operand >> count; |
222 | } |
223 | |
224 | return_ACPI_STATUS(AE_OK); |
225 | } |
226 | #endif |
227 | |
228 | /* |
229 | * Optional support for 64-bit double-precision integer divide. This code |
230 | * is configurable and is implemented in order to support 32-bit kernel |
231 | * environments where a 64-bit double-precision math library is not available. |
232 | * |
233 | * Support for a more normal 64-bit divide/modulo (with check for a divide- |
234 | * by-zero) appears after this optional section of code. |
235 | */ |
236 | #ifndef ACPI_USE_NATIVE_DIVIDE |
237 | |
238 | /******************************************************************************* |
239 | * |
240 | * FUNCTION: acpi_ut_short_divide |
241 | * |
242 | * PARAMETERS: dividend - 64-bit dividend |
243 | * divisor - 32-bit divisor |
244 | * out_quotient - Pointer to where the quotient is returned |
245 | * out_remainder - Pointer to where the remainder is returned |
246 | * |
247 | * RETURN: Status (Checks for divide-by-zero) |
248 | * |
249 | * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) |
250 | * divide and modulo. The result is a 64-bit quotient and a |
251 | * 32-bit remainder. |
252 | * |
253 | ******************************************************************************/ |
254 | |
255 | acpi_status |
256 | acpi_ut_short_divide(u64 dividend, |
257 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
258 | { |
259 | union uint64_overlay dividend_ovl; |
260 | union uint64_overlay quotient; |
261 | u32 remainder32; |
262 | |
263 | ACPI_FUNCTION_TRACE(ut_short_divide); |
264 | |
265 | /* Always check for a zero divisor */ |
266 | |
267 | if (divisor == 0) { |
268 | ACPI_ERROR((AE_INFO, "Divide by zero" )); |
269 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
270 | } |
271 | |
272 | dividend_ovl.full = dividend; |
273 | |
274 | /* |
275 | * The quotient is 64 bits, the remainder is always 32 bits, |
276 | * and is generated by the second divide. |
277 | */ |
278 | ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor, |
279 | quotient.part.hi, remainder32); |
280 | |
281 | ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor, |
282 | quotient.part.lo, remainder32); |
283 | |
284 | /* Return only what was requested */ |
285 | |
286 | if (out_quotient) { |
287 | *out_quotient = quotient.full; |
288 | } |
289 | if (out_remainder) { |
290 | *out_remainder = remainder32; |
291 | } |
292 | |
293 | return_ACPI_STATUS(AE_OK); |
294 | } |
295 | |
296 | /******************************************************************************* |
297 | * |
298 | * FUNCTION: acpi_ut_divide |
299 | * |
300 | * PARAMETERS: in_dividend - Dividend |
301 | * in_divisor - Divisor |
302 | * out_quotient - Pointer to where the quotient is returned |
303 | * out_remainder - Pointer to where the remainder is returned |
304 | * |
305 | * RETURN: Status (Checks for divide-by-zero) |
306 | * |
307 | * DESCRIPTION: Perform a divide and modulo. |
308 | * |
309 | ******************************************************************************/ |
310 | |
311 | acpi_status |
312 | acpi_ut_divide(u64 in_dividend, |
313 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
314 | { |
315 | union uint64_overlay dividend; |
316 | union uint64_overlay divisor; |
317 | union uint64_overlay quotient; |
318 | union uint64_overlay remainder; |
319 | union uint64_overlay normalized_dividend; |
320 | union uint64_overlay normalized_divisor; |
321 | u32 partial1; |
322 | union uint64_overlay partial2; |
323 | union uint64_overlay partial3; |
324 | |
325 | ACPI_FUNCTION_TRACE(ut_divide); |
326 | |
327 | /* Always check for a zero divisor */ |
328 | |
329 | if (in_divisor == 0) { |
330 | ACPI_ERROR((AE_INFO, "Divide by zero" )); |
331 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
332 | } |
333 | |
334 | divisor.full = in_divisor; |
335 | dividend.full = in_dividend; |
336 | if (divisor.part.hi == 0) { |
337 | /* |
338 | * 1) Simplest case is where the divisor is 32 bits, we can |
339 | * just do two divides |
340 | */ |
341 | remainder.part.hi = 0; |
342 | |
343 | /* |
344 | * The quotient is 64 bits, the remainder is always 32 bits, |
345 | * and is generated by the second divide. |
346 | */ |
347 | ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo, |
348 | quotient.part.hi, partial1); |
349 | |
350 | ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo, |
351 | quotient.part.lo, remainder.part.lo); |
352 | } |
353 | |
354 | else { |
355 | /* |
356 | * 2) The general case where the divisor is a full 64 bits |
357 | * is more difficult |
358 | */ |
359 | quotient.part.hi = 0; |
360 | normalized_dividend = dividend; |
361 | normalized_divisor = divisor; |
362 | |
363 | /* Normalize the operands (shift until the divisor is < 32 bits) */ |
364 | |
365 | do { |
366 | ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi, |
367 | normalized_divisor.part.lo); |
368 | ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi, |
369 | normalized_dividend.part.lo); |
370 | |
371 | } while (normalized_divisor.part.hi != 0); |
372 | |
373 | /* Partial divide */ |
374 | |
375 | ACPI_DIV_64_BY_32(normalized_dividend.part.hi, |
376 | normalized_dividend.part.lo, |
377 | normalized_divisor.part.lo, quotient.part.lo, |
378 | partial1); |
379 | |
380 | /* |
381 | * The quotient is always 32 bits, and simply requires |
382 | * adjustment. The 64-bit remainder must be generated. |
383 | */ |
384 | partial1 = quotient.part.lo * divisor.part.hi; |
385 | partial2.full = (u64) quotient.part.lo * divisor.part.lo; |
386 | partial3.full = (u64) partial2.part.hi + partial1; |
387 | |
388 | remainder.part.hi = partial3.part.lo; |
389 | remainder.part.lo = partial2.part.lo; |
390 | |
391 | if (partial3.part.hi == 0) { |
392 | if (partial3.part.lo >= dividend.part.hi) { |
393 | if (partial3.part.lo == dividend.part.hi) { |
394 | if (partial2.part.lo > dividend.part.lo) { |
395 | quotient.part.lo--; |
396 | remainder.full -= divisor.full; |
397 | } |
398 | } else { |
399 | quotient.part.lo--; |
400 | remainder.full -= divisor.full; |
401 | } |
402 | } |
403 | |
404 | remainder.full = remainder.full - dividend.full; |
405 | remainder.part.hi = (u32)-((s32)remainder.part.hi); |
406 | remainder.part.lo = (u32)-((s32)remainder.part.lo); |
407 | |
408 | if (remainder.part.lo) { |
409 | remainder.part.hi--; |
410 | } |
411 | } |
412 | } |
413 | |
414 | /* Return only what was requested */ |
415 | |
416 | if (out_quotient) { |
417 | *out_quotient = quotient.full; |
418 | } |
419 | if (out_remainder) { |
420 | *out_remainder = remainder.full; |
421 | } |
422 | |
423 | return_ACPI_STATUS(AE_OK); |
424 | } |
425 | |
426 | #else |
427 | |
428 | /******************************************************************************* |
429 | * |
430 | * FUNCTION: acpi_ut_short_divide, acpi_ut_divide |
431 | * |
432 | * PARAMETERS: See function headers above |
433 | * |
434 | * DESCRIPTION: Native versions of the ut_divide functions. Use these if either |
435 | * 1) The target is a 64-bit platform and therefore 64-bit |
436 | * integer math is supported directly by the machine. |
437 | * 2) The target is a 32-bit or 16-bit platform, and the |
438 | * double-precision integer math library is available to |
439 | * perform the divide. |
440 | * |
441 | ******************************************************************************/ |
442 | |
443 | acpi_status |
444 | acpi_ut_short_divide(u64 in_dividend, |
445 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
446 | { |
447 | |
448 | ACPI_FUNCTION_TRACE(ut_short_divide); |
449 | |
450 | /* Always check for a zero divisor */ |
451 | |
452 | if (divisor == 0) { |
453 | ACPI_ERROR((AE_INFO, "Divide by zero" )); |
454 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
455 | } |
456 | |
457 | /* Return only what was requested */ |
458 | |
459 | if (out_quotient) { |
460 | *out_quotient = in_dividend / divisor; |
461 | } |
462 | if (out_remainder) { |
463 | *out_remainder = (u32) (in_dividend % divisor); |
464 | } |
465 | |
466 | return_ACPI_STATUS(AE_OK); |
467 | } |
468 | |
469 | acpi_status |
470 | acpi_ut_divide(u64 in_dividend, |
471 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
472 | { |
473 | ACPI_FUNCTION_TRACE(ut_divide); |
474 | |
475 | /* Always check for a zero divisor */ |
476 | |
477 | if (in_divisor == 0) { |
478 | ACPI_ERROR((AE_INFO, "Divide by zero" )); |
479 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
480 | } |
481 | |
482 | /* Return only what was requested */ |
483 | |
484 | if (out_quotient) { |
485 | *out_quotient = in_dividend / in_divisor; |
486 | } |
487 | if (out_remainder) { |
488 | *out_remainder = in_dividend % in_divisor; |
489 | } |
490 | |
491 | return_ACPI_STATUS(AE_OK); |
492 | } |
493 | |
494 | #endif |
495 | |