drivers/bus/acpi/acpica/utilities/utmath.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: utmath - Integer math support routines
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2017, 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