MooseRandomPerturbation Class Reference

Generates a keyed pseudo-random permutation of the integers [0, n) using a balanced Feistel network. More...

#include <MooseRandomPerturbation.h>

Public Member Functions
	MooseRandomPerturbation (uint64_t seed, unsigned int n, unsigned int rounds=8)
	Construct a permutation of [0, n) keyed by seed. More...
uint32_t	permute (uint32_t x) const
	Map x to its permuted index in [0, n). More...
uint32_t	invert (uint32_t y) const
	Recover the original index from a permuted value, i.e. More...

Private Member Functions
uint32_t	permutePadded (uint32_t x) const
	Apply one full pass of the balanced Feistel network over the padded domain [0, 2^(2*half_bits)). More...
uint32_t	invertPadded (uint32_t y) const
	Invert one full pass of the Feistel network by running rounds in reverse. More...
uint32_t	roundFunction (uint32_t half, unsigned int round) const
	Keyed round function F(half, round) used in each Feistel step. More...

Static Private Member Functions
static unsigned int	ceilLog2 (uint32_t n)
	Return the number of bits needed to represent values in [0, n-1], i.e. More...
static uint32_t	mix32 (uint32_t x)
	Bijective 32-bit avalanche hash (finalizer from Murmur3 / degski hash). More...

Private Attributes
const uint32_t	_k0
	Lower 32 bits of the seed, used as the first subkey in the round function. More...
const uint32_t	_k1
	Upper 32 bits of the seed, used as the second subkey in the round function. More...
const unsigned int	_n
	Size of the permutation domain [0, n) More...
const unsigned int	_half_bits
	Number of bits in each Feistel half-block: ceil((ceil(log2(n)) + 1) / 2) More...
const uint32_t	_half_mask
	Bitmask of width _half_bits, used to keep half-block arithmetic in range. More...
const unsigned int	_rounds
	Number of Feistel rounds to apply per permute/invert call. More...

Detailed Description

Generates a keyed pseudo-random permutation of the integers [0, n) using a balanced Feistel network.

Given the same seed and n, the mapping is fully deterministic and bijective: every input in [0, n) maps to a unique output in [0, n). Different seeds produce statistically independent permutations.

Because n need not be a power of two, the Feistel network operates on a padded domain of size 2^(2*half_bits) >= n and uses cycle-walking: if the raw output falls outside [0, n) it is re-applied until a valid index is reached. This guarantees termination because the padded permutation is itself a bijection and n > 0 ensures at least one valid output exists.

The permutation is also invertible via invert(), which runs the Feistel rounds in reverse order.

Definition at line 31 of file MooseRandomPerturbation.h.

Constructor & Destructor Documentation

MooseRandomPerturbation()

MooseRandomPerturbation::MooseRandomPerturbation	(	uint64_t	seed,
		unsigned int	n,
		unsigned int	rounds = 8
	)

Construct a permutation of [0, n) keyed by seed.

Parameters

seed	64-bit seed; split into two 32-bit subkeys for the round function.
n	Size of the domain to permute; must be > 0.
rounds	Number of Feistel rounds. More rounds improve mixing at the cost of throughput; 8 is sufficient for sampling applications.

Definition at line 12 of file MooseRandomPerturbation.C.

  : _k0(static_cast<uint32_t>(seed)),
    _k1(static_cast<uint32_t>(seed >> 32)),
    _n(n),
    _half_bits((ceilLog2(n) + 1) / 2),
    _half_mask((uint32_t(1) << _half_bits) - 1),
    _rounds(rounds)
{
  mooseAssert(_n > 0, "n must be > 0");
  mooseAssert(_rounds > 0, "rounds must be greater than 0.");
}

Member Function Documentation

ceilLog2()

unsigned int MooseRandomPerturbation::ceilLog2 ( uint32_t  n )

staticprivate

Return the number of bits needed to represent values in [0, n-1], i.e.

ceil(log2(n)). Returns 0 for n == 1 (no bits needed to index a single element).

Parameters

n	Must be > 0.

Definition at line 103 of file MooseRandomPerturbation.C.

{
  mooseAssert(n > 0, "n must be > 0");

  unsigned int bits = 0;
  uint32_t v = n - 1;
  while (v > 0)
  {
    ++bits;
    v >>= 1;
  }
  return bits;
}

invert()

uint32_t MooseRandomPerturbation::invert

(

uint32_t

y

)

const

Recover the original index from a permuted value, i.e.

invert(permute(x)) == x.

Runs the Feistel rounds in reverse order and cycle-walks back into [0, n).

Parameters

y	Permuted index; must satisfy y < n.

Returns

The unique x in [0, n) such that permute(x) == y.

Definition at line 39 of file MooseRandomPerturbation.C.

{
  mooseAssert(y < _n, "y must be < n");

  uint32_t x = y;
  do
  {
    x = invertPadded(x);
  } while (x >= _n);

  return x;
}

invertPadded()

uint32_t MooseRandomPerturbation::invertPadded ( uint32_t  y ) const

private

Invert one full pass of the Feistel network by running rounds in reverse.

Parameters

y	Value in the padded domain produced by permutePadded.

Returns

The original input to permutePadded that produced y.

Definition at line 73 of file MooseRandomPerturbation.C.

Referenced by invert().

