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