[PATCH] replace timeconst bc script with an sh script

[PATCH] replace timeconst bc script with an sh script

[Ethan Sommer]

removes the bc build dependency introduced when timeconst.pl was
replaced by timeconst.bc

Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
---
 Kbuild                   |   4 +-
 kernel/time/timeconst.bc | 117 --------------------------------------
 kernel/time/timeconst.sh | 118 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 120 insertions(+), 119 deletions(-)
 delete mode 100644 kernel/time/timeconst.bc
 create mode 100755 kernel/time/timeconst.sh

diff --git a/Kbuild b/Kbuild
index 8637fd14135f..2b5f2957cf04 100644
--- a/Kbuild
+++ b/Kbuild
@@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h
 
 targets += $(timeconst-file)
 
-filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
+filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
 
-$(timeconst-file): kernel/time/timeconst.bc FORCE
+$(timeconst-file): kernel/time/timeconst.sh FORCE
 	$(call filechk,gentimeconst)
 
 #####
diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
deleted file mode 100644
index 7ed0e0fb5831..000000000000
--- a/kernel/time/timeconst.bc
+++ /dev/null
@@ -1,117 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-
-scale=0
-
-define gcd(a,b) {
-	auto t;
-	while (b) {
-		t = b;
-		b = a % b;
-		a = t;
-	}
-	return a;
-}
-
-/* Division by reciprocal multiplication. */
-define fmul(b,n,d) {
-       return (2^b*n+d-1)/d;
-}
-
-/* Adjustment factor when a ceiling value is used.  Use as:
-   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
-define fadj(b,n,d) {
-	auto v;
-	d = d/gcd(n,d);
-	v = 2^b*(d-1)/d;
-	return v;
-}
-
-/* Compute the appropriate mul/adj values as well as a shift count,
-   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
-   a shift value will be correct in the signed integer range and off
-   by at most one in the upper half of the unsigned range. */
-define fmuls(b,n,d) {
-	auto s, m;
-	for (s = 0; 1; s++) {
-		m = fmul(s,n,d);
-		if (m >= 2^(b-1))
-			return s;
-	}
-	return 0;
-}
-
-define timeconst(hz) {
-	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
-	print "/* Time conversion constants for HZ == ", hz, " */\n"
-	print "\n"
-
-	print "#ifndef KERNEL_TIMECONST_H\n"
-	print "#define KERNEL_TIMECONST_H\n\n"
-
-	print "#include <linux/param.h>\n"
-	print "#include <linux/types.h>\n\n"
-
-	print "#if HZ != ", hz, "\n"
-	print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n"
-	print "#endif\n\n"
-
-	if (hz < 2) {
-		print "#error Totally bogus HZ value!\n"
-	} else {
-		s=fmuls(32,1000,hz)
-		obase=16
-		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
-		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000)
-		obase=16
-		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
-		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
-		obase=10
-		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000)
-		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
-		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
-		print "\n"
-
-		s=fmuls(32,1000000,hz)
-		obase=16
-		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n"
-		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000000)
-		obase=16
-		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n"
-		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n"
-		obase=10
-		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000000)
-		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
-		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
-
-		cd=gcd(hz,1000000000)
-		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
-		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
-		print "\n"
-
-		print "#endif /* KERNEL_TIMECONST_H */\n"
-	}
-	halt
-}
-
-hz = read();
-timeconst(hz)
diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
new file mode 100755
index 000000000000..df821988acbf
--- /dev/null
+++ b/kernel/time/timeconst.sh
@@ -0,0 +1,118 @@
+#!/bin/sh
+# SPDX-License-Identifier: GPL-2.0
+
+if [ -z "$1" ]; then
+	printf '%s <HZ>\n' "$0"
+	exit 1
+else
+	hz="$1"
+fi
+
+# 2 to the power of n
+pot() {
+	local i=1
+    local j=1
+	while [ "${j}" -le "$1" ]; do
+		i="$((i * 2))"
+        j="$((j + 1))"
+	done
+	printf '%s\n' "${i}"
+}
+
+# Greatest common denominator
+gcd() {
+	local i="$1"
+	local j="$2"
+	local k
+	while [ "${j}" -ne 0 ]; do
+		k="${j}"
+		j="$((i % j))"
+		i="${k}"
+	done
+	printf '%s\n' "${i}"
+}
+
+# Division by reciprocal multiplication.
+fmul() {
+	printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
+}
+
+# Adjustment factor when a ceiling value is used.
+fadj() {
+	local i="$(gcd "$2" "$3")"
+	printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
+}
+
+# Compute the appropriate mul/adj values as well as a shift count,
+# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
+# a shift value will be correct in the signed integer range and off
+# by at most one in the upper half of the unsigned range.
+fmuls() {
+	local i=0
+    local j
+	while true; do
+        j="$(fmul "${i}" "$2" "$3")"
+		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
+			printf '%s\n' "${i}" && return
+		fi
+		i="$((i + 1))"
+	done
+}
+
+printf '/* Automatically generated by %s */\n' "$0"
+printf '/* Time conversion constants for HZ == %s */\n\n' "$1"
+
+printf '#ifndef KERNEL_TIMECONST_H\n'
+printf '#define KERNEL_TIMECONST_H\n\n'
+
+printf '#include <linux/param.h>\n'
+printf '#include <linux/types.h>\n\n'
+
+printf '#if HZ != %s\n' "$1"
+printf '#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n'
+printf '#endif\n\n'
+
+if [ "$1" -lt 2 ]; then
+	printf '#error Totally bogus HZ value!\n'
+	exit 1
+fi
+
+s="$(fmuls 32 1000 "$1")"
+printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000)"
+printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}"
+
+cd="$(gcd "$1" 1000)"
+printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))"
+printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))"
+
+s="$(fmuls 32 1000000 "$1")"
+printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000000)"
+printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}"
+
+cd="$(gcd "$1" 1000000)"
+printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))"
+printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))"
+
+cd="$(gcd "$1" 1000000000)"
+printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))"
+printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))"
+
+printf '\n#endif /* KERNEL_TIMECONST_H */\n'
-- 
2.22.0

Re: [PATCH] replace timeconst bc script with an sh script

[Kieran Bingham]

Hi Ethan,

Thank you for the patch,

On 20/06/2019 07:22, Ethan Sommer wrote:
> removes the bc build dependency introduced when timeconst.pl was
> replaced by timeconst.bc

Does this introduction of bc cause you problems when building?

Documentation/process/changes.rst states that "You will need bc to build
kernels 3.10 and higher"

Is bc used elsewhere in the kernel?

If this is the only use of BC and it is no longer a dependency - the
process document should be updated.


Though I see uses at:
   tools/testing/selftests/net/forwarding/lib.sh


There is a small issue with quotes highlighted below, and the only other
(really minor) comment is performance.

time (echo 1000 | bc -q ./kernel/time/timeconst.bc)
  real	0m0.006s
  user	0m0.006s
  sys	0m0.000s

vs
time /tmp/timeconst.sh 1000
  real	0m0.176s
  user	0m0.141s
  sys	0m0.050s


So that's 176 milliseconds vs 6. (on an i7 gen8 laptop) which probably
isn't going to affect things too much on the scale of building a kernel.
But I measured it so I thought it was worth posting the results.


