[secp256k1.git] / src / num_gmp_impl.h

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

#ifndef _SECP256K1_NUM_REPR_IMPL_H_
#define _SECP256K1_NUM_REPR_IMPL_H_

#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <gmp.h>

#include "util.h"
#include "num.h"

#ifdef VERIFY
void static secp256k1_num_sanity(const secp256k1_num_t *a) {
    VERIFY_CHECK(a->limbs == 1 || (a->limbs > 1 && a->data[a->limbs-1] != 0));
}
#else
#define secp256k1_num_sanity(a) do { } while(0)
#endif

void static secp256k1_num_init(secp256k1_num_t *r) {
    r->neg = 0;
    r->limbs = 1;
    r->data[0] = 0;
}

void static secp256k1_num_clear(secp256k1_num_t *r) {
    memset(r, 0, sizeof(*r));
}

void static secp256k1_num_free(secp256k1_num_t *r) {
}

void static secp256k1_num_copy(secp256k1_num_t *r, const secp256k1_num_t *a) {
    *r = *a;
}

int static secp256k1_num_bits(const secp256k1_num_t *a) {
    int ret=(a->limbs-1)*GMP_NUMB_BITS;
    mp_limb_t x=a->data[a->limbs-1];
    while (x) {
        x >>= 1;
        ret++;
    }
    return ret;
}


void static secp256k1_num_get_bin(unsigned char *r, unsigned int rlen, const secp256k1_num_t *a) {
    unsigned char tmp[65];
    int len = 0;
    if (a->limbs>1 || a->data[0] != 0) {
        len = mpn_get_str(tmp, 256, (mp_limb_t*)a->data, a->limbs);
    }
    int shift = 0;
    while (shift < len && tmp[shift] == 0) shift++;
    VERIFY_CHECK(len-shift <= rlen);
    memset(r, 0, rlen - len + shift);
    if (len > shift) {
        memcpy(r + rlen - len + shift, tmp + shift, len - shift);
    }
    memset(tmp, 0, sizeof(tmp));
}

void static secp256k1_num_set_bin(secp256k1_num_t *r, const unsigned char *a, unsigned int alen) {
    VERIFY_CHECK(alen > 0);
    VERIFY_CHECK(alen <= 64);
    int len = mpn_set_str(r->data, a, alen, 256);
    VERIFY_CHECK(len <= NUM_LIMBS*2);
    r->limbs = len;
    r->neg = 0;
    while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
}

void static secp256k1_num_set_int(secp256k1_num_t *r, int a) {
    r->limbs = 1;
    r->neg = (a < 0);
    r->data[0] = (a < 0) ? -a : a;
}

void static secp256k1_num_add_abs(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    mp_limb_t c = mpn_add(r->data, a->data, a->limbs, b->data, b->limbs);
    r->limbs = a->limbs;
    if (c != 0) {
        VERIFY_CHECK(r->limbs < 2*NUM_LIMBS);
        r->data[r->limbs++] = c;
    }
}

void static secp256k1_num_sub_abs(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    mp_limb_t c = mpn_sub(r->data, a->data, a->limbs, b->data, b->limbs);
    VERIFY_CHECK(c == 0);
    r->limbs = a->limbs;
    while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
}

void static secp256k1_num_mod(secp256k1_num_t *r, const secp256k1_num_t *m) {
    secp256k1_num_sanity(r);
    secp256k1_num_sanity(m);

    if (r->limbs >= m->limbs) {
        mp_limb_t t[2*NUM_LIMBS];
        mpn_tdiv_qr(t, r->data, 0, r->data, r->limbs, m->data, m->limbs);
        memset(t, 0, sizeof(t));
        r->limbs = m->limbs;
        while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
    }

    if (r->neg && (r->limbs > 1 || r->data[0] != 0)) {
        secp256k1_num_sub_abs(r, m, r);
        r->neg = 0;
    }
}

