+ *
+ * 'scratch' must point to an array of BignumInt of size at least
+ * mul_compute_scratch(len). (This covers the needs of internal_mul
+ * and all its recursive calls to itself.)
+ */
+#define KARATSUBA_THRESHOLD 50
+static int mul_compute_scratch(int len)
+{
+ int ret = 0;
+ while (len > KARATSUBA_THRESHOLD) {
+ int toplen = len/2, botlen = len - toplen; /* botlen is the bigger */
+ int midlen = botlen + 1;
+ ret += 4*midlen;
+ len = midlen;
+ }
+ return ret;
+}
+static void internal_mul(const BignumInt *a, const BignumInt *b,
+ BignumInt *c, int len, BignumInt *scratch)
+{
+ if (len > KARATSUBA_THRESHOLD) {
+ int i;
+
+ /*
+ * Karatsuba divide-and-conquer algorithm. Cut each input in
+ * half, so that it's expressed as two big 'digits' in a giant
+ * base D:
+ *
+ * a = a_1 D + a_0
+ * b = b_1 D + b_0
+ *
+ * Then the product is of course
+ *
+ * ab = a_1 b_1 D^2 + (a_1 b_0 + a_0 b_1) D + a_0 b_0
+ *
+ * and we compute the three coefficients by recursively
+ * calling ourself to do half-length multiplications.
+ *
+ * The clever bit that makes this worth doing is that we only
+ * need _one_ half-length multiplication for the central
+ * coefficient rather than the two that it obviouly looks
+ * like, because we can use a single multiplication to compute
+ *
+ * (a_1 + a_0) (b_1 + b_0) = a_1 b_1 + a_1 b_0 + a_0 b_1 + a_0 b_0
+ *
+ * and then we subtract the other two coefficients (a_1 b_1
+ * and a_0 b_0) which we were computing anyway.
+ *
+ * Hence we get to multiply two numbers of length N in about
+ * three times as much work as it takes to multiply numbers of
+ * length N/2, which is obviously better than the four times
+ * as much work it would take if we just did a long
+ * conventional multiply.
+ */
+
+ int toplen = len/2, botlen = len - toplen; /* botlen is the bigger */
+ int midlen = botlen + 1;
+ BignumDblInt carry;
+
+ /*
+ * The coefficients a_1 b_1 and a_0 b_0 just avoid overlapping
+ * in the output array, so we can compute them immediately in
+ * place.
+ */
+
+#ifdef KARA_DEBUG
+ printf("a1,a0 = 0x");
+ for (i = 0; i < len; i++) {
+ if (i == toplen) printf(", 0x");
+ printf("%0*x", BIGNUM_INT_BITS/4, a[len - 1 - i]);
+ }
+ printf("\n");
+ printf("b1,b0 = 0x");
+ for (i = 0; i < len; i++) {
+ if (i == toplen) printf(", 0x");
+ printf("%0*x", BIGNUM_INT_BITS/4, b[len - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /* a_1 b_1 */
+ internal_mul(a + botlen, b + botlen, c + 2*botlen, toplen, scratch);
+#ifdef KARA_DEBUG
+ printf("a1b1 = 0x");
+ for (i = 0; i < 2*toplen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, c[2*len - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /* a_0 b_0 */
+ internal_mul(a, b, c, botlen, scratch);
+#ifdef KARA_DEBUG
+ printf("a0b0 = 0x");
+ for (i = 0; i < 2*botlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, c[2*botlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /* Zero padding. botlen exceeds toplen by at most 1, and we'll set
+ * the extra carry explicitly below, so we only need to zero at most
+ * one of the top words here.
+ */
+ scratch[midlen - 2] = scratch[2*midlen - 2] = 0;
+
+ for (i = 0; i < toplen; i++) {
+ scratch[i] = a[i + botlen]; /* a_1 */
+ scratch[midlen + i] = b[i + botlen]; /* b_1 */
+ }
+
+ /* compute a_1 + a_0 */
+ scratch[midlen - 1] = internal_add(scratch, a, scratch, botlen);
+#ifdef KARA_DEBUG
+ printf("a1plusa0 = 0x");
+ for (i = 0; i < midlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, scratch[midlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+ /* compute b_1 + b_0 */
+ scratch[2*midlen - 1] = internal_add(scratch+midlen, b,
+ scratch+midlen, botlen);
+#ifdef KARA_DEBUG
+ printf("b1plusb0 = 0x");
+ for (i = 0; i < midlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, scratch[2*midlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /*
+ * Now we can do the third multiplication.
+ */
+ internal_mul(scratch, scratch + midlen, scratch + 2*midlen, midlen,
+ scratch + 4*midlen);
+#ifdef KARA_DEBUG
+ printf("a1plusa0timesb1plusb0 = 0x");
+ for (i = 0; i < 2*midlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, scratch[4*midlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /*
+ * Now we can reuse the first half of 'scratch' to compute the
+ * sum of the outer two coefficients, to subtract from that
+ * product to obtain the middle one.
+ */
+ scratch[2*botlen - 2] = scratch[2*botlen - 1] = 0;
+ for (i = 0; i < 2*toplen; i++)
+ scratch[i] = c[2*botlen + i];
+ scratch[2*botlen] = internal_add(scratch, c, scratch, 2*botlen);
+ scratch[2*botlen + 1] = 0;
+#ifdef KARA_DEBUG
+ printf("a1b1plusa0b0 = 0x");
+ for (i = 0; i < 2*midlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, scratch[2*midlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ internal_sub(scratch + 2*midlen, scratch, scratch, 2*midlen);
+#ifdef KARA_DEBUG
+ printf("a1b0plusa0b1 = 0x");
+ for (i = 0; i < 2*midlen; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, scratch[4*midlen - 1 - i]);
+ }
+ printf("\n");
+#endif
+
+ /*
+ * And now all we need to do is to add that middle coefficient
+ * back into the output. We may have to propagate a carry
+ * further up the output, but we can be sure it won't
+ * propagate right the way off the top.
+ */
+ carry = internal_add(c + botlen, scratch, c + botlen, 2*midlen);
+ i = botlen + 2*midlen;
+ while (carry) {
+ assert(i <= 2*len);
+ carry += c[i];
+ c[i] = (BignumInt)carry;
+ carry >>= BIGNUM_INT_BITS;
+ i++;
+ }
+#ifdef KARA_DEBUG
+ printf("ab = 0x");
+ for (i = 0; i < 2*len; i++) {
+ printf("%0*x", BIGNUM_INT_BITS/4, c[2*len - i]);
+ }
+ printf("\n");
+#endif
+
+ } else {
+ int i;
+ BignumInt carry;
+ BignumDblInt t;
+ const BignumInt *ap, *alim = a + len, *bp, *blim = b + len;
+ BignumInt *cp, *cps;
+
+ /*
+ * Multiply in the ordinary O(N^2) way.
+ */
+
+ for (i = 0; i < 2 * len; i++)
+ c[i] = 0;
+
+ for (cps = c, ap = a; ap < alim; ap++, cps++) {
+ carry = 0;
+ for (cp = cps, bp = b; bp < blim; bp++, cp++) {
+ t = (MUL_WORD(*ap, *bp) + carry) + *cp;
+ *cp = (BignumInt) t;
+ carry = (BignumInt)(t >> BIGNUM_INT_BITS);
+ }
+ *cp = carry;
+ }
+ }
+}
+
+/*
+ * Variant form of internal_mul used for the initial step of
+ * Montgomery reduction. Only bothers outputting 'len' words
+ * (everything above that is thrown away).