--
Regards

Kieran


> Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
> ---
>  Kbuild                   |   4 +-
>  kernel/time/timeconst.bc | 117 --------------------------------------
>  kernel/time/timeconst.sh | 118 +++++++++++++++++++++++++++++++++++++++
>  3 files changed, 120 insertions(+), 119 deletions(-)
>  delete mode 100644 kernel/time/timeconst.bc
>  create mode 100755 kernel/time/timeconst.sh
> 
> diff --git a/Kbuild b/Kbuild
> index 8637fd14135f..2b5f2957cf04 100644
> --- a/Kbuild
> +++ b/Kbuild
> @@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h
>  
>  targets += $(timeconst-file)
>  
> -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
> +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
>  
> -$(timeconst-file): kernel/time/timeconst.bc FORCE
> +$(timeconst-file): kernel/time/timeconst.sh FORCE
>  	$(call filechk,gentimeconst)
>  
>  #####
> diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
> deleted file mode 100644
> index 7ed0e0fb5831..000000000000
> --- a/kernel/time/timeconst.bc
> +++ /dev/null
> @@ -1,117 +0,0 @@
> -/* SPDX-License-Identifier: GPL-2.0 */
> -
> -scale=0
> -
> -define gcd(a,b) {
> -	auto t;
> -	while (b) {
> -		t = b;
> -		b = a % b;
> -		a = t;
> -	}
> -	return a;
> -}
> -
> -/* Division by reciprocal multiplication. */
> -define fmul(b,n,d) {
> -       return (2^b*n+d-1)/d;
> -}
> -
> -/* Adjustment factor when a ceiling value is used.  Use as:
> -   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
> -define fadj(b,n,d) {
> -	auto v;
> -	d = d/gcd(n,d);
> -	v = 2^b*(d-1)/d;
> -	return v;
> -}
> -
> -/* Compute the appropriate mul/adj values as well as a shift count,
> -   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
> -   a shift value will be correct in the signed integer range and off
> -   by at most one in the upper half of the unsigned range. */
> -define fmuls(b,n,d) {
> -	auto s, m;
> -	for (s = 0; 1; s++) {
> -		m = fmul(s,n,d);
> -		if (m >= 2^(b-1))
> -			return s;
> -	}
> -	return 0;
> -}
> -
> -define timeconst(hz) {
> -	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
> -	print "/* Time conversion constants for HZ == ", hz, " */\n"
> -	print "\n"
> -
> -	print "#ifndef KERNEL_TIMECONST_H\n"
> -	print "#define KERNEL_TIMECONST_H\n\n"
> -
> -	print "#include <linux/param.h>\n"
> -	print "#include <linux/types.h>\n\n"
> -
> -	print "#if HZ != ", hz, "\n"
> -	print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n"
> -	print "#endif\n\n"
> -
> -	if (hz < 2) {
> -		print "#error Totally bogus HZ value!\n"
> -	} else {
> -		s=fmuls(32,1000,hz)
> -		obase=16
> -		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
> -		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
> -		obase=10
> -		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
> -
> -		s=fmuls(32,hz,1000)
> -		obase=16
> -		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
> -		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
> -		obase=10
> -		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
> -
> -		obase=10
> -		cd=gcd(hz,1000)
> -		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
> -		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
> -		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
> -		print "\n"
> -
> -		s=fmuls(32,1000000,hz)
> -		obase=16
> -		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n"
> -		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n"
> -		obase=10
> -		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
> -
> -		s=fmuls(32,hz,1000000)
> -		obase=16
> -		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n"
> -		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n"
> -		obase=10
> -		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
> -
> -		obase=10
> -		cd=gcd(hz,1000000)
> -		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
> -		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
> -		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
> -
> -		cd=gcd(hz,1000000000)
> -		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
> -		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
> -		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
> -		print "\n"
> -
> -		print "#endif /* KERNEL_TIMECONST_H */\n"
> -	}
> -	halt
> -}
> -
> -hz = read();
> -timeconst(hz)
> diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
> new file mode 100755
> index 000000000000..df821988acbf
> --- /dev/null
> +++ b/kernel/time/timeconst.sh
> @@ -0,0 +1,118 @@
> +#!/bin/sh
> +# SPDX-License-Identifier: GPL-2.0
> +
> +if [ -z "$1" ]; then
> +	printf '%s <HZ>\n' "$0"
> +	exit 1
> +else
> +	hz="$1"
> +fi
> +
> +# 2 to the power of n
> +pot() {
> +	local i=1
> +    local j=1
> +	while [ "${j}" -le "$1" ]; do
> +		i="$((i * 2))"
> +        j="$((j + 1))"
> +	done
> +	printf '%s\n' "${i}"
> +}
> +
> +# Greatest common denominator
> +gcd() {
> +	local i="$1"
> +	local j="$2"
> +	local k
> +	while [ "${j}" -ne 0 ]; do
> +		k="${j}"
> +		j="$((i % j))"
> +		i="${k}"
> +	done
> +	printf '%s\n' "${i}"
> +}
> +
> +# Division by reciprocal multiplication.
> +fmul() {
> +	printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
> +}
> +
> +# Adjustment factor when a ceiling value is used.
> +fadj() {
> +	local i="$(gcd "$2" "$3")"
> +	printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
> +}
> +
> +# Compute the appropriate mul/adj values as well as a shift count,
> +# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
> +# a shift value will be correct in the signed integer range and off
> +# by at most one in the upper half of the unsigned range.
> +fmuls() {
> +	local i=0
> +    local j
> +	while true; do
> +        j="$(fmul "${i}" "$2" "$3")"
> +		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
> +			printf '%s\n' "${i}" && return
> +		fi
> +		i="$((i + 1))"
> +	done
> +}
> +
> +printf '/* Automatically generated by %s */\n' "$0"
> +printf '/* Time conversion constants for HZ == %s */\n\n' "$1"
> +
> +printf '#ifndef KERNEL_TIMECONST_H\n'
> +printf '#define KERNEL_TIMECONST_H\n\n'
> +
> +printf '#include <linux/param.h>\n'
> +printf '#include <linux/types.h>\n\n'
> +
> +printf '#if HZ != %s\n' "$1"
> +printf '#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n'

This generates an incorrect output:

diff /tmp/bc.timed /tmp/sh.timed
1c1
< /* Automatically generated by kernel/time/timeconst.bc */
---
> /* Automatically generated by /tmp/timeconst.sh */
11c11
< #error "include/generated/timeconst.h has the wrong HZ value!"
---
> #error \qinclude/generated/timeconst.h has the wrong HZ value!\q
    here  ^                                             and here ^



