Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
[linux-2.6] / drivers / acpi / utilities / utmath.c
1 /*******************************************************************************
2  *
3  * Module Name: utmath - Integer math support routines
4  *
5  ******************************************************************************/
6
7 /*
8  * Copyright (C) 2000 - 2008, 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/acpi.h>
45
46 #define _COMPONENT          ACPI_UTILITIES
47 ACPI_MODULE_NAME("utmath")
48
49 /*
50  * Support for double-precision integer divide.  This code is included here
51  * in order to support kernel environments where the double-precision math
52  * library is not available.
53  */
54 #ifndef ACPI_USE_NATIVE_DIVIDE
55 /*******************************************************************************
56  *
57  * FUNCTION:    acpi_ut_short_divide
58  *
59  * PARAMETERS:  Dividend            - 64-bit dividend
60  *              Divisor             - 32-bit divisor
61  *              out_quotient        - Pointer to where the quotient is returned
62  *              out_remainder       - Pointer to where the remainder is returned
63  *
64  * RETURN:      Status (Checks for divide-by-zero)
65  *
66  * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
67  *              divide and modulo.  The result is a 64-bit quotient and a
68  *              32-bit remainder.
69  *
70  ******************************************************************************/
71 acpi_status
72 acpi_ut_short_divide(acpi_integer dividend,
73                      u32 divisor,
74                      acpi_integer * out_quotient, u32 * out_remainder)
75 {
76         union uint64_overlay dividend_ovl;
77         union uint64_overlay quotient;
78         u32 remainder32;
79
80         ACPI_FUNCTION_TRACE(ut_short_divide);
81
82         /* Always check for a zero divisor */
83
84         if (divisor == 0) {
85                 ACPI_ERROR((AE_INFO, "Divide by zero"));
86                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
87         }
88
89         dividend_ovl.full = dividend;
90
91         /*
92          * The quotient is 64 bits, the remainder is always 32 bits,
93          * and is generated by the second divide.
94          */
95         ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor,
96                           quotient.part.hi, remainder32);
97         ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor,
98                           quotient.part.lo, remainder32);
99
100         /* Return only what was requested */
101
102         if (out_quotient) {
103                 *out_quotient = quotient.full;
104         }
105         if (out_remainder) {
106                 *out_remainder = remainder32;
107         }
108
109         return_ACPI_STATUS(AE_OK);
110 }
111
112 /*******************************************************************************
113  *
114  * FUNCTION:    acpi_ut_divide
115  *
116  * PARAMETERS:  in_dividend         - Dividend
117  *              in_divisor          - Divisor
118  *              out_quotient        - Pointer to where the quotient is returned
119  *              out_remainder       - Pointer to where the remainder is returned
120  *
121  * RETURN:      Status (Checks for divide-by-zero)
122  *
123  * DESCRIPTION: Perform a divide and modulo.
124  *
125  ******************************************************************************/
126
127 acpi_status
128 acpi_ut_divide(acpi_integer in_dividend,
129                acpi_integer in_divisor,
130                acpi_integer * out_quotient, acpi_integer * out_remainder)
131 {
132         union uint64_overlay dividend;
133         union uint64_overlay divisor;
134         union uint64_overlay quotient;
135         union uint64_overlay remainder;
136         union uint64_overlay normalized_dividend;
137         union uint64_overlay normalized_divisor;
138         u32 partial1;
139         union uint64_overlay partial2;
140         union uint64_overlay partial3;
141
142         ACPI_FUNCTION_TRACE(ut_divide);
143
144         /* Always check for a zero divisor */
145
146         if (in_divisor == 0) {
147                 ACPI_ERROR((AE_INFO, "Divide by zero"));
148                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
149         }
150
151         divisor.full = in_divisor;
152         dividend.full = in_dividend;
153         if (divisor.part.hi == 0) {
154                 /*
155                  * 1) Simplest case is where the divisor is 32 bits, we can
156                  * just do two divides
157                  */
158                 remainder.part.hi = 0;
159
160                 /*
161                  * The quotient is 64 bits, the remainder is always 32 bits,
162                  * and is generated by the second divide.
163                  */
164                 ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo,
165                                   quotient.part.hi, partial1);
166                 ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo,
167                                   quotient.part.lo, remainder.part.lo);
168         }
169
170         else {
171                 /*
172                  * 2) The general case where the divisor is a full 64 bits
173                  * is more difficult
174                  */
175                 quotient.part.hi = 0;
176                 normalized_dividend = dividend;
177                 normalized_divisor = divisor;
178
179                 /* Normalize the operands (shift until the divisor is < 32 bits) */
180
181                 do {
182                         ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi,
183                                             normalized_divisor.part.lo);
184                         ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi,
185                                             normalized_dividend.part.lo);
186
187                 } while (normalized_divisor.part.hi != 0);
188
189                 /* Partial divide */
190
191                 ACPI_DIV_64_BY_32(normalized_dividend.part.hi,
192                                   normalized_dividend.part.lo,
193                                   normalized_divisor.part.lo,
194                                   quotient.part.lo, partial1);
195
196                 /*
197                  * The quotient is always 32 bits, and simply requires adjustment.
198                  * The 64-bit remainder must be generated.
199                  */
200                 partial1 = quotient.part.lo * divisor.part.hi;
201                 partial2.full =
202                     (acpi_integer) quotient.part.lo * divisor.part.lo;
203                 partial3.full = (acpi_integer) partial2.part.hi + partial1;
204
205                 remainder.part.hi = partial3.part.lo;
206                 remainder.part.lo = partial2.part.lo;
207
208                 if (partial3.part.hi == 0) {
209                         if (partial3.part.lo >= dividend.part.hi) {
210                                 if (partial3.part.lo == dividend.part.hi) {
211                                         if (partial2.part.lo > dividend.part.lo) {
212                                                 quotient.part.lo--;
213                                                 remainder.full -= divisor.full;
214                                         }
215                                 } else {
216                                         quotient.part.lo--;
217                                         remainder.full -= divisor.full;
218                                 }
219                         }
220
221                         remainder.full = remainder.full - dividend.full;
222                         remainder.part.hi = (u32) - ((s32) remainder.part.hi);
223                         remainder.part.lo = (u32) - ((s32) remainder.part.lo);
224
225                         if (remainder.part.lo) {
226                                 remainder.part.hi--;
227                         }
228                 }
229         }
230
231         /* Return only what was requested */
232
233         if (out_quotient) {
234                 *out_quotient = quotient.full;
235         }
236         if (out_remainder) {
237                 *out_remainder = remainder.full;
238         }
239
240         return_ACPI_STATUS(AE_OK);
241 }
242
243 #else
244 /*******************************************************************************
245  *
246  * FUNCTION:    acpi_ut_short_divide, acpi_ut_divide
247  *
248  * PARAMETERS:  See function headers above
249  *
250  * DESCRIPTION: Native versions of the ut_divide functions. Use these if either
251  *              1) The target is a 64-bit platform and therefore 64-bit
252  *                 integer math is supported directly by the machine.
253  *              2) The target is a 32-bit or 16-bit platform, and the
254  *                 double-precision integer math library is available to
255  *                 perform the divide.
256  *
257  ******************************************************************************/
258 acpi_status
259 acpi_ut_short_divide(acpi_integer in_dividend,
260                      u32 divisor,
261                      acpi_integer * out_quotient, u32 * out_remainder)
262 {
263
264         ACPI_FUNCTION_TRACE(ut_short_divide);
265
266         /* Always check for a zero divisor */
267
268         if (divisor == 0) {
269                 ACPI_ERROR((AE_INFO, "Divide by zero"));
270                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
271         }
272
273         /* Return only what was requested */
274
275         if (out_quotient) {
276                 *out_quotient = in_dividend / divisor;
277         }
278         if (out_remainder) {
279                 *out_remainder = (u32) (in_dividend % divisor);
280         }
281
282         return_ACPI_STATUS(AE_OK);
283 }
284
285 acpi_status
286 acpi_ut_divide(acpi_integer in_dividend,
287                acpi_integer in_divisor,
288                acpi_integer * out_quotient, acpi_integer * out_remainder)
289 {
290         ACPI_FUNCTION_TRACE(ut_divide);
291
292         /* Always check for a zero divisor */
293
294         if (in_divisor == 0) {
295                 ACPI_ERROR((AE_INFO, "Divide by zero"));
296                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
297         }
298
299         /* Return only what was requested */
300
301         if (out_quotient) {
302                 *out_quotient = in_dividend / in_divisor;
303         }
304         if (out_remainder) {
305                 *out_remainder = in_dividend % in_divisor;
306         }
307
308         return_ACPI_STATUS(AE_OK);
309 }
310
311 #endif