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 45 #define __UTMATH_C__ 46 47 #include "acpi.h" 48 #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 378 379 380