11670022056

Committed 04 Nov 2024 06:05PM UTC coverage: 55.906% (+0.02%) from 55.891%

Build # 11670022056

Build Type

Pull #3566

github

Committed by

web-flow

Commit Message

Merge ac15bd392 into a856982dd

Pull Request Pull Request #3566: Optimize the ` ToHexString`

Run Details

5792 of 8932 branches covered (64.85%)

Branch coverage included in aggregate %.

32 of 32 new or added lines in 2 files covered. (100.0%)

10 existing lines in 1 file now uncovered.

21753 of 40338 relevant lines covered (53.93%)

86354.94 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.37

/src/Neo.Cryptography.BLS12_381/Scalar.cs

// Copyright (C) 2015-2024 The Neo Project.
//
// Scalar.cs file belongs to the neo project and is free
// software distributed under the MIT software license, see the
// accompanying file LICENSE in the main directory of the
// repository or http://www.opensource.org/licenses/mit-license.php
// for more details.
//
// Redistribution and use in source and binary forms with or without
// modifications are permitted.

using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using System.Text;
using static Neo.Cryptography.BLS12_381.ConstantTimeUtility;
using static Neo.Cryptography.BLS12_381.MathUtility;
using static Neo.Cryptography.BLS12_381.ScalarConstants;

namespace Neo.Cryptography.BLS12_381;

