001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.rng.core.source64;
019
020import java.util.List;
021import java.util.ArrayList;
022import org.apache.commons.rng.core.util.NumberFactory;
023
024/**
025 * Random number generator designed by Mark D. Overton.
026 *
027 * <p>It is one of the many generators described by the author in the following article series:</p>
028 *  <ul>
029 *   <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477">Part one</a></li>
030 *   <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484">Part two</a></li>
031 *  </ul>
032 *
033 * @since 1.0
034 */
035public class TwoCmres extends LongProvider {
036    /** Error message. */
037    private static final String INTERNAL_ERROR_MSG = "Internal error: Please file a bug report";
038    /** A small positive integer. */
039    private static final byte SEED_GUARD = 9;
040    /** Factory of instances of this class. Singleton. */
041    private static final Cmres.Factory FACTORY = new Cmres.Factory();
042    /** First subcycle generator. */
043    private final Cmres x;
044    /** Second subcycle generator. */
045    private final Cmres y;
046    /** State of first subcycle generator. */
047    private long xx;
048    /** State of second subcycle generator. */
049    private long yy;
050
051    /**
052     * Creates a new instance.
053     *
054     * @param seed Initial seed.
055     * @param x First subcycle generator.
056     * @param y Second subcycle generator.
057     */
058    private TwoCmres(int seed,
059                     Cmres x,
060                     Cmres y) {
061        this.x = x;
062        this.y = y;
063        setSeedInternal(seed);
064    }
065
066    /**
067     * Creates a new instance.
068     *
069     * @param seed Seed.
070     */
071    public TwoCmres(Integer seed) {
072        this(seed, 0, 1);
073    }
074
075    /**
076     * Creates a new instance.
077     *
078     * @param seed Seed.
079     * @param i Table entry for first subcycle generator.
080     * @param j Table entry for second subcycle generator.
081     * @throws IllegalArgumentException if {@code i == j}.
082     * @throws IndexOutOfBoundsException if {@code i < 0} or
083     * {@code i >= numberOfSubcycleGenerators()}.
084     * @throws IndexOutOfBoundsException if {@code j < 0} or
085     * {@code j >= numberOfSubcycleGenerators()}.
086     */
087    public TwoCmres(Integer seed,
088                    int i,
089                    int j) {
090        this(seed, FACTORY.getIfDifferent(i, j), FACTORY.get(j));
091    }
092
093    /** {@inheritDoc} */
094    @Override
095    public long next() {
096        xx = x.transform(xx);
097        yy = y.transform(yy);
098
099        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}