path: root/crypto/bn256/cloudflare/gfp_generic.go

// +build !amd64,!arm64 generic

package bn256

func gfpCarry(a *gfP, head uint64) {
    b := &gfP{}

    var carry uint64
    for i, pi := range p2 {
        ai := a[i]
        bi := ai - pi - carry
        b[i] = bi
        carry = (pi&^ai | (pi|^ai)&bi) >> 63
    }
    carry = carry &^ head

    // If b is negative, then return a.
    // Else return b.
    carry = -carry
    ncarry := ^carry
    for i := 0; i < 4; i++ {
        a[i] = (a[i] & carry) | (b[i] & ncarry)
    }
}

func gfpNeg(c, a *gfP) {
    var carry uint64
    for i, pi := range p2 {
        ai := a[i]
        ci := pi - ai - carry
        c[i] = ci
        carry = (ai&^pi | (ai|^pi)&ci) >> 63
    }
    gfpCarry(c, 0)
}

func gfpAdd(c, a, b *gfP) {
    var carry uint64
    for i, ai := range a {
        bi := b[i]
        ci := ai + bi + carry
        c[i] = ci
        carry = (ai&bi | (ai|bi)&^ci) >> 63
    }
    gfpCarry(c, carry)
}

func gfpSub(c, a, b *gfP) {
    t := &gfP{}

    var carry uint64
    for i, pi := range p2 {
        bi := b[i]
        ti := pi - bi - carry
        t[i] = ti
        carry = (bi&^pi | (bi|^pi)&ti) >> 63
    }

    carry = 0
    for i, ai := range a {
        ti := t[i]
        ci := ai + ti + carry
        c[i] = ci
        carry = (ai&ti | (ai|ti)&^ci) >> 63
    }
    gfpCarry(c, carry)
}

func mul(a, b [4]uint64) [8]uint64 {
    const (
        mask16 uint64 = 0x0000ffff
        mask32 uint64 = 0xffffffff
    )

    var buff [32]uint64
    for i, ai := range a {
        a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48

        for j, bj := range b {
            b0, b2 := bj&mask32, bj>>32

            off := 4 * (i + j)
            buff[off+0] += a0 * b0
            buff[off+1] += a1 * b0
            buff[off+2] += a2*b0 + a0*b2
            buff[off+3] += a3*b0 + a1*b2
            buff[off+4] += a2 * b2
            buff[off+5] += a3 * b2
        }
    }

    for i := uint(1); i < 4; i++ {
        shift := 16 * i

        var head, carry uint64
        for j := uint(0); j < 8; j++ {
            block := 4 * j

            xi := buff[block]
            yi := (buff[block+i] << shift) + head
            zi := xi + yi + carry
            buff[block] = zi
            carry = (xi&yi | (xi|yi)&^zi) >> 63

            head = buff[block+i] >> (64 - shift)
        }
    }

    return [8]uint64{buff[0], buff[4], buff[8], buff[12], buff[16], buff[20], buff[24], buff[28]}
}

func halfMul(a, b [4]uint64) [4]uint64 {
    const (
        mask16 uint64 = 0x0000ffff
        mask32 uint64 = 0xffffffff
    )

    var buff [18]uint64
    for i, ai := range a {
        a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48

        for j, bj := range b {
            if i+j > 3 {
                break
            }
            b0, b2 := bj&mask32, bj>>32

            off := 4 * (i + j)
            buff[off+0] += a0 * b0
            buff[off+1] += a1 * b0
            buff[off+2] += a2*b0 + a0*b2
            buff[off+3] += a3*b0 + a1*b2
            buff[off+4] += a2 * b2
            buff[off+5] += a3 * b2
        }
    }

    for i := uint(1); i < 4; i++ {
        shift := 16 * i

        var head, carry uint64
        for j := uint(0); j < 4; j++ {
            block := 4 * j

            xi := buff[block]
            yi := (buff[block+i] << shift) + head
            zi := xi + yi + carry
            buff[block] = zi
            carry = (xi&yi | (xi|yi)&^zi) >> 63

            head = buff[block+i] >> (64 - shift)
        }
    }

    return [4]uint64{buff[0], buff[4], buff[8], buff[12]}
}

func gfpMul(c, a, b *gfP) {
    T := mul(*a, *b)
    m := halfMul([4]uint64{T[0], T[1], T[2], T[3]}, np)
    t := mul([4]uint64{m[0], m[1], m[2], m[3]}, p2)

    var carry uint64
    for i, Ti := range T {
        ti := t[i]
        zi := Ti + ti + carry
        T[i] = zi
        carry = (Ti&ti | (Ti|ti)&^zi) >> 63
    }

    *c = gfP{T[4], T[5], T[6], T[7]}
    gfpCarry(c, carry)
}