[StructLayout(LayoutKind.Explicit, Size = Size)]
public readonly struct Scalar : IEquatable<Scalar>, INumber<Scalar>
{
    public const int Size = 32;
    public const int SizeL = Size / sizeof(ulong);
    public static readonly Scalar Default = new();

    public static ref readonly Scalar Zero => ref Default;
    public static ref readonly Scalar One => ref R;

    public bool IsZero => this == Zero;

    internal Scalar(ulong[] values)
    {
        if (values.Length != SizeL)
            throw new FormatException($"The argument `{nameof(values)}` must contain {SizeL} entries.");

        // This internal method is only used by the constants classes.
        // The data must be in the correct format.
        // So, there is no need to do any additional checks.
        this = Unsafe.As<byte, Scalar>(ref MemoryMarshal.GetReference(MemoryMarshal.Cast<ulong, byte>(values)));
    }

    public Scalar(ulong value)
    {
        Span<ulong> data = stackalloc ulong[SizeL];
        data[0] = value;
        this = FromRaw(data);
    }

    public Scalar(RandomNumberGenerator rng)
    {
        Span<byte> buffer = stackalloc byte[Size * 2];
        rng.GetBytes(buffer);
        this = FromBytesWide(buffer);
    }

    public static Scalar FromBytes(ReadOnlySpan<byte> data)
    {
        if (data.Length != Size)
            throw new FormatException($"The argument `{nameof(data)}` must contain {Size} bytes.");

        ref readonly Scalar ref_ = ref Unsafe.As<byte, Scalar>(ref MemoryMarshal.GetReference(data));

        try
        {
            return ref_ * R2;
        }
        finally
        {
            ReadOnlySpan<ulong> u64 = MemoryMarshal.Cast<byte, ulong>(data);
            ulong borrow = 0;
            (_, borrow) = Sbb(u64[0], MODULUS_LIMBS_64[0], borrow);
            (_, borrow) = Sbb(u64[1], MODULUS_LIMBS_64[1], borrow);
            (_, borrow) = Sbb(u64[2], MODULUS_LIMBS_64[2], borrow);
            (_, borrow) = Sbb(u64[3], MODULUS_LIMBS_64[3], borrow);
            if (borrow == 0)
            {
                // If the element is smaller than MODULUS then the subtraction will underflow.
                // Otherwise, throws.
                // Why not throw before return?
                // Because we want to run the method in a constant time.
                throw new FormatException();
            }
        }
    }

    public static Scalar FromBytesWide(ReadOnlySpan<byte> data)
    {
        if (data.Length != Size * 2)
            throw new FormatException($"The argument `{nameof(data)}` must contain {Size * 2} bytes.");

        ReadOnlySpan<Scalar> d = MemoryMarshal.Cast<byte, Scalar>(data);
        return d[0] * R2 + d[1] * R3;
    }

    public static Scalar FromRaw(ReadOnlySpan<ulong> data)
    {
        if (data.Length != SizeL)
            throw new FormatException($"The argument `{nameof(data)}` must contain {SizeL} entries.");

        ReadOnlySpan<Scalar> span = MemoryMarshal.Cast<ulong, Scalar>(data);
        return span[0] * R2;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private ReadOnlySpan<byte> GetSpan()
    {
        return MemoryMarshal.AsBytes(MemoryMarshal.CreateReadOnlySpan(ref Unsafe.AsRef(in this), 1));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private Span<ulong> GetSpanU64()
    {
        return MemoryMarshal.Cast<Scalar, ulong>(MemoryMarshal.CreateSpan(ref Unsafe.AsRef(in this), 1));
    }

    public override string ToString()
    {
        byte[] bytes = ToArray();
        StringBuilder sb = new();
        sb.Append("0x");
        for (int i = bytes.Length - 1; i >= 0; i--)
            sb.AppendFormat("{0:x2}", bytes[i]);
        return sb.ToString();
    }

    public static bool operator ==(in Scalar a, in Scalar b)
    {
        return ConstantTimeEq(in a, in b);
    }

    public static bool operator !=(in Scalar a, in Scalar b)
    {
        return !(a == b);
    }

    public override bool Equals([NotNullWhen(true)] object? obj)
    {
        if (obj is not Scalar other) return false;
        return this == other;
    }

    public bool Equals(Scalar other)
    {
        return this == other;
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    public Scalar Double()
    {
        return this + this;
    }

    public byte[] ToArray()
    {
        ReadOnlySpan<ulong> self = GetSpanU64();

        // Turn into canonical form by computing
        // (a.R) / R = a
        Scalar result = MontgomeryReduce(self[0], self[1], self[2], self[3], 0, 0, 0, 0);
        return result.GetSpan().ToArray();
    }

    public Scalar Square()
    {
        ReadOnlySpan<ulong> self = GetSpanU64();
        ulong r0, r1, r2, r3, r4, r5, r6, r7;
        ulong carry;

        (r1, carry) = Mac(0, self[0], self[1], 0);
        (r2, carry) = Mac(0, self[0], self[2], carry);
        (r3, r4) = Mac(0, self[0], self[3], carry);

        (r3, carry) = Mac(r3, self[1], self[2], 0);
        (r4, r5) = Mac(r4, self[1], self[3], carry);

        (r5, r6) = Mac(r5, self[2], self[3], 0);

        r7 = r6 >> 63;
        r6 = (r6 << 1) | (r5 >> 63);
        r5 = (r5 << 1) | (r4 >> 63);
        r4 = (r4 << 1) | (r3 >> 63);
        r3 = (r3 << 1) | (r2 >> 63);
        r2 = (r2 << 1) | (r1 >> 63);
        r1 <<= 1;

        (r0, carry) = Mac(0, self[0], self[0], 0);
        (r1, carry) = Adc(r1, carry, 0);
        (r2, carry) = Mac(r2, self[1], self[1], carry);
        (r3, carry) = Adc(r3, carry, 0);
        (r4, carry) = Mac(r4, self[2], self[2], carry);
        (r5, carry) = Adc(r5, carry, 0);
        (r6, carry) = Mac(r6, self[3], self[3], carry);
        (r7, _) = Adc(r7, carry, 0);

        return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);
    }

    public Scalar Sqrt()
    {
        // Tonelli-Shank's algorithm for q mod 16 = 1
        // https://eprint.iacr.org/2012/685.pdf (page 12, algorithm 5)

        // w = self^((t - 1) // 2)
        //   = self^6104339283789297388802252303364915521546564123189034618274734669823
        var w = this.PowVartime(new ulong[]
        {
            0x7fff_2dff_7fff_ffff,
            0x04d0_ec02_a9de_d201,
            0x94ce_bea4_199c_ec04,
            0x0000_0000_39f6_d3a9
        });

        var v = S;
        var x = this * w;
        var b = x * w;

        // Initialize z as the 2^S root of unity.
        var z = ROOT_OF_UNITY;

        for (uint max_v = S; max_v >= 1; max_v--)
        {
            uint k = 1;
            var tmp = b.Square();
            var j_less_than_v = true;

            for (uint j = 2; j < max_v; j++)
            {
                var tmp_is_one = tmp == One;
                var squared = ConditionalSelect(in tmp, in z, tmp_is_one).Square();
                tmp = ConditionalSelect(in squared, in tmp, tmp_is_one);
                var new_z = ConditionalSelect(in z, in squared, tmp_is_one);
                j_less_than_v &= j != v;
                k = ConditionalSelect(j, k, tmp_is_one);
                z = ConditionalSelect(in z, in new_z, j_less_than_v);
            }

            var result = x * z;
            x = ConditionalSelect(in result, in x, b == One);
            z = z.Square();
            b *= z;
            v = k;
        }

        if (x * x != this) throw new ArithmeticException();
        return x;
    }

    public Scalar Pow(ulong[] by)
    {
        if (by.Length != SizeL)
            throw new ArgumentException($"The length of the parameter `{nameof(by)}` must be {SizeL}.");

        var res = One;
        for (int j = by.Length - 1; j >= 0; j--)
        {
            for (int i = 63; i >= 0; i--)
            {
                res = res.Square();
                var tmp = res;
                tmp *= this;
                res.ConditionalAssign(in tmp, ((by[j] >> i) & 1) == 1);
            }
        }
        return res;
    }

    public Scalar Invert()
    {
        static void SquareAssignMulti(ref Scalar n, int num_times)
        {
            for (int i = 0; i < num_times; i++)
            {
                n = n.Square();
            }
        }

        var t0 = Square();
        var t1 = t0 * this;
        var t16 = t0.Square();
        var t6 = t16.Square();
        var t5 = t6 * t0;
        t0 = t6 * t16;
        var t12 = t5 * t16;
        var t2 = t6.Square();
        var t7 = t5 * t6;
        var t15 = t0 * t5;
        var t17 = t12.Square();
        t1 *= t17;
        var t3 = t7 * t2;
        var t8 = t1 * t17;
        var t4 = t8 * t2;
        var t9 = t8 * t7;
        t7 = t4 * t5;
        var t11 = t4 * t17;
        t5 = t9 * t17;
        var t14 = t7 * t15;
        var t13 = t11 * t12;
        t12 = t11 * t17;
        t15 *= t12;
        t16 *= t15;
        t3 *= t16;
        t17 *= t3;
        t0 *= t17;
        t6 *= t0;
        t2 *= t6;
        SquareAssignMulti(ref t0, 8);
        t0 *= t17;
        SquareAssignMulti(ref t0, 9);
        t0 *= t16;
        SquareAssignMulti(ref t0, 9);
        t0 *= t15;
        SquareAssignMulti(ref t0, 9);
        t0 *= t15;
        SquareAssignMulti(ref t0, 7);
        t0 *= t14;
        SquareAssignMulti(ref t0, 7);
        t0 *= t13;
        SquareAssignMulti(ref t0, 10);
        t0 *= t12;
        SquareAssignMulti(ref t0, 9);
        t0 *= t11;
        SquareAssignMulti(ref t0, 8);
        t0 *= t8;
        SquareAssignMulti(ref t0, 8);
        t0 *= this;
        SquareAssignMulti(ref t0, 14);
        t0 *= t9;
        SquareAssignMulti(ref t0, 10);
        t0 *= t8;
        SquareAssignMulti(ref t0, 15);
        t0 *= t7;
        SquareAssignMulti(ref t0, 10);
        t0 *= t6;
        SquareAssignMulti(ref t0, 8);
        t0 *= t5;
        SquareAssignMulti(ref t0, 16);
        t0 *= t3;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 7);
        t0 *= t4;
        SquareAssignMulti(ref t0, 9);
        t0 *= t2;
        SquareAssignMulti(ref t0, 8);
        t0 *= t3;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 8);
        t0 *= t3;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 8);
        t0 *= t2;
        SquareAssignMulti(ref t0, 5);
        t0 *= t1;
        SquareAssignMulti(ref t0, 5);
        t0 *= t1;

        if (this == Zero) throw new DivideByZeroException();
        return t0;
    }

    private static Scalar MontgomeryReduce(ulong r0, ulong r1, ulong r2, ulong r3, ulong r4, ulong r5, ulong r6, ulong r7)
    {
        // The Montgomery reduction here is based on Algorithm 14.32 in
        // Handbook of Applied Cryptography
        // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.

        ulong carry, carry2;

        var k = unchecked(r0 * INV);
        (_, carry) = Mac(r0, k, MODULUS_LIMBS_64[0], 0);
        (r1, carry) = Mac(r1, k, MODULUS_LIMBS_64[1], carry);
        (r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[2], carry);
        (r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[3], carry);
        (r4, carry2) = Adc(r4, 0, carry);

        k = unchecked(r1 * INV);
        (_, carry) = Mac(r1, k, MODULUS_LIMBS_64[0], 0);
        (r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[1], carry);
        (r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[2], carry);
        (r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[3], carry);
        (r5, carry2) = Adc(r5, carry2, carry);

        k = unchecked(r2 * INV);
        (_, carry) = Mac(r2, k, MODULUS_LIMBS_64[0], 0);
        (r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[1], carry);
        (r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[2], carry);
        (r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[3], carry);
        (r6, carry2) = Adc(r6, carry2, carry);

        k = unchecked(r3 * INV);
        (_, carry) = Mac(r3, k, MODULUS_LIMBS_64[0], 0);
        (r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[1], carry);
        (r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[2], carry);
        (r6, carry) = Mac(r6, k, MODULUS_LIMBS_64[3], carry);
        (r7, _) = Adc(r7, carry2, carry);

        // Result may be within MODULUS of the correct value
        ReadOnlySpan<ulong> tmp = stackalloc[] { r4, r5, r6, r7 };
        return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;
    }

    public static Scalar operator *(in Scalar a, in Scalar b)
    {
        ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();
        ulong r0, r1, r2, r3, r4, r5, r6, r7;
        ulong carry;

        (r0, carry) = Mac(0, self[0], rhs[0], 0);
        (r1, carry) = Mac(0, self[0], rhs[1], carry);
        (r2, carry) = Mac(0, self[0], rhs[2], carry);
        (r3, r4) = Mac(0, self[0], rhs[3], carry);

        (r1, carry) = Mac(r1, self[1], rhs[0], 0);
        (r2, carry) = Mac(r2, self[1], rhs[1], carry);
        (r3, carry) = Mac(r3, self[1], rhs[2], carry);
        (r4, r5) = Mac(r4, self[1], rhs[3], carry);

        (r2, carry) = Mac(r2, self[2], rhs[0], 0);
        (r3, carry) = Mac(r3, self[2], rhs[1], carry);
        (r4, carry) = Mac(r4, self[2], rhs[2], carry);
        (r5, r6) = Mac(r5, self[2], rhs[3], carry);

        (r3, carry) = Mac(r3, self[3], rhs[0], 0);
        (r4, carry) = Mac(r4, self[3], rhs[1], carry);
        (r5, carry) = Mac(r5, self[3], rhs[2], carry);
        (r6, r7) = Mac(r6, self[3], rhs[3], carry);

        return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);
    }

    public static Scalar operator -(in Scalar a, in Scalar b)
    {
        ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();
        ulong d0, d1, d2, d3;
        ulong carry, borrow;

        (d0, borrow) = Sbb(self[0], rhs[0], 0);
        (d1, borrow) = Sbb(self[1], rhs[1], borrow);
        (d2, borrow) = Sbb(self[2], rhs[2], borrow);
        (d3, borrow) = Sbb(self[3], rhs[3], borrow);

        borrow = borrow == 0 ? ulong.MinValue : ulong.MaxValue;
        (d0, carry) = Adc(d0, MODULUS_LIMBS_64[0] & borrow, 0);
        (d1, carry) = Adc(d1, MODULUS_LIMBS_64[1] & borrow, carry);
        (d2, carry) = Adc(d2, MODULUS_LIMBS_64[2] & borrow, carry);
        (d3, _) = Adc(d3, MODULUS_LIMBS_64[3] & borrow, carry);

        ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };
        return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];
    }

    public static Scalar operator +(in Scalar a, in Scalar b)
    {
        ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();
        ulong d0, d1, d2, d3;
        ulong carry;

        (d0, carry) = Adc(self[0], rhs[0], 0);
        (d1, carry) = Adc(self[1], rhs[1], carry);
        (d2, carry) = Adc(self[2], rhs[2], carry);
        (d3, _) = Adc(self[3], rhs[3], carry);

        // Attempt to subtract the modulus, to ensure the value
        // is smaller than the modulus.
        ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };
        return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;
    }

    public static Scalar operator -(in Scalar a)
    {
        ReadOnlySpan<ulong> self = a.GetSpanU64();
        ulong d0, d1, d2, d3;
        ulong borrow;

        // Subtract `self` from `MODULUS` to negate. Ignore the final
        // borrow because it cannot underflow; self is guaranteed to
        // be in the field.
        (d0, borrow) = Sbb(MODULUS_LIMBS_64[0], self[0], 0);
        (d1, borrow) = Sbb(MODULUS_LIMBS_64[1], self[1], borrow);
        (d2, borrow) = Sbb(MODULUS_LIMBS_64[2], self[2], borrow);
        (d3, _) = Sbb(MODULUS_LIMBS_64[3], self[3], borrow);

        // `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
        // zero if `self` was zero, and `u64::max_value()` if self was nonzero.
        ulong mask = a.IsZero ? ulong.MinValue : ulong.MaxValue;

        ReadOnlySpan<ulong> tmp = stackalloc[] { d0 & mask, d1 & mask, d2 & mask, d3 & mask };
        return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];
    }

    #region Instance math methods

    public Scalar Negate() => -this;
    public Scalar Multiply(in Scalar value) => this * value;
    public Scalar Sum(in Scalar value) => this + value;
    public Scalar Subtract(in Scalar value) => this - value;

    #endregion
}

