+int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
+ {
+ BN_CTX *new_ctx = NULL;
+ BIGNUM *tmp0, *tmp1;
+ size_t pow2 = 0;
+ BIGNUM **heap = NULL;
+ size_t i;
+ int ret = 0;
+
+ if (num == 0)
+ return 1;
+
+ if (ctx == NULL)
+ {
+ ctx = new_ctx = BN_CTX_new();
+ if (ctx == NULL)
+ return 0;
+ }
+
+ BN_CTX_start(ctx);
+ tmp0 = BN_CTX_get(ctx);
+ tmp1 = BN_CTX_get(ctx);
+ if (tmp0 == NULL || tmp1 == NULL) goto err;
+
+ /* Before converting the individual points, compute inverses of all Z values.
+ * Modular inversion is rather slow, but luckily we can do with a single
+ * explicit inversion, plus about 3 multiplications per input value.
+ */
+
+ pow2 = 1;
+ while (num > pow2)
+ pow2 <<= 1;
+ /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
+ * We need twice that. */
+ pow2 <<= 1;
+
+ heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
+ if (heap == NULL) goto err;
+
+ /* The array is used as a binary tree, exactly as in heapsort:
+ *
+ * heap[1]
+ * heap[2] heap[3]
+ * heap[4] heap[5] heap[6] heap[7]
+ * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
+ *
+ * We put the Z's in the last line;
+ * then we set each other node to the product of its two child-nodes (where
+ * empty or 0 entries are treated as ones);
+ * then we invert heap[1];
+ * then we invert each other node by replacing it by the product of its
+ * parent (after inversion) and its sibling (before inversion).
+ */
+ heap[0] = NULL;
+ for (i = pow2/2 - 1; i > 0; i--)
+ heap[i] = NULL;
+ for (i = 0; i < num; i++)
+ heap[pow2/2 + i] = &points[i]->Z;
+ for (i = pow2/2 + num; i < pow2; i++)
+ heap[i] = NULL;
+
+ /* set each node to the product of its children */
+ for (i = pow2/2 - 1; i > 0; i--)
+ {
+ heap[i] = BN_new();
+ if (heap[i] == NULL) goto err;
+
+ if (heap[2*i] != NULL)
+ {
+ if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
+ {
+ if (!BN_copy(heap[i], heap[2*i])) goto err;
+ }
+ else
+ {
+ if (BN_is_zero(heap[2*i]))
+ {
+ if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
+ }
+ else
+ {
+ if (!group->meth->field_mul(group, heap[i],
+ heap[2*i], heap[2*i + 1], ctx)) goto err;
+ }
+ }
+ }
+ }
+
+ /* invert heap[1] */
+ if (!BN_is_zero(heap[1]))
+ {
+ if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
+ {
+ ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
+ goto err;
+ }
+ }
+ if (group->meth->field_encode != 0)
+ {
+ /* in the Montgomery case, we just turned R*H (representing H)
+ * into 1/(R*H), but we need R*(1/H) (representing 1/H);
+ * i.e. we have need to multiply by the Montgomery factor twice */
+ if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+ if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+ }
+
+ /* set other heap[i]'s to their inverses */
+ for (i = 2; i < pow2/2 + num; i += 2)
+ {
+ /* i is even */
+ if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
+ {
+ if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
+ if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
+ if (!BN_copy(heap[i], tmp0)) goto err;
+ if (!BN_copy(heap[i + 1], tmp1)) goto err;
+ }
+ else
+ {
+ if (!BN_copy(heap[i], heap[i/2])) goto err;
+ }
+ }
+
+ /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
+ for (i = 0; i < num; i++)
+ {
+ EC_POINT *p = points[i];
+
+ if (!BN_is_zero(&p->Z))
+ {
+ /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
+
+ if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
+ if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
+
+ if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
+ if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
+
+ if (group->meth->field_set_to_one != 0)
+ {
+ if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_one(&p->Z)) goto err;
+ }
+ p->Z_is_one = 1;
+ }
+ }
+
+ ret = 1;
+
+ err:
+ BN_CTX_end(ctx);
+ if (new_ctx != NULL)
+ BN_CTX_free(new_ctx);
+ if (heap != NULL)
+ {
+ /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
+ for (i = pow2/2 - 1; i > 0; i--)
+ {
+ if (heap[i] != NULL)
+ BN_clear_free(heap[i]);
+ }
+ OPENSSL_free(heap);
+ }
+ return ret;
+ }
+
+