lib/crypto/mpi/mpih-mul.c

Source file repositories/reference/linux-study-clean/lib/crypto/mpi/mpih-mul.c

File Facts

System
Linux kernel
Corpus path
lib/crypto/mpi/mpih-mul.c
Extension
.c
Size
13890 bytes
Lines
485
Domain
Kernel Services
Bucket
lib
Inferred role
Kernel Services: implementation source
Status
source implementation candidate

Why This File Exists

Shared kernel service surface used by multiple subsystems, including helpers, cryptography, virtualization support, and async I/O infrastructure.

Dependency Surface

Detected Declarations

Annotated Snippet

if (v_limb <= 1) {
			cy = 0;
			if (v_limb == 1)
				cy = mpihelp_add_n(prodp, prodp, up, size);
		} else
			cy = mpihelp_addmul_1(prodp, up, size, v_limb);

		prodp[size] = cy;
		prodp++;
	}

	return cy;
}

static void
mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
		mpi_size_t size, mpi_ptr_t tspace)
{
	if (size & 1) {
		/* The size is odd, and the code below doesn't handle that.
		 * Multiply the least significant (size - 1) limbs with a recursive
		 * call, and handle the most significant limb of S1 and S2
		 * separately.
		 * A slightly faster way to do this would be to make the Karatsuba
		 * code below behave as if the size were even, and let it check for
		 * odd size in the end.  I.e., in essence move this code to the end.
		 * Doing so would save us a recursive call, and potentially make the
		 * stack grow a lot less.
		 */
		mpi_size_t esize = size - 1;	/* even size */
		mpi_limb_t cy_limb;

		MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace);
		cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]);
		prodp[esize + esize] = cy_limb;
		cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]);
		prodp[esize + size] = cy_limb;
	} else {
		/* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
		 *
		 * Split U in two pieces, U1 and U0, such that
		 * U = U0 + U1*(B**n),
		 * and V in V1 and V0, such that
		 * V = V0 + V1*(B**n).
		 *
		 * UV is then computed recursively using the identity
		 *
		 *        2n   n          n                     n
		 * UV = (B  + B )U V  +  B (U -U )(V -V )  +  (B + 1)U V
		 *                1 1        1  0   0  1              0 0
		 *
		 * Where B = 2**BITS_PER_MP_LIMB.
		 */
		mpi_size_t hsize = size >> 1;
		mpi_limb_t cy;
		int negflg;

		/* Product H.      ________________  ________________
		 *                |_____U1 x V1____||____U0 x V0_____|
		 * Put result in upper part of PROD and pass low part of TSPACE
		 * as new TSPACE.
		 */
		MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize,
				  tspace);

		/* Product M.      ________________
		 *                |_(U1-U0)(V0-V1)_|
		 */
		if (mpihelp_cmp(up + hsize, up, hsize) >= 0) {
			mpihelp_sub_n(prodp, up + hsize, up, hsize);
			negflg = 0;
		} else {
			mpihelp_sub_n(prodp, up, up + hsize, hsize);
			negflg = 1;
		}
		if (mpihelp_cmp(vp + hsize, vp, hsize) >= 0) {
			mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
			negflg ^= 1;
		} else {
			mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
			/* No change of NEGFLG.  */
		}
		/* Read temporary operands from low part of PROD.
		 * Put result in low part of TSPACE using upper part of TSPACE
		 * as new TSPACE.
		 */
		MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize,
				  tspace + size);

		/* Add/copy product H. */

Annotation

Implementation Notes