1#! /usr/bin/python3 -B
2#
3# SPDX-License-Identifier: BSD-2-Clause
4#
5# Copyright (c) 2018-2021 Gavin D. Howard and contributors.
6#
7# Redistribution and use in source and binary forms, with or without
8# modification, are permitted provided that the following conditions are met:
9#
10# * Redistributions of source code must retain the above copyright notice, this
11#   list of conditions and the following disclaimer.
12#
13# * Redistributions in binary form must reproduce the above copyright notice,
14#   this list of conditions and the following disclaimer in the documentation
15#   and/or other materials provided with the distribution.
16#
17# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27# POSSIBILITY OF SUCH DAMAGE.
28#
29
30import os
31import sys
32import subprocess
33import time
34
35def usage():
36	print("usage: {} [num_iterations test_num exe]".format(script))
37	print("\n    num_iterations is the number of times to run each karatsuba number; default is 4")
38	print("\n    test_num is the last Karatsuba number to run through tests")
39	sys.exit(1)
40
41def run(cmd, env=None):
42	return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env)
43
44script = sys.argv[0]
45testdir = os.path.dirname(script)
46
47if testdir == "":
48	testdir = os.getcwd()
49
50print("\nWARNING: This script is for distro and package maintainers.")
51print("It is for finding the optimal Karatsuba number.")
52print("Though it only needs to be run once per release/platform,")
53print("it takes forever to run.")
54print("You have been warned.\n")
55print("Note: If you send an interrupt, it will report the current best number.\n")
56
57if __name__ != "__main__":
58	usage()
59
60mx = 520
61mx2 = mx // 2
62mn = 16
63
64num = "9" * mx
65
66args_idx = 4
67
68if len(sys.argv) >= 2:
69	num_iterations = int(sys.argv[1])
70else:
71	num_iterations = 4
72
73if len(sys.argv) >= 3:
74	test_num = int(sys.argv[2])
75else:
76	test_num = 0
77
78if len(sys.argv) >= args_idx:
79	exe = sys.argv[3]
80else:
81	exe = testdir + "/bin/bc"
82
83exedir = os.path.dirname(exe)
84
85indata = "for (i = 0; i < 100; ++i) {} * {}\n"
86indata += "1.23456789^100000\n1.23456789^100000\nhalt"
87indata = indata.format(num, num).encode()
88
89times = []
90nums = []
91runs = []
92nruns = num_iterations + 1
93
94for i in range(0, nruns):
95	runs.append(0)
96
97tests = [ "multiply", "modulus", "power", "sqrt" ]
98scripts = [ "multiply" ]
99
100print("Testing CFLAGS=\"-flto\"...")
101
102flags = dict(os.environ)
103try:
104	flags["CFLAGS"] = flags["CFLAGS"] + " " + "-flto"
105except KeyError:
106	flags["CFLAGS"] = "-flto"
107
108p = run([ "./configure.sh", "-O3" ], flags)
109if p.returncode != 0:
110	print("configure.sh returned an error ({}); exiting...".format(p.returncode))
111	sys.exit(p.returncode)
112
113p = run([ "make" ])
114
115if p.returncode == 0:
116	config_env = flags
117	print("Using CFLAGS=\"-flto\"")
118else:
119	config_env = os.environ
120	print("Not using CFLAGS=\"-flto\"")
121
122p = run([ "make", "clean" ])
123
124print("Testing \"make -j16\"")
125
126if p.returncode != 0:
127	print("make returned an error ({}); exiting...".format(p.returncode))
128	sys.exit(p.returncode)
129
130p = run([ "make", "-j16" ])
131
132if p.returncode == 0:
133	makecmd = [ "make", "-j16" ]
134	print("Using \"make -j16\"")
135else:
136	makecmd = [ "make" ]
137	print("Not using \"make -j16\"")
138
139if test_num != 0:
140	mx2 = test_num
141
142try:
143
144	for i in range(mn, mx2 + 1):
145
146		print("\nCompiling...\n")
147
148		p = run([ "./configure.sh", "-O3", "-k{}".format(i) ], config_env)
149
150		if p.returncode != 0:
151			print("configure.sh returned an error ({}); exiting...".format(p.returncode))
152			sys.exit(p.returncode)
153
154		p = run(makecmd)
155
156		if p.returncode != 0:
157			print("make returned an error ({}); exiting...".format(p.returncode))
158			sys.exit(p.returncode)
159
160		if (test_num >= i):
161
162			print("Running tests for Karatsuba Num: {}\n".format(i))
163
164			for test in tests:
165
166				cmd = [ "{}/tests/test.sh".format(testdir), "bc", test, "0", "0", exe ]
167
168				p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE)
169
170				if p.returncode != 0:
171					print("{} test failed:\n".format(test, p.returncode))
172					print(p.stderr.decode())
173					print("\nexiting...")
174					sys.exit(p.returncode)
175
176			print("")
177
178			for script in scripts:
179
180				cmd = [ "{}/tests/script.sh".format(testdir), "bc", script + ".bc",
181				        "0", "1", "1", "0", exe ]
182
183				p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE)
184
185				if p.returncode != 0:
186					print("{} test failed:\n".format(test, p.returncode))
187					print(p.stderr.decode())
188					print("\nexiting...")
189					sys.exit(p.returncode)
190
191			print("")
192
193		elif test_num == 0:
194
195			print("Timing Karatsuba Num: {}".format(i), end='', flush=True)
196
197			for j in range(0, nruns):
198
199				cmd = [ exe, "{}/tests/bc/power.txt".format(testdir) ]
200
201				start = time.perf_counter()
202				p = subprocess.run(cmd, input=indata, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
203				end = time.perf_counter()
204
205				if p.returncode != 0:
206					print("bc returned an error; exiting...")
207					sys.exit(p.returncode)
208
209				runs[j] = end - start
210
211			run_times = runs[1:]
212			avg = sum(run_times) / len(run_times)
213
214			times.append(avg)
215			nums.append(i)
216			print(", Time: {}".format(times[i - mn]))
217
218except KeyboardInterrupt:
219	nums = nums[0:i]
220	times = times[0:i]
221
222if test_num == 0:
223
224	opt = nums[times.index(min(times))]
225
226	print("\n\nOptimal Karatsuba Num (for this machine): {}".format(opt))
227	print("Run the following:\n")
228	if "-flto" in config_env["CFLAGS"]:
229		print("CFLAGS=\"-flto\" ./configure.sh -O3 -k {}".format(opt))
230	else:
231		print("./configure.sh -O3 -k {}".format(opt))
232	print("make")
233