Fix-Point commented on code in PR #17214:
URL: https://github.com/apache/nuttx/pull/17214#discussion_r2444999887
##########
include/nuttx/lib/math32.h:
##########
@@ -341,6 +355,238 @@ extern "C"
# define div_const_roundnearest(n, base) (((n) + ((base) / 2)) / (base))
#endif
+/* Division optimizing method proposed by T. Granlund and L. Montgomery.
+ * This method converts the runtime-invariant integer division
+ * into multiplication and right-shifting.
+ *
+ * Usage:
+ * If you want to do n/d division where d is an invariant integer,
+ * initialize the param by `invdiv_init_param(d, param)` first,
+ * then do the division by `invdiv(n, param)`.
+ */
+
+/****************************************************************************
+ * Name: invdiv_init_param32
+ *
+ * Description:
+ * Calculate the triple (multiplier, right shift number 1, right shift
+ * number 2) during initialization.
+ *
+ * Input Parameters:
+ * d - The divisor (unsigned integer). d != 0 and d != 1 is required.
+ *
+ * Output Parameters:
+ * param - The invariant division parameter to be cached.
+ *
+ ****************************************************************************/
+
+static inline_function
+void invdiv_init_param32(uint32_t d, FAR invdiv_param32_t *param)
+{
+ int l = log2ceil(d);
+ uint64_t t1 = (uint64_t)1 << 32;
+ uint64_t t2 = (uint64_t)1 << l;
+
+ param->mult = (t1 * (t2 - d)) / d + 1;
+#if ULONG_MAX == 4294967295UL
+ param->shift = l - 1;
+#else
+ param->shift = l;
+#endif
+}
+
+/****************************************************************************
+ * Name: invdiv_u32
+ *
+ * Description:
+ * Return the result of `n / d`
+ * The division is realized by multiplication and right shift,
+ * where d is already converted to invdiv_param_t.
+ *
+ * Input Parameters:
+ * n - The dividend (uint32_t).
+ * param - The invariant division parameter already cached.
+ *
+ * Returned Value:
+ * The result of `n / d`
+ *
+ ****************************************************************************/
+
+static inline_function
+uint64_t invdiv_u32(uint32_t n, FAR const invdiv_param32_t *param)
+{
+ uint8_t sh = param->shift;
+#if ULONG_MAX == 4294967295UL
+ uint32_t m = param->mult;
+ uint32_t t1 = ((uint64_t)m * n) >> 32; /* UMULH if supported */
+ uint32_t t2 = (n - t1) >> 1;
+#else
+ /* This division can be 25% faster using 64-bit register. */
+
+ uint64_t m = param->mult;
+ uint64_t t1 = (m * n) >> 32;
+ uint32_t t2 = n;
+#endif
+
+ return (t1 + t2) >> sh;
+}
+
+/* Helper function to do n bits integer division. */
+
+#define invdiv_udiv_soft(arr, n, q, d) \
+do \
+{ \
+ uint32_t idx; \
+ uint32_t bits_per_idx = sizeof(uint64_t) * 8; \
+ uint32_t bits_max = bits_per_idx * n; \
+ uint64_t reminder = 0ull; \
+ uint64_t high_rem = 0ull; \
+ for (idx = 0; idx < bits_max; idx++) \
+ { \
+ uint32_t bits = bits_max - idx - 1; \
+ uint32_t bits_idx = bits / bits_per_idx; \
+ uint32_t bits_idx_off = bits % bits_per_idx; \
+ reminder <<= 1u; \
+ reminder |= ((arr)[bits_idx] >> bits_idx_off) & 1u; \
+ if (reminder >= (d)) \
+ { \
+ reminder -= (d); \
+ q[bits_idx] |= (1ull << bits_idx_off); \
+ } \
+ else if (high_rem != 0) \
+ { \
+ uint64_t c = 0ull - (d); \
+ high_rem -= 1; \
+ reminder += c; \
+ q[bits_idx] |= (1ull << bits_idx_off); \
+ } \
+ high_rem += (reminder >> (bits_per_idx - 1)) & 1u; \
+ } \
+} \
+while(0)
+
+/* Helper function to calculate 2 64-bit unsigned integers multiplication
+ * The result is the highest half of the 128-bit unsigned integer.
+ */
+
+static inline_function uint64_t invdiv_umulh64(uint64_t a, uint64_t b)
Review Comment:
The bug is caused by the compiler's force-inline behavior under `O0`
optimization. All variables are repeatedly expanded on the stack, leading to
excessive stack usage and even stack overflow. Many functions, including
`invdiv` and `div_const`, can easily trigger this bug.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
