[secp256k1.git] / src / field_5x52_impl.h

/**********************************************************************
 * Copyright (c) 2013, 2014 Pieter Wuille                             *
 * Distributed under the MIT software license, see the accompanying   *
 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
 **********************************************************************/

#ifndef _SECP256K1_FIELD_REPR_IMPL_H_
#define _SECP256K1_FIELD_REPR_IMPL_H_

#if defined HAVE_CONFIG_H
#include "libsecp256k1-config.h"
#endif

#include <string.h>
#include "util.h"
#include "num.h"
#include "field.h"

#if defined(USE_ASM_X86_64)
#include "field_5x52_asm_impl.h"
#else
#include "field_5x52_int128_impl.h"
#endif

/** Implements arithmetic modulo FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F,
 *  represented as 5 uint64_t's in base 2^52. The values are allowed to contain >52 each. In particular,
 *  each FieldElem has a 'magnitude' associated with it. Internally, a magnitude M means each element
 *  is at most M*(2^53-1), except the most significant one, which is limited to M*(2^49-1). All operations
 *  accept any input with magnitude at most M, and have different rules for propagating magnitude to their
 *  output.
 */

#ifdef VERIFY
static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
    const uint64_t *d = a->n;
    int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
   /* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
    r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
    r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
    r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
    r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
    r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
    r &= (a->magnitude >= 0);
    r &= (a->magnitude <= 2048);
    if (a->normalized) {
        r &= (a->magnitude <= 1);
        if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
            r &= (d[0] < 0xFFFFEFFFFFC2FULL);
        }
    }
    VERIFY_CHECK(r == 1);
}
#else
static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
    (void)a;
}
#endif

static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
    uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];

    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
    uint64_t m;
    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;

    /* The first pass ensures the magnitude is 1, ... */
    t0 += x * 0x1000003D1ULL;
    t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;

    /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
    VERIFY_CHECK(t4 >> 49 == 0);

    /* At most a single final reduction is needed; check if the value is >= the field characteristic */
    x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
        & (t0 >= 0xFFFFEFFFFFC2FULL));

    /* Apply the final reduction (for constant-time behaviour, we do it always) */
    t0 += x * 0x1000003D1ULL;
    t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;

    /* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
    VERIFY_CHECK(t4 >> 48 == x);

    /* Mask off the possible multiple of 2^256 from the final reduction */
    t4 &= 0x0FFFFFFFFFFFFULL;

    r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;

#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 1;
    secp256k1_fe_verify(r);
#endif
}

static void secp256k1_fe_normalize_weak(secp256k1_fe_t *r) {
    uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];

    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;

    /* The first pass ensures the magnitude is 1, ... */
    t0 += x * 0x1000003D1ULL;
    t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;

    /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
    VERIFY_CHECK(t4 >> 49 == 0);

    r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;

#ifdef VERIFY
    r->magnitude = 1;
    secp256k1_fe_verify(r);
#endif
}

static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
    uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];

    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
    uint64_t m;
    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;

    /* The first pass ensures the magnitude is 1, ... */
    t0 += x * 0x1000003D1ULL;
    t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;

    /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
    VERIFY_CHECK(t4 >> 49 == 0);

    /* At most a single final reduction is needed; check if the value is >= the field characteristic */
    x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
        & (t0 >= 0xFFFFEFFFFFC2FULL));

    if (x) {
        t0 += 0x1000003D1ULL;
        t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
        t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
        t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
        t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;

        /* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
        VERIFY_CHECK(t4 >> 48 == x);

        /* Mask off the possible multiple of 2^256 from the final reduction */
        t4 &= 0x0FFFFFFFFFFFFULL;
    }

    r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;

#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 1;
    secp256k1_fe_verify(r);
#endif
}

