958 lines
22 KiB
C
958 lines
22 KiB
C
/*
|
|
* bigint2.c
|
|
*
|
|
* Created on: 09.04.2014
|
|
* Author: bg
|
|
*/
|
|
|
|
#include <bigint2.h>
|
|
#include <bigint2_io.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
#define CHECKS 1
|
|
|
|
#define E_PARAM -1;
|
|
#define E_OOM -2;
|
|
#define E_VALUE -3;
|
|
|
|
|
|
#define MAX(a,b) ((a) > (b) ? (a) : (b))
|
|
#define MIN(a,b) ((a) < (b) ? (a) : (b))
|
|
|
|
void *(*int_realloc)(void *ptr, size_t size);
|
|
void (*int_free)(void *ptr);
|
|
|
|
/**
|
|
* \brief used to check if bigint is large enough
|
|
* Checks if the memory of a is large enough to hold min_size
|
|
* words, and if this is not the case tries to increase the allocated memory
|
|
* amount (conserving the memory content).
|
|
* If the allocated memory insufficient and the buffer could not be enlarged
|
|
* E_OOM is returned, otherwise 0 is returned.
|
|
*/
|
|
static
|
|
int check_size(bigint_t *a, bigint_length_t min_size) {
|
|
bigint_word_t *tmp;
|
|
if (a->allocated_W >= min_size) {
|
|
return 0;
|
|
}
|
|
tmp = int_realloc(a->wordv, min_size * sizeof(bigint_word_t));
|
|
if (!tmp) {
|
|
return E_OOM;
|
|
}
|
|
a->wordv = tmp;
|
|
a->allocated_W = min_size;
|
|
return 0;
|
|
}
|
|
|
|
int bigint_copy(bigint_t *dest, const bigint_t *a) {
|
|
int r;
|
|
if (dest == a) {
|
|
return 0;
|
|
}
|
|
r = check_size(dest, a->length_W);
|
|
if (r) {
|
|
return r;
|
|
}
|
|
dest->info = a->info;
|
|
dest->length_W = a->length_W;
|
|
memcpy(dest->wordv, a->wordv, a->length_W * sizeof(bigint_word_t));
|
|
|
|
return 0;
|
|
}
|
|
|
|
int bigint_free(bigint_t *a) {
|
|
if(a->allocated_W) {
|
|
int_free(a->wordv);
|
|
}
|
|
memset(a, 0, sizeof(bigint_t));
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = |a| + |b|
|
|
* Adds the bigints a and b and stores the result in dest.
|
|
* Signs are ignored.
|
|
*/
|
|
int bigint_add_u(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
bigint_word_t t, c1, c2, c = 0;
|
|
bigint_length_t i, j;
|
|
int r;
|
|
#if CHECKS
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
#if CHECKS
|
|
if ((r = check_size(dest, a->length_W))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
j = MIN(a->length_W, b->length_W);
|
|
for (i = 0; i < j; ++i) {
|
|
t = a->wordv[i] + b->wordv[i];
|
|
c1 = t < a->wordv[i];
|
|
dest->wordv[i] = t + c;
|
|
c2 = dest->wordv[i] < t;
|
|
c = c1 | c2;
|
|
}
|
|
for (; i < a->length_W; ++i) {
|
|
t = a->wordv[i];
|
|
dest->wordv[i] = t + c;
|
|
c = dest->wordv[i] < t;
|
|
}
|
|
dest->length_W = i;
|
|
return 0;
|
|
}
|
|
|
|
/** UNSAFE!!!
|
|
* \brief dest = |a| + |b|
|
|
* Adds the bigints a and b and stores the result in dest.
|
|
* Signs are ignored.
|
|
*/
|
|
int bigint_add_auto_u(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
bigint_word_t t, c1, c2, c = 0;
|
|
bigint_length_t i, j;
|
|
int r;
|
|
#if CHECKS
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
if (a->length_W < b->length_W) {
|
|
const bigint_t *t;
|
|
t = a;
|
|
a = b;
|
|
b = t;
|
|
}
|
|
#if CHECKS
|
|
if ((r = check_size(dest, a->length_W + 1))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
j = MIN(a->length_W, b->length_W);
|
|
for (i = 0; i < j; ++i) {
|
|
t = a->wordv[i] + b->wordv[i];
|
|
c1 = t < a->wordv[i];
|
|
dest->wordv[i] = t + c;
|
|
c2 = dest->wordv[i] < t;
|
|
c = c1 | c2;
|
|
}
|
|
for (; i < a->length_W; ++i) {
|
|
t = a->wordv[i];
|
|
dest->wordv[i] = t + c;
|
|
c = dest->wordv[i] < t;
|
|
}
|
|
if (c) {
|
|
dest->wordv[i++] = c;
|
|
}
|
|
dest->length_W = i;
|
|
return 0;
|
|
}
|
|
|
|
|
|
/**
|
|
* \brief dest = ~a
|
|
*/
|
|
int bigint_invert(bigint_t *dest, const bigint_t *a) {
|
|
bigint_length_t i;
|
|
int r;
|
|
#if CHECKS
|
|
if ((r = check_size(dest, a->length_W))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
i = a->length_W;
|
|
while(i--) {
|
|
dest->wordv[i] = ~a->wordv[i];
|
|
}
|
|
dest->length_W = a->length_W;
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = a + 1
|
|
*/
|
|
int bigint_add_one(bigint_t *dest, const bigint_t *a) {
|
|
bigint_t one = {
|
|
.wordv = (bigint_word_t*)"\x01",
|
|
.length_W = 1,
|
|
.allocated_W = 1,
|
|
.info = 0
|
|
};
|
|
return bigint_add_u(dest, a, &one);
|
|
}
|
|
|
|
/**
|
|
* \brief dest = -a
|
|
*/
|
|
int bigint_negate(bigint_t *dest, const bigint_t *a) {
|
|
int r = 0;
|
|
#if CHECKS
|
|
if ((r = check_size(dest, a->length_W))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
r |= bigint_invert(dest, a);
|
|
r |= bigint_add_one(dest, dest);
|
|
return r;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = |a| - |b|
|
|
* Subtracts b from a and stores the result in dest.
|
|
* Signs are ignored
|
|
*/
|
|
int bigint_sub_u(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
bigint_length_t i, j;
|
|
bigint_word_t t, c1, c2, c = 0;
|
|
int r;
|
|
#if CHECKS
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
#if CHECKS
|
|
if ((r = check_size(dest, MAX(a->length_W, b->length_W)))) {
|
|
return r;
|
|
}
|
|
|
|
#endif
|
|
j = MIN(a->length_W, b->length_W);
|
|
for (i = 0; i < j; ++i) {
|
|
t = a->wordv[i] - b->wordv[i];
|
|
c1 = t > a->wordv[i];
|
|
dest->wordv[i] = t - c;
|
|
c2 = dest->wordv[i] > t;
|
|
c = c1 | c2;
|
|
}
|
|
for (; i < a->length_W; ++i) {
|
|
t = a->wordv[i];
|
|
dest->wordv[i] = t - c;
|
|
c = dest->wordv[i] > t;
|
|
}
|
|
dest->length_W = a->length_W;
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief a <<= 1
|
|
*/
|
|
int bigint_shiftleft_words(bigint_t *dest, const bigint_t *a, bigint_length_t s) {
|
|
#if CHECKS
|
|
if (!a) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
if (s == 0) {
|
|
bigint_copy(dest, a);
|
|
return 0;
|
|
}
|
|
int r;
|
|
if ((r = check_size(dest, a->length_W + s))) {
|
|
return r;
|
|
}
|
|
memmove(&dest->wordv[s], &a->wordv[0], a->length_W * sizeof(bigint_word_t));
|
|
memset(&dest->wordv[0], 0, s * sizeof(bigint_word_t));
|
|
dest->length_W = a->length_W + s;
|
|
return 0;
|
|
}
|
|
|
|
|
|
/**
|
|
* \brief a <<= 1
|
|
*/
|
|
int bigint_shiftleft_1bit(bigint_t *a) {
|
|
uint8_t c1 = 0, c2;
|
|
bigint_word_t t;
|
|
bigint_length_t i;
|
|
#if CHECKS
|
|
if (!a) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
|
|
for(i = 0; i < a->length_W; ++i) {
|
|
t = a->wordv[i];
|
|
c2 = t >> (BIGINT_WORD_SIZE - 1);
|
|
t <<= 1;
|
|
t |= c1;
|
|
a->wordv[i] = t;
|
|
c1 = c2;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief a <<= s
|
|
*/
|
|
static
|
|
int bigint_shiftleft_small(bigint_t *dest, const bigint_t *a, uint_fast8_t s) {
|
|
bigint_wordplus_t t = 0;
|
|
bigint_length_t i, l;
|
|
#if CHECKS
|
|
if (!a) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
l = bigint_get_first_set_bit(a) + BIGINT_WORD_SIZE;
|
|
#if CHECKS
|
|
int r;
|
|
if ((r = check_size(dest, (l + s ) / BIGINT_WORD_SIZE))) {
|
|
return r;
|
|
}
|
|
|
|
#endif
|
|
dest->length_W = (l + s ) / BIGINT_WORD_SIZE;
|
|
l /= BIGINT_WORD_SIZE;
|
|
for(i = 0; i < l; ++i) {
|
|
t |= (bigint_wordplus_t)a->wordv[i] << s;
|
|
dest->wordv[i] = t;
|
|
t >>= BIGINT_WORD_SIZE;
|
|
}
|
|
if (t) {
|
|
dest->wordv[i] = t;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = a << s
|
|
*/
|
|
int bigint_shiftleft(bigint_t *dest, const bigint_t *a, bigint_length_t s) {
|
|
int r;
|
|
if((r = bigint_shiftleft_small(dest, a, s % BIGINT_WORD_SIZE))) {
|
|
return r;
|
|
}
|
|
if ((r = bigint_shiftleft_words(dest, dest, s / BIGINT_WORD_SIZE))) {
|
|
return r;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief a >>= 1
|
|
*/
|
|
int bigint_shiftright_1bit(bigint_t *a) {
|
|
uint8_t c1 = 0, c2;
|
|
bigint_word_t t;
|
|
bigint_length_t i;
|
|
#if CHECKS
|
|
if (!a) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
|
|
for(i = a->length_W; i != 0; --i) {
|
|
t = a->wordv[i - 1];
|
|
c2 = t & 1;
|
|
t >>= 1;
|
|
t |= c1 << (BIGINT_WORD_SIZE - 1);
|
|
a->wordv[i - 1] = t;
|
|
c1 = c2;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = a ** 2
|
|
*/
|
|
int bigint_square(bigint_t *dest, const bigint_t *a) {
|
|
bigint_word_t c1, c2;
|
|
bigint_wordplus_t uv;
|
|
bigint_word_t q;
|
|
bigint_length_t i, j;
|
|
#if CHECKS
|
|
int r;
|
|
if (!dest || !a) {
|
|
return E_PARAM;
|
|
}
|
|
if ((r = check_size(dest, a->length_W * 2))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
if (dest == a) {
|
|
bigint_t t = {NULL, 0, 0, 0};
|
|
bigint_copy(&t, a);
|
|
r = bigint_square(dest, &t);
|
|
bigint_free(&t);
|
|
return r;
|
|
}
|
|
memset(dest->wordv, 0, 2 * a->length_W * sizeof(bigint_word_t));
|
|
for(i = 0; i < a->length_W; ++i) {
|
|
uv = (bigint_wordplus_t)dest->wordv[2 * i]
|
|
+ (bigint_wordplus_t)a->wordv[i]
|
|
* (bigint_wordplus_t)a->wordv[i];
|
|
dest->wordv[2 * i] = uv;
|
|
c1 = uv >> BIGINT_WORD_SIZE;
|
|
c2 = 0;
|
|
for (j = i + 1; j < a->length_W; ++j) {
|
|
uv = (bigint_wordplus_t)a->wordv[i]
|
|
* (bigint_wordplus_t)a->wordv[j];
|
|
q = uv >> (2 * BIGINT_WORD_SIZE - 1);
|
|
uv <<= 1;
|
|
uv += dest->wordv[i + j];
|
|
q += (uv < dest->wordv[i + j]); /* this might be dangerous! XXX */
|
|
uv += c1;
|
|
q += (uv < c1); /* this might be dangerous! XXX */
|
|
dest->wordv[i + j] = uv;
|
|
c1 = c2 + (uv >> BIGINT_WORD_SIZE);
|
|
c2 = q + (c1 < c2); /* this might be dangerous! XXX */
|
|
}
|
|
dest->wordv[i + a->length_W] += c1;
|
|
dest->wordv[i + a->length_W + 1] = c2 + (dest->wordv[i + a->length_W] < c1); /* this might be dangerous! XXX */
|
|
}
|
|
dest->length_W = a->length_W * 2;
|
|
return 0;
|
|
}
|
|
|
|
|
|
/**
|
|
* \brief dest = |a * b|
|
|
* unsigned multiply a bigint (a) by a word (b)
|
|
*/
|
|
int bigint_mul_word(bigint_t *dest, const bigint_t *a, const bigint_word_t b) {
|
|
bigint_wordplus_t c1 = 0;
|
|
bigint_length_t i;
|
|
#if CHECKS
|
|
int r;
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
if ((r = check_size(dest, a->length_W + 1))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
for(i = 0; i < a->length_W; ++i) {
|
|
c1 += (bigint_wordplus_t)b * (bigint_wordplus_t)a->wordv[i];
|
|
dest->wordv[i] = c1;
|
|
c1 >>= BIGINT_WORD_SIZE;
|
|
}
|
|
dest->wordv[i++] = c1;
|
|
dest->length_W = i;
|
|
BIGINT_SET_POS(dest);
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* \brief dest = a * b
|
|
*/
|
|
int bigint_mul_schoolbook(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
bigint_wordplus_t v;
|
|
bigint_word_t c;
|
|
bigint_length_t i, j;
|
|
int r;
|
|
#if CHECKS
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
if ((r = check_size(dest, a->length_W + b->length_W))) {
|
|
return r;
|
|
}
|
|
#endif
|
|
if (dest == a) {
|
|
bigint_t t = {NULL, 0, 0, 0};
|
|
bigint_copy(&t, a);
|
|
r = bigint_mul_schoolbook(dest, &t, b);
|
|
bigint_free(&t);
|
|
return r;
|
|
}
|
|
if (dest == b) {
|
|
bigint_t t = {NULL, 0, 0, 0};
|
|
bigint_copy(&t, b);
|
|
r = bigint_mul_schoolbook(dest, a, &t);
|
|
bigint_free(&t);
|
|
return r;
|
|
}
|
|
memset(dest->wordv, 0, (a->length_W + b->length_W) * sizeof(bigint_word_t));
|
|
for(i = 0; i < b->length_W; ++i) {
|
|
c = 0;
|
|
for(j = 0; j < a->length_W; ++j) {
|
|
v = (bigint_wordplus_t)a->wordv[j]
|
|
* (bigint_wordplus_t)b->wordv[i];
|
|
v += (bigint_wordplus_t)dest->wordv[i + j];
|
|
v += (bigint_wordplus_t)c;
|
|
dest->wordv[i + j] = v;
|
|
c = v >> BIGINT_WORD_SIZE;
|
|
}
|
|
dest->wordv[i + j] = c;
|
|
}
|
|
|
|
dest->length_W = a->length_W + b->length_W;
|
|
dest->info &= ~BIGINT_SIGN_MASK;
|
|
dest->info |= (a->info ^ b->info) & BIGINT_SIGN_MASK;
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
* UNSAFE!!!
|
|
*/
|
|
int8_t bigint_cmp_u(const bigint_t *a, const bigint_t *b) {
|
|
int8_t r = 1;
|
|
bigint_length_t i;
|
|
if (a->length_W == 0 && b->length_W == 0) {
|
|
return 0;
|
|
}
|
|
if (b->length_W == 0) {
|
|
return 1;
|
|
}
|
|
if (a->length_W == 0) {
|
|
return -1;
|
|
}
|
|
if (a->length_W < b->length_W) {
|
|
const bigint_t *t;
|
|
t = a;
|
|
a = b;
|
|
b = t;
|
|
r = -1;
|
|
}
|
|
for (i = a->length_W - 1; i > b->length_W - 1; --i) {
|
|
if (a->wordv[i]) {
|
|
return r;
|
|
}
|
|
}
|
|
++i;
|
|
do {
|
|
--i;
|
|
if (a->wordv[i] != b->wordv[i]) {
|
|
return a->wordv[i] > b->wordv[i] ? r : -r;
|
|
}
|
|
} while (i);
|
|
return 0;
|
|
}
|
|
|
|
int8_t bigint_cmp_s(const bigint_t *a, const bigint_t *b) {
|
|
if ( bigint_get_first_set_bit(a) == (bigint_length_t)-1 &&
|
|
bigint_get_first_set_bit(b) == (bigint_length_t)-1 ) {
|
|
return 0;
|
|
}
|
|
if ((a->info & BIGINT_SIGN_MASK) ^ (b->info & BIGINT_SIGN_MASK)) {
|
|
return (a->info & BIGINT_SIGN_MASK) ? -1 : 1;
|
|
} else {
|
|
int r;
|
|
r = bigint_cmp_u(a, b);
|
|
return (a->info & BIGINT_SIGN_MASK) ? -r : r;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
* UNSAFE!!!
|
|
* a <=> b * (B ** s)
|
|
*/
|
|
int8_t bigint_cmp_scale(const bigint_t *a, const bigint_t *b, bigint_length_t s) {
|
|
bigint_length_t i;
|
|
if (s == 0) {
|
|
return bigint_cmp_u(a, b);
|
|
}
|
|
if (a->length_W == 0 && b->length_W == 0) {
|
|
return 0;
|
|
}
|
|
if (b->length_W == 0) {
|
|
return 1;
|
|
}
|
|
if (a->length_W == 0) {
|
|
return -1;
|
|
}
|
|
if (s > a->length_W) {
|
|
return -1;
|
|
}
|
|
for (i = a->length_W - 1; i > b->length_W + s - 1; --i) {
|
|
if (a->wordv[i]) {
|
|
return 1;
|
|
}
|
|
}
|
|
for (; i > s - 1; --i) {
|
|
if (a->wordv[i] != b->wordv[i + s]){
|
|
return a->wordv[i] > b->wordv[i + s] ? 1 : -1;
|
|
}
|
|
}
|
|
++i;
|
|
do {
|
|
--i;
|
|
if (a->wordv[i]) {
|
|
return 1;
|
|
}
|
|
} while (i);
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* XXXXXXXXXXXX
|
|
* \brief dest = |a| - |b| * B ** s
|
|
* Subtracts b from a and stores the result in dest.
|
|
* Signs are ignored
|
|
*/
|
|
int bigint_sub_scale(bigint_t *dest, const bigint_t *a, const bigint_t *b, bigint_length_t s) {
|
|
bigint_length_t i, j;
|
|
bigint_word_t t, c1, c2, c = 0;
|
|
int r;
|
|
#if CHECKS
|
|
if (!dest || !a || !b) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
#if CHECKS
|
|
if ((r = check_size(dest, MAX(a->length_W, b->length_W)))) {
|
|
return r;
|
|
}
|
|
|
|
#endif
|
|
j = MIN(a->length_W, b->length_W);
|
|
for (i = 0; i < j; ++i) {
|
|
t = a->wordv[i + s] - b->wordv[i];
|
|
c1 = t > a->wordv[i + s];
|
|
dest->wordv[i + s] = t - c;
|
|
c2 = dest->wordv[i + s] > t;
|
|
c = c1 | c2;
|
|
}
|
|
for (; i < a->length_W; ++i) {
|
|
t = a->wordv[i + s];
|
|
dest->wordv[i + s] = t - c;
|
|
c = dest->wordv[i + s] > t;
|
|
}
|
|
dest->length_W = a->length_W;
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
* UNSAFE!!!
|
|
*/
|
|
int bigint_adjust_length(bigint_t *a) {
|
|
#if CHECKS
|
|
if (!a) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
while (a->length_W) {
|
|
if (a->wordv[a->length_W - 1]) {
|
|
return 0;
|
|
}
|
|
a->length_W--;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
bigint_length_t bigint_get_first_set_bit(const bigint_t *a) {
|
|
bigint_length_t r;
|
|
bigint_word_t t;
|
|
if (!a) {
|
|
return (bigint_length_t)-1;
|
|
}
|
|
if (a->length_W == 0) {
|
|
return (bigint_length_t)-1;
|
|
}
|
|
r = a->length_W - 1;
|
|
while (r && a->wordv[r] == 0) {
|
|
--r;
|
|
}
|
|
t = a->wordv[r];
|
|
if (!t) {
|
|
return (bigint_length_t)-1;
|
|
}
|
|
r *= BIGINT_WORD_SIZE;
|
|
t >>= 1;
|
|
while (t) {
|
|
t >>= 1;
|
|
++r;
|
|
}
|
|
return r;
|
|
}
|
|
|
|
/*
|
|
* UNSAFE!!!
|
|
* a = q * b + r
|
|
*/
|
|
int bigint_divide(bigint_t *q, bigint_t *r, const bigint_t *a, const bigint_t *b) {
|
|
bigint_t a_ = {NULL, 0, 0, 0}, x_ = {NULL, 0, 0, 0};
|
|
bigint_length_t i, la, lb;
|
|
int ret;
|
|
#if CHECKS
|
|
if (!a || !b || (!q && !r)) {
|
|
return E_PARAM;
|
|
}
|
|
#endif
|
|
la = bigint_get_first_set_bit(a);
|
|
lb = bigint_get_first_set_bit(b);
|
|
if (lb == (bigint_length_t)-1) {
|
|
return E_VALUE;
|
|
}
|
|
if (la == (bigint_length_t)-1) {
|
|
if (q) {
|
|
q->length_W = 0;
|
|
}
|
|
if (r) {
|
|
r->length_W = 0;
|
|
}
|
|
return 0;
|
|
}
|
|
if (la < lb) {
|
|
if (q) {
|
|
q->length_W = 0;
|
|
}
|
|
if (r) {
|
|
bigint_copy(r, a);
|
|
}
|
|
return 0;
|
|
}
|
|
i = la - lb;
|
|
if (q) {
|
|
if ((ret = check_size(q, (i + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE))) {
|
|
return ret;
|
|
}
|
|
q->length_W = (i + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE;
|
|
memset(q->wordv, 0, q->allocated_W * sizeof(bigint_word_t));
|
|
}
|
|
if (r) {
|
|
if ((ret = check_size(q, (lb + BIGINT_WORD_SIZE - 1) / BIGINT_WORD_SIZE))) {
|
|
return ret;
|
|
}
|
|
}
|
|
if ((ret = bigint_copy(&a_, a))) {
|
|
return ret;
|
|
}
|
|
if ((ret = bigint_shiftleft(&x_, b, i))) {
|
|
bigint_free(&a_);
|
|
return ret;
|
|
}
|
|
#if 0
|
|
printf("DBG: x' = ");
|
|
bigint_print_hex(&x_);
|
|
printf("; b = ");
|
|
bigint_print_hex(b);
|
|
printf("; la = %d; lb = %d; i = %d\n", la, lb, i);
|
|
#endif
|
|
do {
|
|
if (bigint_cmp_u(&a_, &x_) >= 0) {
|
|
bigint_sub_u(&a_, &a_, &x_);
|
|
if (q) {
|
|
q->wordv[i / BIGINT_WORD_SIZE] |= 1 << (i % BIGINT_WORD_SIZE);
|
|
}
|
|
}
|
|
bigint_shiftright_1bit(&x_);
|
|
} while (i--);
|
|
if (r) {
|
|
bigint_copy(r, &a_);
|
|
}
|
|
bigint_free(&x_);
|
|
bigint_free(&a_);
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* UNSAFE!!!
|
|
*/
|
|
int bigint_sub_s(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
int8_t s;
|
|
int r;
|
|
if (a->length_W == 0) {
|
|
bigint_copy(dest, b);
|
|
dest->info ^= BIGINT_SIGN_MASK;
|
|
return 0;
|
|
}
|
|
if ((a->info ^ b->info) & BIGINT_SIGN_MASK) {
|
|
/* different signs */
|
|
if ((r = bigint_add_auto_u(dest, a, b))) {
|
|
return r;
|
|
}
|
|
dest->info = a->info;
|
|
} else {
|
|
s = bigint_cmp_u(a, b);
|
|
if (s >= 0) {
|
|
if (( r = bigint_sub_u(dest, a, b))) {
|
|
return r;
|
|
}
|
|
dest->info = a->info;
|
|
} else {
|
|
if (( r = bigint_sub_u(dest, b, a))) {
|
|
return r;
|
|
}
|
|
dest->info = (~a->info) & BIGINT_SIGN_MASK;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* UNSAFE!!!
|
|
*/
|
|
int bigint_add_s(bigint_t *dest, const bigint_t *a, const bigint_t *b) {
|
|
int8_t s;
|
|
int r;
|
|
if ((a->info ^ b->info) & BIGINT_SIGN_MASK) {
|
|
/* different signs */
|
|
s = bigint_cmp_u(a, b);
|
|
if (s >= 0) {
|
|
if (( r = bigint_sub_u(dest, a, b))) {
|
|
return r;
|
|
}
|
|
dest->info = a->info;
|
|
} else {
|
|
if (( r = bigint_sub_u(dest, b, a))) {
|
|
return r;
|
|
}
|
|
dest->info = (~a->info) & BIGINT_SIGN_MASK;
|
|
}
|
|
} else {
|
|
if ((r = bigint_add_auto_u(dest, a, b))) {
|
|
return r;
|
|
}
|
|
dest->info = a->info;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int8_t bigint_is_even(const bigint_t *a) {
|
|
if (!a) {
|
|
return E_VALUE;
|
|
}
|
|
if (a->length_W == 0 || (a->wordv[0] & 1) == 0) {
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int8_t bigint_is_odd(const bigint_t *a) {
|
|
if (!a) {
|
|
return E_VALUE;
|
|
}
|
|
if (a->length_W > 0 && (a->wordv[0] & 1) == 1) {
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* UNSAFE!!!
|
|
* (a, b) -> (x, y, v)
|
|
* v = gcd(a,b)
|
|
* x * a + y * b = v
|
|
*/
|
|
int bigint_gcdext(bigint_t *gcd, bigint_t *x, bigint_t *y, const bigint_t *a, const bigint_t *b) {
|
|
bigint_length_t g = 0;
|
|
bigint_t u = {NULL, 0, 0, 0}, v = {NULL, 0, 0, 0};
|
|
bigint_t x_ = {NULL, 0, 0, 0}, y_ = {NULL, 0, 0, 0};
|
|
bigint_t A = {NULL, 0, 0, 0}, B = {NULL, 0, 0, 0};
|
|
bigint_t C = {NULL, 0, 0, 0}, D = {NULL, 0, 0, 0};
|
|
int r;
|
|
if ((r = bigint_copy(&x_, a))) {
|
|
return r;
|
|
}
|
|
if ((r = bigint_copy(&y_, b))) {
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
bigint_adjust_length(&x_);
|
|
bigint_adjust_length(&y_);
|
|
if (x_.length_W == 0 || y_.length_W == 0) {
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return E_VALUE;
|
|
}
|
|
while (((x_.wordv[0] | y_.wordv[0]) & 1) == 0) {
|
|
++g;
|
|
bigint_shiftright_1bit(&x_);
|
|
bigint_shiftright_1bit(&y_);
|
|
}
|
|
if ((r = check_size(&A, 1 + (bigint_get_first_set_bit(&y_) + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE))) {
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
if ((r = check_size(&C, 1 + (bigint_get_first_set_bit(&y_) + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE))) {
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
if ((r = check_size(&B, 1 + (bigint_get_first_set_bit(&x_) + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE))) {
|
|
bigint_free(&C);
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
if ((r = check_size(&D, 1 + (bigint_get_first_set_bit(&x_) + BIGINT_WORD_SIZE) / BIGINT_WORD_SIZE))) {
|
|
bigint_free(&B);
|
|
bigint_free(&C);
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
if ((r = bigint_copy(&u, &x_))) {
|
|
bigint_free(&D);
|
|
bigint_free(&B);
|
|
bigint_free(&C);
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
if ((r = bigint_copy(&v, &y_))) {
|
|
bigint_free(&u);
|
|
bigint_free(&D);
|
|
bigint_free(&B);
|
|
bigint_free(&C);
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return r;
|
|
}
|
|
A.wordv[0] = D.wordv[0] = 1;
|
|
A.length_W = D.length_W = 1;
|
|
C.length_W = B.length_W = 0;
|
|
|
|
do {
|
|
while ((u.wordv[0] & 1) == 0) {
|
|
bigint_shiftright_1bit(&u);
|
|
if (bigint_is_odd(&A) || bigint_is_odd(&B)) {
|
|
bigint_add_s(&A, &A, &y_);
|
|
bigint_sub_s(&B, &B, &x_);
|
|
}
|
|
bigint_shiftright_1bit(&A);
|
|
bigint_shiftright_1bit(&B);
|
|
}
|
|
while ((v.wordv[0] & 1) == 0) {
|
|
bigint_shiftright_1bit(&v);
|
|
if (bigint_is_odd(&C) || bigint_is_odd(&D)) {
|
|
bigint_add_s(&C, &C, &y_);
|
|
bigint_sub_s(&D, &D, &x_);
|
|
}
|
|
bigint_shiftright_1bit(&C);
|
|
bigint_shiftright_1bit(&D);
|
|
}
|
|
if (bigint_cmp_s(&u, &v) >= 0) {
|
|
bigint_sub_s(&u, &u, &v);
|
|
bigint_sub_s(&A, &A, &C);
|
|
bigint_sub_s(&B, &B, &D);
|
|
} else {
|
|
bigint_sub_s(&v, &v, &u);
|
|
bigint_sub_s(&C, &C, &A);
|
|
bigint_sub_s(&D, &D, &B);
|
|
}
|
|
bigint_adjust_length(&u);
|
|
} while (u.length_W != 0);
|
|
if (gcd) {
|
|
bigint_shiftleft(gcd, &v, g);
|
|
}
|
|
if (x) {
|
|
bigint_copy(x, &C);
|
|
}
|
|
if (y) {
|
|
bigint_copy(y, &D);
|
|
}
|
|
bigint_free(&v);
|
|
bigint_free(&u);
|
|
bigint_free(&D);
|
|
bigint_free(&B);
|
|
bigint_free(&C);
|
|
bigint_free(&A);
|
|
bigint_free(&y_);
|
|
bigint_free(&x_);
|
|
return 0;
|
|
}
|