drivers/acpi/utilities/utmath.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: utmath - Integer math support routines
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2007, R. Byron Moore
   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/acpi.h>
  45
  46 #define _COMPONENT          ACPI_UTILITIES
  47 ACPI_MODULE_NAME("utmath")
  48
  49 /*
  50  * Support for double-precision integer divide.  This code is included here
  51  * in order to support kernel environments where the double-precision math
  52  * library is not available.
  53  */
  54 #ifndef ACPI_USE_NATIVE_DIVIDE
  55 /*******************************************************************************
  56  *
  57  * FUNCTION:    acpi_ut_short_divide
  58  *
  59  * PARAMETERS:  Dividend            - 64-bit dividend
  60  *              Divisor             - 32-bit divisor
  61  *              out_quotient        - Pointer to where the quotient is returned
  62  *              out_remainder       - Pointer to where the remainder is returned
  63  *
  64  * RETURN:      Status (Checks for divide-by-zero)
  65  *
  66  * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
  67  *              divide and modulo.  The result is a 64-bit quotient and a
  68  *              32-bit remainder.
  69  *
  70  ******************************************************************************/
  71 acpi_status
  72 acpi_ut_short_divide(acpi_integer dividend,
  73                      u32 divisor,
  74                      acpi_integer * out_quotient, u32 * out_remainder)
  75 {
  76         union uint64_overlay dividend_ovl;
  77         union uint64_overlay quotient;
  78         u32 remainder32;
  79
  80         ACPI_FUNCTION_TRACE(ut_short_divide);
  81
  82         /* Always check for a zero divisor */
  83
  84         if (divisor == 0) {
  85                 ACPI_ERROR((AE_INFO, "Divide by zero"));
  86                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
  87         }
  88
  89         dividend_ovl.full = dividend;
  90
  91         /*
  92          * The quotient is 64 bits, the remainder is always 32 bits,
  93          * and is generated by the second divide.
  94          */
  95         ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor,
  96                           quotient.part.hi, remainder32);
  97         ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor,
  98                           quotient.part.lo, remainder32);
  99
 100         /* Return only what was requested */
 101
 102         if (out_quotient) {
 103                 *out_quotient = quotient.full;
 104         }
 105         if (out_remainder) {
 106                 *out_remainder = remainder32;
 107         }
 108
 109         return_ACPI_STATUS(AE_OK);
 110 }
 111
 112 /*******************************************************************************
 113  *
 114  * FUNCTION:    acpi_ut_divide
 115  *
 116  * PARAMETERS:  in_dividend         - Dividend
 117  *              in_divisor          - Divisor
 118  *              out_quotient        - Pointer to where the quotient is returned
 119  *              out_remainder       - Pointer to where the remainder is returned
 120  *
 121  * RETURN:      Status (Checks for divide-by-zero)
 122  *
 123  * DESCRIPTION: Perform a divide and modulo.
 124  *
 125  ******************************************************************************/
 126
 127 acpi_status
 128 acpi_ut_divide(acpi_integer in_dividend,
 129                acpi_integer in_divisor,
 130                acpi_integer * out_quotient, acpi_integer * out_remainder)
 131 {
 132         union uint64_overlay dividend;
 133         union uint64_overlay divisor;
 134         union uint64_overlay quotient;
 135         union uint64_overlay remainder;
 136         union uint64_overlay normalized_dividend;
 137         union uint64_overlay normalized_divisor;
 138         u32 partial1;
 139         union uint64_overlay partial2;
 140         union uint64_overlay partial3;
 141
 142         ACPI_FUNCTION_TRACE(ut_divide);
 143
 144         /* Always check for a zero divisor */
 145
 146         if (in_divisor == 0) {
 147                 ACPI_ERROR((AE_INFO, "Divide by zero"));
 148                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
 149         }
 150
 151         divisor.full = in_divisor;
 152         dividend.full = in_dividend;
 153         if (divisor.part.hi == 0) {
 154                 /*
 155                  * 1) Simplest case is where the divisor is 32 bits, we can
 156                  * just do two divides
 157                  */
 158                 remainder.part.hi = 0;
 159
 160                 /*
 161                  * The quotient is 64 bits, the remainder is always 32 bits,
 162                  * and is generated by the second divide.
 163                  */
 164                 ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo,
 165                                   quotient.part.hi, partial1);
 166                 ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo,
 167                                   quotient.part.lo, remainder.part.lo);
 168         }
 169
 170         else {
 171                 /*
 172                  * 2) The general case where the divisor is a full 64 bits
 173                  * is more difficult
 174                  */
 175                 quotient.part.hi = 0;
 176                 normalized_dividend = dividend;
 177                 normalized_divisor = divisor;
 178
 179                 /* Normalize the operands (shift until the divisor is < 32 bits) */
 180
 181                 do {
 182                         ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi,
 183                                             normalized_divisor.part.lo);
 184                         ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi,
 185                                             normalized_dividend.part.lo);
 186
 187                 } while (normalized_divisor.part.hi != 0);
 188
 189                 /* Partial divide */
 190
 191                 ACPI_DIV_64_BY_32(normalized_dividend.part.hi,
 192                                   normalized_dividend.part.lo,
 193                                   normalized_divisor.part.lo,
 194                                   quotient.part.lo, partial1);
 195
 196                 /*
 197                  * The quotient is always 32 bits, and simply requires adjustment.
 198                  * The 64-bit remainder must be generated.
 199                  */
 200                 partial1 = quotient.part.lo * divisor.part.hi;
 201                 partial2.full =
 202                     (acpi_integer) quotient.part.lo * divisor.part.lo;
 203                 partial3.full = (acpi_integer) partial2.part.hi + partial1;
 204
 205                 remainder.part.hi = partial3.part.lo;
 206                 remainder.part.lo = partial2.part.lo;
 207
 208                 if (partial3.part.hi == 0) {
 209                         if (partial3.part.lo >= dividend.part.hi) {
 210                                 if (partial3.part.lo == dividend.part.hi) {
 211                                         if (partial2.part.lo > dividend.part.lo) {
 212                                                 quotient.part.lo--;
 213                                                 remainder.full -= divisor.full;
 214                                         }
 215                                 } else {
 216                                         quotient.part.lo--;
 217                                         remainder.full -= divisor.full;
 218                                 }
 219                         }
 220
 221                         remainder.full = remainder.full - dividend.full;
 222                         remainder.part.hi = (u32) - ((s32) remainder.part.hi);
 223                         remainder.part.lo = (u32) - ((s32) remainder.part.lo);
 224
 225                         if (remainder.part.lo) {
 226                                 remainder.part.hi--;
 227                         }
 228                 }
 229         }
 230
 231         /* Return only what was requested */
 232
 233         if (out_quotient) {
 234                 *out_quotient = quotient.full;
 235         }
 236         if (out_remainder) {
 237                 *out_remainder = remainder.full;
 238         }
 239
 240         return_ACPI_STATUS(AE_OK);
 241 }
 242
 243 #else
 244 /*******************************************************************************
 245  *
 246  * FUNCTION:    acpi_ut_short_divide, acpi_ut_divide
 247  *
 248  * PARAMETERS:  See function headers above
 249  *
 250  * DESCRIPTION: Native versions of the ut_divide functions. Use these if either
 251  *              1) The target is a 64-bit platform and therefore 64-bit
 252  *                 integer math is supported directly by the machine.
 253  *              2) The target is a 32-bit or 16-bit platform, and the
 254  *                 double-precision integer math library is available to
 255  *                 perform the divide.
 256  *
 257  ******************************************************************************/
 258 acpi_status
 259 acpi_ut_short_divide(acpi_integer in_dividend,
 260                      u32 divisor,
 261                      acpi_integer * out_quotient, u32 * out_remainder)
 262 {
 263
 264         ACPI_FUNCTION_TRACE(ut_short_divide);
 265
 266         /* Always check for a zero divisor */
 267
 268         if (divisor == 0) {
 269                 ACPI_ERROR((AE_INFO, "Divide by zero"));
 270                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
 271         }
 272
 273         /* Return only what was requested */
 274
 275         if (out_quotient) {
 276                 *out_quotient = in_dividend / divisor;
 277         }
 278         if (out_remainder) {
 279                 *out_remainder = (u32) in_dividend % divisor;
 280         }
 281
 282         return_ACPI_STATUS(AE_OK);
 283 }
 284
 285 acpi_status
 286 acpi_ut_divide(acpi_integer in_dividend,
 287                acpi_integer in_divisor,
 288                acpi_integer * out_quotient, acpi_integer * out_remainder)
 289 {
 290         ACPI_FUNCTION_TRACE(ut_divide);
 291
 292         /* Always check for a zero divisor */
 293
 294         if (in_divisor == 0) {
 295                 ACPI_ERROR((AE_INFO, "Divide by zero"));
 296                 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
 297         }
 298
 299         /* Return only what was requested */
 300
 301         if (out_quotient) {
 302                 *out_quotient = in_dividend / in_divisor;
 303         }
 304         if (out_remainder) {
 305                 *out_remainder = in_dividend % in_divisor;
 306         }
 307
 308         return_ACPI_STATUS(AE_OK);
 309 }
 310
 311 #endif