pcg_random/

output.rs

pub trait Output<S, O> {
	fn output(s: S) -> O;
}

/// high xorshift, followed by a random shift
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct XshRs;

impl Output<u16, u8> for XshRs {
	#[inline]
	fn output(s: u16) -> u8 {
		let xsh = s ^ (s >> 7);
		(xsh >> (3 + (s >> 14))) as u8
	}
}

impl Output<u32, u16> for XshRs {
	#[inline]
	fn output(s: u32) -> u16 {
		let xsh = s ^ (s >> 11);
		(xsh >> (11 + (s >> 30))) as u16
	}
}

impl Output<u64, u32> for XshRs {
	#[inline]
	fn output(s: u64) -> u32 {
		let xsh = s ^ (s >> 22);
		(xsh >> (22 + (s >> 61))) as u32
	}
}

impl Output<u128, u64> for XshRs {
	#[inline]
	fn output(s: u128) -> u64 {
		let xsh = s ^ (s >> 43);
		(xsh >> (45 + (s >> 124))) as u64
	}
}

/// high xorshift, followed by a random rotate
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct XshRr;

impl Output<u16, u8> for XshRr {
	#[inline]
	fn output(s: u16) -> u8 {
		let xsh = ((s ^ (s >> 5)) >> 5) as u8;
		xsh.rotate_right((s >> 13).into())
	}
}

impl Output<u32, u16> for XshRr {
	#[inline]
	fn output(s: u32) -> u16 {
		let xsh = ((s ^ (s >> 10)) >> 12) as u16;
		xsh.rotate_right(s >> 28)
	}
}

impl Output<u64, u32> for XshRr {
	#[inline]
	fn output(s: u64) -> u32 {
		let xsh = ((s ^ (s >> 18)) >> 27) as u32;
		xsh.rotate_right((s >> 59) as u32)
	}
}

impl Output<u128, u64> for XshRr {
	#[inline]
	fn output(s: u128) -> u64 {
		let xsh = ((s ^ (s >> 35)) >> 58) as u64;
		xsh.rotate_right((s >> 122) as u32)
	}
}

/// random xorshift, mcg multiply, fixed xorshift
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct RxsMXs;

impl Output<u8, u8> for RxsMXs {
	#[inline]
	fn output(s: u8) -> u8 {
		let shift = 2 + (s >> 6);
		let rxs = s ^ (s >> shift);
		let m = rxs.wrapping_mul(0xd9);
		m ^ (m >> 6)
	}
}

impl Output<u16, u16> for RxsMXs {
	#[inline]
	fn output(s: u16) -> u16 {
		let shift = 3 + (s >> 13);
		let rxs = s ^ (s >> shift);
		let m = rxs.wrapping_mul(0xf2d9);
		m ^ (m >> 11)
	}
}

impl Output<u32, u32> for RxsMXs {
	#[inline]
	fn output(s: u32) -> u32 {
		let shift = 4 + (s >> 28);
		let rxs = s ^ (s >> shift);
		let m = rxs.wrapping_mul(0x108ef2d9);
		m ^ (m >> 22)
	}
}

impl Output<u64, u64> for RxsMXs {
	#[inline]
	fn output(s: u64) -> u64 {
		let shift = 5 + (s >> 59);
		let rxs = s ^ (s >> shift);
		let m = rxs.wrapping_mul(0xaef17502108ef2d9);
		m ^ (m >> 43)
	}
}

impl Output<u128, u128> for RxsMXs {
	#[inline]
	fn output(s: u128) -> u128 {
		let shift = 6 + (s >> 122);
		let rxs = s ^ (s >> shift);
		let m = rxs.wrapping_mul(0xf69019274d7f699caef17502108ef2d9);
		m ^ (m >> 86)
	}
}

/// double xorshift multiply
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Dxsm;

impl Output<u16, u8> for Dxsm {
	#[inline]
	fn output(s: u16) -> u8 {
		let mut h = (s >> 8) as u8;
		h ^= h >> 4;
		h = h.wrapping_mul(0x1d);
		h ^= h >> 6;
		h.wrapping_mul(s as u8 | 1)
	}
}

impl Output<u32, u16> for Dxsm {
	#[inline]
	fn output(s: u32) -> u16 {
		let mut h = (s >> 16) as u16;
		h ^= h >> 8;
		h = h.wrapping_mul(0x77b5);
		h ^= h >> 12;
		h.wrapping_mul(s as u16 | 1)
	}
}

impl Output<u64, u32> for Dxsm {
	#[inline]
	fn output(s: u64) -> u32 {
		let mut h = (s >> 32) as u32;
		h ^= h >> 16;
		h = h.wrapping_mul(0x4c957f2d);
		h ^= h >> 24;
		h.wrapping_mul(s as u32 | 1)
	}
}