> +printf '#endif\n\n'
> +
> +if [ "$1" -lt 2 ]; then
> +	printf '#error Totally bogus HZ value!\n'
> +	exit 1
> +fi
> +
> +s="$(fmuls 32 1000 "$1")"
> +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")"
> +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")"
> +printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}"
> +
> +s="$(fmuls 32 "$1" 1000)"
> +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)"
> +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)"
> +printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}"
> +
> +cd="$(gcd "$1" 1000)"
> +printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))"
> +printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))"
> +printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
> +printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))"
> +
> +s="$(fmuls 32 1000000 "$1")"
> +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")"
> +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")"
> +printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}"
> +
> +s="$(fmuls 32 "$1" 1000000)"
> +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)"
> +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)"
> +printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}"
> +
> +cd="$(gcd "$1" 1000000)"
> +printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))"
> +printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))"
> +printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
> +printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))"
> +
> +cd="$(gcd "$1" 1000000000)"
> +printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))"
> +printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))"
> +printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
> +printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))"
> +
> +printf '\n#endif /* KERNEL_TIMECONST_H */\n'
> 

-- 
Regards
--
Kieran

[PATCH v2] replace timeconst bc script with an sh script

[Ethan Sommer]

removes the bc build dependency introduced when timeconst.pl was
replaced by timeconst.bc:
70730bca1331 ("kernel: Replace timeconst.pl with a bc script")

Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
---
 Documentation/process/changes.rst |   6 --
 Kbuild                            |   4 +-
 kernel/time/timeconst.bc          | 117 -----------------------------
 kernel/time/timeconst.sh          | 118 ++++++++++++++++++++++++++++++
 4 files changed, 120 insertions(+), 125 deletions(-)
 delete mode 100644 kernel/time/timeconst.bc
 create mode 100755 kernel/time/timeconst.sh

diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst
index 18735dc460a0..14347f6752ea 100644
--- a/Documentation/process/changes.rst
+++ b/Documentation/process/changes.rst
@@ -108,12 +108,6 @@ Perl
 You will need perl 5 and the following modules: ``Getopt::Long``,
 ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel.
 
-BC
---
-
-You will need bc to build kernels 3.10 and higher
-
-
 OpenSSL
 -------
 
diff --git a/Kbuild b/Kbuild
index 8637fd14135f..2b5f2957cf04 100644
--- a/Kbuild
+++ b/Kbuild
@@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h
 
 targets += $(timeconst-file)
 
-filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
+filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
 
-$(timeconst-file): kernel/time/timeconst.bc FORCE
+$(timeconst-file): kernel/time/timeconst.sh FORCE
 	$(call filechk,gentimeconst)
 
 #####
diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
deleted file mode 100644
index 7ed0e0fb5831..000000000000
--- a/kernel/time/timeconst.bc
+++ /dev/null
@@ -1,117 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-
-scale=0
-
-define gcd(a,b) {
-	auto t;
-	while (b) {
-		t = b;
-		b = a % b;
-		a = t;
-	}
-	return a;
-}
-
-/* Division by reciprocal multiplication. */
-define fmul(b,n,d) {
-       return (2^b*n+d-1)/d;
-}
-
-/* Adjustment factor when a ceiling value is used.  Use as:
-   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
-define fadj(b,n,d) {
-	auto v;
-	d = d/gcd(n,d);
-	v = 2^b*(d-1)/d;
-	return v;
-}
-
-/* Compute the appropriate mul/adj values as well as a shift count,
-   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
-   a shift value will be correct in the signed integer range and off
-   by at most one in the upper half of the unsigned range. */
-define fmuls(b,n,d) {
-	auto s, m;
-	for (s = 0; 1; s++) {
-		m = fmul(s,n,d);
-		if (m >= 2^(b-1))
-			return s;
-	}
-	return 0;
-}
-
-define timeconst(hz) {
-	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
-	print "/* Time conversion constants for HZ == ", hz, " */\n"
-	print "\n"
-
-	print "#ifndef KERNEL_TIMECONST_H\n"
-	print "#define KERNEL_TIMECONST_H\n\n"
-
-	print "#include <linux/param.h>\n"
-	print "#include <linux/types.h>\n\n"
-
-	print "#if HZ != ", hz, "\n"
-	print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n"
-	print "#endif\n\n"
-
-	if (hz < 2) {
-		print "#error Totally bogus HZ value!\n"
-	} else {
-		s=fmuls(32,1000,hz)
-		obase=16
-		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
-		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000)
-		obase=16
-		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
-		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
-		obase=10
-		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000)
-		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
-		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
-		print "\n"
-
-		s=fmuls(32,1000000,hz)
-		obase=16
-		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n"
-		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000000)
-		obase=16
-		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n"
-		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n"
-		obase=10
-		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000000)
-		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
-		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
-
-		cd=gcd(hz,1000000000)
-		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
-		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
-		print "\n"
-
-		print "#endif /* KERNEL_TIMECONST_H */\n"
-	}
-	halt
-}
-
-hz = read();
-timeconst(hz)
diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
new file mode 100755
index 000000000000..20dd24815ae1
--- /dev/null
+++ b/kernel/time/timeconst.sh
@@ -0,0 +1,118 @@
+#!/bin/sh
+# SPDX-License-Identifier: GPL-2.0
+
+if [ -z "$1" ]; then
+	printf '%s <HZ>\n' "$0"
+	exit 1
+else
+	hz="$1"
+fi
+
+# 2 to the power of n
+pot() {
+	local i=1
+    local j=1
+	while [ "${j}" -le "$1" ]; do
+		i="$((i * 2))"
+        j="$((j + 1))"
+	done
+	printf '%s\n' "${i}"
+}
+
+# Greatest common denominator
+gcd() {
+	local i="$1"
+	local j="$2"
+	local k
+	while [ "${j}" -ne 0 ]; do
+		k="${j}"
+		j="$((i % j))"
+		i="${k}"
+	done
+	printf '%s\n' "${i}"
+}
+
+# Division by reciprocal multiplication.
+fmul() {
+	printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
+}
+
+# Adjustment factor when a ceiling value is used.
+fadj() {
+	local i="$(gcd "$2" "$3")"
+	printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
+}
+
+# Compute the appropriate mul/adj values as well as a shift count,
+# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
+# a shift value will be correct in the signed integer range and off
+# by at most one in the upper half of the unsigned range.
+fmuls() {
+	local i=0
+    local j
+	while true; do
+        j="$(fmul "${i}" "$2" "$3")"
+		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
+			printf '%s\n' "${i}" && return
+		fi
+		i="$((i + 1))"
+	done
+}
+
+printf '/* Automatically generated by kernel/time/timeconst.sh */\n'
+printf '/* Time conversion constants for HZ == %s */\n\n' "$1"
+
+printf '#ifndef KERNEL_TIMECONST_H\n'
+printf '#define KERNEL_TIMECONST_H\n\n'
+
+printf '#include <linux/param.h>\n'
+printf '#include <linux/types.h>\n\n'
+
+printf '#if HZ != %s\n' "$1"
+printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n'
+printf '#endif\n\n'
+
+if [ "$1" -lt 2 ]; then
+	printf '#error Totally bogus HZ value!\n'
+	exit 1
+fi
+
+s="$(fmuls 32 1000 "$1")"
+printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000)"
+printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}"
+
+cd="$(gcd "$1" 1000)"
+printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))"
+printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))"
+
+s="$(fmuls 32 1000000 "$1")"
+printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000000)"
+printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}"
+
+cd="$(gcd "$1" 1000000)"
+printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))"
+printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))"
+
+cd="$(gcd "$1" 1000000000)"
+printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))"
+printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))"
+printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))"
+printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))"
+
+printf '\n#endif /* KERNEL_TIMECONST_H */\n'
-- 
2.22.0

