pub const Edwards25519 = struct {
    /// The underlying prime field.
    pub const Fe = @import("field.zig").Fe;
    /// Field arithmetic mod the order of the main subgroup.
    pub const scalar = @import("scalar.zig");
    /// Length in bytes of a compressed representation of a point.
    pub const encoded_length: usize = 32;

    x: Fe,
    y: Fe,
    z: Fe,
    t: Fe,

    is_base: bool = false,

    /// Decode an Edwards25519 point from its compressed (Y+sign) coordinates.
    pub fn fromBytes(s: [encoded_length]u8) EncodingError!Edwards25519 {
        const z = Fe.one;
        const y = Fe.fromBytes(s);
        var u = y.sq();
        var v = u.mul(Fe.edwards25519d);
        u = u.sub(z);
        v = v.add(z);
        var x = u.mul(v).pow2523().mul(u);
        const vxx = x.sq().mul(v);
        const has_m_root = vxx.sub(u).isZero();
        const has_p_root = vxx.add(u).isZero();
        if ((@intFromBool(has_m_root) | @intFromBool(has_p_root)) == 0) { // best-effort to avoid two conditional branches
            return error.InvalidEncoding;
        }
        x.cMov(x.mul(Fe.sqrtm1), 1 - @intFromBool(has_m_root));
        x.cMov(x.neg(), @intFromBool(x.isNegative()) ^ (s[31] >> 7));
        const t = x.mul(y);
        return Edwards25519{ .x = x, .y = y, .z = z, .t = t };
    }

    /// Encode an Edwards25519 point.
    pub fn toBytes(p: Edwards25519) [encoded_length]u8 {
        const zi = p.z.invert();
        var s = p.y.mul(zi).toBytes();
        s[31] ^= @as(u8, @intFromBool(p.x.mul(zi).isNegative())) << 7;
        return s;
    }

    /// Check that the encoding of a point is canonical.
    pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void {
        return Fe.rejectNonCanonical(s, true);
    }

    /// The edwards25519 base point.
    pub const basePoint = Edwards25519{
        .x = Fe{ .limbs = .{ 1738742601995546, 1146398526822698, 2070867633025821, 562264141797630, 587772402128613 } },
        .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } },
        .z = Fe.one,
        .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } },
        .is_base = true,
    };

    pub const identityElement = Edwards25519{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero };

    /// Reject the neutral element.
    pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void {
        if (p.x.isZero()) {
            return error.IdentityElement;
        }
    }

    /// Reject a point if it is not in the prime order subgroup generated by the standard base point.
    ///
    /// If the point is not in the main subgroup:
    ///
    /// - `WeakPublicKeyError` is returned if the point belongs to a low-order subgroup.
    /// - `UnexpectedSubgroupError` is returned otherwise.
    pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void {
        try p.rejectLowOrder();

        // Multiply p by the order of subgroup - This is a prime order group, so the result should be the neutral element.
        const _10 = p.dbl();
        const _11 = p.add(_10);
        const _100 = p.add(_11);
        const _110 = _10.add(_100);
        const _1000 = _10.add(_110);
        const _1011 = _11.add(_1000);
        const _10000 = _1000.dbl();
        const _100000 = _10000.dbl();
        const _100110 = _110.add(_100000);
        const _1000000 = _100000.dbl();
        const _1010000 = _10000.add(_1000000);
        const _1010011 = _11.add(_1010000);
        const _1100011 = _10000.add(_1010011);
        const _1100111 = _100.add(_1100011);
        const _1101011 = _100.add(_1100111);
        const _10010011 = _1000000.add(_1010011);
        const _10010111 = _100.add(_10010011);
        const _10111101 = _100110.add(_10010111);
        const _11010011 = _1000000.add(_10010011);
        const _11100111 = _1010000.add(_10010111);
        const _11101101 = _110.add(_11100111);
        const _11110101 = _1000.add(_11101101);
        const q = ((_11110101.add(((((_1101011.add(((((_10.add(((_1011.add(_11110101)).shift(126)
            .add(_1010011)).shift(9).add(_11110101))).shift(7).add(_1100111)).shift(9).add(_11110101).shift(11)
            .add(_10111101)).shift(8).add(_11100111)).shift(9))).shift(6).add(_1011)).shift(14).add(_10010011).shift(10)
            .add(_1100011)).shift(9).add(_10010111)).shift(10))).shift(8).add(_11010011)).shift(8).add(_11101101);
        q.rejectIdentity() catch return;
        return error.UnexpectedSubgroup;
    }

    /// Multiply a point by the cofactor
    pub fn clearCofactor(p: Edwards25519) Edwards25519 {
        return p.dbl().dbl().dbl();
    }

    /// Check that the point does not generate a low-order group.
    /// Return a `WeakPublicKey` error if it does.
    pub fn rejectLowOrder(p: Edwards25519) WeakPublicKeyError!void {
        const zi = p.z.invert();
        const x = p.x.mul(zi);
        const y = p.y.mul(zi);
        const x_neg = x.neg();
        const iy = Fe.sqrtm1.mul(y);
        if (x.isZero() or y.isZero() or iy.equivalent(x) or iy.equivalent(x_neg)) {
            return error.WeakPublicKey;
        }
    }

    /// Flip the sign of the X coordinate.
    pub inline fn neg(p: Edwards25519) Edwards25519 {
        return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
    }

    /// Double an Edwards25519 point.
    pub fn dbl(p: Edwards25519) Edwards25519 {
        const t0 = p.x.add(p.y).sq();
        var x = p.x.sq();
        var z = p.y.sq();
        const y = z.add(x);
        z = z.sub(x);
        x = t0.sub(y);
        const t = p.z.sq2().sub(z);
        return .{
            .x = x.mul(t),
            .y = y.mul(z),
            .z = z.mul(t),
            .t = x.mul(y),
        };
    }

    /// Add two Edwards25519 points.
    pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519 {
        const a = p.y.sub(p.x).mul(q.y.sub(q.x));
        const b = p.x.add(p.y).mul(q.x.add(q.y));
        const c = p.t.mul(q.t).mul(Fe.edwards25519d2);
        var d = p.z.mul(q.z);
        d = d.add(d);
        const x = b.sub(a);
        const y = b.add(a);
        const z = d.add(c);
        const t = d.sub(c);
        return .{
            .x = x.mul(t),
            .y = y.mul(z),
            .z = z.mul(t),
            .t = x.mul(y),
        };
    }

    /// Subtract two Edwards25519 points.
    pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
        return p.add(q.neg());
    }

    /// Double a point `n` times.
    fn shift(p: Edwards25519, n: comptime_int) Edwards25519 {
        var q = p;
        for (0..n) |_| q = q.dbl();
        return q;
    }

    inline fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
        p.x.cMov(a.x, c);
        p.y.cMov(a.y, c);
        p.z.cMov(a.z, c);
        p.t.cMov(a.t, c);
    }

    inline fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519 {
        var t = Edwards25519.identityElement;
        comptime var i: u8 = 1;
        inline while (i < pc.len) : (i += 1) {
            t.cMov(pc[i], ((@as(usize, b ^ i) -% 1) >> 8) & 1);
        }
        return t;
    }

    fn slide(s: [32]u8) [2 * 32]i8 {
        const reduced = if ((s[s.len - 1] & 0x80) == 0) s else scalar.reduce(s);
        var e: [2 * 32]i8 = undefined;
        for (reduced, 0..) |x, i| {
            e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
            e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
        }
        // Now, e[0..63] is between 0 and 15, e[63] is between 0 and 7
        var carry: i8 = 0;
        for (e[0..63]) |*x| {
            x.* += carry;
            carry = (x.* + 8) >> 4;
            x.* -= carry * 16;
        }
        e[63] += carry;
        // Now, e[*] is between -8 and 8, including e[63]
        return e;
    }

    // Scalar multiplication with a 4-bit window and the first 8 multiples.
    // This requires the scalar to be converted to non-adjacent form.
    // Based on real-world benchmarks, we only use this for multi-scalar multiplication.
    // NAF could be useful to half the size of precomputation tables, but we intentionally
    // avoid these to keep the standard library lightweight.
    fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
        std.debug.assert(vartime);
        const e = slide(s);
        var q = Edwards25519.identityElement;
        var pos: usize = 2 * 32 - 1;
        while (true) : (pos -= 1) {
            const slot = e[pos];
            if (slot > 0) {
                q = q.add(pc[@as(usize, @intCast(slot))]);
            } else if (slot < 0) {
                q = q.sub(pc[@as(usize, @intCast(-slot))]);
            }
            if (pos == 0) break;
            q = q.dbl().dbl().dbl().dbl();
        }
        try q.rejectIdentity();
        return q;
    }

    // Scalar multiplication with a 4-bit window and the first 15 multiples.
    fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
        var q = Edwards25519.identityElement;
        var pos: usize = 252;
        while (true) : (pos -= 4) {
            const slot: u4 = @truncate((s[pos >> 3] >> @as(u3, @truncate(pos))));
            if (vartime) {
                if (slot != 0) {
                    q = q.add(pc[slot]);
                }
            } else {
                q = q.add(pcSelect(16, pc, slot));
            }
            if (pos == 0) break;
            q = q.dbl().dbl().dbl().dbl();
        }
        try q.rejectIdentity();
        return q;
    }

    fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519 {
        var pc: [1 + count]Edwards25519 = undefined;
        pc[0] = Edwards25519.identityElement;
        pc[1] = p;
        var i: usize = 2;
        while (i <= count) : (i += 1) {
            pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].add(p);
        }
        return pc;
    }

    const basePointPc = pc: {
        @setEvalBranchQuota(10000);
        break :pc precompute(Edwards25519.basePoint, 15);
    };

    /// Multiply an Edwards25519 point by a scalar without clamping it.
    /// Return error.WeakPublicKey if the base generates a small-order group,
    /// and error.IdentityElement if the result is the identity element.
    pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        const pc = if (p.is_base) basePointPc else pc: {
            const xpc = precompute(p, 15);
            xpc[4].rejectIdentity() catch return error.WeakPublicKey;
            break :pc xpc;
        };
        return pcMul16(&pc, s, false);
    }

    /// Multiply an Edwards25519 point by a *PUBLIC* scalar *IN VARIABLE TIME*
    /// This can be used for signature verification.
    pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        if (p.is_base) {
            return pcMul16(&basePointPc, s, true);
        } else {
            const pc = precompute(p, 8);
            pc[4].rejectIdentity() catch return error.WeakPublicKey;
            return pcMul(&pc, s, true);
        }
    }

    /// Double-base multiplication of public parameters - Compute (p1*s1)+(p2*s2) *IN VARIABLE TIME*
    /// This can be used for signature verification.
    pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        var pc1_array: [9]Edwards25519 = undefined;
        const pc1 = if (p1.is_base) basePointPc[0..9] else pc: {
            pc1_array = precompute(p1, 8);
            pc1_array[4].rejectIdentity() catch return error.WeakPublicKey;
            break :pc &pc1_array;
        };
        var pc2_array: [9]Edwards25519 = undefined;
        const pc2 = if (p2.is_base) basePointPc[0..9] else pc: {
            pc2_array = precompute(p2, 8);
            pc2_array[4].rejectIdentity() catch return error.WeakPublicKey;
            break :pc &pc2_array;
        };
        const e1 = slide(s1);
        const e2 = slide(s2);
        var q = Edwards25519.identityElement;
        var pos: usize = 2 * 32 - 1;
        while (true) : (pos -= 1) {
            const slot1 = e1[pos];
            if (slot1 > 0) {
                q = q.add(pc1[@as(usize, @intCast(slot1))]);
            } else if (slot1 < 0) {
                q = q.sub(pc1[@as(usize, @intCast(-slot1))]);
            }
            const slot2 = e2[pos];
            if (slot2 > 0) {
                q = q.add(pc2[@as(usize, @intCast(slot2))]);
            } else if (slot2 < 0) {
                q = q.sub(pc2[@as(usize, @intCast(-slot2))]);
            }
            if (pos == 0) break;
            q = q.dbl().dbl().dbl().dbl();
        }
        try q.rejectIdentity();
        return q;
    }

    /// Multiscalar multiplication *IN VARIABLE TIME* for public data
    /// Computes ps0*ss0 + ps1*ss1 + ps2*ss2... faster than doing many of these operations individually
    pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        var pcs: [count][9]Edwards25519 = undefined;

        var bpc: [9]Edwards25519 = undefined;
        @memcpy(&bpc, basePointPc[0..bpc.len]);

        for (ps, 0..) |p, i| {
            if (p.is_base) {
                pcs[i] = bpc;
            } else {
                pcs[i] = precompute(p, 8);
                pcs[i][4].rejectIdentity() catch return error.WeakPublicKey;
            }
        }
        var es: [count][2 * 32]i8 = undefined;
        for (ss, 0..) |s, i| {
            es[i] = slide(s);
        }
        var q = Edwards25519.identityElement;
        var pos: usize = 2 * 32 - 1;
        while (true) : (pos -= 1) {
            for (es, 0..) |e, i| {
                const slot = e[pos];
                if (slot > 0) {
                    q = q.add(pcs[i][@as(usize, @intCast(slot))]);
                } else if (slot < 0) {
                    q = q.sub(pcs[i][@as(usize, @intCast(-slot))]);
                }
            }
            if (pos == 0) break;
            q = q.dbl().dbl().dbl().dbl();
        }
        try q.rejectIdentity();
        return q;
    }

    /// Multiply an Edwards25519 point by a scalar after "clamping" it.
    /// Clamping forces the scalar to be a multiple of the cofactor in
    /// order to prevent small subgroups attacks.
    /// This is strongly recommended for DH operations.
    /// Return error.WeakPublicKey if the resulting point is
    /// the identity element.
    pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        var t: [32]u8 = s;
        scalar.clamp(&t);
        return mul(p, t);
    }

    // montgomery -- recover y = sqrt(x^3 + A*x^2 + x)
    fn xmontToYmont(x: Fe) NotSquareError!Fe {
        var x2 = x.sq();
        const x3 = x.mul(x2);
        x2 = x2.mul32(Fe.edwards25519a_32);
        return x.add(x2).add(x3).sqrt();
    }

    // montgomery affine coordinates to edwards extended coordinates
    fn montToEd(x: Fe, y: Fe) Edwards25519 {
        const x_plus_one = x.add(Fe.one);
        const x_minus_one = x.sub(Fe.one);
        const x_plus_one_y_inv = x_plus_one.mul(y).invert(); // 1/((x+1)*y)

        // xed = sqrt(-A-2)*x/y
        const xed = x.mul(Fe.edwards25519sqrtam2).mul(x_plus_one_y_inv).mul(x_plus_one);

        // yed = (x-1)/(x+1) or 1 if the denominator is 0
        var yed = x_plus_one_y_inv.mul(y).mul(x_minus_one);
        yed.cMov(Fe.one, @intFromBool(x_plus_one_y_inv.isZero()));

        return Edwards25519{
            .x = xed,
            .y = yed,
            .z = Fe.one,
            .t = xed.mul(yed),
        };
    }

    /// Elligator2 map - Returns Montgomery affine coordinates
    pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool } {
        const rr2 = r.sq2().add(Fe.one).invert();
        var x = rr2.mul32(Fe.edwards25519a_32).neg(); // x=x1
        var x2 = x.sq();
        const x3 = x2.mul(x);
        x2 = x2.mul32(Fe.edwards25519a_32); // x2 = A*x1^2
        const gx1 = x3.add(x).add(x2); // gx1 = x1^3 + A*x1^2 + x1
        const not_square = !gx1.isSquare();

        // gx1 not a square => x = -x1-A
        x.cMov(x.neg(), @intFromBool(not_square));
        x2 = Fe.zero;
        x2.cMov(Fe.edwards25519a, @intFromBool(not_square));
        x = x.sub(x2);

        // We have y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1*(A+x1)/(-x1)
        // but it is about as fast to just recompute y from the curve equation.
        const y = xmontToYmont(x) catch unreachable;
        return .{ .x = x, .y = y, .not_square = not_square };
    }

    /// Map a 64-bit hash into an Edwards25519 point
    pub fn fromHash(h: [64]u8) Edwards25519 {
        const fe_f = Fe.fromBytes64(h);
        var elr = elligator2(fe_f);

        const y_sign = !elr.not_square;
        const y_neg = elr.y.neg();
        elr.y.cMov(y_neg, @intFromBool(elr.y.isNegative()) ^ @intFromBool(y_sign));
        return montToEd(elr.x, elr.y).clearCofactor();
    }

    fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519 {
        debug.assert(n <= 2);
        const H = crypto.hash.sha2.Sha512;
        const h_l: usize = 48;
        var xctx = ctx;
        var hctx: [H.digest_length]u8 = undefined;
        if (ctx.len > 0xff) {
            var st = H.init(.{});
            st.update("H2C-OVERSIZE-DST-");
            st.update(ctx);
            st.final(&hctx);
            xctx = hctx[0..];
        }
        const empty_block = [_]u8{0} ** H.block_length;
        var t = [3]u8{ 0, n * h_l, 0 };
        var xctx_len_u8 = [1]u8{@as(u8, @intCast(xctx.len))};
        var st = H.init(.{});
        st.update(empty_block[0..]);
        st.update(s);
        st.update(t[0..]);
        st.update(xctx);
        st.update(xctx_len_u8[0..]);
        var u_0: [H.digest_length]u8 = undefined;
        st.final(&u_0);
        var u: [n * H.digest_length]u8 = undefined;
        var i: usize = 0;
        while (i < n * H.digest_length) : (i += H.digest_length) {
            u[i..][0..H.digest_length].* = u_0;
            var j: usize = 0;
            while (i > 0 and j < H.digest_length) : (j += 1) {
                u[i + j] ^= u[i + j - H.digest_length];
            }
            t[2] += 1;
            st = H.init(.{});
            st.update(u[i..][0..H.digest_length]);
            st.update(t[2..3]);
            st.update(xctx);
            st.update(xctx_len_u8[0..]);
            st.final(u[i..][0..H.digest_length]);
        }
        var px: [n]Edwards25519 = undefined;
        i = 0;
        while (i < n) : (i += 1) {
            @memset(u_0[0 .. H.digest_length - h_l], 0);
            u_0[H.digest_length - h_l ..][0..h_l].* = u[i * h_l ..][0..h_l].*;
            px[i] = fromHash(u_0);
        }
        return px;
    }

    /// Hash a context `ctx` and a string `s` into an Edwards25519 point
    ///
    /// This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_
    /// methods from the "Hashing to Elliptic Curves" standard document.
    ///
    /// Although not strictly required by the standard, it is recommended to avoid NUL characters in
    /// the context in order to be compatible with other implementations.
    pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519 {
        if (random_oracle) {
            const px = stringToPoints(2, ctx, s);
            return px[0].add(px[1]);
        } else {
            return stringToPoints(1, ctx, s)[0];
        }
    }

    /// Map a 32 bit uniform bit string into an edwards25519 point
    pub fn fromUniform(r: [32]u8) Edwards25519 {
        var s = r;
        const x_sign = s[31] >> 7;
        s[31] &= 0x7f;
        const elr = elligator2(Fe.fromBytes(s));
        var p = montToEd(elr.x, elr.y);
        const p_neg = p.neg();
        p.cMov(p_neg, @intFromBool(p.x.isNegative()) ^ x_sign);
        return p.clearCofactor();
    }
}