← 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/arm64/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/arm64/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
#include <strings.h>
 
14
 
 
15
/** Element of a big integer */
 
16
typedef uint64_t bigint_element_t;
 
17
 
 
18
/**
 
19
 * Initialise big integer
 
20
 *
 
21
 * @v value0            Element 0 of big integer to initialise
 
22
 * @v size              Number of elements
 
23
 * @v data              Raw data
 
24
 * @v len               Length of raw data
 
25
 */
 
26
static inline __attribute__ (( always_inline )) void
 
27
bigint_init_raw ( uint64_t *value0, unsigned int size,
 
28
                  const void *data, size_t len ) {
 
29
        size_t pad_len = ( sizeof ( bigint_t ( size ) ) - len );
 
30
        uint8_t *value_byte = ( ( void * ) value0 );
 
31
        const uint8_t *data_byte = ( data + len );
 
32
 
 
33
        /* Copy raw data in reverse order, padding with zeros */
 
34
        while ( len-- )
 
35
                *(value_byte++) = *(--data_byte);
 
36
        while ( pad_len-- )
 
37
                *(value_byte++) = 0;
 
38
}
 
39
 
 
40
/**
 
41
 * Add big integers
 
42
 *
 
43
 * @v addend0           Element 0 of big integer to add
 
44
 * @v value0            Element 0 of big integer to be added to
 
45
 * @v size              Number of elements
 
46
 */
 
47
static inline __attribute__ (( always_inline )) void
 
48
bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 
49
                 unsigned int size ) {
 
50
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
51
                ( ( void * ) value0 );
 
52
        uint64_t *discard_addend;
 
53
        uint64_t *discard_value;
 
54
        uint64_t discard_addend_i;
 
55
        uint64_t discard_value_i;
 
56
        unsigned int discard_size;
 
57
 
 
58
        __asm__ __volatile__ ( "cmn xzr, xzr\n\t" /* clear CF */
 
59
                               "\n1:\n\t"
 
60
                               "ldr %3, [%0], #8\n\t"
 
61
                               "ldr %4, [%1]\n\t"
 
62
                               "adcs %4, %4, %3\n\t"
 
63
                               "str %4, [%1], #8\n\t"
 
64
                               "sub %w2, %w2, #1\n\t"
 
65
                               "cbnz %w2, 1b\n\t"
 
66
                               : "=r" ( discard_addend ),
 
67
                                 "=r" ( discard_value ),
 
68
                                 "=r" ( discard_size ),
 
69
                                 "=r" ( discard_addend_i ),
 
70
                                 "=r" ( discard_value_i ),
 
71
                                 "+m" ( *value )
 
72
                               : "0" ( addend0 ), "1" ( value0 ), "2" ( size )
 
73
                               : "cc" );
 
74
}
 
75
 
 
76
/**
 
77
 * Subtract big integers
 
78
 *
 
79
 * @v subtrahend0       Element 0 of big integer to subtract
 
80
 * @v value0            Element 0 of big integer to be subtracted from
 
81
 * @v size              Number of elements
 
82
 */
 
83
static inline __attribute__ (( always_inline )) void
 
84
bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 
85
                      unsigned int size ) {
 
86
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
87
                ( ( void * ) value0 );
 
88
        uint64_t *discard_subtrahend;
 
89
        uint64_t *discard_value;
 
90
        uint64_t discard_subtrahend_i;
 
91
        uint64_t discard_value_i;
 
92
        unsigned int discard_size;
 
93
 
 
94
        __asm__ __volatile__ ( "cmp xzr, xzr\n\t" /* set CF */
 
95
                               "\n1:\n\t"
 
96
                               "ldr %3, [%0], #8\n\t"
 
97
                               "ldr %4, [%1]\n\t"
 
98
                               "sbcs %4, %4, %3\n\t"
 
99
                               "str %4, [%1], #8\n\t"
 
100
                               "sub %w2, %w2, #1\n\t"
 
101
                               "cbnz %w2, 1b\n\t"
 
102
                               : "=r" ( discard_subtrahend ),
 
103
                                 "=r" ( discard_value ),
 
104
                                 "=r" ( discard_size ),
 
105
                                 "=r" ( discard_subtrahend_i ),
 
106
                                 "=r" ( discard_value_i ),
 
107
                                 "+m" ( *value )
 
108
                               : "0" ( subtrahend0 ), "1" ( value0 ),
 
109
                                 "2" ( size )
 
110
                               : "cc" );
 
111
}
 