Re: [PATCH v2] replace timeconst bc script with an sh script

[Borislav Petkov]

On Thu, Jun 20, 2019 at 04:11:32AM -0400, Ethan Sommer wrote:
> removes the bc build dependency introduced when timeconst.pl was
> replaced by timeconst.bc:
> 70730bca1331 ("kernel: Replace timeconst.pl with a bc script")

I don't see you answering Kieran's questions anywhere...

-- 
Regards/Gruss,
    Boris.

SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg)

Re: [PATCH v2] replace timeconst bc script with an sh script

[Ethan Sommer]

(resend because I didn't know gmail would make it html)
Ah sorry about that, I accidentally replied to Kieran only instead of
to all, my response was "I will upload a patch with those issues fixed
shortly, in terms of the dependency as far as I know commands only required
for running tests don't count as kernel compilation dependencies, and I
don't see any other uses of bc except for Documentation/EDID/Makefile, so
I believe that bc can be removed from the kernel compilation section of the
process document and will include that change with the updated patch that
fixes the 2 issues you pointed out."

On Thu, Jun 20, 2019 at 4:26 AM Borislav Petkov <bp@suse.de> wrote:
>
> On Thu, Jun 20, 2019 at 04:11:32AM -0400, Ethan Sommer wrote:
> > removes the bc build dependency introduced when timeconst.pl was
> > replaced by timeconst.bc:
> > 70730bca1331 ("kernel: Replace timeconst.pl with a bc script")
>
> I don't see you answering Kieran's questions anywhere...
>
> --
> Regards/Gruss,
>     Boris.
>
> SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg)

Re: [PATCH v2] replace timeconst bc script with an sh script

[Borislav Petkov]

On Thu, Jun 20, 2019 at 04:29:19AM -0400, Ethan Sommer wrote:
> Ah sorry about that, I accidentally replied to Kieran only instead of to
> all, my response was "I will upload a patch with those issues fixed
> shortly, in terms of the dependency as far as I know commands only required
> for running tests don't count as kernel compilation dependencies, and I
> don't see any other uses of bc except for Documentation/EDID/Makefile, so I
> believe that bc can be removed from the kernel compilation section of the
> process document and will include that change with the updated patch that
> fixes the 2 issues you pointed out."

Sounds like parts of it should be in your commit message as a
justification *why* you're doing it. You can do that for your next
revision once you've waited a couple of days to gather feedback.

Also, please do not top-post.

Thx.

-- 
Regards/Gruss,
    Boris.

SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg)

[PATCH v3] replace timeconst bc script with an sh script

[Ethan Sommer]

removes the bc build dependency introduced when timeconst.pl was
replaced by timeconst.bc:
commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script")

the reason for this change is that this is the only use of bc in the
actual compilation of the kernel, so by replacing it with a shell script
compiling the kernel no longer depends on bc.

Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
---
 Documentation/process/changes.rst |   6 --
 Kbuild                            |   4 +-
 kernel/time/timeconst.bc          | 117 ------------------------------
 kernel/time/timeconst.sh          | 111 ++++++++++++++++++++++++++++
 4 files changed, 113 insertions(+), 125 deletions(-)
 delete mode 100644 kernel/time/timeconst.bc
 create mode 100644 kernel/time/timeconst.sh

diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst
index 2284f2221f02..3ae168387109 100644
--- a/Documentation/process/changes.rst
+++ b/Documentation/process/changes.rst
@@ -105,12 +105,6 @@ Perl
 You will need perl 5 and the following modules: ``Getopt::Long``,
 ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel.
 
-BC
---
-
-You will need bc to build kernels 3.10 and higher
-
-
 OpenSSL
 -------
 
diff --git a/Kbuild b/Kbuild
index 3109ac786e76..7eba24cbdb78 100644
--- a/Kbuild
+++ b/Kbuild
@@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE
 
 timeconst-file := include/generated/timeconst.h
 
-filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
+filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
 
-$(timeconst-file): kernel/time/timeconst.bc FORCE
+$(timeconst-file): kernel/time/timeconst.sh FORCE
 	$(call filechk,gentimeconst)
 
 #####
diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
deleted file mode 100644
index 7ed0e0fb5831..000000000000
--- a/kernel/time/timeconst.bc
+++ /dev/null
@@ -1,117 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-
-scale=0
-
-define gcd(a,b) {
-	auto t;
-	while (b) {
-		t = b;
-		b = a % b;
-		a = t;
-	}
-	return a;
-}
-
-/* Division by reciprocal multiplication. */
-define fmul(b,n,d) {
-       return (2^b*n+d-1)/d;
-}
-
-/* Adjustment factor when a ceiling value is used.  Use as:
-   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
-define fadj(b,n,d) {
-	auto v;
-	d = d/gcd(n,d);
-	v = 2^b*(d-1)/d;
-	return v;
-}
-
-/* Compute the appropriate mul/adj values as well as a shift count,
-   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
-   a shift value will be correct in the signed integer range and off
-   by at most one in the upper half of the unsigned range. */
-define fmuls(b,n,d) {
-	auto s, m;
-	for (s = 0; 1; s++) {
-		m = fmul(s,n,d);
-		if (m >= 2^(b-1))
-			return s;
-	}
-	return 0;
-}
-
-define timeconst(hz) {
-	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
-	print "/* Time conversion constants for HZ == ", hz, " */\n"
-	print "\n"
-
-	print "#ifndef KERNEL_TIMECONST_H\n"
-	print "#define KERNEL_TIMECONST_H\n\n"
-
-	print "#include <linux/param.h>\n"
-	print "#include <linux/types.h>\n\n"
-
-	print "#if HZ != ", hz, "\n"
-	print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n"
-	print "#endif\n\n"
-
-	if (hz < 2) {
-		print "#error Totally bogus HZ value!\n"
-	} else {
-		s=fmuls(32,1000,hz)
-		obase=16
-		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
-		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000)
-		obase=16
-		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
-		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
-		obase=10
-		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000)
-		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
-		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
-		print "\n"
-
-		s=fmuls(32,1000000,hz)
-		obase=16
-		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n"
-		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n"
-		obase=10
-		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
-
-		s=fmuls(32,hz,1000000)
-		obase=16
-		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n"
-		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n"
-		obase=10
-		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
-
-		obase=10
-		cd=gcd(hz,1000000)
-		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
-		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
-
-		cd=gcd(hz,1000000000)
-		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
-		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
-		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
-		print "\n"
-
-		print "#endif /* KERNEL_TIMECONST_H */\n"
-	}
-	halt
-}
-
-hz = read();
-timeconst(hz)
diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
new file mode 100644
index 000000000000..d1aa25f46be8
--- /dev/null
+++ b/kernel/time/timeconst.sh
@@ -0,0 +1,111 @@
+#!/bin/sh
+# SPDX-License-Identifier: GPL-2.0
+
+if [ -z "$1" ]; then
+	printf '%s <HZ>\n' "$0" >&2
+	exit 1
+fi
+
+# 2 to the power of n
+pot() {
+	local i=1 j=0
+	while [ "$((j += 1))" -le "$1" ]; do
+		: "$((i *= 2))"
+	done
+	printf '%u' "${i}"
+}
+
+# Greatest common denominator
+gcd() {
+	local i="$1" j="$2" k
+	while [ "${j}" -ne 0 ]; do
+		k="${j}" j="$((i % j))" i="${k}"
+	done
+	printf '%u' "${i}"
+}
+
+# Division by reciprocal multiplication.
+fmul() {
+	printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
+}
+
+# Adjustment factor when a ceiling value is used.
+fadj() {
+	local i
+	i="$(gcd "$2" "$3")"
+	printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
+}
+
+# Compute the appropriate mul/adj values as well as a shift count,
+# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
+# a shift value will be correct in the signed integer range and off
+# by at most one in the upper half of the unsigned range.
+fmuls() {
+	local i=0 j
+	while true; do
+		j="$(fmul "${i}" "$2" "$3")"
+		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
+			printf '%u' "${i}"
+			return
+		fi
+		: "$((i += 1))"
+	done
+}
+
+printf '/* Automatically generated by kernel/time/timeconst.sh */\n'
+printf '/* Time conversion constants for HZ == %u */\n\n' "$1"
+
+printf '#ifndef KERNEL_TIMECONST_H\n'
+printf '#define KERNEL_TIMECONST_H\n\n'
+
+printf '#include <linux/param.h>\n'
+printf '#include <linux/types.h>\n\n'
+
+printf '#if HZ != %u\n' "$1"
+printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n'
+printf '#endif\n\n'
+
+if [ "$1" -lt 2 ]; then
+	printf '#error Totally bogus HZ value!\n'
+	exit 1
+fi
+
+s="$(fmuls 32 1000 "$1")"
+printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")"
+printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000)"
+printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)"
+printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}"
+
+cd="$(gcd "$1" 1000)"
+printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))"
+printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))"
+printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
+printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))"
+
+s="$(fmuls 32 1000000 "$1")"
+printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")"
+printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}"
+
+s="$(fmuls 32 "$1" 1000000)"
+printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)"
+printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}"
+
+cd="$(gcd "$1" 1000000)"
+printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))"
+printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))"
+printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
+printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))"
+
+cd="$(gcd "$1" 1000000000)"
+printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))"
+printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))"
+printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
+printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))"
+
+printf '\n#endif /* KERNEL_TIMECONST_H */\n'
-- 
2.23.0