impl Output<u128, u64> for Dxsm {
	#[inline]
	fn output(s: u128) -> u64 {
		let mut h = (s >> 64) as u64;
		h ^= h >> 32;
		h = h.wrapping_mul(0xda942042e4dd58b5);
		h ^= h >> 48;
		h.wrapping_mul(s as u64 | 1)
	}
}

/// fixed xorshift (to low bits), random rotate
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct XslRr;

impl Output<u64, u32> for XslRr {
	#[inline]
	fn output(s: u64) -> u32 {
		let xsl = s ^ (s >> 32);
		(xsl as u32).rotate_right((s >> 59) as u32)
	}
}

impl Output<u128, u64> for XslRr {
	#[inline]
	fn output(s: u128) -> u64 {
		let xsl = s ^ (s >> 64);
		(xsl as u64).rotate_right((s >> 122) as u32)
	}
}

/// fixed xorshift (to low bits), random rotate (both parts)
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct XslRrRr;

impl Output<u64, u64> for XslRrRr {
	#[inline]
	fn output(s: u64) -> u64 {
		let xsl = s ^ (s >> 32);
		let l = (xsl as u32).rotate_right((s >> 59) as u32);
		let h = ((xsl >> 32) as u32).rotate_right(l & 0b11111);
		u64::from(l) | (u64::from(h) << 32)
	}
}

impl Output<u128, u128> for XslRrRr {
	#[inline]
	fn output(s: u128) -> u128 {
		let xsl = s ^ (s >> 64);
		let l = (xsl as u64).rotate_right((s >> 122) as u32);
		let h = ((xsl >> 64) as u64).rotate_right((l & 0b111111) as u32);
		u128::from(l) | (u128::from(h) << 64)
	}
}

#[cfg(test)]
mod tests {
	use crate::DefaultCheapLcgParameters;

