LinuxKPI: implement mul_u64_u64_div_u64()

Implement mul_u64_u64_div_u64() for an updated iwlwifi driver (though
we do not yet use it there; it is used for in-kernel ptp on wifi).

Sponsored by:	The FreeBSD Foundation

(cherry picked from commit b80ea452375f52a3ab7d82a9aef10da0d89985d9)

Unbalanced parentheses broke the build; re-balance.

Fixes:	b80ea452375f ("LinuxKPI: implement mul_u64_u64_div_u64()")
(cherry picked from commit dabbbebcb0f5ced163454cd08b78e551b4a365b5)

linuxkpi math: fix kassert in math64.h

Include <sys/systm.h> in math64.h, so that KASSERT and bool are
defined, to allow compilation to succeed after
b80ea452375f52a3ab7d82a9aef10da0d89985d9 and dabbbebcb0f5...

(cherry picked from commit b6a61d6836d90ff2756d804eb981a02b0828f496)

1 files changed, 49 insertions, 0 deletions

diff --git a/sys/compat/linuxkpi/common/include/linux/math64.h b/sys/compat/linuxkpi/common/include/linux/math64.h
index 1b00fd71e69f..cae5e30b08df 100644
--- a/sys/compat/linuxkpi/common/include/linux/math64.h
+++ b/sys/compat/linuxkpi/common/include/linux/math64.h
@@ -29,6 +29,7 @@
 #define	_LINUXKPI_LINUX_MATH64_H
 
 #include <sys/stdint.h>
+#include <sys/systm.h>
 
 #define	do_div(n, base) ({			\
 	uint32_t __base = (base);		\
@@ -107,6 +108,54 @@ mul_u64_u32_div(uint64_t x, uint32_t y, uint32_t div)
 }
 
 static inline uint64_t
+mul_u64_u64_div_u64(uint64_t x, uint64_t y, uint64_t z)
+{
+	uint64_t res, rem;
+	uint64_t x1, y1, y1z;
+
+	res = rem = 0;
+	x1 = x;
+	y1z = y / z;
+	y1 = y - y1z * z;
+
+	/*
+	 * INVARIANT: x * y = res * z + rem + (y1 + y1z * z) * x1
+	 * INVARIANT: y1 < z
+	 * INVARIANT: rem < z
+	 */
+	while (x1 > 0) {
+		/* Handle low bit. */
+		if (x1 & 1) {
+			x1 &= ~1;
+			res += y1z;
+			rem += y1;
+			if ((rem < y1) || (rem >= z)) {
+				res += 1;
+				rem -= z;
+			}
+		}
+
+		/* Shift x1 right and (y1 + y1z * z) left */
+		x1 >>= 1;
+		if ((y1 * 2 < y1) || (y1 * 2 >= z)) {
+			y1z = y1z * 2 + 1;
+			y1 = y1 * 2 - z;
+		} else {
+			y1z *= 2;
+			y1 *= 2;
+		}
+	}
+
+	KASSERT(res * z + rem == x * y, ("%s: res %ju * z %ju + rem %ju != "
+	    "x %ju * y %ju", __func__, (uintmax_t)res, (uintmax_t)z,
+	    (uintmax_t)rem, (uintmax_t)x, (uintmax_t)y));
+	KASSERT(rem < z, ("%s: rem %ju >= z %ju\n", __func__,
+	    (uintmax_t)rem, (uintmax_t)z));
+
+	return (res);
+}
+
+static inline uint64_t
 mul_u64_u32_shr(uint64_t x, uint32_t y, unsigned int shift)
 {
 	uint32_t hi, lo;