sys/contrib/dev/acpica/source/components/utilities/utmath.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: utmath - Integer math support routines
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2016, 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 /*
  52  * Optional support for 64-bit double-precision integer divide. This code
  53  * is configurable and is implemented in order to support 32-bit kernel
  54  * environments where a 64-bit double-precision math library is not available.
  55  *
  56  * Support for a more normal 64-bit divide/modulo (with check for a divide-
  57  * by-zero) appears after this optional section of code.
  58  */
  59 #ifndef ACPI_USE_NATIVE_DIVIDE
  60
  61 /* Structures used only for 64-bit divide */
  62
  63 typedef struct uint64_struct
  64 {
  65     UINT32                          Lo;
  66     UINT32                          Hi;
  67
  68 } UINT64_STRUCT;
  69
  70 typedef union uint64_overlay
  71 {
  72     UINT64                          Full;
  73     UINT64_STRUCT                   Part;
  74
  75 } UINT64_OVERLAY;
  76
  77
  78 /*******************************************************************************
  79  *
  80  * FUNCTION:    AcpiUtShortDivide
  81  *
  82  * PARAMETERS:  Dividend            - 64-bit dividend
  83  *              Divisor             - 32-bit divisor
  84  *              OutQuotient         - Pointer to where the quotient is returned
  85  *              OutRemainder        - Pointer to where the remainder is returned
  86  *
  87  * RETURN:      Status (Checks for divide-by-zero)
  88  *
  89  * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
  90  *              divide and modulo. The result is a 64-bit quotient and a
  91  *              32-bit remainder.
  92  *
  93  ******************************************************************************/
  94
  95 ACPI_STATUS
  96 AcpiUtShortDivide (
  97     UINT64                  Dividend,
  98     UINT32                  Divisor,
  99     UINT64                  *OutQuotient,
 100     UINT32                  *OutRemainder)
 101 {
 102     UINT64_OVERLAY          DividendOvl;
 103     UINT64_OVERLAY          Quotient;
 104     UINT32                  Remainder32;
 105
 106
 107     ACPI_FUNCTION_TRACE (UtShortDivide);
 108
 109
 110     /* Always check for a zero divisor */
 111
 112     if (Divisor == 0)
 113     {
 114         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 115         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 116     }
 117
 118     DividendOvl.Full = Dividend;
 119
 120     /*
 121      * The quotient is 64 bits, the remainder is always 32 bits,
 122      * and is generated by the second divide.
 123      */
 124     ACPI_DIV_64_BY_32 (0, DividendOvl.Part.Hi, Divisor,
 125         Quotient.Part.Hi, Remainder32);
 126
 127     ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor,
 128         Quotient.Part.Lo, Remainder32);
 129
 130     /* Return only what was requested */
 131
 132     if (OutQuotient)
 133     {
 134         *OutQuotient = Quotient.Full;
 135     }
 136     if (OutRemainder)
 137     {
 138         *OutRemainder = Remainder32;
 139     }
 140
 141     return_ACPI_STATUS (AE_OK);
 142 }
 143
 144
 145 /*******************************************************************************
 146  *
 147  * FUNCTION:    AcpiUtDivide
 148  *
 149  * PARAMETERS:  InDividend          - Dividend
 150  *              InDivisor           - Divisor
 151  *              OutQuotient         - Pointer to where the quotient is returned
 152  *              OutRemainder        - Pointer to where the remainder is returned
 153  *
 154  * RETURN:      Status (Checks for divide-by-zero)
 155  *
 156  * DESCRIPTION: Perform a divide and modulo.
 157  *
 158  ******************************************************************************/
 159
 160 ACPI_STATUS
 161 AcpiUtDivide (
 162     UINT64                  InDividend,
 163     UINT64                  InDivisor,
 164     UINT64                  *OutQuotient,
 165     UINT64                  *OutRemainder)
 166 {
 167     UINT64_OVERLAY          Dividend;
 168     UINT64_OVERLAY          Divisor;
 169     UINT64_OVERLAY          Quotient;
 170     UINT64_OVERLAY          Remainder;
 171     UINT64_OVERLAY          NormalizedDividend;
 172     UINT64_OVERLAY          NormalizedDivisor;
 173     UINT32                  Partial1;
 174     UINT64_OVERLAY          Partial2;
 175     UINT64_OVERLAY          Partial3;
 176
 177
 178     ACPI_FUNCTION_TRACE (UtDivide);
 179
 180
 181     /* Always check for a zero divisor */
 182
 183     if (InDivisor == 0)
 184     {
 185         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 186         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 187     }
 188
 189     Divisor.Full  = InDivisor;
 190     Dividend.Full = InDividend;
 191     if (Divisor.Part.Hi == 0)
 192     {
 193         /*
 194          * 1) Simplest case is where the divisor is 32 bits, we can
 195          * just do two divides
 196          */
 197         Remainder.Part.Hi = 0;
 198
 199         /*
 200          * The quotient is 64 bits, the remainder is always 32 bits,
 201          * and is generated by the second divide.
 202          */
 203         ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo,
 204             Quotient.Part.Hi, Partial1);
 205
 206         ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo,
 207             Quotient.Part.Lo, Remainder.Part.Lo);
 208     }
 209
 210     else
 211     {
 212         /*
 213          * 2) The general case where the divisor is a full 64 bits
 214          * is more difficult
 215          */
 216         Quotient.Part.Hi   = 0;
 217         NormalizedDividend = Dividend;
 218         NormalizedDivisor  = Divisor;
 219
 220         /* Normalize the operands (shift until the divisor is < 32 bits) */
 221
 222         do
 223         {
 224             ACPI_SHIFT_RIGHT_64 (
 225                 NormalizedDivisor.Part.Hi, NormalizedDivisor.Part.Lo);
 226             ACPI_SHIFT_RIGHT_64 (
 227                 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo);
 228
 229         } while (NormalizedDivisor.Part.Hi != 0);
 230
 231         /* Partial divide */
 232
 233         ACPI_DIV_64_BY_32 (
 234             NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo,
 235             NormalizedDivisor.Part.Lo, Quotient.Part.Lo, Partial1);
 236
 237         /*
 238          * The quotient is always 32 bits, and simply requires
 239          * adjustment. The 64-bit remainder must be generated.
 240          */
 241         Partial1 = Quotient.Part.Lo * Divisor.Part.Hi;
 242         Partial2.Full = (UINT64) Quotient.Part.Lo * Divisor.Part.Lo;
 243         Partial3.Full = (UINT64) Partial2.Part.Hi + Partial1;
 244
 245         Remainder.Part.Hi = Partial3.Part.Lo;
 246         Remainder.Part.Lo = Partial2.Part.Lo;
 247
 248         if (Partial3.Part.Hi == 0)
 249         {
 250             if (Partial3.Part.Lo >= Dividend.Part.Hi)
 251             {
 252                 if (Partial3.Part.Lo == Dividend.Part.Hi)
 253                 {
 254                     if (Partial2.Part.Lo > Dividend.Part.Lo)
 255                     {
 256                         Quotient.Part.Lo--;
 257                         Remainder.Full -= Divisor.Full;
 258                     }
 259                 }
 260                 else
 261                 {
 262                     Quotient.Part.Lo--;
 263                     Remainder.Full -= Divisor.Full;
 264                 }
 265             }
 266
 267             Remainder.Full = Remainder.Full - Dividend.Full;
 268             Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi);
 269             Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo);
 270
 271             if (Remainder.Part.Lo)
 272             {
 273                 Remainder.Part.Hi--;
 274             }
 275         }
 276     }
 277
 278     /* Return only what was requested */
 279
 280     if (OutQuotient)
 281     {
 282         *OutQuotient = Quotient.Full;
 283     }
 284     if (OutRemainder)
 285     {
 286         *OutRemainder = Remainder.Full;
 287     }
 288
 289     return_ACPI_STATUS (AE_OK);
 290 }
 291
 292 #else
 293
 294 /*******************************************************************************
 295  *
 296  * FUNCTION:    AcpiUtShortDivide, AcpiUtDivide
 297  *
 298  * PARAMETERS:  See function headers above
 299  *
 300  * DESCRIPTION: Native versions of the UtDivide functions. Use these if either
 301  *              1) The target is a 64-bit platform and therefore 64-bit
 302  *                 integer math is supported directly by the machine.
 303  *              2) The target is a 32-bit or 16-bit platform, and the
 304  *                 double-precision integer math library is available to
 305  *                 perform the divide.
 306  *
 307  ******************************************************************************/
 308
 309 ACPI_STATUS
 310 AcpiUtShortDivide (
 311     UINT64                  InDividend,
 312     UINT32                  Divisor,
 313     UINT64                  *OutQuotient,
 314     UINT32                  *OutRemainder)
 315 {
 316
 317     ACPI_FUNCTION_TRACE (UtShortDivide);
 318
 319
 320     /* Always check for a zero divisor */
 321
 322     if (Divisor == 0)
 323     {
 324         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 325         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 326     }
 327
 328     /* Return only what was requested */
 329
 330     if (OutQuotient)
 331     {
 332         *OutQuotient = InDividend / Divisor;
 333     }
 334     if (OutRemainder)
 335     {
 336         *OutRemainder = (UINT32) (InDividend % Divisor);
 337     }
 338
 339     return_ACPI_STATUS (AE_OK);
 340 }
 341
 342 ACPI_STATUS
 343 AcpiUtDivide (
 344     UINT64                  InDividend,
 345     UINT64                  InDivisor,
 346     UINT64                  *OutQuotient,
 347     UINT64                  *OutRemainder)
 348 {
 349     ACPI_FUNCTION_TRACE (UtDivide);
 350
 351
 352     /* Always check for a zero divisor */
 353
 354     if (InDivisor == 0)
 355     {
 356         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 357         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 358     }
 359
 360
 361     /* Return only what was requested */
 362
 363     if (OutQuotient)
 364     {
 365         *OutQuotient = InDividend / InDivisor;
 366     }
 367     if (OutRemainder)
 368     {
 369         *OutRemainder = InDividend % InDivisor;
 370     }
 371
 372     return_ACPI_STATUS (AE_OK);
 373 }
 374
 375 #endif