From c0cc64f2a7620f3cf7e3ae6cb80ffbb21c5ca6ee Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Thu, 17 Mar 2022 21:34:30 -0700 Subject: [PATCH] convert gfp* instructions to python and add tests --- openpower/sv/bitmanip.mdwn | 48 ++--- openpower/sv/bitmanip/gfpadd.py | 5 + openpower/sv/bitmanip/gfpinv.py | 47 +++++ openpower/sv/bitmanip/gfpmadd.py | 5 + openpower/sv/bitmanip/gfpmsub.py | 5 + openpower/sv/bitmanip/gfpmsubr.py | 5 + openpower/sv/bitmanip/gfpmul.py | 5 + openpower/sv/bitmanip/gfpsub.py | 5 + openpower/sv/bitmanip/test_cl_gfb_gfp.py | 234 +++++++++++++++++++++++ 9 files changed, 324 insertions(+), 35 deletions(-) create mode 100644 openpower/sv/bitmanip/gfpadd.py create mode 100644 openpower/sv/bitmanip/gfpinv.py create mode 100644 openpower/sv/bitmanip/gfpmadd.py create mode 100644 openpower/sv/bitmanip/gfpmsub.py create mode 100644 openpower/sv/bitmanip/gfpmsubr.py create mode 100644 openpower/sv/bitmanip/gfpmul.py create mode 100644 openpower/sv/bitmanip/gfpsub.py diff --git a/openpower/sv/bitmanip.mdwn b/openpower/sv/bitmanip.mdwn index ad120459e..1d17213a4 100644 --- a/openpower/sv/bitmanip.mdwn +++ b/openpower/sv/bitmanip.mdwn @@ -715,13 +715,6 @@ gfbinv RT, RA # Instructions for Prime Galois Fields `GF(p)` -## Helper algorithms - -```python -def int_to_gfp(int_value, prime): - return int_value % prime # follows Python remainder semantics -``` - ## `GFPRIME` SPR -- Prime Modulus For `gfp*` Instructions ## `gfpadd` Prime Galois Field `GF(p)` Addition @@ -730,9 +723,7 @@ def int_to_gfp(int_value, prime): gfpadd RT, RA, RB ``` -``` -(RT) = int_to_gfp((RA) + (RB), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpadd.py" raw="true" feeds="no" actions="yes"]] the addition happens on infinite-precision integers @@ -742,9 +733,7 @@ the addition happens on infinite-precision integers gfpsub RT, RA, RB ``` -``` -(RT) = int_to_gfp((RA) - (RB), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpsub.py" raw="true" feeds="no" actions="yes"]] the subtraction happens on infinite-precision integers @@ -754,9 +743,7 @@ the subtraction happens on infinite-precision integers gfpmul RT, RA, RB ``` -``` -(RT) = int_to_gfp((RA) * (RB), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpmul.py" raw="true" feeds="no" actions="yes"]] the multiplication happens on infinite-precision integers @@ -769,11 +756,7 @@ gfpinv RT, RA Some potential hardware implementations are found in: -``` -(RT) = gfpinv((RA), GFPRIME) -``` - -the multiplication happens on infinite-precision integers +[[!inline pagenames="openpower/sv/bitmanip/gfpinv.py" raw="true" feeds="no" actions="yes"]] ## `gfpmadd` Prime Galois Field `GF(p)` Multiply-Add @@ -781,9 +764,7 @@ the multiplication happens on infinite-precision integers gfpmadd RT, RA, RB, RC ``` -``` -(RT) = int_to_gfp((RA) * (RB) + (RC), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpmadd.py" raw="true" feeds="no" actions="yes"]] the multiplication and addition happens on infinite-precision integers @@ -793,9 +774,7 @@ the multiplication and addition happens on infinite-precision integers gfpmsub RT, RA, RB, RC ``` -``` -(RT) = int_to_gfp((RA) * (RB) - (RC), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpmsub.py" raw="true" feeds="no" actions="yes"]] the multiplication and subtraction happens on infinite-precision integers @@ -805,9 +784,7 @@ the multiplication and subtraction happens on infinite-precision integers gfpmsubr RT, RA, RB, RC ``` -``` -(RT) = int_to_gfp((RC) - (RA) * (RB), GFPRIME) -``` +[[!inline pagenames="openpower/sv/bitmanip/gfpmsubr.py" raw="true" feeds="no" actions="yes"]] the multiplication and subtraction happens on infinite-precision integers @@ -820,14 +797,15 @@ gfpmaddsubr RT, RA, RB, RC TODO: add link to explanation for where `RS` comes from. ``` -product = (RA) * (RB) +factor1 = (RA) +factor2 = (RB) term = (RC) -(RT) = int_to_gfp(product + term, GFPRIME) -(RS) = int_to_gfp(term - product, GFPRIME) +# read all inputs before writing to any outputs in case +# an input overlaps with an output register. +(RT) = gfpmadd(factor1, factor2, term) +(RS) = gfpmsubr(factor1, factor2, term) ``` -the multiplication, addition, and subtraction happens on infinite-precision integers - ## Twin Butterfly (Tukey-Cooley) Mul-add-sub used in combination with SV FFT REMAP to perform diff --git a/openpower/sv/bitmanip/gfpadd.py b/openpower/sv/bitmanip/gfpadd.py new file mode 100644 index 000000000..f00bf8c69 --- /dev/null +++ b/openpower/sv/bitmanip/gfpadd.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpadd(a, b): + return (a + b) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/gfpinv.py b/openpower/sv/bitmanip/gfpinv.py new file mode 100644 index 000000000..e75773abd --- /dev/null +++ b/openpower/sv/bitmanip/gfpinv.py @@ -0,0 +1,47 @@ +from .state import ST + + +def gfpinv(a): + # based on Algorithm ExtEucdInv from: + # https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf + p = ST.GFPRIME + assert p >= 2, "GFPRIME isn't a prime" + assert a != 0, "TODO: decide what happens for division by zero" + assert isinstance(a, int) and 0 < a < p, "a out of range" + if p == 2: + return 1 # the only value possible + + u = p + v = a + r = 0 + s = 1 + while v > 0: + if u & 1 == 0: + u >>= 1 + if r & 1 == 0: + r >>= 1 + else: + r = (r + p) >> 1 + elif v & 1 == 0: + v >>= 1 + if s & 1 == 0: + s >>= 1 + else: + s = (s + p) >> 1 + else: + x = u - v + if x > 0: + u = x + r -= s + if r < 0: + r += p + else: + v = -x + s -= r + if s < 0: + s += p + if r > p: + r -= p + if r < 0: + r += p + return r diff --git a/openpower/sv/bitmanip/gfpmadd.py b/openpower/sv/bitmanip/gfpmadd.py new file mode 100644 index 000000000..e7159a2da --- /dev/null +++ b/openpower/sv/bitmanip/gfpmadd.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpmadd(a, b, c): + return (a * b + c) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/gfpmsub.py b/openpower/sv/bitmanip/gfpmsub.py new file mode 100644 index 000000000..fd0912480 --- /dev/null +++ b/openpower/sv/bitmanip/gfpmsub.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpmsub(a, b, c): + return (a * b - c) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/gfpmsubr.py b/openpower/sv/bitmanip/gfpmsubr.py new file mode 100644 index 000000000..2d349f858 --- /dev/null +++ b/openpower/sv/bitmanip/gfpmsubr.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpmsubr(a, b, c): + return (c - a * b) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/gfpmul.py b/openpower/sv/bitmanip/gfpmul.py new file mode 100644 index 000000000..42c43a233 --- /dev/null +++ b/openpower/sv/bitmanip/gfpmul.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpmul(a, b): + return (a * b) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/gfpsub.py b/openpower/sv/bitmanip/gfpsub.py new file mode 100644 index 000000000..44e5798d7 --- /dev/null +++ b/openpower/sv/bitmanip/gfpsub.py @@ -0,0 +1,5 @@ +from .state import ST + + +def gfpsub(a, b): + return (a - b) % ST.GFPRIME diff --git a/openpower/sv/bitmanip/test_cl_gfb_gfp.py b/openpower/sv/bitmanip/test_cl_gfb_gfp.py index 787deab2a..34133cbe3 100644 --- a/openpower/sv/bitmanip/test_cl_gfb_gfp.py +++ b/openpower/sv/bitmanip/test_cl_gfb_gfp.py @@ -4,6 +4,13 @@ from .clmul import clmul from .gfbmul import gfbmul from .gfbmadd import gfbmadd from .gfbinv import gfbinv +from .gfpadd import gfpadd +from .gfpsub import gfpsub +from .gfpmul import gfpmul +from .gfpinv import gfpinv +from .gfpmadd import gfpmadd +from .gfpmsub import gfpmsub +from .gfpmsubr import gfpmsubr from .pack_poly import pack_poly, unpack_poly import unittest @@ -375,6 +382,133 @@ class TestGFBClass(unittest.TestCase): self.assertEqual(v, expected) +class GFP: + def __init__(self, value, size): + assert isinstance(value, int) + assert isinstance(size, int) and size >= 2, "size is not a prime" + self.value = value % size + self.size = size + + def __repr__(self): + return f"GFP({self.value}, {self.size})" + + def __eq__(self, rhs): + if isinstance(rhs, GFP): + return self.value == rhs.value and self.size == rhs.size + return NotImplemented + + def __add__(self, rhs): + assert isinstance(rhs, GFP) + assert self.size == rhs.size + return GFP((self.value + rhs.value) % self.size, self.size) + + def __sub__(self, rhs): + assert isinstance(rhs, GFP) + assert self.size == rhs.size + return GFP((self.value - rhs.value) % self.size, self.size) + + def __mul__(self, rhs): + assert isinstance(rhs, GFP) + assert self.size == rhs.size + return GFP((self.value * rhs.value) % self.size, self.size) + + def __div__(self, rhs): + assert isinstance(rhs, GFP) + assert self.size == rhs.size + return self * rhs ** -1 + + @property + def __pow_period(self): + period = self.size - 1 + assert period > 0, "internal logic error" + return period + + def __pow__(self, exponent): + assert isinstance(exponent, int) + if self.value == 0: + if exponent < 0: + raise ZeroDivisionError + else: + return GFP(self.value, self.size) + exponent %= self.__pow_period + return GFP(pow(self.value, exponent, self.size), self.size) + + +PRIMES = 2, 3, 5, 7, 11, 13, 17, 19 +"""handy list of small primes for testing""" + + +class TestGFPClass(unittest.TestCase): + def test_add_sub(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + with self.subTest(av=av, bv=bv, prime=prime): + a = GFP(av, prime) + b = GFP(bv, prime) + expected = GFP((av + bv) % prime, prime) + c = a + b + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + c = b + a + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + expected = GFP((av - bv) % prime, prime) + c = a - b + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + expected = GFP((bv - av) % prime, prime) + c = b - a + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + + def test_mul(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + with self.subTest(av=av, bv=bv, prime=prime): + a = GFP(av, prime) + b = GFP(bv, prime) + expected = GFP((av * bv) % prime, prime) + c = a * b + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + c = b * a + self.assertEqual(a, GFP(av, prime)) + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(c, expected) + + def test_pow(self): + for prime in PRIMES: + for bv in range(prime): + with self.subTest(bv=bv, prime=prime): + b = GFP(bv, prime) + period = prime - 1 + e = period - 1 + expected = GFP(pow(bv, e, prime) if bv != 0 else 0, prime) + v = b ** e + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(v, expected) + e = -1 + if bv != 0: + v = b ** e + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(v, expected) + + # test that pow doesn't take inordinately long when given + # a modulus. adding a multiple of `period` should leave + # results unchanged. + e += period * 10 ** 15 + v = b ** e + self.assertEqual(b, GFP(bv, prime)) + self.assertEqual(v, expected) + + class TestCL(unittest.TestCase): def test_cldivrem(self): n_width = 8 @@ -463,5 +597,105 @@ class TestGFBInstructions(unittest.TestCase): self.assertEqual(result, expectedv) +class TestGFPInstructions(unittest.TestCase): + def test_gfpadd(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + expected = a + b + with self.subTest(a=str(a), b=str(b), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpadd(av, bv) + self.assertEqual(v, expected.value) + + def test_gfpsub(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + expected = a - b + with self.subTest(a=str(a), b=str(b), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpsub(av, bv) + self.assertEqual(v, expected.value) + + def test_gfpmul(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + expected = a * b + with self.subTest(a=str(a), b=str(b), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpmul(av, bv) + self.assertEqual(v, expected.value) + + def test_gfpinv(self): + for prime in PRIMES: + for av in range(prime): + a = GFP(av, prime) + if av == 0: + # TODO: determine what's expected for division by zero + continue + else: + expected = a ** -1 + with self.subTest(a=str(a), expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpinv(av) + self.assertEqual(v, expected.value) + + def test_gfpmadd(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + for cv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + c = GFP(cv, prime) + expected = a * b + c + with self.subTest(a=str(a), b=str(b), c=str(c), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpmadd(av, bv, cv) + self.assertEqual(v, expected.value) + + def test_gfpmsub(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + for cv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + c = GFP(cv, prime) + expected = a * b - c + with self.subTest(a=str(a), b=str(b), c=str(c), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpmsub(av, bv, cv) + self.assertEqual(v, expected.value) + + def test_gfpmsubr(self): + for prime in PRIMES: + for av in range(prime): + for bv in range(prime): + for cv in range(prime): + a = GFP(av, prime) + b = GFP(bv, prime) + c = GFP(cv, prime) + expected = c - a * b + with self.subTest(a=str(a), b=str(b), c=str(c), + expected=str(expected)): + ST.reinit(GFPRIME=prime) + v = gfpmsubr(av, bv, cv) + self.assertEqual(v, expected.value) + + if __name__ == "__main__": unittest.main() -- 2.30.2