1	// Copyright (C) 2015-2024 The Neo Project.
2	//
3	// Scalar.cs file belongs to the neo project and is free
4	// software distributed under the MIT software license, see the
5	// accompanying file LICENSE in the main directory of the
6	// repository or http://www.opensource.org/licenses/mit-license.php
7	// for more details.
8	//
9	// Redistribution and use in source and binary forms with or without
10	// modifications are permitted.
11
12	using System.Diagnostics.CodeAnalysis;
13	using System.Runtime.CompilerServices;
14	using System.Runtime.InteropServices;
15	using System.Security.Cryptography;
16	using System.Text;
17	using static Neo.Cryptography.BLS12_381.ConstantTimeUtility;
18	using static Neo.Cryptography.BLS12_381.MathUtility;
19	using static Neo.Cryptography.BLS12_381.ScalarConstants;
20
21	namespace Neo.Cryptography.BLS12_381;
22
23	[StructLayout(LayoutKind.Explicit, Size = Size)]
24	public readonly struct Scalar : IEquatable<Scalar>, INumber<Scalar>
25	{
26	public const int Size = 32;
27	public const int SizeL = Size / sizeof(ulong);
28	public static readonly Scalar Default = new();	2✔
29
30	public static ref readonly Scalar Zero => ref Default;	445✔
31	public static ref readonly Scalar One => ref R;	50,711✔
32
33	public bool IsZero => this == Zero;	14✔
34
35	internal Scalar(ulong[] values)
36	{	19✔
37	if (values.Length != SizeL)	19!
UNCOV 38	throw new FormatException($"The argument `{nameof(values)}` must contain {SizeL} entries.");	×
39
40	// This internal method is only used by the constants classes.
41	// The data must be in the correct format.
42	// So, there is no need to do any additional checks.
43	this = Unsafe.As<byte, Scalar>(ref MemoryMarshal.GetReference(MemoryMarshal.Cast<ulong, byte>(values)));	19✔
44	}	19✔
45
46	public Scalar(ulong value)
47	{	6✔
48	Span<ulong> data = stackalloc ulong[SizeL];	6✔
49	data[0] = value;	6✔
50	this = FromRaw(data);	6✔
51	}	6✔
52
53	public Scalar(RandomNumberGenerator rng)
UNCOV 54	{	×
55	Span<byte> buffer = stackalloc byte[Size * 2];	×
56	rng.GetBytes(buffer);	×
57	this = FromBytesWide(buffer);	×
58	}	×
59
60	public static Scalar FromBytes(ReadOnlySpan<byte> data)
61	{	21✔
62	if (data.Length != Size)	21!
UNCOV 63	throw new FormatException($"The argument `{nameof(data)}` must contain {Size} bytes.");	×
64
65	ref readonly Scalar ref_ = ref Unsafe.As<byte, Scalar>(ref MemoryMarshal.GetReference(data));	21✔
66
67	try
68	{	21✔
69	return ref_ * R2;	21✔
70	}
71	finally
72	{	21✔
73	ReadOnlySpan<ulong> u64 = MemoryMarshal.Cast<byte, ulong>(data);	21✔
74	ulong borrow = 0;	21✔
75	(_, borrow) = Sbb(u64[0], MODULUS_LIMBS_64[0], borrow);	21✔
76	(_, borrow) = Sbb(u64[1], MODULUS_LIMBS_64[1], borrow);	21✔
77	(_, borrow) = Sbb(u64[2], MODULUS_LIMBS_64[2], borrow);	21✔
78	(_, borrow) = Sbb(u64[3], MODULUS_LIMBS_64[3], borrow);	21✔
79	if (borrow == 0)	21✔
80	{	4✔
81	// If the element is smaller than MODULUS then the subtraction will underflow.
82	// Otherwise, throws.
83	// Why not throw before return?
84	// Because we want to run the method in a constant time.
85	throw new FormatException();	4✔
86	}
87	}	17✔
88	}	17✔
89
90	public static Scalar FromBytesWide(ReadOnlySpan<byte> data)
91	{	3✔
92	if (data.Length != Size * 2)	3!
UNCOV 93	throw new FormatException($"The argument `{nameof(data)}` must contain {Size * 2} bytes.");	×
94
95	ReadOnlySpan<Scalar> d = MemoryMarshal.Cast<byte, Scalar>(data);	3✔
96	return d[0] * R2 + d[1] * R3;	3✔
97	}	3✔
98
99	public static Scalar FromRaw(ReadOnlySpan<ulong> data)
100	{	21✔
101	if (data.Length != SizeL)	21!
UNCOV 102	throw new FormatException($"The argument `{nameof(data)}` must contain {SizeL} entries.");	×
103
104	ReadOnlySpan<Scalar> span = MemoryMarshal.Cast<ulong, Scalar>(data);	21✔
105	return span[0] * R2;	21✔
106	}	21✔
107
108	[MethodImpl(MethodImplOptions.AggressiveInlining)]
109	private ReadOnlySpan<byte> GetSpan()
110	{	243✔
111	return MemoryMarshal.AsBytes(MemoryMarshal.CreateReadOnlySpan(ref Unsafe.AsRef(in this), 1));	243✔
112	}	243✔
113
114	[MethodImpl(MethodImplOptions.AggressiveInlining)]
115	private Span<ulong> GetSpanU64()
116	{	1,147,888✔
117	return MemoryMarshal.Cast<Scalar, ulong>(MemoryMarshal.CreateSpan(ref Unsafe.AsRef(in this), 1));	1,147,888✔
118	}	1,147,888✔
119
120	public override string ToString()
121	{	3✔
122	byte[] bytes = ToArray();	3✔
123	StringBuilder sb = new();	3✔
124	sb.Append("0x");	3✔
125	for (int i = bytes.Length - 1; i >= 0; i--)	198✔
126	sb.AppendFormat("{0:x2}", bytes[i]);	96✔
127	return sb.ToString();	3✔
128	}	3✔
129
130	public static bool operator ==(in Scalar a, in Scalar b)
131	{	51,097✔
132	return ConstantTimeEq(in a, in b);	51,097✔
133	}	51,097✔
134
135	public static bool operator !=(in Scalar a, in Scalar b)
136	{	101✔
137	return !(a == b);	101✔
138	}	101✔
139
140	public override bool Equals([NotNullWhen(true)] object? obj)
UNCOV 141	{	×
142	if (obj is not Scalar other) return false;	×
143	return this == other;	×
144	}	×
145
146	public bool Equals(Scalar other)
147	{	580✔
148	return this == other;	580✔
149	}	580✔
150
151	public override int GetHashCode()
UNCOV 152	{	×
153	return base.GetHashCode();	×
154	}	×
155
156	public Scalar Double()
157	{	1✔
158	return this + this;	1✔
159	}	1✔
160
161	public byte[] ToArray()
162	{	243✔
163	ReadOnlySpan<ulong> self = GetSpanU64();	243✔
164
165	// Turn into canonical form by computing
166	// (a.R) / R = a
167	Scalar result = MontgomeryReduce(self[0], self[1], self[2], self[3], 0, 0, 0, 0);	243✔
168	return result.GetSpan().ToArray();	243✔
169	}	243✔
170
171	public Scalar Square()
172	{	182,247✔
173	ReadOnlySpan<ulong> self = GetSpanU64();	182,247✔
174	ulong r0, r1, r2, r3, r4, r5, r6, r7;
175	ulong carry;
176
177	(r1, carry) = Mac(0, self[0], self[1], 0);	182,247✔
178	(r2, carry) = Mac(0, self[0], self[2], carry);	182,247✔
179	(r3, r4) = Mac(0, self[0], self[3], carry);	182,247✔
180
181	(r3, carry) = Mac(r3, self[1], self[2], 0);	182,247✔
182	(r4, r5) = Mac(r4, self[1], self[3], carry);	182,247✔
183
184	(r5, r6) = Mac(r5, self[2], self[3], 0);	182,247✔
185
186	r7 = r6 >> 63;	182,247✔
187	r6 = (r6 << 1) \| (r5 >> 63);	182,247✔
188	r5 = (r5 << 1) \| (r4 >> 63);	182,247✔
189	r4 = (r4 << 1) \| (r3 >> 63);	182,247✔
190	r3 = (r3 << 1) \| (r2 >> 63);	182,247✔
191	r2 = (r2 << 1) \| (r1 >> 63);	182,247✔
192	r1 <<= 1;	182,247✔
193
194	(r0, carry) = Mac(0, self[0], self[0], 0);	182,247✔
195	(r1, carry) = Adc(r1, carry, 0);	182,247✔
196	(r2, carry) = Mac(r2, self[1], self[1], carry);	182,247✔
197	(r3, carry) = Adc(r3, carry, 0);	182,247✔
198	(r4, carry) = Mac(r4, self[2], self[2], carry);	182,247✔
199	(r5, carry) = Adc(r5, carry, 0);	182,247✔
200	(r6, carry) = Mac(r6, self[3], self[3], carry);	182,247✔
201	(r7, _) = Adc(r7, carry, 0);	182,247✔
202
203	return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);	182,247✔
204	}	182,247✔
205
206	public Scalar Sqrt()
207	{	101✔
208	// Tonelli-Shank's algorithm for q mod 16 = 1
209	// https://eprint.iacr.org/2012/685.pdf (page 12, algorithm 5)
210
211	// w = self^((t - 1) // 2)
212	// = self^6104339283789297388802252303364915521546564123189034618274734669823
213	var w = this.PowVartime(new ulong[]	101✔
214	{	101✔
215	0x7fff_2dff_7fff_ffff,	101✔
216	0x04d0_ec02_a9de_d201,	101✔
217	0x94ce_bea4_199c_ec04,	101✔
218	0x0000_0000_39f6_d3a9	101✔
219	});	101✔
220
221	var v = S;	101✔
222	var x = this * w;	101✔
223	var b = x * w;	101✔
224
225	// Initialize z as the 2^S root of unity.
226	var z = ROOT_OF_UNITY;	101✔
227
228	for (uint max_v = S; max_v >= 1; max_v--)	6,666✔
229	{	3,232✔
230	uint k = 1;	3,232✔
231	var tmp = b.Square();	3,232✔
232	var j_less_than_v = true;	3,232✔
233
234	for (uint j = 2; j < max_v; j++)	100,394✔
235	{	46,965✔
236	var tmp_is_one = tmp == One;	46,965✔
237	var squared = ConditionalSelect(in tmp, in z, tmp_is_one).Square();	46,965✔
238	tmp = ConditionalSelect(in squared, in tmp, tmp_is_one);	46,965✔
239	var new_z = ConditionalSelect(in z, in squared, tmp_is_one);	46,965✔
240	j_less_than_v &= j != v;	46,965✔
241	k = ConditionalSelect(j, k, tmp_is_one);	46,965✔
242	z = ConditionalSelect(in z, in new_z, j_less_than_v);	46,965✔
243	}	46,965✔
244
245	var result = x * z;	3,232✔
246	x = ConditionalSelect(in result, in x, b == One);	3,232✔
247	z = z.Square();	3,232✔
248	b *= z;	3,232✔
249	v = k;	3,232✔
250	}	3,232✔
251
252	if (x * x != this) throw new ArithmeticException();	150✔
253	return x;	52✔
254	}	52✔
255
256	public Scalar Pow(ulong[] by)
257	{	100✔
258	if (by.Length != SizeL)	100!
UNCOV 259	throw new ArgumentException($"The length of the parameter `{nameof(by)}` must be {SizeL}.");	×
260
261	var res = One;	100✔
262	for (int j = by.Length - 1; j >= 0; j--)	1,000✔
263	{	400✔
264	for (int i = 63; i >= 0; i--)	52,000✔
265	{	25,600✔
266	res = res.Square();	25,600✔
267	var tmp = res;	25,600✔
268	tmp *= this;	25,600✔
269	res.ConditionalAssign(in tmp, ((by[j] >> i) & 1) == 1);	25,600✔
270	}	25,600✔
271	}	400✔
272	return res;	100✔
273	}	100✔
274
275	public Scalar Invert()
276	{	205✔
277	static void SquareAssignMulti(ref Scalar n, int num_times)
278	{	5,740✔
279	for (int i = 0; i < num_times; i++)	112,750✔
280	{	50,635✔
281	n = n.Square();	50,635✔
282	}	50,635✔
283	}	5,740✔
284
285	var t0 = Square();	205✔
286	var t1 = t0 * this;	205✔
287	var t16 = t0.Square();	205✔
288	var t6 = t16.Square();	205✔
289	var t5 = t6 * t0;	205✔
290	t0 = t6 * t16;	205✔
291	var t12 = t5 * t16;	205✔
292	var t2 = t6.Square();	205✔
293	var t7 = t5 * t6;	205✔
294	var t15 = t0 * t5;	205✔
295	var t17 = t12.Square();	205✔
296	t1 *= t17;	205✔
297	var t3 = t7 * t2;	205✔
298	var t8 = t1 * t17;	205✔
299	var t4 = t8 * t2;	205✔
300	var t9 = t8 * t7;	205✔
301	t7 = t4 * t5;	205✔
302	var t11 = t4 * t17;	205✔
303	t5 = t9 * t17;	205✔
304	var t14 = t7 * t15;	205✔
305	var t13 = t11 * t12;	205✔
306	t12 = t11 * t17;	205✔
307	t15 *= t12;	205✔
308	t16 *= t15;	205✔
309	t3 *= t16;	205✔
310	t17 *= t3;	205✔
311	t0 *= t17;	205✔
312	t6 *= t0;	205✔
313	t2 *= t6;	205✔
314	SquareAssignMulti(ref t0, 8);	205✔
315	t0 *= t17;	205✔
316	SquareAssignMulti(ref t0, 9);	205✔
317	t0 *= t16;	205✔
318	SquareAssignMulti(ref t0, 9);	205✔
319	t0 *= t15;	205✔
320	SquareAssignMulti(ref t0, 9);	205✔
321	t0 *= t15;	205✔
322	SquareAssignMulti(ref t0, 7);	205✔
323	t0 *= t14;	205✔
324	SquareAssignMulti(ref t0, 7);	205✔
325	t0 *= t13;	205✔
326	SquareAssignMulti(ref t0, 10);	205✔
327	t0 *= t12;	205✔
328	SquareAssignMulti(ref t0, 9);	205✔
329	t0 *= t11;	205✔
330	SquareAssignMulti(ref t0, 8);	205✔
331	t0 *= t8;	205✔
332	SquareAssignMulti(ref t0, 8);	205✔
333	t0 *= this;	205✔
334	SquareAssignMulti(ref t0, 14);	205✔
335	t0 *= t9;	205✔
336	SquareAssignMulti(ref t0, 10);	205✔
337	t0 *= t8;	205✔
338	SquareAssignMulti(ref t0, 15);	205✔
339	t0 *= t7;	205✔
340	SquareAssignMulti(ref t0, 10);	205✔
341	t0 *= t6;	205✔
342	SquareAssignMulti(ref t0, 8);	205✔
343	t0 *= t5;	205✔
344	SquareAssignMulti(ref t0, 16);	205✔
345	t0 *= t3;	205✔
346	SquareAssignMulti(ref t0, 8);	205✔
347	t0 *= t2;	205✔
348	SquareAssignMulti(ref t0, 7);	205✔
349	t0 *= t4;	205✔
350	SquareAssignMulti(ref t0, 9);	205✔
351	t0 *= t2;	205✔
352	SquareAssignMulti(ref t0, 8);	205✔
353	t0 *= t3;	205✔
354	SquareAssignMulti(ref t0, 8);	205✔
355	t0 *= t2;	205✔
356	SquareAssignMulti(ref t0, 8);	205✔
357	t0 *= t2;	205✔
358	SquareAssignMulti(ref t0, 8);	205✔
359	t0 *= t2;	205✔
360	SquareAssignMulti(ref t0, 8);	205✔
361	t0 *= t3;	205✔
362	SquareAssignMulti(ref t0, 8);	205✔
363	t0 *= t2;	205✔
364	SquareAssignMulti(ref t0, 8);	205✔
365	t0 *= t2;	205✔
366	SquareAssignMulti(ref t0, 5);	205✔
367	t0 *= t1;	205✔
368	SquareAssignMulti(ref t0, 5);	205✔
369	t0 *= t1;	205✔
370
371	if (this == Zero) throw new DivideByZeroException();	206✔
372	return t0;	204✔
373	}	204✔
374
375	private static Scalar MontgomeryReduce(ulong r0, ulong r1, ulong r2, ulong r3, ulong r4, ulong r5, ulong r6, ulong r7)
376	{	255,554✔
377	// The Montgomery reduction here is based on Algorithm 14.32 in
378	// Handbook of Applied Cryptography
379	// <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
380
381	ulong carry, carry2;
382
383	var k = unchecked(r0 * INV);	255,554✔
384	(_, carry) = Mac(r0, k, MODULUS_LIMBS_64[0], 0);	255,554✔
385	(r1, carry) = Mac(r1, k, MODULUS_LIMBS_64[1], carry);	255,554✔
386	(r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[2], carry);	255,554✔
387	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[3], carry);	255,554✔
388	(r4, carry2) = Adc(r4, 0, carry);	255,554✔
389
390	k = unchecked(r1 * INV);	255,554✔
391	(_, carry) = Mac(r1, k, MODULUS_LIMBS_64[0], 0);	255,554✔
392	(r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[1], carry);	255,554✔
393	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[2], carry);	255,554✔
394	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[3], carry);	255,554✔
395	(r5, carry2) = Adc(r5, carry2, carry);	255,554✔
396
397	k = unchecked(r2 * INV);	255,554✔
398	(_, carry) = Mac(r2, k, MODULUS_LIMBS_64[0], 0);	255,554✔
399	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[1], carry);	255,554✔
400	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[2], carry);	255,554✔
401	(r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[3], carry);	255,554✔
402	(r6, carry2) = Adc(r6, carry2, carry);	255,554✔
403
404	k = unchecked(r3 * INV);	255,554✔
405	(_, carry) = Mac(r3, k, MODULUS_LIMBS_64[0], 0);	255,554✔
406	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[1], carry);	255,554✔
407	(r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[2], carry);	255,554✔
408	(r6, carry) = Mac(r6, k, MODULUS_LIMBS_64[3], carry);	255,554✔
409	(r7, _) = Adc(r7, carry2, carry);	255,554✔
410
411	// Result may be within MODULUS of the correct value
412	ReadOnlySpan<ulong> tmp = stackalloc[] { r4, r5, r6, r7 };	255,554✔
413	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;	255,554✔
414	}	255,554✔
415
416	public static Scalar operator *(in Scalar a, in Scalar b)
417	{	73,064✔
418	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	146,128✔
419	ulong r0, r1, r2, r3, r4, r5, r6, r7;
420	ulong carry;
421
422	(r0, carry) = Mac(0, self[0], rhs[0], 0);	73,064✔
423	(r1, carry) = Mac(0, self[0], rhs[1], carry);	73,064✔
424	(r2, carry) = Mac(0, self[0], rhs[2], carry);	73,064✔
425	(r3, r4) = Mac(0, self[0], rhs[3], carry);	73,064✔
426
427	(r1, carry) = Mac(r1, self[1], rhs[0], 0);	73,064✔
428	(r2, carry) = Mac(r2, self[1], rhs[1], carry);	73,064✔
429	(r3, carry) = Mac(r3, self[1], rhs[2], carry);	73,064✔
430	(r4, r5) = Mac(r4, self[1], rhs[3], carry);	73,064✔
431
432	(r2, carry) = Mac(r2, self[2], rhs[0], 0);	73,064✔
433	(r3, carry) = Mac(r3, self[2], rhs[1], carry);	73,064✔
434	(r4, carry) = Mac(r4, self[2], rhs[2], carry);	73,064✔
435	(r5, r6) = Mac(r5, self[2], rhs[3], carry);	73,064✔
436
437	(r3, carry) = Mac(r3, self[3], rhs[0], 0);	73,064✔
438	(r4, carry) = Mac(r4, self[3], rhs[1], carry);	73,064✔
439	(r5, carry) = Mac(r5, self[3], rhs[2], carry);	73,064✔
440	(r6, r7) = Mac(r6, self[3], rhs[3], carry);	73,064✔
441
442	return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);	73,064✔
443	}	73,064✔
444
445	public static Scalar operator -(in Scalar a, in Scalar b)
446	{	332,643✔
447	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	665,286✔
448	ulong d0, d1, d2, d3;
449	ulong carry, borrow;
450
451	(d0, borrow) = Sbb(self[0], rhs[0], 0);	332,643✔
452	(d1, borrow) = Sbb(self[1], rhs[1], borrow);	332,643✔
453	(d2, borrow) = Sbb(self[2], rhs[2], borrow);	332,643✔
454	(d3, borrow) = Sbb(self[3], rhs[3], borrow);	332,643✔
455
456	borrow = borrow == 0 ? ulong.MinValue : ulong.MaxValue;	332,643✔
457	(d0, carry) = Adc(d0, MODULUS_LIMBS_64[0] & borrow, 0);	332,643✔
458	(d1, carry) = Adc(d1, MODULUS_LIMBS_64[1] & borrow, carry);	332,643✔
459	(d2, carry) = Adc(d2, MODULUS_LIMBS_64[2] & borrow, carry);	332,643✔
460	(d3, _) = Adc(d3, MODULUS_LIMBS_64[3] & borrow, carry);	332,643✔
461
462	ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };	332,643✔
463	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];	332,643✔
464	}	332,643✔
465
466	public static Scalar operator +(in Scalar a, in Scalar b)
467	{	76,985✔
468	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	153,970✔
469	ulong d0, d1, d2, d3;
470	ulong carry;
471
472	(d0, carry) = Adc(self[0], rhs[0], 0);	76,985✔
473	(d1, carry) = Adc(self[1], rhs[1], carry);	76,985✔
474	(d2, carry) = Adc(self[2], rhs[2], carry);	76,985✔
475	(d3, _) = Adc(self[3], rhs[3], carry);	76,985✔
476
477	// Attempt to subtract the modulus, to ensure the value
478	// is smaller than the modulus.
479	ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };	76,985✔
480	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;	76,985✔
481	}	76,985✔
482
483	public static Scalar operator -(in Scalar a)
484	{	14✔
485	ReadOnlySpan<ulong> self = a.GetSpanU64();	14✔
486	ulong d0, d1, d2, d3;
487	ulong borrow;
488
489	// Subtract `self` from `MODULUS` to negate. Ignore the final
490	// borrow because it cannot underflow; self is guaranteed to
491	// be in the field.
492	(d0, borrow) = Sbb(MODULUS_LIMBS_64[0], self[0], 0);	14✔
493	(d1, borrow) = Sbb(MODULUS_LIMBS_64[1], self[1], borrow);	14✔
494	(d2, borrow) = Sbb(MODULUS_LIMBS_64[2], self[2], borrow);	14✔
495	(d3, _) = Sbb(MODULUS_LIMBS_64[3], self[3], borrow);	14✔
496
497	// `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
498	// zero if `self` was zero, and `u64::max_value()` if self was nonzero.
499	ulong mask = a.IsZero ? ulong.MinValue : ulong.MaxValue;	14✔
500
501	ReadOnlySpan<ulong> tmp = stackalloc[] { d0 & mask, d1 & mask, d2 & mask, d3 & mask };	14✔
502	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];	14✔
503	}	14✔
504
505	#region Instance math methods
506
UNCOV 507	public Scalar Negate() => -this;	×
508	public Scalar Multiply(in Scalar value) => this * value;	29,732✔
UNCOV 509	public Scalar Sum(in Scalar value) => this + value;	×
510	public Scalar Subtract(in Scalar value) => this - value;	×
511
512	#endregion
513	}

neo-project / neo / 11670022056

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous