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
18 package org.apache.commons.rng.core.source64;
19
20 import java.util.List;
21 import java.util.ArrayList;
22 import org.apache.commons.rng.core.util.NumberFactory;
23
24 /**
25 * Random number generator designed by Mark D. Overton.
26 *
27 * <p>It is one of the many generators described by the author in the following article series:</p>
28 * <ul>
29 * <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477">Part one</a></li>
30 * <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484">Part two</a></li>
31 * </ul>
32 *
33 * @since 1.0
34 */
35 public class TwoCmres extends LongProvider {
36 /** Error message. */
37 private static final String INTERNAL_ERROR_MSG = "Internal error: Please file a bug report";
38 /** A small positive integer. */
39 private static final byte SEED_GUARD = 9;
40 /** Factory of instances of this class. Singleton. */
41 private static final Cmres.Factory FACTORY = new Cmres.Factory();
42 /** First subcycle generator. */
43 private final Cmres x;
44 /** Second subcycle generator. */
45 private final Cmres y;
46 /** State of first subcycle generator. */
47 private long xx;
48 /** State of second subcycle generator. */
49 private long yy;
50
51 /**
52 * Creates a new instance.
53 *
54 * @param seed Initial seed.
55 * @param x First subcycle generator.
56 * @param y Second subcycle generator.
57 */
58 private TwoCmres(int seed,
59 Cmres x,
60 Cmres y) {
61 this.x = x;
62 this.y = y;
63 setSeedInternal(seed);
64 }
65
66 /**
67 * Creates a new instance.
68 *
69 * @param seed Seed.
70 */
71 public TwoCmres(Integer seed) {
72 this(seed, 0, 1);
73 }
74
75 /**
76 * Creates a new instance.
77 *
78 * @param seed Seed.
79 * @param i Table entry for first subcycle generator.
80 * @param j Table entry for second subcycle generator.
81 * @throws IllegalArgumentException if {@code i == j}.
82 * @throws IndexOutOfBoundsException if {@code i < 0} or
83 * {@code i >= numberOfSubcycleGenerators()}.
84 * @throws IndexOutOfBoundsException if {@code j < 0} or
85 * {@code j >= numberOfSubcycleGenerators()}.
86 */
87 public TwoCmres(Integer seed,
88 int i,
89 int j) {
90 this(seed, FACTORY.getIfDifferent(i, j), FACTORY.get(j));
91 }
92
93 /** {@inheritDoc} */
94 @Override
95 public long next() {
96 xx = x.transform(xx);
97 yy = y.transform(yy);
98
99 return xx + yy;
100 }
101
102 /** {@inheritDoc} */
103 @Override
104 public String toString() {
105 return super.toString() + " (" + x + " + " + y + ")";
106 }
107
108 /**
109 * Get the number of subcycle generators.
110 *
111 * @return the number of subcycle generators.
112 */
113 public static int numberOfSubcycleGenerators() {
114 return FACTORY.numberOfSubcycleGenerators();
115 }
116
117 /** {@inheritDoc} */
118 @Override
119 protected byte[] getStateInternal() {
120 return composeStateInternal(NumberFactory.makeByteArray(new long[] {xx, yy}),
121 super.getStateInternal());
122 }
123
124 /** {@inheritDoc} */
125 @Override
126 protected void setStateInternal(byte[] s) {
127 final byte[][] c = splitStateInternal(s, 16);
128
129 final long[] state = NumberFactory.makeLongArray(c[0]);
130 xx = state[0];
131 yy = state[1];
132
133 super.setStateInternal(c[1]);
134 }
135
136 /**
137 * @param seed Seed.
138 */
139 private void setSeedInternal(int seed) {
140 // The seeding procedure consists in going away from some
141 // point known to be in the cycle.
142 // The total number of calls to the "transform" method will
143 // not exceed about 130,000 (which is negligible as seeding
144 // will not occur more than once in normal usage).
145
146 // Make two positive 16-bits integers from the 32-bit seed.
147 // Add the small positive seed guard. The result will never be negative.
148 final int xMax = (seed & 0xffff) + (SEED_GUARD & 0xff);
149 final int yMax = (seed >>> 16) + (SEED_GUARD & 0xff);
150
151 xx = x.getStart();
152 for (int i = xMax; i > 0; i--) {
153 xx = x.transform(xx);
154 }
155
156 yy = y.getStart();
157 for (int i = yMax; i > 0; i--) {
158 yy = y.transform(yy);
159 }
160 }
161
162 /**
163 * Subcycle generator.
164 * Class is immutable.
165 */
166 static class Cmres {
167 /** Separator. */
168 private static final String SEP = ", ";
169 /** Hexadecimal format. */
170 private static final String HEX_FORMAT = "0x%016xL";
171 /** Cycle start. */
172 private final int start;
173 /** Multiplier. */
174 private final long multiply;
175 /** Rotation. */
176 private final int rotate;
177
178 /**
179 * @param multiply Multiplier.
180 * @param rotate Positive number. Must be in {@code [0, 64]}.
181 * @param start Cycle start.
182 */
183 Cmres(long multiply,
184 int rotate,
185 int start) {
186 this.multiply = multiply;
187 this.rotate = rotate;
188 this.start = start;
189 }
190
191 /** {@inheritDoc} */
192 @Override
193 public String toString() {
194 final String m = String.format((java.util.Locale) null, HEX_FORMAT, multiply);
195 return "Cmres: [" + m + SEP + rotate + SEP + start + "]";
196 }
197
198 /**
199 * @return the multiplier.
200 */
201 public long getMultiply() {
202 return multiply;
203 }
204
205 /**
206 * @return the cycle start.
207 */
208 public int getStart() {
209 return start;
210 }
211
212 /**
213 * @param state Current state.
214 * @return the new state.
215 */
216 long transform(long state) {
217 long s = state;
218 s *= multiply;
219 s = Long.rotateLeft(s, rotate);
220 s -= state;
221 return s;
222 }
223
224 /** Factory. */
225 static class Factory {
226 /** List of good "Cmres" subcycle generators. */
227 private static final List<Cmres> TABLE = new ArrayList<>();
228
229 //
230 // Populates the table.
231 // It lists parameters known to be good (provided in
232 // the article referred to above).
233 // To maintain compatibility, new entries must be added
234 // only at the end of the table.
235 //
236 static {
237 add(0xedce446814d3b3d9L, 33, 0x13b572e7);
238 add(0xc5b3cf786c806df7L, 33, 0x13c8e18a);
239 add(0xdd91bbb8ab9e0e65L, 31, 0x06dd03a6);
240 add(0x7b69342c0790221dL, 31, 0x1646bb8b);
241 add(0x0c72c0d18614c32bL, 33, 0x06014a3d);
242 add(0xd8d98c13bebe26c9L, 33, 0x014e8475);
243 add(0xcb039dc328bbc40fL, 31, 0x008684bd);
244 add(0x858c5ef3c021ed2fL, 32, 0x0dc8d622);
245 add(0x4c8be96bfc23b127L, 33, 0x0b6b20cc);
246 add(0x11eab77f808cf641L, 32, 0x06534421);
247 add(0xbc9bd78810fd28fdL, 31, 0x1d9ba40d);
248 add(0x0f1505c780688cb5L, 33, 0x0b7b7b67);
249 add(0xadc174babc2053afL, 31, 0x267f4197);
250 add(0x900b6b82b31686d9L, 31, 0x023c6985);
251 // Add new entries here.
252 }
253
254 /**
255 * @return the number of subcycle generators.
256 */
257 int numberOfSubcycleGenerators() {
258 return TABLE.size();
259 }
260
261 /**
262 * @param index Index into the list of available generators.
263 * @return the subcycle generator entry at index {@code index}.
264 */
265 Cmres get(int index) {
266 if (index < 0 ||
267 index >= TABLE.size()) {
268 throw new IndexOutOfBoundsException("Out of interval [0, " +
269 (TABLE.size() - 1) + "]");
270 }
271
272 return TABLE.get(index);
273 }
274
275 /**
276 * Get the generator at {@code index} if the {@code other} index is different.
277 *
278 * <p>This method exists to raise an exception before invocation of the
279 * private constructor; this mitigates Finalizer attacks
280 * (see SpotBugs CT_CONSTRUCTOR_THROW).
281 *
282 * @param index Index into the list of available generators.
283 * @param other Other index.
284 * @return the subcycle generator entry at index {@code index}.
285 */
286 Cmres getIfDifferent(int index, int other) {
287 if (index == other) {
288 throw new IllegalArgumentException("Subcycle generators must be different");
289 }
290 return get(index);
291 }
292
293 /**
294 * Adds an entry to the {@link Factory#TABLE}.
295 *
296 * @param multiply Multiplier.
297 * @param rotate Rotate.
298 * @param start Cycle start.
299 */
300 private static void add(long multiply,
301 int rotate,
302 int start) {
303 // Validity check: if there are duplicates, the class initialization
304 // will fail (and the JVM will report "NoClassDefFoundError").
305 checkUnique(TABLE, multiply);
306
307 TABLE.add(new Cmres(multiply, rotate, start));
308 }
309
310 /**
311 * Check the multiply parameter is unique (not contained in any entry in the provided
312 * table).
313 *
314 * @param table the table
315 * @param multiply the multiply parameter
316 */
317 static void checkUnique(List<Cmres> table, long multiply) {
318 for (final Cmres sg : table) {
319 if (multiply == sg.getMultiply()) {
320 throw new IllegalStateException(INTERNAL_ERROR_MSG);
321 }
322 }
323 }
324 }
325 }
326 }