[Qemu-devel] [PATCH pic32 v3 02/16] pic32: use LCG algorithm for generated random index of TLBWR instruction

[Serge Vakulenko <serge.vakulenko@gmail.com>]

The LFSR algorithm, used for generating random TLB indexes for TLBWR instruction,
was inclined to produce a degenerate sequence in some cases.
For example, for 16-entry TLB size and Wired=1, it gives: 15, 6, 7, 2,
7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2...
When replaced with LCG algorithm from ISO/IEC 9899 standard, the sequence
looks much better, with about the same computational effort needed.

Signed-off-by: Serge Vakulenko <serge.vakulenko@gmail.com>
---
 hw/mips/cputimer.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/hw/mips/cputimer.c b/hw/mips/cputimer.c
index 75917cf..58707ed 100644
--- a/hw/mips/cputimer.c
+++ b/hw/mips/cputimer.c
@@ -28,13 +28,16 @@
 /* XXX: do not use a global */
 uint32_t cpu_mips_get_random (CPUMIPSState *env)
 {
-    static uint32_t lfsr = 1;
+    static uint32_t seed = 1;
     static uint32_t prev_idx = 0;
     uint32_t idx;
     /* Don't return same value twice, so get another value */
     do {
-        lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u);
-        idx = lfsr % (env->tlb->nb_tlb - env->CP0_Wired) + env->CP0_Wired;
+        /* Use a simple algorithm of Linear Congruential Generator
+         * from ISO/IEC 9899 standard. */
+        seed = 1103515245 * seed + 12345;
+        idx = (seed >> 16) % (env->tlb->nb_tlb - env->CP0_Wired) +
+            env->CP0_Wired;
     } while (idx == prev_idx);
     prev_idx = idx;
     return idx;
-- 
2.2.2