1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* mpihelp-mul.c  -  MPI helper functions
18 #include "mpi-internal.h"
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()
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()
139 		 * Put result in upper part of PROD and pass low part of TSPACE  in mul_n()
146 		 *                |_(U1-U0)(V0-V1)_|  in mul_n()
162 		/* Read temporary operands from low part of PROD.  in mul_n()
163 		 * Put result in low part of TSPACE using upper part of TSPACE  in mul_n()
176 			cy -=  in mul_n()
186 		 * Read temporary operands from low part of PROD.  in mul_n()
187 		 * Put result in low part of TSPACE using upper part of TSPACE  in mul_n()
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()
273 		 * Put result in upper part of PROD and pass low part of TSPACE  in mpih_sqr_n()
279 		 *                |_(U1-U0)(U0-U1)_|  in mpih_sqr_n()
286 		/* Read temporary operands from low part of PROD.  in mpih_sqr_n()
287 		 * Put result in low part of TSPACE using upper part of TSPACE  in mpih_sqr_n()
297 		cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);  in mpih_sqr_n()
301 		 * Read temporary operands from low part of PROD.  in mpih_sqr_n()
302 		 * Put result in low part of TSPACE using upper part of TSPACE  in mpih_sqr_n()
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()
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()
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()
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()
430 	mpi_ptr_t prod_endp = prodp + usize + vsize - 1;  in mpihelp_mul()
480 		return -ENOMEM;  in mpihelp_mul()