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.core.source32;
18
19 import java.util.Arrays;
20 import org.apache.commons.rng.core.util.NumberFactory;
21
22 /**
23 * Port from Marsaglia's <a href="https://en.wikipedia.org/wiki/Multiply-with-carry">
24 * "Multiply-With-Carry" algorithm</a>.
25 *
26 * <p>
27 * Implementation is based on the (non-portable!) C code reproduced on
28 * <a href="http://school.anhb.uwa.edu.au/personalpages/kwessen/shared/Marsaglia03.html">
29 * that page</a>.
30 * </p>
31 *
32 * @see <a href="https://en.wikipedia.org/wiki/Multiply-with-carry">Multiply with carry (Wikipedia)</a>
33 * @since 1.0
34 */
35 public class MultiplyWithCarry256 extends IntProvider {
36 /** Length of the state array. */
37 private static final int Q_SIZE = 256;
38 /** Size of the seed. */
39 private static final int SEED_SIZE = Q_SIZE + 1;
40 /** Multiply. */
41 private static final long A = 809430660;
42 /** State. */
43 private final int[] state = new int[Q_SIZE];
44 /** Current index in "state" array. */
45 private int index;
46 /** Carry. */
47 private int carry;
48
49 /**
50 * Creates a new instance.
51 *
52 * @param seed Seed.
53 * If the length is larger than 257, only the first 257 elements will
54 * be used; if smaller, the remaining elements will be automatically
55 * set.
56 */
57 public MultiplyWithCarry256(int[] seed) {
58 setSeedInternal(seed);
59 }
60
61 /** {@inheritDoc} */
62 @Override
63 protected byte[] getStateInternal() {
64 final int[] s = Arrays.copyOf(state, SEED_SIZE + 1);
65 s[SEED_SIZE - 1] = carry;
66 s[SEED_SIZE] = index;
67
68 return composeStateInternal(NumberFactory.makeByteArray(s),
69 super.getStateInternal());
70 }
71
72 /** {@inheritDoc} */
73 @Override
74 protected void setStateInternal(byte[] s) {
75 final byte[][] c = splitStateInternal(s, (SEED_SIZE + 1) * 4);
76
77 final int[] tmp = NumberFactory.makeIntArray(c[0]);
78
79 System.arraycopy(tmp, 0, state, 0, Q_SIZE);
80 carry = tmp[SEED_SIZE - 1];
81 index = tmp[SEED_SIZE];
82
83 super.setStateInternal(c[1]);
84 }
85
86 /**
87 * Seeds the RNG.
88 *
89 * @param seed Seed.
90 */
91 private void setSeedInternal(int[] seed) {
92 // Reset the whole state of this RNG (i.e. "state" and "index").
93 // Filling procedure is not part of the reference code.
94 final int[] tmp = new int[SEED_SIZE];
95 fillState(tmp, seed);
96
97 // First element of the "seed" is the initial "carry".
98 final int c = tmp[0];
99 // Marsaglia's recommendation: 0 <= carry < A.
100 carry = (int) (Math.abs(c) % A);
101
102 // Initial state.
103 System.arraycopy(tmp, 1, state, 0, Q_SIZE);
104
105 // Initial index.
106 index = Q_SIZE;
107 }
108
109 /** {@inheritDoc} */
110 @Override
111 public int next() {
112 // Produce an index in the range 0-255
113 index &= 0xff;
114 final long t = A * (state[index] & 0xffffffffL) + carry;
115 carry = (int) (t >> 32);
116 return state[index++] = (int) t;
117 }
118 }