112
 
 
113
/**
 
114
 * Rotate big integer left
 
115
 *
 
116
 * @v value0            Element 0 of big integer
 
117
 * @v size              Number of elements
 
118
 */
 
119
static inline __attribute__ (( always_inline )) void
 
120
bigint_rol_raw ( uint64_t *value0, unsigned int size ) {
 
121
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
122
                ( ( void * ) value0 );
 
123
        uint64_t *discard_value;
 
124
        uint64_t discard_value_i;
 
125
        unsigned int discard_size;
 
126
 
 
127
        __asm__ __volatile__ ( "cmn xzr, xzr\n\t" /* clear CF */
 
128
                               "\n1:\n\t"
 
129
                               "ldr %2, [%0]\n\t"
 
130
                               "adcs %2, %2, %2\n\t"
 
131
                               "str %2, [%0], #8\n\t"
 
132
                               "sub %w1, %w1, #1\n\t"
 
133
                               "cbnz %w1, 1b\n\t"
 
134
                               : "=r" ( discard_value ),
 
135
                                 "=r" ( discard_size ),
 
136
                                 "=r" ( discard_value_i ),
 
137
                                 "+m" ( *value )
 
138
                               : "0" ( value0 ), "1" ( size )
 
139
                               : "cc" );
 
140
}
 
141
 
 
142
/**
 
143
 * Rotate big integer right
 
144
 *
 
145
 * @v value0            Element 0 of big integer
 
146
 * @v size              Number of elements
 
147
 */
 
148
static inline __attribute__ (( always_inline )) void
 
149
bigint_ror_raw ( uint64_t *value0, unsigned int size ) {
 
150
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
151
                ( ( void * ) value0 );
 
152
        uint64_t *discard_value;
 
153
        uint64_t discard_value_i;
 
154
        uint64_t discard_value_j;
 
155
        unsigned int discard_size;
 
156
 
 
157
        __asm__ __volatile__ ( "mov %3, #0\n\t"
 
158
                               "\n1:\n\t"
 
159
                               "sub %w1, %w1, #1\n\t"
 
160
                               "ldr %2, [%0, %1, lsl #3]\n\t"
 
161
                               "extr %3, %3, %2, #1\n\t"
 
162
                               "str %3, [%0, %1, lsl #3]\n\t"
 
163
                               "mov %3, %2\n\t"
 
164
                               "cbnz %w1, 1b\n\t"
 
165
                               : "=r" ( discard_value ),
 
166
                                 "=r" ( discard_size ),
 
167
                                 "=r" ( discard_value_i ),
 
168
                                 "=r" ( discard_value_j ),
 
169
                                 "+m" ( *value )
 
170
                               : "0" ( value0 ), "1" ( size ) );
 
171
}
 
172
 
 
173
/**
 
174
 * Test if big integer is equal to zero
 
175
 *
 
176
 * @v value0            Element 0 of big integer
 
177
 * @v size              Number of elements
 
178
 * @ret is_zero         Big integer is equal to zero
 
179
 */
 
180
static inline __attribute__ (( always_inline, pure )) int
 
181
bigint_is_zero_raw ( const uint64_t *value0, unsigned int size ) {
 
182
        const uint64_t *value = value0;
 
183
        uint64_t value_i;
 
184
 
 
185
        do {
 
186
                value_i = *(value++);
 
187
                if ( value_i )
 
188
                        break;
 
189
        } while ( --size );
 
190
 
 
191
        return ( value_i == 0 );
 
192
}
 
193
 
 
194
/**
 
195
 * Compare big integers
 
196
 *
 
197
 * @v value0            Element 0 of big integer
 
198
 * @v reference0        Element 0 of reference big integer
 
199
 * @v size              Number of elements
 
200
 * @ret geq             Big integer is greater than or equal to the reference
 
201
 */
 
202
static inline __attribute__ (( always_inline, pure )) int
 
203
bigint_is_geq_raw ( const uint64_t *value0, const uint64_t *reference0,
 
204
                    unsigned int size ) {
 
205
        const uint64_t *value = ( value0 + size );
 
206
        const uint64_t *reference = ( reference0 + size );
 
207
        uint64_t value_i;
 
208
        uint64_t reference_i;
 
209
 
 
210
        do {
 
211
                value_i = *(--value);
 
212
                reference_i = *(--reference);
 
213
                if ( value_i != reference_i )
 
214
                        break;
 
215
        } while ( --size );
 
216
 
 
217
        return ( value_i >= reference_i );
 
218
}
 
