From 896bbd1b8d67da395ed08fd524c5ca07a4b50e93 Mon Sep 17 00:00:00 2001 From: Chris Duncan Date: Mon, 28 Sep 2026 14:38:30 -0700 Subject: [PATCH] Start unrolling field element ops to take advantage of faster locals. --- src/assembly/ed25519/fe.ts | 2 +- src/assembly/ed25519/p.ts | 266 +++++++++++++++++++++++++++++++++---- 2 files changed, 241 insertions(+), 27 deletions(-) diff --git a/src/assembly/ed25519/fe.ts b/src/assembly/ed25519/fe.ts index 17964f4..4a4bb8e 100644 --- a/src/assembly/ed25519/fe.ts +++ b/src/assembly/ed25519/fe.ts @@ -930,7 +930,7 @@ export function fe_sq (h: FieldElement, f: FieldElement): void { * @param hx FieldElement power destination * @param fx FieldElement base source */ -export function fe_sq_vec (hx: FieldElement, fx: FieldElement, hy: FieldElement, fy: FieldElement): void { +export function fe_sq_vec (hx: FieldElement, hy: FieldElement, fx: FieldElement, fy: FieldElement): void { const fx_ptr: usize = changetype(fx) const fy_ptr: usize = changetype(fy) const f0: v128 = i32x4(load(fx_ptr, 0), load(fy_ptr, 0), 0, 0) diff --git a/src/assembly/ed25519/p.ts b/src/assembly/ed25519/p.ts index 8d98e90..f6ec9b2 100644 --- a/src/assembly/ed25519/p.ts +++ b/src/assembly/ed25519/p.ts @@ -51,15 +51,78 @@ const ge_p2_dbl_t0: FieldElement = fe() //@ts-expect-error @inline export function ge_p2_dbl (r: ge_p1p1, p: ge_p2): void { - const t0 = ge_p2_dbl_t0 - fe_sq_vec(r.X, p.X, r.Z, p.Y) - fe_sq2(r.T, p.Z) - fe_add(r.Y, p.X, p.Y) - fe_sq(t0, r.Y) - fe_add(r.Y, r.Z, r.X) - fe_sub(r.Z, r.Z, r.X) - fe_sub(r.X, t0, r.Y) - fe_sub(r.T, r.T, r.Z) + const rX_ptr = changetype(r.X) + const rY_ptr = changetype(r.Y) + const rZ_ptr = changetype(r.Z) + const rT_ptr = changetype(r.T) + + const pX_ptr = changetype(p.X) + const pY_ptr = changetype(p.Y) + const pZ_ptr = changetype(p.Z) + + const rYsq = ge_p2_dbl_t0 + const rYsq_ptr = changetype(rYsq) + + fe_sq_vec(r.X, r.Z, p.X, p.Y) // rX = pX²; rY = pY² + fe_sq2(r.T, p.Z) // rT = pZ² + + // Start converting to performant inlined ops with locals to avoid load/store + let rX0 = v128.load(rX_ptr), rX1 = v128.load(rX_ptr, 16), rX2 = v128.load(rX_ptr, 32) + let rY0 = v128.load(rY_ptr), rY1 = v128.load(rY_ptr, 16), rY2 = v128.load(rY_ptr, 32) + let rZ0 = v128.load(rZ_ptr), rZ1 = v128.load(rZ_ptr, 16), rZ2 = v128.load(rZ_ptr, 32) + let rT0 = v128.load(rT_ptr), rT1 = v128.load(rT_ptr, 16), rT2 = v128.load(rT_ptr, 32) + + const pX0 = v128.load(pX_ptr), pX1 = v128.load(pX_ptr, 16), pX2 = v128.load(pX_ptr, 32) + const pY0 = v128.load(pY_ptr), pY1 = v128.load(pY_ptr, 16), pY2 = v128.load(pY_ptr, 32) + const pZ0 = v128.load(pZ_ptr), pZ1 = v128.load(pZ_ptr, 16), pZ2 = v128.load(pZ_ptr, 32) + + // rY = pX + pY + v128.store(rY_ptr, v128.add(pX0, pY0)) + v128.store(rY_ptr, v128.add(pX1, pY1), 16) + v128.store_lane(rY_ptr, v128.add(pX2, pY2), 0, 32) + + // t0 = r.Y² + fe_sq(rYsq, r.Y) + + // Y = Z + X + rY0 = v128.add(rZ0, rX0) + rY1 = v128.add(rZ1, rX1) + rY2 = v128.add(rZ2, rX2) + + // Z = Z - X + rZ0 = v128.sub(rZ0, rX0) + rZ1 = v128.sub(rZ1, rX1) + rZ2 = v128.sub(rZ2, rX2) + + // X = Y^2 - Y + rX0 = v128.sub(v128.load(rYsq_ptr), rY0) + rX1 = v128.sub(v128.load(rYsq_ptr, 16), rY1) + rX2 = v128.sub(v128.load(rYsq_ptr, 32), rY2) + + // T = T - Z + rT0 = v128.sub(rT0, rZ0) + rT1 = v128.sub(rT1, rZ1) + rT2 = v128.sub(rT2, rZ2) + + // store r.X + v128.store(rX_ptr, rX0) + v128.store(rX_ptr, rX1, 16) + v128.store_lane(rX_ptr, rX2, 0, 32) + + // store r.Y + v128.store(rY_ptr, rY0) + v128.store(rY_ptr, rY1, 16) + v128.store_lane(rY_ptr, rY2, 0, 32) + + // store r.Z + v128.store(rZ_ptr, rZ0) + v128.store(rZ_ptr, rZ1, 16) + v128.store_lane(rZ_ptr, rZ2, 0, 32) + + // store r.T + v128.store(rT_ptr, rT0) + v128.store(rT_ptr, rT1, 16) + v128.store_lane(rT_ptr, rT2, 0, 32) } /** @@ -154,23 +217,97 @@ export function ge_precomp_0 (h: ge_precomp): void { fe_0(h.xy2d) } -const ge_add_cached_t0: FieldElement = fe() /** * r = p + q */ export function ge_add_cached (r: ge_p1p1, p: ge_p3, q: ge_cached): void { - const t0 = ge_add_cached_t0 - fe_add(r.X, p.Y, p.X) - fe_sub(r.Y, p.Y, p.X) + const rX_ptr = changetype(r.X) + const rY_ptr = changetype(r.Y) + const rZ_ptr = changetype(r.Z) + const rT_ptr = changetype(r.T) + + const pX_ptr = changetype(p.X) + const pY_ptr = changetype(p.Y) + + let pX0 = v128.load(pX_ptr), pX1 = v128.load(pX_ptr, 16), pX2 = v128.load(pX_ptr, 32) + let pY0 = v128.load(pY_ptr), pY1 = v128.load(pY_ptr, 16), pY2 = v128.load(pY_ptr, 32) + + // fe_add(r.X, p.Y, p.X) + let rX0 = v128.add(pY0, pX0) + let rX1 = v128.add(pY1, pX1) + let rX2 = v128.add(pY2, pX2) + + // fe_sub(r.Y, p.Y, p.X) + let rY0 = v128.sub(pY0, pX0) + let rY1 = v128.sub(pY1, pX1) + let rY2 = v128.sub(pY2, pX2) + + // store r.X + v128.store(rX_ptr, rX0) + v128.store(rX_ptr, rX1, 16) + v128.store_lane(rX_ptr, rX2, 0, 32) + + // store r.Y + v128.store(rY_ptr, rY0) + v128.store(rY_ptr, rY1, 16) + v128.store_lane(rY_ptr, rY2, 0, 32) + + // not yet converted to inline for size and complexity fe_mul(r.Z, r.X, q.YplusX) fe_mul(r.Y, r.Y, q.YminusX) fe_mul(r.T, q.T2d, p.T) fe_mul(r.X, p.Z, q.Z) - fe_dbl(t0, r.X) - fe_sub(r.X, r.Z, r.Y) - fe_add(r.Y, r.Z, r.Y) - fe_add(r.Z, t0, r.T) - fe_sub(r.T, t0, r.T) + + // remaining arithmetic done inline to avoid unnecessary load/store + rX0 = v128.load(rX_ptr), rX1 = v128.load(rX_ptr, 16), rX2 = v128.load(rX_ptr, 32) + rY0 = v128.load(rY_ptr), rY1 = v128.load(rY_ptr, 16), rY2 = v128.load(rY_ptr, 32) + let rZ0 = v128.load(rZ_ptr), rZ1 = v128.load(rZ_ptr, 16), rZ2 = v128.load(rZ_ptr, 32) + let rT0 = v128.load(rT_ptr), rT1 = v128.load(rT_ptr, 16), rT2 = v128.load(rT_ptr, 32) + + // fe_dbl(t0, r.X) + const t0 = v128.shl(rX0, 1) + const t1 = v128.shl(rX1, 1) + const t2 = v128.shl(rX2, 1) + + // fe_sub(r.X, r.Z, r.Y) + rX0 = v128.sub(rZ0, rY0) + rX1 = v128.sub(rZ1, rY1) + rX2 = v128.sub(rZ2, rY2) + + // fe_add(r.Y, r.Z, r.Y) + rY0 = v128.add(rZ0, rY0) + rY1 = v128.add(rZ1, rY1) + rY2 = v128.add(rZ2, rY2) + + // fe_add(r.Z, t, r.T) + rZ0 = v128.add(t0, rT0) + rZ1 = v128.add(t1, rT1) + rZ2 = v128.add(t2, rT2) + + // fe_sub(r.T, t, r.T) + rT0 = v128.sub(t0, rT0) + rT1 = v128.sub(t1, rT1) + rT2 = v128.sub(t2, rT2) + + // store r.X + v128.store(rX_ptr, rX0) + v128.store(rX_ptr, rX1, 16) + v128.store_lane(rX_ptr, rX2, 0, 32) + + // store r.Y + v128.store(rY_ptr, rY0) + v128.store(rY_ptr, rY1, 16) + v128.store_lane(rY_ptr, rY2, 0, 32) + + // store r.Z + v128.store(rZ_ptr, rZ0) + v128.store(rZ_ptr, rZ1, 16) + v128.store_lane(rZ_ptr, rZ2, 0, 32) + + // store r.T + v128.store(rT_ptr, rT0) + v128.store(rT_ptr, rT1, 16) + v128.store_lane(rT_ptr, rT2, 0, 32) } const ge_add_precomp_t0: FieldElement = fe() @@ -180,17 +317,94 @@ const ge_add_precomp_t0: FieldElement = fe() //@ts-expect-error @inline export function ge_add_precomp (r: ge_p1p1, p: ge_p3, q: ge_precomp): void { - const t0 = ge_add_precomp_t0 - fe_add(r.X, p.Y, p.X) - fe_sub(r.Y, p.Y, p.X) + const rX_ptr = changetype(r.X) + const rY_ptr = changetype(r.Y) + const rZ_ptr = changetype(r.Z) + const rT_ptr = changetype(r.T) + + const pX_ptr = changetype(p.X) + const pY_ptr = changetype(p.Y) + const pZ_ptr = changetype(p.Z) + + const pX0 = v128.load(pX_ptr), pX1 = v128.load(pX_ptr, 16), pX2 = v128.load(pX_ptr, 32) + const pY0 = v128.load(pY_ptr), pY1 = v128.load(pY_ptr, 16), pY2 = v128.load(pY_ptr, 32) + const pZ0 = v128.load(pZ_ptr), pZ1 = v128.load(pZ_ptr, 16), pZ2 = v128.load(pZ_ptr, 32) + + // fe_add(r.X, p.Y, p.X) + let rX0 = v128.add(pY0, pX0) + let rX1 = v128.add(pY1, pX1) + let rX2 = v128.add(pY2, pX2) + + // fe_sub(r.Y, p.Y, p.X) + let rY0 = v128.sub(pY0, pX0) + let rY1 = v128.sub(pY1, pX1) + let rY2 = v128.sub(pY2, pX2) + + // store r.X + v128.store(rX_ptr, rX0) + v128.store(rX_ptr, rX1, 16) + v128.store_lane(rX_ptr, rX2, 0, 32) + + // store r.Y + v128.store(rY_ptr, rY0) + v128.store(rY_ptr, rY1, 16) + v128.store_lane(rY_ptr, rY2, 0, 32) + + // not yet converted to inline for size and complexity fe_mul(r.Z, r.X, q.yplusx) fe_mul(r.Y, r.Y, q.yminusx) fe_mul(r.T, q.xy2d, p.T) - fe_dbl(t0, p.Z) - fe_sub(r.X, r.Z, r.Y) - fe_add(r.Y, r.Z, r.Y) - fe_add(r.Z, t0, r.T) - fe_sub(r.T, t0, r.T) + + // remaining arithmetic done inline to avoid unnecessary load/store + rX0 = v128.load(rX_ptr), rX1 = v128.load(rX_ptr, 16), rX2 = v128.load(rX_ptr, 32) + rY0 = v128.load(rY_ptr), rY1 = v128.load(rY_ptr, 16), rY2 = v128.load(rY_ptr, 32) + let rZ0 = v128.load(rZ_ptr), rZ1 = v128.load(rZ_ptr, 16), rZ2 = v128.load(rZ_ptr, 32) + let rT0 = v128.load(rT_ptr), rT1 = v128.load(rT_ptr, 16), rT2 = v128.load(rT_ptr, 32) + + // fe_dbl(t, p.Z) + const t0 = v128.shl(pZ0, 1) + const t1 = v128.shl(pZ1, 1) + const t2 = v128.shl(pZ2, 1) + + // fe_sub(r.X, r.Z, r.Y) + rX0 = v128.sub(rZ0, rY0) + rX1 = v128.sub(rZ1, rY1) + rX2 = v128.sub(rZ2, rY2) + + // fe_add(r.Y, r.Z, r.Y) + rY0 = v128.add(rZ0, rY0) + rY1 = v128.add(rZ1, rY1) + rY2 = v128.add(rZ2, rY2) + + // fe_add(r.Z, t, r.T) + rZ0 = v128.add(t0, rT0) + rZ1 = v128.add(t1, rT1) + rZ2 = v128.add(t2, rT2) + + // fe_sub(r.T, t, r.T) + rT0 = v128.sub(t0, rT0) + rT1 = v128.sub(t1, rT1) + rT2 = v128.sub(t2, rT2) + + // store r.X + v128.store(rX_ptr, rX0) + v128.store(rX_ptr, rX1, 16) + v128.store_lane(rX_ptr, rX2, 0, 32) + + // store r.Y + v128.store(rY_ptr, rY0) + v128.store(rY_ptr, rY1, 16) + v128.store_lane(rY_ptr, rY2, 0, 32) + + // store r.Z + v128.store(rZ_ptr, rZ0) + v128.store(rZ_ptr, rZ1, 16) + v128.store_lane(rZ_ptr, rZ2, 0, 32) + + // store r.T + v128.store(rT_ptr, rT0) + v128.store(rT_ptr, rT1, 16) + v128.store_lane(rT_ptr, rT2, 0, 32) } const ge_sub_p3_q_cached = new ge_cached() -- 2.52.0