Diablo uses a type of pseudo-random number generator called a Linear Congruential Generator (LCG). … Each dungeon seed is picked by advancing the RNG state then treating the 32 bit state as a signed integer value and transforming it into a positive integer value between 0 and 231 using the C standard library function abs() (yielding a 31 bit seed[6]).
[6]: Plus an extra value; because the absolute value of -231 cannot be represented as a positive signed 32 bit integer, Diablo ends up using this value as-is.
Very, very rarely, the random number generator can generate a negative number when the code expects a number to fall within a random range of positive numbers. The issue lies with a broken implementation of Borland's random function (as listed in the Hellfire source code):
//***************************************************************************
//***************************************************************************
long GetRndSeed() {
SeedCount++;
static const DWORD INCREMENT = 1;
static const DWORD MULTIPLIER = 0x015a4e35L;
sglGameSeed = MULTIPLIER * sglGameSeed + INCREMENT;
return abs(sglGameSeed);
}
//***************************************************************************
//***************************************************************************
long random(byte idx,long v) {
if (v <= 0) return 0;
// high order bits are more "random" than low order bits
if (v < 0x0ffff) return (GetRndSeed() >> 16) % v;
return GetRndSeed() % v;
}
The problem is with the call abs(sglGameSeed). The evident intention is that GetRndSeed should never return a negative number; which is why the function takes an absolute value before returning. But there is one case where the output of abs may be negative. When sglGameSeed has the value 1457187811, the calculation MULTIPLIER * sglGameSeed + INCREMENT results in −2147483648; i.e., −231; i.e., 0x80000000, the most negative signed 32-bit integer. Because this value has no positive counterpart in two's complement arithmetic, the call abs(sglGameSeed) returns the same negative value, −2147483648. This is the only case where GetRndSeed returns a negative value, and this is the only negative value it may return.
When this happens, a call to random will return a value that is ''non-positive''. When v evenly divides −2147483648 (i.e., when v is a power of 2), the return value will be 0; otherwise it will be negative. To put it more plainly: if the game needs to generate a random number within a range (and the upper limit of the range is not a power of 2), there is a very small chance that the number generated will actually be a negative number, instead of a number within that range. This can wreak havoc in the game, causing anything from memory corruption to random sound effects being played. Since the chances of this happening are incredibly small and the effects are so random, it's unlikely that this has been observed more than a handful of times over the years.
The idea of an out-of-bounds write is intriguing, because that is the kind of thing that arbitrary code execution exploits and credits warps are made of. If the code is trying to write into a random index of an array of size 10, for example, with the correct RNG seed the game will write to index −8 instead. You would need to find a place in the code where random is called and its return value used in the address of a subsequent write, with either the value written or the modulus v being usefully controllable. You'd likely get only one chance, unless there is way to re-seed the RNG, because it's only one point in the RNG's period where this happens.