utmath.c revision 87031 
150477Speter/*******************************************************************************
250120Swpaul *
370711Sobrien * Module Name: utmath - Integer math support routines
450120Swpaul *              $Revision: 8 $
570711Sobrien *
6190558Simp ******************************************************************************/
7190558Simp
8226995Smarius/******************************************************************************
9226995Smarius *
10175702Smarius * 1. Copyright Notice
11239275Sgonzo *
12239275Sgonzo * Some or all of this work - Copyright (c) 1999, 2000, 2001, Intel Corp.
13216828Syongari * All rights reserved.
14175701Smarius *
1570711Sobrien * 2. License
16213878Smarius *
17226995Smarius * 2.1. This is your license from Intel Corp. under its intellectual property
18226995Smarius * rights.  You may have additional license terms from the party that provided
19226995Smarius * you this software, covering your right to use that party's intellectual
20213878Smarius * property rights.
2189244Smsmith *
22175701Smarius * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a
2389244Smsmith * copy of the source code appearing in this file ("Covered Code") an
2460966Speter * irrevocable, perpetual, worldwide license under Intel's copyrights in the
25 * base code distributed originally by Intel ("Original Intel Code") to copy,
26 * make derivatives, distribute, use and display any portion of the Covered
27 * Code in any form, with the right to sublicense such rights; and
28 *
29 * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent
30 * license (with the right to sublicense), under only those claims of Intel
31 * patents that are infringed by the Original Intel Code, to make, use, sell,
32 * offer to sell, and import the Covered Code and derivative works thereof
33 * solely to the minimum extent necessary to exercise the above copyright
34 * license, and in no event shall the patent license extend to any additions
35 * to or modifications of the Original Intel Code.  No other license or right
36 * is granted directly or by implication, estoppel or otherwise;
37 *
38 * The above copyright and patent license is granted only if the following
39 * conditions are met:
40 *
41 * 3. Conditions
42 *
43 * 3.1. Redistribution of Source with Rights to Further Distribute Source.
44 * Redistribution of source code of any substantial portion of the Covered
45 * Code or modification with rights to further distribute source must include
46 * the above Copyright Notice, the above License, this list of Conditions,
47 * and the following Disclaimer and Export Compliance provision.  In addition,
48 * Licensee must cause all Covered Code to which Licensee contributes to
49 * contain a file documenting the changes Licensee made to create that Covered
50 * Code and the date of any change.  Licensee must include in that file the
51 * documentation of any changes made by any predecessor Licensee.  Licensee
52 * must include a prominent statement that the modification is derived,
53 * directly or indirectly, from Original Intel Code.
54 *
55 * 3.2. Redistribution of Source with no Rights to Further Distribute Source.
56 * Redistribution of source code of any substantial portion of the Covered
57 * Code or modification without rights to further distribute source must
58 * include the following Disclaimer and Export Compliance provision in the
59 * documentation and/or other materials provided with distribution.  In
60 * addition, Licensee may not authorize further sublicense of source of any
61 * portion of the Covered Code, and must include terms to the effect that the
62 * license from Licensee to its licensee is limited to the intellectual
63 * property embodied in the software Licensee provides to its licensee, and
64 * not to intellectual property embodied in modifications its licensee may
65 * make.
66 *
67 * 3.3. Redistribution of Executable. Redistribution in executable form of any
68 * substantial portion of the Covered Code or modification must reproduce the
69 * above Copyright Notice, and the following Disclaimer and Export Compliance
70 * provision in the documentation and/or other materials provided with the
71 * distribution.
72 *
73 * 3.4. Intel retains all right, title, and interest in and to the Original
74 * Intel Code.
75 *
76 * 3.5. Neither the name Intel nor any other trademark owned or controlled by
77 * Intel shall be used in advertising or otherwise to promote the sale, use or
78 * other dealings in products derived from or relating to the Covered Code
79 * without prior written authorization from Intel.
80 *
81 * 4. Disclaimer and Export Compliance
82 *
83 * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED
84 * HERE.  ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE
85 * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT,  ASSISTANCE,
86 * INSTALLATION, TRAINING OR OTHER SERVICES.  INTEL WILL NOT PROVIDE ANY
87 * UPDATES, ENHANCEMENTS OR EXTENSIONS.  INTEL SPECIFICALLY DISCLAIMS ANY
88 * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A
89 * PARTICULAR PURPOSE.
90 *
91 * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES
92 * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR
93 * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT,
94 * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY
95 * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL
96 * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.  THESE LIMITATIONS
97 * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY
98 * LIMITED REMEDY.
99 *
100 * 4.3. Licensee shall not export, either directly or indirectly, any of this
101 * software or system incorporating such software without first obtaining any
102 * required license or other approval from the U. S. Department of Commerce or
103 * any other agency or department of the United States Government.  In the
104 * event Licensee exports any such software from the United States or
105 * re-exports any such software from a foreign destination, Licensee shall
106 * ensure that the distribution and export/re-export of the software is in
107 * compliance with all laws, regulations, orders, or other restrictions of the
108 * U.S. Export Administration Regulations. Licensee agrees that neither it nor
109 * any of its subsidiaries will export/re-export any technical data, process,
110 * software, or service, directly or indirectly, to any country for which the
111 * United States government or any agency thereof requires an export license,
112 * other governmental approval, or letter of assurance, without first obtaining
113 * such license, approval or letter.
114 *
115 *****************************************************************************/
116
117
118#define __UTMATH_C__
119
120#include "acpi.h"
121
122
123#define _COMPONENT          ACPI_UTILITIES
124        MODULE_NAME         ("utmath")
125
126/*
127 * Support for double-precision integer divide.  This code is included here
128 * in order to support kernel environments where the double-precision math
129 * library is not available.
130 */
131
132#ifndef ACPI_USE_NATIVE_DIVIDE
133/*******************************************************************************
134 *
135 * FUNCTION:    AcpiUtShortDivide
136 *
137 * PARAMETERS:  InDividend          - Pointer to the dividend
138 *              Divisor             - 32-bit divisor
139 *              OutQuotient         - Pointer to where the quotient is returned
140 *              OutRemainder        - Pointer to where the remainder is returned
141 *
142 * RETURN:      Status (Checks for divide-by-zero)
143 *
144 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
145 *              divide and modulo.  The result is a 64-bit quotient and a
146 *              32-bit remainder.
147 *
148 ******************************************************************************/
149
150ACPI_STATUS
151AcpiUtShortDivide (
152    ACPI_INTEGER            *InDividend,
153    UINT32                  Divisor,
154    ACPI_INTEGER            *OutQuotient,
155    UINT32                  *OutRemainder)
156{
157    UINT64_OVERLAY          Dividend;
158    UINT64_OVERLAY          Quotient;
159    UINT32                  Remainder32;
160
161
162    FUNCTION_TRACE ("UtShortDivide");
163
164    Dividend.Full = *InDividend;
165
166    /* Always check for a zero divisor */
167
168    if (Divisor == 0)
169    {
170        REPORT_ERROR (("AcpiUtShortDivide: Divide by zero\n"));
171        return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
172    }
173
174    /*
175     * The quotient is 64 bits, the remainder is always 32 bits,
176     * and is generated by the second divide.
177     */
178    ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor,
179                       Quotient.Part.Hi, Remainder32);
180    ACPI_DIV_64_BY_32 (Remainder32, Dividend.Part.Lo,  Divisor,
181                       Quotient.Part.Lo, Remainder32);
182
183    /* Return only what was requested */
184
185    if (OutQuotient)
186    {
187        *OutQuotient = Quotient.Full;
188    }
189    if (OutRemainder)
190    {
191        *OutRemainder = Remainder32;
192    }
193
194    return_ACPI_STATUS (AE_OK);
195}
196
197
198/*******************************************************************************
199 *
200 * FUNCTION:    AcpiUtDivide
201 *
202 * PARAMETERS:  InDividend          - Pointer to the dividend
203 *              InDivisor           - Pointer to the divisor
204 *              OutQuotient         - Pointer to where the quotient is returned
205 *              OutRemainder        - Pointer to where the remainder is returned
206 *
207 * RETURN:      Status (Checks for divide-by-zero)
208 *
209 * DESCRIPTION: Perform a divide and modulo.
210 *
211 ******************************************************************************/
212
213ACPI_STATUS
214AcpiUtDivide (
215    ACPI_INTEGER            *InDividend,
216    ACPI_INTEGER            *InDivisor,
217    ACPI_INTEGER            *OutQuotient,
218    ACPI_INTEGER            *OutRemainder)
219{
220    UINT64_OVERLAY          Dividend;
221    UINT64_OVERLAY          Divisor;
222    UINT64_OVERLAY          Quotient;
223    UINT64_OVERLAY          Remainder;
224    UINT64_OVERLAY          NormalizedDividend;
225    UINT64_OVERLAY          NormalizedDivisor;
226    UINT32                  Partial1;
227    UINT64_OVERLAY          Partial2;
228    UINT64_OVERLAY          Partial3;
229
230
231    FUNCTION_TRACE ("UtDivide");
232
233
234    /* Always check for a zero divisor */
235
236    if (*InDivisor == 0)
237    {
238        REPORT_ERROR (("AcpiUtDivide: Divide by zero\n"));
239        return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
240    }
241
242    Divisor.Full  = *InDivisor;
243    Dividend.Full = *InDividend;
244    if (Divisor.Part.Hi == 0)
245    {
246        /*
247         * 1) Simplest case is where the divisor is 32 bits, we can
248         * just do two divides
249         */
250        Remainder.Part.Hi = 0;
251
252        /*
253         * The quotient is 64 bits, the remainder is always 32 bits,
254         * and is generated by the second divide.
255         */
256        ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo,
257                           Quotient.Part.Hi, Partial1);
258        ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo,
259                           Quotient.Part.Lo, Remainder.Part.Lo);
260    }
261
262    else
263    {
264        /*
265         * 2) The general case where the divisor is a full 64 bits
266         * is more difficult
267         */
268        Quotient.Part.Hi   = 0;
269        NormalizedDividend = Dividend;
270        NormalizedDivisor  = Divisor;
271
272        /* Normalize the operands (shift until the divisor is < 32 bits) */
273
274        do
275        {
276            ACPI_SHIFT_RIGHT_64 (NormalizedDivisor.Part.Hi,
277                                 NormalizedDivisor.Part.Lo);
278            ACPI_SHIFT_RIGHT_64 (NormalizedDividend.Part.Hi,
279                                 NormalizedDividend.Part.Lo);
280
281        } while (NormalizedDivisor.Part.Hi != 0);
282
283        /* Partial divide */
284
285        ACPI_DIV_64_BY_32 (NormalizedDividend.Part.Hi,
286                           NormalizedDividend.Part.Lo,
287                           NormalizedDivisor.Part.Lo,
288                           Quotient.Part.Lo, Partial1);
289
290        /*
291         * The quotient is always 32 bits, and simply requires adjustment.
292         * The 64-bit remainder must be generated.
293         */
294        Partial1      = Quotient.Part.Lo * Divisor.Part.Hi;
295        Partial2.Full = (ACPI_INTEGER) Quotient.Part.Lo * Divisor.Part.Lo;
296        Partial3.Full = Partial2.Part.Hi + Partial1;
297
298        Remainder.Part.Hi = Partial3.Part.Lo;
299        Remainder.Part.Lo = Partial2.Part.Lo;
300
301        if (Partial3.Part.Hi == 0)
302        {
303            if (Partial3.Part.Lo >= Dividend.Part.Hi)
304            {
305                if (Partial3.Part.Lo == Dividend.Part.Hi)
306                {
307                    if (Partial2.Part.Lo > Dividend.Part.Lo)
308                    {
309                        Quotient.Part.Lo--;
310                        Remainder.Full -= Divisor.Full;
311                    }
312                }
313                else
314                {
315                    Quotient.Part.Lo--;
316                    Remainder.Full -= Divisor.Full;
317                }
318            }
319
320            Remainder.Full    = Remainder.Full - Dividend.Full;
321            Remainder.Part.Hi = -((INT32) Remainder.Part.Hi);
322            Remainder.Part.Lo = -((INT32) Remainder.Part.Lo);
323
324            if (Remainder.Part.Lo)
325            {
326                Remainder.Part.Hi--;
327            }
328        }
329    }
330
331    /* Return only what was requested */
332
333    if (OutQuotient)
334    {
335        *OutQuotient = Quotient.Full;
336    }
337    if (OutRemainder)
338    {
339        *OutRemainder = Remainder.Full;
340    }
341
342    return_ACPI_STATUS (AE_OK);
343}
344
345#else
346
347/*******************************************************************************
348 *
349 * FUNCTION:    AcpiUtShortDivide, AcpiUtDivide
350 *
351 * DESCRIPTION: Native versions of the UtDivide functions. Use these if either
352 *              1) The target is a 64-bit platform and therefore 64-bit
353 *                 integer math is supported directly by the machine.
354 *              2) The target is a 32-bit or 16-bit platform, and the
355 *                 double-precision integer math library is available to
356 *                 perform the divide.
357 *
358 ******************************************************************************/
359
360ACPI_STATUS
361AcpiUtShortDivide (
362    ACPI_INTEGER            *InDividend,
363    UINT32                  Divisor,
364    ACPI_INTEGER            *OutQuotient,
365    UINT32                  *OutRemainder)
366{
367
368    FUNCTION_TRACE ("UtShortDivide");
369
370
371    /* Always check for a zero divisor */
372
373    if (Divisor == 0)
374    {
375        REPORT_ERROR (("AcpiUtShortDivide: Divide by zero\n"));
376        return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
377    }
378
379    /* Return only what was requested */
380
381    if (OutQuotient)
382    {
383        *OutQuotient = *InDividend / Divisor;
384    }
385    if (OutRemainder)
386    {
387        *OutRemainder = (UINT32) *InDividend % Divisor;
388    }
389
390    return_ACPI_STATUS (AE_OK);
391}
392
393ACPI_STATUS
394AcpiUtDivide (
395    ACPI_INTEGER            *InDividend,
396    ACPI_INTEGER            *InDivisor,
397    ACPI_INTEGER            *OutQuotient,
398    ACPI_INTEGER            *OutRemainder)
399{
400    FUNCTION_TRACE ("UtDivide");
401
402
403    /* Always check for a zero divisor */
404
405    if (*InDivisor == 0)
406    {
407        REPORT_ERROR (("AcpiUtDivide: Divide by zero\n"));
408        return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
409    }
410
411
412    /* Return only what was requested */
413
414    if (OutQuotient)
415    {
416        *OutQuotient = *InDividend / *InDivisor;
417    }
418    if (OutRemainder)
419    {
420        *OutRemainder = *InDividend % *InDivisor;
421    }
422
423    return_ACPI_STATUS (AE_OK);
424}
425
426#endif
427
428
429