from nmigen_gf.reference.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
    # designed to be dead-easy (and efficient) to implement in hardware
    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

    # initial values`
    u = p
    v = a
    r = 0
    s = 1

    # main loop
    while v > 0:
        # implementations could use count-zeros on
        # both u and r to save cycles
        if u & 1 == 0:
            if r & 1 != 0:
                r += p
            u >>= 1
            r >>= 1
            continue # loop again
        # implementations could use count-zeros on
        # both v and s to save cycles
        if v & 1 == 0:
            if s & 1 != 0:
                s += p
            v >>= 1
            s >>= 1
            continue # loop again
        # both LSB of u and v are 1
        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

    # make sure result r within modulo range 0 <= r <= p
    if r > p:
        r -= p
    if r < 0:
        r += p
    return r