lib/crypto/mpi/mpih-div.c

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

File Facts

System
Linux kernel
Corpus path
lib/crypto/mpi/mpih-div.c
Extension
.c
Size
13559 bytes
Lines
518
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 (normalization_steps) {
			mpi_limb_t divisor_limb_inverted;

			divisor_limb <<= normalization_steps;

			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
			 * most significant bit (with weight 2**N) implicit.
			 *
			 * Special case for DIVISOR_LIMB == 100...000.
			 */
			if (!(divisor_limb << 1))
				divisor_limb_inverted = ~(mpi_limb_t)0;
			else
				udiv_qrnnd(divisor_limb_inverted, dummy,
						-divisor_limb, 0, divisor_limb);

			n1 = dividend_ptr[dividend_size - 1];
			r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);

			/* Possible optimization:
			 * if (r == 0
			 * && divisor_limb > ((n1 << normalization_steps)
			 *		       | (dividend_ptr[dividend_size - 2] >> ...)))
			 * ...one division less...
			 */
			for (i = dividend_size - 2; i >= 0; i--) {
				n0 = dividend_ptr[i];
				UDIV_QRNND_PREINV(dummy, r, r,
						((n1 << normalization_steps)
						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
						divisor_limb, divisor_limb_inverted);
				n1 = n0;
			}
			UDIV_QRNND_PREINV(dummy, r, r,
					n1 << normalization_steps,
					divisor_limb, divisor_limb_inverted);
			return r >> normalization_steps;
		} else {
			mpi_limb_t divisor_limb_inverted;

			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
			 * most significant bit (with weight 2**N) implicit.
			 *
			 * Special case for DIVISOR_LIMB == 100...000.
			 */
			if (!(divisor_limb << 1))
				divisor_limb_inverted = ~(mpi_limb_t)0;
			else
				udiv_qrnnd(divisor_limb_inverted, dummy,
						-divisor_limb, 0, divisor_limb);

			i = dividend_size - 1;
			r = dividend_ptr[i];

			if (r >= divisor_limb)
				r = 0;
			else
				i--;

			for ( ; i >= 0; i--) {
				n0 = dividend_ptr[i];
				UDIV_QRNND_PREINV(dummy, r, r,
						n0, divisor_limb, divisor_limb_inverted);
			}
			return r;
		}
	} else {
		if (UDIV_NEEDS_NORMALIZATION) {
			int normalization_steps;

			normalization_steps = count_leading_zeros(divisor_limb);
			if (normalization_steps) {
				divisor_limb <<= normalization_steps;

				n1 = dividend_ptr[dividend_size - 1];
				r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);

				/* Possible optimization:
				 * if (r == 0
				 * && divisor_limb > ((n1 << normalization_steps)
				 *		   | (dividend_ptr[dividend_size - 2] >> ...)))
				 * ...one division less...
				 */
				for (i = dividend_size - 2; i >= 0; i--) {
					n0 = dividend_ptr[i];
					udiv_qrnnd(dummy, r, r,
						((n1 << normalization_steps)
						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),

Annotation

Implementation Notes