qemu/roms/ipxe/src/include/ipxe/bigint.h

   1 #ifndef _IPXE_BIGINT_H
   2 #define _IPXE_BIGINT_H
   3
   4 /** @file
   5  *
   6  * Big integer support
   7  */
   8
   9 FILE_LICENCE ( GPL2_OR_LATER );
  10
  11 /**
  12  * Define a big-integer type
  13  *
  14  * @v size              Number of elements
  15  * @ret bigint_t        Big integer type
  16  */
  17 #define bigint_t( size )                                                \
  18         struct {                                                        \
  19                 bigint_element_t element[ (size) ];                     \
  20         }
  21
  22 /**
  23  * Determine number of elements required for a big-integer type
  24  *
  25  * @v len               Maximum length of big integer, in bytes
  26  * @ret size            Number of elements
  27  */
  28 #define bigint_required_size( len )                                     \
  29         ( ( (len) + sizeof ( bigint_element_t ) - 1 ) /                 \
  30           sizeof ( bigint_element_t ) )
  31
  32 /**
  33  * Determine number of elements in big-integer type
  34  *
  35  * @v bigint            Big integer
  36  * @ret size            Number of elements
  37  */
  38 #define bigint_size( bigint )                                           \
  39         ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )
  40
  41 /**
  42  * Initialise big integer
  43  *
  44  * @v value             Big integer to initialise
  45  * @v data              Raw data
  46  * @v len               Length of raw data
  47  */
  48 #define bigint_init( value, data, len ) do {                            \
  49         unsigned int size = bigint_size (value);                        \
  50         assert ( (len) <= ( size * sizeof ( (value)->element[0] ) ) );  \
  51         bigint_init_raw ( (value)->element, size, (data), (len) );      \
  52         } while ( 0 )
  53
  54 /**
  55  * Finalise big integer
  56  *
  57  * @v value             Big integer to finalise
  58  * @v out               Output buffer
  59  * @v len               Length of output buffer
  60  */
  61 #define bigint_done( value, out, len ) do {                             \
  62         unsigned int size = bigint_size (value);                        \
  63         bigint_done_raw ( (value)->element, size, (out), (len) );       \
  64         } while ( 0 )
  65
  66 /**
  67  * Add big integers
  68  *
  69  * @v addend            Big integer to add
  70  * @v value             Big integer to be added to
  71  */
  72 #define bigint_add( addend, value ) do {                                \
  73         unsigned int size = bigint_size (addend);                       \
  74         bigint_add_raw ( (addend)->element, (value)->element, size );   \
  75         } while ( 0 )
  76
  77 /**
  78  * Subtract big integers
  79  *
  80  * @v subtrahend        Big integer to subtract
  81  * @v value             Big integer to be subtracted from
  82  */
  83 #define bigint_subtract( subtrahend, value ) do {                       \
  84         unsigned int size = bigint_size (subtrahend);                   \
  85         bigint_subtract_raw ( (subtrahend)->element, (value)->element,  \
  86                               size );                                   \
  87         } while ( 0 )
  88
  89 /**
  90  * Rotate big integer left
  91  *
  92  * @v value             Big integer
  93  */
  94 #define bigint_rol( value ) do {                                        \
  95         unsigned int size = bigint_size (value);                        \
  96         bigint_rol_raw ( (value)->element, size );                      \
  97         } while ( 0 )
  98
  99 /**
 100  * Rotate big integer right
 101  *
 102  * @v value             Big integer
 103  */
 104 #define bigint_ror( value ) do {                                        \
 105         unsigned int size = bigint_size (value);                        \
 106         bigint_ror_raw ( (value)->element, size );                      \
 107         } while ( 0 )
 108
 109 /**
 110  * Test if big integer is equal to zero
 111  *
 112  * @v value             Big integer
 113  * @v size              Number of elements
 114  * @ret is_zero         Big integer is equal to zero
 115  */
 116 #define bigint_is_zero( value ) ( {                                     \
 117         unsigned int size = bigint_size (value);                        \
 118         bigint_is_zero_raw ( (value)->element, size ); } )
 119
 120 /**
 121  * Compare big integers
 122  *
 123  * @v value             Big integer
 124  * @v reference         Reference big integer
 125  * @ret geq             Big integer is greater than or equal to the reference
 126  */
 127 #define bigint_is_geq( value, reference ) ( {                           \
 128         unsigned int size = bigint_size (value);                        \
 129         bigint_is_geq_raw ( (value)->element, (reference)->element,     \
 130                             size ); } )
 131
 132 /**
 133  * Test if bit is set in big integer
 134  *
 135  * @v value             Big integer
 136  * @v bit               Bit to test
 137  * @ret is_set          Bit is set
 138  */
 139 #define bigint_bit_is_set( value, bit ) ( {                             \
 140         unsigned int size = bigint_size (value);                        \
 141         bigint_bit_is_set_raw ( (value)->element, size, bit ); } )
 142
 143 /**
 144  * Find highest bit set in big integer
 145  *
 146  * @v value             Big integer
 147  * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
 148  */
 149 #define bigint_max_set_bit( value ) ( {                                 \
 150         unsigned int size = bigint_size (value);                        \
 151         bigint_max_set_bit_raw ( (value)->element, size ); } )
 152
 153 /**
 154  * Grow big integer
 155  *
 156  * @v source            Source big integer
 157  * @v dest              Destination big integer
 158  */
 159 #define bigint_grow( source, dest ) do {                                \
 160         unsigned int source_size = bigint_size (source);                \
 161         unsigned int dest_size = bigint_size (dest);                    \
 162         bigint_grow_raw ( (source)->element, source_size,               \
 163                           (dest)->element, dest_size );                 \
 164         } while ( 0 )
 165
 166 /**
 167  * Shrink big integer
 168  *
 169  * @v source            Source big integer
 170  * @v dest              Destination big integer
 171  */
 172 #define bigint_shrink( source, dest ) do {                              \
 173         unsigned int source_size = bigint_size (source);                \
 174         unsigned int dest_size = bigint_size (dest);                    \
 175         bigint_shrink_raw ( (source)->element, source_size,             \
 176                             (dest)->element, dest_size );               \
 177         } while ( 0 )
 178
 179 /**
 180  * Multiply big integers
 181  *
 182  * @v multiplicand      Big integer to be multiplied
 183  * @v multiplier        Big integer to be multiplied
 184  * @v result            Big integer to hold result
 185  */
 186 #define bigint_multiply( multiplicand, multiplier, result ) do {        \
 187         unsigned int size = bigint_size (multiplicand);                 \
 188         bigint_multiply_raw ( (multiplicand)->element,                  \
 189                               (multiplier)->element, (result)->element, \
 190                               size );                                   \
 191         } while ( 0 )
 192
 193 /**
 194  * Perform modular multiplication of big integers
 195  *
 196  * @v multiplicand      Big integer to be multiplied
 197  * @v multiplier        Big integer to be multiplied
 198  * @v modulus           Big integer modulus
 199  * @v result            Big integer to hold result
 200  * @v tmp               Temporary working space
 201  */
 202 #define bigint_mod_multiply( multiplicand, multiplier, modulus,         \
 203                              result, tmp ) do {                         \
 204         unsigned int size = bigint_size (multiplicand);                 \
 205         bigint_mod_multiply_raw ( (multiplicand)->element,              \
 206                                   (multiplier)->element,                \
 207                                   (modulus)->element,                   \
 208                                   (result)->element, size, tmp );       \
 209         } while ( 0 )
 210
 211 /**
 212  * Calculate temporary working space required for moduluar multiplication
 213  *
 214  * @v modulus           Big integer modulus
 215  * @ret len             Length of temporary working space
 216  */
 217 #define bigint_mod_multiply_tmp_len( modulus ) ( {                      \
 218         unsigned int size = bigint_size (modulus);                      \
 219         sizeof ( struct {                                               \
 220                 bigint_t ( size * 2 ) temp_result;                      \
 221                 bigint_t ( size * 2 ) temp_modulus;                     \
 222         } ); } )
 223
 224 /**
 225  * Perform modular exponentiation of big integers
 226  *
 227  * @v base              Big integer base
 228  * @v modulus           Big integer modulus
 229  * @v exponent          Big integer exponent
 230  * @v result            Big integer to hold result
 231  * @v tmp               Temporary working space
 232  */
 233 #define bigint_mod_exp( base, modulus, exponent, result, tmp ) do {     \
 234         unsigned int size = bigint_size (base);                         \
 235         unsigned int exponent_size = bigint_size (exponent);            \
 236         bigint_mod_exp_raw ( (base)->element, (modulus)->element,       \
 237                              (exponent)->element, (result)->element,    \
 238                              size, exponent_size, tmp );                \
 239         } while ( 0 )
 240
 241 /**
 242  * Calculate temporary working space required for moduluar exponentiation
 243  *
 244  * @v modulus           Big integer modulus
 245  * @v exponent          Big integer exponent
 246  * @ret len             Length of temporary working space
 247  */
 248 #define bigint_mod_exp_tmp_len( modulus, exponent ) ( {                 \
 249         unsigned int size = bigint_size (modulus);                      \
 250         unsigned int exponent_size = bigint_size (exponent);            \
 251         size_t mod_multiply_len =                                       \
 252                 bigint_mod_multiply_tmp_len (modulus);                  \
 253         sizeof ( struct {                                               \
 254                 bigint_t ( size ) temp_base;                            \
 255                 bigint_t ( exponent_size ) temp_exponent;               \
 256                 uint8_t mod_multiply[mod_multiply_len];                 \
 257         } ); } )
 258
 259 #include <bits/bigint.h>
 260
 261 void bigint_init_raw ( bigint_element_t *value0, unsigned int size,
 262                        const void *data, size_t len );
 263 void bigint_done_raw ( const bigint_element_t *value0, unsigned int size,
 264                        void *out, size_t len );
 265 void bigint_add_raw ( const bigint_element_t *addend0,
 266                       bigint_element_t *value0, unsigned int size );
 267 void bigint_subtract_raw ( const bigint_element_t *subtrahend0,
 268                            bigint_element_t *value0, unsigned int size );
 269 void bigint_rol_raw ( bigint_element_t *value0, unsigned int size );
 270 void bigint_ror_raw ( bigint_element_t *value0, unsigned int size );
 271 int bigint_is_zero_raw ( const bigint_element_t *value0, unsigned int size );
 272 int bigint_is_geq_raw ( const bigint_element_t *value0,
 273                         const bigint_element_t *reference0,
 274                         unsigned int size );
 275 int bigint_bit_is_set_raw ( const bigint_element_t *value0, unsigned int size,
 276                             unsigned int bit );
 277 int bigint_max_set_bit_raw ( const bigint_element_t *value0,
 278                              unsigned int size );
 279 void bigint_grow_raw ( const bigint_element_t *source0,
 280                        unsigned int source_size, bigint_element_t *dest0,
 281                        unsigned int dest_size );
 282 void bigint_shrink_raw ( const bigint_element_t *source0,
 283                          unsigned int source_size, bigint_element_t *dest0,
 284                          unsigned int dest_size );
 285 void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
 286                            const bigint_element_t *multiplier0,
 287                            bigint_element_t *result0,
 288                            unsigned int size );
 289 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
 290                                const bigint_element_t *multiplier0,
 291                                const bigint_element_t *modulus0,
 292                                bigint_element_t *result0,
 293                                unsigned int size, void *tmp );
 294 void bigint_mod_exp_raw ( const bigint_element_t *base0,
 295                           const bigint_element_t *modulus0,
 296                           const bigint_element_t *exponent0,
 297                           bigint_element_t *result0,
 298                           unsigned int size, unsigned int exponent_size,
 299                           void *tmp );
 300
 301 #endif /* _IPXE_BIGINT_H */