Lines Matching +full:up +full:-
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* mpihelp-mul.c - MPI helper functions
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
66 MPN_COPY(prodp, up, size); in mul_n_basecase()
71 cy = mpihelp_mul_1(prodp, up, size, v_limb); 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()
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
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()
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()
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_ptr_t vp, mpi_size_t size) in mpihelp_mul_n() argument
324 if (up == vp) { in mpihelp_mul_n()
326 mpih_sqr_n_basecase(prodp, up, size); in mpihelp_mul_n()
330 mpih_sqr_n(prodp, up, size, tspace); in mpihelp_mul_n()
335 mul_n_basecase(prodp, up, vp, size); in mpihelp_mul_n()
339 mul_n(prodp, up, vp, size, tspace); in mpihelp_mul_n()
347 mpi_ptr_t up, mpi_size_t usize, in mpihelp_mul_karatsuba_case() argument
353 if (!ctx->tspace || ctx->tspace_size < vsize) { in mpihelp_mul_karatsuba_case()
354 if (ctx->tspace) in mpihelp_mul_karatsuba_case()
355 mpi_free_limb_space(ctx->tspace); in mpihelp_mul_karatsuba_case()
356 ctx->tspace = mpi_alloc_limb_space(2 * vsize); in mpihelp_mul_karatsuba_case()
357 if (!ctx->tspace) in mpihelp_mul_karatsuba_case()
358 return -ENOMEM; in mpihelp_mul_karatsuba_case()
359 ctx->tspace_size = vsize; in mpihelp_mul_karatsuba_case()
362 MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace); in mpihelp_mul_karatsuba_case()
365 up += vsize; in mpihelp_mul_karatsuba_case()
366 usize -= vsize; in mpihelp_mul_karatsuba_case()
368 if (!ctx->tp || ctx->tp_size < vsize) { in mpihelp_mul_karatsuba_case()
369 if (ctx->tp) in mpihelp_mul_karatsuba_case()
370 mpi_free_limb_space(ctx->tp); in mpihelp_mul_karatsuba_case()
371 ctx->tp = mpi_alloc_limb_space(2 * vsize); in mpihelp_mul_karatsuba_case()
372 if (!ctx->tp) { in mpihelp_mul_karatsuba_case()
373 if (ctx->tspace) in mpihelp_mul_karatsuba_case()
374 mpi_free_limb_space(ctx->tspace); in mpihelp_mul_karatsuba_case()
375 ctx->tspace = NULL; in mpihelp_mul_karatsuba_case()
376 return -ENOMEM; in mpihelp_mul_karatsuba_case()
378 ctx->tp_size = vsize; in mpihelp_mul_karatsuba_case()
382 MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace); in mpihelp_mul_karatsuba_case()
383 cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize); in mpihelp_mul_karatsuba_case()
384 mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize, in mpihelp_mul_karatsuba_case()
387 up += vsize; in mpihelp_mul_karatsuba_case()
388 usize -= vsize; in mpihelp_mul_karatsuba_case()
395 if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp) in mpihelp_mul_karatsuba_case()
397 return -ENOMEM; in mpihelp_mul_karatsuba_case()
399 if (!ctx->next) { in mpihelp_mul_karatsuba_case()
400 ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL); in mpihelp_mul_karatsuba_case()
401 if (!ctx->next) in mpihelp_mul_karatsuba_case()
402 return -ENOMEM; in mpihelp_mul_karatsuba_case()
404 if (mpihelp_mul_karatsuba_case(ctx->tspace, in mpihelp_mul_karatsuba_case()
406 up, usize, in mpihelp_mul_karatsuba_case()
407 ctx->next) < 0) in mpihelp_mul_karatsuba_case()
408 return -ENOMEM; in mpihelp_mul_karatsuba_case()
411 cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize); in mpihelp_mul_karatsuba_case()
412 mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy); in mpihelp_mul_karatsuba_case()
422 if (ctx->tp) in mpihelp_release_karatsuba_ctx()
423 mpi_free_limb_space(ctx->tp); in mpihelp_release_karatsuba_ctx()
424 if (ctx->tspace) in mpihelp_release_karatsuba_ctx()
425 mpi_free_limb_space(ctx->tspace); in mpihelp_release_karatsuba_ctx()
426 for (ctx = ctx->next; ctx; ctx = ctx2) { in mpihelp_release_karatsuba_ctx()
427 ctx2 = ctx->next; in mpihelp_release_karatsuba_ctx()
428 if (ctx->tp) in mpihelp_release_karatsuba_ctx()
429 mpi_free_limb_space(ctx->tp); in mpihelp_release_karatsuba_ctx()
430 if (ctx->tspace) in mpihelp_release_karatsuba_ctx()
431 mpi_free_limb_space(ctx->tspace); in mpihelp_release_karatsuba_ctx()
436 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
447 * 2. PRODP != UP and PRODP != VP, i.e. the destination
452 mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, in mpihelp_mul() argument
455 mpi_ptr_t prod_endp = prodp + usize + vsize - 1; in mpihelp_mul()
473 MPN_COPY(prodp, up, usize); in mpihelp_mul()
478 cy = mpihelp_mul_1(prodp, up, usize, v_limb); in mpihelp_mul()
490 cy = mpihelp_add_n(prodp, prodp, up, in mpihelp_mul()
493 cy = mpihelp_addmul_1(prodp, up, usize, v_limb); in mpihelp_mul()
504 if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0) in mpihelp_mul()
505 return -ENOMEM; in mpihelp_mul()