1 /* 2 * Copyright(C) 2006 Cameron Rich 3 * 4 * This library is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU Lesser General Public License as published by 6 * the Free Software Foundation; either version 2.1 of the License, or 7 * (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU Lesser General Public License for more details. 13 * 14 * You should have received a copy of the GNU Lesser General Public License 15 * along with this library; if not, write to the Free Software 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 */ 18 19 #ifndef BIGINT_IMPL_HEADER 20 #define BIGINT_IMPL_HEADER 21 22 /* Maintain a number of precomputed variables when doing reduction */ 23 #define BIGINT_M_OFFSET 0 /**< Normal modulo offset. */ 24 #ifdef CONFIG_BIGINT_CRT 25 #define BIGINT_P_OFFSET 1 /**< p modulo offset. */ 26 #define BIGINT_Q_OFFSET 2 /**< q module offset. */ 27 #define BIGINT_NUM_MODS 3 /**< The number of modulus constants used. */ 28 #else 29 #define BIGINT_NUM_MODS 1 30 #endif 31 32 /* Architecture specific functions for big ints */ 33 #ifdef WIN32 34 #define COMP_RADIX 4294967296i64 35 #define COMP_BIG_MSB 0x8000000000000000i64 36 #else 37 #define COMP_RADIX 4294967296ULL /**< Max component + 1 */ 38 #define COMP_BIG_MSB 0x8000000000000000ULL /**< (Max dbl comp + 1)/ 2 */ 39 #endif 40 #define COMP_BIT_SIZE 32 /**< Number of bits in a component. */ 41 #define COMP_BYTE_SIZE 4 /**< Number of bytes in a component. */ 42 #define COMP_NUM_NIBBLES 8 /**< Used For diagnostics only. */ 43 44 typedef uint32_t comp; /**< A single precision component. */ 45 typedef uint64_t long_comp; /**< A double precision component. */ 46 typedef int64_t slong_comp; /**< A signed double precision component. */ 47 48 /** 49 * @struct _bigint 50 * @brief A big integer basic object 51 */ 52 struct _bigint 53 { 54 struct _bigint* next; /**< The next bigint in the cache. */ 55 short size; /**< The number of components in this bigint. */ 56 short max_comps; /**< The heapsize allocated for this bigint */ 57 int refs; /**< An internal reference count. */ 58 comp* comps; /**< A ptr to the actual component data */ 59 }; 60 61 typedef struct _bigint bigint; /**< An alias for _bigint */ 62 63 /** 64 * Maintains the state of the cache, and a number of variables used in 65 * reduction. 66 */ 67 typedef struct /**< A big integer "session" context. */ 68 { 69 bigint *active_list; /**< Bigints currently used. */ 70 bigint *free_list; /**< Bigints not used. */ 71 bigint *bi_radix; /**< The radix used. */ 72 bigint *bi_mod[BIGINT_NUM_MODS]; /**< modulus */ 73 74 #if defined(CONFIG_BIGINT_MONTGOMERY) 75 bigint *bi_RR_mod_m[BIGINT_NUM_MODS]; /**< R^2 mod m */ 76 bigint *bi_R_mod_m[BIGINT_NUM_MODS]; /**< R mod m */ 77 comp N0_dash[BIGINT_NUM_MODS]; 78 #elif defined(CONFIG_BIGINT_BARRETT) 79 bigint *bi_mu[BIGINT_NUM_MODS]; /**< Storage for mu */ 80 #endif 81 bigint *bi_normalised_mod[BIGINT_NUM_MODS]; /**< Normalised mod storage. */ 82 bigint **g; /**< Used by sliding-window. */ 83 int window; /**< The size of the sliding window */ 84 int active_count; /**< Number of active bigints. */ 85 int free_count; /**< Number of free bigints. */ 86 87 #ifdef CONFIG_BIGINT_MONTGOMERY 88 uint8_t use_classical; /**< Use classical reduction. */ 89 #endif 90 uint8_t mod_offset; /**< The mod offset we are using */ 91 } BI_CTX; 92 93 #ifndef WIN32 94 #define max(a,b) ((a)>(b)?(a):(b)) /**< Find the maximum of 2 numbers. */ 95 #define min(a,b) ((a)<(b)?(a):(b)) /**< Find the minimum of 2 numbers. */ 96 #endif 97 98 #define PERMANENT 0x7FFF55AA /**< A magic number for permanents. */ 99 100 #define V1 v->comps[v->size-1] /**< v1 for division */ 101 #define V2 v->comps[v->size-2] /**< v2 for division */ 102 #define U(j) tmp_u->comps[tmp_u->size-j-1] /**< uj for division */ 103 #define Q(j) quotient->comps[quotient->size-j-1] /**< qj for division */ 104 105 #endif 106
