sots-engine/docs/mars-rng.md

mars::rng — the engine PRNG

src/mars/rng/mt19937.h — a textbook 32-bit Mersenne Twister (MT19937), the generator the strategy simulation draws every roll from (map generation, research, encounters, raids, …). Because all lockstep peers share one seeded stream, the reimplementation has to be bit-exact and consume words in the same order; the save file carries the generator state verbatim.

API

mars::rng::MT19937 r(seed);        // seed(): Knuth initializer, then one twist (left == 624)
uint32_t y = r.next_u32();         // tempered output
double   u = r.next_unit();        // y / (2^32 - 1) in double -- see "Draw mappings"
float    f = r.next_float();       // the same draw narrowed to float32; range [0, 1] CLOSED
uint32_t k = r.next_int_inclusive(n);  // uniform [0, n] INCLUSIVE: mask covering n + rejection
r.load_state(mt, left);            // or load_state(blob, 0x9c4) from a save's "RNG" item
r.save_state(out);                 // mt[624] + left, 0x9c4 bytes little-endian
r.left(); r.index(); r.state();

State model

member	meaning
mt[624]	the untempered state block
left	words still unread in the current block; next output is mt[624 - left]

next_u32() twists when left is 0, hands out mt[624 - left], decrements left, and tempers. A freshly seeded generator has already twisted once, so left == 624 and the first draw is mt[0].