219
 
 
220
/**
 
221
 * Test if bit is set in big integer
 
222
 *
 
223
 * @v value0            Element 0 of big integer
 
224
 * @v size              Number of elements
 
225
 * @v bit               Bit to test
 
226
 * @ret is_set          Bit is set
 
227
 */
 
228
static inline __attribute__ (( always_inline )) int
 
229
bigint_bit_is_set_raw ( const uint64_t *value0, unsigned int size,
 
230
                        unsigned int bit ) {
 
231
        const bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
232
                ( ( const void * ) value0 );
 
233
        unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
 
234
        unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
 
235
 
 
236
        return ( !! ( value->element[index] & ( 1UL << subindex ) ) );
 
237
}
 
238
 
 
239
/**
 
240
 * Find highest bit set in big integer
 
241
 *
 
242
 * @v value0            Element 0 of big integer
 
243
 * @v size              Number of elements
 
244
 * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
 
245
 */
 
246
static inline __attribute__ (( always_inline )) int
 
247
bigint_max_set_bit_raw ( const uint64_t *value0, unsigned int size ) {
 
248
        const uint64_t *value = ( value0 + size );
 
249
        int max_bit = ( 8 * sizeof ( bigint_t ( size ) ) );
 
250
        uint64_t value_i;
 
251
 
 
252
        do {
 
253
                value_i = *(--value);
 
254
                max_bit -= ( 64 - fls ( value_i ) );
 
255
                if ( value_i )
 
256
                        break;
 
257
        } while ( --size );
 
258
 
 
259
        return max_bit;
 
260
}
 
261
 
 
262
/**
 
263
 * Grow big integer
 
264
 *
 
265
 * @v source0           Element 0 of source big integer
 
266
 * @v source_size       Number of elements in source big integer
 
267
 * @v dest0             Element 0 of destination big integer
 
268
 * @v dest_size         Number of elements in destination big integer
 
269
 */
 
270
static inline __attribute__ (( always_inline )) void
 
271
bigint_grow_raw ( const uint64_t *source0, unsigned int source_size,
 
272
                  uint64_t *dest0, unsigned int dest_size ) {
 
273
        unsigned int pad_size = ( dest_size - source_size );
 
274
 
 
275
        memcpy ( dest0, source0, sizeof ( bigint_t ( source_size ) ) );
 
276
        memset ( ( dest0 + source_size ), 0, sizeof ( bigint_t ( pad_size ) ) );
 
277
}
 
278
 
 
279
/**
 
280
 * Shrink big integer
 
281
 *
 
282
 * @v source0           Element 0 of source big integer
 
283
 * @v source_size       Number of elements in source big integer
 
284
 * @v dest0             Element 0 of destination big integer
 
285
 * @v dest_size         Number of elements in destination big integer
 
286
 */
 
287
static inline __attribute__ (( always_inline )) void
 
288
bigint_shrink_raw ( const uint64_t *source0, unsigned int source_size __unused,
 
289
                    uint64_t *dest0, unsigned int dest_size ) {
 
290
 
 
291
        memcpy ( dest0, source0, sizeof ( bigint_t ( dest_size ) ) );
 
292
}
 
293
 
 
294
/**
 
295
 * Finalise big integer
 
296
 *
 
297
 * @v value0            Element 0 of big integer to finalise
 
298
 * @v size              Number of elements
 
299
 * @v out               Output buffer
 
300
 * @v len               Length of output buffer
 
301
 */
 
302
static inline __attribute__ (( always_inline )) void
 
303
bigint_done_raw ( const uint64_t *value0, unsigned int size __unused,
 
304
                  void *out, size_t len ) {
 
305
        const uint8_t *value_byte = ( ( const void * ) value0 );
 
306
        uint8_t *out_byte = ( out + len );
 
307
 
 
308
        /* Copy raw data in reverse order */
 
309
        while ( len-- )
 
310
                *(--out_byte) = *(value_byte++);
 
311
}
 
312
 
 
313
extern void bigint_multiply_raw ( const uint64_t *multiplicand0,
 
314
                                  const uint64_t *multiplier0,
 
315
                                  uint64_t *value0, unsigned int size );
 
316
 
 
317
#endif /* _BITS_BIGINT_H */