[PATCH v6 2/2] ntdll: Fix integer overflow in RtlUniform.

[Jinoh Kang]

From: Jinoh Kang

The integer overflow bug in RtlUniform has been fixed since Windows
Vista.  Synchronize Wine's version accordingly.
---
 dlls/ntdll/rtl.c       | 60 ++++++++++++++++++++++++++----------------
 dlls/ntdll/tests/rtl.c |  6 -----
 2 files changed, 38 insertions(+), 28 deletions(-)

diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c
index 84488ea1d81..ba8df59eb25 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,44 @@ __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 */
+    /* 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 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).
+     */
+
+    /* 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.  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;
+
+    /* This produces an integer in the range [0, 0x7fffffff]. */
+    result = (result & 0x7fffffffu) + (result >> 31);
+
+    /* If result is 0x7fffffff, set it to 0. */
+    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);