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
bigint_init_raw(uint32_t * value0,unsigned int size,const void * data,size_t len)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
bigint_add_raw(const uint32_t * addend0,uint32_t * value0,unsigned int size)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
bigint_subtract_raw(const uint32_t * subtrahend0,uint32_t * value0,unsigned int size)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
bigint_rol_raw(uint32_t * value0,unsigned int size)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
bigint_ror_raw(uint32_t * value0,unsigned int size)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
bigint_is_zero_raw(const uint32_t * value0,unsigned int size)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
bigint_is_geq_raw(const uint32_t * value0,const uint32_t * reference0,unsigned int size)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
bigint_bit_is_set_raw(const uint32_t * value0,unsigned int size,unsigned int bit)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
bigint_max_set_bit_raw(const uint32_t * value0,unsigned int size)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
bigint_grow_raw(const uint32_t * source0,unsigned int source_size,uint32_t * dest0,unsigned int dest_size)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
bigint_shrink_raw(const uint32_t * source0,unsigned int source_size __unused,uint32_t * dest0,unsigned int dest_size)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
bigint_done_raw(const uint32_t * value0,unsigned int size __unused,void * out,size_t len)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 */
317