[cfinck] 68991: [SKIPLIST] The Park-Miller Lehmer Random Number Generator only outputs 31 uniformly distributed random bits. Bit 32 is always zero. Fix the code accordingly. This limits the maximum...

Author: cfinck
Date: Fri Sep  4 14:03:00 2015
New Revision: 68991

URL: http://svn.reactos.org/svn/reactos?rev=68991&view=rev
Log:
[SKIPLIST]
The Park-Miller Lehmer Random Number Generator only outputs 31 uniformly distributed
random bits. Bit 32 is always zero.
Fix the code accordingly.

This limits the maximum number of Skiplist levels to 31, but we only use 16 anyway so
far.

Modified:
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h

Modified: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c	[iso-8859-1]
(original)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c	[iso-8859-1] Fri
Sep  4 14:03:00 2015
@@ -28,11 +28,11 @@
     DWORD dwLevel = 0;
     DWORD dwShifted;
 
-    // Generate 32 uniformly distributed pseudo-random bits using the Park-Miller Lehmer
Minimal Standard Random Number Generator.
+    // Generate 31 uniformly distributed pseudo-random bits using the Park-Miller Lehmer
Minimal Standard Random Number Generator.
     dwRandom = (DWORD)(((ULONGLONG)dwRandom * 48271UL) % 2147483647UL);
 
-    // Shift out (32 - SKIPLIST_LEVELS) bits to the right to have no more than
SKIPLIST_LEVELS bits set.
-    dwShifted = dwRandom >> (32 - SKIPLIST_LEVELS);
+    // Shift out (31 - SKIPLIST_LEVELS) bits to the right to have no more than
SKIPLIST_LEVELS bits set.
+    dwShifted = dwRandom >> (31 - SKIPLIST_LEVELS);
 
     // BitScanForward doesn't operate on a zero input value.
     if (dwShifted)
@@ -42,7 +42,7 @@
         BitScanForward(&dwLevel, dwShifted);
     }
 
-    // dwLevel can't have a value higher than 31 this way, so a CHAR is more than
enough.
+    // dwLevel can't have a value higher than 30 this way, so a CHAR is more than
enough.
     return (CHAR)dwLevel;
 }
 

Modified: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h	[iso-8859-1]
(original)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h	[iso-8859-1] Fri
Sep  4 14:03:00 2015
@@ -8,15 +8,15 @@
 #ifndef _REACTOS_SKIPLIST_H
 #define _REACTOS_SKIPLIST_H
 
-// Define SKIPLIST_LEVELS to a value between 1 and 32 before including this header.
+// Define SKIPLIST_LEVELS to a value between 1 and 31 before including this header.
 // This specifies the maximum number of levels you want your Skiplist to have.
 // A value of X is recommended for handling up to 2^X elements.
 #ifndef SKIPLIST_LEVELS
-#error Please define SKIPLIST_LEVELS to a value between 1 and 32.
+#error Please define SKIPLIST_LEVELS to a value between 1 and 31.
 #endif
 
 C_ASSERT(SKIPLIST_LEVELS >= 1);
-C_ASSERT(SKIPLIST_LEVELS <= 32);
+C_ASSERT(SKIPLIST_LEVELS <= 31);
 
 // Function pointer definitions
 typedef PVOID (WINAPI *PSKIPLIST_ALLOCATE_ROUTINE)(DWORD);