← Back to branch summary

~pmdj/ubuntu/trusty/qemu/2.9+applesmc+fadtv3

« back to all changes in this revision

Viewing changes to roms/ipxe/src/arch/x86/include/bits/bigint.h

  • Committer: Phil Dennis-Jordan
  • Date: 2017-07-21 08:03:43 UTC
  • mfrom: (1.1.1)
  • Revision ID: phil@philjordan.eu-20170721080343-2yr2vdj7713czahv
New upstream release 2.9.0.

Show diffs side-by-side

added added

removed removed

Lines of Context:
roms/ipxe/src/arch/x86/include/bits/bigint.h
 
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 */
 
15
typedef uint32_t bigint_element_t;
 
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
 
26
bigint_init_raw ( uint32_t *value0, unsigned int size,
 
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
 
54
bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 
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
 
168
bigint_is_geq_raw ( const uint32_t *value0, const uint32_t *reference0,
 
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 */