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  */
56 static inline __attribute__ (( always_inline )) void
58  unsigned int size ) {
59  bigint_t ( size ) __attribute__ (( may_alias )) *value =
60  ( ( void * ) value0 );
61  long index;
62  void *discard_S;
63  long discard_c;
64 
65  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
66  "\n1:\n\t"
67  "lodsl\n\t"
68  "adcl %%eax, (%4,%0,4)\n\t"
69  "inc %0\n\t" /* Does not affect CF */
70  "loop 1b\n\t"
71  : "=&r" ( index ), "=&S" ( discard_S ),
72  "=&c" ( discard_c ), "+m" ( *value )
73  : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
74  : "eax" );
75 }
76 
77 /**
78  * Subtract big integers
79  *
80  * @v subtrahend0 Element 0 of big integer to subtract
81  * @v value0 Element 0 of big integer to be subtracted from
82  * @v size Number of elements
83  */
84 static inline __attribute__ (( always_inline )) void
85 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
86  unsigned int size ) {
87  bigint_t ( size ) __attribute__ (( may_alias )) *value =
88  ( ( void * ) value0 );
89  long index;
90  void *discard_S;
91  long discard_c;
92 
93  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
94  "\n1:\n\t"
95  "lodsl\n\t"
96  "sbbl %%eax, (%4,%0,4)\n\t"
97  "inc %0\n\t" /* Does not affect CF */
98  "loop 1b\n\t"
99  : "=&r" ( index ), "=&S" ( discard_S ),
100  "=&c" ( discard_c ), "+m" ( *value )
101  : "r" ( value0 ), "1" ( subtrahend0 ),
102  "2" ( size )
103  : "eax" );
104 }
105 
106 /**
107  * Rotate big integer left
108  *
109  * @v value0 Element 0 of big integer
110  * @v size Number of elements
111  */
112 static inline __attribute__ (( always_inline )) void
113 bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
114  bigint_t ( size ) __attribute__ (( may_alias )) *value =
115  ( ( void * ) value0 );
116  long index;
117  long discard_c;
118 
119  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
120  "\n1:\n\t"
121  "rcll $1, (%3,%0,4)\n\t"
122  "inc %0\n\t" /* Does not affect CF */
123  "loop 1b\n\t"
124  : "=&r" ( index ), "=&c" ( discard_c ),
125  "+m" ( *value )
126  : "r" ( value0 ), "1" ( size ) );
127 }
128 
129 /**
130  * Rotate big integer right
131  *
132  * @v value0 Element 0 of big integer
133  * @v size Number of elements
134  */
135 static inline __attribute__ (( always_inline )) void
136 bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
137  bigint_t ( size ) __attribute__ (( may_alias )) *value =
138  ( ( void * ) value0 );
139  long discard_c;
140 
141  __asm__ __volatile__ ( "clc\n\t"
142  "\n1:\n\t"
143  "rcrl $1, -4(%2,%0,4)\n\t"
144  "loop 1b\n\t"
145  : "=&c" ( discard_c ), "+m" ( *value )
146  : "r" ( value0 ), "0" ( size ) );
147 }
148 
149 /**
150  * Test if big integer is equal to zero
151  *
152  * @v value0 Element 0 of big integer
153  * @v size Number of elements
154  * @ret is_zero Big integer is equal to zero
155  */
156 static inline __attribute__ (( always_inline, pure )) int
157 bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
158  void *discard_D;
159  long discard_c;
160  int result;
161 
162  __asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
163  "repe scasl\n\t"
164  "sete %b0\n\t"
165  : "=&a" ( result ), "=&D" ( discard_D ),
166  "=&c" ( discard_c )
167  : "1" ( value0 ), "2" ( size ) );
168  return result;
169 }
170 
171 /**
172  * Compare big integers
173  *
174  * @v value0 Element 0 of big integer
175  * @v reference0 Element 0 of reference big integer
176  * @v size Number of elements
177  * @ret geq Big integer is greater than or equal to the reference
178  */
179 static inline __attribute__ (( always_inline, pure )) int
181  unsigned int size ) {
182  long discard_c;
184  int result;
185 
186  __asm__ __volatile__ ( "\n1:\n\t"
187  "movl -4(%3, %1, 4), %k2\n\t"
188  "cmpl -4(%4, %1, 4), %k2\n\t"
189  "loope 1b\n\t"
190  "setae %b0\n\t"
191  : "=q" ( result ), "=&c" ( discard_c ),
192  "=&r" ( discard_tmp )
193  : "r" ( value0 ), "r" ( reference0 ),
194  "0" ( 0 ), "1" ( size ) );
195  return result;
196 }
197 
198 /**
199  * Test if bit is set in big integer
200  *
201  * @v value0 Element 0 of big integer
202  * @v size Number of elements
203  * @v bit Bit to test
204  * @ret is_set Bit is set
205  */
206 static inline __attribute__ (( always_inline )) int
207 bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
208  unsigned int bit ) {
209  const bigint_t ( size ) __attribute__ (( may_alias )) *value =
210  ( ( const void * ) value0 );
211  unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
212  unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
213 
214  return ( value->element[index] & ( 1 << subindex ) );
215 }
216 
217 /**
218  * Find highest bit set in big integer
219  *
220  * @v value0 Element 0 of big integer
221  * @v size Number of elements
222  * @ret max_bit Highest bit set + 1 (or 0 if no bits set)
223  */
224 static inline __attribute__ (( always_inline )) int
225 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
226  long discard_c;
227  int result;
228 
229  __asm__ __volatile__ ( "\n1:\n\t"
230  "bsrl -4(%2,%1,4), %0\n\t"
231  "loopz 1b\n\t"
232  "rol %1\n\t" /* Does not affect ZF */
233  "rol %1\n\t"
234  "leal 1(%k0,%k1,8), %k0\n\t"
235  "jnz 2f\n\t"
236  "xor %0, %0\n\t"
237  "\n2:\n\t"
238  : "=&r" ( result ), "=&c" ( discard_c )
239  : "r" ( value0 ), "1" ( size ) );
240  return result;
241 }
242 
243 /**
244  * Grow big integer
245  *
246  * @v source0 Element 0 of source big integer
247  * @v source_size Number of elements in source big integer
248  * @v dest0 Element 0 of destination big integer
249  * @v dest_size Number of elements in destination big integer
250  */
251 static inline __attribute__ (( always_inline )) void
252 bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
253  uint32_t *dest0, unsigned int dest_size ) {
254  bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
255  ( ( void * ) dest0 );
257  void *discard_D;
258  void *discard_S;
259  long discard_c;
260 
261  __asm__ __volatile__ ( "rep movsl\n\t"
262  "xorl %%eax, %%eax\n\t"
263  "mov %4, %2\n\t"
264  "rep stosl\n\t"
265  : "=&D" ( discard_D ), "=&S" ( discard_S ),
266  "=&c" ( discard_c ), "+m" ( *dest )
267  : "g" ( pad_size ), "0" ( dest0 ),
268  "1" ( source0 ), "2" ( source_size )
269  : "eax" );
270 }
271 
272 /**
273  * Shrink big integer
274  *
275  * @v source0 Element 0 of source big integer
276  * @v source_size Number of elements in source big integer
277  * @v dest0 Element 0 of destination big integer
278  * @v dest_size Number of elements in destination big integer
279  */
280 static inline __attribute__ (( always_inline )) void
281 bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
282  uint32_t *dest0, unsigned int dest_size ) {
283  bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
284  ( ( void * ) dest0 );
285  void *discard_D;
286  void *discard_S;
287  long discard_c;
288 
289  __asm__ __volatile__ ( "rep movsl\n\t"
290  : "=&D" ( discard_D ), "=&S" ( discard_S ),
291  "=&c" ( discard_c ), "+m" ( *dest )
292  : "0" ( dest0 ), "1" ( source0 ),
293  "2" ( dest_size )
294  : "eax" );
295 }
296 
297 /**
298  * Finalise big integer
299  *
300  * @v value0 Element 0 of big integer to finalise
301  * @v size Number of elements
302  * @v out Output buffer
303  * @v len Length of output buffer
304  */
305 static inline __attribute__ (( always_inline )) void
306 bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
307  void *out, size_t len ) {
308  struct {
309  uint8_t bytes[len];
310  } __attribute__ (( may_alias )) *out_bytes = out;
311  void *discard_D;
312  long discard_c;
313 
314  /* Copy raw data in reverse order */
315  __asm__ __volatile__ ( "\n1:\n\t"
316  "movb -1(%3,%1), %%al\n\t"
317  "stosb\n\t"
318  "loop 1b\n\t"
319  : "=&D" ( discard_D ), "=&c" ( discard_c ),
320  "+m" ( *out_bytes )
321  : "r" ( value0 ), "0" ( out ), "1" ( len )
322  : "eax" );
323 }
324 
325 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
326  const uint32_t *multiplier0,
327  uint32_t *value0, unsigned int size );
328 
329 #endif /* _BITS_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:180
static unsigned int unsigned int bit
Definition: bigint.h:208
void * discard_S
Definition: bigint.h:62
int bigint_max_set_bit_raw(const bigint_element_t *value0, unsigned int size)
long index
Definition: bigint.h:61
void bigint_subtract_raw(const bigint_element_t *subtrahend0, bigint_element_t *value0, unsigned int size)
long pad_size
Definition: bigint.h:256
static uint32_t * value0
Definition: bigint.h:57
long discard_tmp
Definition: bigint.h:183
static unsigned int const void size_t len
Definition: bigint.h:27
void bigint_rol_raw(bigint_element_t *value0, unsigned int size)
int result
Definition: bigint.h:160
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:253
#define bigint_t(size)
Define a big-integer type.
Definition: bigint.h:17
static void * dest
Definition: strings.h:176
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
static __attribute__((always_inline)) void bigint_init_raw(uint32_t *value0
Initialise big integer.
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
int bigint_bit_is_set_raw(const bigint_element_t *value0, unsigned int size, unsigned int bit)
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
static unsigned int source_size __unused
Definition: bigint.h:281
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 unsigned int source_size
Definition: bigint.h:252
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:306
unsigned int subindex
Definition: bigint.h:212
Optimised string operations.
long discard_c
Definition: bigint.h:32
void bigint_ror_raw(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:252
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)