iPXE
bigint.h
Go to the documentation of this file.
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 );
274  unsigned int size );
275 int bigint_bit_is_set_raw ( const bigint_element_t *value0, unsigned int size,
276  unsigned int bit );
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 */
void bigint_multiply_raw(const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, bigint_element_t *result0, unsigned int size)
Multiply big integers.
Definition: x86_bigint.c:43
void bigint_grow_raw(const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
static const uint32_t * reference0
Definition: bigint.h:168
static unsigned int unsigned int bit
Definition: bigint.h:196
int bigint_max_set_bit_raw(const bigint_element_t *value0, unsigned int size)
void bigint_subtract_raw(const bigint_element_t *subtrahend0, bigint_element_t *value0, unsigned int size)
static uint32_t * value0
Definition: bigint.h:54
static unsigned int const void size_t len
Definition: bigint.h:27
void bigint_rol_raw(bigint_element_t *value0, unsigned int size)
static unsigned int const void * data
Definition: bigint.h:26
void bigint_add_raw(const bigint_element_t *addend0, bigint_element_t *value0, unsigned int size)
uint32_t bigint_element_t
Element of a big integer.
Definition: bigint.h:15
void bigint_init_raw(bigint_element_t *value0, unsigned int size, const void *data, size_t len)
static unsigned int uint32_t unsigned int dest_size
Definition: bigint.h:241
void bigint_mod_multiply_raw(const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, bigint_element_t *result0, unsigned int size, void *tmp)
Perform modular multiplication of big integers.
Definition: bigint.c:63
void bigint_mod_exp_raw(const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, bigint_element_t *result0, unsigned int size, unsigned int exponent_size, void *tmp)
Perform modular exponentiation of big integers.
Definition: bigint.c:133
uint8_t * tmp
Definition: entropy.h:156
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
int bigint_bit_is_set_raw(const bigint_element_t *value0, unsigned int size, unsigned int bit)
static unsigned int source_size
Definition: bigint.h:240
void bigint_shrink_raw(const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
void bigint_done_raw(const bigint_element_t *value0, unsigned int size, void *out, size_t len)
static unsigned int size void * out
Definition: bigint.h:290
void bigint_ror_raw(bigint_element_t *value0, unsigned int size)
int bigint_is_zero_raw(const bigint_element_t *value0, unsigned int size)
static unsigned int uint32_t * dest0
Definition: bigint.h:240
static unsigned int size
Definition: bigint.h:26
Big integer support.
int bigint_is_geq_raw(const bigint_element_t *value0, const bigint_element_t *reference0, unsigned int size)