static int secp256k1_fe_normalizes_to_zero(secp256k1_fe_t *r) {
    uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];

    /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
    uint64_t z0, z1;

    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;

    /* The first pass ensures the magnitude is 1, ... */
    t0 += x * 0x1000003D1ULL;
    t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0  = t0; z1  = t0 ^ 0x1000003D0ULL;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
                                                z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;

    /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
    VERIFY_CHECK(t4 >> 49 == 0);

    return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
}

static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe_t *r) {
    uint64_t t0, t1, t2, t3, t4;
    uint64_t z0, z1;
    uint64_t x;

    t0 = r->n[0];
    t4 = r->n[4];

    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
    x = t4 >> 48;

    /* The first pass ensures the magnitude is 1, ... */
    t0 += x * 0x1000003D1ULL;

    /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
    z0 = t0 & 0xFFFFFFFFFFFFFULL;
    z1 = z0 ^ 0x1000003D0ULL;

    /* Fast return path should catch the majority of cases */
    if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL)) {
        return 0;
    }

    t1 = r->n[1];
    t2 = r->n[2];
    t3 = r->n[3];

    t4 &= 0x0FFFFFFFFFFFFULL;

    t1 += (t0 >> 52); t0  = z0;
    t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
    t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
    t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
                                                z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;

    /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
    VERIFY_CHECK(t4 >> 49 == 0);

    return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
}

SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
    r->n[0] = a;
    r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 1;
    secp256k1_fe_verify(r);
#endif
}

SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe_t *a) {
    const uint64_t *t = a->n;
#ifdef VERIFY
    VERIFY_CHECK(a->normalized);
    secp256k1_fe_verify(a);
#endif
    return (t[0] | t[1] | t[2] | t[3] | t[4]) == 0;
}

SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe_t *a) {
#ifdef VERIFY
    VERIFY_CHECK(a->normalized);
    secp256k1_fe_verify(a);
#endif
    return a->n[0] & 1;
}

SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
    int i;
#ifdef VERIFY
    a->magnitude = 0;
    a->normalized = 1;
#endif
    for (i=0; i<5; i++) {
        a->n[i] = 0;
    }
}

static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
    int i;
#ifdef VERIFY
    VERIFY_CHECK(a->normalized);
    VERIFY_CHECK(b->normalized);
    secp256k1_fe_verify(a);
    secp256k1_fe_verify(b);
#endif
    for (i = 4; i >= 0; i--) {
        if (a->n[i] > b->n[i]) {
            return 1;
        }
        if (a->n[i] < b->n[i]) {
            return -1;
        }
    }
    return 0;
}

static int secp256k1_fe_set_b32(secp256k1_fe_t *r, const unsigned char *a) {
    int i;
    r->n[0] = r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
    for (i=0; i<32; i++) {
        int j;
        for (j=0; j<2; j++) {
            int limb = (8*i+4*j)/52;
            int shift = (8*i+4*j)%52;
            r->n[limb] |= (uint64_t)((a[31-i] >> (4*j)) & 0xF) << shift;
        }
    }
    if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
        return 0;
    }
#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 1;
    secp256k1_fe_verify(r);
#endif
    return 1;
}

/** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe_t *a) {
    int i;
#ifdef VERIFY
    VERIFY_CHECK(a->normalized);
    secp256k1_fe_verify(a);
#endif
    for (i=0; i<32; i++) {
        int j;
        int c = 0;
        for (j=0; j<2; j++) {
            int limb = (8*i+4*j)/52;
            int shift = (8*i+4*j)%52;
            c |= ((a->n[limb] >> shift) & 0xF) << (4 * j);
        }
        r[31-i] = c;
    }
}

SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe_t *r, const secp256k1_fe_t *a, int m) {
#ifdef VERIFY
    VERIFY_CHECK(a->magnitude <= m);
    secp256k1_fe_verify(a);
#endif
    r->n[0] = 0xFFFFEFFFFFC2FULL * 2 * (m + 1) - a->n[0];
    r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[1];
    r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[2];
    r->n[3] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[3];
    r->n[4] = 0x0FFFFFFFFFFFFULL * 2 * (m + 1) - a->n[4];
#ifdef VERIFY
    r->magnitude = m + 1;
    r->normalized = 0;
    secp256k1_fe_verify(r);
#endif
}

SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe_t *r, int a) {
    r->n[0] *= a;
    r->n[1] *= a;
    r->n[2] *= a;
    r->n[3] *= a;
    r->n[4] *= a;
#ifdef VERIFY
    r->magnitude *= a;
    r->normalized = 0;
    secp256k1_fe_verify(r);
#endif
}

SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
#ifdef VERIFY
    secp256k1_fe_verify(a);
#endif
    r->n[0] += a->n[0];
    r->n[1] += a->n[1];
    r->n[2] += a->n[2];
    r->n[3] += a->n[3];
    r->n[4] += a->n[4];
#ifdef VERIFY
    r->magnitude += a->magnitude;
    r->normalized = 0;
    secp256k1_fe_verify(r);
#endif
}

static void secp256k1_fe_mul(secp256k1_fe_t *r, const secp256k1_fe_t *a, const secp256k1_fe_t * SECP256K1_RESTRICT b) {
#ifdef VERIFY
    VERIFY_CHECK(a->magnitude <= 8);
    VERIFY_CHECK(b->magnitude <= 8);
    secp256k1_fe_verify(a);
    secp256k1_fe_verify(b);
    VERIFY_CHECK(r != b);
#endif
    secp256k1_fe_mul_inner(r->n, a->n, b->n);
#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 0;
    secp256k1_fe_verify(r);
#endif
}

static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
#ifdef VERIFY
    VERIFY_CHECK(a->magnitude <= 8);
    secp256k1_fe_verify(a);
#endif
    secp256k1_fe_sqr_inner(r->n, a->n);
#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 0;
    secp256k1_fe_verify(r);
#endif
}

static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
    uint64_t mask0, mask1;
    mask0 = flag + ~((uint64_t)0);
    mask1 = ~mask0;
    r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
    r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
    r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
    r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
    r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
#ifdef VERIFY
    if (a->magnitude > r->magnitude) {
        r->magnitude = a->magnitude;
    }
    r->normalized &= a->normalized;
#endif
}

static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t *r, const secp256k1_fe_storage_t *a, int flag) {
    uint64_t mask0, mask1;
    mask0 = flag + ~((uint64_t)0);
    mask1 = ~mask0;
    r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
    r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
    r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
    r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
}

static void secp256k1_fe_to_storage(secp256k1_fe_storage_t *r, const secp256k1_fe_t *a) {
#ifdef VERIFY
    VERIFY_CHECK(a->normalized);
#endif
    r->n[0] = a->n[0] | a->n[1] << 52;
    r->n[1] = a->n[1] >> 12 | a->n[2] << 40;
    r->n[2] = a->n[2] >> 24 | a->n[3] << 28;
    r->n[3] = a->n[3] >> 36 | a->n[4] << 16;
}

static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe_t *r, const secp256k1_fe_storage_t *a) {
    r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
    r->n[1] = a->n[0] >> 52 | ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
    r->n[2] = a->n[1] >> 40 | ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
    r->n[3] = a->n[2] >> 28 | ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
    r->n[4] = a->n[3] >> 16;
#ifdef VERIFY
    r->magnitude = 1;
    r->normalized = 1;
#endif
}

#endif
Commit	Line	Data
71712b27 GM	1	/**********************************************************************
	2	* Copyright (c) 2013, 2014 Pieter Wuille *
	3	* Distributed under the MIT software license, see the accompanying *
	4	* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
	5	**********************************************************************/
0a433ea2	6
7a4b7691 PW	7	#ifndef _SECP256K1_FIELD_REPR_IMPL_H_
	8	#define _SECP256K1_FIELD_REPR_IMPL_H_
	9
78cd96b1 CF	10	#if defined HAVE_CONFIG_H
	11	#include "libsecp256k1-config.h"
	12	#endif
	13