void static secp256k1_num_mod_inverse(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *m) {
    secp256k1_num_sanity(a);
    secp256k1_num_sanity(m);

    // mpn_gcdext computes: (G,S) = gcdext(U,V), where
    // * G = gcd(U,V)
    // * G = U*S + V*T
    // * U has equal or more limbs than V, and V has no padding
    // If we set U to be (a padded version of) a, and V = m:
    //   G = a*S + m*T
    //   G = a*S mod m
    // Assuming G=1:
    //   S = 1/a mod m
    VERIFY_CHECK(m->limbs <= NUM_LIMBS);
    VERIFY_CHECK(m->data[m->limbs-1] != 0);
    mp_limb_t g[NUM_LIMBS+1];
    mp_limb_t u[NUM_LIMBS+1];
    mp_limb_t v[NUM_LIMBS+1];
    for (int i=0; i < m->limbs; i++) {
        u[i] = (i < a->limbs) ? a->data[i] : 0;
        v[i] = m->data[i];
    }
    mp_size_t sn = NUM_LIMBS+1;
    mp_size_t gn = mpn_gcdext(g, r->data, &sn, u, m->limbs, v, m->limbs);
    VERIFY_CHECK(gn == 1);
    VERIFY_CHECK(g[0] == 1);
    r->neg = a->neg ^ m->neg;
    if (sn < 0) {
        mpn_sub(r->data, m->data, m->limbs, r->data, -sn);
        r->limbs = m->limbs;
        while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
    } else {
        r->limbs = sn;
    }
    memset(g, 0, sizeof(g));
    memset(u, 0, sizeof(u));
    memset(v, 0, sizeof(v));
}

int static secp256k1_num_is_zero(const secp256k1_num_t *a) {
    return (a->limbs == 1 && a->data[0] == 0);
}

int static secp256k1_num_is_odd(const secp256k1_num_t *a) {
    return a->data[0] & 1;
}

int static secp256k1_num_is_neg(const secp256k1_num_t *a) {
    return (a->limbs > 1 || a->data[0] != 0) && a->neg;
}

int static secp256k1_num_cmp(const secp256k1_num_t *a, const secp256k1_num_t *b) {
    if (a->limbs > b->limbs) return 1;
    if (a->limbs < b->limbs) return -1;
    return mpn_cmp(a->data, b->data, a->limbs);
}

int static secp256k1_num_eq(const secp256k1_num_t *a, const secp256k1_num_t *b) {
    if (a->limbs > b->limbs) return 0;
    if (a->limbs < b->limbs) return 0;
    if ((a->neg && !secp256k1_num_is_zero(a)) != (b->neg && !secp256k1_num_is_zero(b))) return 0;
    return mpn_cmp(a->data, b->data, a->limbs) == 0;
}

void static secp256k1_num_subadd(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b, int bneg) {
    if (!(b->neg ^ bneg ^ a->neg)) { // a and b have the same sign
        r->neg = a->neg;
        if (a->limbs >= b->limbs) {
            secp256k1_num_add_abs(r, a, b);
        } else {
            secp256k1_num_add_abs(r, b, a);
        }
    } else {
        if (secp256k1_num_cmp(a, b) > 0) {
            r->neg = a->neg;
            secp256k1_num_sub_abs(r, a, b);
        } else {
            r->neg = b->neg ^ bneg;
            secp256k1_num_sub_abs(r, b, a);
        }
    }
}

void static secp256k1_num_add(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    secp256k1_num_sanity(a);
    secp256k1_num_sanity(b);
    secp256k1_num_subadd(r, a, b, 0);
}

void static secp256k1_num_sub(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    secp256k1_num_sanity(a);
    secp256k1_num_sanity(b);
    secp256k1_num_subadd(r, a, b, 1);
}