Re: [PATCH v3] replace timeconst bc script with an sh script

[Kieran Bingham]

Hi Ethan,

On 29/10/2019 21:02, Ethan Sommer wrote:
> removes the bc build dependency introduced when timeconst.pl was
> replaced by timeconst.bc:
> commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script")
> 
> the reason for this change is that this is the only use of bc in the
> actual compilation of the kernel, so by replacing it with a shell script
> compiling the kernel no longer depends on bc.
> 
> Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
> ---
>  Documentation/process/changes.rst |   6 --
>  Kbuild                            |   4 +-
>  kernel/time/timeconst.bc          | 117 ------------------------------
>  kernel/time/timeconst.sh          | 111 ++++++++++++++++++++++++++++

Running shellcheck on kernel/time/timeconst.sh produces the following
warnings:

shellcheck kernel/time/timeconst.sh

In kernel/time/timeconst.sh line 11:
	local i=1 j=0
        ^-- SC2039: In POSIX sh, 'local' is undefined.


In kernel/time/timeconst.sh line 20:
	local i="$1" j="$2" k
        ^-- SC2039: In POSIX sh, 'local' is undefined.


In kernel/time/timeconst.sh line 34:
	local i
        ^-- SC2039: In POSIX sh, 'local' is undefined.


In kernel/time/timeconst.sh line 44:
	local i=0 j
        ^-- SC2039: In POSIX sh, 'local' is undefined.



Will this cause an issue for people running posix shells?
Which shells have you tested your script on ?


Furthermore, I fear this conversion may not be suitable at present, as
it produces potentially different results for CONFIG_HZ < 100

