Re: pgbench - add pseudo-random permutation function

Hello Alvaro,

>> + /*-----
>> + * 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?

Nope, otherwise I would have put a reference. I'm a scholar though, if
it helps:-)

I could not find any algorithm that fitted the bill. The usual approach
(eg benchmarking designs) is too use some hash function and assume that it
is not a permutation, too bad.

Basically the algorithm mimics a few rounds of cryptographic encryption
adapted to any size and simple operators, whereas encryption function are
restricted to power of two blocks (eg the Feistel network). The structure
is the same AES with its AddRoundKey the xor-ing stage (adapted to non
power of two in whiten above), MixColumns which does the scattering, and
for key expansion, I used Donald Knuth generator. Basically one could say
that permute is an inexpensive and insecure AES:-)

We could add a reference to AES for the structure of the algorithm itself,
but otherwise I just iterated designs till I was satisfied with the
result (again: inexpensive and constant cost, any size, permutation…).

--
Fabien.