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 | 52 ++++++++++++++++++++++++------------------ dlls/ntdll/tests/rtl.c | 6 ----- 2 files changed, 30 insertions(+), 28 deletions(-)
diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 11067f44941..11b346796aa 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -706,7 +706,7 @@ __ASM_GLOBAL_FUNC(NTDLL_RtlUshortByteSwap, /************************************************************************* * RtlUniform [NTDLL.@] * - * Generates an uniform random number + * Generates a uniform random number * * PARAMS * seed [O] The seed of the Random function @@ -715,12 +715,7 @@ __ASM_GLOBAL_FUNC(NTDLL_RtlUshortByteSwap, * 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 @@ -730,23 +725,36 @@ __ASM_GLOBAL_FUNC(NTDLL_RtlUshortByteSwap, */ 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 */ + product = (ULONGLONG)*seed * 0x7fffffed + 0x7fffffc3; + + /* + * The following is equivalent to: + * + * result = (product & ((1ui64 << 63) - 1)) % ((1u << 31) - 1); + * + * Since product is never greater than 2^63, it is the same as: + * + * result = product % ((1u << 31) - 1); + * + * This is due to the following identity: + * + * a * (2^31) + b = a + b (mod 2^31 - 1) + * + * because 2^31 is congruent to 1 (mod 2^31 - 1). + */ + + /* The 1st iteration produces an integer in the range [0, 0xffffffff]. */ + result = ((ULONG)product & 0x7fffffff) + (ULONG)(product >> 31); + + /* The 2nd iteration produces an integer in the range [0, 0x80000000]. */ + result = (result & 0x7fffffff) + (result >> 31); + + /* The 3rd iteration produces an integer in the range [0, 0x7fffffff]. */ + result = (result & 0x7fffffff) + (result >> 31); + *seed = result; return result; } diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index e894384c408..4a6a0b6e77b 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -380,7 +380,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); @@ -393,7 +392,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); @@ -423,11 +421,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); @@ -440,11 +436,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);