ReactOS  0.4.14-dev-358-gbef841c
utmath.c
Go to the documentation of this file.
1 /*******************************************************************************
2  *
3  * Module Name: utmath - Integer math support routines
4  *
5  ******************************************************************************/
6 
7 /*
8  * Copyright (C) 2000 - 2019, 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 
54 {
57 
59 
60 typedef union uint64_overlay
61 {
64 
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 
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 
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 
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 = 0;
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 
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 
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 = 0;
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 
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 
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 
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 
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 
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 
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 
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 
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"));
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 
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 
403  UINT64 InDividend,
404  UINT64 InDivisor,
405  UINT64 *OutQuotient,
406  UINT64 *OutRemainder)
407 {
408  UINT64_OVERLAY Dividend;
410  UINT64_OVERLAY Quotient;
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"));
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  {
466  NormalizedDivisor.Part.Hi, NormalizedDivisor.Part.Lo);
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 
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 
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"));
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 
581 }
582 
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"));
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 
614 }
615 
616 #endif
union uint64_overlay UINT64_OVERLAY
ACPI_STATUS AcpiUtShortDivide(UINT64 Dividend, UINT32 Divisor, UINT64 *OutQuotient, UINT32 *OutRemainder)
Definition: utmath.c:337
struct uint64_struct UINT64_STRUCT
UINT64_STRUCT Part
Definition: utmath.c:63
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
ACPI_STATUS AcpiUtDivide(UINT64 InDividend, UINT64 InDivisor, UINT64 *OutQuotient, UINT64 *OutRemainder)
Definition: utmath.c:402
UINT32 ACPI_STATUS
Definition: actypes.h:460
#define ACPI_SHIFT_RIGHT_64(n_hi, n_lo)
Definition: acos2.h:84
ACPI_STATUS AcpiUtShortShiftRight(UINT64 Operand, UINT32 Count, UINT64 *OutResult)
Definition: utmath.c:184
ACPI_STATUS AcpiUtShortShiftLeft(UINT64 Operand, UINT32 Count, UINT64 *OutResult)
Definition: utmath.c:139
unsigned int UINT32
#define ACPI_MODULE_NAME(Name)
Definition: acoutput.h:216
#define AE_INFO
Definition: acoutput.h:230
ACPI_STATUS AcpiUtShortMultiply(UINT64 Multiplicand, UINT32 Multiplier, UINT64 *OutProduct)
Definition: utmath.c:88
UINT64 Full
Definition: utmath.c:62
UINT32 Hi
Definition: utmath.c:56
UINT32 Lo
Definition: utmath.c:55
#define return_ACPI_STATUS(s)
Definition: acoutput.h:496
#define ACPI_FUNCTION_TRACE(a)
Definition: acoutput.h:480
#define ACPI_ERROR(plist)
Definition: acoutput.h:240
_In_ LARGE_INTEGER Divisor
Definition: rtlfuncs.h:3046
signed int INT32
unsigned long long UINT64
#define AE_AML_DIVIDE_BY_ZERO
Definition: acexcep.h:191
#define AE_OK
Definition: acexcep.h:97
_In_ LARGE_INTEGER _Out_opt_ PLARGE_INTEGER Remainder
Definition: rtlfuncs.h:3046