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