11675783166

Committed 05 Nov 2024 01:25AM UTC coverage: 55.899% (+0.008%) from 55.891%

Build # 11675783166

Build Type

Pull #3566

github

Committed by

web-flow

Commit Message

Merge 2bbb8fe88 into a856982dd

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

Run Details

5790 of 8930 branches covered (64.84%)

Branch coverage included in aggregate %.

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

16 existing lines in 1 file now uncovered.

21747 of 40332 relevant lines covered (53.92%)

86367.52 hits per line

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

92.23

/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 Neo.Extensions;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
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()
    {
        return "0x" + ToArray().ToHexString(true);
    }

    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 Neo.Extensions;
13	using System.Diagnostics.CodeAnalysis;
14	using System.Runtime.CompilerServices;
15	using System.Runtime.InteropServices;
16	using System.Security.Cryptography;
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	return "0x" + ToArray().ToHexString(true);	3✔
123	}	3✔
124
125	public static bool operator ==(in Scalar a, in Scalar b)
126	{	51,097✔
127	return ConstantTimeEq(in a, in b);	51,097✔
128	}	51,097✔
129
130	public static bool operator !=(in Scalar a, in Scalar b)
131	{	101✔
132	return !(a == b);	101✔
133	}	101✔
134
135	public override bool Equals([NotNullWhen(true)] object? obj)
UNCOV 136	{	×
UNCOV 137	if (obj is not Scalar other) return false;	×
UNCOV 138	return this == other;	×
UNCOV 139	}	×
140
141	public bool Equals(Scalar other)
142	{	580✔
143	return this == other;	580✔
144	}	580✔
145
146	public override int GetHashCode()
UNCOV 147	{	×
UNCOV 148	return base.GetHashCode();	×
UNCOV 149	}	×
150
151	public Scalar Double()
152	{	1✔
153	return this + this;	1✔
154	}	1✔
155
156	public byte[] ToArray()
157	{	243✔
158	ReadOnlySpan<ulong> self = GetSpanU64();	243✔
159
160	// Turn into canonical form by computing
161	// (a.R) / R = a
162	Scalar result = MontgomeryReduce(self[0], self[1], self[2], self[3], 0, 0, 0, 0);	243✔
163	return result.GetSpan().ToArray();	243✔
164	}	243✔
165
166	public Scalar Square()
167	{	182,247✔
168	ReadOnlySpan<ulong> self = GetSpanU64();	182,247✔
169	ulong r0, r1, r2, r3, r4, r5, r6, r7;
170	ulong carry;
171
172	(r1, carry) = Mac(0, self[0], self[1], 0);	182,247✔
173	(r2, carry) = Mac(0, self[0], self[2], carry);	182,247✔
174	(r3, r4) = Mac(0, self[0], self[3], carry);	182,247✔
175
176	(r3, carry) = Mac(r3, self[1], self[2], 0);	182,247✔
177	(r4, r5) = Mac(r4, self[1], self[3], carry);	182,247✔
178
179	(r5, r6) = Mac(r5, self[2], self[3], 0);	182,247✔
180
181	r7 = r6 >> 63;	182,247✔
182	r6 = (r6 << 1) \| (r5 >> 63);	182,247✔
183	r5 = (r5 << 1) \| (r4 >> 63);	182,247✔
184	r4 = (r4 << 1) \| (r3 >> 63);	182,247✔
185	r3 = (r3 << 1) \| (r2 >> 63);	182,247✔
186	r2 = (r2 << 1) \| (r1 >> 63);	182,247✔
187	r1 <<= 1;	182,247✔
188
189	(r0, carry) = Mac(0, self[0], self[0], 0);	182,247✔
190	(r1, carry) = Adc(r1, carry, 0);	182,247✔
191	(r2, carry) = Mac(r2, self[1], self[1], carry);	182,247✔
192	(r3, carry) = Adc(r3, carry, 0);	182,247✔
193	(r4, carry) = Mac(r4, self[2], self[2], carry);	182,247✔
194	(r5, carry) = Adc(r5, carry, 0);	182,247✔
195	(r6, carry) = Mac(r6, self[3], self[3], carry);	182,247✔
196	(r7, _) = Adc(r7, carry, 0);	182,247✔
197
198	return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);	182,247✔
199	}	182,247✔
200
201	public Scalar Sqrt()
202	{	101✔
203	// Tonelli-Shank's algorithm for q mod 16 = 1
204	// https://eprint.iacr.org/2012/685.pdf (page 12, algorithm 5)
205
206	// w = self^((t - 1) // 2)
207	// = self^6104339283789297388802252303364915521546564123189034618274734669823
208	var w = this.PowVartime(new ulong[]	101✔
209	{	101✔
210	0x7fff_2dff_7fff_ffff,	101✔
211	0x04d0_ec02_a9de_d201,	101✔
212	0x94ce_bea4_199c_ec04,	101✔
213	0x0000_0000_39f6_d3a9	101✔
214	});	101✔
215
216	var v = S;	101✔
217	var x = this * w;	101✔
218	var b = x * w;	101✔
219
220	// Initialize z as the 2^S root of unity.
221	var z = ROOT_OF_UNITY;	101✔
222
223	for (uint max_v = S; max_v >= 1; max_v--)	6,666✔
224	{	3,232✔
225	uint k = 1;	3,232✔
226	var tmp = b.Square();	3,232✔
227	var j_less_than_v = true;	3,232✔
228
229	for (uint j = 2; j < max_v; j++)	100,394✔
230	{	46,965✔
231	var tmp_is_one = tmp == One;	46,965✔
232	var squared = ConditionalSelect(in tmp, in z, tmp_is_one).Square();	46,965✔
233	tmp = ConditionalSelect(in squared, in tmp, tmp_is_one);	46,965✔
234	var new_z = ConditionalSelect(in z, in squared, tmp_is_one);	46,965✔
235	j_less_than_v &= j != v;	46,965✔
236	k = ConditionalSelect(j, k, tmp_is_one);	46,965✔
237	z = ConditionalSelect(in z, in new_z, j_less_than_v);	46,965✔
238	}	46,965✔
239
240	var result = x * z;	3,232✔
241	x = ConditionalSelect(in result, in x, b == One);	3,232✔
242	z = z.Square();	3,232✔
243	b *= z;	3,232✔
244	v = k;	3,232✔
245	}	3,232✔
246
247	if (x * x != this) throw new ArithmeticException();	150✔
248	return x;	52✔
249	}	52✔
250
251	public Scalar Pow(ulong[] by)
252	{	100✔
253	if (by.Length != SizeL)	100!
UNCOV 254	throw new ArgumentException($"The length of the parameter `{nameof(by)}` must be {SizeL}.");	×
255
256	var res = One;	100✔
257	for (int j = by.Length - 1; j >= 0; j--)	1,000✔
258	{	400✔
259	for (int i = 63; i >= 0; i--)	52,000✔
260	{	25,600✔
261	res = res.Square();	25,600✔
262	var tmp = res;	25,600✔
263	tmp *= this;	25,600✔
264	res.ConditionalAssign(in tmp, ((by[j] >> i) & 1) == 1);	25,600✔
265	}	25,600✔
266	}	400✔
267	return res;	100✔
268	}	100✔
269
270	public Scalar Invert()
271	{	205✔
272	static void SquareAssignMulti(ref Scalar n, int num_times)
273	{	5,740✔
274	for (int i = 0; i < num_times; i++)	112,750✔
275	{	50,635✔
276	n = n.Square();	50,635✔
277	}	50,635✔
278	}	5,740✔
279
280	var t0 = Square();	205✔
281	var t1 = t0 * this;	205✔
282	var t16 = t0.Square();	205✔
283	var t6 = t16.Square();	205✔
284	var t5 = t6 * t0;	205✔
285	t0 = t6 * t16;	205✔
286	var t12 = t5 * t16;	205✔
287	var t2 = t6.Square();	205✔
288	var t7 = t5 * t6;	205✔
289	var t15 = t0 * t5;	205✔
290	var t17 = t12.Square();	205✔
291	t1 *= t17;	205✔
292	var t3 = t7 * t2;	205✔
293	var t8 = t1 * t17;	205✔
294	var t4 = t8 * t2;	205✔
295	var t9 = t8 * t7;	205✔
296	t7 = t4 * t5;	205✔
297	var t11 = t4 * t17;	205✔
298	t5 = t9 * t17;	205✔
299	var t14 = t7 * t15;	205✔
300	var t13 = t11 * t12;	205✔
301	t12 = t11 * t17;	205✔
302	t15 *= t12;	205✔
303	t16 *= t15;	205✔
304	t3 *= t16;	205✔
305	t17 *= t3;	205✔
306	t0 *= t17;	205✔
307	t6 *= t0;	205✔
308	t2 *= t6;	205✔
309	SquareAssignMulti(ref t0, 8);	205✔
310	t0 *= t17;	205✔
311	SquareAssignMulti(ref t0, 9);	205✔
312	t0 *= t16;	205✔
313	SquareAssignMulti(ref t0, 9);	205✔
314	t0 *= t15;	205✔
315	SquareAssignMulti(ref t0, 9);	205✔
316	t0 *= t15;	205✔
317	SquareAssignMulti(ref t0, 7);	205✔
318	t0 *= t14;	205✔
319	SquareAssignMulti(ref t0, 7);	205✔
320	t0 *= t13;	205✔
321	SquareAssignMulti(ref t0, 10);	205✔
322	t0 *= t12;	205✔
323	SquareAssignMulti(ref t0, 9);	205✔
324	t0 *= t11;	205✔
325	SquareAssignMulti(ref t0, 8);	205✔
326	t0 *= t8;	205✔
327	SquareAssignMulti(ref t0, 8);	205✔
328	t0 *= this;	205✔
329	SquareAssignMulti(ref t0, 14);	205✔
330	t0 *= t9;	205✔
331	SquareAssignMulti(ref t0, 10);	205✔
332	t0 *= t8;	205✔
333	SquareAssignMulti(ref t0, 15);	205✔
334	t0 *= t7;	205✔
335	SquareAssignMulti(ref t0, 10);	205✔
336	t0 *= t6;	205✔
337	SquareAssignMulti(ref t0, 8);	205✔
338	t0 *= t5;	205✔
339	SquareAssignMulti(ref t0, 16);	205✔
340	t0 *= t3;	205✔
341	SquareAssignMulti(ref t0, 8);	205✔
342	t0 *= t2;	205✔
343	SquareAssignMulti(ref t0, 7);	205✔
344	t0 *= t4;	205✔
345	SquareAssignMulti(ref t0, 9);	205✔
346	t0 *= t2;	205✔
347	SquareAssignMulti(ref t0, 8);	205✔
348	t0 *= t3;	205✔
349	SquareAssignMulti(ref t0, 8);	205✔
350	t0 *= t2;	205✔
351	SquareAssignMulti(ref t0, 8);	205✔
352	t0 *= t2;	205✔
353	SquareAssignMulti(ref t0, 8);	205✔
354	t0 *= t2;	205✔
355	SquareAssignMulti(ref t0, 8);	205✔
356	t0 *= t3;	205✔
357	SquareAssignMulti(ref t0, 8);	205✔
358	t0 *= t2;	205✔
359	SquareAssignMulti(ref t0, 8);	205✔
360	t0 *= t2;	205✔
361	SquareAssignMulti(ref t0, 5);	205✔
362	t0 *= t1;	205✔
363	SquareAssignMulti(ref t0, 5);	205✔
364	t0 *= t1;	205✔
365
366	if (this == Zero) throw new DivideByZeroException();	206✔
367	return t0;	204✔
368	}	204✔
369
370	private static Scalar MontgomeryReduce(ulong r0, ulong r1, ulong r2, ulong r3, ulong r4, ulong r5, ulong r6, ulong r7)
371	{	255,554✔
372	// The Montgomery reduction here is based on Algorithm 14.32 in
373	// Handbook of Applied Cryptography
374	// <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
375
376	ulong carry, carry2;
377
378	var k = unchecked(r0 * INV);	255,554✔
379	(_, carry) = Mac(r0, k, MODULUS_LIMBS_64[0], 0);	255,554✔
380	(r1, carry) = Mac(r1, k, MODULUS_LIMBS_64[1], carry);	255,554✔
381	(r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[2], carry);	255,554✔
382	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[3], carry);	255,554✔
383	(r4, carry2) = Adc(r4, 0, carry);	255,554✔
384
385	k = unchecked(r1 * INV);	255,554✔
386	(_, carry) = Mac(r1, k, MODULUS_LIMBS_64[0], 0);	255,554✔
387	(r2, carry) = Mac(r2, k, MODULUS_LIMBS_64[1], carry);	255,554✔
388	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[2], carry);	255,554✔
389	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[3], carry);	255,554✔
390	(r5, carry2) = Adc(r5, carry2, carry);	255,554✔
391
392	k = unchecked(r2 * INV);	255,554✔
393	(_, carry) = Mac(r2, k, MODULUS_LIMBS_64[0], 0);	255,554✔
394	(r3, carry) = Mac(r3, k, MODULUS_LIMBS_64[1], carry);	255,554✔
395	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[2], carry);	255,554✔
396	(r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[3], carry);	255,554✔
397	(r6, carry2) = Adc(r6, carry2, carry);	255,554✔
398
399	k = unchecked(r3 * INV);	255,554✔
400	(_, carry) = Mac(r3, k, MODULUS_LIMBS_64[0], 0);	255,554✔
401	(r4, carry) = Mac(r4, k, MODULUS_LIMBS_64[1], carry);	255,554✔
402	(r5, carry) = Mac(r5, k, MODULUS_LIMBS_64[2], carry);	255,554✔
403	(r6, carry) = Mac(r6, k, MODULUS_LIMBS_64[3], carry);	255,554✔
404	(r7, _) = Adc(r7, carry2, carry);	255,554✔
405
406	// Result may be within MODULUS of the correct value
407	ReadOnlySpan<ulong> tmp = stackalloc[] { r4, r5, r6, r7 };	255,554✔
408	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;	255,554✔
409	}	255,554✔
410
411	public static Scalar operator *(in Scalar a, in Scalar b)
412	{	73,064✔
413	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	146,128✔
414	ulong r0, r1, r2, r3, r4, r5, r6, r7;
415	ulong carry;
416
417	(r0, carry) = Mac(0, self[0], rhs[0], 0);	73,064✔
418	(r1, carry) = Mac(0, self[0], rhs[1], carry);	73,064✔
419	(r2, carry) = Mac(0, self[0], rhs[2], carry);	73,064✔
420	(r3, r4) = Mac(0, self[0], rhs[3], carry);	73,064✔
421
422	(r1, carry) = Mac(r1, self[1], rhs[0], 0);	73,064✔
423	(r2, carry) = Mac(r2, self[1], rhs[1], carry);	73,064✔
424	(r3, carry) = Mac(r3, self[1], rhs[2], carry);	73,064✔
425	(r4, r5) = Mac(r4, self[1], rhs[3], carry);	73,064✔
426
427	(r2, carry) = Mac(r2, self[2], rhs[0], 0);	73,064✔
428	(r3, carry) = Mac(r3, self[2], rhs[1], carry);	73,064✔
429	(r4, carry) = Mac(r4, self[2], rhs[2], carry);	73,064✔
430	(r5, r6) = Mac(r5, self[2], rhs[3], carry);	73,064✔
431
432	(r3, carry) = Mac(r3, self[3], rhs[0], 0);	73,064✔
433	(r4, carry) = Mac(r4, self[3], rhs[1], carry);	73,064✔
434	(r5, carry) = Mac(r5, self[3], rhs[2], carry);	73,064✔
435	(r6, r7) = Mac(r6, self[3], rhs[3], carry);	73,064✔
436
437	return MontgomeryReduce(r0, r1, r2, r3, r4, r5, r6, r7);	73,064✔
438	}	73,064✔
439
440	public static Scalar operator -(in Scalar a, in Scalar b)
441	{	332,643✔
442	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	665,286✔
443	ulong d0, d1, d2, d3;
444	ulong carry, borrow;
445
446	(d0, borrow) = Sbb(self[0], rhs[0], 0);	332,643✔
447	(d1, borrow) = Sbb(self[1], rhs[1], borrow);	332,643✔
448	(d2, borrow) = Sbb(self[2], rhs[2], borrow);	332,643✔
449	(d3, borrow) = Sbb(self[3], rhs[3], borrow);	332,643✔
450
451	borrow = borrow == 0 ? ulong.MinValue : ulong.MaxValue;	332,643✔
452	(d0, carry) = Adc(d0, MODULUS_LIMBS_64[0] & borrow, 0);	332,643✔
453	(d1, carry) = Adc(d1, MODULUS_LIMBS_64[1] & borrow, carry);	332,643✔
454	(d2, carry) = Adc(d2, MODULUS_LIMBS_64[2] & borrow, carry);	332,643✔
455	(d3, _) = Adc(d3, MODULUS_LIMBS_64[3] & borrow, carry);	332,643✔
456
457	ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };	332,643✔
458	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];	332,643✔
459	}	332,643✔
460
461	public static Scalar operator +(in Scalar a, in Scalar b)
462	{	76,985✔
463	ReadOnlySpan<ulong> self = a.GetSpanU64(), rhs = b.GetSpanU64();	153,970✔
464	ulong d0, d1, d2, d3;
465	ulong carry;
466
467	(d0, carry) = Adc(self[0], rhs[0], 0);	76,985✔
468	(d1, carry) = Adc(self[1], rhs[1], carry);	76,985✔
469	(d2, carry) = Adc(self[2], rhs[2], carry);	76,985✔
470	(d3, _) = Adc(self[3], rhs[3], carry);	76,985✔
471
472	// Attempt to subtract the modulus, to ensure the value
473	// is smaller than the modulus.
474	ReadOnlySpan<ulong> tmp = stackalloc[] { d0, d1, d2, d3 };	76,985✔
475	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0] - MODULUS;	76,985✔
476	}	76,985✔
477
478	public static Scalar operator -(in Scalar a)
479	{	14✔
480	ReadOnlySpan<ulong> self = a.GetSpanU64();	14✔
481	ulong d0, d1, d2, d3;
482	ulong borrow;
483
484	// Subtract `self` from `MODULUS` to negate. Ignore the final
485	// borrow because it cannot underflow; self is guaranteed to
486	// be in the field.
487	(d0, borrow) = Sbb(MODULUS_LIMBS_64[0], self[0], 0);	14✔
488	(d1, borrow) = Sbb(MODULUS_LIMBS_64[1], self[1], borrow);	14✔
489	(d2, borrow) = Sbb(MODULUS_LIMBS_64[2], self[2], borrow);	14✔
490	(d3, _) = Sbb(MODULUS_LIMBS_64[3], self[3], borrow);	14✔
491
492	// `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
493	// zero if `self` was zero, and `u64::max_value()` if self was nonzero.
494	ulong mask = a.IsZero ? ulong.MinValue : ulong.MaxValue;	14✔
495
496	ReadOnlySpan<ulong> tmp = stackalloc[] { d0 & mask, d1 & mask, d2 & mask, d3 & mask };	14✔
497	return MemoryMarshal.Cast<ulong, Scalar>(tmp)[0];	14✔
498	}	14✔
499
500	#region Instance math methods
501
UNCOV 502	public Scalar Negate() => -this;	×
503	public Scalar Multiply(in Scalar value) => this * value;	29,732✔
UNCOV 504	public Scalar Sum(in Scalar value) => this + value;	×
UNCOV 505	public Scalar Subtract(in Scalar value) => this - value;	×
506
507	#endregion
508	}

neo-project / neo / 11675783166

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