Lines Matching +full:up +full:- +full:to
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* mpihelp-mul.c - MPI helper functions
10 * way the data is stored; this is to support the abstraction
12 * to avoid revealing of sensitive data due to paging etc.
14 * however I decided to publish this code under the plain GPL.
18 #include "mpi-internal.h"
21 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ argument
24 mul_n_basecase(prodp, up, vp, size); \
26 mul_n(prodp, up, vp, size, tspace); \
29 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \ argument
32 mpih_sqr_n_basecase(prodp, up, size); \
34 mpih_sqr_n(prodp, up, size, tspace); \
37 /* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
42 * 1. PRODP != UP and PRODP != VP, i.e. the destination
55 mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size) in mul_n_basecase() argument
62 * stored (not added) to PROD. We also avoid a loop for zeroing. */ in mul_n_basecase()
66 MPN_COPY(prodp, up, size); in mul_n_basecase()
71 cy = mpihelp_mul_1(prodp, up, size, v_limb); in mul_n_basecase()
77 * U with one limb from V, and add it to PROD. */ in mul_n_basecase()
83 cy = mpihelp_add_n(prodp, prodp, up, size); in mul_n_basecase()
85 cy = mpihelp_addmul_1(prodp, up, size, v_limb); in mul_n_basecase()
95 mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, in mul_n() argument
100 * Multiply the least significant (size - 1) limbs with a recursive in mul_n()
103 * A slightly faster way to do this would be to make the Karatsuba in mul_n()
105 * odd size in the end. I.e., in essence move this code to the end. in mul_n()
109 mpi_size_t esize = size - 1; /* even size */ in mul_n()
112 MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace); in mul_n()
113 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]); in mul_n()
115 cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]); in mul_n()
118 /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm. in mul_n()
128 * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V in mul_n()
142 MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, in mul_n()
146 * |_(U1-U0)(V0-V1)_| in mul_n()
148 if (mpihelp_cmp(up + hsize, up, hsize) >= 0) { in mul_n()
149 mpihelp_sub_n(prodp, up + hsize, up, hsize); in mul_n()
152 mpihelp_sub_n(prodp, up, up + hsize, hsize); in mul_n()
176 cy -= in mul_n()
190 MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size); in mul_n()
207 void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size) in mpih_sqr_n_basecase() argument
214 * stored (not added) to PROD. We also avoid a loop for zeroing. */ in mpih_sqr_n_basecase()
215 v_limb = up[0]; in mpih_sqr_n_basecase()
218 MPN_COPY(prodp, up, size); in mpih_sqr_n_basecase()
223 cy_limb = mpihelp_mul_1(prodp, up, size, v_limb); in mpih_sqr_n_basecase()
229 * U with one limb from V, and add it to PROD. */ in mpih_sqr_n_basecase()
231 v_limb = up[i]; in mpih_sqr_n_basecase()
235 cy_limb = mpihelp_add_n(prodp, prodp, up, size); in mpih_sqr_n_basecase()
237 cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb); in mpih_sqr_n_basecase()
245 mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace) in mpih_sqr_n() argument
249 * Multiply the least significant (size - 1) limbs with a recursive in mpih_sqr_n()
252 * A slightly faster way to do this would be to make the Karatsuba in mpih_sqr_n()
254 * odd size in the end. I.e., in essence move this code to the end. in mpih_sqr_n()
258 mpi_size_t esize = size - 1; /* even size */ in mpih_sqr_n()
261 MPN_SQR_N_RECURSE(prodp, up, esize, tspace); in mpih_sqr_n()
262 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, up[esize]); in mpih_sqr_n()
264 cy_limb = mpihelp_addmul_1(prodp + esize, up, size, up[esize]); in mpih_sqr_n()
276 MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace); in mpih_sqr_n()
279 * |_(U1-U0)(U0-U1)_| in mpih_sqr_n()
281 if (mpihelp_cmp(up + hsize, up, hsize) >= 0) in mpih_sqr_n()
282 mpihelp_sub_n(prodp, up + hsize, up, hsize); in mpih_sqr_n()
284 mpihelp_sub_n(prodp, up, up + hsize, hsize); in mpih_sqr_n()
297 cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size); in mpih_sqr_n()
304 MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size); in mpih_sqr_n()
322 mpi_ptr_t up, mpi_size_t usize, in mpihelp_mul_karatsuba_case() argument
328 if (!ctx->tspace || ctx->tspace_size < vsize) { in mpihelp_mul_karatsuba_case()
329 if (ctx->tspace) in mpihelp_mul_karatsuba_case()
330 mpi_free_limb_space(ctx->tspace); in mpihelp_mul_karatsuba_case()
331 ctx->tspace = mpi_alloc_limb_space(2 * vsize); in mpihelp_mul_karatsuba_case()
332 if (!ctx->tspace) in mpihelp_mul_karatsuba_case()
333 return -ENOMEM; in mpihelp_mul_karatsuba_case()
334 ctx->tspace_size = vsize; in mpihelp_mul_karatsuba_case()
337 MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace); in mpihelp_mul_karatsuba_case()
340 up += vsize; in mpihelp_mul_karatsuba_case()
341 usize -= vsize; in mpihelp_mul_karatsuba_case()
343 if (!ctx->tp || ctx->tp_size < vsize) { in mpihelp_mul_karatsuba_case()
344 if (ctx->tp) in mpihelp_mul_karatsuba_case()
345 mpi_free_limb_space(ctx->tp); in mpihelp_mul_karatsuba_case()
346 ctx->tp = mpi_alloc_limb_space(2 * vsize); in mpihelp_mul_karatsuba_case()
347 if (!ctx->tp) { in mpihelp_mul_karatsuba_case()
348 if (ctx->tspace) in mpihelp_mul_karatsuba_case()
349 mpi_free_limb_space(ctx->tspace); in mpihelp_mul_karatsuba_case()
350 ctx->tspace = NULL; in mpihelp_mul_karatsuba_case()
351 return -ENOMEM; in mpihelp_mul_karatsuba_case()
353 ctx->tp_size = vsize; in mpihelp_mul_karatsuba_case()
357 MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace); in mpihelp_mul_karatsuba_case()
358 cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize); in mpihelp_mul_karatsuba_case()
359 mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize, in mpihelp_mul_karatsuba_case()
362 up += vsize; in mpihelp_mul_karatsuba_case()
363 usize -= vsize; in mpihelp_mul_karatsuba_case()
370 if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp) in mpihelp_mul_karatsuba_case()
372 return -ENOMEM; in mpihelp_mul_karatsuba_case()
374 if (!ctx->next) { in mpihelp_mul_karatsuba_case()
375 ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL); in mpihelp_mul_karatsuba_case()
376 if (!ctx->next) in mpihelp_mul_karatsuba_case()
377 return -ENOMEM; in mpihelp_mul_karatsuba_case()
379 if (mpihelp_mul_karatsuba_case(ctx->tspace, in mpihelp_mul_karatsuba_case()
381 up, usize, in mpihelp_mul_karatsuba_case()
382 ctx->next) < 0) in mpihelp_mul_karatsuba_case()
383 return -ENOMEM; in mpihelp_mul_karatsuba_case()
386 cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize); in mpihelp_mul_karatsuba_case()
387 mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy); in mpihelp_mul_karatsuba_case()
397 if (ctx->tp) in mpihelp_release_karatsuba_ctx()
398 mpi_free_limb_space(ctx->tp); in mpihelp_release_karatsuba_ctx()
399 if (ctx->tspace) in mpihelp_release_karatsuba_ctx()
400 mpi_free_limb_space(ctx->tspace); in mpihelp_release_karatsuba_ctx()
401 for (ctx = ctx->next; ctx; ctx = ctx2) { in mpihelp_release_karatsuba_ctx()
402 ctx2 = ctx->next; in mpihelp_release_karatsuba_ctx()
403 if (ctx->tp) in mpihelp_release_karatsuba_ctx()
404 mpi_free_limb_space(ctx->tp); in mpihelp_release_karatsuba_ctx()
405 if (ctx->tspace) in mpihelp_release_karatsuba_ctx()
406 mpi_free_limb_space(ctx->tspace); in mpihelp_release_karatsuba_ctx()
411 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
412 * and v (pointed to by VP, with VSIZE limbs), and store the result at
417 * NOTE: The space pointed to by PRODP is overwritten before finished
422 * 2. PRODP != UP and PRODP != VP, i.e. the destination
427 mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, in mpihelp_mul() argument
430 mpi_ptr_t prod_endp = prodp + usize + vsize - 1; in mpihelp_mul()
444 * stored (not added) to PROD. We also avoid a loop for zeroing. */ in mpihelp_mul()
448 MPN_COPY(prodp, up, usize); in mpihelp_mul()
453 cy = mpihelp_mul_1(prodp, up, usize, v_limb); in mpihelp_mul()
459 * U with one limb from V, and add it to PROD. */ in mpihelp_mul()
465 cy = mpihelp_add_n(prodp, prodp, up, in mpihelp_mul()
468 cy = mpihelp_addmul_1(prodp, up, usize, v_limb); in mpihelp_mul()
479 if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0) in mpihelp_mul()
480 return -ENOMEM; in mpihelp_mul()