[PATCH v2 0/2] MR821: Fix integer overflow bug in RtlUniform which has been fixed in Windows since Vista

[Jinoh Kang (＠iamahuman)]

This MR accomplishes two things:

1. It removes unused obsolete tests for Windows XP or earlier.
2. It synchronizes RtlUniform so that it matches that of Windows Vista or later.

--
  v2: ntdll: Fix integer overflow in RtlUniform.

https://gitlab.winehq.org/wine/wine/-/merge_requests/821

[PATCH v2 1/2] ntdll/tests: Update test_RtlUniform to match Windows Vista or later.

[Jinoh Kang]

From: Jinoh Kang

RtlUniform, a linear congruential generator, could overflow before
computing the modulo.  This bug has been fixed since Windows Vista.
---
 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 2e0bfb650e4..62cdd75f341 100644
--- a/dlls/ntdll/tests/rtl.c
+++ b/dlls/ntdll/tests/rtl.c
@@ -336,293 +336,119 @@ static void test_RtlUlonglongByteSwap(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 actually 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) % MAXLONG;
         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 ...
- */
 }

[PATCH v2 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       | 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..1f068b1e89f 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)
+     *
+     * since 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 62cdd75f341..0c38f4c6bb3 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) % MAXLONG;
         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);