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