- uint8_t tmp_b[2*n+2], m_b[2*(n+1)];
- bigint_t tmp, tmp2, m;
- tmp.wordv = tmp_b;
- tmp2.wordv = tmp_b+n+1;
- m.wordv = m_b;
-
- bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */
- bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */
- bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */
- bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp2*tmp */
- bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */
- bigint_sub_u(&m, &m, dest); /* m <= m-dest */
- bigint_sub_u(&m, &m, &tmp); /* m <= m-h */
- bigint_add_scale_u(dest, &m, n);
- bigint_add_scale_u(dest, &tmp, 2*n);
+ /* remember we want to do:
+ * x*y = (xh * b ** n + xl) * (yh * b ** n + yl)
+ * x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + xl*yl
+ * 5 9 2 4 3 7 5 6 1 8 1
+ */
+ bigint_word_t tmp1_b[n*2+2];
+ bigint_t tmp1, tmp2;
+ tmp1.wordv = tmp1_b;
+ tmp2.wordv = &tmp1_b[n+1];
+
+ bigint_add_u(&tmp2, &xh, &xl); /* 2: tmp2 <= xh + xl */
+ bigint_add_u(&tmp1, &yh, &yl); /* 3: tmp1 <= yh + yl */
+ bigint_mul_u(dest, &tmp2, &tmp1); /* 4: dest <= tmp2 * tmp1 */
+ bigint_mul_u(&tmp1, &xh, &yh); /* 5: tmp1 <= xh * yh */
+ bigint_sub_u(dest, dest, &tmp1); /* 7: dest <= dest - tmp1 */
+ bigint_word_t tmp3_b[2*n];
+ tmp2.wordv = tmp3_b;
+ bigint_mul_u(&tmp2, &xl, &yl); /* 1: tmp3 <= xl * yl */
+ bigint_sub_u(dest, dest, &tmp2); /* 6: dest <= dest - tmp3 */
+ bigint_shiftleft(dest, n * sizeof(bigint_word_t) * 8);
+ bigint_add_u(dest, dest, &tmp2); /* 8: dest <= tmp3 + dest ** n */
+ bigint_add_scale_u(dest, &tmp1, 2*n*sizeof(bigint_word_t)); /* 9: dest <= dest + tmp1 ** (2 * n) */
+
+#if 0
+ bigint_mul_u(dest, &xl, &yl); /* 1: dest <= xl * yl */
+ bigint_add_u(&tmp2, &xh, &xl); /* 2: tmp2 <= xh + xl */
+ bigint_add_u(&tmp1, &yh, &yl); /* 3: tmp1 <= yh + yl */
+ bigint_mul_u(&tmp3, &tmp2, &tmp1); /* 4: tmp3 <= tmp2 * tmp1 */
+ bigint_mul_u(&tmp1, &xh, &yh); /* 5: h <= xh * yh */
+ bigint_sub_u(&tmp3, &tmp3, dest); /* 6: tmp3 <= tmp3 - dest */
+ bigint_sub_u(&tmp3, &tmp3, &tmp1); /* 7: tmp3 <= tmp3 - h */
+ bigint_add_scale_u(dest, &tmp3, n*sizeof(bigint_word_t)); /* 8: dest <= dest + tmp3 ** n */
+ bigint_add_scale_u(dest, &tmp1, 2*n*sizeof(bigint_word_t)); /* 9: dest <= dest + tmp1 ** (2 * n) */
+#endif