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