1 /******************************************************************************* 2 * 3 * Module Name: utmath - Integer math support routines 4 * $Revision: 1.21 $ 5 * 6 ******************************************************************************/ 7 8 /****************************************************************************** 9 * 10 * 1. Copyright Notice 11 * 12 * Some or all of this work - Copyright (c) 1999 - 2006, Intel Corp. 13 * All rights reserved. 14 * 15 * 2. License 16 * 17 * 2.1. This is your license from Intel Corp. under its intellectual property 18 * rights. You may have additional license terms from the party that provided 19 * you this software, covering your right to use that party's intellectual 20 * property rights. 21 * 22 * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a 23 * copy of the source code appearing in this file ("Covered Code") an 24 * 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 ACPI_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: Dividend - 64-bit 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 150 ACPI_STATUS 151 AcpiUtShortDivide ( 152 ACPI_INTEGER Dividend, 153 UINT32 Divisor, 154 ACPI_INTEGER *OutQuotient, 155 UINT32 *OutRemainder) 156 { 157 UINT64_OVERLAY DividendOvl; 158 UINT64_OVERLAY Quotient; 159 UINT32 Remainder32; 160 161 162 ACPI_FUNCTION_TRACE (UtShortDivide); 163 164 165 /* Always check for a zero divisor */ 166 167 if (Divisor == 0) 168 { 169 ACPI_ERROR ((AE_INFO, "Divide by zero")); 170 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 171 } 172 173 DividendOvl.Full = Dividend; 174 175 /* 176 * The quotient is 64 bits, the remainder is always 32 bits, 177 * and is generated by the second divide. 178 */ 179 ACPI_DIV_64_BY_32 (0, DividendOvl.Part.Hi, Divisor, 180 Quotient.Part.Hi, Remainder32); 181 ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor, 182 Quotient.Part.Lo, Remainder32); 183 184 /* Return only what was requested */ 185 186 if (OutQuotient) 187 { 188 *OutQuotient = Quotient.Full; 189 } 190 if (OutRemainder) 191 { 192 *OutRemainder = Remainder32; 193 } 194 195 return_ACPI_STATUS (AE_OK); 196 } 197 198 199 /******************************************************************************* 200 * 201 * FUNCTION: AcpiUtDivide 202 * 203 * PARAMETERS: InDividend - Dividend 204 * InDivisor - Divisor 205 * OutQuotient - Pointer to where the quotient is returned 206 * OutRemainder - Pointer to where the remainder is returned 207 * 208 * RETURN: Status (Checks for divide-by-zero) 209 * 210 * DESCRIPTION: Perform a divide and modulo. 211 * 212 ******************************************************************************/ 213 214 ACPI_STATUS 215 AcpiUtDivide ( 216 ACPI_INTEGER InDividend, 217 ACPI_INTEGER InDivisor, 218 ACPI_INTEGER *OutQuotient, 219 ACPI_INTEGER *OutRemainder) 220 { 221 UINT64_OVERLAY Dividend; 222 UINT64_OVERLAY Divisor; 223 UINT64_OVERLAY Quotient; 224 UINT64_OVERLAY Remainder; 225 UINT64_OVERLAY NormalizedDividend; 226 UINT64_OVERLAY NormalizedDivisor; 227 UINT32 Partial1; 228 UINT64_OVERLAY Partial2; 229 UINT64_OVERLAY Partial3; 230 231 232 ACPI_FUNCTION_TRACE (UtDivide); 233 234 235 /* Always check for a zero divisor */ 236 237 if (InDivisor == 0) 238 { 239 ACPI_ERROR ((AE_INFO, "Divide by zero")); 240 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 241 } 242 243 Divisor.Full = InDivisor; 244 Dividend.Full = InDividend; 245 if (Divisor.Part.Hi == 0) 246 { 247 /* 248 * 1) Simplest case is where the divisor is 32 bits, we can 249 * just do two divides 250 */ 251 Remainder.Part.Hi = 0; 252 253 /* 254 * The quotient is 64 bits, the remainder is always 32 bits, 255 * and is generated by the second divide. 256 */ 257 ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo, 258 Quotient.Part.Hi, Partial1); 259 ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo, 260 Quotient.Part.Lo, Remainder.Part.Lo); 261 } 262 263 else 264 { 265 /* 266 * 2) The general case where the divisor is a full 64 bits 267 * is more difficult 268 */ 269 Quotient.Part.Hi = 0; 270 NormalizedDividend = Dividend; 271 NormalizedDivisor = Divisor; 272 273 /* Normalize the operands (shift until the divisor is < 32 bits) */ 274 275 do 276 { 277 ACPI_SHIFT_RIGHT_64 (NormalizedDivisor.Part.Hi, 278 NormalizedDivisor.Part.Lo); 279 ACPI_SHIFT_RIGHT_64 (NormalizedDividend.Part.Hi, 280 NormalizedDividend.Part.Lo); 281 282 } while (NormalizedDivisor.Part.Hi != 0); 283 284 /* Partial divide */ 285 286 ACPI_DIV_64_BY_32 (NormalizedDividend.Part.Hi, 287 NormalizedDividend.Part.Lo, 288 NormalizedDivisor.Part.Lo, 289 Quotient.Part.Lo, Partial1); 290 291 /* 292 * The quotient is always 32 bits, and simply requires adjustment. 293 * The 64-bit remainder must be generated. 294 */ 295 Partial1 = Quotient.Part.Lo * Divisor.Part.Hi; 296 Partial2.Full = (ACPI_INTEGER) Quotient.Part.Lo * Divisor.Part.Lo; 297 Partial3.Full = (ACPI_INTEGER) Partial2.Part.Hi + Partial1; 298 299 Remainder.Part.Hi = Partial3.Part.Lo; 300 Remainder.Part.Lo = Partial2.Part.Lo; 301 302 if (Partial3.Part.Hi == 0) 303 { 304 if (Partial3.Part.Lo >= Dividend.Part.Hi) 305 { 306 if (Partial3.Part.Lo == Dividend.Part.Hi) 307 { 308 if (Partial2.Part.Lo > Dividend.Part.Lo) 309 { 310 Quotient.Part.Lo--; 311 Remainder.Full -= Divisor.Full; 312 } 313 } 314 else 315 { 316 Quotient.Part.Lo--; 317 Remainder.Full -= Divisor.Full; 318 } 319 } 320 321 Remainder.Full = Remainder.Full - Dividend.Full; 322 Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi); 323 Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo); 324 325 if (Remainder.Part.Lo) 326 { 327 Remainder.Part.Hi--; 328 } 329 } 330 } 331 332 /* Return only what was requested */ 333 334 if (OutQuotient) 335 { 336 *OutQuotient = Quotient.Full; 337 } 338 if (OutRemainder) 339 { 340 *OutRemainder = Remainder.Full; 341 } 342 343 return_ACPI_STATUS (AE_OK); 344 } 345 346 #else 347 348 /******************************************************************************* 349 * 350 * FUNCTION: AcpiUtShortDivide, AcpiUtDivide 351 * 352 * PARAMETERS: See function headers above 353 * 354 * DESCRIPTION: Native versions of the UtDivide functions. Use these if either 355 * 1) The target is a 64-bit platform and therefore 64-bit 356 * integer math is supported directly by the machine. 357 * 2) The target is a 32-bit or 16-bit platform, and the 358 * double-precision integer math library is available to 359 * perform the divide. 360 * 361 ******************************************************************************/ 362 363 ACPI_STATUS 364 AcpiUtShortDivide ( 365 ACPI_INTEGER InDividend, 366 UINT32 Divisor, 367 ACPI_INTEGER *OutQuotient, 368 UINT32 *OutRemainder) 369 { 370 371 ACPI_FUNCTION_TRACE (UtShortDivide); 372 373 374 /* Always check for a zero divisor */ 375 376 if (Divisor == 0) 377 { 378 ACPI_ERROR ((AE_INFO, "Divide by zero")); 379 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 380 } 381 382 /* Return only what was requested */ 383 384 if (OutQuotient) 385 { 386 *OutQuotient = InDividend / Divisor; 387 } 388 if (OutRemainder) 389 { 390 *OutRemainder = (UINT32) InDividend % Divisor; 391 } 392 393 return_ACPI_STATUS (AE_OK); 394 } 395 396 ACPI_STATUS 397 AcpiUtDivide ( 398 ACPI_INTEGER InDividend, 399 ACPI_INTEGER InDivisor, 400 ACPI_INTEGER *OutQuotient, 401 ACPI_INTEGER *OutRemainder) 402 { 403 ACPI_FUNCTION_TRACE (UtDivide); 404 405 406 /* Always check for a zero divisor */ 407 408 if (InDivisor == 0) 409 { 410 ACPI_ERROR ((AE_INFO, "Divide by zero")); 411 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 412 } 413 414 415 /* Return only what was requested */ 416 417 if (OutQuotient) 418 { 419 *OutQuotient = InDividend / InDivisor; 420 } 421 if (OutRemainder) 422 { 423 *OutRemainder = InDividend % InDivisor; 424 } 425 426 return_ACPI_STATUS (AE_OK); 427 } 428 429 #endif 430 431 432