mt19937-period.rs

const P : usize = 19937;
const N : usize = 624;
const M : usize = 397;
const W : usize = 32;
const R : usize = 31;
const MATRIX_A : u32 = 0x9908b0df;
const LMASK : u32 = (1 << R) - 1;
const UMASK : u32 = LMASK ^ 0xffffffff;

struct State {
	vector : [u32; N],
	index : usize
}

impl State {
	fn new(vector: [u32; N]) -> State {
		return State {vector: vector, index: 0};
	}
	
	fn next(&mut self, a: u32) -> u32 {
		if self.index >= N {
			self.index = 0;
			for k in 0..N-M {
				self.vector[k] = self.vector[k+M] ^ State::mult_a((self.vector[k] & UMASK) | (self.vector[k+1] & LMASK), a);
			}
			for k in N-M..N-1 {
				self.vector[k] = self.vector[k+M-N] ^ State::mult_a((self.vector[k] & UMASK) | (self.vector[k+1] & LMASK), a);
			}
			self.vector[N-1] = self.vector[M-1] ^ State::mult_a((self.vector[N-1] & UMASK) | (self.vector[0] & LMASK), a);
		}
		let x = self.vector[self.index] & 1;
		self.index += 1;
		return x;
	}
	
	fn mult_a(v: u32, a: u32) -> u32 {
		let mag01 = [0, a];
		return (v >> 1) ^ mag01[(v & 1) as usize];
	}
}

fn phi_inverse(bits : [u32; P], a: u32) -> State {
	let mut x : [u32; P+1] = [0; P+1];
	for i in 0..P {
		x[i + 1] = bits[i];
	}
	for i in (N..P+1).rev() {
		let y = (x[i] ^ x[i-N+M] ^ ((x[i-N+1] & 1) * a)) << 1;
		x[i-N+1] = (x[i-N+1] & UMASK) | (y & LMASK) | (x[i-N+1] & 1);
		x[i-N] = (y & UMASK) | (x[i-N] & LMASK);
	}
	let mut vector : [u32; N] = [0; N];
	for i in 0..N {
		vector[i] = x[i];
	}
	return State::new(vector);
}

fn generate(state: &mut State, a: u32) -> [u32; P] {
	let mut bits : [u32; P] = [0; P];
	state.next(a);
	for i in 0..P {
		bits[i] = state.next(a);
		state.next(a);
	}
	return bits;
}

fn show(x: [u32; P]) -> String {
	let mut s = String::new();
	for i in 0..20 {
		s.push_str(&x[i].to_string()[..]);
	}
	return s;
}

fn equal(x: [u32; P], y: [u32; P]) -> bool {
	for i in 0..P {
		if x[i] != y[i] {
			return false;
		}
	}
	return true;
}

fn test(a: u32) -> bool {
	let mut initial : [u32; P] = [0; P];
	initial[1] = 1;
	let mut x = initial;
	for i in 0..P {
		let mut state = phi_inverse(x, a);
		x = generate(&mut state, a);
	}
	return equal(x, initial);
}

fn main() {
	println!("{}: {}", MATRIX_A, test(MATRIX_A));
}