GhostScramble

Table of Contents

• Introduction
• Author
• License
• Implementation
• Parallelism
• Randomness Quality
• Speed

Introduction

GhostScramble is the efficient PRNG (for advanced graphics rendering in video game engines) that has 64-bit integers (for modern 64-bit architecture), a minimum period of at least 2⁶⁴ (from a Weyl sequence), excellent randomness test results, hyper-fast speed, low-footprint implementation, reversibility (non-cryptographic state rewinding) and segmented parallel sequences.

Author

GhostScramble was created by William Stafford Parsons as a product of Eightomic.

License

GhostScramble uses a proprietary license.

Implementation

Each mention of GhostScramble refers to each of the 3 following variants individually (ghostscramble64, ghostscramble128 and ghostscramble256) implemented in C (requiring the stdint.h header to define a 64-bit, unsigned integral type for uint64_t).

ghostscramble.c

ghostscramble64

The ghostscramble64 function modifies the state in a struct ghostscramble64_state instance to generate a pseudorandom uint64_t integer as the return value.

Each state variable (a, b and c) in a struct ghostscramble64_state instance must be seeded before generating a deterministic ghostscramble64 sequence (that must discard the first 3 ghostscramble64 results as a state warmup).

ghostscramble128

The ghostscramble128 function modifies the state in a struct ghostscramble128_state instance to generate 2 pseudorandom uint64_t integers in the output array.

Each single-letter state variable (a, b and c) in a struct ghostscramble128_state instance must be seeded before generating a deterministic ghostscramble128 sequence (that must discard the first 3 ghostscramble128 results as a state warmup).

ghostscramble256

The ghostscramble256 function modifies the state in a struct ghostscramble256_state instance to generate 4 pseudorandom uint64_t integers in the output array.

Each single-letter state variable (a, b, c and d) in a struct ghostscramble256_state instance must be seeded before generating a deterministic ghostscramble256 sequence (that must discard the first 3 ghostscramble256 results as a state warmup).

Parallelism

Each instance within a set of parallel GhostScramble instances must adhere to the following single-letter variable seeding rules before generating a set of up to 2⁶⁴ parallel GhostScramble sequences (that each have non-probabilistic full state collision avoidance with each other for a period of at least 2⁶⁴) without fixed-key variables or fixed-length jump-ahead functions (each parallel GhostScramble sequence has a minimum distance of 2⁶⁴ output results between each other).

1. a (the chaotic accumulation mixing variable that XOR-rotates with b) must be seeded with an integer that's unique among the set of parallel GhostScramble instances.
2. b (the Weyl sequence variable) must be seeded with an integer that's consistent among the set of parallel GhostScramble instances.
3. The remaining single-letter state variables must be seeded.

After seeding a set of parallel GhostScramble instances, reseeding (or tampering with) either a or b voids the aforementioned parallelism independence properties that are provable in the following exhaustive black-box tests (scaled down to 8-bit integers for computational feasibility).

#include <stdint.h>
#include <stdio.h>

int circular_shift;
unsigned short odd_increase;

struct black_box_state {
  uint8_t a;
  uint8_t b;
};

void black_box(struct black_box_state *s) {
  s->a = ((s->a << circular_shift) | (s->a >> (8 - circular_shift))) ^ s->b;
  s->b += odd_increase;
}

int main(void) {
  struct black_box_state s;
  unsigned short i = 0;
  unsigned short j;

  while (i < 256) {
    j = 0;

    while (j < 256) {
      circular_shift = 1;

      while (circular_shift < 8) {
        odd_increase = 1;

        while (odd_increase < 256) {
          s.a = i;
          s.b = j;
          black_box(&s);

          while (s.b != j) {
            black_box(&s);
          }

          if (s.a != i) {
            printf("The state collides when a is %u and b is %u.\n", i, j);
          }

          odd_increase += 2;
        }

        circular_shift++;
      }

      j++;
    }

    i++;
  }

  return 0;
}

