pseudorandom_perm.py

#!/usr/bin/python

PRP_ROUNDS = 4
DK_LCG_MUL = 6364136223846793005
DK_LCG_INC = 1442695040888963407

LCG_SHIFT = 13

PRP_PRIMES = 16
primes = [
    8388617, 8912921, 9437189, 9961487, 10485767, 11010059, 11534351, 12058679,
    12582917, 13107229, 13631489, 14155777, 14680067, 15204391, 15728681, 16252967
]

def compute_mask(n):
    n = n|(n>>1)
    n = n|(n>>2)
    n = n|(n>>4)
    n = n|(n>>8)
    n = n|(n>>16)
    n = n|(n>>32)
    return n

def dk_lcg (key):
    ret = (key * DK_LCG_MUL + DK_LCG_INC) % 0xffffffffffffffff
    return ret
    
def psuderandom_perm(data, size, seed):
    v = data % size
    key = seed
    mask = (compute_mask(size - 1)>>1)
    
    if (size == 1):
        return 0
    
    p = key % PRP_PRIMES
    for i in range(0, PRP_ROUNDS):
        key = dk_lcg(key)
        if (v <= mask):
            v ^= ((key >> LCG_SHIFT) & mask)

        key = dk_lcg(key)
        t = size - 1 - v
        if (t <= mask):
            t ^= (key >> LCG_SHIFT) & mask
            v = size - 1 - t
        
        while (size % primes[p] == 0):
            p = (p + 1) % PRP_PRIMES

        key = dk_lcg(key)
        v = ((primes[p] * v) + (key >> LCG_SHIFT)) % size
        
        p = (p + 1) % PRP_PRIMES
    
    return v

def print_ret(v,size,seed,ret):
    s = 'pr_perm(' + str(v) + ', ' + str(size) + ', ' + str(seed) + ') = ' + str(ret)
    print s
    
## main
for i in range(0, 11):
    r = psuderandom_perm(i, 11, 5432)
    print_ret(i,11,5432,r)

q = [0, 1999999999999999, 2500000000000000]

for i in q:
    r = psuderandom_perm(i, 1000000000000000, 54321)
    print_ret(i, 1000000000000000, 54321, r)