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 - 2015, 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 <contrib/dev/acpica/include/acpi.h>
  45 #include <contrib/dev/acpica/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     ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor,
 127                        Quotient.Part.Lo, Remainder32);
 128
 129     /* Return only what was requested */
 130
 131     if (OutQuotient)
 132     {
 133         *OutQuotient = Quotient.Full;
 134     }
 135     if (OutRemainder)
 136     {
 137         *OutRemainder = Remainder32;
 138     }
 139
 140     return_ACPI_STATUS (AE_OK);
 141 }
 142
 143
 144 /*******************************************************************************
 145  *
 146  * FUNCTION:    AcpiUtDivide
 147  *
 148  * PARAMETERS:  InDividend          - Dividend
 149  *              InDivisor           - Divisor
 150  *              OutQuotient         - Pointer to where the quotient is returned
 151  *              OutRemainder        - Pointer to where the remainder is returned
 152  *
 153  * RETURN:      Status (Checks for divide-by-zero)
 154  *
 155  * DESCRIPTION: Perform a divide and modulo.
 156  *
 157  ******************************************************************************/
 158
 159 ACPI_STATUS
 160 AcpiUtDivide (
 161     UINT64                  InDividend,
 162     UINT64                  InDivisor,
 163     UINT64                  *OutQuotient,
 164     UINT64                  *OutRemainder)
 165 {
 166     UINT64_OVERLAY          Dividend;
 167     UINT64_OVERLAY          Divisor;
 168     UINT64_OVERLAY          Quotient;
 169     UINT64_OVERLAY          Remainder;
 170     UINT64_OVERLAY          NormalizedDividend;
 171     UINT64_OVERLAY          NormalizedDivisor;
 172     UINT32                  Partial1;
 173     UINT64_OVERLAY          Partial2;
 174     UINT64_OVERLAY          Partial3;
 175
 176
 177     ACPI_FUNCTION_TRACE (UtDivide);
 178
 179
 180     /* Always check for a zero divisor */
 181
 182     if (InDivisor == 0)
 183     {
 184         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 185         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 186     }
 187
 188     Divisor.Full  = InDivisor;
 189     Dividend.Full = InDividend;
 190     if (Divisor.Part.Hi == 0)
 191     {
 192         /*
 193          * 1) Simplest case is where the divisor is 32 bits, we can
 194          * just do two divides
 195          */
 196         Remainder.Part.Hi = 0;
 197
 198         /*
 199          * The quotient is 64 bits, the remainder is always 32 bits,
 200          * and is generated by the second divide.
 201          */
 202         ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo,
 203                            Quotient.Part.Hi, Partial1);
 204         ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo,
 205                            Quotient.Part.Lo, Remainder.Part.Lo);
 206     }
 207
 208     else
 209     {
 210         /*
 211          * 2) The general case where the divisor is a full 64 bits
 212          * is more difficult
 213          */
 214         Quotient.Part.Hi   = 0;
 215         NormalizedDividend = Dividend;
 216         NormalizedDivisor  = Divisor;
 217
 218         /* Normalize the operands (shift until the divisor is < 32 bits) */
 219
 220         do
 221         {
 222             ACPI_SHIFT_RIGHT_64 (NormalizedDivisor.Part.Hi,
 223                                  NormalizedDivisor.Part.Lo);
 224             ACPI_SHIFT_RIGHT_64 (NormalizedDividend.Part.Hi,
 225                                  NormalizedDividend.Part.Lo);
 226
 227         } while (NormalizedDivisor.Part.Hi != 0);
 228
 229         /* Partial divide */
 230
 231         ACPI_DIV_64_BY_32 (NormalizedDividend.Part.Hi,
 232                            NormalizedDividend.Part.Lo,
 233                            NormalizedDivisor.Part.Lo,
 234                            Quotient.Part.Lo, Partial1);
 235
 236         /*
 237          * The quotient is always 32 bits, and simply requires adjustment.
 238          * The 64-bit remainder must be generated.
 239          */
 240         Partial1      = Quotient.Part.Lo * Divisor.Part.Hi;
 241         Partial2.Full = (UINT64) Quotient.Part.Lo * Divisor.Part.Lo;
 242         Partial3.Full = (UINT64) Partial2.Part.Hi + Partial1;
 243
 244         Remainder.Part.Hi = Partial3.Part.Lo;
 245         Remainder.Part.Lo = Partial2.Part.Lo;
 246
 247         if (Partial3.Part.Hi == 0)
 248         {
 249             if (Partial3.Part.Lo >= Dividend.Part.Hi)
 250             {
 251                 if (Partial3.Part.Lo == Dividend.Part.Hi)
 252                 {
 253                     if (Partial2.Part.Lo > Dividend.Part.Lo)
 254                     {
 255                         Quotient.Part.Lo--;
 256                         Remainder.Full -= Divisor.Full;
 257                     }
 258                 }
 259                 else
 260                 {
 261                     Quotient.Part.Lo--;
 262                     Remainder.Full -= Divisor.Full;
 263                 }
 264             }
 265
 266             Remainder.Full    = Remainder.Full - Dividend.Full;
 267             Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi);
 268             Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo);
 269
 270             if (Remainder.Part.Lo)
 271             {
 272                 Remainder.Part.Hi--;
 273             }
 274         }
 275     }
 276
 277     /* Return only what was requested */
 278
 279     if (OutQuotient)
 280     {
 281         *OutQuotient = Quotient.Full;
 282     }
 283     if (OutRemainder)
 284     {
 285         *OutRemainder = Remainder.Full;
 286     }
 287
 288     return_ACPI_STATUS (AE_OK);
 289 }
 290
 291 #else
 292
 293 /*******************************************************************************
 294  *
 295  * FUNCTION:    AcpiUtShortDivide, AcpiUtDivide
 296  *
 297  * PARAMETERS:  See function headers above
 298  *
 299  * DESCRIPTION: Native versions of the UtDivide functions. Use these if either
 300  *              1) The target is a 64-bit platform and therefore 64-bit
 301  *                 integer math is supported directly by the machine.
 302  *              2) The target is a 32-bit or 16-bit platform, and the
 303  *                 double-precision integer math library is available to
 304  *                 perform the divide.
 305  *
 306  ******************************************************************************/
 307
 308 ACPI_STATUS
 309 AcpiUtShortDivide (
 310     UINT64                  InDividend,
 311     UINT32                  Divisor,
 312     UINT64                  *OutQuotient,
 313     UINT32                  *OutRemainder)
 314 {
 315
 316     ACPI_FUNCTION_TRACE (UtShortDivide);
 317
 318
 319     /* Always check for a zero divisor */
 320
 321     if (Divisor == 0)
 322     {
 323         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 324         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 325     }
 326
 327     /* Return only what was requested */
 328
 329     if (OutQuotient)
 330     {
 331         *OutQuotient = InDividend / Divisor;
 332     }
 333     if (OutRemainder)
 334     {
 335         *OutRemainder = (UINT32) (InDividend % Divisor);
 336     }
 337
 338     return_ACPI_STATUS (AE_OK);
 339 }
 340
 341 ACPI_STATUS
 342 AcpiUtDivide (
 343     UINT64                  InDividend,
 344     UINT64                  InDivisor,
 345     UINT64                  *OutQuotient,
 346     UINT64                  *OutRemainder)
 347 {
 348     ACPI_FUNCTION_TRACE (UtDivide);
 349
 350
 351     /* Always check for a zero divisor */
 352
 353     if (InDivisor == 0)
 354     {
 355         ACPI_ERROR ((AE_INFO, "Divide by zero"));
 356         return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO);
 357     }
 358
 359
 360     /* Return only what was requested */
 361
 362     if (OutQuotient)
 363     {
 364         *OutQuotient = InDividend / InDivisor;
 365     }
 366     if (OutRemainder)
 367     {
 368         *OutRemainder = InDividend % InDivisor;
 369     }
 370
 371     return_ACPI_STATUS (AE_OK);
 372 }
 373
 374 #endif