(There may be more diffs, but I haven't yet compared a larger search space)

using a quick script I put together to compare the output of
timeconst.sh and timeconst.bc for a given CONFIG_HZ:


 https://gist.github.com/kbingham/76e8718df7b7dc97361405cc1801a160


$ for i in `seq 0 300`; do ./check-timeconst.sh $i; done

produces a diff on almost every value 2 - 243

   http://paste.ubuntu.com/p/wNggrfFZXB/

Or rather 137 faults to be exact:

 for i in `seq 0 250`; \
	do ./check-timeconst.sh $i; \
 done | grep -- "--- BC" | wc -l


I think that might be considered a blocker to this implementation, or
those values and the impact should certainly be investigated thoroughly.

I haven't looked into detail into the change of any of those values, so
I can not ascertain which one is more correct (though I suspect it's
likely to be bc that will have the 'more correct' value)

I would fear doing this in shell just isn't going to maintain the
correct precision, which is likely a strong reason why bc was selected
in the first place.


If you can find the issue that causes this diff in your shell
processing, and clarify or fix it - then it might be possible to gain
some backing to the implementation, but even then it might become a
shell specific precision issue ...

--
Regards

Kieran



>  4 files changed, 113 insertions(+), 125 deletions(-)
>  delete mode 100644 kernel/time/timeconst.bc
>  create mode 100644 kernel/time/timeconst.sh
> 
> diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst
> index 2284f2221f02..3ae168387109 100644
> --- a/Documentation/process/changes.rst
> +++ b/Documentation/process/changes.rst
> @@ -105,12 +105,6 @@ Perl
>  You will need perl 5 and the following modules: ``Getopt::Long``,
>  ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel.
>  
> -BC
> ---
> -
> -You will need bc to build kernels 3.10 and higher
> -
> -
>  OpenSSL
>  -------
>  
> diff --git a/Kbuild b/Kbuild
> index 3109ac786e76..7eba24cbdb78 100644
> --- a/Kbuild
> +++ b/Kbuild
> @@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE
>  
>  timeconst-file := include/generated/timeconst.h
>  
> -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
> +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
>  
> -$(timeconst-file): kernel/time/timeconst.bc FORCE
> +$(timeconst-file): kernel/time/timeconst.sh FORCE
>  	$(call filechk,gentimeconst)
>  
>  #####
> diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
> deleted file mode 100644
> index 7ed0e0fb5831..000000000000
> --- a/kernel/time/timeconst.bc
> +++ /dev/null
> @@ -1,117 +0,0 @@
> -/* SPDX-License-Identifier: GPL-2.0 */
> -
> -scale=0
> -
> -define gcd(a,b) {
> -	auto t;
> -	while (b) {
> -		t = b;
> -		b = a % b;
> -		a = t;
> -	}
> -	return a;
> -}
> -
> -/* Division by reciprocal multiplication. */
> -define fmul(b,n,d) {
> -       return (2^b*n+d-1)/d;
> -}
> -
> -/* Adjustment factor when a ceiling value is used.  Use as:
> -   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
> -define fadj(b,n,d) {
> -	auto v;
> -	d = d/gcd(n,d);
> -	v = 2^b*(d-1)/d;
> -	return v;
> -}
> -
> -/* Compute the appropriate mul/adj values as well as a shift count,
> -   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
> -   a shift value will be correct in the signed integer range and off
> -   by at most one in the upper half of the unsigned range. */
> -define fmuls(b,n,d) {
> -	auto s, m;
> -	for (s = 0; 1; s++) {
> -		m = fmul(s,n,d);
> -		if (m >= 2^(b-1))
> -			return s;
> -	}
> -	return 0;
> -}
> -
> -define timeconst(hz) {
> -	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
> -	print "/* Time conversion constants for HZ == ", hz, " */\n"
> -	print "\n"
> -
> -	print "#ifndef KERNEL_TIMECONST_H\n"
> -	print "#define KERNEL_TIMECONST_H\n\n"
> -
> -	print "#include <linux/param.h>\n"
> -	print "#include <linux/types.h>\n\n"
> -
> -	print "#if HZ != ", hz, "\n"
> -	print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n"
> -	print "#endif\n\n"
> -
> -	if (hz < 2) {
> -		print "#error Totally bogus HZ value!\n"
> -	} else {
> -		s=fmuls(32,1000,hz)
> -		obase=16
> -		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
> -		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
> -		obase=10
> -		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
> -
> -		s=fmuls(32,hz,1000)
> -		obase=16
> -		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
> -		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
> -		obase=10
> -		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
> -
> -		obase=10
> -		cd=gcd(hz,1000)
> -		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
> -		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
> -		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
> -		print "\n"
> -
> -		s=fmuls(32,1000000,hz)
> -		obase=16
> -		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n"
> -		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n"
> -		obase=10
> -		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
> -
> -		s=fmuls(32,hz,1000000)
> -		obase=16
> -		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n"
> -		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n"
> -		obase=10
> -		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
> -
> -		obase=10
> -		cd=gcd(hz,1000000)
> -		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
> -		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
> -		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
> -
> -		cd=gcd(hz,1000000000)
> -		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
> -		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
> -		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
> -		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
> -		print "\n"
> -
> -		print "#endif /* KERNEL_TIMECONST_H */\n"
> -	}
> -	halt
> -}
> -
> -hz = read();
> -timeconst(hz)
> diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
> new file mode 100644
> index 000000000000..d1aa25f46be8
> --- /dev/null
> +++ b/kernel/time/timeconst.sh
> @@ -0,0 +1,111 @@
> +#!/bin/sh
> +# SPDX-License-Identifier: GPL-2.0
> +
> +if [ -z "$1" ]; then
> +	printf '%s <HZ>\n' "$0" >&2
> +	exit 1
> +fi
> +
> +# 2 to the power of n
> +pot() {
> +	local i=1 j=0
> +	while [ "$((j += 1))" -le "$1" ]; do
> +		: "$((i *= 2))"
> +	done
> +	printf '%u' "${i}"
> +}
> +
> +# Greatest common denominator
> +gcd() {
> +	local i="$1" j="$2" k
> +	while [ "${j}" -ne 0 ]; do
> +		k="${j}" j="$((i % j))" i="${k}"
> +	done
> +	printf '%u' "${i}"
> +}
> +
> +# Division by reciprocal multiplication.
> +fmul() {
> +	printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
> +}
> +
> +# Adjustment factor when a ceiling value is used.
> +fadj() {
> +	local i
> +	i="$(gcd "$2" "$3")"
> +	printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
> +}
> +
> +# Compute the appropriate mul/adj values as well as a shift count,
> +# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
> +# a shift value will be correct in the signed integer range and off
> +# by at most one in the upper half of the unsigned range.
> +fmuls() {
> +	local i=0 j
> +	while true; do
> +		j="$(fmul "${i}" "$2" "$3")"
> +		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
> +			printf '%u' "${i}"
> +			return
> +		fi
> +		: "$((i += 1))"
> +	done
> +}
> +
> +printf '/* Automatically generated by kernel/time/timeconst.sh */\n'
> +printf '/* Time conversion constants for HZ == %u */\n\n' "$1"
> +
> +printf '#ifndef KERNEL_TIMECONST_H\n'
> +printf '#define KERNEL_TIMECONST_H\n\n'
> +
> +printf '#include <linux/param.h>\n'
> +printf '#include <linux/types.h>\n\n'
> +
> +printf '#if HZ != %u\n' "$1"
> +printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n'
> +printf '#endif\n\n'
> +
> +if [ "$1" -lt 2 ]; then
> +	printf '#error Totally bogus HZ value!\n'
> +	exit 1
> +fi
> +
> +s="$(fmuls 32 1000 "$1")"
> +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")"
> +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")"
> +printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}"
> +
> +s="$(fmuls 32 "$1" 1000)"
> +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)"
> +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)"
> +printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}"
> +
> +cd="$(gcd "$1" 1000)"
> +printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))"
> +printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))"
> +printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
> +printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))"
> +
> +s="$(fmuls 32 1000000 "$1")"
> +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")"
> +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")"
> +printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}"
> +
> +s="$(fmuls 32 "$1" 1000000)"
> +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)"
> +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)"
> +printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}"
> +
> +cd="$(gcd "$1" 1000000)"
> +printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))"
> +printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))"
> +printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
> +printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))"
> +
> +cd="$(gcd "$1" 1000000000)"
> +printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))"
> +printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))"
> +printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
> +printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))"
> +
> +printf '\n#endif /* KERNEL_TIMECONST_H */\n'
> 

-- 
Regards
--
Kieran

Re: [PATCH v3] replace timeconst bc script with an sh script

[Ethan Sommer]

