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 long discard_c;
171 long discard_tmp;
172 int result;
173
174 __asm__ __volatile__ ( "\n1:\n\t"
175 "movl -4(%3, %1, 4), %k2\n\t"
176 "cmpl -4(%4, %1, 4), %k2\n\t"
177 "loope 1b\n\t"
178 "setae %b0\n\t"
179 : "=q" ( result ), "=&c" ( discard_c ),
180 "=&r" ( discard_tmp )
181 : "r" ( value0 ), "r" ( reference0 ),
182 "0" ( 0 ), "1" ( size ) );
183 return result;
184 }
185
186 /**
187 * Test if bit is set in big integer
188 *
189 * @v value0 Element 0 of big integer
190 * @v size Number of elements
191 * @v bit Bit to test
192 * @ret is_set Bit is set
193 */
194 static inline __attribute__ (( always_inline )) int
bigint_bit_is_set_raw(const uint32_t * value0,unsigned int size,unsigned int bit)195 bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
196 unsigned int bit ) {
197 const bigint_t ( size ) __attribute__ (( may_alias )) *value =
198 ( ( const void * ) value0 );
199 unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
200 unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
201
202 return ( value->element[index] & ( 1 << subindex ) );
203 }
204
205 /**
206 * Find highest bit set in big integer
207 *
208 * @v value0 Element 0 of big integer
209 * @v size Number of elements
210 * @ret max_bit Highest bit set + 1 (or 0 if no bits set)
211 */
212 static inline __attribute__ (( always_inline )) int
bigint_max_set_bit_raw(const uint32_t * value0,unsigned int size)213 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
214 long discard_c;
215 int result;
216
217 __asm__ __volatile__ ( "\n1:\n\t"
218 "bsrl -4(%2,%1,4), %0\n\t"
219 "loopz 1b\n\t"
220 "rol %1\n\t" /* Does not affect ZF */
221 "rol %1\n\t"
222 "leal 1(%k0,%k1,8), %k0\n\t"
223 "jnz 2f\n\t"
224 "xor %0, %0\n\t"
225 "\n2:\n\t"
226 : "=&r" ( result ), "=&c" ( discard_c )
227 : "r" ( value0 ), "1" ( size ) );
228 return result;
229 }
230
231 /**
232 * Grow big integer
233 *
234 * @v source0 Element 0 of source big integer
235 * @v source_size Number of elements in source big integer
236 * @v dest0 Element 0 of destination big integer
237 * @v dest_size Number of elements in destination big integer
238 */
239 static inline __attribute__ (( always_inline )) void
bigint_grow_raw(const uint32_t * source0,unsigned int source_size,uint32_t * dest0,unsigned int dest_size)240 bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
241 uint32_t *dest0, unsigned int dest_size ) {
242 long pad_size = ( dest_size - source_size );
243 void *discard_D;
244 void *discard_S;
245 long discard_c;
246
247 __asm__ __volatile__ ( "rep movsl\n\t"
248 "xorl %%eax, %%eax\n\t"
249 "mov %3, %2\n\t"
250 "rep stosl\n\t"
251 : "=&D" ( discard_D ), "=&S" ( discard_S ),
252 "=&c" ( discard_c )
253 : "g" ( pad_size ), "0" ( dest0 ),
254 "1" ( source0 ), "2" ( source_size )
255 : "eax" );
256 }
257
258 /**
259 * Shrink big integer
260 *
261 * @v source0 Element 0 of source big integer
262 * @v source_size Number of elements in source big integer
263 * @v dest0 Element 0 of destination big integer
264 * @v dest_size Number of elements in destination big integer
265 */
266 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)267 bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
268 uint32_t *dest0, unsigned int dest_size ) {
269 void *discard_D;
270 void *discard_S;
271 long discard_c;
272
273 __asm__ __volatile__ ( "rep movsl\n\t"
274 : "=&D" ( discard_D ), "=&S" ( discard_S ),
275 "=&c" ( discard_c )
276 : "0" ( dest0 ), "1" ( source0 ),
277 "2" ( dest_size )
278 : "eax" );
279 }
280
281 /**
282 * Finalise big integer
283 *
284 * @v value0 Element 0 of big integer to finalise
285 * @v size Number of elements
286 * @v out Output buffer
287 * @v len Length of output buffer
288 */
289 static inline __attribute__ (( always_inline )) void
bigint_done_raw(const uint32_t * value0,unsigned int size __unused,void * out,size_t len)290 bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
291 void *out, size_t len ) {
292 void *discard_D;
293 long discard_c;
294
295 /* Copy raw data in reverse order */
296 __asm__ __volatile__ ( "\n1:\n\t"
297 "movb -1(%2,%1), %%al\n\t"
298 "stosb\n\t"
299 "loop 1b\n\t"
300 : "=&D" ( discard_D ), "=&c" ( discard_c )
301 : "r" ( value0 ), "0" ( out ), "1" ( len )
302 : "eax" );
303 }
304
305 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
306 const uint32_t *multiplier0,
307 uint32_t *value0, unsigned int size );
308
309 #endif /* _BITS_BIGINT_H */
310