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_OR_UBDL ); 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 */ 302