Memory free pseudo random permutation of a range of indices

permute.cpp

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

// Non stored iteration order over a 2D array of dimension NxM
// (walk through every cell only once)

// 1. deterministic orders 
// row per row
// col per col
// tile per tile
// Z order (Morton code)
// hilbert curve order (and others space filling curves orders)

// 2. pseudo random orders
// LCG pseudo random of size N*M, cf. https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
// Pseudo random permutations AES 
// Hash permutations : cf permute

// cf. Correlated Multi Jittered Sampling 
// https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf
// provided code: up to 2^27 sized domain
// + cycle walking for non power of 2 domains size
unsigned int permute(unsigned int i, unsigned int l, unsigned int p)
{
    unsigned int w = l - 1 ;
    w |= w >> 1;
    w |= w >> 2;
    w |= w >> 4;
    w |= w >> 8;
    w |= w >> 16;
    do
    {
        i ^= p;
        i *= 0xe170893d;
        i ^= p >> 16;
        i ^= (i & w) >>  4;
        i ^= p >> 8;  
        i *= 0x0929eb3f;
        i ^= p >> 23;
        i ^= (i & w) >> 1;   
        i *= 1 | p >> 27;  
        i *= 0x6935fa69;
        i ^= (i & w) >> 11;  
        i *= 0x74dcb303;
        i ^= (i & w) >> 2;  
        i *= 0x9e501cc3;
        i ^= (i & w) >> 2;  
        i *= 0xc860a3df;
        i &= w;
        i ^= i >> 5;
    }
    while(i >= l);
    return (i+p)%l;
}

bool test(const std::vector<int>& vec)
{
    return std::all_of(vec.cbegin(), vec.cend(), [](int i){return i == 1;});
}

int main(int argc, char * argv[])
{   
    int n = 1024*1024;
    std::vector<int> vec(n, 0);
    unsigned int seed = std::random_device()();
    for(int i = 0; i < n; ++i)
    {
        int idperm = permute(i, n, seed);
        ++vec[idperm]; 
    }
    bool all = test(vec);
    printf("Each index is drawn only once ? %d\n", (int)all);
    return 0;
}