void static secp256k1_num_mul(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    secp256k1_num_sanity(a);
    secp256k1_num_sanity(b);

    mp_limb_t tmp[2*NUM_LIMBS+1];
    VERIFY_CHECK(a->limbs + b->limbs <= 2*NUM_LIMBS+1);
    if ((a->limbs==1 && a->data[0]==0) || (b->limbs==1 && b->data[0]==0)) {
        r->limbs = 1;
        r->neg = 0;
        r->data[0] = 0;
        return;
    }
    if (a->limbs >= b->limbs)
        mpn_mul(tmp, a->data, a->limbs, b->data, b->limbs);
    else
        mpn_mul(tmp, b->data, b->limbs, a->data, a->limbs);
    r->limbs = a->limbs + b->limbs;
    if (r->limbs > 1 && tmp[r->limbs - 1]==0) r->limbs--;
    VERIFY_CHECK(r->limbs <= 2*NUM_LIMBS);
    mpn_copyi(r->data, tmp, r->limbs);
    r->neg = a->neg ^ b->neg;
    memset(tmp, 0, sizeof(tmp));
}

void static secp256k1_num_div(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
    secp256k1_num_sanity(a);
    secp256k1_num_sanity(b);
    if (b->limbs > a->limbs) {
        r->limbs = 1;
        r->data[0] = 0;
        r->neg = 0;
        return;
    }

    mp_limb_t quo[2*NUM_LIMBS+1];
    mp_limb_t rem[2*NUM_LIMBS+1];
    mpn_tdiv_qr(quo, rem, 0, a->data, a->limbs, b->data, b->limbs);
    mpn_copyi(r->data, quo, a->limbs - b->limbs + 1);
    r->limbs = a->limbs - b->limbs + 1;
    while (r->limbs > 1 && r->data[r->limbs - 1]==0) r->limbs--;
    r->neg = a->neg ^ b->neg;
}

void static secp256k1_num_mod_mul(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b, const secp256k1_num_t *m) {
    secp256k1_num_mul(r, a, b);
    secp256k1_num_mod(r, m);
}


int static secp256k1_num_shift(secp256k1_num_t *r, int bits) {
    VERIFY_CHECK(bits <= GMP_NUMB_BITS);
    mp_limb_t ret = mpn_rshift(r->data, r->data, r->limbs, bits);
    if (r->limbs>1 && r->data[r->limbs-1]==0) r->limbs--;
    ret >>= (GMP_NUMB_BITS - bits);
    return ret;
}

int static secp256k1_num_get_bit(const secp256k1_num_t *a, int pos) {
    return (a->limbs*GMP_NUMB_BITS > pos) && ((a->data[pos/GMP_NUMB_BITS] >> (pos % GMP_NUMB_BITS)) & 1);
}

void static secp256k1_num_inc(secp256k1_num_t *r) {
    mp_limb_t ret = mpn_add_1(r->data, r->data, r->limbs, (mp_limb_t)1);
    if (ret) {
        VERIFY_CHECK(r->limbs < 2*NUM_LIMBS);
        r->data[r->limbs++] = ret;
    }
}

void static secp256k1_num_set_hex(secp256k1_num_t *r, const char *a, int alen) {
    static const unsigned char cvt[256] = {
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0,
        0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
        0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0
    };
    char num[257] = {};
    for (int i=0; i<alen; i++) {
        num[i] = cvt[a[i]];
    }
    r->limbs = mpn_set_str(r->data, num, alen, 16);
    while (r->limbs > 1 && r->data[r->limbs-1] == 0) r->limbs--;
}

