owen_scramble.rs

// This implementation is written for clarity rather than for performance
// or memory footprint.  Possible optimizations include:
//
// - Storing the table with bit-packing, reducing its size to 24 bytes.
// - Inlining the hash into the scramble functions to remove
//   redundant seed manipulations.
// - Using the iteration of the scramble process itself to randomize things
//   with fewer hashing rounds.
// - Using SIMD to compute multiple scrambles at once.
// - Etc.


/// Performs a base-2 Owen scramble on an integer.
///
/// Passing different seeds results in different scrambles.
pub fn owen_scramble_base_2(n: u32, seed: u32) -> u32 {
    let mut result = n;
    for i in 0..32 {
        let mask = !1 << i;
        result ^= hash(n & mask, seed) & (1 << i);
    }

    result
}


/// Performs a base-4 Owen scramble on an integer.
///
/// Passing different seeds results in different scrambles.
pub fn owen_scramble_base_4(n: u32, seed: u32) -> u32 {
    const PERMUTATION_TABLE: [[u8; 4]; 24] = [
        [0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3],
        [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1],
        [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3],
        [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0],
        [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3],
        [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0],
        [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2],
        [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0],
    ];

    let mut result = 0;
    for i in 0..16 {
        let mask = !0b11 << (i * 2);
        let perm_i = hash(n & mask, seed ^ (i << 16)) % 24;
        let cell_i = (n >> (i * 2)) & 0b11;
        result |= (PERMUTATION_TABLE[perm_i as usize][cell_i as usize] as u32) << (i * 2);
    }

    result
}


//-------------------------------------------------------------


/// A fast, seedable hash function for use in the functions above.
///
/// This can be replaced with any seedable hash function of reasonble quality.
pub fn hash(mut n: u32, seed: u32) -> u32 {
    // Rotate the bits of `seed` so it's unlikely to interact with `n`
    // in bad ways if they're both e.g. incrementing.  The particular
    // rotation constant used here isn't special.
    n ^= seed.rotate_left(23);

    // The actual hash, from https://github.com/skeeto/hash-prospector
    n ^= n >> 16;
    n = n.wrapping_mul(0x21f0aaad);
    n ^= n >> 15;
    n = n.wrapping_mul(0xd35a2d97);
    n ^= n >> 15;

    // Xor by a random number so input `n = 0, seed = 0` doesn't map
    // to output zero.  The particular number used here isn't special.
    n ^ 0xe6fe3beb
}