openpower/sv/gf2.py

   1 # a mish-mash of various GF(2^m) functions from different sources
   2 # on the internet which help demonstrate arithmetic in GF(2^m)
   3 # these are intended to be implemented in hardware, so the basic
   4 # primitives need to be *real* basic: XOR, shift, AND, OR, etc.
   5 #
   6 # development discussion and links at:
   7 # https://bugs.libre-soc.org/show_bug.cgi?id=782
   8
   9 from functools import reduce
  10
  11 # https://stackoverflow.com/questions/45442396/
  12
  13
  14 def gf_degree(a):
  15     res = 0
  16     a >>= 1
  17     while (a != 0):
  18         a >>= 1
  19         res += 1
  20     return res
  21
  22
  23 # useful constants used throughout this module
  24 degree = mask1 = mask2 = polyred = None
  25
  26
  27 def getGF2():
  28     """reconstruct the polynomial coefficients of g(x)
  29     """
  30     return polyred | mask1
  31
  32
  33 # original at https://jhafranco.com/tag/binary-finite-field/
  34 def setGF2(irPoly):
  35     """Define parameters of binary finite field GF(2^m)/g(x)
  36        - irPoly: coefficients of irreducible polynomial g(x)
  37     """
  38     # degree: extension degree of binary field
  39     global degree, mask1, mask2, polyred
  40     degree = gf_degree(irPoly)
  41
  42     def i2P(sInt):
  43         """Convert an integer into a polynomial"""
  44         return [(sInt >> i) & 1
  45                 for i in reversed(range(sInt.bit_length()))]
  46
  47     mask1 = mask2 = 1 << degree
  48     mask2 -= 1
  49     polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])
  50
  51
  52 # original at https://jhafranco.com/tag/binary-finite-field/
  53 def multGF2(p1, p2):
  54     """Multiply two polynomials in GF(2^m)/g(x)"""
  55     p = 0
  56     while p2:
  57         if p2 & 1:
  58             p ^= p1
  59         p1 <<= 1
  60         if p1 & mask1:
  61             p1 ^= polyred
  62         p2 >>= 1
  63     return p & mask2
  64
  65
  66 # https://github.com/jpahullo/python-multiprocessing/
  67 # py_ecc/ffield.py
  68 def divmodGF2(f, v):
  69     fDegree, vDegree = gf_degree(f), gf_degree(v)
  70     res, rem = 0, f
  71     i = fDegree
  72     mask = 1 << i
  73     while (i >= vDegree):
  74         if (mask & rem):
  75             res ^= (1 << (i - vDegree))
  76             rem ^= (v << (i - vDegree))
  77         i -= 1
  78         mask >>= 1
  79     return (res, rem)
  80
  81
  82 # https://en.m.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
  83 def xgcd(a, b):
  84     """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
  85     x0, x1, y0, y1 = 0, 1, 1, 0
  86     while a != 0:
  87         (q, a), b = divmodGF2(b, a), a
  88         y0, y1 = y1, y0 ^ multGF2(q, y1)
  89         x0, x1 = x1, x0 ^ multGF2(q, x1)
  90     return b, x0, y0
  91
  92
  93 # https://bugs.libre-soc.org/show_bug.cgi?id=782#c33
  94 # https://ftp.libre-soc.org/ARITH18_Kobayashi.pdf
  95 def gf_invert(a):
  96
  97     s = getGF2()  # get the full polynomial (including the MSB)
  98     r = a
  99     v = 0
 100     u = 1
 101     j = 0
 102
 103     for i in range(1, 2*degree+1):
 104         # could use count-trailing-1s here to skip ahead
 105         if r & mask1:          # test MSB of r
 106             if s & mask1:      # test MSB of s
 107                 s ^= r
 108                 v ^= u
 109             s <<= 1            # shift left 1
 110             if j == 0:
 111                 r, s = s, r    # swap r,s
 112                 u, v = v << 1, u  # shift v and swap
 113                 j = 1
 114             else:
 115                 u >>= 1        # right shift left
 116                 j -= 1
 117         else:
 118             r <<= 1            # shift left 1
 119             u <<= 1            # shift left 1
 120             j += 1
 121
 122     return u
 123
 124
 125 if __name__ == "__main__":
 126
 127     # Define binary field GF(2^3)/x^3 + x + 1
 128     setGF2(0b1011)  # degree 3
 129
 130     # Evaluate the product (x^2 + x + 1)(x^2 + 1)
 131     x = multGF2(0b111, 0b101)
 132     print("%02x" % x)
 133
 134     # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
 135     # (used in Rijndael)
 136     # note that polyred has the MSB stripped!
 137     setGF2(0b100011011)  # degree 8
 138
 139     # Evaluate the product (x^7 + x^2)(x^7 + x + 1)
 140     x = 0b10000100
 141     y = 0b10000011
 142     z = multGF2(x, y)
 143     print("%02x * %02x = %02x" % (x, y, z))
 144
 145     # divide z by y into result/remainder
 146     res, rem = divmodGF2(z, y)
 147     print("%02x / %02x = (%02x, %02x)" % (z, y, res, rem))
 148
 149     # reconstruct x by multiplying divided result by y and adding the remainder
 150     x1 = multGF2(res, y)
 151     print("%02x == %02x" % (z, x1 ^ rem))  # XOR is "add" in GF2
 152
 153     # demo output of xgcd
 154     print(xgcd(x, y))
 155
 156     # for i in range(1, 256):
 157     #   print (i, gf_invert(i))
 158
 159     # show how inversion-and-multiply works.  answer here should be "x":
 160     # z = x * y, therefore z * (1/y) should equal "x"
 161     y1 = gf_invert(y)
 162     z1 = multGF2(z, y1)
 163     print(hex(polyred), hex(y1), hex(x), "==", hex(z1))