void static secp256k1_num_get_hex(char *r, int rlen, const secp256k1_num_t *a) {
    static const unsigned char cvt[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    unsigned char *tmp = malloc(257);
    mp_size_t len = mpn_get_str(tmp, 16, (mp_limb_t*)a->data, a->limbs);
    VERIFY_CHECK(len <= rlen);
    for (int i=0; i<len; i++) {
        VERIFY_CHECK(rlen-len+i >= 0);
        VERIFY_CHECK(rlen-len+i < rlen);
        VERIFY_CHECK(tmp[i] >= 0);
        VERIFY_CHECK(tmp[i] < 16);
        r[rlen-len+i] = cvt[tmp[i]];
    }
    for (int i=0; i<rlen-len; i++) {
        VERIFY_CHECK(i >= 0);
        VERIFY_CHECK(i < rlen);
        r[i] = cvt[0];
    }
    free(tmp);
}

void static secp256k1_num_split(secp256k1_num_t *rl, secp256k1_num_t *rh, const secp256k1_num_t *a, int bits) {
    VERIFY_CHECK(bits > 0);
    rh->neg = a->neg;
    if (bits >= a->limbs * GMP_NUMB_BITS) {
        *rl = *a;
        rh->limbs = 1;
        rh->data[0] = 0;
        return;
    }
    rl->limbs = 0;
    rl->neg = a->neg;
    int left = bits;
    while (left >= GMP_NUMB_BITS) {
        rl->data[rl->limbs] = a->data[rl->limbs];
        rl->limbs++;
        left -= GMP_NUMB_BITS;
    }
    if (left == 0) {
        mpn_copyi(rh->data, a->data + rl->limbs, a->limbs - rl->limbs);
        rh->limbs = a->limbs - rl->limbs;
    } else {
        mpn_rshift(rh->data, a->data + rl->limbs, a->limbs - rl->limbs, left);
        rh->limbs = a->limbs - rl->limbs;
        while (rh->limbs>1 && rh->data[rh->limbs-1]==0) rh->limbs--;
    }
    if (left > 0) {
        rl->data[rl->limbs] = a->data[rl->limbs] & ((((mp_limb_t)1) << left) - 1);
        rl->limbs++;
    }
    while (rl->limbs>1 && rl->data[rl->limbs-1]==0) rl->limbs--;
}

void static secp256k1_num_negate(secp256k1_num_t *r) {
    r->neg ^= 1;
}

#endif
Commit	Line	Data
0a433ea2 PW	1	// Copyright (c) 2013 Pieter Wuille
	2	// Distributed under the MIT/X11 software license, see the accompanying
	3	// file COPYING or http://www.opensource.org/licenses/mit-license.php.
	4
7a4b7691 PW	5	#ifndef _SECP256K1_NUM_REPR_IMPL_H_
	6	#define _SECP256K1_NUM_REPR_IMPL_H_
	7
607884fc	8	#include <assert.h>
607884fc PW	9	#include <string.h>
	10	#include <stdlib.h>
	11	#include <gmp.h>
	12
1c7fa133	13	#include "util.h"
4adf6b2a	14	#include "num.h"
607884fc	15
898cecb3 PW	16	#ifdef VERIFY
898cecb3 PW	17	void static secp256k1_num_sanity(const secp256k1_num_t *a) {
1c7fa133	18	VERIFY_CHECK(a->limbs == 1 \|\| (a->limbs > 1 && a->data[a->limbs-1] != 0));
898cecb3 PW	19	}
	20	#else
	21	#define secp256k1_num_sanity(a) do { } while(0)
	22	#endif
607884fc	23
4adf6b2a	24	void static secp256k1_num_init(secp256k1_num_t *r) {
898cecb3 PW	25	r->neg = 0;
	26	r->limbs = 1;
	27	r->data[0] = 0;
607884fc PW	28	}
607884fc PW	29
2f6c8019 GM	30	void static secp256k1_num_clear(secp256k1_num_t *r) {
	31	memset(r, 0, sizeof(*r));
	32	}
	33
4adf6b2a	34	void static secp256k1_num_free(secp256k1_num_t *r) {
607884fc PW	35	}
607884fc PW	36
4adf6b2a	37	void static secp256k1_num_copy(secp256k1_num_t r, const secp256k1_num_t a) {
898cecb3 PW	38	r = a;
	39	}
	40
	41	int static secp256k1_num_bits(const secp256k1_num_t *a) {
	42	int ret=(a->limbs-1)*GMP_NUMB_BITS;
	43	mp_limb_t x=a->data[a->limbs-1];
	44	while (x) {
	45	x >>= 1;
	46	ret++;
	47	}
	48	return ret;
607884fc PW	49	}
607884fc PW	50
898cecb3	51
4adf6b2a	52	void static secp256k1_num_get_bin(unsigned char r, unsigned int rlen, const secp256k1_num_t a) {
898cecb3	53	unsigned char tmp[65];
404c30a8 PW	54	int len = 0;
	55	if (a->limbs>1 \|\| a->data[0] != 0) {
	56	len = mpn_get_str(tmp, 256, (mp_limb_t*)a->data, a->limbs);
	57	}
	58	int shift = 0;
	59	while (shift < len && tmp[shift] == 0) shift++;
1c7fa133	60	VERIFY_CHECK(len-shift <= rlen);
404c30a8	61	memset(r, 0, rlen - len + shift);
2f6c8019	62	if (len > shift) {
404c30a8	63	memcpy(r + rlen - len + shift, tmp + shift, len - shift);
2f6c8019 GM	64	}
2f6c8019 GM	65	memset(tmp, 0, sizeof(tmp));
607884fc PW	66	}
607884fc PW	67
4adf6b2a	68	void static secp256k1_num_set_bin(secp256k1_num_t r, const unsigned char a, unsigned int alen) {
1c7fa133 PW	69	VERIFY_CHECK(alen > 0);
1c7fa133 PW	70	VERIFY_CHECK(alen <= 64);
898cecb3	71	int len = mpn_set_str(r->data, a, alen, 256);
1c7fa133	72	VERIFY_CHECK(len <= NUM_LIMBS*2);
898cecb3 PW	73	r->limbs = len;
	74	r->neg = 0;
	75	while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
607884fc PW	76	}
607884fc PW	77
4adf6b2a	78	void static secp256k1_num_set_int(secp256k1_num_t *r, int a) {
898cecb3 PW	79	r->limbs = 1;
	80	r->neg = (a < 0);
	81	r->data[0] = (a < 0) ? -a : a;
	82	}
	83
79b0ce6c PW	84	void static secp256k1_num_add_abs(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
	85	mp_limb_t c = mpn_add(r->data, a->data, a->limbs, b->data, b->limbs);
	86	r->limbs = a->limbs;
	87	if (c != 0) {
1c7fa133	88	VERIFY_CHECK(r->limbs < 2*NUM_LIMBS);
79b0ce6c PW	89	r->data[r->limbs++] = c;
	90	}
	91	}
	92
	93	void static secp256k1_num_sub_abs(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
	94	mp_limb_t c = mpn_sub(r->data, a->data, a->limbs, b->data, b->limbs);
1c7fa133	95	VERIFY_CHECK(c == 0);
79b0ce6c PW	96	r->limbs = a->limbs;
	97	while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
	98	}
	99
2f9e831d PW	100	void static secp256k1_num_mod(secp256k1_num_t r, const secp256k1_num_t m) {
	101	secp256k1_num_sanity(r);
	102	secp256k1_num_sanity(m);
898cecb3	103
2f9e831d PW	104	if (r->limbs >= m->limbs) {
	105	mp_limb_t t[2*NUM_LIMBS];
	106	mpn_tdiv_qr(t, r->data, 0, r->data, r->limbs, m->data, m->limbs);
2f6c8019	107	memset(t, 0, sizeof(t));
2f9e831d PW	108	r->limbs = m->limbs;
2f9e831d PW	109	while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
79b0ce6c PW	110	}
	111
	112	if (r->neg && (r->limbs > 1 \|\| r->data[0] != 0)) {
	113	secp256k1_num_sub_abs(r, m, r);
	114	r->neg = 0;
898cecb3	115	}
607884fc PW	116	}
607884fc PW	117
4adf6b2a	118	void static secp256k1_num_mod_inverse(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *m) {
898cecb3 PW	119	secp256k1_num_sanity(a);
	120	secp256k1_num_sanity(m);
	121
898cecb3 PW	122	// mpn_gcdext computes: (G,S) = gcdext(U,V), where
	123	// * G = gcd(U,V)
	124	// * G = US + VT
	125	// * U has equal or more limbs than V, and V has no padding
	126	// If we set U to be (a padded version of) a, and V = m:
	127	// G = aS + mT
	128	// G = a*S mod m
	129	// Assuming G=1:
	130	// S = 1/a mod m
1c7fa133 PW	131	VERIFY_CHECK(m->limbs <= NUM_LIMBS);
1c7fa133 PW	132	VERIFY_CHECK(m->data[m->limbs-1] != 0);
898cecb3 PW	133	mp_limb_t g[NUM_LIMBS+1];
	134	mp_limb_t u[NUM_LIMBS+1];
	135	mp_limb_t v[NUM_LIMBS+1];
	136	for (int i=0; i < m->limbs; i++) {
	137	u[i] = (i < a->limbs) ? a->data[i] : 0;
	138	v[i] = m->data[i];
	139	}
	140	mp_size_t sn = NUM_LIMBS+1;
	141	mp_size_t gn = mpn_gcdext(g, r->data, &sn, u, m->limbs, v, m->limbs);
1c7fa133 PW	142	VERIFY_CHECK(gn == 1);
1c7fa133 PW	143	VERIFY_CHECK(g[0] == 1);
898cecb3 PW	144	r->neg = a->neg ^ m->neg;
	145	if (sn < 0) {
	146	mpn_sub(r->data, m->data, m->limbs, r->data, -sn);
	147	r->limbs = m->limbs;
	148	while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
	149	} else {
	150	r->limbs = sn;
	151	}
2f6c8019 GM	152	memset(g, 0, sizeof(g));
	153	memset(u, 0, sizeof(u));
	154	memset(v, 0, sizeof(v));
607884fc PW	155	}
607884fc PW	156
898cecb3 PW	157	int static secp256k1_num_is_zero(const secp256k1_num_t *a) {
898cecb3 PW	158	return (a->limbs == 1 && a->data[0] == 0);
607884fc PW	159	}
607884fc PW	160
898cecb3 PW	161	int static secp256k1_num_is_odd(const secp256k1_num_t *a) {
898cecb3 PW	162	return a->data[0] & 1;
607884fc PW	163	}
607884fc PW	164
898cecb3 PW	165	int static secp256k1_num_is_neg(const secp256k1_num_t *a) {
898cecb3 PW	166	return (a->limbs > 1 \|\| a->data[0] != 0) && a->neg;
607884fc PW	167	}
607884fc PW	168
898cecb3 PW	169	int static secp256k1_num_cmp(const secp256k1_num_t a, const secp256k1_num_t b) {
	170	if (a->limbs > b->limbs) return 1;
	171	if (a->limbs < b->limbs) return -1;
	172	return mpn_cmp(a->data, b->data, a->limbs);
607884fc PW	173	}
607884fc PW	174
1a749b4a PW	175	int static secp256k1_num_eq(const secp256k1_num_t a, const secp256k1_num_t b) {
	176	if (a->limbs > b->limbs) return 0;
	177	if (a->limbs < b->limbs) return 0;
	178	if ((a->neg && !secp256k1_num_is_zero(a)) != (b->neg && !secp256k1_num_is_zero(b))) return 0;
	179	return mpn_cmp(a->data, b->data, a->limbs) == 0;
	180	}
	181
898cecb3 PW	182	void static secp256k1_num_subadd(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b, int bneg) {
	183	if (!(b->neg ^ bneg ^ a->neg)) { // a and b have the same sign
	184	r->neg = a->neg;
	185	if (a->limbs >= b->limbs) {
	186	secp256k1_num_add_abs(r, a, b);
	187	} else {
	188	secp256k1_num_add_abs(r, b, a);
	189	}
	190	} else {
	191	if (secp256k1_num_cmp(a, b) > 0) {
	192	r->neg = a->neg;
	193	secp256k1_num_sub_abs(r, a, b);
	194	} else {
	195	r->neg = b->neg ^ bneg;
	196	secp256k1_num_sub_abs(r, b, a);
	197	}
	198	}
607884fc PW	199	}
607884fc PW	200
898cecb3 PW	201	void static secp256k1_num_add(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
	202	secp256k1_num_sanity(a);
	203	secp256k1_num_sanity(b);
898cecb3	204	secp256k1_num_subadd(r, a, b, 0);
607884fc PW	205	}
607884fc PW	206
898cecb3	207	void static secp256k1_num_sub(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
898cecb3 PW	208	secp256k1_num_sanity(a);
898cecb3 PW	209	secp256k1_num_sanity(b);
898cecb3	210	secp256k1_num_subadd(r, a, b, 1);
607884fc PW	211	}
607884fc PW	212
898cecb3	213	void static secp256k1_num_mul(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
898cecb3 PW	214	secp256k1_num_sanity(a);
	215	secp256k1_num_sanity(b);
	216
	217	mp_limb_t tmp[2*NUM_LIMBS+1];
1c7fa133	218	VERIFY_CHECK(a->limbs + b->limbs <= 2*NUM_LIMBS+1);
898cecb3 PW	219	if ((a->limbs==1 && a->data[0]==0) \|\| (b->limbs==1 && b->data[0]==0)) {
	220	r->limbs = 1;
	221	r->neg = 0;
	222	r->data[0] = 0;
	223	return;
	224	}
	225	if (a->limbs >= b->limbs)
	226	mpn_mul(tmp, a->data, a->limbs, b->data, b->limbs);
	227	else
	228	mpn_mul(tmp, b->data, b->limbs, a->data, a->limbs);
	229	r->limbs = a->limbs + b->limbs;
	230	if (r->limbs > 1 && tmp[r->limbs - 1]==0) r->limbs--;
1c7fa133	231	VERIFY_CHECK(r->limbs <= 2*NUM_LIMBS);
898cecb3 PW	232	mpn_copyi(r->data, tmp, r->limbs);
898cecb3 PW	233	r->neg = a->neg ^ b->neg;
2f6c8019	234	memset(tmp, 0, sizeof(tmp));
607884fc PW	235	}
607884fc PW	236
898cecb3 PW	237	void static secp256k1_num_div(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t *b) {
	238	secp256k1_num_sanity(a);
	239	secp256k1_num_sanity(b);
	240	if (b->limbs > a->limbs) {
	241	r->limbs = 1;
	242	r->data[0] = 0;
	243	r->neg = 0;
	244	return;
	245	}
	246
	247	mp_limb_t quo[2*NUM_LIMBS+1];
	248	mp_limb_t rem[2*NUM_LIMBS+1];
	249	mpn_tdiv_qr(quo, rem, 0, a->data, a->limbs, b->data, b->limbs);
	250	mpn_copyi(r->data, quo, a->limbs - b->limbs + 1);
	251	r->limbs = a->limbs - b->limbs + 1;
	252	while (r->limbs > 1 && r->data[r->limbs - 1]==0) r->limbs--;
	253	r->neg = a->neg ^ b->neg;
607884fc PW	254	}
607884fc PW	255
898cecb3	256	void static secp256k1_num_mod_mul(secp256k1_num_t r, const secp256k1_num_t a, const secp256k1_num_t b, const secp256k1_num_t m) {
2f9e831d PW	257	secp256k1_num_mul(r, a, b);
2f9e831d PW	258	secp256k1_num_mod(r, m);
898cecb3 PW	259	}
	260
	261
	262	int static secp256k1_num_shift(secp256k1_num_t *r, int bits) {
1c7fa133	263	VERIFY_CHECK(bits <= GMP_NUMB_BITS);
898cecb3 PW	264	mp_limb_t ret = mpn_rshift(r->data, r->data, r->limbs, bits);
	265	if (r->limbs>1 && r->data[r->limbs-1]==0) r->limbs--;
	266	ret >>= (GMP_NUMB_BITS - bits);
	267	return ret;
607884fc PW	268	}
607884fc PW	269
4adf6b2a	270	int static secp256k1_num_get_bit(const secp256k1_num_t *a, int pos) {
898cecb3	271	return (a->limbs*GMP_NUMB_BITS > pos) && ((a->data[pos/GMP_NUMB_BITS] >> (pos % GMP_NUMB_BITS)) & 1);
607884fc PW	272	}
607884fc PW	273
4adf6b2a	274	void static secp256k1_num_inc(secp256k1_num_t *r) {
898cecb3 PW	275	mp_limb_t ret = mpn_add_1(r->data, r->data, r->limbs, (mp_limb_t)1);
898cecb3 PW	276	if (ret) {
1c7fa133	277	VERIFY_CHECK(r->limbs < 2*NUM_LIMBS);
898cecb3 PW	278	r->data[r->limbs++] = ret;
898cecb3 PW	279	}
607884fc PW	280	}
607884fc PW	281
4adf6b2a	282	void static secp256k1_num_set_hex(secp256k1_num_t r, const char a, int alen) {
898cecb3 PW	283	static const unsigned char cvt[256] = {
	284	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	285	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	286	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	287	0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0,
	288	0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
	289	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	290	0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
	291	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	292	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	293	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	294	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	295	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	296	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	297	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	298	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
	299	0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0
	300	};
	301	char num[257] = {};
	302	for (int i=0; i<alen; i++) {
	303	num[i] = cvt[a[i]];
	304	}
	305	r->limbs = mpn_set_str(r->data, num, alen, 16);
	306	while (r->limbs > 1 && r->data[r->limbs-1] == 0) r->limbs--;
607884fc PW	307	}
607884fc PW	308
898cecb3 PW	309	void static secp256k1_num_get_hex(char r, int rlen, const secp256k1_num_t a) {
	310	static const unsigned char cvt[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
	311	unsigned char *tmp = malloc(257);
	312	mp_size_t len = mpn_get_str(tmp, 16, (mp_limb_t*)a->data, a->limbs);
1c7fa133	313	VERIFY_CHECK(len <= rlen);
898cecb3	314	for (int i=0; i<len; i++) {
1c7fa133 PW	315	VERIFY_CHECK(rlen-len+i >= 0);
	316	VERIFY_CHECK(rlen-len+i < rlen);
	317	VERIFY_CHECK(tmp[i] >= 0);
	318	VERIFY_CHECK(tmp[i] < 16);
898cecb3	319	r[rlen-len+i] = cvt[tmp[i]];
4adf6b2a	320	}
898cecb3	321	for (int i=0; i<rlen-len; i++) {
1c7fa133 PW	322	VERIFY_CHECK(i >= 0);
1c7fa133 PW	323	VERIFY_CHECK(i < rlen);
898cecb3 PW	324	r[i] = cvt[0];
	325	}
	326	free(tmp);
607884fc PW	327	}
607884fc PW	328
4adf6b2a	329	void static secp256k1_num_split(secp256k1_num_t rl, secp256k1_num_t rh, const secp256k1_num_t *a, int bits) {
1c7fa133	330	VERIFY_CHECK(bits > 0);
898cecb3 PW	331	rh->neg = a->neg;
	332	if (bits >= a->limbs * GMP_NUMB_BITS) {
	333	rl = a;
	334	rh->limbs = 1;
	335	rh->data[0] = 0;
	336	return;
	337	}
	338	rl->limbs = 0;
	339	rl->neg = a->neg;
	340	int left = bits;
	341	while (left >= GMP_NUMB_BITS) {
	342	rl->data[rl->limbs] = a->data[rl->limbs];
	343	rl->limbs++;
	344	left -= GMP_NUMB_BITS;
	345	}
	346	if (left == 0) {
	347	mpn_copyi(rh->data, a->data + rl->limbs, a->limbs - rl->limbs);
	348	rh->limbs = a->limbs - rl->limbs;
	349	} else {
	350	mpn_rshift(rh->data, a->data + rl->limbs, a->limbs - rl->limbs, left);
	351	rh->limbs = a->limbs - rl->limbs;
	352	while (rh->limbs>1 && rh->data[rh->limbs-1]==0) rh->limbs--;
	353	}
	354	if (left > 0) {
	355	rl->data[rl->limbs] = a->data[rl->limbs] & ((((mp_limb_t)1) << left) - 1);
	356	rl->limbs++;
	357	}
	358	while (rl->limbs>1 && rl->data[rl->limbs-1]==0) rl->limbs--;
607884fc PW	359	}
607884fc PW	360
4adf6b2a	361	void static secp256k1_num_negate(secp256k1_num_t *r) {
898cecb3	362	r->neg ^= 1;
607884fc PW	363	}
607884fc PW	364
7a4b7691	365	#endif