910d0de4	14	#include <string.h>
1c7fa133	15	#include "util.h"
11ab5622 PW	16	#include "num.h"
11ab5622 PW	17	#include "field.h"
e6d142a8	18
1ba4a60a	19	#if defined(USE_ASM_X86_64)
11ab5622	20	#include "field_5x52_asm_impl.h"
f0c89aad	21	#else
1ba4a60a	22	#include "field_5x52_int128_impl.h"
e6d142a8 PW	23	#endif
e6d142a8 PW	24
e6d142a8 PW	25	/** Implements arithmetic modulo FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F,
	26	* represented as 5 uint64_t's in base 2^52. The values are allowed to contain >52 each. In particular,
	27	* each FieldElem has a 'magnitude' associated with it. Internally, a magnitude M means each element
	28	* is at most M(2^53-1), except the most significant one, which is limited to M(2^49-1). All operations
	29	* accept any input with magnitude at most M, and have different rules for propagating magnitude to their
	30	* output.
	31	*/
	32
59447da3	33	#ifdef VERIFY
a4a43d75	34	static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
59447da3	35	const uint64_t *d = a->n;
21f81a84	36	int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
6efd6e77	37	/* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
59447da3 PD	38	r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
	39	r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
	40	r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
	41	r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
	42	r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
7d681ac6	43	r &= (a->magnitude >= 0);
7688e341	44	r &= (a->magnitude <= 2048);
59447da3	45	if (a->normalized) {
7d681ac6	46	r &= (a->magnitude <= 1);
59447da3 PD	47	if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
	48	r &= (d[0] < 0xFFFFEFFFFFC2FULL);
	49	}
	50	}
1c7fa133	51	VERIFY_CHECK(r == 1);
59447da3	52	}
21f81a84	53	#else
2cad067a GM	54	static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
	55	(void)a;
	56	}
59447da3 PD	57	#endif
59447da3 PD	58
a4a43d75	59	static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
90377077 PD	60	uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
90377077 PD	61
71712b27	62	/* Reduce t4 at the start so there will be at most a single carry from the first pass */
42822baa	63	uint64_t m;
25b35c7e	64	uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
90377077	65
71712b27	66	/* The first pass ensures the magnitude is 1, ... */
90377077 PD	67	t0 += x * 0x1000003D1ULL;
90377077 PD	68	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
42822baa PD	69	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
	70	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
	71	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
90377077	72
71712b27	73	/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
1c7fa133	74	VERIFY_CHECK(t4 >> 49 == 0);
90377077	75
71712b27	76	/* At most a single final reduction is needed; check if the value is >= the field characteristic */
42822baa	77	x = (t4 >> 48) \| ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
90377077 PD	78	& (t0 >= 0xFFFFEFFFFFC2FULL));
90377077 PD	79
71712b27	80	/* Apply the final reduction (for constant-time behaviour, we do it always) */
90377077 PD	81	t0 += x * 0x1000003D1ULL;
	82	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
	83	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
	84	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
	85	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
	86
71712b27	87	/* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
1c7fa133	88	VERIFY_CHECK(t4 >> 48 == x);
90377077	89
71712b27	90	/* Mask off the possible multiple of 2^256 from the final reduction */
90377077 PD	91	t4 &= 0x0FFFFFFFFFFFFULL;
90377077 PD	92
910d0de4 PW	93	r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
	94
	95	#ifdef VERIFY
	96	r->magnitude = 1;
	97	r->normalized = 1;
