openpower/sv/bitmanip/test_cl_gfb_gfp.py

   1 from .cldivrem import cldivrem
   2 from .clmul import clmul
   3 from .pack_poly import pack_poly, unpack_poly
   4 import unittest
   5
   6
   7 class GF2Poly:
   8     """Polynomial with GF(2) coefficients.
   9
  10     `self.coefficients`: a list where `coefficients[-1] != 0`.
  11     `coefficients[i]` is the coefficient for `x ** i`.
  12     """
  13
  14     def __init__(self, coefficients=None):
  15         self.coefficients = []
  16         if coefficients is not None:
  17             if not isinstance(coefficients, (tuple, list)):
  18                 coefficients = list(coefficients)
  19             # reversed to resize self.coefficients once
  20             for i in reversed(range(len(coefficients))):
  21                 self[i] = coefficients[i]
  22
  23     def __len__(self):
  24         return len(self.coefficients)
  25
  26     @property
  27     def degree(self):
  28         return len(self) - 1
  29
  30     @property
  31     def lc(self):
  32         """leading coefficient."""
  33         return 0 if len(self) == 0 else self.coefficients[-1]
  34
  35     def __getitem__(self, key):
  36         assert key >= 0
  37         if key < len(self):
  38             return self.coefficients[key]
  39         return 0
  40
  41     def __setitem__(self, key, value):
  42         assert key >= 0
  43         assert value == 0 or value == 1
  44         if key < len(self):
  45             self.coefficients[key] = value
  46             while len(self) and self.coefficients[-1] == 0:
  47                 self.coefficients.pop()
  48         elif value != 0:
  49             self.coefficients += [0] * (key + 1 - len(self))
  50             self.coefficients[key] = value
  51
  52     def __repr__(self):
  53         return f"GF2Poly({self.coefficients})"
  54
  55     def __iadd__(self, rhs):
  56         for i in range(max(len(self), len(rhs))):
  57             self[i] ^= rhs[i]
  58         return self
  59
  60     def __add__(self, rhs):
  61         return GF2Poly(self).__iadd__(rhs)
  62
  63     def __isub__(self, rhs):
  64         return self.__iadd__(rhs)
  65
  66     def __sub__(self, rhs):
  67         return self.__add__(rhs)
  68
  69     def __iter__(self):
  70         return iter(self.coefficients)
  71
  72     def __mul__(self, rhs):
  73         retval = GF2Poly()
  74         # reversed to resize retval.coefficients once
  75         for i in reversed(range(len(self))):
  76             if self[i]:
  77                 for j in reversed(range(len(rhs))):
  78                     retval[i + j] ^= rhs[j]
  79         return retval
  80
  81     def __ilshift__(self, amount):
  82         """multiplies `self` by the polynomial `x**amount`"""
  83         if len(self) != 0:
  84             self.coefficients[:0] = [0] * amount
  85         return self
  86
  87     def __lshift__(self, amount):
  88         """returns the polynomial `self * x**amount`"""
  89         return GF2Poly(self).__ilshift__(amount)
  90
  91     def __irshift__(self, amount):
  92         """divides `self` by the polynomial `x**amount`, discarding the
  93             remainder.
  94         """
  95         if amount < len(self):
  96             del self.coefficients[:amount]
  97         else:
  98             del self.coefficients[:]
  99         return self
 100
 101     def __rshift__(self, amount):
 102         """divides `self` by the polynomial `x**amount`, discarding the
 103             remainder.
 104         """
 105         return GF2Poly(self).__irshift__(amount)
 106
 107     def __divmod__(self, divisor):
 108         # based on https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division
 109         assert isinstance(divisor, GF2Poly)
 110         if len(divisor) == 0:
 111             raise ZeroDivisionError
 112         q = GF2Poly()
 113         r = GF2Poly(self)
 114         while r.degree >= divisor.degree:
 115             shift = r.degree - divisor.degree
 116             q[shift] ^= 1
 117             r -= divisor << shift
 118         return q, r
 119
 120     def __floordiv__(self, divisor):
 121         q, r = divmod(self, divisor)
 122         return q
 123
 124     def __mod__(self, divisor):
 125         q, r = divmod(self, divisor)
 126         return r
 127
 128     def __eq__(self, rhs):
 129         if isinstance(rhs, GF2Poly):
 130             return self.coefficients == rhs.coefficients
 131         return NotImplemented
 132
 133
 134 class TestGF2Poly(unittest.TestCase):
 135     def test_add(self):
 136         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 137         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0])
 138         c = a + b
 139         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 140         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 141         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1]))
 142         c = b + a
 143         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 144         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 145         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1]))
 146         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 147         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1])
 148         c = a + b
 149         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 150         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]))
 151         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 152         c = a - b
 153         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 154         c = b - a
 155         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 156
 157     def test_shift(self):
 158         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 159         c = a << 0
 160         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 161         self.assertEqual(c, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 162         c = a << 5
 163         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 164         self.assertEqual(c, GF2Poly(
 165             [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 166         c = a << 10
 167         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 168         self.assertEqual(c, GF2Poly(
 169             [0] * 10 + [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 170         c = a >> 0
 171         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 172         self.assertEqual(c, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 173         c = a >> 5
 174         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 175         self.assertEqual(c, GF2Poly([1, 1, 0, 1, 0, 1]))
 176         c = a >> 10
 177         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 178         self.assertEqual(c, GF2Poly([1]))
 179         c = a >> 11
 180         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 181         self.assertEqual(c, GF2Poly([]))
 182         c = a >> 100
 183         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 184         self.assertEqual(c, GF2Poly([]))
 185
 186     def test_mul(self):
 187         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 188         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1])
 189         c = a * b
 190         expected = GF2Poly([0, 0, 1, 0, 1, 0, 1, 1, 1, 0,
 191                             0, 1, 0, 1, 1, 0, 0, 1, 1])
 192         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 193         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 194         self.assertEqual(c, expected)
 195
 196     def test_divmod(self):
 197         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 198         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1])
 199         q, r = divmod(a, b)
 200         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 201         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 202         self.assertEqual(q, GF2Poly([1, 1, 1]))
 203         self.assertEqual(r, GF2Poly([1, 0, 1, 0, 0, 1, 0, 1]))
 204         q = a // b
 205         self.assertEqual(q, GF2Poly([1, 1, 1]))
 206         r = a % b
 207         self.assertEqual(r, GF2Poly([1, 0, 1, 0, 0, 1, 0, 1]))
 208
 209
 210 class TestCL(unittest.TestCase):
 211     def test_cldivrem(self):
 212         n_width = 8
 213         d_width = 4
 214         width = max(n_width, d_width)
 215         for nv in range(2 ** n_width):
 216             n = GF2Poly(unpack_poly(nv))
 217             for dv in range(1, 2 ** d_width):
 218                 d = GF2Poly(unpack_poly(dv))
 219                 with self.subTest(n=str(n), nv=nv, d=str(d), dv=dv):
 220                     q_expected, r_expected = divmod(n, d)
 221                     self.assertEqual(q_expected * d + r_expected, n)
 222                     q, r = cldivrem(nv, dv, width)
 223                     q_expected = pack_poly(q_expected.coefficients)
 224                     r_expected = pack_poly(r_expected.coefficients)
 225                     self.assertEqual((q, r), (q_expected, r_expected))
 226
 227     def test_clmul(self):
 228         a_width = 5
 229         b_width = 5
 230         for av in range(2 ** a_width):
 231             a = GF2Poly(unpack_poly(av))
 232             for bv in range(2 ** b_width):
 233                 b = GF2Poly(unpack_poly(bv))
 234                 with self.subTest(a=str(a), av=av, b=str(b), bv=bv):
 235                     expected = a * b
 236                     product = clmul(av, bv)
 237                     expected = pack_poly(expected.coefficients)
 238                     self.assertEqual(product, expected)
 239
 240
 241 if __name__ == "__main__":
 242     unittest.main()