extends RefCounted
class_name Pcg32
## DETERMINISTIC RANDOMNESS for the fold (#120 F4, docs/node-tree-and-stacks.md §5).
##
## PCG32 (O'Neill's pcg-c-basic, `pcg32_random_r` / `pcg32_srandom_r` /
## `pcg32_boundedrand_r`), so a generator that scatters panels or sags a cable gives
## every peer the same brushes. Godot's RandomNumberGenerator is never used in a fold:
## its algorithm is not a contract between engine versions.
##
## NO 64-BIT OVERFLOW, ANYWHERE. GDScript's int is a signed int64, and PCG needs
## unsigned 64-bit multiply mod 2^64; letting int64 wrap is C++ undefined behaviour in
## the engine. So the 64-bit state is two 32-bit halves and every product is built from
## 16-bit limbs, which keeps each intermediate below 2^34. Floats come only from
## `u32 / 2^32`.
const M32 := 0xffffffff
## 6364136223846793005, the PCG 64-bit multiplier, as halves.
const MUL_HI := 0x5851f42d
const MUL_LO := 0x4c957f2d
var _sh := 0 # state, high and low 32 bits
var _sl := 0
var _ih := 0 # increment (always odd)
var _il := 0
## pcg32_srandom_r(initstate, initseq), each given as 32-bit halves.
func _init(state_hi: int = 0, state_lo: int = 0, seq_hi: int = 0, seq_lo: int = 0) -> void:
# inc = (initseq << 1) | 1
_ih = ((seq_hi << 1) | (seq_lo >> 31)) & M32
_il = ((seq_lo << 1) | 1) & M32
_sh = 0
_sl = 0
next_u32()
var s := _add64(_sh, _sl, state_hi & M32, state_lo & M32)
_sh = s[0]
_sl = s[1]
next_u32()
## Seeded from two non-negative ints (each below 2^63).
static func seeded(state: int, seq: int) -> Pcg32:
return Pcg32.new((state >> 32) & M32, state & M32, (seq >> 32) & M32, seq & M32)
## Seeded from what makes a stream unique — record dot, stage index, the user's seed —
## through SHA-256 (a standard, so the same on every peer and engine version). Two
## modifiers never share a stream, and a reseed is one changed part.
static func from_parts(parts: Array) -> Pcg32:
var text := ""
for i in parts.size():
text += ("|" if i > 0 else "") + str(parts[i])
var h: PackedByteArray = text.sha256_buffer()
return Pcg32.new(_u32(h, 0), _u32(h, 4), _u32(h, 8), _u32(h, 12))
## The next 32-bit output, 0 .. 2^32 - 1.
func next_u32() -> int:
var oh := _sh
var ol := _sl
var m := _mul64(oh, ol, MUL_HI, MUL_LO)
var s := _add64(m[0], m[1], _ih, _il)
_sh = s[0]
_sl = s[1]
# xorshifted = ((old >> 18) ^ old) >> 27, truncated to 32 bits
var vh := (oh >> 18) ^ oh
var vl := (((ol >> 18) | (oh << 14)) & M32) ^ ol
var x := ((vl >> 27) | (vh << 5)) & M32
var rot := oh >> 27 # old >> 59
return ((x >> rot) | (x << ((32 - rot) & 31))) & M32
## Uniform in 0 .. bound - 1 with no modulo bias (pcg32_boundedrand_r).
func bounded(bound: int) -> int:
if bound <= 1:
return 0
var threshold := ((M32 + 1 - bound) & M32) % bound
while true:
var r := next_u32()
if r >= threshold:
return r % bound
return 0
## Uniform in [0, 1).
func next_float() -> float:
return float(next_u32()) / 4294967296.0
## Uniform in [lo, hi).
func range_f(lo: float, hi: float) -> float:
return lo + (hi - lo) * next_float()
static func _u32(b: PackedByteArray, at: int) -> int:
return (b[at] << 24) | (b[at + 1] << 16) | (b[at + 2] << 8) | b[at + 3]
static func _add64(ah: int, al: int, bh: int, bl: int) -> Array:
var l := al + bl
return [(ah + bh + (l >> 32)) & M32, l & M32]
## The full 64-bit product of two 32-bit values, as [hi, lo], from 16-bit limbs.
static func _mul32(x: int, y: int) -> Array:
var x1 := x >> 16
var x0 := x & 0xffff
var y1 := y >> 16
var y0 := y & 0xffff
var mid := x0 * y1 + x1 * y0 # < 2^33
var low := x0 * y0 + ((mid & 0xffff) << 16) # < 2^33
return [(x1 * y1 + (mid >> 16) + (low >> 32)) & M32, low & M32]
## (a * b) mod 2^64, halves in and out.
static func _mul64(ah: int, al: int, bh: int, bl: int) -> Array:
var p: Array = _mul32(al, bl)
var cross: int = ((_mul32(ah, bl)[1] as int) + (_mul32(al, bh)[1] as int)) & M32
return [((p[0] as int) + cross) & M32, p[1]]