gf_reference/test_cl_gfb_gfp.py

   1 from nmigen_gf.reference.state import ST
   2 from nmigen_gf.reference.cldivrem import cldivrem
   3 from nmigen_gf.reference.clmul import clmul
   4 from nmigen_gf.reference.gfbmul import gfbmul
   5 from nmigen_gf.reference.gfbmadd import gfbmadd
   6 from nmigen_gf.reference.gfbinv import gfbinv
   7 from nmigen_gf.reference.gfpadd import gfpadd
   8 from nmigen_gf.reference.gfpsub import gfpsub
   9 from nmigen_gf.reference.gfpmul import gfpmul
  10 from nmigen_gf.reference.gfpinv import gfpinv
  11 from nmigen_gf.reference.gfpmadd import gfpmadd
  12 from nmigen_gf.reference.gfpmsub import gfpmsub
  13 from nmigen_gf.reference.gfpmsubr import gfpmsubr
  14 from nmigen_gf.reference.pack_poly import pack_poly, unpack_poly
  15 import unittest
  16
  17
  18 class GF2Poly:
  19     """Polynomial with GF(2) coefficients.
  20
  21     `self.coefficients`: a list where `coefficients[-1] != 0`.
  22     `coefficients[i]` is the coefficient for `x ** i`.
  23     """
  24
  25     def __init__(self, coefficients=None):
  26         self.coefficients = []
  27         if coefficients is not None:
  28             if not isinstance(coefficients, (tuple, list)):
  29                 coefficients = list(coefficients)
  30             # reversed to resize self.coefficients once
  31             for i in reversed(range(len(coefficients))):
  32                 self[i] = coefficients[i]
  33
  34     def __len__(self):
  35         return len(self.coefficients)
  36
  37     @property
  38     def degree(self):
  39         return len(self) - 1
  40
  41     @property
  42     def lc(self):
  43         """leading coefficient."""
  44         return 0 if len(self) == 0 else self.coefficients[-1]
  45
  46     def __getitem__(self, key):
  47         assert key >= 0
  48         if key < len(self):
  49             return self.coefficients[key]
  50         return 0
  51
  52     def __setitem__(self, key, value):
  53         assert key >= 0
  54         assert value == 0 or value == 1
  55         if key < len(self):
  56             self.coefficients[key] = value
  57             while len(self) and self.coefficients[-1] == 0:
  58                 self.coefficients.pop()
  59         elif value != 0:
  60             self.coefficients += [0] * (key + 1 - len(self))
  61             self.coefficients[key] = value
  62
  63     def __repr__(self):
  64         return f"GF2Poly({self.coefficients})"
  65
  66     def __iadd__(self, rhs):
  67         for i in range(max(len(self), len(rhs))):
  68             self[i] ^= rhs[i]
  69         return self
  70
  71     def __add__(self, rhs):
  72         return GF2Poly(self).__iadd__(rhs)
  73
  74     def __isub__(self, rhs):
  75         return self.__iadd__(rhs)
  76
  77     def __sub__(self, rhs):
  78         return self.__add__(rhs)
  79
  80     def __iter__(self):
  81         return iter(self.coefficients)
  82
  83     def __mul__(self, rhs):
  84         retval = GF2Poly()
  85         # reversed to resize retval.coefficients once
  86         for i in reversed(range(len(self))):
  87             if self[i]:
  88                 for j in reversed(range(len(rhs))):
  89                     retval[i + j] ^= rhs[j]
  90         return retval
  91
  92     def __ilshift__(self, amount):
  93         """multiplies `self` by the polynomial `x**amount`"""
  94         if len(self) != 0:
  95             self.coefficients[:0] = [0] * amount
  96         return self
  97
  98     def __lshift__(self, amount):
  99         """returns the polynomial `self * x**amount`"""
 100         return GF2Poly(self).__ilshift__(amount)
 101
 102     def __irshift__(self, amount):
 103         """divides `self` by the polynomial `x**amount`, discarding the
 104             remainder.
 105         """
 106         if amount < len(self):
 107             del self.coefficients[:amount]
 108         else:
 109             del self.coefficients[:]
 110         return self
 111
 112     def __rshift__(self, amount):
 113         """divides `self` by the polynomial `x**amount`, discarding the
 114             remainder.
 115         """
 116         return GF2Poly(self).__irshift__(amount)
 117
 118     def __divmod__(self, divisor):
 119         # based on https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division
 120         assert isinstance(divisor, GF2Poly)
 121         if len(divisor) == 0:
 122             raise ZeroDivisionError
 123         q = GF2Poly()
 124         r = GF2Poly(self)
 125         while r.degree >= divisor.degree:
 126             shift = r.degree - divisor.degree
 127             q[shift] ^= 1
 128             r -= divisor << shift
 129         return q, r
 130
 131     def __floordiv__(self, divisor):
 132         q, r = divmod(self, divisor)
 133         return q
 134
 135     def __mod__(self, divisor):
 136         q, r = divmod(self, divisor)
 137         return r
 138
 139     def __pow__(self, exponent, modulus=None):
 140         assert isinstance(exponent, int) and exponent >= 0
 141         assert modulus is None or isinstance(modulus, GF2Poly)
 142         retval = GF2Poly([1])
 143         pow2 = GF2Poly(self)
 144         while exponent != 0:
 145             if exponent & 1:
 146                 retval *= pow2
 147                 if modulus is not None:
 148                     retval %= modulus
 149                 exponent &= ~1
 150             else:
 151                 pow2 *= pow2
 152                 if modulus is not None:
 153                     pow2 %= modulus
 154                 exponent >>= 1
 155         return retval
 156
 157     def __eq__(self, rhs):
 158         if isinstance(rhs, GF2Poly):
 159             return self.coefficients == rhs.coefficients
 160         return NotImplemented
 161
 162
 163 class TestGF2Poly(unittest.TestCase):
 164     def test_add(self):
 165         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 166         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0])
 167         c = a + b
 168         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 169         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 170         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1]))
 171         c = b + a
 172         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 173         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 174         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1]))
 175         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 176         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1])
 177         c = a + b
 178         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 179         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]))
 180         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 181         c = a - b
 182         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 183         c = b - a
 184         self.assertEqual(c, GF2Poly([1, 0, 1, 1, 1, 0, 0, 1]))
 185
 186     def test_shift(self):
 187         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 188         c = a << 0
 189         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 190         self.assertEqual(c, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 191         c = a << 5
 192         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 193         self.assertEqual(c, GF2Poly(
 194             [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 195         c = a << 10
 196         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 197         self.assertEqual(c, GF2Poly(
 198             [0] * 10 + [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 199         c = a >> 0
 200         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 201         self.assertEqual(c, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 202         c = a >> 5
 203         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 204         self.assertEqual(c, GF2Poly([1, 1, 0, 1, 0, 1]))
 205         c = a >> 10
 206         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 207         self.assertEqual(c, GF2Poly([1]))
 208         c = a >> 11
 209         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 210         self.assertEqual(c, GF2Poly([]))
 211         c = a >> 100
 212         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 213         self.assertEqual(c, GF2Poly([]))
 214
 215     def test_mul(self):
 216         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 217         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1])
 218         c = a * b
 219         expected = GF2Poly([0, 0, 1, 0, 1, 0, 1, 1, 1, 0,
 220                             0, 1, 0, 1, 1, 0, 0, 1, 1])
 221         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 222         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 223         self.assertEqual(c, expected)
 224
 225     def test_divmod(self):
 226         a = GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1])
 227         b = GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1])
 228         q, r = divmod(a, b)
 229         self.assertEqual(a, GF2Poly([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]))
 230         self.assertEqual(b, GF2Poly([0, 0, 1, 0, 1, 1, 1, 1, 1]))
 231         self.assertEqual(q, GF2Poly([1, 1, 1]))
 232         self.assertEqual(r, GF2Poly([1, 0, 1, 0, 0, 1, 0, 1]))
 233         q = a // b
 234         self.assertEqual(q, GF2Poly([1, 1, 1]))
 235         r = a % b
 236         self.assertEqual(r, GF2Poly([1, 0, 1, 0, 0, 1, 0, 1]))
 237
 238     def test_pow(self):
 239         b = GF2Poly([0, 1])
 240         for e in range(8):
 241             expected = GF2Poly([0] * e + [1])
 242             with self.subTest(b=str(b), e=e, expected=str(expected)):
 243                 v = b ** e
 244                 self.assertEqual(b, GF2Poly([0, 1]))
 245                 self.assertEqual(v, expected)
 246
 247         # AES's finite field reducing polynomial
 248         m = GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1])
 249         period = 2 ** m.degree - 1
 250         b = GF2Poly([1, 1, 0, 0, 1, 0, 1])
 251         e = period - 1
 252         expected = GF2Poly([0, 1, 0, 1, 0, 0, 1, 1])
 253         v = pow(b, e, m)
 254         self.assertEqual(m, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 255         self.assertEqual(b, GF2Poly([1, 1, 0, 0, 1, 0, 1]))
 256         self.assertEqual(v, expected)
 257
 258         # test that pow doesn't take inordinately long when given a modulus.
 259         # adding a multiple of `period` should leave results unchanged.
 260         e += period * 10 ** 15
 261         v = pow(b, e, m)
 262         self.assertEqual(m, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 263         self.assertEqual(b, GF2Poly([1, 1, 0, 0, 1, 0, 1]))
 264         self.assertEqual(v, expected)
 265
 266
 267 class GFB:
 268     def __init__(self, value, red_poly=None):
 269         if isinstance(value, GFB):
 270             # copy value
 271             assert red_poly is None
 272             self.red_poly = GF2Poly(value.red_poly)
 273             self.value = GF2Poly(value.value)
 274             return
 275         assert isinstance(value, GF2Poly)
 276         assert isinstance(red_poly, GF2Poly)
 277         assert red_poly.degree > 0
 278         self.value = value % red_poly
 279         self.red_poly = red_poly
 280
 281     def __repr__(self):
 282         return f"GFB({self.value}, {self.red_poly})"
 283
 284     def __add__(self, rhs):
 285         assert isinstance(rhs, GFB)
 286         assert self.red_poly == rhs.red_poly
 287         return GFB((self.value + rhs.value) % self.red_poly, self.red_poly)
 288
 289     def __sub__(self, rhs):
 290         return self.__add__(rhs)
 291
 292     def __eq__(self, rhs):
 293         if isinstance(rhs, GFB):
 294             return self.value == rhs.value and self.red_poly == rhs.red_poly
 295         return NotImplemented
 296
 297     def __mul__(self, rhs):
 298         assert isinstance(rhs, GFB)
 299         assert self.red_poly == rhs.red_poly
 300         return GFB((self.value * rhs.value) % self.red_poly, self.red_poly)
 301
 302     def __div__(self, rhs):
 303         assert isinstance(rhs, GFB)
 304         assert self.red_poly == rhs.red_poly
 305         return self * rhs ** -1
 306
 307     @property
 308     def __pow_period(self):
 309         period = (1 << self.red_poly.degree) - 1
 310         assert period > 0, "internal logic error"
 311         return period
 312
 313     def __pow__(self, exponent):
 314         assert isinstance(exponent, int)
 315         if len(self.value) == 0:
 316             if exponent < 0:
 317                 raise ZeroDivisionError
 318             else:
 319                 return GFB(self)
 320         exponent %= self.__pow_period
 321         return GFB(pow(self.value, exponent, self.red_poly), self.red_poly)
 322
 323
 324 class TestGFBClass(unittest.TestCase):
 325     def test_add(self):
 326         # AES's finite field reducing polynomial
 327         red_poly = GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1])
 328         a = GFB(GF2Poly([0, 1, 0, 1]), red_poly)
 329         b = GFB(GF2Poly([0, 0, 0, 0, 0, 0, 1, 1]), red_poly)
 330         expected = GFB(GF2Poly([0, 1, 0, 1, 0, 0, 1, 1]), red_poly)
 331         c = a + b
 332         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 333         self.assertEqual(a, GFB(GF2Poly([0, 1, 0, 1]), red_poly))
 334         self.assertEqual(b, GFB(GF2Poly([0, 0, 0, 0, 0, 0, 1, 1]), red_poly))
 335         self.assertEqual(c, expected)
 336         c = a - b
 337         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 338         self.assertEqual(a, GFB(GF2Poly([0, 1, 0, 1]), red_poly))
 339         self.assertEqual(b, GFB(GF2Poly([0, 0, 0, 0, 0, 0, 1, 1]), red_poly))
 340         self.assertEqual(c, expected)
 341         c = b - a
 342         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 343         self.assertEqual(a, GFB(GF2Poly([0, 1, 0, 1]), red_poly))
 344         self.assertEqual(b, GFB(GF2Poly([0, 0, 0, 0, 0, 0, 1, 1]), red_poly))
 345         self.assertEqual(c, expected)
 346
 347     def test_mul(self):
 348         # AES's finite field reducing polynomial
 349         red_poly = GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1])
 350         a = GFB(GF2Poly([0, 1, 0, 1, 0, 0, 1, 1]), red_poly)
 351         b = GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly)
 352         expected = GFB(GF2Poly([1]), red_poly)
 353         c = a * b
 354         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 355         self.assertEqual(a, GFB(GF2Poly([0, 1, 0, 1, 0, 0, 1, 1]), red_poly))
 356         self.assertEqual(b, GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly))
 357         self.assertEqual(c, expected)
 358
 359     def test_pow(self):
 360         # AES's finite field reducing polynomial
 361         red_poly = GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1])
 362         period = 2 ** red_poly.degree - 1
 363         b = GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly)
 364         e = period - 1
 365         expected = GFB(GF2Poly([0, 1, 0, 1, 0, 0, 1, 1]), red_poly)
 366         v = b ** e
 367         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 368         self.assertEqual(b, GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly))
 369         self.assertEqual(v, expected)
 370         e = -1
 371         v = b ** e
 372         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 373         self.assertEqual(b, GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly))
 374         self.assertEqual(v, expected)
 375
 376         # test that pow doesn't take inordinately long when given a modulus.
 377         # adding a multiple of `period` should leave results unchanged.
 378         e += period * 10 ** 15
 379         v = b ** e
 380         self.assertEqual(red_poly, GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1]))
 381         self.assertEqual(b, GFB(GF2Poly([1, 1, 0, 0, 1, 0, 1]), red_poly))
 382         self.assertEqual(v, expected)
 383
 384
 385 class GFP:
 386     def __init__(self, value, size):
 387         assert isinstance(value, int)
 388         assert isinstance(size, int) and size >= 2, "size is not a prime"
 389         self.value = value % size
 390         self.size = size
 391
 392     def __repr__(self):
 393         return f"GFP({self.value}, {self.size})"
 394
 395     def __eq__(self, rhs):
 396         if isinstance(rhs, GFP):
 397             return self.value == rhs.value and self.size == rhs.size
 398         return NotImplemented
 399
 400     def __add__(self, rhs):
 401         assert isinstance(rhs, GFP)
 402         assert self.size == rhs.size
 403         return GFP((self.value + rhs.value) % self.size, self.size)
 404
 405     def __sub__(self, rhs):
 406         assert isinstance(rhs, GFP)
 407         assert self.size == rhs.size
 408         return GFP((self.value - rhs.value) % self.size, self.size)
 409
 410     def __mul__(self, rhs):
 411         assert isinstance(rhs, GFP)
 412         assert self.size == rhs.size
 413         return GFP((self.value * rhs.value) % self.size, self.size)
 414
 415     def __div__(self, rhs):
 416         assert isinstance(rhs, GFP)
 417         assert self.size == rhs.size
 418         return self * rhs ** -1
 419
 420     @property
 421     def __pow_period(self):
 422         period = self.size - 1
 423         assert period > 0, "internal logic error"
 424         return period
 425
 426     def __pow__(self, exponent):
 427         assert isinstance(exponent, int)
 428         if self.value == 0:
 429             if exponent < 0:
 430                 raise ZeroDivisionError
 431             else:
 432                 return GFP(self.value, self.size)
 433         exponent %= self.__pow_period
 434         return GFP(pow(self.value, exponent, self.size), self.size)
 435
 436
 437 PRIMES = 2, 3, 5, 7, 11, 13, 17, 19
 438 """handy list of small primes for testing"""
 439
 440
 441 class TestGFPClass(unittest.TestCase):
 442     def test_add_sub(self):
 443         for prime in PRIMES:
 444             for av in range(prime):
 445                 for bv in range(prime):
 446                     with self.subTest(av=av, bv=bv, prime=prime):
 447                         a = GFP(av, prime)
 448                         b = GFP(bv, prime)
 449                         expected = GFP((av + bv) % prime, prime)
 450                         c = a + b
 451                         self.assertEqual(a, GFP(av, prime))
 452                         self.assertEqual(b, GFP(bv, prime))
 453                         self.assertEqual(c, expected)
 454                         c = b + a
 455                         self.assertEqual(a, GFP(av, prime))
 456                         self.assertEqual(b, GFP(bv, prime))
 457                         self.assertEqual(c, expected)
 458                         expected = GFP((av - bv) % prime, prime)
 459                         c = a - b
 460                         self.assertEqual(a, GFP(av, prime))
 461                         self.assertEqual(b, GFP(bv, prime))
 462                         self.assertEqual(c, expected)
 463                         expected = GFP((bv - av) % prime, prime)
 464                         c = b - a
 465                         self.assertEqual(a, GFP(av, prime))
 466                         self.assertEqual(b, GFP(bv, prime))
 467                         self.assertEqual(c, expected)
 468
 469     def test_mul(self):
 470         for prime in PRIMES:
 471             for av in range(prime):
 472                 for bv in range(prime):
 473                     with self.subTest(av=av, bv=bv, prime=prime):
 474                         a = GFP(av, prime)
 475                         b = GFP(bv, prime)
 476                         expected = GFP((av * bv) % prime, prime)
 477                         c = a * b
 478                         self.assertEqual(a, GFP(av, prime))
 479                         self.assertEqual(b, GFP(bv, prime))
 480                         self.assertEqual(c, expected)
 481                         c = b * a
 482                         self.assertEqual(a, GFP(av, prime))
 483                         self.assertEqual(b, GFP(bv, prime))
 484                         self.assertEqual(c, expected)
 485
 486     def test_pow(self):
 487         for prime in PRIMES:
 488             for bv in range(prime):
 489                 with self.subTest(bv=bv, prime=prime):
 490                     b = GFP(bv, prime)
 491                     period = prime - 1
 492                     e = period - 1
 493                     expected = GFP(pow(bv, e, prime) if bv != 0 else 0, prime)
 494                     v = b ** e
 495                     self.assertEqual(b, GFP(bv, prime))
 496                     self.assertEqual(v, expected)
 497                     e = -1
 498                     if bv != 0:
 499                         v = b ** e
 500                         self.assertEqual(b, GFP(bv, prime))
 501                         self.assertEqual(v, expected)
 502
 503                     # test that pow doesn't take inordinately long when given
 504                     # a modulus. adding a multiple of `period` should leave
 505                     # results unchanged.
 506                     e += period * 10 ** 15
 507                     v = b ** e
 508                     self.assertEqual(b, GFP(bv, prime))
 509                     self.assertEqual(v, expected)
 510
 511
 512 class TestCL(unittest.TestCase):
 513     def test_cldivrem(self):
 514         n_width = 8
 515         d_width = 4
 516         width = max(n_width, d_width)
 517         for nv in range(2 ** n_width):
 518             n = GF2Poly(unpack_poly(nv))
 519             for dv in range(1, 2 ** d_width):
 520                 d = GF2Poly(unpack_poly(dv))
 521                 with self.subTest(n=str(n), nv=nv, d=str(d), dv=dv):
 522                     q_expected, r_expected = divmod(n, d)
 523                     self.assertEqual(q_expected * d + r_expected, n)
 524                     q, r = cldivrem(nv, dv, width)
 525                     q_expected = pack_poly(q_expected.coefficients)
 526                     r_expected = pack_poly(r_expected.coefficients)
 527                     self.assertEqual((q, r), (q_expected, r_expected))
 528
 529     def test_clmul(self):
 530         a_width = 5
 531         b_width = 5
 532         for av in range(2 ** a_width):
 533             a = GF2Poly(unpack_poly(av))
 534             for bv in range(2 ** b_width):
 535                 b = GF2Poly(unpack_poly(bv))
 536                 with self.subTest(a=str(a), av=av, b=str(b), bv=bv):
 537                     expected = a * b
 538                     product = clmul(av, bv)
 539                     expected = pack_poly(expected.coefficients)
 540                     self.assertEqual(product, expected)
 541
 542
 543 class TestGFBInstructions(unittest.TestCase):
 544     @staticmethod
 545     def init_aes_red_poly():
 546         # AES's finite field reducing polynomial
 547         red_poly = GF2Poly([1, 1, 0, 1, 1, 0, 0, 0, 1])
 548         ST.reinit(GFBREDPOLY=pack_poly(red_poly.coefficients))
 549         return red_poly
 550
 551     def test_gfbmul(self):
 552         # AES's finite field reducing polynomial
 553         red_poly = self.init_aes_red_poly()
 554         a_width = 8
 555         b_width = 4
 556         for av in range(2 ** a_width):
 557             a = GFB(GF2Poly(unpack_poly(av)), red_poly)
 558             for bv in range(2 ** b_width):
 559                 b = GFB(GF2Poly(unpack_poly(bv)), red_poly)
 560                 expected = a * b
 561                 with self.subTest(a=str(a), av=av, b=str(b), bv=bv, expected=str(expected)):
 562                     product = gfbmul(av, bv)
 563                     expectedv = pack_poly(expected.value.coefficients)
 564                     self.assertEqual(product, expectedv)
 565
 566     def test_gfbmadd(self):
 567         # AES's finite field reducing polynomial
 568         red_poly = self.init_aes_red_poly()
 569         a_width = 5
 570         b_width = 4
 571         c_width = 4
 572         for av in range(2 ** a_width):
 573             a = GFB(GF2Poly(unpack_poly(av)), red_poly)
 574             for bv in range(2 ** b_width):
 575                 b = GFB(GF2Poly(unpack_poly(bv)), red_poly)
 576                 for cv in range(2 ** c_width):
 577                     c = GFB(GF2Poly(unpack_poly(cv)), red_poly)
 578                     expected = a * b + c
 579                     with self.subTest(a=str(a), av=av,
 580                                       b=str(b), bv=bv,
 581                                       c=str(c), cv=cv,
 582                                       expected=str(expected)):
 583                         result = gfbmadd(av, bv, cv)
 584                         expectedv = pack_poly(expected.value.coefficients)
 585                         self.assertEqual(result, expectedv)
 586
 587     def test_gfbinv(self):
 588         # AES's finite field reducing polynomial
 589         red_poly = self.init_aes_red_poly()
 590         width = 8
 591         for av in range(2 ** width):
 592             a = GFB(GF2Poly(unpack_poly(av)), red_poly)
 593             expected = a ** -1 if av != 0 else GFB(GF2Poly(), red_poly)
 594             with self.subTest(a=str(a), av=av, expected=str(expected)):
 595                 result = gfbinv(av)
 596                 expectedv = pack_poly(expected.value.coefficients)
 597                 self.assertEqual(result, expectedv)
 598
 599
 600 class TestGFPInstructions(unittest.TestCase):
 601     def test_gfpadd(self):
 602         for prime in PRIMES:
 603             for av in range(prime):
 604                 for bv in range(prime):
 605                     a = GFP(av, prime)
 606                     b = GFP(bv, prime)
 607                     expected = a + b
 608                     with self.subTest(a=str(a), b=str(b),
 609                                       expected=str(expected)):
 610                         ST.reinit(GFPRIME=prime)
 611                         v = gfpadd(av, bv)
 612                         self.assertEqual(v, expected.value)
 613
 614     def test_gfpsub(self):
 615         for prime in PRIMES:
 616             for av in range(prime):
 617                 for bv in range(prime):
 618                     a = GFP(av, prime)
 619                     b = GFP(bv, prime)
 620                     expected = a - b
 621                     with self.subTest(a=str(a), b=str(b),
 622                                       expected=str(expected)):
 623                         ST.reinit(GFPRIME=prime)
 624                         v = gfpsub(av, bv)
 625                         self.assertEqual(v, expected.value)
 626
 627     def test_gfpmul(self):
 628         for prime in PRIMES:
 629             for av in range(prime):
 630                 for bv in range(prime):
 631                     a = GFP(av, prime)
 632                     b = GFP(bv, prime)
 633                     expected = a * b
 634                     with self.subTest(a=str(a), b=str(b),
 635                                       expected=str(expected)):
 636                         ST.reinit(GFPRIME=prime)
 637                         v = gfpmul(av, bv)
 638                         self.assertEqual(v, expected.value)
 639
 640     def test_gfpinv(self):
 641         for prime in PRIMES:
 642             for av in range(prime):
 643                 a = GFP(av, prime)
 644                 if av == 0:
 645                     # TODO: determine what's expected for division by zero
 646                     continue
 647                 else:
 648                     expected = a ** -1
 649                 with self.subTest(a=str(a), expected=str(expected)):
 650                     ST.reinit(GFPRIME=prime)
 651                     v = gfpinv(av)
 652                     self.assertEqual(v, expected.value)
 653
 654     def test_gfpmadd(self):
 655         for prime in PRIMES:
 656             for av in range(prime):
 657                 for bv in range(prime):
 658                     for cv in range(prime):
 659                         a = GFP(av, prime)
 660                         b = GFP(bv, prime)
 661                         c = GFP(cv, prime)
 662                         expected = a * b + c
 663                         with self.subTest(a=str(a), b=str(b), c=str(c),
 664                                           expected=str(expected)):
 665                             ST.reinit(GFPRIME=prime)
 666                             v = gfpmadd(av, bv, cv)
 667                             self.assertEqual(v, expected.value)
 668
 669     def test_gfpmsub(self):
 670         for prime in PRIMES:
 671             for av in range(prime):
 672                 for bv in range(prime):
 673                     for cv in range(prime):
 674                         a = GFP(av, prime)
 675                         b = GFP(bv, prime)
 676                         c = GFP(cv, prime)
 677                         expected = a * b - c
 678                         with self.subTest(a=str(a), b=str(b), c=str(c),
 679                                           expected=str(expected)):
 680                             ST.reinit(GFPRIME=prime)
 681                             v = gfpmsub(av, bv, cv)
 682                             self.assertEqual(v, expected.value)
 683
 684     def test_gfpmsubr(self):
 685         for prime in PRIMES:
 686             for av in range(prime):
 687                 for bv in range(prime):
 688                     for cv in range(prime):
 689                         a = GFP(av, prime)
 690                         b = GFP(bv, prime)
 691                         c = GFP(cv, prime)
 692                         expected = c - a * b
 693                         with self.subTest(a=str(a), b=str(b), c=str(c),
 694                                           expected=str(expected)):
 695                             ST.reinit(GFPRIME=prime)
 696                             v = gfpmsubr(av, bv, cv)
 697                             self.assertEqual(v, expected.value)
 698
 699
 700 if __name__ == "__main__":
 701     unittest.main()