iPXE
bigint.h
Go to the documentation of this file.
1 #ifndef _BITS_BIGINT_H
2 #define _BITS_BIGINT_H
3 
4 /** @file
5  *
6  * Big integer support
7  */
8 
9 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
10 
11 #include <stdint.h>
12 #include <string.h>
13 
14 /** Element of a big integer */
16 
17 /**
18  * Initialise big integer
19  *
20  * @v value0 Element 0 of big integer to initialise
21  * @v size Number of elements
22  * @v data Raw data
23  * @v len Length of raw data
24  */
25 static inline __attribute__ (( always_inline )) void
27  const void *data, size_t len ) {
28  bigint_t ( size ) __attribute__ (( may_alias )) *value =
29  ( ( void * ) value0 );
30  long pad_len = ( sizeof ( *value ) - len );
31  void *discard_D;
32  long discard_c;
33 
34  /* Copy raw data in reverse order, padding with zeros */
35  __asm__ __volatile__ ( "\n1:\n\t"
36  "movb -1(%3,%1), %%al\n\t"
37  "stosb\n\t"
38  "loop 1b\n\t"
39  "xorl %%eax, %%eax\n\t"
40  "mov %4, %1\n\t"
41  "rep stosb\n\t"
42  : "=&D" ( discard_D ), "=&c" ( discard_c ),
43  "+m" ( *value )
44  : "r" ( data ), "g" ( pad_len ), "0" ( value0 ),
45  "1" ( len )
46  : "eax" );
47 }
48 
49 /**
50  * Add big integers
51  *
52  * @v addend0 Element 0 of big integer to add
53  * @v value0 Element 0 of big integer to be added to
54  * @v size Number of elements
55  * @ret carry Carry flag
56  */
57 static inline __attribute__ (( always_inline )) int
59  unsigned int size ) {
60  bigint_t ( size ) __attribute__ (( may_alias )) *value =
61  ( ( void * ) value0 );
62  long index;
63  void *discard_S;
64  long discard_c;
65  int carry;
66 
67  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
68  "\n1:\n\t"
69  "lodsl\n\t"
70  "adcl %%eax, (%5,%0,4)\n\t"
71  "inc %0\n\t" /* Does not affect CF */
72  "loop 1b\n\t"
73  : "=&r" ( index ), "=&S" ( discard_S ),
74  "=&c" ( discard_c ), "=@ccc" ( carry ),
75  "+m" ( *value )
76  : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
77  : "eax" );
78  return carry;
79 }
80 
81 /**
82  * Subtract big integers
83  *
84  * @v subtrahend0 Element 0 of big integer to subtract
85  * @v value0 Element 0 of big integer to be subtracted from
86  * @v size Number of elements
87  * @ret borrow Borrow flag
88  */
89 static inline __attribute__ (( always_inline )) int
90 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
91  unsigned int size ) {
92  bigint_t ( size ) __attribute__ (( may_alias )) *value =
93  ( ( void * ) value0 );
94  long index;
95  void *discard_S;
96  long discard_c;
97  int borrow;
98 
99  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
100  "\n1:\n\t"
101  "lodsl\n\t"
102  "sbbl %%eax, (%5,%0,4)\n\t"
103  "inc %0\n\t" /* Does not affect CF */
104  "loop 1b\n\t"
105  : "=&r" ( index ), "=&S" ( discard_S ),
106  "=&c" ( discard_c ), "=@ccc" ( borrow ),
107  "+m" ( *value )
108  : "r" ( value0 ), "1" ( subtrahend0 ),
109  "2" ( size )
110  : "eax" );
111  return borrow;
112 }
113 
114 /**
115  * Shift big integer left
116  *
117  * @v value0 Element 0 of big integer
118  * @v size Number of elements
119  * @ret out Bit shifted out
120  */
121 static inline __attribute__ (( always_inline )) int
122 bigint_shl_raw ( uint32_t *value0, unsigned int size ) {
123  bigint_t ( size ) __attribute__ (( may_alias )) *value =
124  ( ( void * ) value0 );
125  long index;
126  long discard_c;
127  int out;
128 
129  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
130  "\n1:\n\t"
131  "rcll $1, (%4,%0,4)\n\t"
132  "inc %0\n\t" /* Does not affect CF */
133  "loop 1b\n\t"
134  : "=&r" ( index ), "=&c" ( discard_c ),
135  "=@ccc" ( out ), "+m" ( *value )
136  : "r" ( value0 ), "1" ( size ) );
137  return out;
138 }
139 
140 /**
141  * Shift big integer right
142  *
143  * @v value0 Element 0 of big integer
144  * @v size Number of elements
145  * @ret out Bit shifted out
146  */
147 static inline __attribute__ (( always_inline )) int
148 bigint_shr_raw ( uint32_t *value0, unsigned int size ) {
149  bigint_t ( size ) __attribute__ (( may_alias )) *value =
150  ( ( void * ) value0 );
151  long discard_c;
152  int out;
153 
154  __asm__ __volatile__ ( "clc\n\t"
155  "\n1:\n\t"
156  "rcrl $1, -4(%3,%0,4)\n\t"
157  "loop 1b\n\t"
158  : "=&c" ( discard_c ), "=@ccc" ( out ),
159  "+m" ( *value )
160  : "r" ( value0 ), "0" ( size ) );
161  return out;
162 }
163 
164 /**
165  * Test if big integer is equal to zero
166  *
167  * @v value0 Element 0 of big integer
168  * @v size Number of elements
169  * @ret is_zero Big integer is equal to zero
170  */
171 static inline __attribute__ (( always_inline, pure )) int
172 bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
173  void *discard_D;
174  long discard_c;
175  int result;
176 
177  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
178  "repe scasl\n\t"
179  "sete %b0\n\t"
180  : "=&a" ( result ), "=&D" ( discard_D ),
181  "=&c" ( discard_c )
182  : "1" ( value0 ), "2" ( size ) );
183  return result;
184 }
185 
186 /**
187  * Compare big integers
188  *
189  * @v value0 Element 0 of big integer
190  * @v reference0 Element 0 of reference big integer
191  * @v size Number of elements
192  * @ret geq Big integer is greater than or equal to the reference
193  */
194 static inline __attribute__ (( always_inline, pure )) int
196  unsigned int size ) {
197  long discard_c;
199  int result;
200 
201  __asm__ __volatile__ ( "\n1:\n\t"
202  "movl -4(%3, %1, 4), %k2\n\t"
203  "cmpl -4(%4, %1, 4), %k2\n\t"
204  "loope 1b\n\t"
205  "setae %b0\n\t"
206  : "=q" ( result ), "=&c" ( discard_c ),
207  "=&r" ( discard_tmp )
208  : "r" ( value0 ), "r" ( reference0 ),
209  "0" ( 0 ), "1" ( size ) );
210  return result;
211 }
212 
213 /**
214  * Find highest bit set in big integer
215  *
216  * @v value0 Element 0 of big integer
217  * @v size Number of elements
218  * @ret max_bit Highest bit set + 1 (or 0 if no bits set)
219  */
220 static inline __attribute__ (( always_inline )) int
221 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
222  long discard_c;
223  int result;
224 
225  __asm__ __volatile__ ( "\n1:\n\t"
226  "bsrl -4(%2,%1,4), %0\n\t"
227  "loopz 1b\n\t"
228  "rol %1\n\t" /* Does not affect ZF */
229  "rol %1\n\t"
230  "leal 1(%k0,%k1,8), %k0\n\t"
231  "jnz 2f\n\t"
232  "xor %0, %0\n\t"
233  "\n2:\n\t"
234  : "=&r" ( result ), "=&c" ( discard_c )
235  : "r" ( value0 ), "1" ( size ) );
236  return result;
237 }
238 
239 /**
240  * Grow big integer
241  *
242  * @v source0 Element 0 of source big integer
243  * @v source_size Number of elements in source big integer
244  * @v dest0 Element 0 of destination big integer
245  * @v dest_size Number of elements in destination big integer
246  */
247 static inline __attribute__ (( always_inline )) void
248 bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
249  uint32_t *dest0, unsigned int dest_size ) {
250  bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
251  ( ( void * ) dest0 );
253  void *discard_D;
254  void *discard_S;
255  long discard_c;
256 
257  __asm__ __volatile__ ( "rep movsl\n\t"
258  "xorl %%eax, %%eax\n\t"
259  "mov %4, %2\n\t"
260  "rep stosl\n\t"
261  : "=&D" ( discard_D ), "=&S" ( discard_S ),
262  "=&c" ( discard_c ), "+m" ( *dest )
263  : "g" ( pad_size ), "0" ( dest0 ),
264  "1" ( source0 ), "2" ( source_size )
265  : "eax" );
266 }
267 
268 /**
269  * Shrink big integer
270  *
271  * @v source0 Element 0 of source big integer
272  * @v source_size Number of elements in source big integer
273  * @v dest0 Element 0 of destination big integer
274  * @v dest_size Number of elements in destination big integer
275  */
276 static inline __attribute__ (( always_inline )) void
277 bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
278  uint32_t *dest0, unsigned int dest_size ) {
279  bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
280  ( ( void * ) dest0 );
281  void *discard_D;
282  void *discard_S;
283  long discard_c;
284 
285  __asm__ __volatile__ ( "rep movsl\n\t"
286  : "=&D" ( discard_D ), "=&S" ( discard_S ),
287  "=&c" ( discard_c ), "+m" ( *dest )
288  : "0" ( dest0 ), "1" ( source0 ),
289  "2" ( dest_size )
290  : "eax" );
291 }
292 
293 /**
294  * Finalise big integer
295  *
296  * @v value0 Element 0 of big integer to finalise
297  * @v size Number of elements
298  * @v out Output buffer
299  * @v len Length of output buffer
300  */
301 static inline __attribute__ (( always_inline )) void
302 bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
303  void *out, size_t len ) {
304  struct {
305  uint8_t bytes[len];
306  } __attribute__ (( may_alias )) *out_bytes = out;
307  void *discard_D;
308  long discard_c;
309 
310  /* Copy raw data in reverse order */
311  __asm__ __volatile__ ( "\n1:\n\t"
312  "movb -1(%3,%1), %%al\n\t"
313  "stosb\n\t"
314  "loop 1b\n\t"
315  : "=&D" ( discard_D ), "=&c" ( discard_c ),
316  "+m" ( *out_bytes )
317  : "r" ( value0 ), "0" ( out ), "1" ( len )
318  : "eax" );
319 }
320 
321 /**
322  * Multiply big integer elements
323  *
324  * @v multiplicand Multiplicand element
325  * @v multiplier Multiplier element
326  * @v result Result element
327  * @v carry Carry element
328  */
329 static inline __attribute__ (( always_inline )) void
330 bigint_multiply_one ( const uint32_t multiplicand, const uint32_t multiplier,
332  uint32_t discard_a;
333 
334  __asm__ __volatile__ ( /* Perform multiplication */
335  "mull %3\n\t"
336  /* Accumulate carry */
337  "addl %5, %0\n\t"
338  "adcl $0, %1\n\t"
339  /* Accumulate result */
340  "addl %0, %2\n\t"
341  "adcl $0, %1\n\t"
342  : "=&a" ( discard_a ),
343  "=&d" ( *carry ),
344  "+m" ( *result )
345  : "g" ( multiplicand ),
346  "0" ( multiplier ),
347  "r" ( *carry ) );
348 }
349 
350 #endif /* _BITS_BIGINT_H */
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:195
int carry
Definition: bigint.h:65
void * discard_S
Definition: bigint.h:63
int bigint_max_set_bit_raw(const bigint_element_t *value0, unsigned int size)
long index
Definition: bigint.h:62
void bigint_multiply_one(const bigint_element_t multiplicand, const bigint_element_t multiplier, bigint_element_t *result, bigint_element_t *carry)
long pad_size
Definition: bigint.h:252
static uint32_t * value0
Definition: bigint.h:58
long discard_tmp
Definition: bigint.h:198
static unsigned int const void size_t len
Definition: bigint.h:27
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
static unsigned int const void * data
Definition: bigint.h:26
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
int result
Definition: bigint.h:175
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:249
int borrow
Definition: bigint.h:97
static __attribute__((always_inline)) void bigint_init_raw(uint32_t *value0
Initialise big integer.
unsigned char uint8_t
Definition: stdint.h:10
__asm__ __volatile__("\n1:\n\t" "movb -1(%3,%1), %%al\n\t" "stosb\n\t" "loop 1b\n\t" "xorl %%eax, %%eax\n\t" "mov %4, %1\n\t" "rep stosb\n\t" :"=&D"(discard_D), "=&c"(discard_c), "+m"(*value) :"r"(data), "g"(pad_len), "0"(value0), "1"(len) :"eax")
void * discard_D
Definition: bigint.h:31
unsigned int uint32_t
Definition: stdint.h:12
int bigint_shl_raw(bigint_element_t *value0, unsigned int size)
static unsigned int source_size __unused
Definition: bigint.h:277
long pad_len
Definition: bigint.h:30
__asm__(".section \".rodata\", \"a\", " PROGBITS "\n\t" "\nprivate_key_data:\n\t" ".size private_key_data, ( . - private_key_data )\n\t" ".equ private_key_len, ( . - private_key_data )\n\t" ".previous\n\t")
static const uint32_t multiplier
Port multiplier number.
Definition: bigint.h:330
static unsigned int source_size
Definition: bigint.h:248
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)
int out
Definition: bigint.h:127
int bigint_add_raw(const bigint_element_t *addend0, bigint_element_t *value0, unsigned int size)
if(len >=6 *4) __asm__ __volatile__("movsl" if(len >=5 *4) __asm__ __volatile__("movsl" if(len >=4 *4) __asm__ __volatile__("movsl" if(len >=3 *4) __asm__ __volatile__("movsl" if(len >=2 *4) __asm__ __volatile__("movsl" if(len >=1 *4) __asm__ __volatile__("movsl" if((len % 4) >=2) __asm__ __volatile__("movsw" if((len % 2) >=1) __asm__ __volatile__("movsb" return dest
Definition: string.h:150
Optimised string operations.
long discard_c
Definition: bigint.h:32
int bigint_shr_raw(bigint_element_t *value0, unsigned int size)
int bigint_subtract_raw(const bigint_element_t *subtrahend0, bigint_element_t *value0, unsigned int size)
uint8_t bytes[64]
Definition: ib_mad.h:16
int bigint_is_zero_raw(const bigint_element_t *value0, unsigned int size)
static unsigned int uint32_t * dest0
Definition: bigint.h:248
static unsigned int size
Definition: bigint.h:26
int bigint_is_geq_raw(const bigint_element_t *value0, const bigint_element_t *reference0, unsigned int size)
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.