utmath.c revision 9980:13d7f3eec672
11911SN/A/******************************************************************************* 21911SN/A * 31911SN/A * Module Name: utmath - Integer math support routines 41911SN/A * 51911SN/A ******************************************************************************/ 61911SN/A 71911SN/A/****************************************************************************** 81911SN/A * 91911SN/A * 1. Copyright Notice 101911SN/A * 111911SN/A * Some or all of this work - Copyright (c) 1999 - 2009, Intel Corp. 121911SN/A * All rights reserved. 131911SN/A * 141911SN/A * 2. License 151911SN/A * 161911SN/A * 2.1. This is your license from Intel Corp. under its intellectual property 171911SN/A * rights. You may have additional license terms from the party that provided 181911SN/A * you this software, covering your right to use that party's intellectual 191911SN/A * property rights. 201911SN/A * 211911SN/A * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a 221911SN/A * copy of the source code appearing in this file ("Covered Code") an 231911SN/A * irrevocable, perpetual, worldwide license under Intel's copyrights in the 241911SN/A * base code distributed originally by Intel ("Original Intel Code") to copy, 251911SN/A * make derivatives, distribute, use and display any portion of the Covered 261911SN/A * Code in any form, with the right to sublicense such rights; and 271911SN/A * 281911SN/A * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent 2911707Stpivovarova * license (with the right to sublicense), under only those claims of Intel 3011707Stpivovarova * patents that are infringed by the Original Intel Code, to make, use, sell, 3111707Stpivovarova * offer to sell, and import the Covered Code and derivative works thereof 3211707Stpivovarova * solely to the minimum extent necessary to exercise the above copyright 3311707Stpivovarova * license, and in no event shall the patent license extend to any additions 3411707Stpivovarova * to or modifications of the Original Intel Code. No other license or right 3511707Stpivovarova * is granted directly or by implication, estoppel or otherwise; 3611707Stpivovarova * 371911SN/A * The above copyright and patent license is granted only if the following 381911SN/A * conditions are met: 391911SN/A * 401911SN/A * 3. Conditions 411911SN/A * 421911SN/A * 3.1. Redistribution of Source with Rights to Further Distribute Source. 431911SN/A * Redistribution of source code of any substantial portion of the Covered 441911SN/A * Code or modification with rights to further distribute source must include 451911SN/A * the above Copyright Notice, the above License, this list of Conditions, 461911SN/A * and the following Disclaimer and Export Compliance provision. In addition, 471911SN/A * Licensee must cause all Covered Code to which Licensee contributes to 481911SN/A * contain a file documenting the changes Licensee made to create that Covered 491911SN/A * Code and the date of any change. Licensee must include in that file the 501911SN/A * documentation of any changes made by any predecessor Licensee. Licensee 511911SN/A * must include a prominent statement that the modification is derived, 521911SN/A * directly or indirectly, from Original Intel Code. 531911SN/A * 541911SN/A * 3.2. Redistribution of Source with no Rights to Further Distribute Source. 551911SN/A * Redistribution of source code of any substantial portion of the Covered 561911SN/A * Code or modification without rights to further distribute source must 571911SN/A * include the following Disclaimer and Export Compliance provision in the 581911SN/A * documentation and/or other materials provided with distribution. In 591911SN/A * addition, Licensee may not authorize further sublicense of source of any 601911SN/A * portion of the Covered Code, and must include terms to the effect that the 611911SN/A * license from Licensee to its licensee is limited to the intellectual 621911SN/A * property embodied in the software Licensee provides to its licensee, and 63 * not to intellectual property embodied in modifications its licensee may 64 * make. 65 * 66 * 3.3. Redistribution of Executable. Redistribution in executable form of any 67 * substantial portion of the Covered Code or modification must reproduce the 68 * above Copyright Notice, and the following Disclaimer and Export Compliance 69 * provision in the documentation and/or other materials provided with the 70 * distribution. 71 * 72 * 3.4. Intel retains all right, title, and interest in and to the Original 73 * Intel Code. 74 * 75 * 3.5. Neither the name Intel nor any other trademark owned or controlled by 76 * Intel shall be used in advertising or otherwise to promote the sale, use or 77 * other dealings in products derived from or relating to the Covered Code 78 * without prior written authorization from Intel. 79 * 80 * 4. Disclaimer and Export Compliance 81 * 82 * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED 83 * HERE. ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE 84 * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT, ASSISTANCE, 85 * INSTALLATION, TRAINING OR OTHER SERVICES. INTEL WILL NOT PROVIDE ANY 86 * UPDATES, ENHANCEMENTS OR EXTENSIONS. INTEL SPECIFICALLY DISCLAIMS ANY 87 * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A 88 * PARTICULAR PURPOSE. 89 * 90 * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES 91 * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR 92 * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT, 93 * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY 94 * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL 95 * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES. THESE LIMITATIONS 96 * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY 97 * LIMITED REMEDY. 98 * 99 * 4.3. Licensee shall not export, either directly or indirectly, any of this 100 * software or system incorporating such software without first obtaining any 101 * required license or other approval from the U. S. Department of Commerce or 102 * any other agency or department of the United States Government. In the 103 * event Licensee exports any such software from the United States or 104 * re-exports any such software from a foreign destination, Licensee shall 105 * ensure that the distribution and export/re-export of the software is in 106 * compliance with all laws, regulations, orders, or other restrictions of the 107 * U.S. Export Administration Regulations. Licensee agrees that neither it nor 108 * any of its subsidiaries will export/re-export any technical data, process, 109 * software, or service, directly or indirectly, to any country for which the 110 * United States government or any agency thereof requires an export license, 111 * other governmental approval, or letter of assurance, without first obtaining 112 * such license, approval or letter. 113 * 114 *****************************************************************************/ 115 116 117#define __UTMATH_C__ 118 119#include "acpi.h" 120#include "accommon.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 150ACPI_STATUS 151AcpiUtShortDivide ( 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 214ACPI_STATUS 215AcpiUtDivide ( 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 363ACPI_STATUS 364AcpiUtShortDivide ( 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 396ACPI_STATUS 397AcpiUtDivide ( 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