1 /******************************************************************************* 2 * 3 * Module Name: utmath - Integer math support routines 4 * 5 ******************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2020, 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.h" 45 #include "accommon.h" 46 47 48 #define _COMPONENT ACPI_UTILITIES 49 ACPI_MODULE_NAME ("utmath") 50 51 /* Structures used only for 64-bit divide */ 52 53 typedef struct uint64_struct 54 { 55 UINT32 Lo; 56 UINT32 Hi; 57 58 } UINT64_STRUCT; 59 60 typedef union uint64_overlay 61 { 62 UINT64 Full; 63 UINT64_STRUCT Part; 64 65 } UINT64_OVERLAY; 66 67 /* 68 * Optional support for 64-bit double-precision integer multiply and shift. 69 * This code is configurable and is implemented in order to support 32-bit 70 * kernel environments where a 64-bit double-precision math library is not 71 * available. 72 */ 73 #ifndef ACPI_USE_NATIVE_MATH64 74 75 /******************************************************************************* 76 * 77 * FUNCTION: AcpiUtShortMultiply 78 * 79 * PARAMETERS: Multiplicand - 64-bit multiplicand 80 * Multiplier - 32-bit multiplier 81 * OutProduct - Pointer to where the product is returned 82 * 83 * DESCRIPTION: Perform a short multiply. 84 * 85 ******************************************************************************/ 86 87 ACPI_STATUS 88 AcpiUtShortMultiply ( 89 UINT64 Multiplicand, 90 UINT32 Multiplier, 91 UINT64 *OutProduct) 92 { 93 UINT64_OVERLAY MultiplicandOvl; 94 UINT64_OVERLAY Product; 95 UINT32 Carry32; 96 97 98 ACPI_FUNCTION_TRACE (UtShortMultiply); 99 100 101 MultiplicandOvl.Full = Multiplicand; 102 103 /* 104 * The Product is 64 bits, the carry is always 32 bits, 105 * and is generated by the second multiply. 106 */ 107 ACPI_MUL_64_BY_32 (0, MultiplicandOvl.Part.Hi, Multiplier, 108 Product.Part.Hi, Carry32); 109 110 ACPI_MUL_64_BY_32 (0, MultiplicandOvl.Part.Lo, Multiplier, 111 Product.Part.Lo, Carry32); 112 113 Product.Part.Hi += Carry32; 114 115 /* Return only what was requested */ 116 117 if (OutProduct) 118 { 119 *OutProduct = Product.Full; 120 } 121 122 return_ACPI_STATUS (AE_OK); 123 } 124 125 126 /******************************************************************************* 127 * 128 * FUNCTION: AcpiUtShortShiftLeft 129 * 130 * PARAMETERS: Operand - 64-bit shift operand 131 * Count - 32-bit shift count 132 * OutResult - Pointer to where the result is returned 133 * 134 * DESCRIPTION: Perform a short left shift. 135 * 136 ******************************************************************************/ 137 138 ACPI_STATUS 139 AcpiUtShortShiftLeft ( 140 UINT64 Operand, 141 UINT32 Count, 142 UINT64 *OutResult) 143 { 144 UINT64_OVERLAY OperandOvl; 145 146 147 ACPI_FUNCTION_TRACE (UtShortShiftLeft); 148 149 150 OperandOvl.Full = Operand; 151 152 if ((Count & 63) >= 32) 153 { 154 OperandOvl.Part.Hi = OperandOvl.Part.Lo; 155 OperandOvl.Part.Lo = 0; 156 Count = (Count & 63) - 32; 157 } 158 ACPI_SHIFT_LEFT_64_BY_32 (OperandOvl.Part.Hi, 159 OperandOvl.Part.Lo, Count); 160 161 /* Return only what was requested */ 162 163 if (OutResult) 164 { 165 *OutResult = OperandOvl.Full; 166 } 167 168 return_ACPI_STATUS (AE_OK); 169 } 170 171 /******************************************************************************* 172 * 173 * FUNCTION: AcpiUtShortShiftRight 174 * 175 * PARAMETERS: Operand - 64-bit shift operand 176 * Count - 32-bit shift count 177 * OutResult - Pointer to where the result is returned 178 * 179 * DESCRIPTION: Perform a short right shift. 180 * 181 ******************************************************************************/ 182 183 ACPI_STATUS 184 AcpiUtShortShiftRight ( 185 UINT64 Operand, 186 UINT32 Count, 187 UINT64 *OutResult) 188 { 189 UINT64_OVERLAY OperandOvl; 190 191 192 ACPI_FUNCTION_TRACE (UtShortShiftRight); 193 194 195 OperandOvl.Full = Operand; 196 197 if ((Count & 63) >= 32) 198 { 199 OperandOvl.Part.Lo = OperandOvl.Part.Hi; 200 OperandOvl.Part.Hi = 0; 201 Count = (Count & 63) - 32; 202 } 203 ACPI_SHIFT_RIGHT_64_BY_32 (OperandOvl.Part.Hi, 204 OperandOvl.Part.Lo, Count); 205 206 /* Return only what was requested */ 207 208 if (OutResult) 209 { 210 *OutResult = OperandOvl.Full; 211 } 212 213 return_ACPI_STATUS (AE_OK); 214 } 215 #else 216 217 /******************************************************************************* 218 * 219 * FUNCTION: AcpiUtShortMultiply 220 * 221 * PARAMETERS: See function headers above 222 * 223 * DESCRIPTION: Native version of the UtShortMultiply function. 224 * 225 ******************************************************************************/ 226 227 ACPI_STATUS 228 AcpiUtShortMultiply ( 229 UINT64 Multiplicand, 230 UINT32 Multiplier, 231 UINT64 *OutProduct) 232 { 233 234 ACPI_FUNCTION_TRACE (UtShortMultiply); 235 236 237 /* Return only what was requested */ 238 239 if (OutProduct) 240 { 241 *OutProduct = Multiplicand * Multiplier; 242 } 243 244 return_ACPI_STATUS (AE_OK); 245 } 246 247 /******************************************************************************* 248 * 249 * FUNCTION: AcpiUtShortShiftLeft 250 * 251 * PARAMETERS: See function headers above 252 * 253 * DESCRIPTION: Native version of the UtShortShiftLeft function. 254 * 255 ******************************************************************************/ 256 257 ACPI_STATUS 258 AcpiUtShortShiftLeft ( 259 UINT64 Operand, 260 UINT32 Count, 261 UINT64 *OutResult) 262 { 263 264 ACPI_FUNCTION_TRACE (UtShortShiftLeft); 265 266 267 /* Return only what was requested */ 268 269 if (OutResult) 270 { 271 *OutResult = Operand << Count; 272 } 273 274 return_ACPI_STATUS (AE_OK); 275 } 276 277 /******************************************************************************* 278 * 279 * FUNCTION: AcpiUtShortShiftRight 280 * 281 * PARAMETERS: See function headers above 282 * 283 * DESCRIPTION: Native version of the UtShortShiftRight function. 284 * 285 ******************************************************************************/ 286 287 ACPI_STATUS 288 AcpiUtShortShiftRight ( 289 UINT64 Operand, 290 UINT32 Count, 291 UINT64 *OutResult) 292 { 293 294 ACPI_FUNCTION_TRACE (UtShortShiftRight); 295 296 297 /* Return only what was requested */ 298 299 if (OutResult) 300 { 301 *OutResult = Operand >> Count; 302 } 303 304 return_ACPI_STATUS (AE_OK); 305 } 306 #endif 307 308 /* 309 * Optional support for 64-bit double-precision integer divide. This code 310 * is configurable and is implemented in order to support 32-bit kernel 311 * environments where a 64-bit double-precision math library is not available. 312 * 313 * Support for a more normal 64-bit divide/modulo (with check for a divide- 314 * by-zero) appears after this optional section of code. 315 */ 316 #ifndef ACPI_USE_NATIVE_DIVIDE 317 318 319 /******************************************************************************* 320 * 321 * FUNCTION: AcpiUtShortDivide 322 * 323 * PARAMETERS: Dividend - 64-bit dividend 324 * Divisor - 32-bit divisor 325 * OutQuotient - Pointer to where the quotient is returned 326 * OutRemainder - Pointer to where the remainder is returned 327 * 328 * RETURN: Status (Checks for divide-by-zero) 329 * 330 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) 331 * divide and modulo. The result is a 64-bit quotient and a 332 * 32-bit remainder. 333 * 334 ******************************************************************************/ 335 336 ACPI_STATUS 337 AcpiUtShortDivide ( 338 UINT64 Dividend, 339 UINT32 Divisor, 340 UINT64 *OutQuotient, 341 UINT32 *OutRemainder) 342 { 343 UINT64_OVERLAY DividendOvl; 344 UINT64_OVERLAY Quotient; 345 UINT32 Remainder32; 346 347 348 ACPI_FUNCTION_TRACE (UtShortDivide); 349 350 351 /* Always check for a zero divisor */ 352 353 if (Divisor == 0) 354 { 355 ACPI_ERROR ((AE_INFO, "Divide by zero")); 356 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 357 } 358 359 DividendOvl.Full = Dividend; 360 361 /* 362 * The quotient is 64 bits, the remainder is always 32 bits, 363 * and is generated by the second divide. 364 */ 365 ACPI_DIV_64_BY_32 (0, DividendOvl.Part.Hi, Divisor, 366 Quotient.Part.Hi, Remainder32); 367 368 ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor, 369 Quotient.Part.Lo, Remainder32); 370 371 /* Return only what was requested */ 372 373 if (OutQuotient) 374 { 375 *OutQuotient = Quotient.Full; 376 } 377 if (OutRemainder) 378 { 379 *OutRemainder = Remainder32; 380 } 381 382 return_ACPI_STATUS (AE_OK); 383 } 384 385 386 /******************************************************************************* 387 * 388 * FUNCTION: AcpiUtDivide 389 * 390 * PARAMETERS: InDividend - Dividend 391 * InDivisor - Divisor 392 * OutQuotient - Pointer to where the quotient is returned 393 * OutRemainder - Pointer to where the remainder is returned 394 * 395 * RETURN: Status (Checks for divide-by-zero) 396 * 397 * DESCRIPTION: Perform a divide and modulo. 398 * 399 ******************************************************************************/ 400 401 ACPI_STATUS 402 AcpiUtDivide ( 403 UINT64 InDividend, 404 UINT64 InDivisor, 405 UINT64 *OutQuotient, 406 UINT64 *OutRemainder) 407 { 408 UINT64_OVERLAY Dividend; 409 UINT64_OVERLAY Divisor; 410 UINT64_OVERLAY Quotient; 411 UINT64_OVERLAY Remainder; 412 UINT64_OVERLAY NormalizedDividend; 413 UINT64_OVERLAY NormalizedDivisor; 414 UINT32 Partial1; 415 UINT64_OVERLAY Partial2; 416 UINT64_OVERLAY Partial3; 417 418 419 ACPI_FUNCTION_TRACE (UtDivide); 420 421 422 /* Always check for a zero divisor */ 423 424 if (InDivisor == 0) 425 { 426 ACPI_ERROR ((AE_INFO, "Divide by zero")); 427 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 428 } 429 430 Divisor.Full = InDivisor; 431 Dividend.Full = InDividend; 432 if (Divisor.Part.Hi == 0) 433 { 434 /* 435 * 1) Simplest case is where the divisor is 32 bits, we can 436 * just do two divides 437 */ 438 Remainder.Part.Hi = 0; 439 440 /* 441 * The quotient is 64 bits, the remainder is always 32 bits, 442 * and is generated by the second divide. 443 */ 444 ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo, 445 Quotient.Part.Hi, Partial1); 446 447 ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo, 448 Quotient.Part.Lo, Remainder.Part.Lo); 449 } 450 451 else 452 { 453 /* 454 * 2) The general case where the divisor is a full 64 bits 455 * is more difficult 456 */ 457 Quotient.Part.Hi = 0; 458 NormalizedDividend = Dividend; 459 NormalizedDivisor = Divisor; 460 461 /* Normalize the operands (shift until the divisor is < 32 bits) */ 462 463 do 464 { 465 ACPI_SHIFT_RIGHT_64 ( 466 NormalizedDivisor.Part.Hi, NormalizedDivisor.Part.Lo); 467 ACPI_SHIFT_RIGHT_64 ( 468 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo); 469 470 } while (NormalizedDivisor.Part.Hi != 0); 471 472 /* Partial divide */ 473 474 ACPI_DIV_64_BY_32 ( 475 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo, 476 NormalizedDivisor.Part.Lo, Quotient.Part.Lo, Partial1); 477 478 /* 479 * The quotient is always 32 bits, and simply requires 480 * adjustment. The 64-bit remainder must be generated. 481 */ 482 Partial1 = Quotient.Part.Lo * Divisor.Part.Hi; 483 Partial2.Full = (UINT64) Quotient.Part.Lo * Divisor.Part.Lo; 484 Partial3.Full = (UINT64) Partial2.Part.Hi + Partial1; 485 486 Remainder.Part.Hi = Partial3.Part.Lo; 487 Remainder.Part.Lo = Partial2.Part.Lo; 488 489 if (Partial3.Part.Hi == 0) 490 { 491 if (Partial3.Part.Lo >= Dividend.Part.Hi) 492 { 493 if (Partial3.Part.Lo == Dividend.Part.Hi) 494 { 495 if (Partial2.Part.Lo > Dividend.Part.Lo) 496 { 497 Quotient.Part.Lo--; 498 Remainder.Full -= Divisor.Full; 499 } 500 } 501 else 502 { 503 Quotient.Part.Lo--; 504 Remainder.Full -= Divisor.Full; 505 } 506 } 507 508 Remainder.Full = Remainder.Full - Dividend.Full; 509 Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi); 510 Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo); 511 512 if (Remainder.Part.Lo) 513 { 514 Remainder.Part.Hi--; 515 } 516 } 517 } 518 519 /* Return only what was requested */ 520 521 if (OutQuotient) 522 { 523 *OutQuotient = Quotient.Full; 524 } 525 if (OutRemainder) 526 { 527 *OutRemainder = Remainder.Full; 528 } 529 530 return_ACPI_STATUS (AE_OK); 531 } 532 533 #else 534 535 /******************************************************************************* 536 * 537 * FUNCTION: AcpiUtShortDivide, AcpiUtDivide 538 * 539 * PARAMETERS: See function headers above 540 * 541 * DESCRIPTION: Native versions of the UtDivide functions. Use these if either 542 * 1) The target is a 64-bit platform and therefore 64-bit 543 * integer math is supported directly by the machine. 544 * 2) The target is a 32-bit or 16-bit platform, and the 545 * double-precision integer math library is available to 546 * perform the divide. 547 * 548 ******************************************************************************/ 549 550 ACPI_STATUS 551 AcpiUtShortDivide ( 552 UINT64 InDividend, 553 UINT32 Divisor, 554 UINT64 *OutQuotient, 555 UINT32 *OutRemainder) 556 { 557 558 ACPI_FUNCTION_TRACE (UtShortDivide); 559 560 561 /* Always check for a zero divisor */ 562 563 if (Divisor == 0) 564 { 565 ACPI_ERROR ((AE_INFO, "Divide by zero")); 566 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 567 } 568 569 /* Return only what was requested */ 570 571 if (OutQuotient) 572 { 573 *OutQuotient = InDividend / Divisor; 574 } 575 if (OutRemainder) 576 { 577 *OutRemainder = (UINT32) (InDividend % Divisor); 578 } 579 580 return_ACPI_STATUS (AE_OK); 581 } 582 583 ACPI_STATUS 584 AcpiUtDivide ( 585 UINT64 InDividend, 586 UINT64 InDivisor, 587 UINT64 *OutQuotient, 588 UINT64 *OutRemainder) 589 { 590 ACPI_FUNCTION_TRACE (UtDivide); 591 592 593 /* Always check for a zero divisor */ 594 595 if (InDivisor == 0) 596 { 597 ACPI_ERROR ((AE_INFO, "Divide by zero")); 598 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 599 } 600 601 602 /* Return only what was requested */ 603 604 if (OutQuotient) 605 { 606 *OutQuotient = InDividend / InDivisor; 607 } 608 if (OutRemainder) 609 { 610 *OutRemainder = InDividend % InDivisor; 611 } 612 613 return_ACPI_STATUS (AE_OK); 614 } 615 616 #endif 617