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