[PATCH v8 0/2] MR821: Replace obsolete RtlUniform tests that no longer work (currently skipped) since Windows Vista; update RtlUniform impl.
Today, test_RtlUniform() skips almost all of its tests on Windows Vista or later. The skipped tests only succeed in Windows XP, and fail on Windows Vista or later. This is because RtlUniform()'s behavior has changed, presumably due to a bug fix shipped in Windows Vista. It appears that RtlUniform, a linear congruential generator, could overflow before computing the modulo in WindoWs XP. This is no longer the case in Windows Vista or later. Meanwhile, we no longer support Windows XP behavior and thus do not test for it regularly; therefore, the tests are obsolete as of 2023. Remove obsolete tests that no longer work with any of the Windows versions actively tested by WineHQ (as of 2023), and replace them with updated tests that works in the Windows versions from Vista up to 10. Also, fix Wine's RtlUniform() to match the new behavior accordingly. -- v8: ntdll: Fix integer overflow in RtlUniform. https://gitlab.winehq.org/wine/wine/-/merge_requests/821
From: Jinoh Kang <jinoh.kang.kr(a)gmail.com> Today, test_RtlUniform() skips almost all of its tests on Windows Vista or later. The skipped tests only succeed in Windows XP, and fail on Windows Vista or later. This is because RtlUniform()'s behavior has changed, presumably due to a bug fix shipped in Windows Vista. It appears that RtlUniform, a linear congruential generator, could overflow before computing the modulo in WindoWs XP. This is no longer the case in Windows Vista or later. Meanwhile, we no longer support Windows XP behavior and thus do not test for it regularly; therefore, the tests are obsolete as of 2023. Remove obsolete tests that no longer work with any of the Windows versions actively tested by WineHQ (as of 2023), and replace them with updated tests that works in the Windows versions from Vista up to 10. --- dlls/ntdll/tests/rtl.c | 330 ++++++++++------------------------------- 1 file changed, 78 insertions(+), 252 deletions(-) diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index a7c43a46e07..3a308b38499 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -381,293 +381,119 @@ static void test_RtlByteSwap(void) static void test_RtlUniform(void) { - ULONGLONG num; + const ULONG step = 0x7fff; + ULONG num; ULONG seed; ULONG seed_bak; ULONG expected; ULONG result; -/* - * According to the documentation RtlUniform is using D.H. Lehmer's 1948 - * algorithm. This algorithm is: - * - * seed = (seed * const_1 + const_2) % const_3; - * - * According to the documentation the random number is distributed over - * [0..MAXLONG]. Therefore const_3 is MAXLONG + 1: - * - * seed = (seed * const_1 + const_2) % (MAXLONG + 1); - * - * Because MAXLONG is 0x7fffffff (and MAXLONG + 1 is 0x80000000) the - * algorithm can be expressed without division as: - * - * seed = (seed * const_1 + const_2) & MAXLONG; - * - * To find out const_2 we just call RtlUniform with seed set to 0: - */ + /* + * According to the documentation RtlUniform is using D.H. Lehmer's 1948 + * algorithm. We assume a more generic version of this algorithm, + * which is the linear congruential generator (LCG). Its formula is: + * + * X_(n+1) = (a * X_n + c) % m + * + * where a is the multiplier, c is the increment, and m is the modulus. + * + * According to the documentation, the random numbers are distributed over + * [0..MAXLONG]. Therefore, the modulus is MAXLONG + 1: + * + * X_(n+1) = (a * X_n + c) % (MAXLONG + 1) + * + * To find out the increment, we just call RtlUniform with seed set to 0. + * This reveals c = 0x7fffffc3. + */ seed = 0; expected = 0x7fffffc3; result = RtlUniform(&seed); ok(result == expected, "RtlUniform(&seed (seed == 0)) returns %lx, expected %lx\n", result, expected); -/* - * The algorithm is now: - * - * seed = (seed * const_1 + 0x7fffffc3) & MAXLONG; - * - * To find out const_1 we can use: - * - * const_1 = RtlUniform(1) - 0x7fffffc3; - * - * If that does not work a search loop can try all possible values of - * const_1 and compare to the result to RtlUniform(1). - * This way we find out that const_1 is 0xffffffed. - * - * For seed = 1 the const_2 is 0x7fffffc4: - */ - seed = 1; - expected = seed * 0xffffffed + 0x7fffffc3 + 1; - result = RtlUniform(&seed); - ok(result == expected, - "RtlUniform(&seed (seed == 1)) returns %lx, expected %lx\n", - result, expected); -/* - * For seed = 2 the const_2 is 0x7fffffc3: - */ - seed = 2; - expected = seed * 0xffffffed + 0x7fffffc3; - result = RtlUniform(&seed); - -/* - * Windows Vista uses different algorithms, so skip the rest of the tests - * until that is figured out. Trace output for the failures is about 10.5 MB! - */ - - if (result == 0x7fffff9f) { - skip("Most likely running on Windows Vista which uses a different algorithm\n"); - return; - } - - ok(result == expected, - "RtlUniform(&seed (seed == 2)) returns %lx, expected %lx\n", - result, expected); -/* - * More tests show that if seed is odd the result must be incremented by 1: - */ - seed = 3; - expected = seed * 0xffffffed + 0x7fffffc3 + (seed & 1); + /* + * The formula is now: + * + * X_(n+1) = (a * X_n + 0x7fffffc3) % (MAXLONG + 1) + * + * If the modulus is correct, RtlUniform(0) shall equal RtlUniform(MAXLONG + 1). + * However, testing reveals that this is not the case. + * That is, the modulus in the documentation is incorrect. + */ + seed = 0x80000000U; + expected = 0x7fffffb1; result = RtlUniform(&seed); - ok(result == expected, - "RtlUniform(&seed (seed == 3)) returns %lx, expected %lx\n", - result, expected); - seed = 0x6bca1aa; - expected = seed * 0xffffffed + 0x7fffffc3; - result = RtlUniform(&seed); + todo_wine ok(result == expected, - "RtlUniform(&seed (seed == 0x6bca1aa)) returns %lx, expected %lx\n", + "RtlUniform(&seed (seed == 0x80000000)) returns %lx, expected %lx\n", result, expected); - seed = 0x6bca1ab; - expected = seed * 0xffffffed + 0x7fffffc3 + 1; - result = RtlUniform(&seed); - ok(result == expected, - "RtlUniform(&seed (seed == 0x6bca1ab)) returns %lx, expected %lx\n", - result, expected); -/* - * When seed is 0x6bca1ac there is an exception: - */ - seed = 0x6bca1ac; - expected = seed * 0xffffffed + 0x7fffffc3 + 2; - result = RtlUniform(&seed); - ok(result == expected, - "RtlUniform(&seed (seed == 0x6bca1ac)) returns %lx, expected %lx\n", - result, expected); -/* - * Note that up to here const_3 is not used - * (the highest bit of the result is not set). - * - * Starting with 0x6bca1ad: If seed is even the result must be incremented by 1: - */ - seed = 0x6bca1ad; - expected = (seed * 0xffffffed + 0x7fffffc3) & MAXLONG; + /* + * We try another value for modulus, say MAXLONG. + * We discover that RtlUniform(0) equals RtlUniform(MAXLONG), which means + * the correct value for the modulus is actually MAXLONG. + */ + seed = 0x7fffffff; + expected = 0x7fffffc3; result = RtlUniform(&seed); + todo_wine ok(result == expected, - "RtlUniform(&seed (seed == 0x6bca1ad)) returns %lx, expected %lx\n", + "RtlUniform(&seed (seed == 0x7fffffff)) returns %lx, expected %lx\n", result, expected); - seed = 0x6bca1ae; - expected = (seed * 0xffffffed + 0x7fffffc3 + 1) & MAXLONG; + /* + * The formula is now: + * + * X_(n+1) = (a * X_n + 0x7fffffc3) % MAXLONG + * + * To find out the multiplier we can use: + * + * a = RtlUniform(1) - 0x7fffffc3 (mod MAXLONG) + * + * This way, we find out that a = -18 (mod MAXLONG), + * which is congruent to 0x7fffffed (MAXLONG - 18). + */ + seed = 1; + expected = ((ULONGLONG)seed * 0x7fffffed + 0x7fffffc3) % MAXLONG; result = RtlUniform(&seed); ok(result == expected, - "RtlUniform(&seed (seed == 0x6bca1ae)) returns %lx, expected %lx\n", + "RtlUniform(&seed (seed == 1)) returns %lx, expected %lx\n", result, expected); -/* - * There are several ranges where for odd or even seed the result must be - * incremented by 1. You can see this ranges in the following test. - * - * For a full test use one of the following loop heads: - * - * for (num = 0; num <= 0xffffffff; num++) { - * seed = num; - * ... - * - * seed = 0; - * for (num = 0; num <= 0xffffffff; num++) { - * ... - */ - seed = 0; - for (num = 0; num <= 100000; num++) { - expected = seed * 0xffffffed + 0x7fffffc3; - if (seed < 0x6bca1ac) { - expected = expected + (seed & 1); - } else if (seed == 0x6bca1ac) { - expected = (expected + 2) & MAXLONG; - } else if (seed < 0xd79435c) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x1435e50b) { - expected = expected + (seed & 1); - } else if (seed < 0x1af286ba) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x21af2869) { - expected = expected + (seed & 1); - } else if (seed < 0x286bca18) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x2f286bc7) { - expected = expected + (seed & 1); - } else if (seed < 0x35e50d77) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x3ca1af26) { - expected = expected + (seed & 1); - } else if (seed < 0x435e50d5) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x4a1af284) { - expected = expected + (seed & 1); - } else if (seed < 0x50d79433) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x579435e2) { - expected = expected + (seed & 1); - } else if (seed < 0x5e50d792) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x650d7941) { - expected = expected + (seed & 1); - } else if (seed < 0x6bca1af0) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x7286bc9f) { - expected = expected + (seed & 1); - } else if (seed < 0x79435e4e) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x7ffffffd) { - expected = expected + (seed & 1); - } else if (seed < 0x86bca1ac) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed == 0x86bca1ac) { - expected = (expected + 1) & MAXLONG; - } else if (seed < 0x8d79435c) { - expected = expected + (seed & 1); - } else if (seed < 0x9435e50b) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0x9af286ba) { - expected = expected + (seed & 1); - } else if (seed < 0xa1af2869) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xa86bca18) { - expected = expected + (seed & 1); - } else if (seed < 0xaf286bc7) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed == 0xaf286bc7) { - expected = (expected + 2) & MAXLONG; - } else if (seed < 0xb5e50d77) { - expected = expected + (seed & 1); - } else if (seed < 0xbca1af26) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xc35e50d5) { - expected = expected + (seed & 1); - } else if (seed < 0xca1af284) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xd0d79433) { - expected = expected + (seed & 1); - } else if (seed < 0xd79435e2) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xde50d792) { - expected = expected + (seed & 1); - } else if (seed < 0xe50d7941) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xebca1af0) { - expected = expected + (seed & 1); - } else if (seed < 0xf286bc9f) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else if (seed < 0xf9435e4e) { - expected = expected + (seed & 1); - } else if (seed < 0xfffffffd) { - expected = (expected + (~seed & 1)) & MAXLONG; - } else { - expected = expected + (seed & 1); - } /* if */ - seed_bak = seed; + num = 2; + do + { + seed = num; + expected = ((ULONGLONG)seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; result = RtlUniform(&seed); + todo_wine_if(num >= 2) ok(result == expected, - "test: 0x%s RtlUniform(&seed (seed == %lx)) returns %lx, expected %lx\n", - wine_dbgstr_longlong(num), seed_bak, result, expected); + "test: RtlUniform(&seed (seed == %lx)) returns %lx, expected %lx\n", + num, result, expected); + todo_wine_if(num >= 2) ok(seed == expected, - "test: 0x%s RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", - wine_dbgstr_longlong(num), seed_bak, result, expected); - } /* for */ -/* - * Further investigation shows: In the different regions the highest bit - * is set or cleared when even or odd seeds need an increment by 1. - * This leads to a simplified algorithm: - * - * seed = seed * 0xffffffed + 0x7fffffc3; - * if (seed == 0xffffffff || seed == 0x7ffffffe) { - * seed = (seed + 2) & MAXLONG; - * } else if (seed == 0x7fffffff) { - * seed = 0; - * } else if ((seed & 0x80000000) == 0) { - * seed = seed + (~seed & 1); - * } else { - * seed = (seed + (seed & 1)) & MAXLONG; - * } - * - * This is also the algorithm used for RtlUniform of wine (see dlls/ntdll/rtl.c). - * - * Now comes the funny part: - * It took me one weekend, to find the complicated algorithm and one day more, - * to find the simplified algorithm. Several weeks later I found out: The value - * MAXLONG (=0x7fffffff) is never returned, neither with the native function - * nor with the simplified algorithm. In reality the native function and our - * function return a random number distributed over [0..MAXLONG-1]. Note - * that this is different from what native documentation states [0..MAXLONG]. - * Expressed with D.H. Lehmer's 1948 algorithm it looks like: - * - * seed = (seed * const_1 + const_2) % MAXLONG; - * - * Further investigations show that the real algorithm is: - * - * seed = (seed * 0x7fffffed + 0x7fffffc3) % MAXLONG; - * - * This is checked with the test below: - */ + "test: RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", + num, result, expected); + + num += step; + } while (num >= 2 + step); + seed = 0; for (num = 0; num <= 100000; num++) { - expected = (seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; + expected = ((ULONGLONG)seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff; seed_bak = seed; result = RtlUniform(&seed); + todo_wine_if(seed_bak >= 2) ok(result == expected, - "test: 0x%s RtlUniform(&seed (seed == %lx)) returns %lx, expected %lx\n", - wine_dbgstr_longlong(num), seed_bak, 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: 0x%s RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", - wine_dbgstr_longlong(num), seed_bak, result, expected); + "test: %ld RtlUniform(&seed (seed == %lx)) sets seed to %lx, expected %lx\n", + num, seed_bak, result, expected); } /* for */ -/* - * More tests show that RtlUniform does not return 0x7ffffffd for seed values - * in the range [0..MAXLONG-1]. Additionally 2 is returned twice. This shows - * that there is more than one cycle of generated randon numbers ... - */ } -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/821
From: Jinoh Kang <jinoh.kang.kr(a)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); -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/821
v8: - Fixed tests when `seed > 0x7fffffff`. - Add more comments to clarify the code. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/821#note_22491
participants (2)
-
Jinoh Kang -
Jinoh Kang (＠iamahuman)