| /* ----> DO NOT REMOVE THE FOLLOWING NOTICE <---- |
| |
| Copyright (c) 2014-2015 Datalight, Inc. |
| All Rights Reserved Worldwide. |
| |
| This program is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; use version 2 of the License. |
| |
| This program is distributed in the hope that it will be useful, |
| but "AS-IS," WITHOUT ANY WARRANTY; without even the implied warranty |
| of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License along |
| with this program; if not, write to the Free Software Foundation, Inc., |
| 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| */ |
| /* Businesses and individuals that for commercial or other reasons cannot |
| comply with the terms of the GPLv2 license may obtain a commercial license |
| before incorporating Reliance Edge into proprietary software for |
| distribution in any form. Visit http://www.datalight.com/reliance-edge for |
| more information. |
| */ |
| /** @file |
| @brief Implements routines for certain 64-bit math operations and simulated |
| floating point. |
| |
| RedUint64DivMod32() and RedUint64DivMod64() are derived from code at |
| http://www.hackersdelight.org. This web site states explicitly that "You |
| are free to use, copy, and distribute any of the code on this web site, |
| whether modified by you or not. You need not give attribution." |
| */ |
| #include <redfs.h> |
| #include <redtestutils.h> |
| |
| |
| static uint32_t nlz64(uint64_t ullValue); |
| |
| |
| /** @brief Return a ratio value formatted as a floating point string accurate to |
| the specified number of decimal places. |
| |
| The function exists to provide floating point style output without using |
| any actual floating point types. |
| |
| This function may scale the numbers down to avoid overflow at the high end. |
| Likewise, potential divide-by-zero errors are internally avoided. Here are |
| some examples: |
| |
| Dividend | Divisor | DecPlaces | Result |
| -------- | ------- | --------- | ------ |
| 12133 | 28545 | 2 | "0.42" |
| 1539 | 506 | 2 | "3.04" |
| |
| To get a number formatted as a percentage, take the take the portion of the |
| total (normally the smaller part), multiply it by 100, and pass it to this |
| function as the Dividend, pass the "total" value to this function as the |
| Divisor, and specify the desired number of decimal places. |
| |
| For example, if you have a disk format overhead value of N blocks out of a |
| total of Y blocks on the disk, and you want to display the format overhead |
| as a percentage, you would use a function call |
| similar to: |
| |
| ~~~{.c} |
| RedRatio(szBuffer, sizeof(szBuffer), N*100U, Y, 2U); |
| ~~~ |
| |
| If N=145, Y=4096, and decimal places is 2, the resulting output would be |
| "3.54". |
| |
| The string returned will always be null-terminated, even if it means |
| stomping on the least significant decimal digit. |
| |
| If either the dividend or divisor values are zero, the string "0.0" will be |
| returned, with the prescribed number of decimal places. |
| |
| @note This function has "reasonable" limits which meet the needs of the |
| various supplemental utilities which use this function. Extremely |
| large ratios, or using many decimal places may not function as |
| desired. |
| |
| Parameters: |
| @param pBuffer A pointer to the buffer in which to store the null |
| terminated results. |
| @param ulBufferLen The length of the output buffer. |
| @param ullDividend The "total" value to divide. |
| @param ullDivisor The portion of ullDividend for which to calculate the |
| ratio (may be greater than ulDividend). |
| @param ulDecPlaces The number of decimal places to use, from 0 to 9. |
| |
| @return @p pBuffer. |
| */ |
| char *RedRatio( |
| char *pBuffer, |
| uint32_t ulBufferLen, |
| uint64_t ullDividend, |
| uint64_t ullDivisor, |
| uint32_t ulDecPlaces) |
| { |
| REDASSERT(pBuffer != NULL); |
| REDASSERT(ulBufferLen > 0U); |
| REDASSERT(ulDecPlaces <= 9U); /* arbitrary */ |
| |
| if((ullDivisor > 0U) && (ullDividend > 0U)) |
| { |
| uint32_t ii; |
| uint32_t ulFactor = 1U; |
| uint64_t ullDecimal; |
| uint64_t ullTemp; |
| |
| for(ii = 1U; ii <= ulDecPlaces; ii++) |
| { |
| ulFactor *= 10U; |
| } |
| |
| ullDecimal = RedMulDiv64(ullDividend, ulFactor, ullDivisor); |
| |
| /* Shouldn't really be calling this function in a situation where we |
| can overflow at this point... |
| */ |
| REDASSERT(ullDecimal != UINT64_MAX); |
| |
| if(ullDivisor <= ullDividend) |
| { |
| uint32_t ulDecimal; |
| |
| (void)RedUint64DivMod32(ullDecimal, ulFactor, &ulDecimal); |
| ullDecimal = ulDecimal; |
| } |
| |
| ullTemp = RedUint64DivMod64(ullDividend, ullDivisor, NULL); |
| |
| if(ulDecPlaces > 0U) |
| { |
| RedSNPrintf(pBuffer, ulBufferLen, "%llu.%0*llu", (unsigned long long)ullTemp, |
| (unsigned)ulDecPlaces, (unsigned long long)ullDecimal); |
| } |
| else |
| { |
| RedSNPrintf(pBuffer, ulBufferLen, "%llu", (unsigned long long)ullTemp); |
| } |
| } |
| else |
| { |
| /* If either the dividend or divisor is zero, then just output a "0.0" |
| string with the prescribed number of decimal places. |
| */ |
| if(ulDecPlaces > 0U) |
| { |
| RedSNPrintf(pBuffer, ulBufferLen, "0.%0*u", (unsigned)ulDecPlaces, 0U); |
| } |
| else |
| { |
| RedStrNCpy(pBuffer, "0", ulBufferLen); |
| } |
| } |
| |
| /* Ensure the returned buffer is always null-terminated |
| */ |
| pBuffer[ulBufferLen - 1U] = '\0'; |
| |
| return pBuffer; |
| } |
| |
| |
| /** @brief Multiply 64-bit and 32-bit numbers, and divide by a 64-bit number, |
| returning a 64-bit result. |
| |
| @note This function may return an approximate value if multiplying |
| @p ullBase and @p ulMultplier results in a number larger than 64-bits |
| _and_ this cannot be avoided by scaling. |
| |
| @param ullBase The base 64-bit number number. |
| @param ulMultiplier The 32-bit number by which to multiply. |
| @param ullDivisor The 64-bit number by which to divide. |
| |
| @return The 64-bit unsigned integer result. Always returns zero if either |
| @p ullBase or @p ulMultiplier are zero (regardless what |
| @p ullDivisor is). Returns UINT64_MAX if an overflow condition |
| occurred, or if @p ullDivisor is zero. |
| */ |
| uint64_t RedMulDiv64( |
| uint64_t ullBase, |
| uint32_t ulMultiplier, |
| uint64_t ullDivisor) |
| { |
| uint64_t ullTemp; |
| |
| /* Result would always be zero if either of these are zero. Specifically |
| test this case before looking for a zero divisor. |
| */ |
| if((ullBase == 0U) || (ulMultiplier == 0U)) |
| { |
| return 0U; |
| } |
| |
| if(ullDivisor == 0U) |
| { |
| return UINT64_MAX; |
| } |
| |
| /* Since we don't have the ability (yet) to use 128-bit numbers, we jump |
| through the following hoops (in order) to try to determine the proper |
| results without losing precision: |
| |
| 1) Shift the divisor and one of the multiplicands as many times as is |
| necessary to reduce the scale -- only if it can be done without |
| losing precision. |
| 2) Divide one of the multiplicands by the divisor first, but only if it |
| divides evenly, preserving precision. |
| 3) Same as #2, but try it for the other multiplicand. |
| 4) Last ditch, divide the larger multiplicand by the divisor first, then |
| do the multiply. This <WILL> lose precision. |
| |
| These solutions are identified as CODE-PATHs #1-4 which are used to |
| identify the matching tests in dltmain.c. |
| |
| Note that execution might partially include CODE-PATH #1 up until |
| shifting can no longer be done without losing precision. In that case, |
| one of the three remaining options will be used. |
| */ |
| |
| ullTemp = RedUint64DivMod32(UINT64_MAX, ulMultiplier, NULL); |
| while(ullBase > ullTemp) |
| { |
| uint64_t ullMod; |
| uint64_t ullBaseTemp; |
| uint64_t ullWideMultiplier; |
| |
| /* CODE-PATH #1 |
| */ |
| /* So long as ulDivisor, and at least one of the other numbers, are |
| evenly divisible by 2, we can scale the numbers so the result does |
| not overflow the intermediate 64-bit value. |
| */ |
| if((ullDivisor & 1U) == 0U) |
| { |
| if((ullBase & 1U) == 0U) |
| { |
| /* CODE-PATH #1a |
| */ |
| ullDivisor >>= 1U; |
| ullBase >>= 1U; |
| continue; |
| } |
| |
| if(((ulMultiplier & 1U) == 0U) && ((ullTemp & UINT64_SUFFIX(0x8000000000000000)) == 0U)) |
| { |
| /* CODE-PATH #1b |
| */ |
| ullDivisor >>= 1U; |
| ulMultiplier >>= 1U; |
| ullTemp <<= 1U; |
| continue; |
| } |
| } |
| |
| /* If we get to this point, the above method (#1) cannot be used |
| because not enough of the numbers are even long enough to scale the |
| operands down. We'll see if either multiplicand is evenly divisble |
| by ulDivisor, and if so, do the divide first, then the multiply. |
| (Note that once we get to this point, we will never exercise the |
| while{} loop anymore.) |
| */ |
| |
| /* CODE-PATH #2 |
| */ |
| ullBaseTemp = RedUint64DivMod64(ullBase, ullDivisor, &ullMod); |
| if(ullMod == 0U) |
| { |
| /* Evenly divides, so check that we won't overflow, and finish up. |
| */ |
| ullBase = ullBaseTemp; |
| if(ullBase > ullTemp) |
| { |
| return UINT64_MAX; |
| } |
| else |
| { |
| /* We've validated that this will not overflow. |
| */ |
| ullBase *= ulMultiplier; |
| return ullBase; |
| } |
| } |
| |
| /* CODE-PATH #3 |
| */ |
| ullWideMultiplier = RedUint64DivMod64(ulMultiplier, ullDivisor, &ullMod); |
| if(ullMod == 0U) |
| { |
| /* Evenly divides, so check that we won't overflow, and finish up. |
| */ |
| |
| /* Must recalculate ullTemp relative to ullBase |
| */ |
| ullTemp = RedUint64DivMod64(UINT64_MAX, ullBase, NULL); |
| if(ullWideMultiplier > ullTemp) |
| { |
| return UINT64_MAX; |
| } |
| else |
| { |
| uint32_t ulNarrowMultiplier = (uint32_t)ullWideMultiplier; |
| |
| /* We've validated that this will not overflow. |
| */ |
| ullBase *= ulNarrowMultiplier; |
| return ullBase; |
| } |
| } |
| |
| /* CODE-PATH #4 |
| |
| Neither of the multipliers is evenly divisible by the divisor, so |
| just punt and divide the larger number first, then do the final |
| multiply. |
| |
| All the other attempts above would preserve precision -- this is the |
| only case where precision may be lost. |
| */ |
| |
| /* If necessary reverse the ullBase and ulMultiplier operands so that |
| ullBase contains the larger of the two values. |
| */ |
| if(ullBase < ulMultiplier) |
| { |
| uint32_t ulTemp = ulMultiplier; |
| |
| ulMultiplier = (uint32_t)ullBase; |
| ullBase = ulTemp; |
| } |
| |
| ullBase = RedUint64DivMod64(ullBase, ullDivisor, NULL); |
| ullTemp = RedUint64DivMod32(UINT64_MAX, ulMultiplier, NULL); |
| if(ullBase > ullTemp) |
| { |
| return UINT64_MAX; |
| } |
| else |
| { |
| ullBase *= ulMultiplier; |
| return ullBase; |
| } |
| } |
| |
| /* We only get to this point if either there was never any chance of |
| overflow, or if the pure shifting mechanism succeeded in reducing |
| the scale so overflow is not a problem. |
| */ |
| |
| ullBase *= ulMultiplier; |
| ullBase = RedUint64DivMod64(ullBase, ullDivisor, NULL); |
| |
| return ullBase; |
| } |
| |
| |
| /** @brief Divide a 64-bit value by a 32-bit value, returning the quotient and |
| the remainder. |
| |
| Essentially this function does the following: |
| |
| ~~~{.c} |
| if(pulRemainder != NULL) |
| { |
| *pulRemainder = (uint32_t)(ullDividend % ulDivisor); |
| } |
| return ullDividend / ulDivisor; |
| ~~~ |
| |
| However, it does so without ever actually dividing/modulating a 64-bit |
| value, since such operations are not allowed in all environments. |
| |
| @param ullDividend The value to divide. |
| @param ulDivisor The value to divide by. |
| @param pulRemainder Populated with the remainder; may be NULL. |
| |
| @return The quotient (result of the division). |
| */ |
| uint64_t RedUint64DivMod32( |
| uint64_t ullDividend, |
| uint32_t ulDivisor, |
| uint32_t *pulRemainder) |
| { |
| uint64_t ullQuotient; |
| uint32_t ulResultRemainder; |
| |
| /* Check for divide by zero. |
| */ |
| if(ulDivisor == 0U) |
| { |
| REDERROR(); |
| |
| /* Nonsense value if no asserts. |
| */ |
| ullQuotient = UINT64_SUFFIX(0xFFFFFFFFFFFFFBAD); |
| ulResultRemainder = 0xFFFFFBADU; |
| } |
| else if(ullDividend <= UINT32_MAX) |
| { |
| uint32_t ulDividend = (uint32_t)ullDividend; |
| |
| ullQuotient = ulDividend / ulDivisor; |
| ulResultRemainder = ulDividend % ulDivisor; |
| } |
| else |
| { |
| uint32_t ulResultHi; |
| uint32_t ulResultLo; |
| uint32_t ulRemainder; |
| uint8_t bIndex; |
| uint32_t ulThisDivision; |
| uint32_t ulMask; |
| uint8_t ucNextValue; |
| uint32_t ulInterimHi, ulInterimLo; |
| uint32_t ulLowDword = (uint32_t)ullDividend; |
| uint32_t ulHighDword = (uint32_t)(ullDividend >> 32U); |
| |
| /* Compute the high part and get the remainder |
| */ |
| ulResultHi = ulHighDword / ulDivisor; |
| ulResultLo = 0U; |
| ulRemainder = ulHighDword % ulDivisor; |
| |
| /* Compute the low part |
| */ |
| ulMask = 0xFF000000U; |
| for(bIndex = 0U; bIndex < sizeof(uint32_t); bIndex++) |
| { |
| ucNextValue = (uint8_t)((ulLowDword & ulMask) >> ((sizeof(uint32_t) - 1U - bIndex) * 8U)); |
| ulInterimHi = ulRemainder >> 24U; |
| ulInterimLo = (ulRemainder << 8U) | ucNextValue; |
| ulThisDivision = 0U; |
| while(ulInterimHi != 0U) |
| { |
| uint64_t ullInterim = ((uint64_t)ulInterimHi << 32U) + ulInterimLo; |
| |
| ullInterim -= ulDivisor; |
| ulThisDivision++; |
| |
| ulInterimHi = (uint32_t)(ullInterim >> 32U); |
| ulInterimLo = (uint32_t)ullInterim; |
| } |
| ulThisDivision += ulInterimLo / ulDivisor; |
| ulRemainder = ulInterimLo % ulDivisor; |
| ulResultLo <<= 8U; |
| ulResultLo += ulThisDivision; |
| ulMask >>= 8U; |
| } |
| |
| ullQuotient = ((uint64_t)ulResultHi << 32U) + ulResultLo; |
| ulResultRemainder = (uint32_t)(ullDividend - (ullQuotient * ulDivisor)); |
| } |
| |
| if(pulRemainder != NULL) |
| { |
| *pulRemainder = ulResultRemainder; |
| } |
| |
| return ullQuotient; |
| } |
| |
| |
| /** @brief Divide a 64-bit value by a 64-bit value, returning the quotient and |
| the remainder. |
| |
| Essentially this function does the following: |
| |
| ~~~{.c} |
| if(pullRemainder != NULL) |
| { |
| *pullRemainder = ullDividend % ullDivisor; |
| } |
| return ullDividend / ullDivisor; |
| ~~~ |
| |
| However, it does so without ever actually dividing/modulating a 64-bit |
| value, since such operations are not allowed in all environments. |
| |
| @param ullDividend The value to divide. |
| @param ullDivisor The value to divide by. |
| @param pullRemainder Populated with the remainder; may be NULL. |
| |
| @return The quotient (result of the division). |
| */ |
| uint64_t RedUint64DivMod64( |
| uint64_t ullDividend, |
| uint64_t ullDivisor, |
| uint64_t *pullRemainder) |
| { |
| /* The variables u0, u1, etc. take on only 32-bit values, but they are |
| declared uint64_t to avoid some compiler warning messages and to avoid |
| some unnecessary EXTRs that the compiler would put in, to convert |
| uint64_ts to ints. |
| */ |
| uint64_t u0; |
| uint64_t u1; |
| uint64_t q0; |
| uint64_t q1; |
| uint64_t ullQuotient; |
| |
| /* First the procedure takes care of the case in which the divisor is a |
| 32-bit quantity. There are two subcases: (1) If the left half of the |
| dividend is less than the divisor, one execution of RedUint64DivMod32() |
| is all that is required (overflow is not possible). (2) Otherwise it |
| does two divisions, using the grade school method. |
| */ |
| |
| if((ullDivisor >> 32U) == 0U) |
| { |
| if((ullDividend >> 32U) < ullDivisor) |
| { |
| /* If ullDividend/ullDivisor cannot overflow, just do one division. |
| */ |
| ullQuotient = RedUint64DivMod32(ullDividend, (uint32_t)ullDivisor, NULL); |
| } |
| else |
| { |
| uint32_t k; |
| |
| /* If ullDividend/ullDivisor would overflow: |
| */ |
| |
| /* Break ullDividend up into two halves. |
| */ |
| u1 = ullDividend >> 32U; |
| u0 = ullDividend & 0xFFFFFFFFU; |
| |
| /* First quotient digit and first remainder. |
| */ |
| q1 = RedUint64DivMod32(u1, (uint32_t)ullDivisor, &k); |
| |
| /* 2nd quot. digit. |
| */ |
| q0 = RedUint64DivMod32(((uint64_t)k << 32U) + u0, (uint32_t)ullDivisor, NULL); |
| |
| ullQuotient = (q1 << 32U) + q0; |
| } |
| } |
| else |
| { |
| uint64_t n; |
| uint64_t v1; |
| |
| n = nlz64(ullDivisor); /* 0 <= n <= 31. */ |
| v1 = (ullDivisor << n) >> 32U; /* Normalize the divisor so its MSB is 1. */ |
| u1 = ullDividend >> 1U; /* To ensure no overflow. */ |
| |
| /* Get quotient from divide unsigned insn. |
| */ |
| q1 = RedUint64DivMod32(u1, (uint32_t)v1, NULL); |
| |
| q0 = (q1 << n) >> 31U; /* Undo normalization and division of ullDividend by 2. */ |
| |
| /* Make q0 correct or too small by 1. |
| */ |
| if(q0 != 0U) |
| { |
| q0--; |
| } |
| |
| if((ullDividend - (q0 * ullDivisor)) >= ullDivisor) |
| { |
| q0++; /* Now q0 is correct. */ |
| } |
| |
| ullQuotient = q0; |
| } |
| |
| if(pullRemainder != NULL) |
| { |
| *pullRemainder = ullDividend - (ullQuotient * ullDivisor); |
| } |
| |
| return ullQuotient; |
| } |
| |
| |
| /** @brief Compute the number of leading zeroes in a 64-bit value. |
| |
| @param ullValue The value for which to compute the NLZ. |
| |
| @return The number of leading zeroes in @p ullValue. |
| */ |
| static uint32_t nlz64( |
| uint64_t ullValue) |
| { |
| uint32_t n; |
| |
| if(ullValue == 0U) |
| { |
| n = 64U; |
| } |
| else |
| { |
| uint64_t x = ullValue; |
| |
| n = 0U; |
| |
| if(x <= UINT64_SUFFIX(0x00000000FFFFFFFF)) |
| { |
| n += 32U; |
| x <<= 32U; |
| } |
| |
| if(x <= UINT64_SUFFIX(0x0000FFFFFFFFFFFF)) |
| { |
| n += 16U; |
| x <<= 16U; |
| } |
| |
| if(x <= UINT64_SUFFIX(0x00FFFFFFFFFFFFFF)) |
| { |
| n += 8U; |
| x <<= 8U; |
| } |
| |
| if(x <= UINT64_SUFFIX(0x0FFFFFFFFFFFFFFF)) |
| { |
| n += 4U; |
| x <<= 4U; |
| } |
| |
| if(x <= UINT64_SUFFIX(0x3FFFFFFFFFFFFFFF)) |
| { |
| n += 2U; |
| x <<= 2U; |
| } |
| |
| if(x <= UINT64_SUFFIX(0x7FFFFFFFFFFFFFFF)) |
| { |
| n += 1; |
| } |
| } |
| |
| return n; |
| } |
| |
