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

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