/* Name: gmp_compat.c Purpose: Provide GMP compatiable routines for imath library Author: David Peixotto Copyright (c) 2012 Qualcomm Innovation Center, Inc. All rights reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #include "gmp_compat.h" #include <assert.h> #include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #if defined(_MSC_VER) #include <BaseTsd.h> typedef SSIZE_T ssize_t; #else #include <sys/types.h> #endif #ifdef NDEBUG #define CHECK(res) … #else #define CHECK … #endif /* *(signed char *)&endian_test will thus either be: * 0b00000001 = 1 on big-endian * 0b11111111 = -1 on little-endian */ static const uint16_t endian_test = …; #define HOST_ENDIAN … /************************************************************************* * * Functions with direct translations * *************************************************************************/ /* gmp: mpq_clear */ void GMPQAPI(clear)(mp_rat x) { … } /* gmp: mpq_cmp */ int GMPQAPI(cmp)(mp_rat op1, mp_rat op2) { … } /* gmp: mpq_init */ void GMPQAPI(init)(mp_rat x) { … } /* gmp: mpq_mul */ void GMPQAPI(mul)(mp_rat product, mp_rat multiplier, mp_rat multiplicand) { … } /* gmp: mpq_set */ void GMPQAPI(set)(mp_rat rop, mp_rat op) { … } /* gmp: mpz_abs */ void GMPZAPI(abs)(mp_int rop, mp_int op) { … } /* gmp: mpz_add */ void GMPZAPI(add)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_clear */ void GMPZAPI(clear)(mp_int x) { … } /* gmp: mpz_cmp_si */ int GMPZAPI(cmp_si)(mp_int op1, long op2) { … } /* gmp: mpz_cmpabs */ int GMPZAPI(cmpabs)(mp_int op1, mp_int op2) { … } /* gmp: mpz_cmp */ int GMPZAPI(cmp)(mp_int op1, mp_int op2) { … } /* gmp: mpz_init */ void GMPZAPI(init)(mp_int x) { … } /* gmp: mpz_mul */ void GMPZAPI(mul)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_neg */ void GMPZAPI(neg)(mp_int rop, mp_int op) { … } /* gmp: mpz_set_si */ void GMPZAPI(set_si)(mp_int rop, long op) { … } /* gmp: mpz_set */ void GMPZAPI(set)(mp_int rop, mp_int op) { … } /* gmp: mpz_sub */ void GMPZAPI(sub)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_swap */ void GMPZAPI(swap)(mp_int rop1, mp_int rop2) { … } /* gmp: mpq_sgn */ int GMPQAPI(sgn)(mp_rat op) { … } /* gmp: mpz_sgn */ int GMPZAPI(sgn)(mp_int op) { … } /* gmp: mpq_set_ui */ void GMPQAPI(set_ui)(mp_rat rop, unsigned long op1, unsigned long op2) { … } /* gmp: mpz_set_ui */ void GMPZAPI(set_ui)(mp_int rop, unsigned long op) { … } /* gmp: mpq_den_ref */ mp_int GMPQAPI(denref)(mp_rat op) { … } /* gmp: mpq_num_ref */ mp_int GMPQAPI(numref)(mp_rat op) { … } /* gmp: mpq_canonicalize */ void GMPQAPI(canonicalize)(mp_rat op) { … } /* * Functions that can be implemented as a combination of imath functions */ /* gmp: mpz_addmul */ /* gmp: rop = rop + (op1 * op2) */ void GMPZAPI(addmul)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_divexact */ /* gmp: only produces correct results when d divides n */ void GMPZAPI(divexact)(mp_int q, mp_int n, mp_int d) { … } /* gmp: mpz_divisible_p */ /* gmp: return 1 if d divides n, 0 otherwise */ /* gmp: 0 is considered to divide only 0 */ int GMPZAPI(divisible_p)(mp_int n, mp_int d) { … } /* gmp: mpz_submul */ /* gmp: rop = rop - (op1 * op2) */ void GMPZAPI(submul)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_add_ui */ void GMPZAPI(add_ui)(mp_int rop, mp_int op1, unsigned long op2) { … } /* gmp: mpz_divexact_ui */ /* gmp: only produces correct results when d divides n */ void GMPZAPI(divexact_ui)(mp_int q, mp_int n, unsigned long d) { … } /* gmp: mpz_mul_ui */ void GMPZAPI(mul_ui)(mp_int rop, mp_int op1, unsigned long op2) { … } /* gmp: mpz_pow_ui */ /* gmp: 0^0 = 1 */ void GMPZAPI(pow_ui)(mp_int rop, mp_int base, unsigned long exp) { … } /* gmp: mpz_sub_ui */ void GMPZAPI(sub_ui)(mp_int rop, mp_int op1, unsigned long op2) { … } /************************************************************************* * * Functions with different behavior in corner cases * *************************************************************************/ /* gmp: mpz_gcd */ void GMPZAPI(gcd)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_get_str */ char *GMPZAPI(get_str)(char *str, int radix, mp_int op) { … } /* gmp: mpq_get_str */ char *GMPQAPI(get_str)(char *str, int radix, mp_rat op) { … } /* gmp: mpz_set_str */ int GMPZAPI(set_str)(mp_int rop, char *str, int base) { … } /* gmp: mpq_set_str */ int GMPQAPI(set_str)(mp_rat rop, char *s, int base) { … } static unsigned long get_long_bits(mp_int op) { … } /* gmp: mpz_get_ui */ unsigned long GMPZAPI(get_ui)(mp_int op) { … } /* gmp: mpz_get_si */ long GMPZAPI(get_si)(mp_int op) { … } /* gmp: mpz_lcm */ void GMPZAPI(lcm)(mp_int rop, mp_int op1, mp_int op2) { … } /* gmp: mpz_mul_2exp */ /* gmp: allow big values for op2 when op1 == 0 */ void GMPZAPI(mul_2exp)(mp_int rop, mp_int op1, unsigned long op2) { … } /* * Functions needing expanded functionality */ /* [Note]Overview of division implementation All division operations (N / D) compute q and r such that N = q * D + r, with 0 <= abs(r) < abs(d) The q and r values are not uniquely specified by N and D. To specify which q and r values should be used, GMP implements three different rounding modes for integer division: ceiling - round q twords +infinity, r has opposite sign as d floor - round q twords -infinity, r has same sign as d truncate - round q twords zero, r has same sign as n The imath library only supports truncate as a rounding mode. We need to implement the other rounding modes in terms of truncating division. We first perform the division in trucate mode and then adjust q accordingly. Once we know q, we can easily compute the correct r according the the formula above by computing: r = N - q * D The main task is to compute q. We can compute the correct q from a trucated version as follows. For ceiling rounding mode, if q is less than 0 then the truncated rounding mode is the same as the ceiling rounding mode. If q is greater than zero then we need to round q up by one because the truncated version was rounded down to zero. If q equals zero then check to see if the result of the divison is positive. A positive result needs to increment q to one. For floor rounding mode, if q is greater than 0 then the trucated rounding mode is the same as the floor rounding mode. If q is less than zero then we need to round q down by one because the trucated mode rounded q up by one twords zero. If q is zero then we need to check to see if the result of the division is negative. A negative result needs to decrement q to negative one. */ /* gmp: mpz_cdiv_q */ void GMPZAPI(cdiv_q)(mp_int q, mp_int n, mp_int d) { … } /* gmp: mpz_fdiv_q */ void GMPZAPI(fdiv_q)(mp_int q, mp_int n, mp_int d) { … } /* gmp: mpz_fdiv_r */ void GMPZAPI(fdiv_r)(mp_int r, mp_int n, mp_int d) { … } /* gmp: mpz_tdiv_q */ void GMPZAPI(tdiv_q)(mp_int q, mp_int n, mp_int d) { … } /* gmp: mpz_fdiv_q_ui */ unsigned long GMPZAPI(fdiv_q_ui)(mp_int q, mp_int n, unsigned long d) { … } /* gmp: mpz_export */ void *GMPZAPI(export)(void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, mp_int op) { … } /* gmp: mpz_import */ void GMPZAPI(import)(mp_int rop, size_t count, int order, size_t size, int endian, size_t nails, const void *op) { … } /* gmp: mpz_sizeinbase */ size_t GMPZAPI(sizeinbase)(mp_int op, int base) { … }
Codebase Browser
llvm