← 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/arm32/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/arm32/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 uint32_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 ( uint32_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 uint32_t *addend0, uint32_t *value0,
 
49
                 unsigned int size ) {
 
50
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
51
                ( ( void * ) value0 );
 
52
        uint32_t *discard_addend;
 
53
        uint32_t *discard_value;
 
54
        uint32_t *discard_end;
 
55
        uint32_t discard_addend_i;
 
56
        uint32_t discard_value_i;
 
57
 
 
58
        __asm__ __volatile__ ( "adds %2, %0, %8, lsl #2\n\t" /* clear CF */
 
59
                               "\n1:\n\t"
 
60
                               "ldmia %0!, {%3}\n\t"
 
61
                               "ldr %4, [%1]\n\t"
 
62
                               "adcs %4, %3\n\t"
 
63
                               "stmia %1!, {%4}\n\t"
 
64
                               "teq %0, %2\n\t"
 
65
                               "bne 1b\n\t"
 
66
                               : "=l" ( discard_addend ),
 
67
                                 "=l" ( discard_value ),
 
68
                                 "=l" ( discard_end ),
 
69
                                 "=l" ( discard_addend_i ),
 
70
                                 "=l" ( discard_value_i ),
 
71
                                 "+m" ( *value )
 
72
                               : "0" ( addend0 ), "1" ( value0 ), "l" ( 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 uint32_t *subtrahend0, uint32_t *value0,
 
85
                      unsigned int size ) {
 
86
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
87
                ( ( void * ) value0 );
 
88
        uint32_t *discard_subtrahend;
 
89
        uint32_t *discard_value;
 
90
        uint32_t *discard_end;
 
91
        uint32_t discard_subtrahend_i;
 
92
        uint32_t discard_value_i;
 
93
 
 
94
        __asm__ __volatile__ ( "add %2, %0, %8, lsl #2\n\t"
 
95
                               "cmp %2, %0\n\t" /* set CF */
 
96
                               "\n1:\n\t"
 
97
                               "ldmia %0!, {%3}\n\t"
 
98
                               "ldr %4, [%1]\n\t"
 
99
                               "sbcs %4, %3\n\t"
 
100
                               "stmia %1!, {%4}\n\t"
 
101
                               "teq %0, %2\n\t"
 
102
                               "bne 1b\n\t"
 
103
                               : "=l" ( discard_subtrahend ),
 
104
                                 "=l" ( discard_value ),
 
105
                                 "=l" ( discard_end ),
 
106
                                 "=l" ( discard_subtrahend_i ),
 
107
                                 "=l" ( discard_value_i ),
 
108
                                 "+m" ( *value )
 
109
                               : "0" ( subtrahend0 ), "1" ( value0 ),
 
110
                                 "l" ( size )
 
111
                               : "cc" );
 
112
}
 
113
 
 
114
/**
 
115
 * Rotate big integer left
 
116
 *
 
117
 * @v value0            Element 0 of big integer
 
118
 * @v size              Number of elements
 
119
 */
 
120
static inline __attribute__ (( always_inline )) void
 
121
bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
 
122
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
123
                ( ( void * ) value0 );
 
124
        uint32_t *discard_value;
 
125
        uint32_t *discard_end;
 
126
        uint32_t discard_value_i;
 
127
 
 
128
        __asm__ __volatile__ ( "adds %1, %0, %5, lsl #2\n\t" /* clear CF */
 
129
                               "\n1:\n\t"
 
130
                               "ldr %2, [%0]\n\t"
 
131
                               "adcs %2, %2\n\t"
 
132
                               "stmia %0!, {%2}\n\t"
 
133
                               "teq %0, %1\n\t"
 
134
                               "bne 1b\n\t"
 
135
                               : "=l" ( discard_value ),
 
136
                                 "=l" ( discard_end ),
 
137
                                 "=l" ( discard_value_i ),
 
138
                                 "+m" ( *value )
 
139
                               : "0" ( value0 ), "1" ( size )
 
140
                               : "cc" );
 
141
}
 
142
 
 
143
/**
 
144
 * Rotate big integer right
 
145
 *
 
146
 * @v value0            Element 0 of big integer
 
147
 * @v size              Number of elements
 
148
 */
 
149
static inline __attribute__ (( always_inline )) void
 
150
bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
 
151
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
152
                ( ( void * ) value0 );
 
153
        uint32_t *discard_value;
 
154
        uint32_t *discard_end;
 
155
        uint32_t discard_value_i;
 
156
 
 
157
        __asm__ __volatile__ ( "adds %1, %0, %5, lsl #2\n\t" /* clear CF */
 
158
                               "\n1:\n\t"
 
159
                               "ldmdb %1!, {%2}\n\t"
 
160
                               "rrxs %2, %2\n\t"
 
161
                               "str %2, [%1]\n\t"
 
162
                               "teq %0, %1\n\t"
 
163
                               "bne 1b\n\t"
 
164
                               : "=l" ( discard_value ),
 
165
                                 "=l" ( discard_end ),
 
166
                                 "=l" ( discard_value_i ),
 
167
                                 "+m" ( *value )
 
168
                               : "0" ( value0 ), "1" ( size )
 
169
                               : "cc" );
 
170
}
 
