Add m-esr52 at 52.6.0

1 files changed, 958 insertions, 0 deletions

diff --git a/security/nss/lib/freebl/ecl/ecl_gf.c b/security/nss/lib/freebl/ecl/ecl_gf.c
new file mode 100644
index 000000000..81b007705
--- /dev/null
+++ b/security/nss/lib/freebl/ecl/ecl_gf.c
@@ -0,0 +1,958 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mpi.h"
+#include "mp_gf2m.h"
+#include "ecl-priv.h"
+#include "mpi-priv.h"
+#include <stdlib.h>
+
+/* Allocate memory for a new GFMethod object. */
+GFMethod *
+GFMethod_new()
+{
+    mp_err res = MP_OKAY;
+    GFMethod *meth;
+    meth = (GFMethod *)malloc(sizeof(GFMethod));
+    if (meth == NULL)
+        return NULL;
+    meth->constructed = MP_YES;
+    MP_DIGITS(&meth->irr) = 0;
+    meth->extra_free = NULL;
+    MP_CHECKOK(mp_init(&meth->irr));
+
+CLEANUP:
+    if (res != MP_OKAY) {
+        GFMethod_free(meth);
+        return NULL;
+    }
+    return meth;
+}
+
+/* Construct a generic GFMethod for arithmetic over prime fields with
+ * irreducible irr. */
+GFMethod *
+GFMethod_consGFp(const mp_int *irr)
+{
+    mp_err res = MP_OKAY;
+    GFMethod *meth = NULL;
+
+    meth = GFMethod_new();
+    if (meth == NULL)
+        return NULL;
+
+    MP_CHECKOK(mp_copy(irr, &meth->irr));
+    meth->irr_arr[0] = mpl_significant_bits(irr);
+    meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
+        meth->irr_arr[4] = 0;
+    switch (MP_USED(&meth->irr)) {
+        /* maybe we need 1 and 2 words here as well?*/
+        case 3:
+            meth->field_add = &ec_GFp_add_3;
+            meth->field_sub = &ec_GFp_sub_3;
+            break;
+        case 4:
+            meth->field_add = &ec_GFp_add_4;
+            meth->field_sub = &ec_GFp_sub_4;
+            break;
+        case 5:
+            meth->field_add = &ec_GFp_add_5;
+            meth->field_sub = &ec_GFp_sub_5;
+            break;
+        case 6:
+            meth->field_add = &ec_GFp_add_6;
+            meth->field_sub = &ec_GFp_sub_6;
+            break;
+        default:
+            meth->field_add = &ec_GFp_add;
+            meth->field_sub = &ec_GFp_sub;
+    }
+    meth->field_neg = &ec_GFp_neg;
+    meth->field_mod = &ec_GFp_mod;
+    meth->field_mul = &ec_GFp_mul;
+    meth->field_sqr = &ec_GFp_sqr;
+    meth->field_div = &ec_GFp_div;
+    meth->field_enc = NULL;
+    meth->field_dec = NULL;
+    meth->extra1 = NULL;
+    meth->extra2 = NULL;
+    meth->extra_free = NULL;
+
+CLEANUP:
+    if (res != MP_OKAY) {
+        GFMethod_free(meth);
+        return NULL;
+    }
+    return meth;
+}
+
+/* Free the memory allocated (if any) to a GFMethod object. */
+void
+GFMethod_free(GFMethod *meth)
+{
+    if (meth == NULL)
+        return;
+    if (meth->constructed == MP_NO)
+        return;
+    mp_clear(&meth->irr);
+    if (meth->extra_free != NULL)
+        meth->extra_free(meth);
+    free(meth);
+}
+
+/* Wrapper functions for generic prime field arithmetic. */
+
+/* Add two field elements.  Assumes that 0 <= a, b < meth->irr */
+mp_err
+ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
+           const GFMethod *meth)
+{
+    /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
+    mp_err res;
+
+    if ((res = mp_add(a, b, r)) != MP_OKAY) {
+        return res;
+    }
+    if (mp_cmp(r, &meth->irr) >= 0) {
+        return mp_sub(r, &meth->irr, r);
+    }
+    return res;
+}
+
+/* Negates a field element.  Assumes that 0 <= a < meth->irr */
+mp_err
+ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
+
+    if (mp_cmp_z(a) == 0) {
+        mp_zero(r);
+        return MP_OKAY;
+    }
+    return mp_sub(&meth->irr, a, r);
+}
+
+/* Subtracts two field elements.  Assumes that 0 <= a, b < meth->irr */
+mp_err
+ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
+           const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+
+    /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
+    res = mp_sub(a, b, r);
+    if (res == MP_RANGE) {
+        MP_CHECKOK(mp_sub(b, a, r));
+        if (mp_cmp_z(r) < 0) {
+            MP_CHECKOK(mp_add(r, &meth->irr, r));
+        }
+        MP_CHECKOK(ec_GFp_neg(r, r, meth));
+    }
+    if (mp_cmp_z(r) < 0) {
+        MP_CHECKOK(mp_add(r, &meth->irr, r));
+    }
+CLEANUP:
+    return res;
+}
+/*
+ * Inline adds for small curve lengths.
+ */
+/* 3 words */
+mp_err
+ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit a0 = 0, a1 = 0, a2 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0;
+    mp_digit carry;
+
+    switch (MP_USED(a)) {
+        case 3:
+            a2 = MP_DIGIT(a, 2);
+        case 2:
+            a1 = MP_DIGIT(a, 1);
+        case 1:
+            a0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 3:
+            r2 = MP_DIGIT(b, 2);
+        case 2:
+            r1 = MP_DIGIT(b, 1);
+        case 1:
+            r0 = MP_DIGIT(b, 0);
+    }
+
+#ifndef MPI_AMD64_ADD
+    carry = 0;
+    MP_ADD_CARRY(a0, r0, r0, carry);
+    MP_ADD_CARRY(a1, r1, r1, carry);
+    MP_ADD_CARRY(a2, r2, r2, carry);
+#else
+    __asm__(
+        "xorq   %3,%3           \n\t"
+        "addq   %4,%0           \n\t"
+        "adcq   %5,%1           \n\t"
+        "adcq   %6,%2           \n\t"
+        "adcq   $0,%3           \n\t"
+        : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
+        : "r"(a0), "r"(a1), "r"(a2),
+          "0"(r0), "1"(r1), "2"(r2)
+        : "%cc");
+#endif
+
+    MP_CHECKOK(s_mp_pad(r, 3));
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 3;
+
+    /* Do quick 'subract' if we've gone over
+     * (add the 2's complement of the curve field) */
+    a2 = MP_DIGIT(&meth->irr, 2);
+    if (carry || r2 > a2 ||
+        ((r2 == a2) && mp_cmp(r, &meth->irr) != MP_LT)) {
+        a1 = MP_DIGIT(&meth->irr, 1);
+        a0 = MP_DIGIT(&meth->irr, 0);
+#ifndef MPI_AMD64_ADD
+        carry = 0;
+        MP_SUB_BORROW(r0, a0, r0, carry);
+        MP_SUB_BORROW(r1, a1, r1, carry);
+        MP_SUB_BORROW(r2, a2, r2, carry);
+#else
+        __asm__(
+            "subq   %3,%0           \n\t"
+            "sbbq   %4,%1           \n\t"
+            "sbbq   %5,%2           \n\t"
+            : "=r"(r0), "=r"(r1), "=r"(r2)
+            : "r"(a0), "r"(a1), "r"(a2),
+              "0"(r0), "1"(r1), "2"(r2)
+            : "%cc");
+#endif
+        MP_DIGIT(r, 2) = r2;
+        MP_DIGIT(r, 1) = r1;
+        MP_DIGIT(r, 0) = r0;
+    }
+
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 4 words */
+mp_err
+ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
+    mp_digit carry;
+
+    switch (MP_USED(a)) {
+        case 4:
+            a3 = MP_DIGIT(a, 3);
+        case 3:
+            a2 = MP_DIGIT(a, 2);
+        case 2:
+            a1 = MP_DIGIT(a, 1);
+        case 1:
+            a0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 4:
+            r3 = MP_DIGIT(b, 3);
+        case 3:
+            r2 = MP_DIGIT(b, 2);
+        case 2:
+            r1 = MP_DIGIT(b, 1);
+        case 1:
+            r0 = MP_DIGIT(b, 0);
+    }
+
+#ifndef MPI_AMD64_ADD
+    carry = 0;
+    MP_ADD_CARRY(a0, r0, r0, carry);
+    MP_ADD_CARRY(a1, r1, r1, carry);
+    MP_ADD_CARRY(a2, r2, r2, carry);
+    MP_ADD_CARRY(a3, r3, r3, carry);
+#else
+    __asm__(
+        "xorq   %4,%4           \n\t"
+        "addq   %5,%0           \n\t"
+        "adcq   %6,%1           \n\t"
+        "adcq   %7,%2           \n\t"
+        "adcq   %8,%3           \n\t"
+        "adcq   $0,%4           \n\t"
+        : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
+        : "r"(a0), "r"(a1), "r"(a2), "r"(a3),
+          "0"(r0), "1"(r1), "2"(r2), "3"(r3)
+        : "%cc");
+#endif
+
+    MP_CHECKOK(s_mp_pad(r, 4));
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 4;
+
+    /* Do quick 'subract' if we've gone over
+     * (add the 2's complement of the curve field) */
+    a3 = MP_DIGIT(&meth->irr, 3);
+    if (carry || r3 > a3 ||
+        ((r3 == a3) && mp_cmp(r, &meth->irr) != MP_LT)) {
+        a2 = MP_DIGIT(&meth->irr, 2);
+        a1 = MP_DIGIT(&meth->irr, 1);
+        a0 = MP_DIGIT(&meth->irr, 0);
+#ifndef MPI_AMD64_ADD
+        carry = 0;
+        MP_SUB_BORROW(r0, a0, r0, carry);
+        MP_SUB_BORROW(r1, a1, r1, carry);
+        MP_SUB_BORROW(r2, a2, r2, carry);
+        MP_SUB_BORROW(r3, a3, r3, carry);
+#else
+        __asm__(
+            "subq   %4,%0           \n\t"
+            "sbbq   %5,%1           \n\t"
+            "sbbq   %6,%2           \n\t"
+            "sbbq   %7,%3           \n\t"
+            : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
+            : "r"(a0), "r"(a1), "r"(a2), "r"(a3),
+              "0"(r0), "1"(r1), "2"(r2), "3"(r3)
+            : "%cc");
+#endif
+        MP_DIGIT(r, 3) = r3;
+        MP_DIGIT(r, 2) = r2;
+        MP_DIGIT(r, 1) = r1;
+        MP_DIGIT(r, 0) = r0;
+    }
+
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 5 words */
+mp_err
+ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
+    mp_digit carry;
+
+    switch (MP_USED(a)) {
+        case 5:
+            a4 = MP_DIGIT(a, 4);
+        case 4:
+            a3 = MP_DIGIT(a, 3);
+        case 3:
+            a2 = MP_DIGIT(a, 2);
+        case 2:
+            a1 = MP_DIGIT(a, 1);
+        case 1:
+            a0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 5:
+            r4 = MP_DIGIT(b, 4);
+        case 4:
+            r3 = MP_DIGIT(b, 3);
+        case 3:
+            r2 = MP_DIGIT(b, 2);
+        case 2:
+            r1 = MP_DIGIT(b, 1);
+        case 1:
+            r0 = MP_DIGIT(b, 0);
+    }
+
+    carry = 0;
+    MP_ADD_CARRY(a0, r0, r0, carry);
+    MP_ADD_CARRY(a1, r1, r1, carry);
+    MP_ADD_CARRY(a2, r2, r2, carry);
+    MP_ADD_CARRY(a3, r3, r3, carry);
+    MP_ADD_CARRY(a4, r4, r4, carry);
+
+    MP_CHECKOK(s_mp_pad(r, 5));
+    MP_DIGIT(r, 4) = r4;
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 5;
+
+    /* Do quick 'subract' if we've gone over
+     * (add the 2's complement of the curve field) */
+    a4 = MP_DIGIT(&meth->irr, 4);
+    if (carry || r4 > a4 ||
+        ((r4 == a4) && mp_cmp(r, &meth->irr) != MP_LT)) {
+        a3 = MP_DIGIT(&meth->irr, 3);
+        a2 = MP_DIGIT(&meth->irr, 2);
+        a1 = MP_DIGIT(&meth->irr, 1);
+        a0 = MP_DIGIT(&meth->irr, 0);
+        carry = 0;
+        MP_SUB_BORROW(r0, a0, r0, carry);
+        MP_SUB_BORROW(r1, a1, r1, carry);
+        MP_SUB_BORROW(r2, a2, r2, carry);
+        MP_SUB_BORROW(r3, a3, r3, carry);
+        MP_SUB_BORROW(r4, a4, r4, carry);
+        MP_DIGIT(r, 4) = r4;
+        MP_DIGIT(r, 3) = r3;
+        MP_DIGIT(r, 2) = r2;
+        MP_DIGIT(r, 1) = r1;
+        MP_DIGIT(r, 0) = r0;
+    }
+
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 6 words */
+mp_err
+ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
+    mp_digit carry;
+
+    switch (MP_USED(a)) {
+        case 6:
+            a5 = MP_DIGIT(a, 5);
+        case 5:
+            a4 = MP_DIGIT(a, 4);
+        case 4:
+            a3 = MP_DIGIT(a, 3);
+        case 3:
+            a2 = MP_DIGIT(a, 2);
+        case 2:
+            a1 = MP_DIGIT(a, 1);
+        case 1:
+            a0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 6:
+            r5 = MP_DIGIT(b, 5);
+        case 5:
+            r4 = MP_DIGIT(b, 4);
+        case 4:
+            r3 = MP_DIGIT(b, 3);
+        case 3:
+            r2 = MP_DIGIT(b, 2);
+        case 2:
+            r1 = MP_DIGIT(b, 1);
+        case 1:
+            r0 = MP_DIGIT(b, 0);
+    }
+
+    carry = 0;
+    MP_ADD_CARRY(a0, r0, r0, carry);
+    MP_ADD_CARRY(a1, r1, r1, carry);
+    MP_ADD_CARRY(a2, r2, r2, carry);
+    MP_ADD_CARRY(a3, r3, r3, carry);
+    MP_ADD_CARRY(a4, r4, r4, carry);
+    MP_ADD_CARRY(a5, r5, r5, carry);
+
+    MP_CHECKOK(s_mp_pad(r, 6));
+    MP_DIGIT(r, 5) = r5;
+    MP_DIGIT(r, 4) = r4;
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 6;
+
+    /* Do quick 'subract' if we've gone over
+     * (add the 2's complement of the curve field) */
+    a5 = MP_DIGIT(&meth->irr, 5);
+    if (carry || r5 > a5 ||
+        ((r5 == a5) && mp_cmp(r, &meth->irr) != MP_LT)) {
+        a4 = MP_DIGIT(&meth->irr, 4);
+        a3 = MP_DIGIT(&meth->irr, 3);
+        a2 = MP_DIGIT(&meth->irr, 2);
+        a1 = MP_DIGIT(&meth->irr, 1);
+        a0 = MP_DIGIT(&meth->irr, 0);
+        carry = 0;
+        MP_SUB_BORROW(r0, a0, r0, carry);
+        MP_SUB_BORROW(r1, a1, r1, carry);
+        MP_SUB_BORROW(r2, a2, r2, carry);
+        MP_SUB_BORROW(r3, a3, r3, carry);
+        MP_SUB_BORROW(r4, a4, r4, carry);
+        MP_SUB_BORROW(r5, a5, r5, carry);
+        MP_DIGIT(r, 5) = r5;
+        MP_DIGIT(r, 4) = r4;
+        MP_DIGIT(r, 3) = r3;
+        MP_DIGIT(r, 2) = r2;
+        MP_DIGIT(r, 1) = r1;
+        MP_DIGIT(r, 0) = r0;
+    }
+
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/*
+ * The following subraction functions do in-line subractions based
+ * on our curve size.
+ *
+ * ... 3 words
+ */
+mp_err
+ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit b0 = 0, b1 = 0, b2 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0;
+    mp_digit borrow;
+
+    switch (MP_USED(a)) {
+        case 3:
+            r2 = MP_DIGIT(a, 2);
+        case 2:
+            r1 = MP_DIGIT(a, 1);
+        case 1:
+            r0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 3:
+            b2 = MP_DIGIT(b, 2);
+        case 2:
+            b1 = MP_DIGIT(b, 1);
+        case 1:
+            b0 = MP_DIGIT(b, 0);
+    }
+
+#ifndef MPI_AMD64_ADD
+    borrow = 0;
+    MP_SUB_BORROW(r0, b0, r0, borrow);
+    MP_SUB_BORROW(r1, b1, r1, borrow);
+    MP_SUB_BORROW(r2, b2, r2, borrow);
+#else
+    __asm__(
+        "xorq   %3,%3           \n\t"
+        "subq   %4,%0           \n\t"
+        "sbbq   %5,%1           \n\t"
+        "sbbq   %6,%2           \n\t"
+        "adcq   $0,%3           \n\t"
+        : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow)
+        : "r"(b0), "r"(b1), "r"(b2),
+          "0"(r0), "1"(r1), "2"(r2)
+        : "%cc");
+#endif
+
+    /* Do quick 'add' if we've gone under 0
+     * (subtract the 2's complement of the curve field) */
+    if (borrow) {
+        b2 = MP_DIGIT(&meth->irr, 2);
+        b1 = MP_DIGIT(&meth->irr, 1);
+        b0 = MP_DIGIT(&meth->irr, 0);
+#ifndef MPI_AMD64_ADD
+        borrow = 0;
+        MP_ADD_CARRY(b0, r0, r0, borrow);
+        MP_ADD_CARRY(b1, r1, r1, borrow);
+        MP_ADD_CARRY(b2, r2, r2, borrow);
+#else
+        __asm__(
+            "addq   %3,%0           \n\t"
+            "adcq   %4,%1           \n\t"
+            "adcq   %5,%2           \n\t"
+            : "=r"(r0), "=r"(r1), "=r"(r2)
+            : "r"(b0), "r"(b1), "r"(b2),
+              "0"(r0), "1"(r1), "2"(r2)
+            : "%cc");
+#endif
+    }
+
+#ifdef MPI_AMD64_ADD
+    /* compiler fakeout? */
+    if ((r2 == b0) && (r1 == b0) && (r0 == b0)) {
+        MP_CHECKOK(s_mp_pad(r, 4));
+    }
+#endif
+    MP_CHECKOK(s_mp_pad(r, 3));
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 3;
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 4 words */
+mp_err
+ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
+    mp_digit borrow;
+
+    switch (MP_USED(a)) {
+        case 4:
+            r3 = MP_DIGIT(a, 3);
+        case 3:
+            r2 = MP_DIGIT(a, 2);
+        case 2:
+            r1 = MP_DIGIT(a, 1);
+        case 1:
+            r0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 4:
+            b3 = MP_DIGIT(b, 3);
+        case 3:
+            b2 = MP_DIGIT(b, 2);
+        case 2:
+            b1 = MP_DIGIT(b, 1);
+        case 1:
+            b0 = MP_DIGIT(b, 0);
+    }
+
+#ifndef MPI_AMD64_ADD
+    borrow = 0;
+    MP_SUB_BORROW(r0, b0, r0, borrow);
+    MP_SUB_BORROW(r1, b1, r1, borrow);
+    MP_SUB_BORROW(r2, b2, r2, borrow);
+    MP_SUB_BORROW(r3, b3, r3, borrow);
+#else
+    __asm__(
+        "xorq   %4,%4           \n\t"
+        "subq   %5,%0           \n\t"
+        "sbbq   %6,%1           \n\t"
+        "sbbq   %7,%2           \n\t"
+        "sbbq   %8,%3           \n\t"
+        "adcq   $0,%4           \n\t"
+        : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(borrow)
+        : "r"(b0), "r"(b1), "r"(b2), "r"(b3),
+          "0"(r0), "1"(r1), "2"(r2), "3"(r3)
+        : "%cc");
+#endif
+
+    /* Do quick 'add' if we've gone under 0
+     * (subtract the 2's complement of the curve field) */
+    if (borrow) {
+        b3 = MP_DIGIT(&meth->irr, 3);
+        b2 = MP_DIGIT(&meth->irr, 2);
+        b1 = MP_DIGIT(&meth->irr, 1);
+        b0 = MP_DIGIT(&meth->irr, 0);
+#ifndef MPI_AMD64_ADD
+        borrow = 0;
+        MP_ADD_CARRY(b0, r0, r0, borrow);
+        MP_ADD_CARRY(b1, r1, r1, borrow);
+        MP_ADD_CARRY(b2, r2, r2, borrow);
+        MP_ADD_CARRY(b3, r3, r3, borrow);
+#else
+        __asm__(
+            "addq   %4,%0           \n\t"
+            "adcq   %5,%1           \n\t"
+            "adcq   %6,%2           \n\t"
+            "adcq   %7,%3           \n\t"
+            : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
+            : "r"(b0), "r"(b1), "r"(b2), "r"(b3),
+              "0"(r0), "1"(r1), "2"(r2), "3"(r3)
+            : "%cc");
+#endif
+    }
+#ifdef MPI_AMD64_ADD
+    /* compiler fakeout? */
+    if ((r3 == b0) && (r1 == b0) && (r0 == b0)) {
+        MP_CHECKOK(s_mp_pad(r, 4));
+    }
+#endif
+    MP_CHECKOK(s_mp_pad(r, 4));
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 4;
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 5 words */
+mp_err
+ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
+    mp_digit borrow;
+
+    switch (MP_USED(a)) {
+        case 5:
+            r4 = MP_DIGIT(a, 4);
+        case 4:
+            r3 = MP_DIGIT(a, 3);
+        case 3:
+            r2 = MP_DIGIT(a, 2);
+        case 2:
+            r1 = MP_DIGIT(a, 1);
+        case 1:
+            r0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 5:
+            b4 = MP_DIGIT(b, 4);
+        case 4:
+            b3 = MP_DIGIT(b, 3);
+        case 3:
+            b2 = MP_DIGIT(b, 2);
+        case 2:
+            b1 = MP_DIGIT(b, 1);
+        case 1:
+            b0 = MP_DIGIT(b, 0);
+    }
+
+    borrow = 0;
+    MP_SUB_BORROW(r0, b0, r0, borrow);
+    MP_SUB_BORROW(r1, b1, r1, borrow);
+    MP_SUB_BORROW(r2, b2, r2, borrow);
+    MP_SUB_BORROW(r3, b3, r3, borrow);
+    MP_SUB_BORROW(r4, b4, r4, borrow);
+
+    /* Do quick 'add' if we've gone under 0
+     * (subtract the 2's complement of the curve field) */
+    if (borrow) {
+        b4 = MP_DIGIT(&meth->irr, 4);
+        b3 = MP_DIGIT(&meth->irr, 3);
+        b2 = MP_DIGIT(&meth->irr, 2);
+        b1 = MP_DIGIT(&meth->irr, 1);
+        b0 = MP_DIGIT(&meth->irr, 0);
+        borrow = 0;
+        MP_ADD_CARRY(b0, r0, r0, borrow);
+        MP_ADD_CARRY(b1, r1, r1, borrow);
+        MP_ADD_CARRY(b2, r2, r2, borrow);
+        MP_ADD_CARRY(b3, r3, r3, borrow);
+        MP_ADD_CARRY(b4, r4, r4, borrow);
+    }
+    MP_CHECKOK(s_mp_pad(r, 5));
+    MP_DIGIT(r, 4) = r4;
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 5;
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* 6 words */
+mp_err
+ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
+             const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
+    mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
+    mp_digit borrow;
+
+    switch (MP_USED(a)) {
+        case 6:
+            r5 = MP_DIGIT(a, 5);
+        case 5:
+            r4 = MP_DIGIT(a, 4);
+        case 4:
+            r3 = MP_DIGIT(a, 3);
+        case 3:
+            r2 = MP_DIGIT(a, 2);
+        case 2:
+            r1 = MP_DIGIT(a, 1);
+        case 1:
+            r0 = MP_DIGIT(a, 0);
+    }
+    switch (MP_USED(b)) {
+        case 6:
+            b5 = MP_DIGIT(b, 5);
+        case 5:
+            b4 = MP_DIGIT(b, 4);
+        case 4:
+            b3 = MP_DIGIT(b, 3);
+        case 3:
+            b2 = MP_DIGIT(b, 2);
+        case 2:
+            b1 = MP_DIGIT(b, 1);
+        case 1:
+            b0 = MP_DIGIT(b, 0);
+    }
+
+    borrow = 0;
+    MP_SUB_BORROW(r0, b0, r0, borrow);
+    MP_SUB_BORROW(r1, b1, r1, borrow);
+    MP_SUB_BORROW(r2, b2, r2, borrow);
+    MP_SUB_BORROW(r3, b3, r3, borrow);
+    MP_SUB_BORROW(r4, b4, r4, borrow);
+    MP_SUB_BORROW(r5, b5, r5, borrow);
+
+    /* Do quick 'add' if we've gone under 0
+     * (subtract the 2's complement of the curve field) */
+    if (borrow) {
+        b5 = MP_DIGIT(&meth->irr, 5);
+        b4 = MP_DIGIT(&meth->irr, 4);
+        b3 = MP_DIGIT(&meth->irr, 3);
+        b2 = MP_DIGIT(&meth->irr, 2);
+        b1 = MP_DIGIT(&meth->irr, 1);
+        b0 = MP_DIGIT(&meth->irr, 0);
+        borrow = 0;
+        MP_ADD_CARRY(b0, r0, r0, borrow);
+        MP_ADD_CARRY(b1, r1, r1, borrow);
+        MP_ADD_CARRY(b2, r2, r2, borrow);
+        MP_ADD_CARRY(b3, r3, r3, borrow);
+        MP_ADD_CARRY(b4, r4, r4, borrow);
+        MP_ADD_CARRY(b5, r5, r5, borrow);
+    }
+
+    MP_CHECKOK(s_mp_pad(r, 6));
+    MP_DIGIT(r, 5) = r5;
+    MP_DIGIT(r, 4) = r4;
+    MP_DIGIT(r, 3) = r3;
+    MP_DIGIT(r, 2) = r2;
+    MP_DIGIT(r, 1) = r1;
+    MP_DIGIT(r, 0) = r0;
+    MP_SIGN(r) = MP_ZPOS;
+    MP_USED(r) = 6;
+    s_mp_clamp(r);
+
+CLEANUP:
+    return res;
+}
+
+/* Reduces an integer to a field element. */
+mp_err
+ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    return mp_mod(a, &meth->irr, r);
+}
+
+/* Multiplies two field elements. */
+mp_err
+ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
+           const GFMethod *meth)
+{
+    return mp_mulmod(a, b, &meth->irr, r);
+}
+
+/* Squares a field element. */
+mp_err
+ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    return mp_sqrmod(a, &meth->irr, r);
+}
+
+/* Divides two field elements. If a is NULL, then returns the inverse of
+ * b. */
+mp_err
+ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
+           const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_int t;
+
+    /* If a is NULL, then return the inverse of b, otherwise return a/b. */
+    if (a == NULL) {
+        return mp_invmod(b, &meth->irr, r);
+    } else {
+        /* MPI doesn't support divmod, so we implement it using invmod and
+         * mulmod. */
+        MP_CHECKOK(mp_init(&t));
+        MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
+        MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
+    CLEANUP:
+        mp_clear(&t);
+        return res;
+    }
+}
+
+/* Wrapper functions for generic binary polynomial field arithmetic. */
+
+/* Adds two field elements. */
+mp_err
+ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
+            const GFMethod *meth)
+{
+    return mp_badd(a, b, r);
+}
+
+/* Negates a field element. Note that for binary polynomial fields, the
+ * negation of a field element is the field element itself. */
+mp_err
+ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    if (a == r) {
+        return MP_OKAY;
+    } else {
+        return mp_copy(a, r);
+    }
+}
+
+/* Reduces a binary polynomial to a field element. */
+mp_err
+ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    return mp_bmod(a, meth->irr_arr, r);
+}
+
+/* Multiplies two field elements. */
+mp_err
+ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
+            const GFMethod *meth)
+{
+    return mp_bmulmod(a, b, meth->irr_arr, r);
+}
+
+/* Squares a field element. */
+mp_err
+ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+    return mp_bsqrmod(a, meth->irr_arr, r);
+}
+
+/* Divides two field elements. If a is NULL, then returns the inverse of
+ * b. */
+mp_err
+ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
+            const GFMethod *meth)
+{
+    mp_err res = MP_OKAY;
+    mp_int t;
+
+    /* If a is NULL, then return the inverse of b, otherwise return a/b. */
+    if (a == NULL) {
+        /* The GF(2^m) portion of MPI doesn't support invmod, so we
+         * compute 1/b. */
+        MP_CHECKOK(mp_init(&t));
+        MP_CHECKOK(mp_set_int(&t, 1));
+        MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
+    CLEANUP:
+        mp_clear(&t);
+        return res;
+    } else {
+        return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
+    }
+}