21f81a84	98	secp256k1_fe_verify(r);
910d0de4 PW	99	#endif
910d0de4 PW	100	}
e6d142a8	101
0295f0a3 PW	102	static void secp256k1_fe_normalize_weak(secp256k1_fe_t *r) {
	103	uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
	104
	105	/* Reduce t4 at the start so there will be at most a single carry from the first pass */
	106	uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
	107
	108	/* The first pass ensures the magnitude is 1, ... */
	109	t0 += x * 0x1000003D1ULL;
	110	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
	111	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
	112	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
	113	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
	114
	115	/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
	116	VERIFY_CHECK(t4 >> 49 == 0);
	117
	118	r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
	119
	120	#ifdef VERIFY
	121	r->magnitude = 1;
	122	secp256k1_fe_verify(r);
	123	#endif
	124	}
	125
39bd94d8 PW	126	static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
	127	uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
	128
	129	/* Reduce t4 at the start so there will be at most a single carry from the first pass */
39bd94d8	130	uint64_t m;
25b35c7e	131	uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
39bd94d8 PW	132
	133	/* The first pass ensures the magnitude is 1, ... */
	134	t0 += x * 0x1000003D1ULL;
	135	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
	136	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
	137	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
	138	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
	139
	140	/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
	141	VERIFY_CHECK(t4 >> 49 == 0);
	142
	143	/* At most a single final reduction is needed; check if the value is >= the field characteristic */
	144	x = (t4 >> 48) \| ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
	145	& (t0 >= 0xFFFFEFFFFFC2FULL));
	146
	147	if (x) {
	148	t0 += 0x1000003D1ULL;
	149	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
	150	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
	151	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
	152	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
	153
	154	/* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
	155	VERIFY_CHECK(t4 >> 48 == x);
	156
	157	/* Mask off the possible multiple of 2^256 from the final reduction */
	158	t4 &= 0x0FFFFFFFFFFFFULL;
	159	}
	160
	161	r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
	162
	163	#ifdef VERIFY
	164	r->magnitude = 1;
	165	r->normalized = 1;
	166	secp256k1_fe_verify(r);
	167	#endif
	168	}
	169
eed599dd PD	170	static int secp256k1_fe_normalizes_to_zero(secp256k1_fe_t *r) {
	171	uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
	172
eed599dd PD	173	/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
	174	uint64_t z0, z1;
	175
25b35c7e GM	176	/* Reduce t4 at the start so there will be at most a single carry from the first pass */
	177	uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
	178
eed599dd PD	179	/* The first pass ensures the magnitude is 1, ... */
	180	t0 += x * 0x1000003D1ULL;
	181	t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0 = t0; z1 = t0 ^ 0x1000003D0ULL;
	182	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 \|= t1; z1 &= t1;
	183	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 \|= t2; z1 &= t2;
	184	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 \|= t3; z1 &= t3;
	185	z0 \|= t4; z1 &= t4 ^ 0xF000000000000ULL;
49ee0dbe PD	186
	187	/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
	188	VERIFY_CHECK(t4 >> 49 == 0);
	189
	190	return (z0 == 0) \| (z1 == 0xFFFFFFFFFFFFFULL);
	191	}
	192
	193	static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe_t *r) {
25b35c7e GM	194	uint64_t t0, t1, t2, t3, t4;
	195	uint64_t z0, z1;
	196	uint64_t x;
	197
	198	t0 = r->n[0];
	199	t4 = r->n[4];
49ee0dbe PD	200
49ee0dbe PD	201	/* Reduce t4 at the start so there will be at most a single carry from the first pass */
25b35c7e	202	x = t4 >> 48;
49ee0dbe PD	203
	204	/* The first pass ensures the magnitude is 1, ... */
	205	t0 += x * 0x1000003D1ULL;
	206
	207	/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
25b35c7e GM	208	z0 = t0 & 0xFFFFFFFFFFFFFULL;
25b35c7e GM	209	z1 = z0 ^ 0x1000003D0ULL;
49ee0dbe PD	210
49ee0dbe PD	211	/* Fast return path should catch the majority of cases */
26320197	212	if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL)) {
49ee0dbe	213	return 0;
26320197	214	}
49ee0dbe	215
25b35c7e GM	216	t1 = r->n[1];
	217	t2 = r->n[2];
	218	t3 = r->n[3];
	219