> Running shellcheck on kernel/time/timeconst.sh produces the following
> warnings:
>
> shellcheck kernel/time/timeconst.sh
>
> In kernel/time/timeconst.sh line 11:
>         local i=1 j=0
>         ^-- SC2039: In POSIX sh, 'local' is undefined.
>
>
> In kernel/time/timeconst.sh line 20:
>         local i="$1" j="$2" k
>         ^-- SC2039: In POSIX sh, 'local' is undefined.
>
>
> In kernel/time/timeconst.sh line 34:
>         local i
>         ^-- SC2039: In POSIX sh, 'local' is undefined.
>
>
> In kernel/time/timeconst.sh line 44:
>         local i=0 j
>         ^-- SC2039: In POSIX sh, 'local' is undefined.
>
>
>
> Will this cause an issue for people running posix shells?
> Which shells have you tested your script on ?
While local is not part of POSIX, it is widely supported, including by
dash, and is used by many shell scripts in the kernel's build including
link-vmlinux.sh, however I can easily make the script work without local
by using unique variable names in each function and resetting all of
them at the beginning of the functions if that is desired instead of
local.
>
> Furthermore, I fear this conversion may not be suitable at present, as
> it produces potentially different results for CONFIG_HZ < 100
>
> (There may be more diffs, but I haven't yet compared a larger search space)
>
> using a quick script I put together to compare the output of
> timeconst.sh and timeconst.bc for a given CONFIG_HZ:
>
>
>  https://gist.github.com/kbingham/76e8718df7b7dc97361405cc1801a160
>
>
> $ for i in `seq 0 300`; do ./check-timeconst.sh $i; done
>
> produces a diff on almost every value 2 - 243
>
>    http://paste.ubuntu.com/p/wNggrfFZXB/
>
> Or rather 137 faults to be exact:
>
>  for i in `seq 0 250`; \
>         do ./check-timeconst.sh $i; \
>  done | grep -- "--- BC" | wc -l
>
>
> I think that might be considered a blocker to this implementation, or
> those values and the impact should certainly be investigated thoroughly.
>
> I haven't looked into detail into the change of any of those values, so
> I can not ascertain which one is more correct (though I suspect it's
> likely to be bc that will have the 'more correct' value)
>
> I would fear doing this in shell just isn't going to maintain the
> correct precision, which is likely a strong reason why bc was selected
> in the first place.
>
>
> If you can find the issue that causes this diff in your shell
> processing, and clarify or fix it - then it might be possible to gain
> some backing to the implementation, but even then it might become a
> shell specific precision issue ...
That definitely is a blocker, I will attempt to make this implementation
match the bc script for those values.

Re: [PATCH v3] replace timeconst bc script with an sh script

[hpa]

On October 29, 2019 2:02:44 PM PDT, Ethan Sommer <e5ten.arch@gmail.com> wrote:
>removes the bc build dependency introduced when timeconst.pl was
>replaced by timeconst.bc:
>commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script")
>
>the reason for this change is that this is the only use of bc in the
>actual compilation of the kernel, so by replacing it with a shell
>script
>compiling the kernel no longer depends on bc.
>
>Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com>
>---
> Documentation/process/changes.rst |   6 --
> Kbuild                            |   4 +-
> kernel/time/timeconst.bc          | 117 ------------------------------
> kernel/time/timeconst.sh          | 111 ++++++++++++++++++++++++++++
> 4 files changed, 113 insertions(+), 125 deletions(-)
> delete mode 100644 kernel/time/timeconst.bc
> create mode 100644 kernel/time/timeconst.sh
>
>diff --git a/Documentation/process/changes.rst
>b/Documentation/process/changes.rst
>index 2284f2221f02..3ae168387109 100644
>--- a/Documentation/process/changes.rst
>+++ b/Documentation/process/changes.rst
>@@ -105,12 +105,6 @@ Perl
> You will need perl 5 and the following modules: ``Getopt::Long``,
>``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the
>kernel.
> 
>-BC
>---
>-
>-You will need bc to build kernels 3.10 and higher
>-
>-
> OpenSSL
> -------
> 
>diff --git a/Kbuild b/Kbuild
>index 3109ac786e76..7eba24cbdb78 100644
>--- a/Kbuild
>+++ b/Kbuild
>@@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE
> 
> timeconst-file := include/generated/timeconst.h
> 
>-filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $<
>+filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ)
> 
>-$(timeconst-file): kernel/time/timeconst.bc FORCE
>+$(timeconst-file): kernel/time/timeconst.sh FORCE
> 	$(call filechk,gentimeconst)
> 
> #####
>diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc
>deleted file mode 100644
>index 7ed0e0fb5831..000000000000
>--- a/kernel/time/timeconst.bc
>+++ /dev/null
>@@ -1,117 +0,0 @@
>-/* SPDX-License-Identifier: GPL-2.0 */
>-
>-scale=0
>-
>-define gcd(a,b) {
>-	auto t;
>-	while (b) {
>-		t = b;
>-		b = a % b;
>-		a = t;
>-	}
>-	return a;
>-}
>-
>-/* Division by reciprocal multiplication. */
>-define fmul(b,n,d) {
>-       return (2^b*n+d-1)/d;
>-}
>-
>-/* Adjustment factor when a ceiling value is used.  Use as:
>-   (imul * n) + (fmulxx * n + fadjxx) >> xx) */
>-define fadj(b,n,d) {
>-	auto v;
>-	d = d/gcd(n,d);
>-	v = 2^b*(d-1)/d;
>-	return v;
>-}
>-
>-/* Compute the appropriate mul/adj values as well as a shift count,
>-   which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
>-   a shift value will be correct in the signed integer range and off
>-   by at most one in the upper half of the unsigned range. */
>-define fmuls(b,n,d) {
>-	auto s, m;
>-	for (s = 0; 1; s++) {
>-		m = fmul(s,n,d);
>-		if (m >= 2^(b-1))
>-			return s;
>-	}
>-	return 0;
>-}
>-
>-define timeconst(hz) {
>-	print "/* Automatically generated by kernel/time/timeconst.bc */\n"
>-	print "/* Time conversion constants for HZ == ", hz, " */\n"
>-	print "\n"
>-
>-	print "#ifndef KERNEL_TIMECONST_H\n"
>-	print "#define KERNEL_TIMECONST_H\n\n"
>-
>-	print "#include <linux/param.h>\n"
>-	print "#include <linux/types.h>\n\n"
>-
>-	print "#if HZ != ", hz, "\n"
>-	print "#error \qinclude/generated/timeconst.h has the wrong HZ
>value!\q\n"
>-	print "#endif\n\n"
>-
>-	if (hz < 2) {
>-		print "#error Totally bogus HZ value!\n"
>-	} else {
>-		s=fmuls(32,1000,hz)
>-		obase=16
>-		print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n"
>-		print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n"
>-		obase=10
>-		print "#define HZ_TO_MSEC_SHR32\t", s, "\n"
>-
>-		s=fmuls(32,hz,1000)
>-		obase=16
>-		print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n"
>-		print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n"
>-		obase=10
>-		print "#define MSEC_TO_HZ_SHR32\t", s, "\n"
>-
>-		obase=10
>-		cd=gcd(hz,1000)
>-		print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n"
>-		print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n"
>-		print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
>-		print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n"
>-		print "\n"
>-
>-		s=fmuls(32,1000000,hz)
>-		obase=16
>-		print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz),
>")\n"
>-		print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz),
>")\n"
>-		obase=10
>-		print "#define HZ_TO_USEC_SHR32\t", s, "\n"
>-
>-		s=fmuls(32,hz,1000000)
>-		obase=16
>-		print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000),
>")\n"
>-		print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000),
>")\n"
>-		obase=10
>-		print "#define USEC_TO_HZ_SHR32\t", s, "\n"
>-
>-		obase=10
>-		cd=gcd(hz,1000000)
>-		print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n"
>-		print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n"
>-		print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n"
>-		print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n"
>-
>-		cd=gcd(hz,1000000000)
>-		print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n"
>-		print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n"
>-		print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n"
>-		print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n"
>-		print "\n"
>-
>-		print "#endif /* KERNEL_TIMECONST_H */\n"
>-	}
>-	halt
>-}
>-
>-hz = read();
>-timeconst(hz)
>diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh
>new file mode 100644
>index 000000000000..d1aa25f46be8
>--- /dev/null
>+++ b/kernel/time/timeconst.sh
>@@ -0,0 +1,111 @@
>+#!/bin/sh
>+# SPDX-License-Identifier: GPL-2.0
>+
>+if [ -z "$1" ]; then
>+	printf '%s <HZ>\n' "$0" >&2
>+	exit 1
>+fi
>+
>+# 2 to the power of n
>+pot() {
>+	local i=1 j=0
>+	while [ "$((j += 1))" -le "$1" ]; do
>+		: "$((i *= 2))"
>+	done
>+	printf '%u' "${i}"
>+}
>+
>+# Greatest common denominator
>+gcd() {
>+	local i="$1" j="$2" k
>+	while [ "${j}" -ne 0 ]; do
>+		k="${j}" j="$((i % j))" i="${k}"
>+	done
>+	printf '%u' "${i}"
>+}
>+
>+# Division by reciprocal multiplication.
>+fmul() {
>+	printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))"
>+}
>+
>+# Adjustment factor when a ceiling value is used.
>+fadj() {
>+	local i
>+	i="$(gcd "$2" "$3")"
>+	printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))"
>+}
>+
>+# Compute the appropriate mul/adj values as well as a shift count,
>+# which brings the mul value into the range 2^b-1 <= x < 2^b.  Such
>+# a shift value will be correct in the signed integer range and off
>+# by at most one in the upper half of the unsigned range.
>+fmuls() {
>+	local i=0 j
>+	while true; do
>+		j="$(fmul "${i}" "$2" "$3")"
>+		if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then
>+			printf '%u' "${i}"
>+			return
>+		fi
>+		: "$((i += 1))"
>+	done
>+}
>+
>+printf '/* Automatically generated by kernel/time/timeconst.sh */\n'
>+printf '/* Time conversion constants for HZ == %u */\n\n' "$1"
>+
>+printf '#ifndef KERNEL_TIMECONST_H\n'
>+printf '#define KERNEL_TIMECONST_H\n\n'
>+
>+printf '#include <linux/param.h>\n'
>+printf '#include <linux/types.h>\n\n'
>+
>+printf '#if HZ != %u\n' "$1"
>+printf '#error "include/generated/timeconst.h has the wrong HZ
>value!"\n'
>+printf '#endif\n\n'
>+
>+if [ "$1" -lt 2 ]; then
>+	printf '#error Totally bogus HZ value!\n'
>+	exit 1
>+fi
>+
>+s="$(fmuls 32 1000 "$1")"
>+printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000
>"$1")"
>+printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000
>"$1")"
>+printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}"
>+
>+s="$(fmuls 32 "$1" 1000)"
>+printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1"
>1000)"
>+printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1"
>1000)"
>+printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}"
>+
>+cd="$(gcd "$1" 1000)"
>+printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))"
>+printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))"
>+printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
>+printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))"
>+
>+s="$(fmuls 32 1000000 "$1")"
>+printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}"
>1000000 "$1")"
>+printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}"
>1000000 "$1")"
>+printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}"
>+
>+s="$(fmuls 32 "$1" 1000000)"
>+printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1"
>1000000)"
>+printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1"
>1000000)"
>+printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}"
>+
>+cd="$(gcd "$1" 1000000)"
>+printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))"
>+printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))"
>+printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
>+printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))"
>+
>+cd="$(gcd "$1" 1000000000)"
>+printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))"
>+printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))"
>+printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))"
>+printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))"
>+
>+printf '\n#endif /* KERNEL_TIMECONST_H */\n'

