1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include <linux/string.h>
31#include "mpi-internal.h"
32#include "longlong.h"
33
34#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
35 do { \
36 if ((size) < KARATSUBA_THRESHOLD) \
37 mul_n_basecase(prodp, up, vp, size); \
38 else \
39 mul_n(prodp, up, vp, size, tspace); \
40 } while (0);
41
42#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
43 do { \
44 if ((size) < KARATSUBA_THRESHOLD) \
45 mpih_sqr_n_basecase(prodp, up, size); \
46 else \
47 mpih_sqr_n(prodp, up, size, tspace); \
48 } while (0);
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67static mpi_limb_t
68mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
69{
70 mpi_size_t i;
71 mpi_limb_t cy;
72 mpi_limb_t v_limb;
73
74
75
76 v_limb = vp[0];
77 if (v_limb <= 1) {
78 if (v_limb == 1)
79 MPN_COPY(prodp, up, size);
80 else
81 MPN_ZERO(prodp, size);
82 cy = 0;
83 } else
84 cy = mpihelp_mul_1(prodp, up, size, v_limb);
85
86 prodp[size] = cy;
87 prodp++;
88
89
90
91 for (i = 1; i < size; i++) {
92 v_limb = vp[i];
93 if (v_limb <= 1) {
94 cy = 0;
95 if (v_limb == 1)
96 cy = mpihelp_add_n(prodp, prodp, up, size);
97 } else
98 cy = mpihelp_addmul_1(prodp, up, size, v_limb);
99
100 prodp[size] = cy;
101 prodp++;
102 }
103
104 return cy;
105}
106
107static void
108mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
109 mpi_size_t size, mpi_ptr_t tspace)
110{
111 if (size & 1) {
112
113
114
115
116
117
118
119
120
121
122 mpi_size_t esize = size - 1;
123 mpi_limb_t cy_limb;
124
125 MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace);
126 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]);
127 prodp[esize + esize] = cy_limb;
128 cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]);
129 prodp[esize + size] = cy_limb;
130 } else {
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146 mpi_size_t hsize = size >> 1;
147 mpi_limb_t cy;
148 int negflg;
149
150
151
152
153
154
155 MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize,
156 tspace);
157
158
159
160
161 if (mpihelp_cmp(up + hsize, up, hsize) >= 0) {
162 mpihelp_sub_n(prodp, up + hsize, up, hsize);
163 negflg = 0;
164 } else {
165 mpihelp_sub_n(prodp, up, up + hsize, hsize);
166 negflg = 1;
167 }
168 if (mpihelp_cmp(vp + hsize, vp, hsize) >= 0) {
169 mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
170 negflg ^= 1;
171 } else {
172 mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
173
174 }
175
176
177
178
179 MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize,
180 tspace + size);
181
182
183 MPN_COPY(prodp + hsize, prodp + size, hsize);
184 cy = mpihelp_add_n(prodp + size, prodp + size,
185 prodp + size + hsize, hsize);
186
187
188 if (negflg)
189 cy -=
190 mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace,
191 size);
192 else
193 cy +=
194 mpihelp_add_n(prodp + hsize, prodp + hsize, tspace,
195 size);
196
197
198
199
200
201
202
203 MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
204
205
206
207 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
208 if (cy)
209 mpihelp_add_1(prodp + hsize + size,
210 prodp + hsize + size, hsize, cy);
211
212 MPN_COPY(prodp, tspace, hsize);
213 cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
214 hsize);
215 if (cy)
216 mpihelp_add_1(prodp + size, prodp + size, size, 1);
217 }
218}
219
220void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size)
221{
222 mpi_size_t i;
223 mpi_limb_t cy_limb;
224 mpi_limb_t v_limb;
225
226
227
228 v_limb = up[0];
229 if (v_limb <= 1) {
230 if (v_limb == 1)
231 MPN_COPY(prodp, up, size);
232 else
233 MPN_ZERO(prodp, size);
234 cy_limb = 0;
235 } else
236 cy_limb = mpihelp_mul_1(prodp, up, size, v_limb);
237
238 prodp[size] = cy_limb;
239 prodp++;
240
241
242
243 for (i = 1; i < size; i++) {
244 v_limb = up[i];
245 if (v_limb <= 1) {
246 cy_limb = 0;
247 if (v_limb == 1)
248 cy_limb = mpihelp_add_n(prodp, prodp, up, size);
249 } else
250 cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
251
252 prodp[size] = cy_limb;
253 prodp++;
254 }
255}
256
257void
258mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
259{
260 if (size & 1) {
261
262
263
264
265
266
267
268
269
270
271 mpi_size_t esize = size - 1;
272 mpi_limb_t cy_limb;
273
274 MPN_SQR_N_RECURSE(prodp, up, esize, tspace);
275 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, up[esize]);
276 prodp[esize + esize] = cy_limb;
277 cy_limb = mpihelp_addmul_1(prodp + esize, up, size, up[esize]);
278
279 prodp[esize + size] = cy_limb;
280 } else {
281 mpi_size_t hsize = size >> 1;
282 mpi_limb_t cy;
283
284
285
286
287
288
289 MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
290
291
292
293
294 if (mpihelp_cmp(up + hsize, up, hsize) >= 0)
295 mpihelp_sub_n(prodp, up + hsize, up, hsize);
296 else
297 mpihelp_sub_n(prodp, up, up + hsize, hsize);
298
299
300
301
302 MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
303
304
305 MPN_COPY(prodp + hsize, prodp + size, hsize);
306 cy = mpihelp_add_n(prodp + size, prodp + size,
307 prodp + size + hsize, hsize);
308
309
310 cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
311
312
313
314
315
316
317 MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size);
318
319
320 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
321 if (cy)
322 mpihelp_add_1(prodp + hsize + size,
323 prodp + hsize + size, hsize, cy);
324
325 MPN_COPY(prodp, tspace, hsize);
326 cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
327 hsize);
328 if (cy)
329 mpihelp_add_1(prodp + size, prodp + size, size, 1);
330 }
331}
332
333int
334mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
335 mpi_ptr_t up, mpi_size_t usize,
336 mpi_ptr_t vp, mpi_size_t vsize,
337 struct karatsuba_ctx *ctx)
338{
339 mpi_limb_t cy;
340
341 if (!ctx->tspace || ctx->tspace_size < vsize) {
342 if (ctx->tspace)
343 mpi_free_limb_space(ctx->tspace);
344 ctx->tspace = mpi_alloc_limb_space(2 * vsize);
345 if (!ctx->tspace)
346 return -ENOMEM;
347 ctx->tspace_size = vsize;
348 }
349
350 MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace);
351
352 prodp += vsize;
353 up += vsize;
354 usize -= vsize;
355 if (usize >= vsize) {
356 if (!ctx->tp || ctx->tp_size < vsize) {
357 if (ctx->tp)
358 mpi_free_limb_space(ctx->tp);
359 ctx->tp = mpi_alloc_limb_space(2 * vsize);
360 if (!ctx->tp) {
361 if (ctx->tspace)
362 mpi_free_limb_space(ctx->tspace);
363 ctx->tspace = NULL;
364 return -ENOMEM;
365 }
366 ctx->tp_size = vsize;
367 }
368
369 do {
370 MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace);
371 cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize);
372 mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize,
373 cy);
374 prodp += vsize;
375 up += vsize;
376 usize -= vsize;
377 } while (usize >= vsize);
378 }
379
380 if (usize) {
381 if (usize < KARATSUBA_THRESHOLD) {
382 mpi_limb_t tmp;
383 if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp)
384 < 0)
385 return -ENOMEM;
386 } else {
387 if (!ctx->next) {
388 ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL);
389 if (!ctx->next)
390 return -ENOMEM;
391 }
392 if (mpihelp_mul_karatsuba_case(ctx->tspace,
393 vp, vsize,
394 up, usize,
395 ctx->next) < 0)
396 return -ENOMEM;
397 }
398
399 cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize);
400 mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy);
401 }
402
403 return 0;
404}
405
406void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx)
407{
408 struct karatsuba_ctx *ctx2;
409
410 if (ctx->tp)
411 mpi_free_limb_space(ctx->tp);
412 if (ctx->tspace)
413 mpi_free_limb_space(ctx->tspace);
414 for (ctx = ctx->next; ctx; ctx = ctx2) {
415 ctx2 = ctx->next;
416 if (ctx->tp)
417 mpi_free_limb_space(ctx->tp);
418 if (ctx->tspace)
419 mpi_free_limb_space(ctx->tspace);
420 kfree(ctx);
421 }
422}
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439int
440mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
441 mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result)
442{
443 mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
444 mpi_limb_t cy;
445 struct karatsuba_ctx ctx;
446
447 if (vsize < KARATSUBA_THRESHOLD) {
448 mpi_size_t i;
449 mpi_limb_t v_limb;
450
451 if (!vsize) {
452 *_result = 0;
453 return 0;
454 }
455
456
457
458 v_limb = vp[0];
459 if (v_limb <= 1) {
460 if (v_limb == 1)
461 MPN_COPY(prodp, up, usize);
462 else
463 MPN_ZERO(prodp, usize);
464 cy = 0;
465 } else
466 cy = mpihelp_mul_1(prodp, up, usize, v_limb);
467
468 prodp[usize] = cy;
469 prodp++;
470
471
472
473 for (i = 1; i < vsize; i++) {
474 v_limb = vp[i];
475 if (v_limb <= 1) {
476 cy = 0;
477 if (v_limb == 1)
478 cy = mpihelp_add_n(prodp, prodp, up,
479 usize);
480 } else
481 cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
482
483 prodp[usize] = cy;
484 prodp++;
485 }
486
487 *_result = cy;
488 return 0;
489 }
490
491 memset(&ctx, 0, sizeof ctx);
492 if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0)
493 return -ENOMEM;
494 mpihelp_release_karatsuba_ctx(&ctx);
495 *_result = *prod_endp;
496 return 0;
497}
498