49ee0dbe PD	220	t4 &= 0x0FFFFFFFFFFFFULL;
	221
	222	t1 += (t0 >> 52); t0 = z0;
	223	t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 \|= t1; z1 &= t1;
	224	t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 \|= t2; z1 &= t2;
	225	t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 \|= t3; z1 &= t3;
	226	z0 \|= t4; z1 &= t4 ^ 0xF000000000000ULL;
eed599dd PD	227
	228	/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
	229	VERIFY_CHECK(t4 >> 49 == 0);
	230
	231	return (z0 == 0) \| (z1 == 0xFFFFFFFFFFFFFULL);
	232	}
	233
a4a43d75	234	SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
910d0de4 PW	235	r->n[0] = a;
	236	r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
	237	#ifdef VERIFY
	238	r->magnitude = 1;
	239	r->normalized = 1;
21f81a84	240	secp256k1_fe_verify(r);
e6d142a8 PW	241	#endif
	242	}
	243
a4a43d75	244	SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe_t *a) {
25b35c7e	245	const uint64_t *t = a->n;
910d0de4	246	#ifdef VERIFY
1c7fa133	247	VERIFY_CHECK(a->normalized);
21f81a84	248	secp256k1_fe_verify(a);
e6d142a8	249	#endif
137e77af	250	return (t[0] \| t[1] \| t[2] \| t[3] \| t[4]) == 0;
e6d142a8 PW	251	}
e6d142a8 PW	252
a4a43d75	253	SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe_t *a) {
910d0de4	254	#ifdef VERIFY
1c7fa133	255	VERIFY_CHECK(a->normalized);
21f81a84	256	secp256k1_fe_verify(a);
e6d142a8	257	#endif
910d0de4	258	return a->n[0] & 1;
e6d142a8 PW	259	}
e6d142a8 PW	260
a4a43d75	261	SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
25b35c7e	262	int i;
2f6c8019 GM	263	#ifdef VERIFY
2f6c8019 GM	264	a->magnitude = 0;
7d681ac6	265	a->normalized = 1;
2f6c8019	266	#endif
25b35c7e	267	for (i=0; i<5; i++) {
2f6c8019 GM	268	a->n[i] = 0;
	269	}
	270	}
	271
f24041d6	272	static int secp256k1_fe_cmp_var(const secp256k1_fe_t a, const secp256k1_fe_t b) {
25b35c7e	273	int i;
f24041d6 PW	274	#ifdef VERIFY
	275	VERIFY_CHECK(a->normalized);
	276	VERIFY_CHECK(b->normalized);
	277	secp256k1_fe_verify(a);
	278	secp256k1_fe_verify(b);
	279	#endif
25b35c7e	280	for (i = 4; i >= 0; i--) {
26320197 GM	281	if (a->n[i] > b->n[i]) {
	282	return 1;
	283	}
	284	if (a->n[i] < b->n[i]) {
	285	return -1;
	286	}
f24041d6 PW	287	}
	288	return 0;
	289	}
	290
d907ebc0	291	static int secp256k1_fe_set_b32(secp256k1_fe_t r, const unsigned char a) {
25b35c7e	292	int i;
910d0de4	293	r->n[0] = r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
25b35c7e GM	294	for (i=0; i<32; i++) {
	295	int j;
	296	for (j=0; j<2; j++) {
e6d142a8 PW	297	int limb = (8i+4j)/52;
e6d142a8 PW	298	int shift = (8i+4j)%52;
910d0de4	299	r->n[limb] \|= (uint64_t)((a[31-i] >> (4*j)) & 0xF) << shift;
e6d142a8	300	}
e6d142a8	301	}
d907ebc0 PW	302	if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
	303	return 0;
	304	}
