/* ----> 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 pulRemander 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 pullRemander 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; | |
} | |