	#[test]
	#[ignore]
	fn xsh_rs() {
		const NAME: &str = "XshRs";

		#[allow(clippy::cast_possible_wrap, clippy::int_plus_one)]
		fn print(bits: u32, x_bits: u32) {
			let spare = bits - x_bits;

			let op = if spare as i32 - 5 >= 64 {
				5
			} else if spare as i32 - 4 >= 32 {
				4
			} else if spare as i32 - 3 >= 16 {
				3
			} else if spare as i32 - 2 >= 4 {
				2
			} else if spare as i32 - 1 >= 1 {
				1
			} else {
				0
			};

			let mask = (1 << op) - 1;
			let max_rand_shift = mask;
			let top_spare = op;
			let bottom_spare = spare - top_spare;
			let x_shift = top_spare + (x_bits + max_rand_shift) / 2;

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let xsh = s ^ (s >> {x_shift});");
			println!(
				"		(xsh >> ({} + (s >> {}))) as u{x_bits}",
				bottom_spare - max_rand_shift,
				bits - op
			);
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// high xorshift, followed by a random shift");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(16, 8);
		print(32, 16);
		print(64, 32);
		print(128, 64);
	}

	#[test]
	#[ignore]
	fn xsh_rr() {
		const NAME: &str = "XshRr";

		fn print(bits: u32, x_bits: u32) {
			let spare = bits - x_bits;

			let wanted_op = if x_bits >= 128 {
				7
			} else if x_bits >= 64 {
				6
			} else if x_bits >= 32 {
				5
			} else if x_bits >= 16 {
				4
			} else {
				3
			};

			let op = if spare >= wanted_op { wanted_op } else { spare };
			let amplifier = wanted_op - op;
			assert!(amplifier == 0);
			let top_spare = op;
			let bottom_spare = spare - top_spare;
			let x_shift = (top_spare + x_bits) / 2;

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let xsh = ((s ^ (s >> {x_shift})) >> {bottom_spare}) as u{x_bits};");
			println!("		xsh.rotate_right((s >> {}) as u32)", bits - op);
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// high xorshift, followed by a random shift");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(16, 8);
		print(32, 16);
		print(64, 32);
		print(128, 64);
	}

	fn multiplier(bits: u32) -> String {
		const M: u128 = 0xf69019274d7f699caef17502108ef2d9;

		match bits {
			8 => format!("0x{:02x}", M as u8),
			16 => format!("0x{:04x}", M as u16),
			32 => format!("0x{:08x}", M as u32),
			64 => format!("0x{:016x}", M as u64),
			128 => format!("0x{M:032x}"),
			_ => panic!()
		}
	}

	#[test]
	#[ignore]
	fn rxs_m_xs() {
		const NAME: &str = "RxsMXs";

		fn print(bits: u32, x_bits: u32) {
			let op = if x_bits >= 128 {
				6
			} else if x_bits >= 64 {
				5
			} else if x_bits >= 32 {
				4
			} else if x_bits >= 16 {
				3
			} else {
				2
			};

			let shift = bits - x_bits;
			assert!(shift == 0);

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let shift = {} + (s >> {});", op, bits - op);
			println!("		let rxs = s ^ (s >> shift);");
			println!("		let m = rxs.wrapping_mul({});", multiplier(bits));
			println!("		m ^ (m >> {})", (x_bits * 2).div_ceil(3));
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// random xorshift, mcg multiply, fixed xorshift");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(8, 8);
		print(16, 16);
		print(32, 32);
		print(64, 64);
		print(128, 128);
	}

	#[test]
	#[ignore]
	fn dxsm() {
		const NAME: &str = "Dxsm";

		fn print(bits: u32, x_bits: u32) {
			assert!(x_bits == bits / 2);

			let multiplier = match bits {
				16 => format!("0x{:02x}", DefaultCheapLcgParameters::<u16>::multiplier() as u8),
				32 => format!("0x{:04x}", DefaultCheapLcgParameters::<u32>::multiplier() as u16),
				64 => {
					format!("0x{:08x}", DefaultCheapLcgParameters::<u64>::multiplier() as u32)
				}
				128 => {
					format!("0x{:016x}", DefaultCheapLcgParameters::<u128>::multiplier() as u64)
				}
				_ => panic!()
			};

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let mut h = (s >> {}) as u{x_bits};", x_bits);
			println!("		h ^= h >> {};", x_bits / 2);
			println!("		h = h.wrapping_mul({multiplier});");
			println!("		h ^= h >> {};", (x_bits / 4) * 3);
			println!("		h.wrapping_mul(s as u{x_bits} | 1)");
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// double xorshift multiply");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(16, 8);
		print(32, 16);
		print(64, 32);
		print(128, 64);
	}

	#[test]
	#[ignore]
	fn xsl_rr() {
		const NAME: &str = "XslRr";

		fn print(bits: u32, x_bits: u32) {
			let spare = bits - x_bits;

			let wanted_op = if x_bits >= 128 {
				7
			} else if x_bits >= 64 {
				6
			} else if x_bits >= 32 {
				5
			} else if x_bits >= 16 {
				4
			} else {
				3
			};

			let op = if spare >= wanted_op { wanted_op } else { spare };
			let amplifier = wanted_op - op;
			assert!(amplifier == 0);
			let top_spare = spare;
			let bottom_spare = spare - top_spare;
			assert!(bottom_spare == 0);
			let x_shift = (top_spare + x_bits) / 2;

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let xsl = s ^ (s >> {x_shift});");
			println!("		(xsl as u{x_bits}).rotate_right((s >> {}) as u32)", bits - op);
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// fixed xorshift (to low bits), random rotate");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(64, 32);
		print(128, 64);
	}

	#[test]
	#[ignore]
	fn xsl_rr_rr() {
		const NAME: &str = "XslRrRr";

		fn print(bits: u32, x_bits: u32) {
			assert!(bits == x_bits);
			let spare = bits - bits / 2;

			let wanted_op = if bits / 2 >= 128 {
				7
			} else if bits / 2 >= 64 {
				6
			} else if bits / 2 >= 32 {
				5
			} else if bits / 2 >= 16 {
				4
			} else {
				3
			};

			let op = if spare >= wanted_op { wanted_op } else { spare };
			let amplifier = wanted_op - op;
			assert!(amplifier == 0);
			let top_spare = spare;
			let x_shift = (top_spare + bits / 2) / 2;

			println!("impl Output<u{bits}, u{x_bits}> for {NAME} {{");
			println!("	#[inline]");
			println!("	fn output(s: u{bits}) -> u{x_bits} {{");
			println!("		let xsl = s ^ (s >> {x_shift});");
			println!("		let l = (xsl as u{}).rotate_right((s >> {}) as u32);", bits / 2, bits - op);
			println!(
				"		let h = ((xsl >> {top_spare}) as u{}).rotate_right((l & 0b{:b}) as u32);",
				bits / 2,
				(1 << op) - 1
			);
			println!("		u{x_bits}::from(l) | (u{x_bits}::from(h) << {top_spare})");
			println!("	}}");
			println!("}}");
			println!();
		}

		println!("/// fixed xorshift (to low bits), random rotate (both parts)");
		println!("#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]");
		println!("pub struct {NAME};");
		println!();

		print(64, 64);
		print(128, 128);
	}
}