From 0f4a014cf9cb7dfb8a2ba2b64494408cc80d8c1c Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Fri, 6 Oct 2023 15:21:07 -0700 Subject: [PATCH] rename divmod algorithm -> divmod_shift_sub in prep for adding divmod based on Knuth's Algorithm D --- src/openpower/decoder/isa/test_caller_svp64_powmod.py | 7 ++++--- src/openpower/test/bigint/powmod.py | 11 ++++++----- 2 files changed, 10 insertions(+), 8 deletions(-) diff --git a/src/openpower/decoder/isa/test_caller_svp64_powmod.py b/src/openpower/decoder/isa/test_caller_svp64_powmod.py index 055b40d4..1ea02a23 100644 --- a/src/openpower/decoder/isa/test_caller_svp64_powmod.py +++ b/src/openpower/decoder/isa/test_caller_svp64_powmod.py @@ -15,18 +15,19 @@ import unittest from functools import lru_cache import os from openpower.test.bigint.powmod import ( - PowModCases, python_divmod_algorithm, python_powmod_256_algorithm) + PowModCases, python_divmod_shift_sub_algorithm, + python_powmod_256_algorithm) from openpower.test.runner import TestRunnerBase class TestPythonAlgorithms(unittest.TestCase): - def test_python_divmod_algorithm(self): + def test_python_divmod_shift_sub_algorithm(self): for n, d in PowModCases.divmod_512x256_to_256x256_test_inputs(): q, r = divmod(n, d) with self.subTest(n=f"{n:#_x}", d=f"{d:#_x}", q=f"{q:#_x}", r=f"{r:#_x}"): log_regex = n == 2 ** 511 - 1 and d == 2 ** 256 - 1 - out_q, out_r = python_divmod_algorithm( + out_q, out_r = python_divmod_shift_sub_algorithm( n, d, log_regex=log_regex) with self.subTest(out_q=f"{out_q:#_x}", out_r=f"{out_r:#_x}"): self.assertEqual(out_q, q) diff --git a/src/openpower/test/bigint/powmod.py b/src/openpower/test/bigint/powmod.py index 4f2f2d93..f17139b0 100644 --- a/src/openpower/test/bigint/powmod.py +++ b/src/openpower/test/bigint/powmod.py @@ -123,7 +123,7 @@ def python_mul_algorithm2(a, b): return y -DIVMOD_512x256_TO_256x256_ASM = ( +DIVMOD_SHIFT_SUB_512x256_TO_256x256_ASM = ( # extremely slow and simplistic shift and subtract algorithm. # a future task is to rewrite to use Knuth's Algorithm D, # which is generally an order of magnitude faster @@ -228,7 +228,7 @@ class _DivModRegsRegexLogger: log("DIVMOD REGEX:", "".join(segments)) -def python_divmod_algorithm(n, d, width=256, log_regex=False): +def python_divmod_shift_sub_algorithm(n, d, width=256, log_regex=False): assert n >= 0 and d > 0 and width > 0 and n < (d << width), "invalid input" do_log = _DivModRegsRegexLogger(enabled=log_regex).log @@ -332,7 +332,7 @@ POWMOD_256_ASM = ( "sv.ld *14, -144(1)", # restore all callee-save registers "bclr 20, 0, 0 # blr", *MUL_256_X_256_TO_512_ASM, - *DIVMOD_512x256_TO_256x256_ASM, + *DIVMOD_SHIFT_SUB_512x256_TO_256x256_ASM, ) @@ -409,7 +409,7 @@ class PowModCases(TestAccumulatorBase): n -= d << 256 yield (n, d) - def case_divmod_512x256_to_256x256(self): + def case_divmod_shift_sub_512x256_to_256x256(self): for n, d in self.divmod_512x256_to_256x256_test_inputs(): q, r = divmod(n, d) with self.subTest(n=f"{n:#_x}", d=f"{d:#_x}", @@ -434,7 +434,8 @@ class PowModCases(TestAccumulatorBase): # write r in LE order to regs 8-11 e.intregs[8 + i] = (r >> (64 * i)) % 2**64 - self.call_case(DIVMOD_512x256_TO_256x256_ASM, e, initial_regs) + self.call_case( + DIVMOD_SHIFT_SUB_512x256_TO_256x256_ASM, e, initial_regs) @staticmethod def powmod_256_test_inputs(): -- 2.30.2