Serialized form (the save's RNG frame)

Sim → RNG { "." raw[2503] }: 624 × uint32 (mt) followed by one int32 (left) = 0x9c4 = 2500 bytes, plus the 3 joint-padding bytes of the item. MT19937::load_state(blob, n) parses it and rejects left outside 0..624; save_state writes the same layout.

Verified on the real saves (tests/mars_stream/test_save.cpp): the 624-word block in all three saves equals seed(CreateParams.RSeed) followed by exactly two whole twists, and left decreases turn over turn (454 → 432 → 413, i.e. ~20 draws per turn). That confirms the initializer, the twist, the seed source (RSeed) and the blob layout. It does not exercise the tempering or the float mapping (those never touch the saved state).

Reference vectors (tests/mars_stream/test_rng.cpp)

• seed 5489 → 3499211612, 581869302, 3890346734, … ; the 10000th output is 4123659995.
• save_state/load_state round trip, left positioning, malformed-blob rejection.

Draw mappings (settled from the binary, B3)

Both public draws were re-read instruction by instruction for B3 (docs/B3.md), and both corrections below are behaviour changes, not cosmetics.

1. The unit divisor is 2^32 - 1, not 2^32. The multiplier in the image is the double 0x3df0000000001000, which is 1/4294967295, and the sequence is: sign-extending integer load of the tempered word, + 2^32 when the signed reading is negative (the unsigned fix-up), then the multiply. So next_unit() == y / (2^32 - 1) and the range is closed: y == 0xffffffff maps to exactly 1.0, not to just below it. MT19937::kUnitScale holds the constant. The previous 2^-32 mapping differed by 2^-32 relative, which is far below a float32 ulp, so the two agree for roughly 99 words in 100 once narrowed. That is worth stating plainly: a behavioural compare over a handful of turns is not strong evidence for either divisor, and tests/mars_stream/test_rng.cpp pins the difference so nobody reads it that way.

2. The value stays in the x87 register. The function leaves the product in st(0) and the caller narrows it; every consumer in the strategic sim stores it to a 4-byte float first, which is what next_float() models. The one thing the binary cannot tell us is the x87 precision-control field in force at run time: at the MSVC default (53-bit) the multiply rounds to double and the caller's store rounds again, while a Direct3D 9 device created without FPU_PRESERVE leaves 24-bit precision, in which the fix-up and the multiply each round to 24 bits. float_from_pc24() models the second case; the shim records the control word with every ProcessResearch call so one run settles it. The two mappings can only differ in the last bit of the float.

3. next_int_inclusive(n) is inclusive. The mask is the smallest 2^k - 1 that is >= n (computed from n itself, not n - 1), and the loop re-draws while the masked word is greater than n — so the result is uniform on [0, n], one value wider than the half-open range the notes assumed. n == 0 masks to 0 and still consumes a word. The bound reaches the callee by pointer, which is why the prototype had stayed unverified.

The entry points, and what each one costs in words

A per-turn RNG budget is only as good as this table. Counting "draws" is not enough: the entry points differ in how many words one call spends, and two of them spend an unbounded number. Seven distinct entry points are recovered; three of them were in no earlier list.

entry point	receives the generator as	words per call
unit / float draw	&mt (object + 4)	exactly 1
bounded integer, inclusive	&mt, bound by pointer	1 + rejections
probability test	the object	0 or 1 — short-circuits with no draw when p <= 0 or p >= 1
raw 32-bit draw	the object	exactly 1, unconditional
float range (float_range)	the object	exactly 1
triangular integer range (int_range_bell)	the object, as a stack argument	≥ 2
truncated-normal integer range	the object, as a stack argument	2 per attempt, unbounded

Three consequences worth stating separately, because each one is a way a ledger goes wrong:

1. Two conventions for the same object. The unit and bounded-integer draws are entered with a pointer to the state block, i.e. the generator plus four bytes; the other five are entered with the generator itself and do the + 4 internally. One caller uses both conventions within forty bytes of itself. Reading the wrong base is the failure mode guides/method-rules.md rule 1 already paid for once, at a different offset.

2. Two different divisors live in the same image. The unit draw scales by 1/(2^32 - 1); the truncated-normal path scales by 2^-32 and offsets the word by +0.5 first. They are not interchangeable, and the second is not modelled here.

3. float_range narrows twice. lo + (hi - lo) * unit is computed with the product stored to a 4-byte float before lo is added, and the sum stored to a float again. Evaluating the whole expression in double and narrowing once disagrees on a measurable fraction of words; test_rng.cpp asserts the two models are distinguishable so the shortcut cannot creep back in unnoticed.

The probability test (chance) is the only entry point that can cost nothing, and that is load-bearing. p <= 0 returns false and p >= 1 returns true, each without touching the generator; in between it spends exactly one word and compares with a strict <. The zero-cost cases decide stream alignment wherever a caller's probability climbs: the spy counter-mission adds 0.2f per failed turn, so it spends a word for four turns and then nothing at all from the fifth on. A model without the early-outs is one word out of step from that point forward, for ever — and one word of drift is the whole determinism claim.

NaN is deliberately not special-cased. Both early-out tests are written in the original as pairs of ordered comparisons, which a NaN makes false, so a NaN probability falls through, draws a word, and returns false. That word is reproduced here: a caller that computes a NaN probability really does perturb the stream, and smoothing it over would hide a genuine divergence rather than prevent one.

int_range_bell is triangular, not uniform: the span is split into h/2 and h - h/2 (truncating toward zero) and each half is drawn separately, so the sum peaks in the middle. The two bounds reach the draw as unsigned, so an inverted range does not produce an empty result — it produces a very large first bound. That is reproduced rather than corrected.

The truncated-normal generator is documented but not modelled: it is rejection sampling around a Box–Muller pair, so it needs log, sqrt and cos to agree bit for bit with the original's CRT before its stream position can be predicted, and nothing in the strategic turn reaches it. Its cost is recorded here so that a ledger which one day sees it does not mistake its two-words-per-attempt for one draw.

Draws the call graph cannot see

The unit draw is inlined at several sites, so the only edge such a site leaves in a call graph is one to the twist — which reads as a bare twist and is not one; it is the lazy twist inside the draw. Any word budget assembled by counting calls to the entry points above is therefore a lower bound, and the way to find the rest is to scan for the tempering immediates at real instruction boundaries rather than for calls. Image-wide, eleven game functions carry such a site — twenty-eight sites between them — besides the ones inside the entry points themselves. Exactly one of the eleven is reachable from the strategic turn driver, and one more from the combat path; the other nine belong to map setup, the lobby, the network layer and two scripted encounters.

Choices that still need binary confirmation

1. Twist timing at the block boundary. We twist lazily when left reaches 0 (so a saved state may carry left == 0). The original's NextFloat/NextInt both test left == 0 on entry, which is the same lazy rule; what the three saves (left = 454/432/413) still do not show is a state saved exactly at the boundary.