Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /******************************************************************************* |
| 2 | * |
| 3 | * Module Name: utmath - Integer math support routines |
| 4 | * |
| 5 | ******************************************************************************/ |
| 6 | |
| 7 | /* |
Bob Moore | fbb7a2d | 2014-02-08 09:42:25 +0800 | [diff] [blame] | 8 | * Copyright (C) 2000 - 2014, Intel Corp. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 44 | #include <acpi/acpi.h> |
Len Brown | e2f7a77 | 2009-01-09 00:30:03 -0500 | [diff] [blame] | 45 | #include "accommon.h" |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 46 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 47 | #define _COMPONENT ACPI_UTILITIES |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 48 | ACPI_MODULE_NAME("utmath") |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 49 | |
| 50 | /* |
Bob Moore | e786db7 | 2010-09-15 14:00:53 +0800 | [diff] [blame] | 51 | * Optional support for 64-bit double-precision integer divide. This code |
| 52 | * is configurable and is implemented in order to support 32-bit kernel |
| 53 | * environments where a 64-bit double-precision math library is not available. |
| 54 | * |
| 55 | * Support for a more normal 64-bit divide/modulo (with check for a divide- |
| 56 | * by-zero) appears after this optional section of code. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 57 | */ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 58 | #ifndef ACPI_USE_NATIVE_DIVIDE |
Bob Moore | e786db7 | 2010-09-15 14:00:53 +0800 | [diff] [blame] | 59 | /* Structures used only for 64-bit divide */ |
| 60 | typedef struct uint64_struct { |
| 61 | u32 lo; |
| 62 | u32 hi; |
| 63 | |
| 64 | } uint64_struct; |
| 65 | |
| 66 | typedef union uint64_overlay { |
| 67 | u64 full; |
| 68 | struct uint64_struct part; |
| 69 | |
| 70 | } uint64_overlay; |
| 71 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 72 | /******************************************************************************* |
| 73 | * |
| 74 | * FUNCTION: acpi_ut_short_divide |
| 75 | * |
Bob Moore | ba494be | 2012-07-12 09:40:10 +0800 | [diff] [blame] | 76 | * PARAMETERS: dividend - 64-bit dividend |
| 77 | * divisor - 32-bit divisor |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 78 | * out_quotient - Pointer to where the quotient is returned |
| 79 | * out_remainder - Pointer to where the remainder is returned |
| 80 | * |
| 81 | * RETURN: Status (Checks for divide-by-zero) |
| 82 | * |
| 83 | * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) |
Bob Moore | 73a3090 | 2012-10-31 02:26:55 +0000 | [diff] [blame] | 84 | * divide and modulo. The result is a 64-bit quotient and a |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 85 | * 32-bit remainder. |
| 86 | * |
| 87 | ******************************************************************************/ |
Bob Moore | e786db7 | 2010-09-15 14:00:53 +0800 | [diff] [blame] | 88 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 89 | acpi_status |
Bob Moore | 5df7e6c | 2010-01-21 10:06:32 +0800 | [diff] [blame] | 90 | acpi_ut_short_divide(u64 dividend, |
| 91 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 92 | { |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 93 | union uint64_overlay dividend_ovl; |
| 94 | union uint64_overlay quotient; |
| 95 | u32 remainder32; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 96 | |
Bob Moore | b229cf9 | 2006-04-21 17:15:00 -0400 | [diff] [blame] | 97 | ACPI_FUNCTION_TRACE(ut_short_divide); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 98 | |
| 99 | /* Always check for a zero divisor */ |
| 100 | |
| 101 | if (divisor == 0) { |
Bob Moore | b8e4d89 | 2006-01-27 16:43:00 -0500 | [diff] [blame] | 102 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 103 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 104 | } |
| 105 | |
| 106 | dividend_ovl.full = dividend; |
| 107 | |
| 108 | /* |
| 109 | * The quotient is 64 bits, the remainder is always 32 bits, |
| 110 | * and is generated by the second divide. |
| 111 | */ |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 112 | ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 113 | quotient.part.hi, remainder32); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 114 | ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 115 | quotient.part.lo, remainder32); |
| 116 | |
| 117 | /* Return only what was requested */ |
| 118 | |
| 119 | if (out_quotient) { |
| 120 | *out_quotient = quotient.full; |
| 121 | } |
| 122 | if (out_remainder) { |
| 123 | *out_remainder = remainder32; |
| 124 | } |
| 125 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 126 | return_ACPI_STATUS(AE_OK); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 127 | } |
| 128 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 129 | /******************************************************************************* |
| 130 | * |
| 131 | * FUNCTION: acpi_ut_divide |
| 132 | * |
| 133 | * PARAMETERS: in_dividend - Dividend |
| 134 | * in_divisor - Divisor |
| 135 | * out_quotient - Pointer to where the quotient is returned |
| 136 | * out_remainder - Pointer to where the remainder is returned |
| 137 | * |
| 138 | * RETURN: Status (Checks for divide-by-zero) |
| 139 | * |
| 140 | * DESCRIPTION: Perform a divide and modulo. |
| 141 | * |
| 142 | ******************************************************************************/ |
| 143 | |
| 144 | acpi_status |
Bob Moore | 5df7e6c | 2010-01-21 10:06:32 +0800 | [diff] [blame] | 145 | acpi_ut_divide(u64 in_dividend, |
| 146 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 147 | { |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 148 | union uint64_overlay dividend; |
| 149 | union uint64_overlay divisor; |
| 150 | union uint64_overlay quotient; |
| 151 | union uint64_overlay remainder; |
| 152 | union uint64_overlay normalized_dividend; |
| 153 | union uint64_overlay normalized_divisor; |
| 154 | u32 partial1; |
| 155 | union uint64_overlay partial2; |
| 156 | union uint64_overlay partial3; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 157 | |
Bob Moore | b229cf9 | 2006-04-21 17:15:00 -0400 | [diff] [blame] | 158 | ACPI_FUNCTION_TRACE(ut_divide); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 159 | |
| 160 | /* Always check for a zero divisor */ |
| 161 | |
| 162 | if (in_divisor == 0) { |
Bob Moore | b8e4d89 | 2006-01-27 16:43:00 -0500 | [diff] [blame] | 163 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 164 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 165 | } |
| 166 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 167 | divisor.full = in_divisor; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 168 | dividend.full = in_dividend; |
| 169 | if (divisor.part.hi == 0) { |
| 170 | /* |
| 171 | * 1) Simplest case is where the divisor is 32 bits, we can |
| 172 | * just do two divides |
| 173 | */ |
| 174 | remainder.part.hi = 0; |
| 175 | |
| 176 | /* |
| 177 | * The quotient is 64 bits, the remainder is always 32 bits, |
| 178 | * and is generated by the second divide. |
| 179 | */ |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 180 | ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 181 | quotient.part.hi, partial1); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 182 | ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 183 | quotient.part.lo, remainder.part.lo); |
| 184 | } |
| 185 | |
| 186 | else { |
| 187 | /* |
| 188 | * 2) The general case where the divisor is a full 64 bits |
| 189 | * is more difficult |
| 190 | */ |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 191 | quotient.part.hi = 0; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 192 | normalized_dividend = dividend; |
| 193 | normalized_divisor = divisor; |
| 194 | |
| 195 | /* Normalize the operands (shift until the divisor is < 32 bits) */ |
| 196 | |
| 197 | do { |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 198 | ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi, |
| 199 | normalized_divisor.part.lo); |
| 200 | ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi, |
| 201 | normalized_dividend.part.lo); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 202 | |
| 203 | } while (normalized_divisor.part.hi != 0); |
| 204 | |
| 205 | /* Partial divide */ |
| 206 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 207 | ACPI_DIV_64_BY_32(normalized_dividend.part.hi, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 208 | normalized_dividend.part.lo, |
| 209 | normalized_divisor.part.lo, |
| 210 | quotient.part.lo, partial1); |
| 211 | |
| 212 | /* |
| 213 | * The quotient is always 32 bits, and simply requires adjustment. |
| 214 | * The 64-bit remainder must be generated. |
| 215 | */ |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 216 | partial1 = quotient.part.lo * divisor.part.hi; |
Bob Moore | 5df7e6c | 2010-01-21 10:06:32 +0800 | [diff] [blame] | 217 | partial2.full = (u64) quotient.part.lo * divisor.part.lo; |
| 218 | partial3.full = (u64) partial2.part.hi + partial1; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 219 | |
| 220 | remainder.part.hi = partial3.part.lo; |
| 221 | remainder.part.lo = partial2.part.lo; |
| 222 | |
| 223 | if (partial3.part.hi == 0) { |
| 224 | if (partial3.part.lo >= dividend.part.hi) { |
| 225 | if (partial3.part.lo == dividend.part.hi) { |
| 226 | if (partial2.part.lo > dividend.part.lo) { |
| 227 | quotient.part.lo--; |
| 228 | remainder.full -= divisor.full; |
| 229 | } |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 230 | } else { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 231 | quotient.part.lo--; |
| 232 | remainder.full -= divisor.full; |
| 233 | } |
| 234 | } |
| 235 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 236 | remainder.full = remainder.full - dividend.full; |
| 237 | remainder.part.hi = (u32) - ((s32) remainder.part.hi); |
| 238 | remainder.part.lo = (u32) - ((s32) remainder.part.lo); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 239 | |
| 240 | if (remainder.part.lo) { |
| 241 | remainder.part.hi--; |
| 242 | } |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | /* Return only what was requested */ |
| 247 | |
| 248 | if (out_quotient) { |
| 249 | *out_quotient = quotient.full; |
| 250 | } |
| 251 | if (out_remainder) { |
| 252 | *out_remainder = remainder.full; |
| 253 | } |
| 254 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 255 | return_ACPI_STATUS(AE_OK); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 256 | } |
| 257 | |
| 258 | #else |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 259 | /******************************************************************************* |
| 260 | * |
| 261 | * FUNCTION: acpi_ut_short_divide, acpi_ut_divide |
| 262 | * |
Robert Moore | 44f6c01 | 2005-04-18 22:49:35 -0400 | [diff] [blame] | 263 | * PARAMETERS: See function headers above |
| 264 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 265 | * DESCRIPTION: Native versions of the ut_divide functions. Use these if either |
| 266 | * 1) The target is a 64-bit platform and therefore 64-bit |
| 267 | * integer math is supported directly by the machine. |
| 268 | * 2) The target is a 32-bit or 16-bit platform, and the |
| 269 | * double-precision integer math library is available to |
| 270 | * perform the divide. |
| 271 | * |
| 272 | ******************************************************************************/ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 273 | acpi_status |
Bob Moore | 5df7e6c | 2010-01-21 10:06:32 +0800 | [diff] [blame] | 274 | acpi_ut_short_divide(u64 in_dividend, |
| 275 | u32 divisor, u64 *out_quotient, u32 *out_remainder) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 276 | { |
| 277 | |
Bob Moore | b229cf9 | 2006-04-21 17:15:00 -0400 | [diff] [blame] | 278 | ACPI_FUNCTION_TRACE(ut_short_divide); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 279 | |
| 280 | /* Always check for a zero divisor */ |
| 281 | |
| 282 | if (divisor == 0) { |
Bob Moore | b8e4d89 | 2006-01-27 16:43:00 -0500 | [diff] [blame] | 283 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 284 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 285 | } |
| 286 | |
| 287 | /* Return only what was requested */ |
| 288 | |
| 289 | if (out_quotient) { |
| 290 | *out_quotient = in_dividend / divisor; |
| 291 | } |
| 292 | if (out_remainder) { |
Bob Moore | 1f549a2 | 2008-04-10 19:06:40 +0400 | [diff] [blame] | 293 | *out_remainder = (u32) (in_dividend % divisor); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 294 | } |
| 295 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 296 | return_ACPI_STATUS(AE_OK); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 297 | } |
| 298 | |
| 299 | acpi_status |
Bob Moore | 5df7e6c | 2010-01-21 10:06:32 +0800 | [diff] [blame] | 300 | acpi_ut_divide(u64 in_dividend, |
| 301 | u64 in_divisor, u64 *out_quotient, u64 *out_remainder) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 302 | { |
Bob Moore | b229cf9 | 2006-04-21 17:15:00 -0400 | [diff] [blame] | 303 | ACPI_FUNCTION_TRACE(ut_divide); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 304 | |
| 305 | /* Always check for a zero divisor */ |
| 306 | |
| 307 | if (in_divisor == 0) { |
Bob Moore | b8e4d89 | 2006-01-27 16:43:00 -0500 | [diff] [blame] | 308 | ACPI_ERROR((AE_INFO, "Divide by zero")); |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 309 | return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 310 | } |
| 311 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 312 | /* Return only what was requested */ |
| 313 | |
| 314 | if (out_quotient) { |
| 315 | *out_quotient = in_dividend / in_divisor; |
| 316 | } |
| 317 | if (out_remainder) { |
| 318 | *out_remainder = in_dividend % in_divisor; |
| 319 | } |
| 320 | |
Len Brown | 4be44fc | 2005-08-05 00:44:28 -0400 | [diff] [blame] | 321 | return_ACPI_STATUS(AE_OK); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 322 | } |
| 323 | |
| 324 | #endif |