758b8bf69b7936b9907753bdea3874498904ce26
[reactos.git] / drivers / bus / acpi / acpica / utilities / utmath.c
1 /*******************************************************************************
2 *
3 * Module Name: utmath - Integer math support routines
4 *
5 ******************************************************************************/
6
7 /*
8 * Copyright (C) 2000 - 2017, 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 "acpi.h"
45 #include "accommon.h"
46
47
48 #define _COMPONENT ACPI_UTILITIES
49 ACPI_MODULE_NAME ("utmath")
50
51 /* Structures used only for 64-bit divide */
52
53 typedef struct uint64_struct
54 {
55 UINT32 Lo;
56 UINT32 Hi;
57
58 } UINT64_STRUCT;
59
60 typedef union uint64_overlay
61 {
62 UINT64 Full;
63 UINT64_STRUCT Part;
64
65 } UINT64_OVERLAY;
66
67 /*
68 * Optional support for 64-bit double-precision integer multiply and shift.
69 * This code is configurable and is implemented in order to support 32-bit
70 * kernel environments where a 64-bit double-precision math library is not
71 * available.
72 */
73 #ifndef ACPI_USE_NATIVE_MATH64
74
75 /*******************************************************************************
76 *
77 * FUNCTION: AcpiUtShortMultiply
78 *
79 * PARAMETERS: Multiplicand - 64-bit multiplicand
80 * Multiplier - 32-bit multiplier
81 * OutProduct - Pointer to where the product is returned
82 *
83 * DESCRIPTION: Perform a short multiply.
84 *
85 ******************************************************************************/
86
87 ACPI_STATUS
88 AcpiUtShortMultiply (
89 UINT64 Multiplicand,
90 UINT32 Multiplier,
91 UINT64 *OutProduct)
92 {
93 UINT64_OVERLAY MultiplicandOvl;
94 UINT64_OVERLAY Product;
95 UINT32 Carry32;
96
97
98 ACPI_FUNCTION_TRACE (UtShortMultiply);
99
100
101 MultiplicandOvl.Full = Multiplicand;
102
103 /*
104 * The Product is 64 bits, the carry is always 32 bits,
105 * and is generated by the second multiply.
106 */
107 ACPI_MUL_64_BY_32 (0, MultiplicandOvl.Part.Hi, Multiplier,
108 Product.Part.Hi, Carry32);
109
110 ACPI_MUL_64_BY_32 (0, MultiplicandOvl.Part.Lo, Multiplier,
111 Product.Part.Lo, Carry32);
112
113 Product.Part.Hi += Carry32;
114
115 /* Return only what was requested */
116
117 if (OutProduct)
118 {
119 *OutProduct = Product.Full;
120 }
121
122 return_ACPI_STATUS (AE_OK);
123 }
124
125
126 /*******************************************************************************
127 *
128 * FUNCTION: AcpiUtShortShiftLeft
129 *
130 * PARAMETERS: Operand - 64-bit shift operand
131 * Count - 32-bit shift count
132 * OutResult - Pointer to where the result is returned
133 *
134 * DESCRIPTION: Perform a short left shift.
135 *
136 ******************************************************************************/
137
138 ACPI_STATUS
139 AcpiUtShortShiftLeft (
140 UINT64 Operand,
141 UINT32 Count,
142 UINT64 *OutResult)
143 {
144 UINT64_OVERLAY OperandOvl;
145
146
147 ACPI_FUNCTION_TRACE (UtShortShiftLeft);
148
149
150 OperandOvl.Full = Operand;
151
152 if ((Count & 63) >= 32)
153 {
154 OperandOvl.Part.Hi = OperandOvl.Part.Lo;
155 OperandOvl.Part.Lo ^= OperandOvl.Part.Lo;
156 Count = (Count & 63) - 32;
157 }
158 ACPI_SHIFT_LEFT_64_BY_32 (OperandOvl.Part.Hi,
159 OperandOvl.Part.Lo, Count);
160
161 /* Return only what was requested */
162
163 if (OutResult)
164 {
165 *OutResult = OperandOvl.Full;
166 }
167
168 return_ACPI_STATUS (AE_OK);
169 }
170
171 /*******************************************************************************
172 *
173 * FUNCTION: AcpiUtShortShiftRight
174 *
175 * PARAMETERS: Operand - 64-bit shift operand
176 * Count - 32-bit shift count
177 * OutResult - Pointer to where the result is returned
178 *
179 * DESCRIPTION: Perform a short right shift.
180 *
181 ******************************************************************************/
182
183 ACPI_STATUS
184 AcpiUtShortShiftRight (
185 UINT64 Operand,
186 UINT32 Count,
187 UINT64 *OutResult)
188 {
189 UINT64_OVERLAY OperandOvl;
190
191
192 ACPI_FUNCTION_TRACE (UtShortShiftRight);
193
194
195 OperandOvl.Full = Operand;
196
197 if ((Count & 63) >= 32)
198 {
199 OperandOvl.Part.Lo = OperandOvl.Part.Hi;
200 OperandOvl.Part.Hi ^= OperandOvl.Part.Hi;
201 Count = (Count & 63) - 32;
202 }
203 ACPI_SHIFT_RIGHT_64_BY_32 (OperandOvl.Part.Hi,
204 OperandOvl.Part.Lo, Count);
205
206 /* Return only what was requested */
207
208 if (OutResult)
209 {
210 *OutResult = OperandOvl.Full;
211 }
212
213 return_ACPI_STATUS (AE_OK);
214 }
215 #else
216
217 /*******************************************************************************
218 *
219 * FUNCTION: AcpiUtShortMultiply
220 *
221 * PARAMETERS: See function headers above
222 *
223 * DESCRIPTION: Native version of the UtShortMultiply function.
224 *
225 ******************************************************************************/
226
227 ACPI_STATUS
228 AcpiUtShortMultiply (
229 UINT64 Multiplicand,
230 UINT32 Multiplier,
231 UINT64 *OutProduct)
232 {
233
234 ACPI_FUNCTION_TRACE (UtShortMultiply);
235
236
237 /* Return only what was requested */
238
239 if (OutProduct)
240 {
241 *OutProduct = Multiplicand * Multiplier;
242 }
243
244 return_ACPI_STATUS (AE_OK);
245 }
246
247 /*******************************************************************************
248 *
249 * FUNCTION: AcpiUtShortShiftLeft
250 *
251 * PARAMETERS: See function headers above
252 *
253 * DESCRIPTION: Native version of the UtShortShiftLeft function.
254 *
255 ******************************************************************************/
256
257 ACPI_STATUS
258 AcpiUtShortShiftLeft (
259 UINT64 Operand,
260 UINT32 Count,
261 UINT64 *OutResult)
262 {
263
264 ACPI_FUNCTION_TRACE (UtShortShiftLeft);
265
266
267 /* Return only what was requested */
268
269 if (OutResult)
270 {
271 *OutResult = Operand << Count;
272 }
273
274 return_ACPI_STATUS (AE_OK);
275 }
276
277 /*******************************************************************************
278 *
279 * FUNCTION: AcpiUtShortShiftRight
280 *
281 * PARAMETERS: See function headers above
282 *
283 * DESCRIPTION: Native version of the UtShortShiftRight function.
284 *
285 ******************************************************************************/
286
287 ACPI_STATUS
288 AcpiUtShortShiftRight (
289 UINT64 Operand,
290 UINT32 Count,
291 UINT64 *OutResult)
292 {
293
294 ACPI_FUNCTION_TRACE (UtShortShiftRight);
295
296
297 /* Return only what was requested */
298
299 if (OutResult)
300 {
301 *OutResult = Operand >> Count;
302 }
303
304 return_ACPI_STATUS (AE_OK);
305 }
306 #endif
307
308 /*
309 * Optional support for 64-bit double-precision integer divide. This code
310 * is configurable and is implemented in order to support 32-bit kernel
311 * environments where a 64-bit double-precision math library is not available.
312 *
313 * Support for a more normal 64-bit divide/modulo (with check for a divide-
314 * by-zero) appears after this optional section of code.
315 */
316 #ifndef ACPI_USE_NATIVE_DIVIDE
317
318
319 /*******************************************************************************
320 *
321 * FUNCTION: AcpiUtShortDivide
322 *
323 * PARAMETERS: Dividend - 64-bit dividend
324 * Divisor - 32-bit divisor
325 * OutQuotient - Pointer to where the quotient is returned
326 * OutRemainder - Pointer to where the remainder is returned
327 *
328 * RETURN: Status (Checks for divide-by-zero)
329 *
330 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
331 * divide and modulo. The result is a 64-bit quotient and a
332 * 32-bit remainder.
333 *
334 ******************************************************************************/
335
336 ACPI_STATUS
337 AcpiUtShortDivide (
338 UINT64 Dividend,
339 UINT32 Divisor,
340 UINT64 *OutQuotient,
341 UINT32 *OutRemainder)
342 {
343 UINT64_OVERLAY DividendOvl;
344 UINT64_OVERLAY Quotient;
345 UINT32 Remainder32;
346
347
348 ACPI_FUNCTION_TRACE (UtShortDivide);
349
350
351 /* Always check for a zero divisor */
352
353 if (Divisor == 0)
354 {
355 ACPI_ERROR ((AE_INFO, "Divide by zero"));
356 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
357 }
358
359 DividendOvl.Full = Dividend;
360
361 /*
362 * The quotient is 64 bits, the remainder is always 32 bits,
363 * and is generated by the second divide.
364 */
365 ACPI_DIV_64_BY_32 (0, DividendOvl.Part.Hi, Divisor,
366 Quotient.Part.Hi, Remainder32);
367
368 ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor,
369 Quotient.Part.Lo, Remainder32);
370
371 /* Return only what was requested */
372
373 if (OutQuotient)
374 {
375 *OutQuotient = Quotient.Full;
376 }
377 if (OutRemainder)
378 {
379 *OutRemainder = Remainder32;
380 }
381
382 return_ACPI_STATUS (AE_OK);
383 }
384
385
386 /*******************************************************************************
387 *
388 * FUNCTION: AcpiUtDivide
389 *
390 * PARAMETERS: InDividend - Dividend
391 * InDivisor - Divisor
392 * OutQuotient - Pointer to where the quotient is returned
393 * OutRemainder - Pointer to where the remainder is returned
394 *
395 * RETURN: Status (Checks for divide-by-zero)
396 *
397 * DESCRIPTION: Perform a divide and modulo.
398 *
399 ******************************************************************************/
400
401 ACPI_STATUS
402 AcpiUtDivide (
403 UINT64 InDividend,
404 UINT64 InDivisor,
405 UINT64 *OutQuotient,
406 UINT64 *OutRemainder)
407 {
408 UINT64_OVERLAY Dividend;
409 UINT64_OVERLAY Divisor;
410 UINT64_OVERLAY Quotient;
411 UINT64_OVERLAY Remainder;
412 UINT64_OVERLAY NormalizedDividend;
413 UINT64_OVERLAY NormalizedDivisor;
414 UINT32 Partial1;
415 UINT64_OVERLAY Partial2;
416 UINT64_OVERLAY Partial3;
417
418
419 ACPI_FUNCTION_TRACE (UtDivide);
420
421
422 /* Always check for a zero divisor */
423
424 if (InDivisor == 0)
425 {
426 ACPI_ERROR ((AE_INFO, "Divide by zero"));
427 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
428 }
429
430 Divisor.Full = InDivisor;
431 Dividend.Full = InDividend;
432 if (Divisor.Part.Hi == 0)
433 {
434 /*
435 * 1) Simplest case is where the divisor is 32 bits, we can
436 * just do two divides
437 */
438 Remainder.Part.Hi = 0;
439
440 /*
441 * The quotient is 64 bits, the remainder is always 32 bits,
442 * and is generated by the second divide.
443 */
444 ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo,
445 Quotient.Part.Hi, Partial1);
446
447 ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo,
448 Quotient.Part.Lo, Remainder.Part.Lo);
449 }
450
451 else
452 {
453 /*
454 * 2) The general case where the divisor is a full 64 bits
455 * is more difficult
456 */
457 Quotient.Part.Hi = 0;
458 NormalizedDividend = Dividend;
459 NormalizedDivisor = Divisor;
460
461 /* Normalize the operands (shift until the divisor is < 32 bits) */
462
463 do
464 {
465 ACPI_SHIFT_RIGHT_64 (
466 NormalizedDivisor.Part.Hi, NormalizedDivisor.Part.Lo);
467 ACPI_SHIFT_RIGHT_64 (
468 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo);
469
470 } while (NormalizedDivisor.Part.Hi != 0);
471
472 /* Partial divide */
473
474 ACPI_DIV_64_BY_32 (
475 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo,
476 NormalizedDivisor.Part.Lo, Quotient.Part.Lo, Partial1);
477
478 /*
479 * The quotient is always 32 bits, and simply requires
480 * adjustment. The 64-bit remainder must be generated.
481 */
482 Partial1 = Quotient.Part.Lo * Divisor.Part.Hi;
483 Partial2.Full = (UINT64) Quotient.Part.Lo * Divisor.Part.Lo;
484 Partial3.Full = (UINT64) Partial2.Part.Hi + Partial1;
485
486 Remainder.Part.Hi = Partial3.Part.Lo;
487 Remainder.Part.Lo = Partial2.Part.Lo;
488
489 if (Partial3.Part.Hi == 0)
490 {
491 if (Partial3.Part.Lo >= Dividend.Part.Hi)
492 {
493 if (Partial3.Part.Lo == Dividend.Part.Hi)
494 {
495 if (Partial2.Part.Lo > Dividend.Part.Lo)
496 {
497 Quotient.Part.Lo--;
498 Remainder.Full -= Divisor.Full;
499 }
500 }
501 else
502 {
503 Quotient.Part.Lo--;
504 Remainder.Full -= Divisor.Full;
505 }
506 }
507
508 Remainder.Full = Remainder.Full - Dividend.Full;
509 Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi);
510 Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo);
511
512 if (Remainder.Part.Lo)
513 {
514 Remainder.Part.Hi--;
515 }
516 }
517 }
518
519 /* Return only what was requested */
520
521 if (OutQuotient)
522 {
523 *OutQuotient = Quotient.Full;
524 }
525 if (OutRemainder)
526 {
527 *OutRemainder = Remainder.Full;
528 }
529
530 return_ACPI_STATUS (AE_OK);
531 }
532
533 #else
534
535 /*******************************************************************************
536 *
537 * FUNCTION: AcpiUtShortDivide, AcpiUtDivide
538 *
539 * PARAMETERS: See function headers above
540 *
541 * DESCRIPTION: Native versions of the UtDivide functions. Use these if either
542 * 1) The target is a 64-bit platform and therefore 64-bit
543 * integer math is supported directly by the machine.
544 * 2) The target is a 32-bit or 16-bit platform, and the
545 * double-precision integer math library is available to
546 * perform the divide.
547 *
548 ******************************************************************************/
549
550 ACPI_STATUS
551 AcpiUtShortDivide (
552 UINT64 InDividend,
553 UINT32 Divisor,
554 UINT64 *OutQuotient,
555 UINT32 *OutRemainder)
556 {
557
558 ACPI_FUNCTION_TRACE (UtShortDivide);
559
560
561 /* Always check for a zero divisor */
562
563 if (Divisor == 0)
564 {
565 ACPI_ERROR ((AE_INFO, "Divide by zero"));
566 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
567 }
568
569 /* Return only what was requested */
570
571 if (OutQuotient)
572 {
573 *OutQuotient = InDividend / Divisor;
574 }
575 if (OutRemainder)
576 {
577 *OutRemainder = (UINT32) (InDividend % Divisor);
578 }
579
580 return_ACPI_STATUS (AE_OK);
581 }
582
583 ACPI_STATUS
584 AcpiUtDivide (
585 UINT64 InDividend,
586 UINT64 InDivisor,
587 UINT64 *OutQuotient,
588 UINT64 *OutRemainder)
589 {
590 ACPI_FUNCTION_TRACE (UtDivide);
591
592
593 /* Always check for a zero divisor */
594
595 if (InDivisor == 0)
596 {
597 ACPI_ERROR ((AE_INFO, "Divide by zero"));
598 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
599 }
600
601
602 /* Return only what was requested */
603
604 if (OutQuotient)
605 {
606 *OutQuotient = InDividend / InDivisor;
607 }
608 if (OutRemainder)
609 {
610 *OutRemainder = InDividend % InDivisor;
611 }
612
613 return_ACPI_STATUS (AE_OK);
614 }
615
616 #endif