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