| 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 |
|---|