Subtle stochastic cross-correlations among segmented parallel GhostScramble instances fall within practical tolerance parameters (for visual artifact reduction) in advanced graphics rendering scenarios (such as complex output transformations for rejection sampling).

Randomness Quality

GhostScramble uses straightforward chaotic state accumulation procedures (drastically reducing the probability of encountering hidden statistical biases from specific seeded states) to generate sequences that each have a minimum period of at least 2⁶⁴ (from a Weyl sequence).

Therefore, GhostScramble yielded excellent results (not tampering with GhostScramble state variables after seeding each single-letter state variable with 0) from statistical test suites for randomness quality.

PractRand 0.96

GhostScramble passed RNG_test stdin -tlmax 4TB -tlmin 1KB tests.

TestU01 1.2.3

GhostScramble passed BigCrush tests (using each uint64_t output integer as 2 uint32_t integers).

Dieharder 3.31.1

GhostScramble passed dieharder -Y 1 -a -g 200 -k 2 extended tests (each ambiguous result resolved to a PASSED result).

NIST STS 2.1.2

GhostScramble passed assess 1000000 tests (using 100 bitstreams).

Speed

Each of the following results log the fastest process execution speed (in milliseconds) among several repetitions of a speed benchmark (using gcc -O3 from an AMD A4-9120C) that generates (and hashes) 1 billion pseudorandom uint64_t integers in a #pragma GCC unroll 0 loop.

PRNG	Elapsed
ghostscramble256	561ms
ghostscramble128	743ms
***shishua_avx2 (-mavx2)	866ms
**aesdec2 (-maes -msse4)	905ms
**shishua_sse4 (-msse4)	978ms
ghostscramble64	1072ms
**shishua_sse3 (-msse3)	1147ms
**shishua_sse2 (-msse2)	1154ms
biski64	1292ms
sfc64	1320ms
xoshiro256_plus	1546ms
xorshiftr128_plus	1654ms
jsf64_2rotate	1718ms
xoroshiro128_plus	1733ms
mrsf64	1833ms
jsf64_3rotate	1841ms
mrc64	1862ms
romu_trio	1894ms
wob2m	1928ms
mwc192	1997ms
wyrand	2033ms
xorshift64	2135ms
shishua	2251ms
xorshift128_plus	2260ms
*xorwow	2882ms
romu_mono	2982ms
*pcg32_minimal	2983ms
*pcg_oneseq_64_xsh_rr_32	2987ms
mwc128	2998ms
*lehmer_mcg32	3402ms
*pcg_oneseq_64_xsh_rs_32	3404ms
*lcg32	3409ms
lehmer_mcg64	3413ms
lcg64	3416ms
**aes_ni_ctr_128 (-maes -msse4)	3796ms
pcg_oneseq_64_xsl_rr_rr_64	3928ms
*isaac	4099ms
splitmix64	4385ms
cwg64	4680ms
cwg128	4757ms
**sfmt (-msse2)	5525ms
lxm_xbg128	5863ms
wanghash64	5983ms
pcg_oneseq_128_xsh_rr_64	6833ms
mt19937_64	7126ms
*squares32	7552ms
pcg64_dxsm	7604ms
pcg_oneseq_128_xsh_rs_64	7676ms
philox4x64	9171ms
*****google_randen (-maes -msse4)	9206ms
squares64	9596ms
*chacha8	13230ms
tinymt64	16081ms
****mrg32k3a	19356ms
*chacha20	26402ms
*rand (stdlib.h)	46083ms

* Each n-bit output integer was casted to a uint64_t integer.

** Each 128-bit output integer was extracted as 2 uint64_t integers.

*** Each 256-bit output integer was extracted as 4 uint64_t integers.

**** Each output integer was returned as a uint64_t integer (omitting the double integer conversion).

***** Each block of 4 uint8_t output integers were merged into a uint32_t integer that was casted to a uint64_t integer.