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}