LXR linux/drivers/acpi/acpica/utmath.c

   1/*******************************************************************************
   2 *
   3 * Module Name: utmath - Integer math support routines
   4 *
   5 ******************************************************************************/
   6
   7/*
   8 * Copyright (C) 2000 - 2011, 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
  48ACPI_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 */
  60typedef struct uint64_struct {
  61        u32 lo;
  62        u32 hi;
  63
  64} uint64_struct;
  65
  66typedef 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
  89acpi_status
  90acpi_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
 144acpi_status
 145acpi_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 ******************************************************************************/
 273acpi_status
 274acpi_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
 299acpi_status
 300acpi_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
 325