Branch data Line data Source code
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 : 0 : acpi_ut_short_multiply(u64 multiplicand, u32 multiplier, u64 *out_product)
166 : : {
167 : :
168 : 0 : ACPI_FUNCTION_TRACE(ut_short_multiply);
169 : :
170 : : /* Return only what was requested */
171 : :
172 [ # # ]: 0 : if (out_product) {
173 : 0 : *out_product = multiplicand * multiplier;
174 : : }
175 : :
176 : 0 : 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 : 0 : acpi_status acpi_ut_short_shift_left(u64 operand, u32 count, u64 *out_result)
190 : : {
191 : :
192 : 0 : ACPI_FUNCTION_TRACE(ut_short_shift_left);
193 : :
194 : : /* Return only what was requested */
195 : :
196 [ # # ]: 0 : if (out_result) {
197 : 0 : *out_result = operand << count;
198 : : }
199 : :
200 : 0 : 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 : 25272 : acpi_status acpi_ut_short_shift_right(u64 operand, u32 count, u64 *out_result)
214 : : {
215 : :
216 : 25272 : ACPI_FUNCTION_TRACE(ut_short_shift_right);
217 : :
218 : : /* Return only what was requested */
219 : :
220 [ + - ]: 25272 : if (out_result) {
221 : 25272 : *out_result = operand >> count;
222 : : }
223 : :
224 : 25272 : 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 : 2496 : acpi_ut_short_divide(u64 in_dividend,
445 : : u32 divisor, u64 *out_quotient, u32 *out_remainder)
446 : : {
447 : :
448 : 2496 : ACPI_FUNCTION_TRACE(ut_short_divide);
449 : :
450 : : /* Always check for a zero divisor */
451 : :
452 [ - + ]: 2496 : if (divisor == 0) {
453 : 0 : ACPI_ERROR((AE_INFO, "Divide by zero"));
454 : 0 : return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
455 : : }
456 : :
457 : : /* Return only what was requested */
458 : :
459 [ + - ]: 2496 : if (out_quotient) {
460 : 2496 : *out_quotient = in_dividend / divisor;
461 : : }
462 [ + + ]: 2496 : if (out_remainder) {
463 : 1404 : *out_remainder = (u32) (in_dividend % divisor);
464 : : }
465 : :
466 : : return_ACPI_STATUS(AE_OK);
467 : : }
468 : :
469 : : acpi_status
470 : 0 : acpi_ut_divide(u64 in_dividend,
471 : : u64 in_divisor, u64 *out_quotient, u64 *out_remainder)
472 : : {
473 : 0 : ACPI_FUNCTION_TRACE(ut_divide);
474 : :
475 : : /* Always check for a zero divisor */
476 : :
477 [ # # ]: 0 : if (in_divisor == 0) {
478 : 0 : ACPI_ERROR((AE_INFO, "Divide by zero"));
479 : 0 : return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
480 : : }
481 : :
482 : : /* Return only what was requested */
483 : :
484 [ # # ]: 0 : if (out_quotient) {
485 : 0 : *out_quotient = in_dividend / in_divisor;
486 : : }
487 [ # # ]: 0 : if (out_remainder) {
488 : 0 : *out_remainder = in_dividend % in_divisor;
489 : : }
490 : :
491 : : return_ACPI_STATUS(AE_OK);
492 : : }
493 : :
494 : : #endif
|