Please let me point out, again, that bc *is* part of the basic POSIX toolset, and the only tool in that toolset that allows for arbitrary-precision arithmetic. That being said, GNU as, which we also depends on, also contains bigint arithmetic, so it might be possible to coax as into outputting ASCII output without manually implementing bigints manually.

Another option would be to use a C program linked with gmp. Binutils requires gmp, so it doesn't inherently add dependencies, but running it though as would probably be easier at least for the LLVM guys.

I also have written a small, portable C bigint library, but that is a lot of code to add to the tree.
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: [PATCH v3] replace timeconst bc script with an sh script

[Ethan Sommer]

> Please let me point out, again, that bc *is* part of the basic POSIX toolset, and the only tool in that toolset that allows for arbitrary-precision arithmetic. That being said, GNU as, which we also depends on, also contains bigint arithmetic, so it might be possible to coax as into outputting ASCII output without manually implementing bigints manually.
>
> Another option would be to use a C program linked with gmp. Binutils requires gmp, so it doesn't inherently add dependencies, but running it though as would probably be easier at least for the LLVM guys.
>
> I also have written a small, portable C bigint library, but that is a lot of code to add to the tree.
I don't know what the requirement is for the level of precision this
would need to support is, so I don't know if this meets them, but I made
a C program that doesn't use gmp, so while it probably doesn't
theoretically have the same level of precision as bc, it does match it
for output on anything up to 15000 (it doesn't stop matching
timeconst.bc above 15000 I just didn't test any higher). The program is
here: http://ix.io/20Ka
If this is considered precise enough to be an acceptable replacement
I will make a new patch to use it in place of timeconst.bc.

Re: [PATCH v3] replace timeconst bc script with an sh script

[hpa]

On November 3, 2019 1:56:50 PM PST, Ethan Sommer <e5ten.arch@gmail.com> wrote:
>> Please let me point out, again, that bc *is* part of the basic POSIX
>toolset, and the only tool in that toolset that allows for
>arbitrary-precision arithmetic. That being said, GNU as, which we also
>depends on, also contains bigint arithmetic, so it might be possible to
>coax as into outputting ASCII output without manually implementing
>bigints manually.
>>
>> Another option would be to use a C program linked with gmp. Binutils
>requires gmp, so it doesn't inherently add dependencies, but running it
>though as would probably be easier at least for the LLVM guys.
>>
>> I also have written a small, portable C bigint library, but that is a
>lot of code to add to the tree.
>I don't know what the requirement is for the level of precision this
>would need to support is, so I don't know if this meets them, but I
>made
>a C program that doesn't use gmp, so while it probably doesn't
>theoretically have the same level of precision as bc, it does match it
>for output on anything up to 15000 (it doesn't stop matching
>timeconst.bc above 15000 I just didn't test any higher). The program is
>here: http://ix.io/20Ka
>If this is considered precise enough to be an acceptable replacement
>I will make a new patch to use it in place of timeconst.bc.

The point isn't to make it work *now*, but getting it to *stay* work.
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: [PATCH v3] replace timeconst bc script with an sh script

[Ethan Sommer]

> The point isn't to make it work *now*, but getting it to *stay* work.
Since the only thing that can change to affect the outcome of the script
or program is the value of CONFIG_HZ, isn't knowing that it works within
a range of any reasonable values to set CONFIG_HZ to enough to know that
it will stay working? I just tested again using the bc script and my C
program, and this time I tested every possible value up to 100000, and
they both still matched output. It doesn't seem like there's something
that would cause the C program to stop working in the future due to
precision issues.

Re: [PATCH v3] replace timeconst bc script with an sh script

[hpa]

On November 3, 2019 3:57:06 PM PST, Ethan Sommer <e5ten.arch@gmail.com> wrote:
>> The point isn't to make it work *now*, but getting it to *stay* work.
>Since the only thing that can change to affect the outcome of the
>script
>or program is the value of CONFIG_HZ, isn't knowing that it works
>within
>a range of any reasonable values to set CONFIG_HZ to enough to know
>that
>it will stay working? I just tested again using the bc script and my C
>program, and this time I tested every possible value up to 100000, and
>they both still matched output. It doesn't seem like there's something
>that would cause the C program to stop working in the future due to
>precision issues.

No, it's not. Because some time we are going to want to change the way the constants we need, or use them for something else, and be so on.
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.