171
 
 
172
/**
 
173
 * Test if big integer is equal to zero
 
174
 *
 
175
 * @v value0            Element 0 of big integer
 
176
 * @v size              Number of elements
 
177
 * @ret is_zero         Big integer is equal to zero
 
178
 */
 
179
static inline __attribute__ (( always_inline, pure )) int
 
180
bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
 
181
        const uint32_t *value = value0;
 
182
        uint32_t value_i;
 
183
 
 
184
        do {
 
185
                value_i = *(value++);
 
186
                if ( value_i )
 
187
                        break;
 
188
        } while ( --size );
 
189
 
 
190
        return ( value_i == 0 );
 
191
}
 
192
 
 
193
/**
 
194
 * Compare big integers
 
195
 *
 
196
 * @v value0            Element 0 of big integer
 
197
 * @v reference0        Element 0 of reference big integer
 
198
 * @v size              Number of elements
 
199
 * @ret geq             Big integer is greater than or equal to the reference
 
200
 */
 
201
static inline __attribute__ (( always_inline, pure )) int
 
202
bigint_is_geq_raw ( const uint32_t *value0, const uint32_t *reference0,
 
203
                    unsigned int size ) {
 
204
        const uint32_t *value = ( value0 + size );
 
205
        const uint32_t *reference = ( reference0 + size );
 
206
        uint32_t value_i;
 
207
        uint32_t reference_i;
 
208
 
 
209
        do {
 
210
                value_i = *(--value);
 
211
                reference_i = *(--reference);
 
212
                if ( value_i != reference_i )
 
213
                        break;
 
214
        } while ( --size );
 
215
 
 
216
        return ( value_i >= reference_i );
 
217
}
 
218
 
 
219
/**
 
220
 * Test if bit is set in big integer
 
221
 *
 
222
 * @v value0            Element 0 of big integer
 
223
 * @v size              Number of elements
 
224
 * @v bit               Bit to test
 
225
 * @ret is_set          Bit is set
 
226
 */
 
227
static inline __attribute__ (( always_inline )) int
 
228
bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
 
229
                        unsigned int bit ) {
 
230
        const bigint_t ( size ) __attribute__ (( may_alias )) *value =
 
231
                ( ( const void * ) value0 );
 
232
        unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
 
233
        unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
 
234
 
 
235
        return ( value->element[index] & ( 1 << subindex ) );
 
236
}
 
237
 
 
238
/**
 
239
 * Find highest bit set in big integer
 
240
 *
 
241
 * @v value0            Element 0 of big integer
 
242
 * @v size              Number of elements
 
243
 * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
 
244
 */
 
245
static inline __attribute__ (( always_inline )) int
 
246
bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
 
247
        const uint32_t *value = ( value0 + size );
 
248
        int max_bit = ( 8 * sizeof ( bigint_t ( size ) ) );
 
249
        uint32_t value_i;
 
250
 
 
251
        do {
 
252
                value_i = *(--value);
 
253
                max_bit -= ( 32 - fls ( value_i ) );
 
254
                if ( value_i )
 
255
                        break;
 
256
        } while ( --size );
 
257
 
 
258
        return max_bit;
 
259
}
 
260
 
 
261
/**
 
262
 * Grow big integer
 
263
 *
 
264
 * @v source0           Element 0 of source big integer
 
265
 * @v source_size       Number of elements in source big integer
 
266
 * @v dest0             Element 0 of destination big integer
 
267
 * @v dest_size         Number of elements in destination big integer
 
268
 */
 
269
static inline __attribute__ (( always_inline )) void
 
270
bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
 
271
                  uint32_t *dest0, unsigned int dest_size ) {
 
272
        unsigned int pad_size = ( dest_size - source_size );
 
273
 
 
274
        memcpy ( dest0, source0, sizeof ( bigint_t ( source_size ) ) );
 
275
        memset ( ( dest0 + source_size ), 0, sizeof ( bigint_t ( pad_size ) ) );
 
276
}
 
277
 
 
278
/**
 
279
 * Shrink big integer
 
280
 *
 
281
 * @v source0           Element 0 of source big integer
 
282
 * @v source_size       Number of elements in source big integer
 
283
 * @v dest0             Element 0 of destination big integer
 
284
 * @v dest_size         Number of elements in destination big integer
 
285
 */
 
286
static inline __attribute__ (( always_inline )) void
 
287
bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
 
288
                    uint32_t *dest0, unsigned int dest_size ) {
 
289
 
 
290
        memcpy ( dest0, source0, sizeof ( bigint_t ( dest_size ) ) );
 
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
        const uint8_t *value_byte = ( ( const void * ) value0 );
 
305
        uint8_t *out_byte = ( out + len );
 
306
 
 
307
        /* Copy raw data in reverse order */
 
308
        while ( len-- )
 
309
                *(--out_byte) = *(value_byte++);
 
310
}
 
311
 
 
312
extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
 
313
                                  const uint32_t *multiplier0,
 
314
                                  uint32_t *value0, unsigned int size );
 
315
 
 
316
#endif /* _BITS_BIGINT_H */