9 FILE_LICENCE ( GPL2_OR_LATER );
14 /** Element of a big integer */
15 typedef uint32_t bigint_element_t;
18 * Initialise big integer
20 * @v value0 Element 0 of big integer to initialise
21 * @v size Number of elements
23 * @v len Length of raw data
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 );
32 /* Copy raw data in reverse order, padding with zeros */
33 __asm__ __volatile__ ( "\n1:\n\t"
34 "movb -1(%2,%1), %%al\n\t"
37 "xorl %%eax, %%eax\n\t"
40 : "=&D" ( discard_D ), "=&c" ( discard_c )
41 : "r" ( data ), "g" ( pad_len ), "0" ( value0 ),
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
53 static inline __attribute__ (( always_inline )) void
54 bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
60 __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
63 "adcl %%eax, (%3,%0,4)\n\t"
64 "inc %0\n\t" /* Does not affect CF */
66 : "=&r" ( index ), "=&S" ( discard_S ),
68 : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
73 * Subtract big integers
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
79 static inline __attribute__ (( always_inline )) void
80 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
86 __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
89 "sbbl %%eax, (%3,%0,4)\n\t"
90 "inc %0\n\t" /* Does not affect CF */
92 : "=&r" ( index ), "=&S" ( discard_S ),
94 : "r" ( value0 ), "1" ( subtrahend0 ),
100 * Rotate big integer left
102 * @v value0 Element 0 of big integer
103 * @v size Number of elements
105 static inline __attribute__ (( always_inline )) void
106 bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
110 __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
112 "rcll $1, (%2,%0,4)\n\t"
113 "inc %0\n\t" /* Does not affect CF */
115 : "=&r" ( index ), "=&c" ( discard_c )
116 : "r" ( value0 ), "1" ( size ) );
120 * Rotate big integer right
122 * @v value0 Element 0 of big integer
123 * @v size Number of elements
125 static inline __attribute__ (( always_inline )) void
126 bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
129 __asm__ __volatile__ ( "clc\n\t"
131 "rcrl $1, -4(%1,%0,4)\n\t"
133 : "=&c" ( discard_c )
134 : "r" ( value0 ), "0" ( size ) );
138 * Test if big integer is equal to zero
140 * @v value0 Element 0 of big integer
141 * @v size Number of elements
142 * @ret is_zero Big integer is equal to zero
144 static inline __attribute__ (( always_inline, pure )) int
145 bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
150 __asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
153 : "=&a" ( result ), "=&D" ( discard_D ),
155 : "1" ( value0 ), "2" ( size ) );
160 * Compare big integers
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
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 );
179 __asm__ __volatile__ ( "std\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 ] ),
196 * Test if bit is set in big integer
198 * @v value0 Element 0 of big integer
199 * @v size Number of elements
201 * @ret is_set Bit is set
203 static inline __attribute__ (( always_inline )) int
204 bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
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] ) ) );
211 return ( value->element[index] & ( 1 << subindex ) );
215 * Find highest bit set in big integer
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)
221 static inline __attribute__ (( always_inline )) int
222 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
226 __asm__ __volatile__ ( "\n1:\n\t"
227 "bsrl -4(%2,%1,4), %0\n\t"
229 "rol %1\n\t" /* Does not affect ZF */
231 "leal 1(%k0,%k1,8), %k0\n\t"
235 : "=&r" ( result ), "=&c" ( discard_c )
236 : "r" ( value0 ), "1" ( size ) );
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
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 );
256 __asm__ __volatile__ ( "rep movsl\n\t"
257 "xorl %%eax, %%eax\n\t"
260 : "=&D" ( discard_D ), "=&S" ( discard_S ),
262 : "g" ( pad_size ), "0" ( dest0 ),
263 "1" ( source0 ), "2" ( source_size )
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
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 ) {
282 __asm__ __volatile__ ( "rep movsl\n\t"
283 : "=&D" ( discard_D ), "=&S" ( discard_S ),
285 : "0" ( dest0 ), "1" ( source0 ),
291 * Finalise big integer
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
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 ) {
304 /* Copy raw data in reverse order */
305 __asm__ __volatile__ ( "\n1:\n\t"
306 "movb -1(%2,%1), %%al\n\t"
309 : "=&D" ( discard_D ), "=&c" ( discard_c )
310 : "r" ( value0 ), "0" ( out ), "1" ( len )
314 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
315 const uint32_t *multiplier0,
316 uint32_t *value0, unsigned int size );
318 #endif /* _BITS_BIGINT_H */