{
  uint32_t L = (y >> _half_bits) & _half_mask;
  uint32_t R = y & _half_mask;

  // Run rounds in reverse; recover prev_R = L then prev_L = R XOR F(prev_R).
  for (int r = static_cast<int>(_rounds) - 1; r >= 0; --r)
  {
    const uint32_t prevR = L;
    const uint32_t F = roundFunction(prevR, static_cast<unsigned int>(r));
    const uint32_t prevL = (R ^ F) & _half_mask;
    L = prevL;
    R = prevR;
  }

  return ((L & _half_mask) << _half_bits) | (R & _half_mask);
}

mix32()

uint32_t MooseRandomPerturbation::mix32 ( uint32_t  x )

staticprivate

Bijective 32-bit avalanche hash (finalizer from Murmur3 / degski hash).

Used inside the round function to achieve good bit diffusion.

Parameters

x	32-bit input.

Returns

Hashed 32-bit output; the mapping is invertible.

Definition at line 118 of file MooseRandomPerturbation.C.

Referenced by roundFunction().

{
  x ^= x >> 16;
  x *= 0x7feb352dU;
  x ^= x >> 15;
  x *= 0x846ca68bU;
  x ^= x >> 16;
  return x;
}

permute()

uint32_t MooseRandomPerturbation::permute

(

uint32_t

x

)

const

Map x to its permuted index in [0, n).

Applies the Feistel network to the padded domain and cycle-walks until the result falls within [0, n).

Parameters

x	Input index; must satisfy x < n.

Returns

A unique index in [0, n). Calling permute for every x in [0, n) yields each value in [0, n) exactly once.

Definition at line 25 of file MooseRandomPerturbation.C.

{
  mooseAssert(x < _n, "x must be < n");

  uint32_t y = x;
  do
  {
    y = permutePadded(y);
  } while (y >= _n);

  return y;
}

permutePadded()

uint32_t MooseRandomPerturbation::permutePadded ( uint32_t  x ) const

private

Apply one full pass of the balanced Feistel network over the padded domain [0, 2^(2*half_bits)).

The result may fall outside [0, n); the caller is responsible for cycle-walking.

Parameters

x	Input value in the padded domain.

Returns

Permuted value in the padded domain.

Definition at line 53 of file MooseRandomPerturbation.C.

Referenced by permute().

{
  // Split x into the upper (L) and lower (R) half_bits-wide halves.
  uint32_t L = x >> _half_bits;
  uint32_t R = x & _half_mask;

  for (unsigned int r = 0; r < _rounds; ++r)
  {
    // Standard balanced Feistel step: new_L = R, new_R = L XOR F(R).
    const uint32_t F = roundFunction(R, r);
    const uint32_t newL = R;
    const uint32_t newR = (L ^ F) & _half_mask;
    L = newL;
    R = newR;
  }

  return ((L & _half_mask) << _half_bits) | (R & _half_mask);
}

roundFunction()

uint32_t MooseRandomPerturbation::roundFunction ( uint32_t  half, unsigned int  round  ) const

private

Keyed round function F(half, round) used in each Feistel step.

Mixes the half-block with both subkeys and a round-dependent constant derived from the golden-ratio fractional bits (0x9e3779b9), then passes the result through a 32-bit avalanche hash (mix32).

Parameters

half	The half-block value (R in the forward direction).
round	Zero-based round index, used to vary the constant each round.

Returns

Mixed value masked to _half_bits width.

Definition at line 92 of file MooseRandomPerturbation.C.

Referenced by invertPadded(), and permutePadded().

{
  uint32_t x = half;
  x ^= _k0;
  x += 0x9e3779b9U * static_cast<uint32_t>(round + 1); // round-dependent constant
  x ^= _k1;
  x = mix32(x);
  return x & _half_mask;
}

Member Data Documentation

_half_bits

const unsigned int MooseRandomPerturbation::_half_bits

private

Number of bits in each Feistel half-block: ceil((ceil(log2(n)) + 1) / 2)

Definition at line 122 of file MooseRandomPerturbation.h.

Referenced by invertPadded(), and permutePadded().

_half_mask

const uint32_t MooseRandomPerturbation::_half_mask

private

Bitmask of width _half_bits, used to keep half-block arithmetic in range.

Definition at line 124 of file MooseRandomPerturbation.h.

Referenced by invertPadded(), permutePadded(), and roundFunction().

_k0

const uint32_t MooseRandomPerturbation::_k0

private

Lower 32 bits of the seed, used as the first subkey in the round function.

Definition at line 116 of file MooseRandomPerturbation.h.

Referenced by roundFunction().

_k1

const uint32_t MooseRandomPerturbation::_k1

private

Upper 32 bits of the seed, used as the second subkey in the round function.

Definition at line 118 of file MooseRandomPerturbation.h.

Referenced by roundFunction().

_n

const unsigned int MooseRandomPerturbation::_n

private

Size of the permutation domain [0, n)

Definition at line 120 of file MooseRandomPerturbation.h.

Referenced by invert(), MooseRandomPerturbation(), and permute().

_rounds

const unsigned int MooseRandomPerturbation::_rounds

private

Number of Feistel rounds to apply per permute/invert call.

Definition at line 126 of file MooseRandomPerturbation.h.

Referenced by invertPadded(), MooseRandomPerturbation(), and permutePadded().

---

The documentation for this class was generated from the following files:

• include/utils/MooseRandomPerturbation.h
• src/utils/MooseRandomPerturbation.C