1 /******************************************************************************* 2 * 3 * Module Name: utmath - Integer math support routines 4 * 5 ******************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2016, 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.h" 45 #include "accommon.h" 46 47 48 #define _COMPONENT ACPI_UTILITIES 49 ACPI_MODULE_NAME ("utmath") 50 51 /* 52 * Optional support for 64-bit double-precision integer divide. This code 53 * is configurable and is implemented in order to support 32-bit kernel 54 * environments where a 64-bit double-precision math library is not available. 55 * 56 * Support for a more normal 64-bit divide/modulo (with check for a divide- 57 * by-zero) appears after this optional section of code. 58 */ 59 #ifndef ACPI_USE_NATIVE_DIVIDE 60 61 /* Structures used only for 64-bit divide */ 62 63 typedef struct uint64_struct 64 { 65 UINT32 Lo; 66 UINT32 Hi; 67 68 } UINT64_STRUCT; 69 70 typedef union uint64_overlay 71 { 72 UINT64 Full; 73 UINT64_STRUCT Part; 74 75 } UINT64_OVERLAY; 76 77 78 /******************************************************************************* 79 * 80 * FUNCTION: AcpiUtShortDivide 81 * 82 * PARAMETERS: Dividend - 64-bit dividend 83 * Divisor - 32-bit divisor 84 * OutQuotient - Pointer to where the quotient is returned 85 * OutRemainder - Pointer to where the remainder is returned 86 * 87 * RETURN: Status (Checks for divide-by-zero) 88 * 89 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits) 90 * divide and modulo. The result is a 64-bit quotient and a 91 * 32-bit remainder. 92 * 93 ******************************************************************************/ 94 95 ACPI_STATUS 96 AcpiUtShortDivide ( 97 UINT64 Dividend, 98 UINT32 Divisor, 99 UINT64 *OutQuotient, 100 UINT32 *OutRemainder) 101 { 102 UINT64_OVERLAY DividendOvl; 103 UINT64_OVERLAY Quotient; 104 UINT32 Remainder32; 105 106 107 ACPI_FUNCTION_TRACE (UtShortDivide); 108 109 110 /* Always check for a zero divisor */ 111 112 if (Divisor == 0) 113 { 114 ACPI_ERROR ((AE_INFO, "Divide by zero")); 115 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 116 } 117 118 DividendOvl.Full = Dividend; 119 120 /* 121 * The quotient is 64 bits, the remainder is always 32 bits, 122 * and is generated by the second divide. 123 */ 124 ACPI_DIV_64_BY_32 (0, DividendOvl.Part.Hi, Divisor, 125 Quotient.Part.Hi, Remainder32); 126 127 ACPI_DIV_64_BY_32 (Remainder32, DividendOvl.Part.Lo, Divisor, 128 Quotient.Part.Lo, Remainder32); 129 130 /* Return only what was requested */ 131 132 if (OutQuotient) 133 { 134 *OutQuotient = Quotient.Full; 135 } 136 if (OutRemainder) 137 { 138 *OutRemainder = Remainder32; 139 } 140 141 return_ACPI_STATUS (AE_OK); 142 } 143 144 145 /******************************************************************************* 146 * 147 * FUNCTION: AcpiUtDivide 148 * 149 * PARAMETERS: InDividend - Dividend 150 * InDivisor - Divisor 151 * OutQuotient - Pointer to where the quotient is returned 152 * OutRemainder - Pointer to where the remainder is returned 153 * 154 * RETURN: Status (Checks for divide-by-zero) 155 * 156 * DESCRIPTION: Perform a divide and modulo. 157 * 158 ******************************************************************************/ 159 160 ACPI_STATUS 161 AcpiUtDivide ( 162 UINT64 InDividend, 163 UINT64 InDivisor, 164 UINT64 *OutQuotient, 165 UINT64 *OutRemainder) 166 { 167 UINT64_OVERLAY Dividend; 168 UINT64_OVERLAY Divisor; 169 UINT64_OVERLAY Quotient; 170 UINT64_OVERLAY Remainder; 171 UINT64_OVERLAY NormalizedDividend; 172 UINT64_OVERLAY NormalizedDivisor; 173 UINT32 Partial1; 174 UINT64_OVERLAY Partial2; 175 UINT64_OVERLAY Partial3; 176 177 178 ACPI_FUNCTION_TRACE (UtDivide); 179 180 181 /* Always check for a zero divisor */ 182 183 if (InDivisor == 0) 184 { 185 ACPI_ERROR ((AE_INFO, "Divide by zero")); 186 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 187 } 188 189 Divisor.Full = InDivisor; 190 Dividend.Full = InDividend; 191 if (Divisor.Part.Hi == 0) 192 { 193 /* 194 * 1) Simplest case is where the divisor is 32 bits, we can 195 * just do two divides 196 */ 197 Remainder.Part.Hi = 0; 198 199 /* 200 * The quotient is 64 bits, the remainder is always 32 bits, 201 * and is generated by the second divide. 202 */ 203 ACPI_DIV_64_BY_32 (0, Dividend.Part.Hi, Divisor.Part.Lo, 204 Quotient.Part.Hi, Partial1); 205 206 ACPI_DIV_64_BY_32 (Partial1, Dividend.Part.Lo, Divisor.Part.Lo, 207 Quotient.Part.Lo, Remainder.Part.Lo); 208 } 209 210 else 211 { 212 /* 213 * 2) The general case where the divisor is a full 64 bits 214 * is more difficult 215 */ 216 Quotient.Part.Hi = 0; 217 NormalizedDividend = Dividend; 218 NormalizedDivisor = Divisor; 219 220 /* Normalize the operands (shift until the divisor is < 32 bits) */ 221 222 do 223 { 224 ACPI_SHIFT_RIGHT_64 ( 225 NormalizedDivisor.Part.Hi, NormalizedDivisor.Part.Lo); 226 ACPI_SHIFT_RIGHT_64 ( 227 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo); 228 229 } while (NormalizedDivisor.Part.Hi != 0); 230 231 /* Partial divide */ 232 233 ACPI_DIV_64_BY_32 ( 234 NormalizedDividend.Part.Hi, NormalizedDividend.Part.Lo, 235 NormalizedDivisor.Part.Lo, Quotient.Part.Lo, Partial1); 236 237 /* 238 * The quotient is always 32 bits, and simply requires 239 * adjustment. The 64-bit remainder must be generated. 240 */ 241 Partial1 = Quotient.Part.Lo * Divisor.Part.Hi; 242 Partial2.Full = (UINT64) Quotient.Part.Lo * Divisor.Part.Lo; 243 Partial3.Full = (UINT64) Partial2.Part.Hi + Partial1; 244 245 Remainder.Part.Hi = Partial3.Part.Lo; 246 Remainder.Part.Lo = Partial2.Part.Lo; 247 248 if (Partial3.Part.Hi == 0) 249 { 250 if (Partial3.Part.Lo >= Dividend.Part.Hi) 251 { 252 if (Partial3.Part.Lo == Dividend.Part.Hi) 253 { 254 if (Partial2.Part.Lo > Dividend.Part.Lo) 255 { 256 Quotient.Part.Lo--; 257 Remainder.Full -= Divisor.Full; 258 } 259 } 260 else 261 { 262 Quotient.Part.Lo--; 263 Remainder.Full -= Divisor.Full; 264 } 265 } 266 267 Remainder.Full = Remainder.Full - Dividend.Full; 268 Remainder.Part.Hi = (UINT32) -((INT32) Remainder.Part.Hi); 269 Remainder.Part.Lo = (UINT32) -((INT32) Remainder.Part.Lo); 270 271 if (Remainder.Part.Lo) 272 { 273 Remainder.Part.Hi--; 274 } 275 } 276 } 277 278 /* Return only what was requested */ 279 280 if (OutQuotient) 281 { 282 *OutQuotient = Quotient.Full; 283 } 284 if (OutRemainder) 285 { 286 *OutRemainder = Remainder.Full; 287 } 288 289 return_ACPI_STATUS (AE_OK); 290 } 291 292 #else 293 294 /******************************************************************************* 295 * 296 * FUNCTION: AcpiUtShortDivide, AcpiUtDivide 297 * 298 * PARAMETERS: See function headers above 299 * 300 * DESCRIPTION: Native versions of the UtDivide functions. Use these if either 301 * 1) The target is a 64-bit platform and therefore 64-bit 302 * integer math is supported directly by the machine. 303 * 2) The target is a 32-bit or 16-bit platform, and the 304 * double-precision integer math library is available to 305 * perform the divide. 306 * 307 ******************************************************************************/ 308 309 ACPI_STATUS 310 AcpiUtShortDivide ( 311 UINT64 InDividend, 312 UINT32 Divisor, 313 UINT64 *OutQuotient, 314 UINT32 *OutRemainder) 315 { 316 317 ACPI_FUNCTION_TRACE (UtShortDivide); 318 319 320 /* Always check for a zero divisor */ 321 322 if (Divisor == 0) 323 { 324 ACPI_ERROR ((AE_INFO, "Divide by zero")); 325 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 326 } 327 328 /* Return only what was requested */ 329 330 if (OutQuotient) 331 { 332 *OutQuotient = InDividend / Divisor; 333 } 334 if (OutRemainder) 335 { 336 *OutRemainder = (UINT32) (InDividend % Divisor); 337 } 338 339 return_ACPI_STATUS (AE_OK); 340 } 341 342 ACPI_STATUS 343 AcpiUtDivide ( 344 UINT64 InDividend, 345 UINT64 InDivisor, 346 UINT64 *OutQuotient, 347 UINT64 *OutRemainder) 348 { 349 ACPI_FUNCTION_TRACE (UtDivide); 350 351 352 /* Always check for a zero divisor */ 353 354 if (InDivisor == 0) 355 { 356 ACPI_ERROR ((AE_INFO, "Divide by zero")); 357 return_ACPI_STATUS (AE_AML_DIVIDE_BY_ZERO); 358 } 359 360 361 /* Return only what was requested */ 362 363 if (OutQuotient) 364 { 365 *OutQuotient = InDividend / InDivisor; 366 } 367 if (OutRemainder) 368 { 369 *OutRemainder = InDividend % InDivisor; 370 } 371 372 return_ACPI_STATUS (AE_OK); 373 } 374 375 #endif 376