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 */
017package org.apache.commons.rng.core.source32;
018
019import java.util.Arrays;
020import org.apache.commons.rng.core.util.NumberFactory;
021
022/**
023 * Port from Marsaglia's <a href="https://en.wikipedia.org/wiki/Multiply-with-carry">
024 * "Multiply-With-Carry" algorithm</a>.
025 *
026 * <p>
027 * Implementation is based on the (non-portable!) C code reproduced on
028 * <a href="http://school.anhb.uwa.edu.au/personalpages/kwessen/shared/Marsaglia03.html">
029 * that page</a>.
030 * </p>
031 *
032 * @see <a href="https://en.wikipedia.org/wiki/Multiply-with-carry">Multiply with carry (Wikipedia)</a>
033 * @since 1.0
034 */
035public class MultiplyWithCarry256 extends IntProvider {
036    /** Length of the state array. */
037    private static final int Q_SIZE = 256;
038    /** Size of the seed. */
039    private static final int SEED_SIZE = Q_SIZE + 1;
040    /** Multiply. */
041    private static final long A = 809430660;
042    /** State. */
043    private final int[] state = new int[Q_SIZE];
044    /** Current index in "state" array. */
045    private int index;
046    /** Carry. */
047    private int carry;
048
049    /**
050     * Creates a new instance.
051     *
052     * @param seed Seed.
053     * If the length is larger than 257, only the first 257 elements will
054     * be used; if smaller, the remaining elements will be automatically
055     * set.
056     */
057    public MultiplyWithCarry256(int[] seed) {
058        setSeedInternal(seed);
059    }
060
061    /** {@inheritDoc} */
062    @Override
063    protected byte[] getStateInternal() {
064        final int[] s = Arrays.copyOf(state, SEED_SIZE + 1);
065        s[SEED_SIZE - 1] = carry;
066        s[SEED_SIZE] = index;
067
068        return NumberFactory.makeByteArray(s);
069    }
070
071    /** {@inheritDoc} */
072    @Override
073    protected void setStateInternal(byte[] s) {
074        checkStateSize(s, (SEED_SIZE + 1) * 4);
075
076        final int[] tmp = NumberFactory.makeIntArray(s);
077
078        System.arraycopy(tmp, 0, state, 0, Q_SIZE);
079        carry = tmp[SEED_SIZE - 1];
080        index = tmp[SEED_SIZE];
081    }
082
083    /**
084     * Seeds the RNG.
085     *
086     * @param seed Seed.
087     */
088    private void setSeedInternal(int[] seed) {
089        // Reset the whole state of this RNG (i.e. "state" and "index").
090        // Filling procedure is not part of the reference code.
091        final int[] tmp = new int[SEED_SIZE];
092        fillState(tmp, seed);
093
094        // First element of the "seed" is the initial "carry".
095        final int c = tmp[0];
096        // Marsaglia's recommendation: 0 <= carry < A.
097        carry = (int) ((c < 0 ? -c : c) % A);
098
099        // Initial state.
100        System.arraycopy(tmp, 1, state, 0, Q_SIZE);
101
102        // Initial index.
103        index = Q_SIZE;
104    }
105
106    /** {@inheritDoc} */
107    @Override
108    public int next() {
109        if (index == Q_SIZE) { // Whole state used up.
110            // Refill.
111            for (int i = 0; i < Q_SIZE; i++) {
112                final long t = A * (state[i] & 0xffffffffL) + carry;
113                carry = (int) (t >> 32);
114                state[i] = (int) t;
115            }
116
117            // Reset current index.
118            index = 0;
119        }
120
121        return state[index++];
122    }
123}