From a016436e89721aac718581893bcf222b2ebeb0d2 Mon Sep 17 00:00:00 2001 From: Kevin Jones Date: Tue, 24 Jul 2018 22:55:58 -0400 Subject: [PATCH] Added GetInt32 to RandomNumberGenerator. (dotnet/corefx#31243) Fixes 30873. Commit migrated from https://github.com/dotnet/corefx/commit/928873f0027f3c4fbea94c501990a7037ad27066 --- ....Security.Cryptography.Algorithms.netcoreapp.cs | 2 + .../src/Resources/Strings.resx | 3 + .../Security/Cryptography/RandomNumberGenerator.cs | 59 ++++++- .../tests/RandomNumberGeneratorTests.netcoreapp.cs | 190 +++++++++++++++++++++ 4 files changed, 250 insertions(+), 4 deletions(-) diff --git a/src/libraries/System.Security.Cryptography.Algorithms/ref/System.Security.Cryptography.Algorithms.netcoreapp.cs b/src/libraries/System.Security.Cryptography.Algorithms/ref/System.Security.Cryptography.Algorithms.netcoreapp.cs index 0e30915..c476737 100644 --- a/src/libraries/System.Security.Cryptography.Algorithms/ref/System.Security.Cryptography.Algorithms.netcoreapp.cs +++ b/src/libraries/System.Security.Cryptography.Algorithms/ref/System.Security.Cryptography.Algorithms.netcoreapp.cs @@ -43,6 +43,8 @@ namespace System.Security.Cryptography public static void Fill(Span data) => throw null; public virtual void GetBytes(System.Span data) { } public virtual void GetNonZeroBytes(System.Span data) { } + public static int GetInt32(int fromInclusive, int toExclusive) { throw null; } + public static int GetInt32(int toExclusive) { throw null; } } public abstract partial class RSA : System.Security.Cryptography.AsymmetricAlgorithm { diff --git a/src/libraries/System.Security.Cryptography.Algorithms/src/Resources/Strings.resx b/src/libraries/System.Security.Cryptography.Algorithms/src/Resources/Strings.resx index 23bad46..cb57503 100644 --- a/src/libraries/System.Security.Cryptography.Algorithms/src/Resources/Strings.resx +++ b/src/libraries/System.Security.Cryptography.Algorithms/src/Resources/Strings.resx @@ -64,6 +64,9 @@ Positive number required. + + Range of random number does not contain at least one possibility. + Offset and length were out of bounds for the array or count is greater than the number of elements from index to the end of the source collection. diff --git a/src/libraries/System.Security.Cryptography.Algorithms/src/System/Security/Cryptography/RandomNumberGenerator.cs b/src/libraries/System.Security.Cryptography.Algorithms/src/System/Security/Cryptography/RandomNumberGenerator.cs index 8a3895f..e28f0dd 100644 --- a/src/libraries/System.Security.Cryptography.Algorithms/src/System/Security/Cryptography/RandomNumberGenerator.cs +++ b/src/libraries/System.Security.Cryptography.Algorithms/src/System/Security/Cryptography/RandomNumberGenerator.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Buffers; +using System.Runtime.InteropServices; namespace System.Security.Cryptography { @@ -96,12 +97,62 @@ namespace System.Security.Cryptography RandomNumberGeneratorImplementation.FillSpan(data); } + public static int GetInt32(int fromInclusive, int toExclusive) + { + if (fromInclusive >= toExclusive) + throw new ArgumentException(SR.Argument_InvalidRandomRange); + + // The total possible range is [0, 4,294,967,295). + // Subtract one to account for zero being an actual possibility. + uint range = (uint)toExclusive - (uint)fromInclusive - 1; + + // If there is only one possible choice, nothing random will actually happen, so return + // the only possibility. + if (range == 0) + { + return fromInclusive; + } + + // Create a mask for the bits that we care about for the range. The other bits will be + // masked away. + uint mask = range; + mask |= mask >> 1; + mask |= mask >> 2; + mask |= mask >> 4; + mask |= mask >> 8; + mask |= mask >> 16; + + Span resultSpan = stackalloc uint[1]; + uint result; + + do + { + RandomNumberGeneratorImplementation.FillSpan(MemoryMarshal.AsBytes(resultSpan)); + result = mask & resultSpan[0]; + } + while (result > range); + + return (int)result + fromInclusive; + } + + public static int GetInt32(int toExclusive) + { + if (toExclusive <= 0) + throw new ArgumentOutOfRangeException(nameof(toExclusive), SR.ArgumentOutOfRange_NeedPosNum); + + return GetInt32(0, toExclusive); + } + internal void VerifyGetBytes(byte[] data, int offset, int count) { - if (data == null) throw new ArgumentNullException(nameof(data)); - if (offset < 0) throw new ArgumentOutOfRangeException(nameof(offset), SR.ArgumentOutOfRange_NeedNonNegNum); - if (count < 0) throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NeedNonNegNum); - if (count > data.Length - offset) throw new ArgumentException(SR.Argument_InvalidOffLen); + if (data == null) + throw new ArgumentNullException(nameof(data)); + if (offset < 0) + throw new ArgumentOutOfRangeException(nameof(offset), SR.ArgumentOutOfRange_NeedNonNegNum); + if (count < 0) + throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NeedNonNegNum); + if (count > data.Length - offset) + throw new ArgumentException(SR.Argument_InvalidOffLen); } } } diff --git a/src/libraries/System.Security.Cryptography.Algorithms/tests/RandomNumberGeneratorTests.netcoreapp.cs b/src/libraries/System.Security.Cryptography.Algorithms/tests/RandomNumberGeneratorTests.netcoreapp.cs index 018e2b0..0345fba 100644 --- a/src/libraries/System.Security.Cryptography.Algorithms/tests/RandomNumberGeneratorTests.netcoreapp.cs +++ b/src/libraries/System.Security.Cryptography.Algorithms/tests/RandomNumberGeneratorTests.netcoreapp.cs @@ -2,6 +2,8 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. +using System.Buffers.Binary; +using System.Collections.Generic; using Xunit; namespace System.Security.Cryptography.RNG.Tests @@ -92,5 +94,193 @@ namespace System.Security.Cryptography.RNG.Tests RandomDataGenerator.VerifyRandomDistribution(random); } + + [Theory] + [InlineData(10, 10)] + [InlineData(10, 9)] + [InlineData(-10, -10)] + [InlineData(-10, -11)] + public static void GetInt32_LowerAndUpper_InvalidRange(int fromInclusive, int toExclusive) + { + Assert.Throws(() => RandomNumberGenerator.GetInt32(fromInclusive, toExclusive)); + } + + [Theory] + [InlineData(0)] + [InlineData(-10)] + public static void GetInt32_Upper_InvalidRange(int toExclusive) + { + Assert.Throws(() => RandomNumberGenerator.GetInt32(toExclusive)); + } + + [Theory] + [InlineData(1 << 1)] + [InlineData(1 << 4)] + [InlineData(1 << 16)] + [InlineData(1 << 24)] + public static void GetInt32_PowersOfTwo(int toExclusive) + { + for (int i = 0; i < 10; i++) + { + int result = RandomNumberGenerator.GetInt32(toExclusive); + Assert.InRange(result, 0, toExclusive - 1); + } + } + + [Theory] + [InlineData((1 << 1) + 1)] + [InlineData((1 << 4) + 1)] + [InlineData((1 << 16) + 1)] + [InlineData((1 << 24) + 1)] + public static void GetInt32_PowersOfTwoPlusOne(int toExclusive) + { + for (int i = 0; i < 10; i++) + { + int result = RandomNumberGenerator.GetInt32(toExclusive); + Assert.InRange(result, 0, toExclusive - 1); + } + } + + [Fact] + public static void GetInt32_FullRange() + { + int result = RandomNumberGenerator.GetInt32(int.MinValue, int.MaxValue); + Assert.NotEqual(int.MaxValue, result); + } + + [Fact] + public static void GetInt32_DoesNotProduceSameNumbers() + { + int result1 = RandomNumberGenerator.GetInt32(int.MinValue, int.MaxValue); + int result2 = RandomNumberGenerator.GetInt32(int.MinValue, int.MaxValue); + int result3 = RandomNumberGenerator.GetInt32(int.MinValue, int.MaxValue); + + // The changes of this happening are (2^32 - 1) * 3. + Assert.False(result1 == result2 && result2 == result3, "Generated the same number three times in a row."); + } + + [Fact] + public static void GetInt32_FullRange_DistributesBitsEvenly() + { + // This test should work since we are selecting random numbers that are a + // Power of two minus one so no bit should favored. + int numberToGenerate = 256; + byte[] bytes = new byte[numberToGenerate * 4]; + Span bytesSpan = bytes.AsSpan(); + for (int i = 0, j = 0; i < numberToGenerate; i++, j += 4) + { + int result = RandomNumberGenerator.GetInt32(int.MinValue, int.MaxValue); + Span slice = bytesSpan.Slice(j, 4); + BinaryPrimitives.WriteInt32LittleEndian(slice, result); + } + RandomDataGenerator.VerifyRandomDistribution(bytes); + } + + [Fact] + public static void GetInt32_CoinFlipLowByte() + { + int numberToGenerate = 1024; + Span generated = stackalloc int[numberToGenerate]; + + for (int i = 0; i < numberToGenerate; i++) + { + generated[i] = RandomNumberGenerator.GetInt32(0, 2); + } + VerifyAllInRange(generated, 0, 2); + VerifyDistribution(generated, 0.5); + } + + + [Fact] + public static void GetInt32_CoinFlipOverByteBoundary() + { + int numberToGenerate = 1024; + Span generated = stackalloc int[numberToGenerate]; + + for (int i = 0; i < numberToGenerate; i++) + { + generated[i] = RandomNumberGenerator.GetInt32(255, 257); + } + VerifyAllInRange(generated, 255, 257); + VerifyDistribution(generated, 0.5); + } + + [Fact] + public static void GetInt32_NegativeBounds1000d20() + { + int numberToGenerate = 1000; + Span generated = stackalloc int[numberToGenerate]; + + for (int i = 0; i < numberToGenerate; i++) + { + generated[i] = RandomNumberGenerator.GetInt32(-4000, -3979); + } + VerifyAllInRange(generated, -4000, -3979); + VerifyDistribution(generated, 0.05); + } + + [Fact] + public static void GetInt32_1000d6() + { + int numberToGenerate = 1000; + Span generated = stackalloc int[numberToGenerate]; + + for (int i = 0; i < numberToGenerate; i++) + { + generated[i] = RandomNumberGenerator.GetInt32(1, 7); + } + VerifyAllInRange(generated, 1, 7); + VerifyDistribution(generated, 0.16); + } + + [Theory] + [InlineData(int.MinValue, int.MinValue + 3)] + [InlineData(-257, -129)] + [InlineData(-100, 5)] + [InlineData(254, 512)] + [InlineData(-1_073_741_909, - 1_073_741_825)] + [InlineData(65_534, 65_539)] + [InlineData(16_777_214, 16_777_217)] + public static void GetInt32_MaskRangeCorrect(int fromInclusive, int toExclusive) + { + int numberToGenerate = 1000; + Span generated = stackalloc int[numberToGenerate]; + + for (int i = 0; i < numberToGenerate; i++) + { + generated[i] = RandomNumberGenerator.GetInt32(fromInclusive, toExclusive); + } + + double expectedDistribution = 1d / (toExclusive - fromInclusive); + VerifyAllInRange(generated, fromInclusive, toExclusive); + VerifyDistribution(generated, expectedDistribution); + } + + private static void VerifyAllInRange(ReadOnlySpan numbers, int fromInclusive, int toExclusive) + { + for (int i = 0; i < numbers.Length; i++) + { + Assert.InRange(numbers[i], fromInclusive, toExclusive - 1); + } + } + + private static void VerifyDistribution(ReadOnlySpan numbers, double expected) + { + var observedNumbers = new Dictionary(numbers.Length); + for (int i = 0; i < numbers.Length; i++) + { + int number = numbers[i]; + if (!observedNumbers.TryAdd(number, 1)) + { + observedNumbers[number]++; + } + } + const double tolerance = 0.07; + foreach ((_, int occurences) in observedNumbers) + { + double percentage = occurences / (double)numbers.Length; + Assert.True(Math.Abs(expected - percentage) < tolerance, "Occurred number of times within threshold."); + } + } } } -- 2.7.4