arch/generic/mul_n.c

54 impn_mul_n_basecase (mp_ptr prodp, mp_srcptr up, mp_srcptr vp, mp_size_t size)
56 impn_mul_n_basecase (prodp, up, vp, size)
60      mp_size_t size;
73 	MPN_COPY (prodp, up, size);
75 	MPN_ZERO (prodp, size);
79     cy_limb = mpn_mul_1 (prodp, up, size, v_limb);
81   prodp[size] = cy_limb;
86   for (i = 1; i < size; i++)
93 	    cy_limb = mpn_add_n (prodp, prodp, up, size);
96 	cy_limb = mpn_addmul_1 (prodp, up, size, v_limb);
98       prodp[size] = cy_limb;
106 	     mp_srcptr up, mp_srcptr vp, mp_size_t size, mp_ptr tspace)
108 impn_mul_n (prodp, up, vp, size, tspace)
112      mp_size_t size;
116   if ((size & 1) != 0)
118       /* The size is odd, the code code below doesn't handle that.
119 	 Multiply the least significant (size - 1) limbs with a recursive
123 	 code below behave as if the size were even, and let it check for
124 	 odd size in the end.  I.e., in essence move this code to the end.
128       mp_size_t esize = size - 1;	/* even size */
134       cy_limb = mpn_addmul_1 (prodp + esize, vp, size, up[esize]);
136       prodp[esize + size] = cy_limb;
155       mp_size_t hsize = size >> 1;
163       MPN_MUL_N_RECURSE (prodp + size, up + hsize, vp + hsize, hsize, tspace);
190       MPN_MUL_N_RECURSE (tspace, prodp, prodp + hsize, hsize, tspace + size);
193       MPN_COPY (prodp + hsize, prodp + size, hsize);
194       cy = mpn_add_n (prodp + size, prodp + size, prodp + size + hsize, hsize);
198 	cy -= mpn_sub_n (prodp + hsize, prodp + hsize, tspace, size);
200 	cy += mpn_add_n (prodp + hsize, prodp + hsize, tspace, size);
207       MPN_MUL_N_RECURSE (tspace, up, vp, hsize, tspace + size);
211       cy += mpn_add_n (prodp + hsize, prodp + hsize, tspace, size);
213 	mpn_add_1 (prodp + hsize + size, prodp + hsize + size, hsize, cy);
218 	mpn_add_1 (prodp + size, prodp + size, size, 1);
224 impn_sqr_n_basecase (mp_ptr prodp, mp_srcptr up, mp_size_t size)
226 impn_sqr_n_basecase (prodp, up, size)
229      mp_size_t size;
242 	MPN_COPY (prodp, up, size);
244 	MPN_ZERO (prodp, size);
248     cy_limb = mpn_mul_1 (prodp, up, size, v_limb);
250   prodp[size] = cy_limb;
255   for (i = 1; i < size; i++)
262 	    cy_limb = mpn_add_n (prodp, prodp, up, size);
265 	cy_limb = mpn_addmul_1 (prodp, up, size, v_limb);
267       prodp[size] = cy_limb;
275 	     mp_srcptr up, mp_size_t size, mp_ptr tspace)
277 impn_sqr_n (prodp, up, size, tspace)
280      mp_size_t size;
284   if ((size & 1) != 0)
286       /* The size is odd, the code code below doesn't handle that.
287 	 Multiply the least significant (size - 1) limbs with a recursive
291 	 code below behave as if the size were even, and let it check for
292 	 odd size in the end.  I.e., in essence move this code to the end.
296       mp_size_t esize = size - 1;	/* even size */
302       cy_limb = mpn_addmul_1 (prodp + esize, up, size, up[esize]);
304       prodp[esize + size] = cy_limb;
308       mp_size_t hsize = size >> 1;
315       MPN_SQR_N_RECURSE (prodp + size, up + hsize, hsize, tspace);
331       MPN_SQR_N_RECURSE (tspace, prodp, hsize, tspace + size);
334       MPN_COPY (prodp + hsize, prodp + size, hsize);
335       cy = mpn_add_n (prodp + size, prodp + size, prodp + size + hsize, hsize);
338       cy -= mpn_sub_n (prodp + hsize, prodp + hsize, tspace, size);
345       MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size);
349       cy += mpn_add_n (prodp + hsize, prodp + hsize, tspace, size);
351 	mpn_add_1 (prodp + hsize + size, prodp + hsize + size, hsize, cy);
356 	mpn_add_1 (prodp + size, prodp + size, size, 1);
363 mpn_mul_n (mp_ptr prodp, mp_srcptr up, mp_srcptr vp, mp_size_t size)
365 mpn_mul_n (prodp, up, vp, size)
369      mp_size_t size;
376       if (size < KARATSUBA_THRESHOLD)
378 	  impn_sqr_n_basecase (prodp, up, size);
383 	  tspace = (mp_ptr) TMP_ALLOC (2 * size * BYTES_PER_MP_LIMB);
384 	  impn_sqr_n (prodp, up, size, tspace);
389       if (size < KARATSUBA_THRESHOLD)
391 	  impn_mul_n_basecase (prodp, up, vp, size);
396 	  tspace = (mp_ptr) TMP_ALLOC (2 * size * BYTES_PER_MP_LIMB);
397 	  impn_mul_n (prodp, up, vp, size, tspace);