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 composeStateInternal(NumberFactory.makeByteArray(s),
069                                    super.getStateInternal());
070    }
071
072    /** {@inheritDoc} */
073    @Override
074    protected void setStateInternal(byte[] s) {
075        final byte[][] c = splitStateInternal(s, (SEED_SIZE + 1) * 4);
076
077        final int[] tmp = NumberFactory.makeIntArray(c[0]);
078
079        System.arraycopy(tmp, 0, state, 0, Q_SIZE);
080        carry = tmp[SEED_SIZE - 1];
081        index = tmp[SEED_SIZE];
082
083        super.setStateInternal(c[1]);
084    }
085
086    /**
087     * Seeds the RNG.
088     *
089     * @param seed Seed.
090     */
091    private void setSeedInternal(int[] seed) {
092        // Reset the whole state of this RNG (i.e. "state" and "index").
093        // Filling procedure is not part of the reference code.
094        final int[] tmp = new int[SEED_SIZE];
095        fillState(tmp, seed);
096
097        // First element of the "seed" is the initial "carry".
098        final int c = tmp[0];
099        // 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}