RNG of flexible output

37 views
Skip to first unread message

Jsknkj RNG

unread,
Oct 24, 2021, 12:31:37 PM10/24/21
to prng
Suppose I wanted to use an output size as necessary throughout the code. I wpould write something like this:

#include <stdint.h>

static inline uint64_t rotl64(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}

static inline uint32_t rotl32(const uint32_t x, int k) {
return (x << k) | (x >> (32 - k));
}

static inline uint16_t rotl16(const uint16_t x, int k) {
return (x << k) | (x >> (16 - k));
}

static inline uint8_t rotl8(const uint8_t x, int k) {
return (x << k) | (x >> (8 - k));
}

union rngstate{
 uint8_t s8[16];
 uint16_t s16[8];
 uint32_t s32[4];
 uint64_t s64[2];
};

static rngstate s;

static int p8;

uint64_t next64(void) {
const uint64_t s0 = s.s64[0];
uint64_t s1 = s.s64[1];
const uint64_t result = rotl64(s0 + s1, 17) + s0;
s1 ^= s0;
s.s64[0] = rotl64(s0, 49) ^ s1 ^ (s1 << 21); // a, b
s.s64[1] = rotl64(s1, 28); // c
return result;
}

long double nextld(void) {
const uint64_t s0 = s.s64[0];
uint64_t s1 = s.s64[1];
const long double result = (rotl64(s0 + s1, 17) + s0)/0x1.p-64l;
s1 ^= s0;
s.s64[0] = rotl64(s0, 49) ^ s1 ^ (s1 << 21); // a, b
s.s64[1] = rotl64(s1, 28); // c
return result;
}

double nextd(void) {
const uint64_t s0 = s.s64[0];
uint64_t s1 = s.s64[1];
const double result = ((s0 + s1)>>11)/0x1.p-53;
s1 ^= s0;
s.s64[0] = rotl64(s0, 49) ^ s1 ^ (s1 << 21); // a, b
s.s64[1] = rotl64(s1, 28); // c
return result;
}

uint32_t next32(void) {
const uint32_t result = rotl32(s.s32[0] + s.s32[3], 7) + s.s32[0];
const uint32_t t = s.s32[1] << 9;
s.s32[2] ^= s.s32[0];
s.s32[3] ^= s.s32[1];
s.s32[1] ^= s.s32[2];
s.s32[0] ^= s.s32[3];
s.s32[2] ^= t;
s.s32[3] = rotl32(s.s32[3], 11);
return result;
}

float nextf(void) {
const float result = ((s.s32[0] + s.s32[3])>>8)/0x1.p-24f;
const uint32_t t = s.s32[1] << 9;
s.s32[2] ^= s.s32[0];
s.s32[3] ^= s.s32[1];
s.s32[1] ^= s.s32[2];
s.s32[0] ^= s.s32[3];
s.s32[2] ^= t;
s.s32[3] = rotl32(s.s32[3], 11);
return result;
}

uint16_t next16(void) {
const uint16_t result = rotl16(s.s16[0] + s.s16[2], 1) + s.s16[2];
const uint16_t t = s.s16[1] << 11;
s.s16[2] ^= s.s16[0];
s.s16[5] ^= s.s16[1];
s.s16[1] ^= s.s16[2];
s.s16[7] ^= s.s16[3];
s.s16[3] ^= s.s16[4];
s.s16[4] ^= s.s16[5];
s.s16[0] ^= s.s16[6];
s.s16[6] ^= s.s16[7];
s.s16[6] ^= t;
s.s16[7] = rotl16(s.s16[7], 5);
return result;
}

uint8_t next8(void) {
const int q = p8;
const uint8_t s0 = s.s8[p8 = (p8 + 1) & 15];
uint8_t s15 = s.s8[q];
const uint8_t result = rotl8(s0 + s15, 7) + s15;
s15 ^= s0;
s.s8[q] = rotl8(s0, 1) ^ s15 ^ (s15 << 3);
s.s8[p8] = rotl8(s15, 4);
return result;
}

(I know the constants for next16 and next8 are most likely incorrect, but this is for demonstration)

In this example, I compile to 32-bit x86 (in a compiler that supports 64-bit integer type, and long double is extended precision of 64 significant bits) and have long double, double, float, 64-bit, 32-bit, 16-bit, and 8-bit output all from a single 128-bit state. Because both xoroshiro and xoshiro require the state not to be all zeros, so there should not be zero array interference between them. However, it might be possible that advancing one generator could be equivalent to going a few steps back in another, leading to sequence overlap. What do you think?

Jsknkj RNG

unread,
Oct 26, 2021, 11:24:19 AM10/26/21
to prng
Added 4-bit and 2-bit generators.

static inline uint8_t rotl4(const uint8_t x, int k) {
return ((x << k) | (x >> (4 - k)))&0xF;
}

static inline uint8_t rotl2(const uint8_t x, int k) {
return ((x << k) | (x >> (2 - k)))&0x3;
}

static int p4;

static int p2;

uint8_t next4(void) {
const int q = p4;
p4 = (p4 + 1) & 31;
const uint8_t s0 = ((s.s8[p4>>1])>>((p4&1)*4))&0xF;
uint8_t s31 = ((s.s8[q>>1])>>((q&1)*4))&0xF;
const uint8_t result = (rotl4((s0 + s31)&0xF, 3) + s31)&0xF;
s31 ^= s0;
s.s8[q>>1] &= ~(0x0F<<((q&1)*4));
s.s8[q>>1] |= ((rotl4(s0, 1) ^ s31 ^ ((s31 << 3)&0xF))<<((q&1)*4));
s.s8[p4>>1] &= ~(0x0F<<((p4&1)*4));
s.s8[p4>>1] |= ((rotl4(s31, 2))<<((p4&1)*4));
return result;
}

uint8_t next2(void) {
const int q = p2;
p2 = (p2 + 1) & 63;
const uint8_t s0 = ((s.s8[p2>>2])>>((p2&3)*2))&0x3;
uint8_t s63 = ((s.s8[q>>2])>>((q&3)*2))&0x3;
const uint8_t result = (rotl2((s0 + s63)&0x3, 1) + s63)&0x3;
s63 ^= s0;
s.s8[q>>2] &= ~(0x03<<((q&3)*2));
s.s8[q>>2] |= ((rotl2(s0, 1) ^ s63 ^ ((s63 << 1)&0x3))<<((q&3)*2));
s.s8[p2>>2] &= ~(0x03<<((p2&3)*2));
s.s8[p2>>2] |= ((rotl2(s63, 1))<<((p2&3)*2));
return result;
}

In the 2-bit case, the low bit of the scrambler is an LFSR (so ++ is a weak scrambler for 2-bit). Changing the rotation to 0 would make both bits LFSR. The shift has to stay at 1, the other rotations could be changed to 0 as the only potential reparametrizations remaining.

It's impossible to get a 1-bit xoroshiro working, because the bitshift part cannot be done with only 1 bit and the generator fails.
Reply all
Reply to author
Forward
0 new messages