Re: pgbench - add pseudo-random permutation function

On 2021-Mar-14, Fabien COELHO wrote:

> + /*-----
> + * Apply 4 rounds of bijective transformations using key updated
> + * at each stage:
> + *
> + * (1) whiten: partial xors on overlapping power-of-2 subsets
> + * for instance with v in 0 .. 14 (i.e. with size == 15):
> + * if v is in 0 .. 7 do v = (v ^ k) % 8
> + * if v is in 7 .. 14 do v = 14 - ((14-v) ^ k) % 8
> + * note that because of the overlap (here 7), v may be changed twice.
> + * this transformation if bijective because the condition to apply it
> + * is still true after applying it, and xor itself is bijective on a
> + * power-of-2 size.
> + *
> + * (2) scatter: linear modulo
> + * v = (v * p + k) % size
> + * this transformation is bijective is p & size are prime, which is
> + * ensured in the code by the while loop which discards primes when
> + * size is a multiple of it.
> + *
> + */

My main question on this now is, do you have a scholar reference for
this algorithm?

--
Álvaro Herrera Valdivia, Chile
"Someone said that it is at least an order of magnitude more work to do
production software than a prototype. I think he is wrong by at least
an order of magnitude." (Brian Kernighan)