View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.rng.simple.internal;
18  
19  import java.util.Map;
20  import java.util.HashMap;
21  import org.junit.Assert;
22  import org.junit.Test;
23  import org.apache.commons.rng.UniformRandomProvider;
24  import org.apache.commons.rng.core.source32.IntProvider;
25  import org.apache.commons.rng.core.source64.RandomLongSource;
26  import org.apache.commons.rng.core.util.NumberFactory;
27  
28  /**
29   * Tests for {@link SeedFactory}.
30   */
31  public class SeedFactoryTest {
32      @Test
33      public void testCreateLong() {
34          final Map<Long, Integer> values = new HashMap<Long, Integer>();
35  
36          final int n = 100000;
37          for (int i = 0; i < n; i++) {
38              final long v = SeedFactory.createLong();
39  
40              Integer count = values.get(v);
41              if (count == null) {
42                  count = 0;
43              }
44              values.put(v, count + 1);
45          }
46  
47          // Check that all seeds are different.
48          assertDifferentValues(values);
49      }
50  
51      @Test
52      public void testCreateLongArray() {
53          final Map<Long, Integer> values = new HashMap<Long, Integer>();
54  
55          final int n = 100000;
56          final long[] array = SeedFactory.createLongArray(n);
57          Assert.assertEquals(n, array.length);
58  
59          for (long v : array) {
60              Integer count = values.get(v);
61              if (count == null) {
62                  count = 0;
63              }
64              values.put(v, count + 1);
65          }
66  
67          // Check that all seeds are different.
68          assertDifferentValues(values);
69      }
70  
71      @Test
72      public void testCreateIntArray() {
73          final Map<Long, Integer> values = new HashMap<Long, Integer>();
74  
75          for (int i = 0; i < 50000; i++) {
76              final int[] a = SeedFactory.createIntArray(2);
77              final long v = NumberFactory.makeLong(a[0], a[1]);
78              Integer count = values.get(v);
79              if (count == null) {
80                  count = 0;
81              }
82              values.put(v, count + 1);
83          }
84  
85          // Check that all pairs in are different.
86          assertDifferentValues(values);
87      }
88  
89      /**
90       * Asserts that all the keys in given {@code map} have their
91       * value equal to 1.
92       *
93       * @param map Map to counts.
94       */
95      private static <T> void assertDifferentValues(Map<T, Integer> map) {
96          final StringBuilder sb = new StringBuilder();
97  
98          int duplicates = 0;
99          for (Map.Entry<T, Integer> entry : map.entrySet()) {
100             final int count = entry.getValue();
101             if (count <= 0) {
102                 throw new IllegalStateException();
103             }
104 
105             if (count > 1) {
106                 duplicates += count - 1;
107                 sb.append(entry.getKey() + ": " + count + "\n");
108             }
109         }
110 
111         if (duplicates > 0) {
112             Assert.fail(duplicates + " duplicates\n" + sb);
113         }
114     }
115 
116     @Test
117     public void testCreateIntArrayWithCompleteBlockSize() {
118         // Block size is 8 for int
119         assertCreateIntArray(8);
120     }
121 
122     @Test
123     public void testCreateIntArrayWithIncompleteBlockSize() {
124         // Block size is 8 for int
125         assertCreateIntArray(8 + 1);
126     }
127 
128     /**
129      * Checks that the int array values can be placed into 2 bins with
130      * approximately equal number of counts.
131      * The test uses the expectation from a fixed-step "random walk".
132      *
133      * @param n The size of the array.
134      */
135     private static void assertCreateIntArray(int n) {
136         final int[] array = SeedFactory.createIntArray(n);
137         Assert.assertEquals("Incorrect array length", n, array.length);
138         // The bit count should be 50%.
139         int bitCount = 0;
140         for (final int i : array) {
141             bitCount += Integer.bitCount(i);
142         }
143         final int numberOfBits = n * Integer.SIZE;
144         assertMonobit(bitCount, numberOfBits);
145     }
146 
147     @Test
148     public void testCreateLongArrayWithCompleteBlockSize() {
149         // Block size is 4 for long
150         assertCreateLongArray(4);
151     }
152 
153     @Test
154     public void testCreateLongArrayWithIncompleteBlockSize() {
155         // Block size is 4 for long
156         assertCreateLongArray(4 + 1);
157     }
158 
159     /**
160      * Checks that the long array values can be placed into 2 bins with
161      * approximately equal number of counts.
162      * The test uses the expectation from a fixed-step "random walk".
163      *
164      * @param n The size of the array.
165      */
166     private static void assertCreateLongArray(int n) {
167         final long[] array = SeedFactory.createLongArray(n);
168         Assert.assertEquals("Incorrect array length", n, array.length);
169         // The bit count should be 50%.
170         int bitCount = 0;
171         for (final long i : array) {
172             bitCount += Long.bitCount(i);
173         }
174         final int numberOfBits = n * Long.SIZE;
175         assertMonobit(bitCount, numberOfBits);
176     }
177 
178     /**
179      * Assert that the number of 1 bits is approximately 50%. This is based upon a
180      * fixed-step "random walk" of +1/-1 from zero.
181      *
182      * <p>The test is equivalent to the NIST Monobit test with a fixed p-value of 0.0001.
183      * The number of bits is recommended to be above 100.</p>
184      *
185      * @see <A
186      * href="https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final">Bassham, et
187      * al (2010) NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom
188      * Number Generators for Cryptographic Applications. Section 2.1.</a>
189      *
190      * @param bitCount The bit count.
191      * @param numberOfBits Number of bits.
192      */
193     private static void assertMonobit(int bitCount, int numberOfBits) {
194         // Convert the bit count into a number of +1/-1 steps.
195         final double sum = 2.0 * bitCount - numberOfBits;
196         // The reference distribution is Normal with a standard deviation of sqrt(n).
197         // Check the absolute position is not too far from the mean of 0 with a fixed
198         // p-value of 0.0001 taken from a 2-tailed Normal distribution. Computation of
199         // the p-value requires the complimentary error function.
200         // The p-value is set to be equal to a 0.01 with 1 allowed re-run.
201         // (Re-runs are not configured for this test.)
202         final double absSum = Math.abs(sum);
203         final double max = Math.sqrt(numberOfBits) * 3.891;
204         Assert.assertTrue("Walked too far astray: " + absSum +
205                           " > " + max +
206                           " (test will fail randomly about 1 in 10,000 times)",
207                           absSum <= max);
208     }
209 
210     @Test
211     public void testCreateByteArrayWithSizeZero() {
212         assertCreateByteArray(new byte[0]);
213     }
214 
215     @Test
216     public void testCreateByteArrayIgnoresNonZeroPositions() {
217         final byte position = 123;
218         int n = 3;
219         for (int i = 0; i < n; i++) {
220             final byte[] expected = new byte[n];
221             expected[i] = position;
222             assertCreateByteArray(expected);
223         }
224     }
225 
226     /**
227      * Assert that the SeedFactory uses the bytes exactly as generated by the
228      * {@link UniformRandomProvider#nextBytes(byte[])} method (assuming they are not all zero).
229      *
230      * @param expected the expected
231      */
232     private static void assertCreateByteArray(final byte[] expected) {
233         final UniformRandomProvider rng = new IntProvider() {
234             @Override
235             public int next() {
236                 Assert.fail("This method should not be used");
237                 return 0;
238             }
239 
240             @Override
241             public void nextBytes(byte[] bytes) {
242                 System.arraycopy(expected, 0, bytes, 0, Math.min(expected.length, bytes.length));
243             }
244         };
245 
246         final byte[] seed = SeedFactory.createByteArray(rng, expected.length);
247         Assert.assertArrayEquals(expected, seed);
248     }
249 
250     @Test
251     public void testCreateByteArrayWithAllZeroBytesUpdatesPosition0() {
252         final UniformRandomProvider rng = new IntProvider() {
253             @Override
254             public int next() {
255                 // Deliberately produce zero
256                 return 0;
257             }
258         };
259         // Test the method only replaces position 0
260         final byte[] seed = SeedFactory.createByteArray(rng, 4);
261         Assert.assertNotEquals("Zero at position 0 should be modified", 0, seed[0]);
262         for (int i = 1; i < seed.length; i++) {
263             Assert.assertEquals("Position above 0 should be unmodified", 0, seed[i]);
264         }
265     }
266 
267     @Test
268     public void testEnsureNonZeroIntArrayIgnoresEmptySeed() {
269         final int[] seed = new int[0];
270         SeedFactory.ensureNonZero(seed);
271         // Note: Nothing to assert.
272         // This tests an ArrayIndexOutOfBoundsException does not occur.
273     }
274 
275     @Test
276     public void testEnsureNonZeroIntArrayIgnoresNonZeroPosition0() {
277         final int position0 = 123;
278         final int[] seed = new int[] {position0, 0, 0, 0};
279         final int[] before = seed.clone();
280         SeedFactory.ensureNonZero(seed);
281         Assert.assertEquals("Non-zero at position 0 should be unmodified", position0, seed[0]);
282         for (int i = 1; i < seed.length; i++) {
283             Assert.assertEquals("Position above 0 should be unmodified", before[i], seed[i]);
284         }
285     }
286 
287     @Test
288     public void testEnsureNonZeroIntArrayUpdatesZeroPosition0() {
289         // Test the method replaces position 0 even if the rest of the array is non-zero
290         final int[] seed = new int[] {0, 123, 456, 789};
291         final int[] before = seed.clone();
292         SeedFactory.ensureNonZero(seed);
293         Assert.assertNotEquals("Zero at position 0 should be modified", 0, seed[0]);
294         for (int i = 1; i < seed.length; i++) {
295             Assert.assertEquals("Position above 0 should be unmodified", before[i], seed[i]);
296         }
297     }
298 
299     @Test
300     public void testEnsureNonZeroLongArrayIgnoresEmptySeed() {
301         final long[] seed = new long[0];
302         SeedFactory.ensureNonZero(seed);
303         // Note: Nothing to assert.
304         // This tests an ArrayIndexOutOfBoundsException does not occur.
305     }
306 
307     @Test
308     public void testEnsureNonZeroLongArrayIgnoresNonZeroPosition0() {
309         final long position0 = 123;
310         final long[] seed = new long[] {position0, 0, 0, 0};
311         final long[] before = seed.clone();
312         SeedFactory.ensureNonZero(seed);
313         Assert.assertEquals("Non-zero at position 0 should be unmodified", position0, seed[0]);
314         for (int i = 1; i < seed.length; i++) {
315             Assert.assertEquals("Position above 0 should be unmodified", before[i], seed[i]);
316         }
317     }
318 
319     @Test
320     public void testEnsureNonZeroLongArrayUpdatesZeroPosition0() {
321         // Test the method replaces position 0 even if the rest of the array is non-zero
322         final long[] seed = new long[] {0, 123, 456, 789};
323         final long[] before = seed.clone();
324         SeedFactory.ensureNonZero(seed);
325         Assert.assertNotEquals("Zero at position 0 should be modified", 0, seed[0]);
326         for (int i = 1; i < seed.length; i++) {
327             Assert.assertEquals("Position above 0 should be unmodified", before[i], seed[i]);
328         }
329     }
330 
331     @Test
332     public void testEnsureNonZeroValue() {
333         final long expected = 345;
334         RandomLongSource source = new RandomLongSource() {
335             @Override
336             public long next() {
337                 return expected;
338             }
339         };
340         Assert.assertEquals("Zero should be replaced using the random source",
341                 expected, SeedFactory.ensureNonZero(source, 0));
342         for (final long nonZero : new long[] {Long.MIN_VALUE, -1, 1, 9876654321L, Long.MAX_VALUE}) {
343             Assert.assertEquals("Non-zero should be unmodified",
344                     nonZero, SeedFactory.ensureNonZero(source, nonZero));
345         }
346     }
347 }