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 | 51 ++++++++++++++++++++++++------------------ dlls/ntdll/tests/rtl.c | 6 ----- 2 files changed, 29 insertions(+), 28 deletions(-)
diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 84488ea1d81..25c733c2df0 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,35 @@ __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 */ + product = (ULONGLONG)*seed * 0x7fffffed + 0x7fffffc3; + + /* We want to compute the following without using a 64-bit integer modulo + * operation, for better performance 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). + */ + + /* The 1st iteration produces an integer in the range [0, 0xffffffff] + * Note that `product` is always less than 2^63 (i.e. MSB is unset). + */ + 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 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);