gf_reference/gfpinv.py

   1 from nmigen_gf.reference.state import ST
   2
   3
   4 def gfpinv(a):
   5     # based on Algorithm ExtEucdInv from:
   6     # https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf
   7     # designed to be dead-easy (and efficient) to implement in hardware
   8     p = ST.GFPRIME
   9     assert p >= 2, "GFPRIME isn't a prime"
  10     assert a != 0, "TODO: decide what happens for division by zero"
  11     assert isinstance(a, int) and 0 < a < p, "a out of range"
  12     if p == 2:
  13         return 1  # the only value possible
  14
  15     # initial values`
  16     u = p
  17     v = a
  18     r = 0
  19     s = 1
  20
  21     # main loop
  22     while v > 0:
  23         # implementations could use count-zeros on
  24         # both u and r to save cycles
  25         if u & 1 == 0:
  26             if r & 1 != 0:
  27                 r += p
  28             u >>= 1
  29             r >>= 1
  30             continue # loop again
  31         # implementations could use count-zeros on
  32         # both v and s to save cycles
  33         if v & 1 == 0:
  34             if s & 1 != 0:
  35                 s += p
  36             v >>= 1
  37             s >>= 1
  38             continue # loop again
  39         # both LSB of u and v are 1
  40         x = u - v
  41         if x > 0:
  42             u = x
  43             r -= s
  44             if r < 0:
  45                 r += p
  46         else:
  47             v = -x
  48             s -= r
  49             if s < 0:
  50                 s += p
  51
  52     # make sure result r within modulo range 0 <= r <= p
  53     if r > p:
  54         r -= p
  55     if r < 0:
  56         r += p
  57     return r