From: Jinoh Kang jinoh.kang.kr@gmail.com
The integer overflow bug in RtlUniform has been fixed since Windows Vista. Synchronize Wine's version accordingly. --- dlls/ntdll/rtl.c | 73 +++++++++++++++++++++++++++++------------- dlls/ntdll/tests/rtl.c | 6 ---- 2 files changed, 51 insertions(+), 28 deletions(-)
diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 84488ea1d81..0068e78a575 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -684,7 +684,7 @@ __ASM_FASTCALL_FUNC(RtlUshortByteSwap, 4, /************************************************************************* * RtlUniform [NTDLL.@] * - * Generates an uniform random number + * Generates a uniform random number * * PARAMS * seed [O] The seed of the Random function @@ -693,12 +693,7 @@ __ASM_FASTCALL_FUNC(RtlUshortByteSwap, 4, * It returns a random number uniformly distributed over [0..MAXLONG-1]. * * NOTES - * Generates an uniform random number using D.H. Lehmer's 1948 algorithm. - * In our case the algorithm is: - * - *| result = (*seed * 0x7fffffed + 0x7fffffc3) % MAXLONG; - *| - *| *seed = result; + * Generates a uniform random number using a linear congruential generator. * * DIFFERENCES * The native documentation states that the random number is @@ -708,23 +703,57 @@ __ASM_FASTCALL_FUNC(RtlUshortByteSwap, 4, */ ULONG WINAPI RtlUniform (PULONG seed) { + ULONGLONG product; ULONG result;
- /* - * Instead of the algorithm stated above, we use the algorithm - * below, which is totally equivalent (see the tests), but does - * not use a division and therefore is faster. - */ - result = *seed * 0xffffffed + 0x7fffffc3; - if (result == 0xffffffff || result == 0x7ffffffe) { - result = (result + 2) & MAXLONG; - } else if (result == 0x7fffffff) { - result = 0; - } else if ((result & 0x80000000) == 0) { - result = result + (~result & 1); - } else { - result = (result + (result & 1)) & MAXLONG; - } /* if */ + /* The algorithm below is equivalent to the following expression: + * + * result = ((ULONGLONG)*seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; + * return (*seed = result); + */ + + /* This produces an integer in the range [0, 0x120000002a]. */ + product = (ULONGLONG)*seed * 18 + 60; + + /* We want to compute the following without using a 64-bit integer modulo + * operation, for better performance (especially on 32-bit architectures): + * + * result = product % ((1u << 31) - 1); + * + * We can replace the modulo with addition and bitwise operations using the + * following identity: + * + * a * (2^31) + b = a + b (mod 2^31 - 1) + * + * This identity holds since 2^31 is congruent to 1 (mod 2^31 - 1). + */ + + /* Perform the 1st round of the modulus calculation. + * This produces an integer in the range [0, 0x8000001c]. + * + * Note that `product` is always less than 2^63 (i.e. MSB is unset). + */ + result = ((ULONG)product & 0x7fffffffu) + (ULONG)(product >> 31); + + /* Negate the result, modulo 2^31 - 1. If we negate the multiplier and + * increment instead, this will result in a product that is too large for + * the 32-bit addition above to handle. + * + * This produces an integer in the range [0x7fffffe2, 0xfffffffe]. + */ + result = 0x7fffffffu * 2 - result; + + /* Perform the 2nd round of the modulus calculation. + * This produces an integer in the range [0, 0x7fffffff]. + */ + result = (result & 0x7fffffffu) + (result >> 31); + + /* If result is 0x7fffffff, set it to 0. We avoid branching here so that + * RtlUniform runs in near-constant time. This also avoids unexpected + * performance hit due to polluted branch target buffer. + */ + result &= -((0x7fffffffu * 2 - result) >> 31); + *seed = result; return result; } diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index 3a308b38499..493cdc92cac 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -425,7 +425,6 @@ static void test_RtlUniform(void) expected = 0x7fffffb1; result = RtlUniform(&seed);
- todo_wine ok(result == expected, "RtlUniform(&seed (seed == 0x80000000)) returns %lx, expected %lx\n", result, expected); @@ -438,7 +437,6 @@ static void test_RtlUniform(void) seed = 0x7fffffff; expected = 0x7fffffc3; result = RtlUniform(&seed); - todo_wine ok(result == expected, "RtlUniform(&seed (seed == 0x7fffffff)) returns %lx, expected %lx\n", result, expected); @@ -468,11 +466,9 @@ static void test_RtlUniform(void) seed = num; expected = ((ULONGLONG)seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; result = RtlUniform(&seed); - todo_wine_if(num >= 2) ok(result == expected, "test: RtlUniform(&seed (seed == %lx)) returns %lx, expected %lx\n", num, result, expected); - todo_wine_if(num >= 2) ok(seed == expected, "test: RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", num, result, expected); @@ -485,11 +481,9 @@ static void test_RtlUniform(void) expected = ((ULONGLONG)seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; seed_bak = seed; result = RtlUniform(&seed); - todo_wine_if(seed_bak >= 2) ok(result == expected, "test: %ld RtlUniform(&seed (seed == %lx)) returns %lx, expected %lx\n", num, seed_bak, result, expected); - todo_wine_if(seed_bak >= 2) ok(seed == expected, "test: %ld RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", num, seed_bak, result, expected);