DS+DLSFR (Delta-State + Double-LSFR) PRNG

prng.py

import itertools
    

def bit_slice(x, start, stop=None, relative=True):
    if stop is None:
        stop = 16
        
    if not relative:
        stop -= start
        
    mask = (2 ** stop - 1) << start
    return (x & mask) >> start

# 16-bit PRNG.
def evolve(seed):
    new_bits = ~(~bit_slice(seed, 0, 2) ^ ~(bit_slice(seed, 6, 2) ^ bit_slice(seed, 9, 2)))
    
    return (new_bits << 14 | seed >> 2) & 0xFFFF

def prng_infinite(seed):
    while True:
        seed = evolve(seed)
        yield seed
        
def prng(seed, amount=30):
    return itertools.islice(prng_infinite(seed), amount)

if __name__ == "__main__":
    import sys, random
    
    avg_p = 0
    i = 0
    min_p = None
    max_p = None
    
    for initial_seed in range(0x10000):
        seed = initial_seed
        cur_p = 0
        
        while True:
            seed = evolve(seed)
            
            if seed == initial_seed:
                break
                
            cur_p += 1
            
        if i == 0:
            avg_p = cur_p
            
        else:
            avg_p = ((avg_p * i) + cur_p) / (i + 1)
            
        print(initial_seed, cur_p, avg_p)
        i += 1
        
        if min_p is None or cur_p < min_p:
            min_p = cur_p
            
        if max_p is None or cur_p > max_p:
            max_p = cur_p
    
    print("Average PRNG period: {} | Min: {} | Max: {}".format(avg_p, min_p, max_p))

sprng.py

from seedlist import prng


def selfgen(func):
    def _inner(*args, **kw):
        return func(func, *args, **kw)
    
    return _inner

def make_delta(seed):
    delta = ~(prng.evolve(seed) ^ seed)
    
    if delta < 0:
        delta = -delta
        
    return delta

@selfgen
def generate(self, seed, delta=None):
    if delta is None:
        delta = make_delta(seed)
    
    seed_a = seed & 0xFFFF
    seed_b = prng.evolve(delta) ^ seed_a
    self.init_delta = delta
    
    while True:
        seed_a = prng.evolve(seed_b) & 0xFFFF
        seed_b = ~prng.evolve(seed_a) & 0xFFFF
        
        new_bits = ~(prng.bit_slice(seed_a, 0, 2) ^ ~(prng.bit_slice(seed_a, 5, 2) ^ ~(prng.bit_slice(seed_b, 3, 2) ^ prng.bit_slice(seed_a, 9, 2))))
        
        if new_bits < 0:
            new_bits = -new_bits
        
        seed_a = seed_a ^ delta
        seed_b = seed_b ^ delta
        
        delta = delta >> 2 | (new_bits << 14)
        
        yield (seed_a, seed_b, delta)
        
def decode(seeds):
    return ((seeds[0] << 8 & 0xFFFF0000 | seeds[1] >> 8) ^ ~(seeds[0] ^ seeds[1])) & 0xFFFF, seeds[2]
        
def evolve(seed, delta=None):
    return next(generate(seed, delta))

if __name__ == "__main__":
    import sys, random
    
    avg_p = 0
    i = 0
    min_p = None
    max_p = None
    
    for initial_seed in range(0x10000):
        initial_delta = make_delta(initial_seed)
        it = generate(initial_seed, initial_delta)
        found = {}
        seed = initial_seed
        cur_p = 0
        
        while True:
            seed, delta = decode(next(it))
            
            if seed in found and delta in found[seed]:
                break
                
            cur_p += 1
            
            if seed in found:
                found[seed].add(delta)
                
            else:
                found[seed] = {delta}
                
            # print(seed)
            
        if i == 0:
            avg_p = cur_p
            
        else:
            avg_p = ((avg_p * i) + cur_p) / (i + 1)
            
        print("i={} c={} p={}".format(initial_seed, cur_p, avg_p))
        i += 1
        
        if min_p is None or cur_p < min_p:
            min_p = cur_p
            
        if max_p is None or cur_p > max_p:
            max_p = cur_p
    
    print("Average PRNG period: {} | Min: {} | Max: {}".format(avg_p, min_p, max_p))