bigint_impl.h

00001 /*
00002  * Copyright (c) 2007, Cameron Rich
00003  * 
00004  * All rights reserved.
00005  * 
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met:
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  *   this list of conditions and the following disclaimer.
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  *   this list of conditions and the following disclaimer in the documentation 
00013  *   and/or other materials provided with the distribution.
00014  * * Neither the name of the axTLS project nor the names of its contributors 
00015  *   may be used to endorse or promote products derived from this software 
00016  *   without specific prior written permission.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00026  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  */
00030 
00031 #ifndef BIGINT_IMPL_HEADER
00032 #define BIGINT_IMPL_HEADER
00033 
00034 /* Maintain a number of precomputed variables when doing reduction */
00035 #define BIGINT_M_OFFSET     0    /**< Normal modulo offset. */
00036 #ifdef CONFIG_BIGINT_CRT
00037 #define BIGINT_P_OFFSET     1    /**< p modulo offset. */
00038 #define BIGINT_Q_OFFSET     2    /**< q module offset. */
00039 #define BIGINT_NUM_MODS     3    /**< The number of modulus constants used. */
00040 #else
00041 #define BIGINT_NUM_MODS     1    
00042 #endif
00043 
00044 
00045 /* Architecture specific functions for big ints */
00046 #if defined(CONFIG_INTEGER_8BIT)
00047 #define COMP_RADIX          256U       /**< Max component + 1 */
00048 #define COMP_MAX            0xFFFFU/**< (Max dbl comp -1) */
00049 #define COMP_BIT_SIZE       8   /**< Number of bits in a component. */
00050 #define COMP_BYTE_SIZE      1   /**< Number of bytes in a component. */
00051 #define COMP_NUM_NIBBLES    2   /**< Used For diagnostics only. */
00052 typedef uint8_t comp;            /**< A single precision component. */
00053 typedef uint16_t long_comp;     /**< A double precision component. */
00054 typedef int16_t slong_comp;     /**< A signed double precision component. */
00055 #elif defined(CONFIG_INTEGER_16BIT)
00056 #define COMP_RADIX          65536U       /**< Max component + 1 */
00057 #define COMP_MAX            0xFFFFFFFFU/**< (Max dbl comp -1) */
00058 #define COMP_BIT_SIZE       16  /**< Number of bits in a component. */
00059 #define COMP_BYTE_SIZE      2   /**< Number of bytes in a component. */
00060 #define COMP_NUM_NIBBLES    4   /**< Used For diagnostics only. */
00061 typedef uint16_t comp;            /**< A single precision component. */
00062 typedef uint32_t long_comp;     /**< A double precision component. */
00063 typedef int32_t slong_comp;     /**< A signed double precision component. */
00064 #else /* regular 32 bit */
00065 #ifdef WIN32
00066 #define COMP_RADIX          4294967296i64         
00067 #define COMP_MAX            0xFFFFFFFFFFFFFFFFui64
00068 #else
00069 #define COMP_RADIX          4294967296ULL         /**< Max component + 1 */
00070 #define COMP_MAX            0xFFFFFFFFFFFFFFFFULL/**< (Max dbl comp -1) */
00071 #endif
00072 #define COMP_BIT_SIZE       32  /**< Number of bits in a component. */
00073 #define COMP_BYTE_SIZE      4   /**< Number of bytes in a component. */
00074 #define COMP_NUM_NIBBLES    8   /**< Used For diagnostics only. */
00075 #include <stdint.h>
00076 typedef uint32_t comp;            /**< A single precision component. */
00077 typedef uint64_t long_comp;     /**< A double precision component. */
00078 typedef int64_t slong_comp;     /**< A signed double precision component. */
00079 #endif
00080 
00081 /**
00082  * @struct  _bigint
00083  * @brief A big integer basic object
00084  */
00085 struct _bigint
00086 {
00087     struct _bigint* next;       /**< The next bigint in the cache. */
00088     short size;                 /**< The number of components in this bigint. */
00089     short max_comps;            /**< The heapsize allocated for this bigint */
00090     int refs;                   /**< An internal reference count. */
00091     comp* comps;                /**< A ptr to the actual component data */
00092 };
00093 
00094 typedef struct _bigint bigint;  /**< An alias for _bigint */
00095 
00096 /**
00097  * Maintains the state of the cache, and a number of variables used in 
00098  * reduction.
00099  */
00100 typedef struct /**< A big integer "session" context. */
00101 {
00102     bigint *active_list;                    /**< Bigints currently used. */
00103     bigint *free_list;                      /**< Bigints not used. */
00104     bigint *bi_radix;                       /**< The radix used. */
00105     bigint *bi_mod[BIGINT_NUM_MODS];        /**< modulus */
00106 
00107 #if defined(CONFIG_BIGINT_MONTGOMERY)
00108     bigint *bi_RR_mod_m[BIGINT_NUM_MODS];   /**< R^2 mod m */
00109     bigint *bi_R_mod_m[BIGINT_NUM_MODS];    /**< R mod m */
00110     comp N0_dash[BIGINT_NUM_MODS];
00111 #elif defined(CONFIG_BIGINT_BARRETT)
00112     bigint *bi_mu[BIGINT_NUM_MODS];         /**< Storage for mu */
00113 #endif
00114     bigint *bi_normalised_mod[BIGINT_NUM_MODS]; /**< Normalised mod storage. */
00115     bigint **g;                 /**< Used by sliding-window. */
00116     int window;                 /**< The size of the sliding window */
00117     int active_count;           /**< Number of active bigints. */
00118     int free_count;             /**< Number of free bigints. */
00119 
00120 #ifdef CONFIG_BIGINT_MONTGOMERY
00121     uint8_t use_classical;      /**< Use classical reduction. */
00122 #endif
00123     uint8_t mod_offset;         /**< The mod offset we are using */
00124 } BI_CTX;
00125 
00126 #ifndef WIN32
00127 #define max(a,b) ((a)>(b)?(a):(b))  /**< Find the maximum of 2 numbers. */
00128 #define min(a,b) ((a)<(b)?(a):(b))  /**< Find the minimum of 2 numbers. */
00129 #endif
00130 
00131 #define PERMANENT           0x7FFF55AA  /**< A magic number for permanents. */
00132 
00133 #endif
00134 
00135