910d0de4 PW	305	#ifdef VERIFY
910d0de4 PW	306	r->magnitude = 1;
eb0be8ee	307	r->normalized = 1;
21f81a84	308	secp256k1_fe_verify(r);
910d0de4	309	#endif
d907ebc0	310	return 1;
e6d142a8 PW	311	}
e6d142a8 PW	312
910d0de4	313	/** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
a4a43d75	314	static void secp256k1_fe_get_b32(unsigned char r, const secp256k1_fe_t a) {
25b35c7e	315	int i;
910d0de4	316	#ifdef VERIFY
1c7fa133	317	VERIFY_CHECK(a->normalized);
21f81a84	318	secp256k1_fe_verify(a);
910d0de4	319	#endif
25b35c7e GM	320	for (i=0; i<32; i++) {
25b35c7e GM	321	int j;
910d0de4	322	int c = 0;
25b35c7e	323	for (j=0; j<2; j++) {
e6d142a8 PW	324	int limb = (8i+4j)/52;
e6d142a8 PW	325	int shift = (8i+4j)%52;
910d0de4	326	c \|= ((a->n[limb] >> shift) & 0xF) << (4 * j);
e6d142a8	327	}
910d0de4	328	r[31-i] = c;
e6d142a8	329	}
e6d142a8 PW	330	}
e6d142a8 PW	331
a4a43d75	332	SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe_t r, const secp256k1_fe_t a, int m) {
910d0de4	333	#ifdef VERIFY
1c7fa133	334	VERIFY_CHECK(a->magnitude <= m);
21f81a84	335	secp256k1_fe_verify(a);
e6d142a8	336	#endif
7a8e385d PW	337	r->n[0] = 0xFFFFEFFFFFC2FULL * 2 * (m + 1) - a->n[0];
	338	r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[1];
	339	r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[2];
	340	r->n[3] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[3];
	341	r->n[4] = 0x0FFFFFFFFFFFFULL * 2 * (m + 1) - a->n[4];
910d0de4	342	#ifdef VERIFY
21f81a84	343	r->magnitude = m + 1;
eb0be8ee	344	r->normalized = 0;
21f81a84	345	secp256k1_fe_verify(r);
e6d142a8	346	#endif
21f81a84 PW	347	}
21f81a84 PW	348
a4a43d75	349	SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe_t *r, int a) {
910d0de4 PW	350	r->n[0] *= a;
	351	r->n[1] *= a;
	352	r->n[2] *= a;
	353	r->n[3] *= a;
	354	r->n[4] *= a;
910d0de4	355	#ifdef VERIFY
21f81a84	356	r->magnitude *= a;
910d0de4	357	r->normalized = 0;
21f81a84	358	secp256k1_fe_verify(r);
e6d142a8	359	#endif
21f81a84 PW	360	}
21f81a84 PW	361
a4a43d75	362	SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe_t r, const secp256k1_fe_t a) {
7d681ac6 PD	363	#ifdef VERIFY
	364	secp256k1_fe_verify(a);
	365	#endif
910d0de4 PW	366	r->n[0] += a->n[0];
	367	r->n[1] += a->n[1];
	368	r->n[2] += a->n[2];
	369	r->n[3] += a->n[3];
	370	r->n[4] += a->n[4];
21f81a84 PW	371	#ifdef VERIFY
	372	r->magnitude += a->magnitude;
	373	r->normalized = 0;
	374	secp256k1_fe_verify(r);
21f81a84	375	#endif
e6d142a8 PW	376	}
e6d142a8 PW	377
be82e92f	378	static void secp256k1_fe_mul(secp256k1_fe_t r, const secp256k1_fe_t a, const secp256k1_fe_t * SECP256K1_RESTRICT b) {
910d0de4	379	#ifdef VERIFY
1c7fa133 PW	380	VERIFY_CHECK(a->magnitude <= 8);
1c7fa133 PW	381	VERIFY_CHECK(b->magnitude <= 8);
21f81a84 PW	382	secp256k1_fe_verify(a);
21f81a84 PW	383	secp256k1_fe_verify(b);
be82e92f	384	VERIFY_CHECK(r != b);
21f81a84	385	#endif
b2c9681c	386	secp256k1_fe_mul_inner(r->n, a->n, b->n);
21f81a84	387	#ifdef VERIFY
910d0de4 PW	388	r->magnitude = 1;
910d0de4 PW	389	r->normalized = 0;
21f81a84	390	secp256k1_fe_verify(r);
e6d142a8 PW	391	#endif
	392	}
	393
a4a43d75	394	static void secp256k1_fe_sqr(secp256k1_fe_t r, const secp256k1_fe_t a) {
910d0de4	395	#ifdef VERIFY
1c7fa133	396	VERIFY_CHECK(a->magnitude <= 8);
7d681ac6	397	secp256k1_fe_verify(a);
21f81a84	398	#endif
b2c9681c	399	secp256k1_fe_sqr_inner(r->n, a->n);
21f81a84	400	#ifdef VERIFY
fba1d58d PW	401	r->magnitude = 1;
fba1d58d PW	402	r->normalized = 0;
7d681ac6	403	secp256k1_fe_verify(r);
e6d142a8 PW	404	#endif
e6d142a8 PW	405	}
7a4b7691	406
bb0ea50d GM	407	static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe_t r, const secp256k1_fe_t a, int flag) {
	408	uint64_t mask0, mask1;
	409	mask0 = flag + ~((uint64_t)0);
	410	mask1 = ~mask0;
	411	r->n[0] = (r->n[0] & mask0) \| (a->n[0] & mask1);
	412	r->n[1] = (r->n[1] & mask0) \| (a->n[1] & mask1);
	413	r->n[2] = (r->n[2] & mask0) \| (a->n[2] & mask1);
	414	r->n[3] = (r->n[3] & mask0) \| (a->n[3] & mask1);
	415	r->n[4] = (r->n[4] & mask0) \| (a->n[4] & mask1);
	416	#ifdef VERIFY
a0601cd7 PD	417	if (a->magnitude > r->magnitude) {
	418	r->magnitude = a->magnitude;
	419	}
	420	r->normalized &= a->normalized;
bb0ea50d GM	421	#endif
	422	}
	423
f735446c	424	static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t r, const secp256k1_fe_storage_t a, int flag) {
27bc1311 GM	425	uint64_t mask0, mask1;
	426	mask0 = flag + ~((uint64_t)0);
	427	mask1 = ~mask0;
ff889f7d PW	428	r->n[0] = (r->n[0] & mask0) \| (a->n[0] & mask1);
	429	r->n[1] = (r->n[1] & mask0) \| (a->n[1] & mask1);
	430	r->n[2] = (r->n[2] & mask0) \| (a->n[2] & mask1);
	431	r->n[3] = (r->n[3] & mask0) \| (a->n[3] & mask1);
	432	}
	433
	434	static void secp256k1_fe_to_storage(secp256k1_fe_storage_t r, const secp256k1_fe_t a) {
	435	#ifdef VERIFY
	436	VERIFY_CHECK(a->normalized);
	437	#endif
	438	r->n[0] = a->n[0] \| a->n[1] << 52;
	439	r->n[1] = a->n[1] >> 12 \| a->n[2] << 40;
	440	r->n[2] = a->n[2] >> 24 \| a->n[3] << 28;
	441	r->n[3] = a->n[3] >> 36 \| a->n[4] << 16;
	442	}
	443
f735446c	444	static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe_t r, const secp256k1_fe_storage_t a) {
ff889f7d PW	445	r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
	446	r->n[1] = a->n[0] >> 52 \| ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
	447	r->n[2] = a->n[1] >> 40 \| ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
	448	r->n[3] = a->n[2] >> 28 \| ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
	449	r->n[4] = a->n[3] >> 16;
	450	#ifdef VERIFY
	451	r->magnitude = 1;
	452	r->normalized = 1;
	453	#endif
	454	}
	455
7a4b7691	456	#endif