|
Packit |
fb9d21 |
/*
|
|
Packit |
fb9d21 |
Name: gmp_compat.c
|
|
Packit |
fb9d21 |
Purpose: Provide GMP compatiable routines for imath library
|
|
Packit |
fb9d21 |
Author: David Peixotto
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
Copyright (c) 2012 Qualcomm Innovation Center, Inc. All rights reserved.
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
Packit |
fb9d21 |
of this software and associated documentation files (the "Software"), to deal
|
|
Packit |
fb9d21 |
in the Software without restriction, including without limitation the rights
|
|
Packit |
fb9d21 |
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
Packit |
fb9d21 |
copies of the Software, and to permit persons to whom the Software is
|
|
Packit |
fb9d21 |
furnished to do so, subject to the following conditions:
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
The above copyright notice and this permission notice shall be included in
|
|
Packit |
fb9d21 |
all copies or substantial portions of the Software.
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
Packit |
fb9d21 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
Packit |
fb9d21 |
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
Packit |
fb9d21 |
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
Packit |
fb9d21 |
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
Packit |
fb9d21 |
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
|
Packit |
fb9d21 |
SOFTWARE.
|
|
Packit |
fb9d21 |
*/
|
|
Packit |
fb9d21 |
#include "gmp_compat.h"
|
|
Packit |
fb9d21 |
#include <stdlib.h>
|
|
Packit |
fb9d21 |
#include <assert.h>
|
|
Packit |
fb9d21 |
#include <ctype.h>
|
|
Packit |
fb9d21 |
#include <string.h>
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
#ifdef NDEBUG
|
|
Packit |
fb9d21 |
#define CHECK(res) (res)
|
|
Packit |
fb9d21 |
#else
|
|
Packit |
fb9d21 |
#define CHECK(res) assert(((res) == MP_OK) && "expected MP_OK")
|
|
Packit |
fb9d21 |
#endif
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/*************************************************************************
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
* Functions with direct translations
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
*************************************************************************/
|
|
Packit |
fb9d21 |
/* gmp: mpq_clear */
|
|
Packit |
fb9d21 |
void GMPQAPI(clear)(mp_rat x) {
|
|
Packit |
fb9d21 |
mp_rat_clear(x);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_cmp */
|
|
Packit |
fb9d21 |
int GMPQAPI(cmp)(mp_rat op1, mp_rat op2) {
|
|
Packit |
fb9d21 |
return mp_rat_compare(op1, op2);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_init */
|
|
Packit |
fb9d21 |
void GMPQAPI(init)(mp_rat x) {
|
|
Packit |
fb9d21 |
CHECK(mp_rat_init(x));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_mul */
|
|
Packit |
fb9d21 |
void GMPQAPI(mul)(mp_rat product, mp_rat multiplier, mp_rat multiplicand) {
|
|
Packit |
fb9d21 |
CHECK(mp_rat_mul(multiplier, multiplicand, product));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_set*/
|
|
Packit |
fb9d21 |
void GMPQAPI(set)(mp_rat rop, mp_rat op) {
|
|
Packit |
fb9d21 |
CHECK(mp_rat_copy(op, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_abs */
|
|
Packit |
fb9d21 |
void GMPZAPI(abs)(mp_int rop, mp_int op) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_abs(op, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_add */
|
|
Packit |
fb9d21 |
void GMPZAPI(add)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_add(op1, op2, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_clear */
|
|
Packit |
fb9d21 |
void GMPZAPI(clear)(mp_int x) {
|
|
Packit |
fb9d21 |
mp_int_clear(x);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_cmp_si */
|
|
Packit |
fb9d21 |
int GMPZAPI(cmp_si)(mp_int op1, long op2) {
|
|
Packit |
fb9d21 |
return mp_int_compare_value(op1, op2);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_cmpabs */
|
|
Packit |
fb9d21 |
int GMPZAPI(cmpabs)(mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
return mp_int_compare_unsigned(op1, op2);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_cmp */
|
|
Packit |
fb9d21 |
int GMPZAPI(cmp)(mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
return mp_int_compare(op1, op2);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_init */
|
|
Packit |
fb9d21 |
void GMPZAPI(init)(mp_int x) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(x));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_mul */
|
|
Packit |
fb9d21 |
void GMPZAPI(mul)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_mul(op1, op2, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_neg */
|
|
Packit |
fb9d21 |
void GMPZAPI(neg)(mp_int rop, mp_int op) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_neg(op, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_set_si */
|
|
Packit |
fb9d21 |
void GMPZAPI(set_si)(mp_int rop, long op) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_set_value(rop, op));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_set */
|
|
Packit |
fb9d21 |
void GMPZAPI(set)(mp_int rop, mp_int op) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_copy(op, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_sub */
|
|
Packit |
fb9d21 |
void GMPZAPI(sub)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_sub(op1, op2, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_swap */
|
|
Packit |
fb9d21 |
void GMPZAPI(swap)(mp_int rop1, mp_int rop2) {
|
|
Packit |
fb9d21 |
mp_int_swap(rop1, rop2);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_sgn */
|
|
Packit |
fb9d21 |
int GMPQAPI(sgn)(mp_rat op) {
|
|
Packit |
fb9d21 |
return mp_rat_compare_zero(op);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_sgn */
|
|
Packit |
fb9d21 |
int GMPZAPI(sgn)(mp_int op) {
|
|
Packit |
fb9d21 |
return mp_int_compare_zero(op);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_set_ui */
|
|
Packit |
fb9d21 |
void GMPQAPI(set_ui)(mp_rat rop, unsigned long op1, unsigned long op2) {
|
|
Packit |
fb9d21 |
CHECK(mp_rat_set_uvalue(rop, op1, op2));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_set_ui */
|
|
Packit |
fb9d21 |
void GMPZAPI(set_ui)(mp_int rop, unsigned long op) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_set_uvalue(rop, op));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_den_ref */
|
|
Packit |
fb9d21 |
mp_int GMPQAPI(denref)(mp_rat op) {
|
|
Packit |
fb9d21 |
return mp_rat_denom_ref(op);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_num_ref */
|
|
Packit |
fb9d21 |
mp_int GMPQAPI(numref)(mp_rat op) {
|
|
Packit |
fb9d21 |
return mp_rat_numer_ref(op);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_canonicalize */
|
|
Packit |
fb9d21 |
void GMPQAPI(canonicalize)(mp_rat op) {
|
|
Packit |
fb9d21 |
CHECK(mp_rat_reduce(op));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/*************************************************************************
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
* Functions that can be implemented as a combination of imath functions
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
*************************************************************************/
|
|
Packit |
fb9d21 |
/* gmp: mpz_addmul */
|
|
Packit |
fb9d21 |
/* gmp: rop = rop + (op1 * op2) */
|
|
Packit |
fb9d21 |
void GMPZAPI(addmul)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
mp_int_init(temp);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_mul(op1, op2, temp));
|
|
Packit |
fb9d21 |
CHECK(mp_int_add(rop, temp, rop));
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_divexact */
|
|
Packit |
fb9d21 |
/* gmp: only produces correct results when d divides n */
|
|
Packit |
fb9d21 |
void GMPZAPI(divexact)(mp_int q, mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, d, q, NULL));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_divisible_p */
|
|
Packit |
fb9d21 |
/* gmp: return 1 if d divides n, 0 otherwise */
|
|
Packit |
fb9d21 |
/* gmp: 0 is considered to divide 0*/
|
|
Packit |
fb9d21 |
int GMPZAPI(divisible_p)(mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
/* variables to hold remainder */
|
|
Packit |
fb9d21 |
mpz_t rz;
|
|
Packit |
fb9d21 |
mp_int r = &rz;
|
|
Packit |
fb9d21 |
int r_is_zero;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* check for n = 0, d = 0 */
|
|
Packit |
fb9d21 |
int n_is_zero = mp_int_compare_zero(n) == 0;
|
|
Packit |
fb9d21 |
int d_is_zero = mp_int_compare_zero(d) == 0;
|
|
Packit |
fb9d21 |
if (n_is_zero && d_is_zero)
|
|
Packit |
fb9d21 |
return 1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* return true if remainder is 0 */
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(r));
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, d, NULL, r));
|
|
Packit |
fb9d21 |
r_is_zero = mp_int_compare_zero(r) == 0;
|
|
Packit |
fb9d21 |
mp_int_clear(r);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return r_is_zero;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_submul */
|
|
Packit |
fb9d21 |
/* gmp: rop = rop - (op1 * op2) */
|
|
Packit |
fb9d21 |
void GMPZAPI(submul)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
mp_int_init(temp);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_mul(op1, op2, temp));
|
|
Packit |
fb9d21 |
CHECK(mp_int_sub(rop, temp, rop));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_add_ui */
|
|
Packit |
fb9d21 |
void GMPZAPI(add_ui)(mp_int rop, mp_int op1, unsigned long op2) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, op2));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_add(op1, temp, rop));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_divexact_ui */
|
|
Packit |
fb9d21 |
/* gmp: only produces correct results when d divides n */
|
|
Packit |
fb9d21 |
void GMPZAPI(divexact_ui)(mp_int q, mp_int n, unsigned long d) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, d));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, temp, q, NULL));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_mul_ui */
|
|
Packit |
fb9d21 |
void GMPZAPI(mul_ui)(mp_int rop, mp_int op1, unsigned long op2) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, op2));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_mul(op1, temp, rop));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_pow_ui */
|
|
Packit |
fb9d21 |
/* gmp: 0^0 = 1 */
|
|
Packit |
fb9d21 |
void GMPZAPI(pow_ui)(mp_int rop, mp_int base, unsigned long exp) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* check for 0^0 */
|
|
Packit |
fb9d21 |
if (exp == 0 && mp_int_compare_zero(base) == 0) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_set_value(rop, 1));
|
|
Packit |
fb9d21 |
return;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* rop = base^exp */
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, exp));
|
|
Packit |
fb9d21 |
CHECK(mp_int_expt_full(base, temp, rop));
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_sub_ui */
|
|
Packit |
fb9d21 |
void GMPZAPI(sub_ui)(mp_int rop, mp_int op1, unsigned long op2) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, op2));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_sub(op1, temp, rop));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/*************************************************************************
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
* Functions with different behavior in corner cases
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
*************************************************************************/
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_gcd */
|
|
Packit |
fb9d21 |
void GMPZAPI(gcd)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
int op1_is_zero = mp_int_compare_zero(op1) == 0;
|
|
Packit |
fb9d21 |
int op2_is_zero = mp_int_compare_zero(op2) == 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
if (op1_is_zero && op2_is_zero) {
|
|
Packit |
fb9d21 |
mp_int_zero(rop);
|
|
Packit |
fb9d21 |
return;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_gcd(op1, op2, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_get_str */
|
|
Packit |
fb9d21 |
char* GMPZAPI(get_str)(char *str, int radix, mp_int op) {
|
|
Packit |
fb9d21 |
int i, r, len;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Support negative radix like gmp */
|
|
Packit |
fb9d21 |
r = radix;
|
|
Packit |
fb9d21 |
if (r < 0)
|
|
Packit |
fb9d21 |
r = -r;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Compute the length of the string needed to hold the int */
|
|
Packit |
fb9d21 |
len = mp_int_string_len(op, r);
|
|
Packit |
fb9d21 |
if (str == NULL) {
|
|
Packit |
fb9d21 |
str = malloc(len);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Convert to string using imath function */
|
|
Packit |
fb9d21 |
CHECK(mp_int_to_string(op, r, str, len));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Change case to match gmp */
|
|
Packit |
fb9d21 |
for (i = 0; i < len; i++)
|
|
Packit |
fb9d21 |
if (radix < 0)
|
|
Packit |
fb9d21 |
str[i] = toupper(str[i]);
|
|
Packit |
fb9d21 |
else
|
|
Packit |
fb9d21 |
str[i] = tolower(str[i]);
|
|
Packit |
fb9d21 |
return str;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_get_str */
|
|
Packit |
fb9d21 |
char* GMPQAPI(get_str)(char *str, int radix, mp_rat op) {
|
|
Packit |
fb9d21 |
int i, r, len;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Only print numerator if it is a whole number */
|
|
Packit |
fb9d21 |
if (mp_int_compare_value(mp_rat_denom_ref(op), 1) == 0)
|
|
Packit |
fb9d21 |
return GMPZAPI(get_str)(str, radix, mp_rat_numer_ref(op));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Support negative radix like gmp */
|
|
Packit |
fb9d21 |
r = radix;
|
|
Packit |
fb9d21 |
if (r < 0)
|
|
Packit |
fb9d21 |
r = -r;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Compute the length of the string needed to hold the int */
|
|
Packit |
fb9d21 |
len = mp_rat_string_len(op, r);
|
|
Packit |
fb9d21 |
if (str == NULL) {
|
|
Packit |
fb9d21 |
str = malloc(len);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Convert to string using imath function */
|
|
Packit |
fb9d21 |
CHECK(mp_rat_to_string(op, r, str, len));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Change case to match gmp */
|
|
Packit |
fb9d21 |
for (i = 0; i < len; i++)
|
|
Packit |
fb9d21 |
if (radix < 0)
|
|
Packit |
fb9d21 |
str[i] = toupper(str[i]);
|
|
Packit |
fb9d21 |
else
|
|
Packit |
fb9d21 |
str[i] = tolower(str[i]);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return str;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_set_str */
|
|
Packit |
fb9d21 |
int GMPZAPI(set_str)(mp_int rop, char *str, int base) {
|
|
Packit |
fb9d21 |
mp_result res = mp_int_read_string(rop, base, str);
|
|
Packit |
fb9d21 |
return ((res == MP_OK) ? 0 : -1);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpq_set_str */
|
|
Packit |
fb9d21 |
int GMPQAPI(set_str)(mp_rat rop, char *s, int base) {
|
|
Packit |
fb9d21 |
char *slash;
|
|
Packit |
fb9d21 |
char *str;
|
|
Packit |
fb9d21 |
mp_result resN;
|
|
Packit |
fb9d21 |
mp_result resD;
|
|
Packit |
fb9d21 |
int res = 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Copy string to temporary storage so we can modify it below */
|
|
Packit |
fb9d21 |
str = malloc(strlen(s)+1);
|
|
Packit |
fb9d21 |
strcpy(str, s);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Properly format the string as an int by terminating at the / */
|
|
Packit |
fb9d21 |
slash = strchr(str, '/');
|
|
Packit |
fb9d21 |
if (slash)
|
|
Packit |
fb9d21 |
*slash = '\0';
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Parse numerator */
|
|
Packit |
fb9d21 |
resN = mp_int_read_string(mp_rat_numer_ref(rop), base, str);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Parse denomenator if given or set to 1 if not */
|
|
Packit |
fb9d21 |
if (slash)
|
|
Packit |
fb9d21 |
resD = mp_int_read_string(mp_rat_denom_ref(rop), base, slash+1);
|
|
Packit |
fb9d21 |
else
|
|
Packit |
fb9d21 |
resD = mp_int_set_uvalue(mp_rat_denom_ref(rop), 1);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Return failure if either parse failed */
|
|
Packit |
fb9d21 |
if (resN != MP_OK || resD != MP_OK)
|
|
Packit |
fb9d21 |
res = -1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
free(str);
|
|
Packit |
fb9d21 |
return res;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
static unsigned long get_long_bits(mp_int op) {
|
|
Packit |
fb9d21 |
/* Deal with integer that does not fit into unsigned long. We want to grab
|
|
Packit |
fb9d21 |
* the least significant digits that will fit into the long. Read the digits
|
|
Packit |
fb9d21 |
* into the long starting at the most significant digit that fits into a
|
|
Packit |
fb9d21 |
* long. The long is shifted over by MP_DIGIT_BIT before each digit is added.
|
|
Packit |
fb9d21 |
* The shift is decomposed into two steps to follow the patten used in the
|
|
Packit |
fb9d21 |
* rest of the imath library. The two step shift is used to accomedate
|
|
Packit |
fb9d21 |
* architectures that don't deal well with 32-bit shifts. */
|
|
Packit |
fb9d21 |
mp_size num_digits_in_long = sizeof(unsigned long) / sizeof(mp_digit);
|
|
Packit |
fb9d21 |
mp_digit *digits = MP_DIGITS(op);
|
|
Packit |
fb9d21 |
unsigned long out = 0;
|
|
Packit |
fb9d21 |
int i;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
for (i = num_digits_in_long - 1; i >= 0; i--) {
|
|
Packit |
fb9d21 |
out <<= (MP_DIGIT_BIT/2);
|
|
Packit |
fb9d21 |
out <<= (MP_DIGIT_BIT/2);
|
|
Packit |
fb9d21 |
out |= digits[i];
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return out;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_get_ui */
|
|
Packit |
fb9d21 |
unsigned long GMPZAPI(get_ui)(mp_int op) {
|
|
Packit |
fb9d21 |
unsigned long out;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Try a standard conversion that fits into an unsigned long */
|
|
Packit |
fb9d21 |
mp_result res = mp_int_to_uint(op, &out;;
|
|
Packit |
fb9d21 |
if (res == MP_OK)
|
|
Packit |
fb9d21 |
return out;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Abort the try if we don't have a range error in the conversion.
|
|
Packit |
fb9d21 |
* The range error indicates that the value cannot fit into a long. */
|
|
Packit |
fb9d21 |
CHECK(res == MP_RANGE ? MP_OK : MP_RANGE);
|
|
Packit |
fb9d21 |
if (res != MP_RANGE)
|
|
Packit |
fb9d21 |
return 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return get_long_bits(op);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_get_si */
|
|
Packit |
fb9d21 |
long GMPZAPI(get_si)(mp_int op) {
|
|
Packit |
fb9d21 |
long out;
|
|
Packit |
fb9d21 |
unsigned long uout;
|
|
Packit |
fb9d21 |
int long_msb;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Try a standard conversion that fits into a long */
|
|
Packit |
fb9d21 |
mp_result res = mp_int_to_int(op, &out;;
|
|
Packit |
fb9d21 |
if (res == MP_OK)
|
|
Packit |
fb9d21 |
return out;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Abort the try if we don't have a range error in the conversion.
|
|
Packit |
fb9d21 |
* The range error indicates that the value cannot fit into a long. */
|
|
Packit |
fb9d21 |
CHECK(res == MP_RANGE ? MP_OK : MP_RANGE);
|
|
Packit |
fb9d21 |
if (res != MP_RANGE)
|
|
Packit |
fb9d21 |
return 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* get least significant bits into an unsigned long */
|
|
Packit |
fb9d21 |
uout = get_long_bits(op);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* clear the top bit */
|
|
Packit |
fb9d21 |
long_msb = (sizeof(unsigned long) * 8) - 1;
|
|
Packit |
fb9d21 |
uout &= (~(1UL << long_msb));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* convert to negative if needed based on sign of op */
|
|
Packit |
fb9d21 |
if (MP_SIGN(op) == MP_NEG)
|
|
Packit |
fb9d21 |
uout = 0 - uout;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
out = (long) uout;
|
|
Packit |
fb9d21 |
return out;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_lcm */
|
|
Packit |
fb9d21 |
void GMPZAPI(lcm)(mp_int rop, mp_int op1, mp_int op2) {
|
|
Packit |
fb9d21 |
int op1_is_zero = mp_int_compare_zero(op1) == 0;
|
|
Packit |
fb9d21 |
int op2_is_zero = mp_int_compare_zero(op2) == 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
if (op1_is_zero || op2_is_zero) {
|
|
Packit |
fb9d21 |
mp_int_zero(rop);
|
|
Packit |
fb9d21 |
return;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
CHECK(mp_int_lcm(op1, op2, rop));
|
|
Packit |
fb9d21 |
CHECK(mp_int_abs(rop, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_mul_2exp */
|
|
Packit |
fb9d21 |
/* gmp: allow big values for op2 when op1 == 0 */
|
|
Packit |
fb9d21 |
void GMPZAPI(mul_2exp)(mp_int rop, mp_int op1, unsigned long op2) {
|
|
Packit |
fb9d21 |
if (mp_int_compare_zero(op1) == 0)
|
|
Packit |
fb9d21 |
mp_int_zero(rop);
|
|
Packit |
fb9d21 |
else
|
|
Packit |
fb9d21 |
CHECK(mp_int_mul_pow2(op1, op2, rop));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/*************************************************************************
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
* Functions needing expanded functionality
|
|
Packit |
fb9d21 |
*
|
|
Packit |
fb9d21 |
*************************************************************************/
|
|
Packit |
fb9d21 |
/* [Note]Overview of division implementation
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
All division operations (N / D) compute q and r such that
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
N = q * D + r, with 0 <= abs(r) < abs(d)
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
The q and r values are not uniquely specified by N and D. To specify which q
|
|
Packit |
fb9d21 |
and r values should be used, GMP implements three different rounding modes
|
|
Packit |
fb9d21 |
for integer division:
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
ceiling - round q twords +infinity, r has opposite sign as d
|
|
Packit |
fb9d21 |
floor - round q twords -infinity, r has same sign as d
|
|
Packit |
fb9d21 |
truncate - round q twords zero, r has same sign as n
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
The imath library only supports truncate as a rounding mode. We need to
|
|
Packit |
fb9d21 |
implement the other rounding modes in terms of truncating division. We first
|
|
Packit |
fb9d21 |
perform the division in trucate mode and then adjust q accordingly. Once we
|
|
Packit |
fb9d21 |
know q, we can easily compute the correct r according the the formula above
|
|
Packit |
fb9d21 |
by computing:
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
r = N - q * D
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
The main task is to compute q. We can compute the correct q from a trucated
|
|
Packit |
fb9d21 |
version as follows.
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
For ceiling rounding mode, if q is less than 0 then the truncated rounding
|
|
Packit |
fb9d21 |
mode is the same as the ceiling rounding mode. If q is greater than zero
|
|
Packit |
fb9d21 |
then we need to round q up by one because the truncated version was rounded
|
|
Packit |
fb9d21 |
down to zero. If q equals zero then check to see if the result of the
|
|
Packit |
fb9d21 |
divison is positive. A positive result needs to increment q to one.
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
For floor rounding mode, if q is greater than 0 then the trucated rounding
|
|
Packit |
fb9d21 |
mode is the same as the floor rounding mode. If q is less than zero then we
|
|
Packit |
fb9d21 |
need to round q down by one because the trucated mode rounded q up by one
|
|
Packit |
fb9d21 |
twords zero. If q is zero then we need to check to see if the result of the
|
|
Packit |
fb9d21 |
division is negative. A negative result needs to decrement q to negative
|
|
Packit |
fb9d21 |
one.
|
|
Packit |
fb9d21 |
*/
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_cdiv_q */
|
|
Packit |
fb9d21 |
void GMPZAPI(cdiv_q)(mp_int q, mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
mpz_t rz;
|
|
Packit |
fb9d21 |
mp_int r = &rz;
|
|
Packit |
fb9d21 |
int qsign, rsign, nsign, dsign;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(r));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* save signs before division because q can alias with n or d */
|
|
Packit |
fb9d21 |
nsign = mp_int_compare_zero(n);
|
|
Packit |
fb9d21 |
dsign = mp_int_compare_zero(d);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* truncating division */
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, d, q, r));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* see: [Note]Overview of division implementation */
|
|
Packit |
fb9d21 |
qsign = mp_int_compare_zero(q);
|
|
Packit |
fb9d21 |
rsign = mp_int_compare_zero(r);
|
|
Packit |
fb9d21 |
if (qsign > 0) { /* q > 0 */
|
|
Packit |
fb9d21 |
if (rsign != 0) { /* r != 0 */
|
|
Packit |
fb9d21 |
CHECK(mp_int_add_value(q, 1, q));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
else if (qsign == 0) { /* q == 0 */
|
|
Packit |
fb9d21 |
if (rsign != 0) { /* r != 0 */
|
|
Packit |
fb9d21 |
if ((nsign > 0 && dsign > 0) || (nsign < 0 && dsign < 0)) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_set_value(q, 1));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
mp_int_clear(r);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_fdiv_q */
|
|
Packit |
fb9d21 |
void GMPZAPI(fdiv_q)(mp_int q, mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
mpz_t rz;
|
|
Packit |
fb9d21 |
mp_int r = &rz;
|
|
Packit |
fb9d21 |
int qsign, rsign, nsign, dsign;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(r));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* save signs before division because q can alias with n or d */
|
|
Packit |
fb9d21 |
nsign = mp_int_compare_zero(n);
|
|
Packit |
fb9d21 |
dsign = mp_int_compare_zero(d);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* truncating division */
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, d, q, r));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* see: [Note]Overview of division implementation */
|
|
Packit |
fb9d21 |
qsign = mp_int_compare_zero(q);
|
|
Packit |
fb9d21 |
rsign = mp_int_compare_zero(r);
|
|
Packit |
fb9d21 |
if (qsign < 0) { /* q < 0 */
|
|
Packit |
fb9d21 |
if (rsign != 0) { /* r != 0 */
|
|
Packit |
fb9d21 |
CHECK(mp_int_sub_value(q, 1, q));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
else if (qsign == 0) { /* q == 0 */
|
|
Packit |
fb9d21 |
if (rsign != 0) { /* r != 0 */
|
|
Packit |
fb9d21 |
if ((nsign < 0 && dsign > 0) || (nsign > 0 && dsign < 0)) {
|
|
Packit |
fb9d21 |
CHECK(mp_int_set_value(q, -1));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
mp_int_clear(r);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_fdiv_r */
|
|
Packit |
fb9d21 |
void GMPZAPI(fdiv_r)(mp_int r, mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
mpz_t qz;
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mpz_t orig_dz;
|
|
Packit |
fb9d21 |
mpz_t orig_nz;
|
|
Packit |
fb9d21 |
mp_int q = &qz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
mp_int orig_d = &orig_dz;
|
|
Packit |
fb9d21 |
mp_int orig_n = &orig_nz;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(q));
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(temp));
|
|
Packit |
fb9d21 |
/* Make a copy of n in case n and d in case they overlap with q */
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_copy(orig_d, d));
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_copy(orig_n, n));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* floor division */
|
|
Packit |
fb9d21 |
GMPZAPI(fdiv_q)(q, n, d);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* see: [Note]Overview of division implementation */
|
|
Packit |
fb9d21 |
/* n = q * d + r ==> r = n - q * d */
|
|
Packit |
fb9d21 |
mp_int_mul(q, orig_d, temp);
|
|
Packit |
fb9d21 |
mp_int_sub(orig_n, temp, r);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(q);
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
mp_int_clear(orig_d);
|
|
Packit |
fb9d21 |
mp_int_clear(orig_n);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_tdiv_q */
|
|
Packit |
fb9d21 |
void GMPZAPI(tdiv_q)(mp_int q, mp_int n, mp_int d) {
|
|
Packit |
fb9d21 |
/* truncating division*/
|
|
Packit |
fb9d21 |
CHECK(mp_int_div(n, d, q, NULL));
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_fdiv_q_ui */
|
|
Packit |
fb9d21 |
unsigned long GMPZAPI(fdiv_q_ui)(mp_int q, mp_int n, unsigned long d) {
|
|
Packit |
fb9d21 |
mpz_t tempz;
|
|
Packit |
fb9d21 |
mp_int temp = &tempz;
|
|
Packit |
fb9d21 |
mpz_t rz;
|
|
Packit |
fb9d21 |
mp_int r = &rz;
|
|
Packit |
fb9d21 |
mpz_t orig_nz;
|
|
Packit |
fb9d21 |
mp_int orig_n = &orig_nz;
|
|
Packit |
fb9d21 |
unsigned long rl;
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_uvalue(temp, d));
|
|
Packit |
fb9d21 |
CHECK(mp_int_init(r));
|
|
Packit |
fb9d21 |
/* Make a copy of n in case n and q overlap */
|
|
Packit |
fb9d21 |
CHECK(mp_int_init_copy(orig_n, n));
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* use floor division mode to compute q and r */
|
|
Packit |
fb9d21 |
GMPZAPI(fdiv_q)(q, n, temp);
|
|
Packit |
fb9d21 |
GMPZAPI(fdiv_r)(r, orig_n, temp);
|
|
Packit |
fb9d21 |
CHECK(mp_int_to_uint(r, &rl);;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
mp_int_clear(temp);
|
|
Packit |
fb9d21 |
mp_int_clear(r);
|
|
Packit |
fb9d21 |
mp_int_clear(orig_n);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return rl;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_export */
|
|
Packit |
fb9d21 |
void* GMPZAPI(export)(void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, mp_int op) {
|
|
Packit |
fb9d21 |
int i;
|
|
Packit |
fb9d21 |
int num_used_bytes;
|
|
Packit |
fb9d21 |
size_t num_words, num_missing_bytes;
|
|
Packit |
fb9d21 |
unsigned char* dst;
|
|
Packit |
fb9d21 |
unsigned char* src;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* We do not have a complete implementation. Assert to ensure our
|
|
Packit |
fb9d21 |
* restrictions are in place, We do not support big endian output, but do not
|
|
Packit |
fb9d21 |
* check that native endian is little endian. */
|
|
Packit |
fb9d21 |
assert(nails == 0 && "Do not support non-full words");
|
|
Packit |
fb9d21 |
assert((endian == 0 || endian == -1) && "Do not support big endian");
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* The gmp API requires that order must be -1 or 1.
|
|
Packit |
fb9d21 |
Not sure how gmp behaves when order is not 1 or -1, so force all non-one
|
|
Packit |
fb9d21 |
values to -1 for now. */
|
|
Packit |
fb9d21 |
if (order != 1) order = -1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Test for zero */
|
|
Packit |
fb9d21 |
if (mp_int_compare_zero(op) == 0) {
|
|
Packit |
fb9d21 |
if (countp)
|
|
Packit |
fb9d21 |
*countp = 0;
|
|
Packit |
fb9d21 |
return rop;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Calculate how many words we need */
|
|
Packit |
fb9d21 |
num_used_bytes = mp_int_unsigned_len(op);
|
|
Packit |
fb9d21 |
num_words = (num_used_bytes + (size-1)) / size; /* ceil division */
|
|
Packit |
fb9d21 |
assert(num_used_bytes > 0);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Check to see if we will have missing bytes in the last word.
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
Missing bytes can only occur when the size of words we output is
|
|
Packit |
fb9d21 |
greater than the size of words used internally by imath. The number of
|
|
Packit |
fb9d21 |
missing bytes is the number of bytes needed to fill out the last word. If
|
|
Packit |
fb9d21 |
this number is greater than the size of a single mp_digit, then we need to
|
|
Packit |
fb9d21 |
pad the word with extra zeros. Otherwise, the missing bytes can be filled
|
|
Packit |
fb9d21 |
directly from the zeros in the last digit in the number.
|
|
Packit |
fb9d21 |
*/
|
|
Packit |
fb9d21 |
num_missing_bytes = (size * num_words) - num_used_bytes;
|
|
Packit |
fb9d21 |
assert(num_missing_bytes < size);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Allocate space for the result if needed */
|
|
Packit |
fb9d21 |
if (rop == NULL) {
|
|
Packit |
fb9d21 |
rop = malloc(num_words * size);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Initialize dst and src pointers */
|
|
Packit |
fb9d21 |
dst = (unsigned char *)rop;
|
|
Packit |
fb9d21 |
src = (unsigned char *)MP_DIGITS(op);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Most significant word first */
|
|
Packit |
fb9d21 |
if (order == 1) {
|
|
Packit |
fb9d21 |
size_t words_written = 0;
|
|
Packit |
fb9d21 |
src += (num_words-1) * size;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Handle write of first word specially */
|
|
Packit |
fb9d21 |
for (i = 0; i < size - num_missing_bytes; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
for (; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = 0;
|
|
Packit |
fb9d21 |
dst += size;
|
|
Packit |
fb9d21 |
src -= size;
|
|
Packit |
fb9d21 |
words_written++;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
for (; words_written < num_words; words_written++) {
|
|
Packit |
fb9d21 |
for (i = 0; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
dst += size;
|
|
Packit |
fb9d21 |
src -= size;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
/* Least significant word first */
|
|
Packit |
fb9d21 |
else {
|
|
Packit |
fb9d21 |
size_t words_written = 0;
|
|
Packit |
fb9d21 |
for (; words_written < num_words - 1; words_written++) {
|
|
Packit |
fb9d21 |
for (i = 0; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
dst += size;
|
|
Packit |
fb9d21 |
src += size;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Handle write of last word specially */
|
|
Packit |
fb9d21 |
for (i = 0; i < size - num_missing_bytes; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
for (; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = 0;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
if (countp)
|
|
Packit |
fb9d21 |
*countp = num_words;
|
|
Packit |
fb9d21 |
return rop;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_import */
|
|
Packit |
fb9d21 |
void GMPZAPI(import)(mp_int rop, size_t count, int order, size_t size, int endian, size_t nails, const void* op) {
|
|
Packit |
fb9d21 |
mpz_t tmpz;
|
|
Packit |
fb9d21 |
mp_int tmp = &tmpz;
|
|
Packit |
fb9d21 |
size_t total_size;
|
|
Packit |
fb9d21 |
size_t num_digits;
|
|
Packit |
fb9d21 |
const char *src;
|
|
Packit |
fb9d21 |
char *dst;
|
|
Packit |
fb9d21 |
int i;
|
|
Packit |
fb9d21 |
if (count == 0 || op == NULL)
|
|
Packit |
fb9d21 |
return;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* We do not have a complete implementation. Assert to ensure our
|
|
Packit |
fb9d21 |
* restrictions are in place, We do not support big endian output, but do not
|
|
Packit |
fb9d21 |
* check that native endian is little endian. */
|
|
Packit |
fb9d21 |
assert(nails == 0 && "Do not support non-full words");
|
|
Packit |
fb9d21 |
assert((endian == 0 || endian == -1) && "Do not support big endian");
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Compute number of needed digits by ceil division */
|
|
Packit |
fb9d21 |
total_size = count * size;
|
|
Packit |
fb9d21 |
num_digits = (total_size + sizeof(mp_digit) - 1) / sizeof(mp_digit);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Init temporary */
|
|
Packit |
fb9d21 |
mp_int_init_size(tmp, num_digits);
|
|
Packit |
fb9d21 |
for (i = 0; i < num_digits; i++)
|
|
Packit |
fb9d21 |
tmp->digits[i] = 0;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Copy bytes */
|
|
Packit |
fb9d21 |
src = (const char *) op;
|
|
Packit |
fb9d21 |
dst = (char *)MP_DIGITS(tmp);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Most significant word is first */
|
|
Packit |
fb9d21 |
if (order == 1) {
|
|
Packit |
fb9d21 |
size_t word;
|
|
Packit |
fb9d21 |
dst += (count - 1) * size;
|
|
Packit |
fb9d21 |
for (word = 0; word < count; word++) {
|
|
Packit |
fb9d21 |
for (i = 0; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
dst -= size;
|
|
Packit |
fb9d21 |
src += size;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
/* Least significant word is first */
|
|
Packit |
fb9d21 |
else {
|
|
Packit |
fb9d21 |
size_t word;
|
|
Packit |
fb9d21 |
for (word = 0; word < count; word++) {
|
|
Packit |
fb9d21 |
for (i = 0; i < size; i++)
|
|
Packit |
fb9d21 |
dst[i] = src[i];
|
|
Packit |
fb9d21 |
dst += size;
|
|
Packit |
fb9d21 |
src += size;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
MP_USED(tmp) = num_digits;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Remove leading zeros from number */
|
|
Packit |
fb9d21 |
{
|
|
Packit |
fb9d21 |
mp_size uz_ = MP_USED(tmp);
|
|
Packit |
fb9d21 |
mp_digit *dz_ = MP_DIGITS(tmp) + uz_ -1;
|
|
Packit |
fb9d21 |
while (uz_ > 1 && (*dz_-- == 0))
|
|
Packit |
fb9d21 |
--uz_;
|
|
Packit |
fb9d21 |
MP_USED(tmp) = uz_;
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Copy to destination */
|
|
Packit |
fb9d21 |
mp_int_copy(tmp, rop);
|
|
Packit |
fb9d21 |
}
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* gmp: mpz_sizeinbase */
|
|
Packit |
fb9d21 |
size_t GMPZAPI(sizeinbase)(mp_int op, int base) {
|
|
Packit |
fb9d21 |
mp_result res;
|
|
Packit |
fb9d21 |
size_t size;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* If op == 0, return 1 */
|
|
Packit |
fb9d21 |
if (mp_int_compare_zero(op) == 0)
|
|
Packit |
fb9d21 |
return 1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Compute string length in base */
|
|
Packit |
fb9d21 |
res = mp_int_string_len(op, base);
|
|
Packit |
fb9d21 |
CHECK((res > 0) == MP_OK);
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* Now adjust the final size by getting rid of string artifacts */
|
|
Packit |
fb9d21 |
size = res;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* subtract one for the null terminator */
|
|
Packit |
fb9d21 |
size -= 1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
/* subtract one for the negative sign */
|
|
Packit |
fb9d21 |
if (mp_int_compare_zero(op) < 0)
|
|
Packit |
fb9d21 |
size -= 1;
|
|
Packit |
fb9d21 |
|
|
Packit |
fb9d21 |
return size;
|
|
Packit |
fb9d21 |
}
|