1 /******************************************************************************* 2 * 3 * Module Name: utmath - Integer math support routines 4 * 5 ******************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2018, 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 /* Structures used only for 64-bit divide */ 51 typedef struct uint64_struct { 52 u32 lo; 53 u32 hi; 54 55 } uint64_struct; 56 57 typedef union uint64_overlay { 58 u64 full; 59 struct uint64_struct part; 60 61 } uint64_overlay; 62 63 /* 64 * Optional support for 64-bit double-precision integer multiply and shift. 65 * This code is configurable and is implemented in order to support 32-bit 66 * kernel environments where a 64-bit double-precision math library is not 67 * available. 68 */ 69 #ifndef ACPI_USE_NATIVE_MATH64 70 71 /******************************************************************************* 72 * 73 * FUNCTION: acpi_ut_short_multiply 74 * 75 * PARAMETERS: multiplicand - 64-bit multiplicand 76 * multiplier - 32-bit multiplier 77 * out_product - Pointer to where the product is returned 78 * 79 * DESCRIPTION: Perform a short multiply. 80 * 81 ******************************************************************************/ 82 83 acpi_status 84 acpi_ut_short_multiply(u64 multiplicand, u32 multiplier, u64 *out_product) 85 { 86 union uint64_overlay multiplicand_ovl; 87 union uint64_overlay product; 88 u32 carry32; 89 90 ACPI_FUNCTION_TRACE(ut_short_multiply); 91 92 multiplicand_ovl.full = multiplicand; 93 94 /* 95 * The Product is 64 bits, the carry is always 32 bits, 96 * and is generated by the second multiply. 97 */ 98 ACPI_MUL_64_BY_32(0, multiplicand_ovl.part.hi, multiplier, 99 product.part.hi, carry32); 100 101 ACPI_MUL_64_BY_32(0, multiplicand_ovl.part.lo, multiplier, 102 product.part.lo, carry32); 103 104 product.part.hi += carry32; 105 106 /* Return only what was requested */ 107 108 if (out_product) { 109 *out_product = product.full; 110 } 111 112 return_ACPI_STATUS(AE_OK); 113 } 114 115 /******************************************************************************* 116 * 117 * FUNCTION: acpi_ut_short_shift_left 118 * 119 * PARAMETERS: operand - 64-bit shift operand 120 * count - 32-bit shift count 121 * out_result - Pointer to where the result is returned 122 * 123 * DESCRIPTION: Perform a short left shift. 124 * 125 ******************************************************************************/ 126 127 acpi_status acpi_ut_short_shift_left(u64 operand, u32 count, u64 *out_result) 128 { 129 union uint64_overlay operand_ovl; 130 131 ACPI_FUNCTION_TRACE(ut_short_shift_left); 132 133 operand_ovl.full = operand; 134 135 if ((count & 63) >= 32) { 136 operand_ovl.part.hi = operand_ovl.part.lo; 137 operand_ovl.part.lo = 0; 138 count = (count & 63) - 32; 139 } 140 ACPI_SHIFT_LEFT_64_BY_32(operand_ovl.part.hi, 141 operand_ovl.part.lo, count); 142 143 /* Return only what was requested */ 144 145 if (out_result) { 146 *out_result = operand_ovl.full; 147 } 148 149 return_ACPI_STATUS(AE_OK); 150 } 151 152 /******************************************************************************* 153 * 154 * FUNCTION: acpi_ut_short_shift_right 155 * 156 * PARAMETERS: operand - 64-bit shift operand 157 * count - 32-bit shift count 158 * out_result - Pointer to where the result is returned 159 * 160 * DESCRIPTION: Perform a short right shift. 161 * 162 ******************************************************************************/ 163 164 acpi_status acpi_ut_short_shift_right(u64 operand, u32 count, u64 *out_result) 165 { 166 union uint64_overlay operand_ovl; 167 168 ACPI_FUNCTION_TRACE(ut_short_shift_right); 169 170 operand_ovl.full = operand; 171 172 if ((count & 63) >= 32) { 173 operand_ovl.part.lo = operand_ovl.part.hi; 174 operand_ovl.part.hi = 0; 175 count = (count & 63) - 32; 176 } 177 ACPI_SHIFT_RIGHT_64_BY_32(operand_ovl.part.hi, 178 operand_ovl.part.lo, count); 179 180 /* Return only what was requested */ 181 182 if (out_result) { 183 *out_result = operand_ovl.full; 184 } 185 186 return_ACPI_STATUS(AE_OK); 187 } 188 #else 189 190 /******************************************************************************* 191 * 192 * FUNCTION: acpi_ut_short_multiply 193 * 194 * PARAMETERS: See function headers above 195 * 196 * DESCRIPTION: Native version of the ut_short_multiply function. 197 * 198 ******************************************************************************/ 199 200 acpi_status 201 acpi_ut_short_multiply(u64 multiplicand, u32 multiplier, u64 *out_product) 202 { 203 204 ACPI_FUNCTION_TRACE(ut_short_multiply); 205 206 /* Return only what was requested */ 207 208 if (out_product) { 209 *out_product = multiplicand * multiplier; 210 } 211 212 return_ACPI_STATUS(AE_OK); 213 } 214 215 /******************************************************************************* 216 * 217 * FUNCTION: acpi_ut_short_shift_left 218 * 219 * PARAMETERS: See function headers above 220 * 221 * DESCRIPTION: Native version of the ut_short_shift_left function. 222 * 223 ******************************************************************************/ 224 225 acpi_status acpi_ut_short_shift_left(u64 operand, u32 count, u64 *out_result) 226 { 227 228 ACPI_FUNCTION_TRACE(ut_short_shift_left); 229 230 /* Return only what was requested */ 231 232 if (out_result) { 233 *out_result = operand << count; 234 } 235 236 return_ACPI_STATUS(AE_OK); 237 } 238 239 /******************************************************************************* 240 * 241 * FUNCTION: acpi_ut_short_shift_right 242 * 243 * PARAMETERS: See function headers above 244 * 245 * DESCRIPTION: Native version of the ut_short_shift_right function. 246 * 247 ******************************************************************************/ 248 249 acpi_status acpi_ut_short_shift_right(u64 operand, u32 count, u64 *out_result) 250 { 251 252 ACPI_FUNCTION_TRACE(ut_short_shift_right); 253 254 /* Return only what was requested */ 255 256 if (out_result) { 257 *out_result = operand >> count; 258 } 259 260 return_ACPI_STATUS(AE_OK); 261 } 262 #endif 263 264 /* 265 * Optional support for 64-bit double-precision integer divide. This code 266 * is configurable and is implemented in order to support 32-bit kernel 267 * environments where a 64-bit double-precision math library is not available. 268 * 269 * Support for a more normal 64-bit divide/modulo (with check for a divide- 270 * by-zero) appears after this optional section of code. 271 */ 272 #ifndef ACPI_USE_NATIVE_DIVIDE 273 274 /******************************************************************************* 275 * 276 * FUNCTION: acpi_ut_short_divide 277 * 278 * PARAMETERS: dividend - 64-bit dividend 279 * divisor - 32-bit divisor 280 * out_quotient - Pointer to where the quotient is returned 281 * out_remainder - Pointer to where the remainder is returned 282 * 283 * RETURN: Status (Checks for divide-by-zero) 284 * 285 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) 286 * divide and modulo. The result is a 64-bit quotient and a 287 * 32-bit remainder. 288 * 289 ******************************************************************************/ 290 291 acpi_status 292 acpi_ut_short_divide(u64 dividend, 293 u32 divisor, u64 *out_quotient, u32 *out_remainder) 294 { 295 union uint64_overlay dividend_ovl; 296 union uint64_overlay quotient; 297 u32 remainder32; 298 299 ACPI_FUNCTION_TRACE(ut_short_divide); 300 301 /* Always check for a zero divisor */ 302 303 if (divisor == 0) { 304 ACPI_ERROR((AE_INFO, "Divide by zero")); 305 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); 306 } 307 308 dividend_ovl.full = dividend; 309 310 /* 311 * The quotient is 64 bits, the remainder is always 32 bits, 312 * and is generated by the second divide. 313 */ 314 ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor, 315 quotient.part.hi, remainder32); 316 317 ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor, 318 quotient.part.lo, remainder32); 319 320 /* Return only what was requested */ 321 322 if (out_quotient) { 323 *out_quotient = quotient.full; 324 } 325 if (out_remainder) { 326 *out_remainder = remainder32; 327 } 328 329 return_ACPI_STATUS(AE_OK); 330 } 331 332 /******************************************************************************* 333 * 334 * FUNCTION: acpi_ut_divide 335 * 336 * PARAMETERS: in_dividend - Dividend 337 * in_divisor - Divisor 338 * out_quotient - Pointer to where the quotient is returned 339 * out_remainder - Pointer to where the remainder is returned 340 * 341 * RETURN: Status (Checks for divide-by-zero) 342 * 343 * DESCRIPTION: Perform a divide and modulo. 344 * 345 ******************************************************************************/ 346 347 acpi_status 348 acpi_ut_divide(u64 in_dividend, 349 u64 in_divisor, u64 *out_quotient, u64 *out_remainder) 350 { 351 union uint64_overlay dividend; 352 union uint64_overlay divisor; 353 union uint64_overlay quotient; 354 union uint64_overlay remainder; 355 union uint64_overlay normalized_dividend; 356 union uint64_overlay normalized_divisor; 357 u32 partial1; 358 union uint64_overlay partial2; 359 union uint64_overlay partial3; 360 361 ACPI_FUNCTION_TRACE(ut_divide); 362 363 /* Always check for a zero divisor */ 364 365 if (in_divisor == 0) { 366 ACPI_ERROR((AE_INFO, "Divide by zero")); 367 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); 368 } 369 370 divisor.full = in_divisor; 371 dividend.full = in_dividend; 372 if (divisor.part.hi == 0) { 373 /* 374 * 1) Simplest case is where the divisor is 32 bits, we can 375 * just do two divides 376 */ 377 remainder.part.hi = 0; 378 379 /* 380 * The quotient is 64 bits, the remainder is always 32 bits, 381 * and is generated by the second divide. 382 */ 383 ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo, 384 quotient.part.hi, partial1); 385 386 ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo, 387 quotient.part.lo, remainder.part.lo); 388 } 389 390 else { 391 /* 392 * 2) The general case where the divisor is a full 64 bits 393 * is more difficult 394 */ 395 quotient.part.hi = 0; 396 normalized_dividend = dividend; 397 normalized_divisor = divisor; 398 399 /* Normalize the operands (shift until the divisor is < 32 bits) */ 400 401 do { 402 ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi, 403 normalized_divisor.part.lo); 404 ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi, 405 normalized_dividend.part.lo); 406 407 } while (normalized_divisor.part.hi != 0); 408 409 /* Partial divide */ 410 411 ACPI_DIV_64_BY_32(normalized_dividend.part.hi, 412 normalized_dividend.part.lo, 413 normalized_divisor.part.lo, quotient.part.lo, 414 partial1); 415 416 /* 417 * The quotient is always 32 bits, and simply requires 418 * adjustment. The 64-bit remainder must be generated. 419 */ 420 partial1 = quotient.part.lo * divisor.part.hi; 421 partial2.full = (u64) quotient.part.lo * divisor.part.lo; 422 partial3.full = (u64) partial2.part.hi + partial1; 423 424 remainder.part.hi = partial3.part.lo; 425 remainder.part.lo = partial2.part.lo; 426 427 if (partial3.part.hi == 0) { 428 if (partial3.part.lo >= dividend.part.hi) { 429 if (partial3.part.lo == dividend.part.hi) { 430 if (partial2.part.lo > dividend.part.lo) { 431 quotient.part.lo--; 432 remainder.full -= divisor.full; 433 } 434 } else { 435 quotient.part.lo--; 436 remainder.full -= divisor.full; 437 } 438 } 439 440 remainder.full = remainder.full - dividend.full; 441 remainder.part.hi = (u32)-((s32)remainder.part.hi); 442 remainder.part.lo = (u32)-((s32)remainder.part.lo); 443 444 if (remainder.part.lo) { 445 remainder.part.hi--; 446 } 447 } 448 } 449 450 /* Return only what was requested */ 451 452 if (out_quotient) { 453 *out_quotient = quotient.full; 454 } 455 if (out_remainder) { 456 *out_remainder = remainder.full; 457 } 458 459 return_ACPI_STATUS(AE_OK); 460 } 461 462 #else 463 464 /******************************************************************************* 465 * 466 * FUNCTION: acpi_ut_short_divide, acpi_ut_divide 467 * 468 * PARAMETERS: See function headers above 469 * 470 * DESCRIPTION: Native versions of the ut_divide functions. Use these if either 471 * 1) The target is a 64-bit platform and therefore 64-bit 472 * integer math is supported directly by the machine. 473 * 2) The target is a 32-bit or 16-bit platform, and the 474 * double-precision integer math library is available to 475 * perform the divide. 476 * 477 ******************************************************************************/ 478 479 acpi_status 480 acpi_ut_short_divide(u64 in_dividend, 481 u32 divisor, u64 *out_quotient, u32 *out_remainder) 482 { 483 484 ACPI_FUNCTION_TRACE(ut_short_divide); 485 486 /* Always check for a zero divisor */ 487 488 if (divisor == 0) { 489 ACPI_ERROR((AE_INFO, "Divide by zero")); 490 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); 491 } 492 493 /* Return only what was requested */ 494 495 if (out_quotient) { 496 *out_quotient = in_dividend / divisor; 497 } 498 if (out_remainder) { 499 *out_remainder = (u32) (in_dividend % divisor); 500 } 501 502 return_ACPI_STATUS(AE_OK); 503 } 504 505 acpi_status 506 acpi_ut_divide(u64 in_dividend, 507 u64 in_divisor, u64 *out_quotient, u64 *out_remainder) 508 { 509 ACPI_FUNCTION_TRACE(ut_divide); 510 511 /* Always check for a zero divisor */ 512 513 if (in_divisor == 0) { 514 ACPI_ERROR((AE_INFO, "Divide by zero")); 515 return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO); 516 } 517 518 /* Return only what was requested */ 519 520 if (out_quotient) { 521 *out_quotient = in_dividend / in_divisor; 522 } 523 if (out_remainder) { 524 *out_remainder = in_dividend % in_divisor; 525 } 526 527 return_ACPI_STATUS(AE_OK); 528 } 529 530 #endif 531