iPXE
bigint.h
Go to the documentation of this file.
00001 #ifndef _IPXE_BIGINT_H
00002 #define _IPXE_BIGINT_H
00003 
00004 /** @file
00005  *
00006  * Big integer support
00007  */
00008 
00009 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00010 
00011 /**
00012  * Define a big-integer type
00013  *
00014  * @v size              Number of elements
00015  * @ret bigint_t        Big integer type
00016  */
00017 #define bigint_t( size )                                                \
00018         struct {                                                        \
00019                 bigint_element_t element[ (size) ];                     \
00020         }
00021 
00022 /**
00023  * Determine number of elements required for a big-integer type
00024  *
00025  * @v len               Maximum length of big integer, in bytes
00026  * @ret size            Number of elements
00027  */
00028 #define bigint_required_size( len )                                     \
00029         ( ( (len) + sizeof ( bigint_element_t ) - 1 ) /                 \
00030           sizeof ( bigint_element_t ) )
00031 
00032 /**
00033  * Determine number of elements in big-integer type
00034  *
00035  * @v bigint            Big integer
00036  * @ret size            Number of elements
00037  */
00038 #define bigint_size( bigint )                                           \
00039         ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )
00040 
00041 /**
00042  * Initialise big integer
00043  *
00044  * @v value             Big integer to initialise
00045  * @v data              Raw data
00046  * @v len               Length of raw data
00047  */
00048 #define bigint_init( value, data, len ) do {                            \
00049         unsigned int size = bigint_size (value);                        \
00050         assert ( (len) <= ( size * sizeof ( (value)->element[0] ) ) );  \
00051         bigint_init_raw ( (value)->element, size, (data), (len) );      \
00052         } while ( 0 )
00053 
00054 /**
00055  * Finalise big integer
00056  *
00057  * @v value             Big integer to finalise
00058  * @v out               Output buffer
00059  * @v len               Length of output buffer
00060  */
00061 #define bigint_done( value, out, len ) do {                             \
00062         unsigned int size = bigint_size (value);                        \
00063         bigint_done_raw ( (value)->element, size, (out), (len) );       \
00064         } while ( 0 )
00065 
00066 /**
00067  * Add big integers
00068  *
00069  * @v addend            Big integer to add
00070  * @v value             Big integer to be added to
00071  */
00072 #define bigint_add( addend, value ) do {                                \
00073         unsigned int size = bigint_size (addend);                       \
00074         bigint_add_raw ( (addend)->element, (value)->element, size );   \
00075         } while ( 0 )
00076 
00077 /**
00078  * Subtract big integers
00079  *
00080  * @v subtrahend        Big integer to subtract
00081  * @v value             Big integer to be subtracted from
00082  */
00083 #define bigint_subtract( subtrahend, value ) do {                       \
00084         unsigned int size = bigint_size (subtrahend);                   \
00085         bigint_subtract_raw ( (subtrahend)->element, (value)->element,  \
00086                               size );                                   \
00087         } while ( 0 )
00088 
00089 /**
00090  * Rotate big integer left
00091  *
00092  * @v value             Big integer
00093  */
00094 #define bigint_rol( value ) do {                                        \
00095         unsigned int size = bigint_size (value);                        \
00096         bigint_rol_raw ( (value)->element, size );                      \
00097         } while ( 0 )
00098 
00099 /**
00100  * Rotate big integer right
00101  *
00102  * @v value             Big integer
00103  */
00104 #define bigint_ror( value ) do {                                        \
00105         unsigned int size = bigint_size (value);                        \
00106         bigint_ror_raw ( (value)->element, size );                      \
00107         } while ( 0 )
00108 
00109 /**
00110  * Test if big integer is equal to zero
00111  *
00112  * @v value             Big integer
00113  * @v size              Number of elements
00114  * @ret is_zero         Big integer is equal to zero
00115  */
00116 #define bigint_is_zero( value ) ( {                                     \
00117         unsigned int size = bigint_size (value);                        \
00118         bigint_is_zero_raw ( (value)->element, size ); } )
00119 
00120 /**
00121  * Compare big integers
00122  *
00123  * @v value             Big integer
00124  * @v reference         Reference big integer
00125  * @ret geq             Big integer is greater than or equal to the reference
00126  */
00127 #define bigint_is_geq( value, reference ) ( {                           \
00128         unsigned int size = bigint_size (value);                        \
00129         bigint_is_geq_raw ( (value)->element, (reference)->element,     \
00130                             size ); } )
00131 
00132 /**
00133  * Test if bit is set in big integer
00134  *
00135  * @v value             Big integer
00136  * @v bit               Bit to test
00137  * @ret is_set          Bit is set
00138  */
00139 #define bigint_bit_is_set( value, bit ) ( {                             \
00140         unsigned int size = bigint_size (value);                        \
00141         bigint_bit_is_set_raw ( (value)->element, size, bit ); } )
00142 
00143 /**
00144  * Find highest bit set in big integer
00145  *
00146  * @v value             Big integer
00147  * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
00148  */
00149 #define bigint_max_set_bit( value ) ( {                                 \
00150         unsigned int size = bigint_size (value);                        \
00151         bigint_max_set_bit_raw ( (value)->element, size ); } )
00152 
00153 /**
00154  * Grow big integer
00155  *
00156  * @v source            Source big integer
00157  * @v dest              Destination big integer
00158  */
00159 #define bigint_grow( source, dest ) do {                                \
00160         unsigned int source_size = bigint_size (source);                \
00161         unsigned int dest_size = bigint_size (dest);                    \
00162         bigint_grow_raw ( (source)->element, source_size,               \
00163                           (dest)->element, dest_size );                 \
00164         } while ( 0 )
00165 
00166 /**
00167  * Shrink big integer
00168  *
00169  * @v source            Source big integer
00170  * @v dest              Destination big integer
00171  */
00172 #define bigint_shrink( source, dest ) do {                              \
00173         unsigned int source_size = bigint_size (source);                \
00174         unsigned int dest_size = bigint_size (dest);                    \
00175         bigint_shrink_raw ( (source)->element, source_size,             \
00176                             (dest)->element, dest_size );               \
00177         } while ( 0 )
00178 
00179 /**
00180  * Multiply big integers
00181  *
00182  * @v multiplicand      Big integer to be multiplied
00183  * @v multiplier        Big integer to be multiplied
00184  * @v result            Big integer to hold result
00185  */
00186 #define bigint_multiply( multiplicand, multiplier, result ) do {        \
00187         unsigned int size = bigint_size (multiplicand);                 \
00188         bigint_multiply_raw ( (multiplicand)->element,                  \
00189                               (multiplier)->element, (result)->element, \
00190                               size );                                   \
00191         } while ( 0 )
00192 
00193 /**
00194  * Perform modular multiplication of big integers
00195  *
00196  * @v multiplicand      Big integer to be multiplied
00197  * @v multiplier        Big integer to be multiplied
00198  * @v modulus           Big integer modulus
00199  * @v result            Big integer to hold result
00200  * @v tmp               Temporary working space
00201  */
00202 #define bigint_mod_multiply( multiplicand, multiplier, modulus,         \
00203                              result, tmp ) do {                         \
00204         unsigned int size = bigint_size (multiplicand);                 \
00205         bigint_mod_multiply_raw ( (multiplicand)->element,              \
00206                                   (multiplier)->element,                \
00207                                   (modulus)->element,                   \
00208                                   (result)->element, size, tmp );       \
00209         } while ( 0 )
00210 
00211 /**
00212  * Calculate temporary working space required for moduluar multiplication
00213  *
00214  * @v modulus           Big integer modulus
00215  * @ret len             Length of temporary working space
00216  */
00217 #define bigint_mod_multiply_tmp_len( modulus ) ( {                      \
00218         unsigned int size = bigint_size (modulus);                      \
00219         sizeof ( struct {                                               \
00220                 bigint_t ( size * 2 ) temp_result;                      \
00221                 bigint_t ( size * 2 ) temp_modulus;                     \
00222         } ); } )
00223 
00224 /**
00225  * Perform modular exponentiation of big integers
00226  *
00227  * @v base              Big integer base
00228  * @v modulus           Big integer modulus
00229  * @v exponent          Big integer exponent
00230  * @v result            Big integer to hold result
00231  * @v tmp               Temporary working space
00232  */
00233 #define bigint_mod_exp( base, modulus, exponent, result, tmp ) do {     \
00234         unsigned int size = bigint_size (base);                         \
00235         unsigned int exponent_size = bigint_size (exponent);            \
00236         bigint_mod_exp_raw ( (base)->element, (modulus)->element,       \
00237                              (exponent)->element, (result)->element,    \
00238                              size, exponent_size, tmp );                \
00239         } while ( 0 )
00240 
00241 /**
00242  * Calculate temporary working space required for moduluar exponentiation
00243  *
00244  * @v modulus           Big integer modulus
00245  * @v exponent          Big integer exponent
00246  * @ret len             Length of temporary working space
00247  */
00248 #define bigint_mod_exp_tmp_len( modulus, exponent ) ( {                 \
00249         unsigned int size = bigint_size (modulus);                      \
00250         unsigned int exponent_size = bigint_size (exponent);            \
00251         size_t mod_multiply_len =                                       \
00252                 bigint_mod_multiply_tmp_len (modulus);                  \
00253         sizeof ( struct {                                               \
00254                 bigint_t ( size ) temp_base;                            \
00255                 bigint_t ( exponent_size ) temp_exponent;               \
00256                 uint8_t mod_multiply[mod_multiply_len];                 \
00257         } ); } )
00258 
00259 #include <bits/bigint.h>
00260 
00261 void bigint_init_raw ( bigint_element_t *value0, unsigned int size,
00262                        const void *data, size_t len );
00263 void bigint_done_raw ( const bigint_element_t *value0, unsigned int size,
00264                        void *out, size_t len );
00265 void bigint_add_raw ( const bigint_element_t *addend0,
00266                       bigint_element_t *value0, unsigned int size );
00267 void bigint_subtract_raw ( const bigint_element_t *subtrahend0,
00268                            bigint_element_t *value0, unsigned int size );
00269 void bigint_rol_raw ( bigint_element_t *value0, unsigned int size );
00270 void bigint_ror_raw ( bigint_element_t *value0, unsigned int size );
00271 int bigint_is_zero_raw ( const bigint_element_t *value0, unsigned int size );
00272 int bigint_is_geq_raw ( const bigint_element_t *value0,
00273                         const bigint_element_t *reference0,
00274                         unsigned int size );
00275 int bigint_bit_is_set_raw ( const bigint_element_t *value0, unsigned int size,
00276                             unsigned int bit );
00277 int bigint_max_set_bit_raw ( const bigint_element_t *value0,
00278                              unsigned int size );
00279 void bigint_grow_raw ( const bigint_element_t *source0,
00280                        unsigned int source_size, bigint_element_t *dest0,
00281                        unsigned int dest_size );
00282 void bigint_shrink_raw ( const bigint_element_t *source0,
00283                          unsigned int source_size, bigint_element_t *dest0,
00284                          unsigned int dest_size );
00285 void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
00286                            const bigint_element_t *multiplier0,
00287                            bigint_element_t *result0,
00288                            unsigned int size );
00289 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
00290                                const bigint_element_t *multiplier0,
00291                                const bigint_element_t *modulus0,
00292                                bigint_element_t *result0,
00293                                unsigned int size, void *tmp );
00294 void bigint_mod_exp_raw ( const bigint_element_t *base0,
00295                           const bigint_element_t *modulus0,
00296                           const bigint_element_t *exponent0,
00297                           bigint_element_t *result0,
00298                           unsigned int size, unsigned int exponent_size,
00299                           void *tmp );
00300 
00301 #endif /* _IPXE_BIGINT_H */